الگوريتمهاي مسيريابي،براي يافتن بهترين مسيرشبکه

[diamonds55]

اصول عملكرد


روترها از الگوريتمهاي مسيريابي،براي يافتن بهترين مسير تا مقصد استفاده مينمايند
هنگامي آه ما در مورد بهترين مسير صحبت ميكنيم،پارامترهايي همانند تعداد hop ها
( مسيري آه يك بسته از يك روتر ديگر در شبكه منتقل ميشود ). زمان تغيير و هزينه
ارتباطي ارسال بسته را در نظر ميگيريم .


مبتني بر اينكه روترها چگونه اطلاعاتي در مورد ساختار يك شبكه جمع آوري مينمايند و
نيز تحليل آنها از اطلاعات براي تعيين بهترين مسير،ما دو الگوريتم مسير يابي اصلي را
در اختيار داريم : الگوريتم مسير يابي عمومي و الگوريتمهاي مسير يابي غير متمرآز .
در الگوريتم هاي مسير يابي غير متمرآز،هر روتر اطلاعاتي در مورد روترهايي آه
مستقيما به آنها متصل ميباشند در اختيار دارد . در اين روش هر روتر در مورد همه روتر
DV ( هاي موجود در شبكه،اطلاعات در اختيار ندارد . اين الگوريتمها تحت نام الگوريتمهاي
معروف هستند . در الگوريتمهاي مسيريابي عمومي،هر روتر اطلاعات (distance vector
آاملي در مورد همه روترهاي ديگر شبكه و نيز وضعيت ترافيك شبكه در اختيار دارد . اين
الگوريتمها تحت نام الگوريتمهاي LS(Link state) معروف هستند . ما در ادامه مقاله به
بررسي الگوريتمهاي LS ميپردازيم .


LS الگوريتمهاي

در الگوريتمهاي LS ،هر روتر ميبايست مراحل ذيل را به انجام رساند :
روترهاي را آه به لحاظ فيزيكي به آنها متصل ميباشد را شناسايي نموده و هنگامي
آه شروع به آار ميكند آدرسهاي IP آنها بدست آورد . اين روتر ابتدا يك بسته HELLO را
روي شبكه ارسال ميكند . هر روتري آه اين بسته را دريافت ميكند از طريق يك پيام آه
داراي آدرس IP خود اين روتر ميباشد به پيام HELLO پاسخ ميدهد .

مان تاخير مربوط به روترهاي مجاور را اندازه گيري نمايد ( يا هر پارامتر مهم ديگري از
شبكه همانند ترافيك متوسط )

براي انجام اين آار ،روترها بسته هاي echo را روي شبكه ارسال ميكنند . هر روتري آه
اين بسته ها را دريافت ميكند با يك بسته echo reply به آن پاسخ ميدهد . با تقسيم
زمان مسير رفت و برگشت به دو،روترها ميتوانند زمان تاخير را محاسبه آنند .( زمان
مسير رفت و برگشت،سنجشي از تاخير فعلي روي يك شبكه ميباشد ) توجه داشته
باشيد آه اين زمان شامل زمانهاي ارسال و پردازش ميباشد .
اطلاعات خود را در مورد شبكه،براي استفاده ساير روترها منتشر نموده و اطلاعات
روترهاي ديگر را دريافت آند .
در اين مرحله همه روترها دانش خود را با روتر هاي ديگر به اشتراك گذاشته و اطلاعات
مربوط به شبكه را با يكديگر مبادله ميكنند . با اين روش هر روتر ميتواند در مورد ساختار و
وضعيت شبكه اطلاعات آافي بدست آورد .
با استفاده از اين الگوريتم مناسب،بهترين مسير بين هر دو گره از شبكه راشناسايي
آند .
در اين مرحله،روترها بهترين مسير تا هر گره را انتخاب ميكنند . آنها اين آار را با استفاده
از يك الگوريتم همانند الگوريتم آوتاهترين مسير Dijkstra انجام ميدهند . در اين
الگوريتم،يك روتر مبتني بر اطلاعاتي آه از ساير روترها جمع آوري نموده است،گرافي
از شبكه را ايجاد مينمايد . اين گراف مكان روترهاي موجود در شبكه و نقاط پيوند آنها را
به يكديگر نشان ميدهد . هر پيوند با يك شماره به نام Cost يا weight مشخص
ميشود . اين شماره تابعي از زمان تاخير،متوسط ترافيك و گاهي اوقات تعداد hop هاي
بين گره ها ميباشد . براي مثال اگر دو پيوند بين يك گره و مقصد وجود داشته باشد،روتر
پيوندي با آمترين Weight را انتخاب ميكند .

الگوريتم Dijkstra داراي مراحل ذيل ميباشد :

روتر گرافي از شبكه را ايجاد نموده و گره هاي منبع و مقصد ( براي مثال V1 و (V2 را
شناسايي ميكند . سپس يك ماتريس به نام ماتريس adjacency را ميسازد . در اين
Vj وVi ،وزن يك پيوند بين [i,j] ميباشد . براي مثال Weight ماتريس يك مختصه مبين
ميباشد . در صورتي آه هيچ پيوند مستقيمي بين Vi و Vj وجود نداشته باشد اين وزن
( ويت ) بصورت infinity در نظر گرفته ميشود .


روتر يك مجموعه رآورد وضعيت را براي هر گره روي شبكه ايجاد مينمايد اين رآورد
داراي سه فيلد ميباشد :

فيلد Predecessor اولين فيلدي آه گره قبلي را نشان ميدهد .
فيلد Length فيلد دوم آه جمع وزنهاي از منبع تا آن گره را نشان ميدهد .
فيلد Label آخرين فيلد آه وضعيت گره را نشان ميدهد . هر گره ميتواند داراي يك مود
permanent يا tentative: وضعيت باشد
روتر،پارامترهاي مجموعه رآورد وضعيت براي همه گره ها را آماده سازي اوليه نموده و
طول آنها را در حالت infinity و Label آن را در وضعيت tentative قرار ميدهد .
روتر،يك گره T را ايجاد ميكند . براي مثال اگر V1 ميبايست گره T منبع باشد،روتر
برچسب V1 را در وضعيت permanent قرار ميدهد . هنگامي آه يك Label به حالت
agent در واقع يك T تغيير ميكند ديگر هرگز تغيير نخواهد آرد . يك گره permanent
ميباشد .
T را آه مستقيما به گره Tentative روتر،مجموع رآورد وضعيت مربوط به همه گره هاي
منبع متصل هستند،روز آمد مينمايد .
روتر همه گره هاي Tentative را بررسي نموده و گرهاي را آه وزن آن تا V1 آمترين
مقدار را دارد انتخاب ميكند . سپس اين گره،گره T مقصد خواهد بود
اگر اين گره، V2 نباشد ( گره مقصد ) روتر به مرحله 5 باز ميگردد .
اگر اين گره V2 باشد،روتر گره قبلي آن را از مجموع رآورد وضعيت استخراج نموده و اين
آار را انجام ميدهد تا به V1 برسد،اين فرست از گره ها،بهترين مسير از V1 تا V2 را
نشان ميدهد .
اين مراحل بصورت يك فلوچارت در شكل نشان داده شده است ما از اين الگوريتم
بعنوان يك مثال در ادامه مقاله استفاده خواهيم نمود .

مثالDijkstraالگوريتم


در اينجا ما ميخواهيم بهترين مسير بين گره هاي A و E را پيدا آنيم همانطور آه
ميبينيد 6 مسير بين A و E وجود دارد .) ACDBE ، ABDCE ، ACDE ، ABDE ، ACE ، (ABE و
واضح است آه ABDE بهترين مسير ميباشد زيرا آمترين وزن را دارد اما هميشه به اين
سادگي نيست و برخي موارد پيچيده وجود دارد آه در آن ما مجبوريم از الگوريتم هايي
براي يافتن بهترين مسير استفاده آنيم .
همانطور آه در تصوير ذيل مشاهده ميكنيد،گره منبع (A) بعنوان گره T انتخواب شده و
بنابراين برچسب آن، Permanent ميباشد . ( ما گره هاي Permanent را با دايره هاي تو
پر و گره هاي T را با يك پيكان نشان ميدهيم )


در اين مرحله شما ميبينيد آه مجموع رآورد وضعيت گره هاي Tentative آه مستقيما
به گره T (C) ، B متصل شده اند،تغيير يافته است . همچنين از آنجايي آه گره B آمترين
وزن را دارد،بعنوان گره T انتخاب شده و برچسب آن به حالت Permanent تغيير آرده
است .

Tentative در اين مرحله همانند مرحله قبل دو مجموعه رآورد وضعيت گره هايي آه
داراي اتصال مستقيم به گره T ميباشد E) ، (D تغيير آرده است . همچنين از آنجايي آه
Permanent انتخاب شده و برچسب آن به وضعيت T وزن آمتري دارد،بعنوان گره Dگره
تغيير آرده است .

در اين مرحله ما هيچ گره Tentative نداريم بنابراين فقط گره T بعدي را شناسايي
ميكنيم . از آنجايي آه E داراي آمترين وزن ميباشد بعنوان گره T انتخاب ميشود .
گره مقصد بوده بنابر اين آار ما در اينجا تمام ميشود . اآنون ما آار شناسايي مسير را E
به انتها رسانده ايم . گره قبلي E گره D ،گره B ميباشد و گره قبلي B ،گره A ميباشد . بنابر
اين بهترين مسير ABDE است در اين مورد وزن آل مسير، 4(1+2+1) ميباشد .

با وجودي آه اين الگوريتم بخوبي آار ميكند اما آنقدر پيچيده است آه زمان پردازش آن
براي روتر طولاني بوده و راندمان شبكه را آاهش ميدهد . همچنين اگر يك روتر اطلاعات
غلطي را به روترهاي ديگر بدهد،همه تصميمات مسير يابي نادرست خواهد بود .

DVالگوريتمهاي


الگوريتمهاي DV با نامهاي الگوريتمهاي مسيريابي Bellman-Ford و ford-fulkerson نيز
ياد ميشوند . در اين الگوريتمها،هر روتر داراي يك جدول مسيريابي ميباشد آه بهترين
مسير تا هر مقصد را نشان ميدهد . يك گراف معمولي و جدول مسيريابي مربوط به روتر
. در شكل زير نشان داده شده است G

در الگوريتمهاي DV ،هر روتر ميبايست مراحل ذيل را انجام دهد :

وزن لينكهاي مستقيما متصل به آن را اندازه گرفته و اين اطلاعات را در جدول خود
ذخيره آند .
در يك دوره زماني خواص،روتر جدول خود را به روترهاي مجاور ارسال نموده و جدول
مسيريابي هر يك از روترهاي مجاور خود را دريافت ميكند .


مبتني بر اطلاعات بدست آمده از جداول مسيريابي روترهاي مجاور،جدول خود را روز
آمدسازي مينمايد .

Count to infinity ،مشكلDV يكي از مهمترين مشكلات،هنگام آار با الگوريتمهاي
اجازه بدهيد اين مشكل را با ذآر يك مثال روشن آنيم .

همانطور آه در قسمت ذيل نشان داده شده است يك شبكه را در ذهن خود تصور
آنيد . همانطور آه در اين جدول ميبينيد،فقط يك پيوند بين A و ساير بخشهاي شبكه
وجود دارد . در اينجا شما ميتوانيد،اين گراف و جدول مسيريابي همه گره ها را مشاهده
آنيد
D C B A
3,D 2,B 1,A 0,- A
3,D 2,C 0,- 1,B B
1,C 0,- 1,C 2,B C
0,- 1,D 2,C 3,B D

اآنون تصور آنيد آه پيوند بين A و B قطع شود . در اين هنگام، B جدول خود را تصحيح
ميكند بعد از يك مدت زمان خاص،روترها جداول خود را مبادله نموده و بنابراين B جدول
B و A نميداند چه اتفاقي براي پيوند بين C را دريافت ميكند . از آنجايي آه Cمسيريابي
رخ داده است اين اطلاعات را حفظ ميكند B. اين جدول را دريافت نموده و فكر ميكند آه
infinity وجود دارد،بنابراين جدول خود را تصحيح نموده مقدار A وC يك پيوند جداگانه بين
را به 3 تغيير ميدهد . به همين شكل دوباره روترها جداول خود را مبادله ميكنند . هنگامي
آه C ،جدول مسيريابي B را دريافت ميكند،مشاهده ميكنيد آه B وزن پيوند خود تا A را
از 1 به 3 تغيير داده است،بنابراين C ،جدول خود را روزآمد نموده و وزن پيوند خود تا A را
به 4 تغيير ميدهد . اين پروسه تكرار ميشود تا همه گره ها وزن پيوند خود را تا A در
وضعيت infinity قرار دهند . اين وضعيت در جدول زير نشان داده شده است .


D C B

3,C 2,B ∞,A Sum of weight to A after link cut
3,C 2,B 3,C Sum of weight to B after 1st updating
3,C 4,B 3,C Sum of weight to A after 2nd updating
5,C 4,B 5,C Sum of weight to A after 3rd updating
5,C 6,B 5,C Sum of weight to A after 4th updating
7,C 6,B 7,C Sum of weight to A after 5th updating



در اين روش متخصصين ميگويند،الگوريتمهاي DV داراي يك سرعت همگرايي پايين
هستند . يك روش براي حل اين مشكل در مورد روترها،ارسال اطلاعات فقط به روترهايي


ميباشد آه داراي پيوند انحصاري تا مقصد نيستند . براي مثال در اين مورد، C نميبايست
هيچ اطلاعاتي را به گره B در مورد A ارسال آند زيرا B فقط يك مسير تا A را در اختيار
دارد .


مسيريابي سلسله مراتبي

همانطور آه شما ميبينيد،در هر دو الگوريتم LS و DV ،هر روتر مجبور به ذخيره نمودن
اطلاعات مربوط به روترهاي ديگر ميباشد . هنگامي آه اندازه شبكه رشد ميكند،تعداد
روترهاي شبكه افزايش مي يابد در نتيجه اندازه جداول مسيريابي نيز افزايش مي يابد
و روترها نميوانند ترافيك شبكه را به طور موثر آنترل آنند . ما از مسيريابي سلسله
مراتبي براي برطرف آردن اين مشكل استفاده ميكنيم .


مثال نشان داده شده در ذيل،هر گره از شبكه مجبور به نگهداري يك جدول مسيريابي با 17
رآورد ميباشد . در اينجا يك گراف معمولي و جدول مسيريابي مربوط به A ارائه شده
است .


Weight Line Destination
- - A
1 B B
1 C C
2 B D
3 B E
3 B F
4 B G
5 B H
5 C I
J

6 C J
5 C K
4 C L
4 C M
3 C N
4 C O
2 C P
3 C Q


در مسيريابي سلسله مراتبي،روترها در گروههايي به نام regions طبقه بندي
ميشوند . هر روتر داراي اطلاعاتي فقط در مورد روترهايي آه در region آنها قرار دارد در
اختيار داشته و هيچ گونه اطلاعاتي در مورد region هاي ديگر ندارند .
در اين مثال ما شبكه خود را به پنج region تقسيم ميكنيم . اگر A بخواهد بسته ها را به
هر روتر در region2 ارسال آند،آنها را به B ارسال ميكند و الي آخر .
در اين نوع مسيريابي،جداول را ميتوان خلاصه نمود بنابراين راندمان شبكه بهبود
مييابد . مثال بالا مسيريابي سلسله مراتبي دو سطحي را نشان ميدهد همچنين
ميتوان
مسيريابي سلسله مراتبي 3 سطحي،شبكه به تعدادي آلاستر تقسيم بندي
ميشود . هر آلاستر متشكل از تعدادي region و هر region داراي تعدادي روتر
ميباشد . مسيريابي سلسله مراتبي به طور وسيعي در مسيريابي اينترنت مورد
استفاده قرار ميگيرد و استفاده از چندين پروتكل مسيريابي را ممكن مي سازد .