الگو ریتمهای مسیریابی

اصول عملكرد
روترها از الگوریتمهای مسیریابی،برای یافتن بهترین مسیر تا مقصد استفاده مینمایند هنگامی كه ما در مورد بهترین مسیر صحبت میكنیم،پارامترهایی همانند تعداد hopها (مسیری كه یك بسته از یك روتر دیگر در شبكه منتقل میشود).زمان تغییر و هزینه ارتباطی ارسال بسته را در نظر میگیریم.
مبتنی بر اینكه روترها چگونه اطلاعاتی در مورد ساختار یك شبكه جمع آوری مینمایند و نیز تحلیل آنها از اطلاعات برای تعیین بهترین مسیر،ما دو الگوریتم مسیر یابی اصلی را در اختیار داریم:الگوریتم مسیر یابی عمومی و الگوریتمهای مسیر یابی غیر متمركز.
در الگوریتم های مسیر یابی غیر متمركز،هر روتر اطلاعاتی در مورد روترهایی كه مستقیما به آنها متصل میباشند در اختیار دارد. در این روش هر روتر در مورد همه روتر های موجود در شبكه،اطلاعات در اختیار ندارد.این الگوریتمها تحت نام الگوریتمهای (DV (distance vectorمعروف هستند.در الگوریتمهای مسیریابی عمومی،هر روتر اطلاعات كاملی در مورد همه روترهای دیگر شبكه و نیز وضعیت ترافیك شبكه در اختیار دارد.این الگوریتمها تحت نام الگوریتمهای(LS(Link state معروف هستند.ما در ادامه مقاله به بررسی الگوریتمهای LS میپردازیم
الگوریتمهای LS
در الگوریتمهای LS ،هر روتر میبایست مراحل ذیل را به انجام رساند:
روترهای را كه به لحاظ فیزیكی به آنها متصل میباشد را شناسایی نموده و هنگامی كه شروع به كار میكند آدرسهایIP آنها بدست آورد. این روتر ابتدا یك بسته HELLO را روی شبكه ارسال میكند. هر روتری كه این بسته را دریافت میكند از طریق یك پیام كه دارای آدرس IP خود این روتر میباشد به پیام HELLO پاسخ میدهد.
زمان تاخیر مربوط به روترهای مجاور را اندازه گیری نماید(یا هر پارامتر مهم دیگری از شبكه همانند ترافیك متوسط)
برای انجام این كار ،روترها بسته های echo را روی شبكه ارسال میكنند. هر روتری كه این بسته ها را دریافت میكند با یك بسته echo reply به آن پاسخ میدهد.با تقسیم زمان مسیر رفت و برگشت به دو،روترها میتوانند زمان تاخیر را محاسبه كنند.(زمان مسیر رفت و برگشت،سنجشی از تاخیر فعلی روی یك شبكه میباشد)توجه داشته باشید كه این زمان شامل زمانهای ارسال و پردازش میباشد.
اطلاعات خود را در مورد شبكه،برای استفاده سایر روترها منتشر نموده و اطلاعات روترهای دیگر را دریافت كند.
در این مرحله همه روترها دانش خود را با روتر های دیگر به اشتراك گذاشته و اطلاعات مربوط به شبكه را با یكدیگر مبادله میكنند.با این روش هر روتر میتواند در مورد ساختار و وضعیت شبكه اطلاعات كافی بدست آورد.
با استفاده از این الگوریتم مناسب،بهترین مسیر بین هر دو گره از شبكه راشناسایی كند.
در این مرحله،روترها بهترین مسیر تا هر گره را انتخاب میكنند.آنها این كار را با استفاده از یك الگوریتم همانند الگوریتم كوتاهترین مسیر Dijkstra انجام میدهند.در این الگوریتم،یك روتر مبتنی بر اطلاعاتی كه از سایر روترها جمع آوری نموده است،گرافی از شبكه را ایجاد مینماید.این گراف مكان روترهای موجود در شبكه و نقاط پیوند آنها را به یكدیگر نشان میدهد.هر پیوند با یك شماره به نام Costیاweight مشخص میشود.این شماره تابعی از زمان تاخیر،متوسط ترافیك و گاهی اوقات تعداد hopهای بین گره ها میباشد.برای مثال اگر دو پیوند بین یك گره و مقصد وجود داشته باشد،روتر پیوندی با كمترین Weight را انتخاب میكند.
الگوریتم Dijkstra دارای مراحل ذیل میباشد:
روتر گرافی از شبكه را ایجاد نموده و گره های منبع و مقصد(برای مثال V۱ وV۲)را شناسایی میكند.سپس یك ماتریس به نام ماتریس adjacency را میسازد.در این ماتریس یك مختصه مبین Weight میباشد.برای مثال[i,j]،وزن یك پیوند بین Viو Vj میباشد.در صورتی كه هیچ پیوند مستقیمی بین Vi وVj وجود نداشته باشد این وزن (ویت) بصورت infinity در نظر گرفته میشود.
روتر یك مجموعه ركورد وضعیت را برای هر گره روی شبكه ایجاد مینماید این ركورد دارای سه فیلد میباشد:
فیلد Predecessor:اولین فیلدی كه گره قبلی را نشان میدهد.
فیلد Length:فیلد دوم كه جمع وزنهای از منبع تا آن گره را نشان میدهد.فیلد Label:آخرین فیلد كه وضعیت گره را نشان میدهد.هر گره میتواند دارای یك مود وضعیت باشد:tentative یا permanent
روتر،پارامترهای مجموعه ركورد وضعیت برای همه گره ها را آماده سازی اولیه نموده و طول آنها را در حالت infinity و Labelآن را در وضعیت tentative قرار میدهد.
روتر،یك گره T را ایجاد میكند.برای مثال اگر V۱ میبایست گره T منبع باشد،روتر برچسب V۱را در وضعیت permanent قرار میدهد.هنگامی كه یك Label به حالت permanent تغییر میكند دیگر هرگز تغییر نخواهد كرد. یك گره T در واقع یك agent میباشد.
روتر،مجموع ركورد وضعیت مربوط به همه گره های Tentative را كه مستقیما به گره T منبع متصل هستند،روز آمد مینماید.
روتر همه گره های Tentative را بررسی نموده و گرهای را كه وزن آن تا V۱ كمترین مقدار را دارد انتخاب میكند.سپس این گره،گره Tمقصد خواهد بود
اگر این گره،V۲ نباشد(گره مقصد)روتر به مرحله ۵باز میگردد.
اگر این گره V۲ باشد،روتر گره قبلی آن را از مجموع ركورد وضعیت استخراج نموده و این كار را انجام میدهد تا به V۱ برسد،این فرست از گره ها،بهترین مسیر از V۱تاV۲را نشان میدهد.
این مراحل بصورت یك فلوچارت در شكل نشان داده شده است ما از این الگوریتم بعنوان یك مثال در ادامه مقاله استفاده خواهیم نمود.
مثال
الگوریتم Dijkstra
در اینجا ما میخواهیم بهترین مسیر بین گره های A و E را پیدا كنیم همانطور كه میبینید ۶ مسیر بین 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)تغییر كرده است.همچنین از آنجایی كه گره D وزن كمتری دارد،بعنوان گره T انتخاب شده و برچسب آن به وضعیت Permanent تغییر كرده است.
در این مرحله ما هیچ گره Tentative نداریم بنابراین فقط گره T بعدی را شناسایی میكنیم.از آنجایی كه Eدارای كمترین وزن میباشد بعنوان گرهTانتخاب میشود.
E گره مقصد بوده بنابر این كار ما در اینجا تمام میشود.اكنون ما كار شناسایی مسیر را به انتها رسانده ایم.گره قبلی Eگره D،گره B میباشد و گره قبلی B،گره A میباشد.بنابر این بهترین مسیر ABDE است در این مورد وزن كل مسیر،(۱+۲+۱)۴میباشد.
با وجودی كه این الگوریتم بخوبی كار میكند اما آنقدر پیچیده است كه زمان پردازش آن برای روتر طولانی بوده و راندمان شبكه را كاهش میدهد.همچنین اگر یك روتر اطلاعات غلطی را به روترهای دیگر بدهد،همه تصمیمات مسیر یابی نادرست خواهد بود.
الگوریتمهای DV
الگوریتمهای DVبا نامهای الگوریتمهای مسیریابی Bellman-Ford و ford-fulkerson نیز یاد میشوند.در این الگوریتمها،هر روتر دارای یك جدول مسیریابی میباشد كه بهترین مسیر تا هر مقصد را نشان میدهد.یك گراف معمولی و جدول مسیریابی مربوط به روتر G در شكل زیر نشان داده شده است.
همانطور كه در جدول مشاهده میكنید،اگر روتر G بخواهد بسته هایی را به روتر D ارسال كند،میبایست آنها را به روتر H ارسال نماید.هنگامی كه بسته ها به روتر H رسیدند،این روتر جدول خود را بررسی نموده و روی چگونگی ارسال بسته ها به D تصمیم گیری می كند.Destination Weight Line
A ۸ A
B ۲۰ A
C ۲۸ I
D ۲۰ H
E ۱۷ I
F ۳۰ I
G ۱۸ H
H ۱۲ H
I ۱۰ I
J ۰ -
K ۶ K
L ۱۵ K
در الگوریتمهای DV،هر روتر میبایست مراحل ذیل را انجام دهد:
وزن لینكهای مستقیما متصل به آن را اندازه گرفته و این اطلاعات را در جدول خود ذخیره كند.
در یك دوره زمانی خواص،روتر جدول خود را به روترهای مجاور ارسال نموده و جدول مسیریابی هر یك از روترهای مجاور خود را دریافت میكند.
مبتنی بر اطلاعات بدست آمده از جداول مسیریابی روترهای مجاور،جدول خود را روز آمدسازی مینماید.
یكی از مهمترین مشكلات،هنگام كار با الگوریتمهای DV،مشكل ‍Count to infinity اجازه بدهید این مشكل را با ذكر یك مثال روشن كنیم.
همانطور كه در قسمت ذیل نشان داده شده است یك شبكه را در ذهن خود تصور كنید.همانطور كه در این جدول میبینید،فقط یك پیوند بین A و سایر بخشهای شبكه وجود دارد.در اینجا شما میتوانید،این گراف و جدول مسیریابی همه گره ها را مشاهده كنید:
A B C D
A ۰,- ۱,A ۲,B ۳,D
B ۱,B ۰,- ۲,C ۳,D
C ۲,B ۱,C ۰,- ۱,C
D ۳,B ۲,C ۱,D ۰,-
اكنون تصور كنید كه پیوند بین A و B قطع شود.در این هنگام، B جدول خود را تصحیح میكند بعد از یك مدت زمان خاص،روترها جداول خود را مبادله نموده و بنابراین B جدول مسیریابی C را دریافت میكند. از آنجایی كه C نمیداند چه اتفاقی برای پیوند بین A و B رخ داده است این اطلاعات را حفظ میكند.B این جدول را دریافت نموده و فكر میكند كه یك پیوند جداگانه بین Cو A وجود دارد،بنابراین جدول خود را تصحیح نموده مقدار infinity را به ۳ تغییر میدهد.به همین شكل دوباره روترها جداول خود را مبادله میكنند.هنگامی كه C،جدول مسیریابی B را دریافت میكند،مشاهده میكنید كه B وزن پیوند خود تا A را از ۱به ۳ تغییر داده است،بنابراین C ،جدول خود را روزآمد نموده و وزن پیوند خود تا Aرا به ۴ تغییر میدهد.این پروسه تكرار میشود تا همه گره ها وزن پیوند خود را تا A در وضعیت infinity قرار دهند.این وضعیت در جدول زیر نشان داده شده است.
B C D
Sum of weight to A after link cut ∞,A ۲,B ۳,C
Sum of weight to B after ۱st updating ۳,C ۲,B ۳,C
Sum of weight to A after ۲nd updating ۳,C ۴,B ۳,C
Sum of weight to A after ۳rd updating ۵,C ۴,B ۵,C
Sum of weight to A after ۴th updating ۵,C ۶,B ۵,C
Sum of weight to A after ۵th updating ۷,C ۶,B ۷,C
در این روش متخصصین میگویند،الگوریتمهای DV دارای یك سرعت همگرایی پایین هستند.یك روش برای حل این مشكل در مورد روترها،ارسال اطلاعات فقط به روترهایی میباشد كه دارای پیوند انحصاری تا مقصد نیستند.برای مثال در این مورد،C نمیبایست هیچ اطلاعاتی را به گره B در مورد A ارسال كند زیرا B فقط یك مسیر تا A را در اختیار دارد.مسیریابی سلسله مراتبی
همانطور كه شما میبینید،در هر دو الگوریتم LS و DV،هر روتر مجبور به ذخیره نمودن اطلاعات مربوط به روترهای دیگر میباشد.هنگامی كه اندازه شبكه رشد میكند،تعداد روترهای شبكه افزایش می یابد در نتیجه اندازه جداول مسیریابی نیز افزایش می یابد و روترها نمیوانند ترافیك شبكه را به طور موثر كنترل كنند.ما از مسیریابی سلسله مراتبی برای برطرف كردن این مشكل استفاده میكنیم.اجازه بدهید این موضوع با ذكر یك مثال روشن كنیم:
ما از الگوریتمهای DV برای یافتن بهترین مسیر بین گره ها استفاده میكنیم در وضعیت نشان داده شده در ذیل،هر گره از شبكه مجبور به نگهداری یك جدول مسیریابی با ۱۷ ركورد میباشد.در اینجا یك گراف معمولی و جدول مسیریابی مربوط به A ارائه شده است.
Destination Line Weight
A - -
B B ۱
C C ۱
D B ۲
E B ۳
F B ۳
G B ۴
H B ۵
I C ۵
J C ۶
K C ۵
L C ۴
M C ۴
N C ۳
O C ۴
P C ۲
Q C ۳
در مسیریابی سلسله مراتبی،روترها در گروههایی به نام regions طبقه بندی میشوند.هر روتر دارای اطلاعاتی فقط در مورد روترهایی كه در region آنها قرار دارد در اختیار داشته و هیچ گونه اطلاعاتی در مورد region های دیگر ندارند.
در این مثال ما شبكه خود را به پنج region تقسیم میكنیم.اگر A بخواهد بسته ها را به هر روتر در region۲ ارسال كند،آنها را به B ارسال میكند و الی آخر.
Destination Line Weight
A - -
B B ۱
C C ۱
Region ۲ B ۲
Region ۳ C ۲
Region ۴ C ۳
Region ۵ C ۴
در این نوع مسیریابی،جداول را میتوان خلاصه نمود بنابراین راندمان شبكه بهبود مییابد.مثال بالا مسیریابی سلسله مراتبی دو سطحی را نشان میدهد همچنین میتوان از مسیریابی سلسله مراتبی ۳ سطحی و ۴ سطحی استفاده كرد.در مسیریابی سلسله مراتبی ۳سطحی،شبكه به تعدادی كلاستر تقسیم بندی میشود.هر كلاستر متشكل از تعدادی region و هر region دارای تعدادی روتر میباشد.مسیریابی سلسله مراتبی به طور وسیعی در مسیریابی اینترنت مورد استفاده قرار میگیرد و استفاده از چندین پروتكل مسیریابی را ممكن می سازد.

منبع : پویش رایانه