کامپیوتر البرز - کرج
تبادل اطلاعات و اطلاع رسانی کامپیوتر در استان البرز - کرجکامپیوتر البرز - کرج
تبادل اطلاعات و اطلاع رسانی کامپیوتر در استان البرز - کرجالگوریتم های مسیر یابی
الگوریتم های مسیر یابی
اصول عملکرد
روترها از الگوریتمهای مسیریابی،برای یافتن بهترین مسیر تا مقصد استفاده مینمایند هنگامی که ما در مورد بهترین مسیر صحبت میکنیم،پارامترهایی همانند تعداد 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 را میسازد.در این ماتریس یک مختصه مبین Weight میباشد.برای مثال[i,j]،وزن یک پیوند بین Viو Vj میباشد.در صورتی که هیچ پیوند مستقیمی بین Vi وVj وجود نداشته باشد این وزن (ویت) بصورت infinity در نظر گرفته میشود.
روتر یک مجموعه رکورد وضعیت را برای هر گره روی شبکه ایجاد مینماید این رکورد دارای سه فیلد میباشد:
فیلد Predecessor:اولین فیلدی که گره قبلی را نشان میدهد.
فیلد Length:فیلد دوم که جمع وزنهای از منبع تا آن گره را نشان میدهد.
فیلد Label:آخرین فیلد که وضعیت گره را نشان میدهد.هر گره میتواند دارای یک مود وضعیت باشد:tentative یا permanent
روتر،پارامترهای مجموعه رکورد وضعیت برای همه گره ها را آماده سازی اولیه نموده و طول آنها را در حالت infinity و Labelآن را در وضعیت tentative قرار میدهد.
روتر،یک گره T را ایجاد میکند.برای مثال اگر V1 میبایست گره T منبع باشد،روتر برچسب V1را در وضعیت permanent قرار میدهد.هنگامی که یک Label به حالت permanent تغییر میکند دیگر هرگز تغییر نخواهد کرد. یک گره T در واقع یک agent میباشد.
روتر،مجموع رکورد وضعیت مربوط به همه گره های Tentative را که مستقیما به گره T منبع متصل هستند،روز آمد مینماید.
روتر همه گره های 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)تغییر کرده است.همچنین از آنجایی که گره D وزن کمتری دارد،بعنوان گره T انتخاب شده و برچسب آن به وضعیت Permanent تغییر کرده است.
در این مرحله ما هیچ گره Tentative نداریم بنابراین فقط گره T بعدی را شناسایی میکنیم.از آنجایی که Eدارای کمترین وزن میباشد بعنوان گرهTانتخاب میشود.
E گره مقصد بوده بنابر این کار ما در اینجا تمام میشود.اکنون ما کار شناسایی مسیر را به انتها رسانده ایم.گره قبلی Eگره D،گره B میباشد و گره قبلی B،گره A میباشد.بنابر این بهترین مسیر ABDE است در این مورد وزن کل مسیر،(1+2+1)4میباشد.
با وجودی که این الگوریتم بخوبی کار میکند اما آنقدر پیچیده است که زمان پردازش آن برای روتر طولانی بوده و راندمان شبکه را کاهش میدهد.همچنین اگر یک روتر اطلاعات غلطی را به روترهای دیگر بدهد،همه تصمیمات مسیر یابی نادرست خواهد بود.
الگوریتمهای DV
الگوریتمهای DVبا نامهای الگوریتمهای مسیریابی Bellman-Ford و ford-fulkerson نیز یاد میشوند.در این الگوریتمها،هر روتر دارای یک جدول مسیریابی میباشد که بهترین مسیر تا هر مقصد را نشان میدهد.یک گراف معمولی و جدول مسیریابی مربوط به روتر G در شکل زیر نشان داده شده است.
همانطور که در جدول مشاهده میکنید،اگر روتر G بخواهد بسته هایی را به روتر D ارسال کند،میبایست آنها را به روتر H ارسال نماید.هنگامی که بسته ها به روتر H رسیدند،این روتر جدول خود را بررسی نموده و روی چگونگی ارسال بسته ها به D تصمیم گیری می کند.
|
Destination |
Weight |
Line |
|
A |
8 |
A |
|
B |
20 |
A |
|
C |
28 |
I |
|
D |
20 |
H |
|
E |
17 |
I |
|
F |
30 |
I |
|
G |
18 |
H |
|
H |
12 |
H |
|
I |
10 |
I |
|
J |
0 |
- |
|
K |
6 |
K |
|
L |
15 |
K |
در الگوریتمهای DV،هر روتر میبایست مراحل ذیل را انجام دهد:
وزن لینکهای مستقیما متصل به آن را اندازه گرفته و این اطلاعات را در جدول خود ذخیره کند.
در یک دوره زمانی خواص،روتر جدول خود را به روترهای مجاور ارسال نموده و جدول مسیریابی هر یک از روترهای مجاور خود را دریافت میکند.
مبتنی بر اطلاعات بدست آمده از جداول مسیریابی روترهای مجاور،جدول خود را روز آمدسازی مینماید.
یکی از مهمترین مشکلات،هنگام کار با الگوریتمهای DV،مشکل Count to infinity اجازه بدهید این مشکل را با ذکر یک مثال روشن کنیم.
همانطور که در قسمت ذیل نشان داده شده است یک شبکه را در ذهن خود تصور کنید.همانطور که در این جدول میبینید،فقط یک پیوند بین A و سایر بخشهای شبکه وجود دارد.در اینجا شما میتوانید،این گراف و جدول مسیریابی همه گره ها را مشاهده کنید:
|
|
A |
B |
C |
D |
|
A |
0,- |
1,A |
2,B |
3,D |
|
B |
1,B |
0,- |
2,C |
3,D |
|
C |
2,B |
1,C |
0,- |
1,C |
|
D |
3,B |
2,C |
1,D |
0,- |
اکنون تصور کنید که پیوند بین A و B قطع شود.در این هنگام، B جدول خود را تصحیح میکند بعد از یک مدت زمان خاص،روترها جداول خود را مبادله نموده و بنابراین B جدول مسیریابی C را دریافت میکند. از آنجایی که C نمیداند چه اتفاقی برای پیوند بین A و B رخ داده است این اطلاعات را حفظ میکند.B این جدول را دریافت نموده و فکر میکند که یک پیوند جداگانه بین Cو A وجود دارد،بنابراین جدول خود را تصحیح نموده مقدار infinity را به 3 تغییر میدهد.به همین شکل دوباره روترها جداول خود را مبادله میکنند.هنگامی که C،جدول مسیریابی B را دریافت میکند،مشاهده میکنید که B وزن پیوند خود تا A را از 1به 3 تغییر داده است،بنابراین C ،جدول خود را روزآمد نموده و وزن پیوند خود تا Aرا به 4 تغییر میدهد.این پروسه تکرار میشود تا همه گره ها وزن پیوند خود را تا A در وضعیت infinity قرار دهند.این وضعیت در جدول زیر نشان داده شده است.
|
|
B |
C |
D |
|
Sum of weight to A after link cut |
∞,A |
2,B |
3,C |
|
Sum of weight to B after 1st updating |
3,C |
2,B |
3,C |
|
Sum of weight to A after 2nd updating |
3,C |
4,B |
3,C |
|
Sum of weight to A after 3rd updating |
5,C |
4,B |
5,C |
|
Sum of weight to A after 4th updating |
5,C |
6,B |
5,C |
|
Sum of weight to A after 5th updating |
7,C |
6,B |
7,C |
در این روش متخصصین میگویند،الگوریتمهای DV دارای یک سرعت همگرایی پایین هستند.یک روش برای حل این مشکل در مورد روترها،ارسال اطلاعات فقط به روترهایی میباشد که دارای پیوند انحصاری تا مقصد نیستند.برای مثال در این مورد،C نمیبایست هیچ اطلاعاتی را به گره B در مورد A ارسال کند زیرا B فقط یک مسیر تا A را در اختیار دارد.
همانطور که شما میبینید،در هر دو الگوریتم LS و DV،هر روتر مجبور به ذخیره نمودن اطلاعات مربوط به روترهای دیگر میباشد.هنگامی که اندازه شبکه رشد میکند،تعداد روترهای شبکه افزایش می یابد در نتیجه اندازه جداول مسیریابی نیز افزایش می یابد و روترها نمیوانند ترافیک شبکه را به طور موثر کنترل کنند.ما از مسیریابی سلسله مراتبی برای برطرف کردن این مشکل استفاده میکنیم.اجازه بدهید این موضوع با ذکر یک مثال روشن کنیم:
ما از الگوریتمهای DV برای یافتن بهترین مسیر بین گره ها استفاده میکنیم در وضعیت نشان داده شده در ذیل،هر گره از شبکه مجبور به نگهداری یک جدول مسیریابی با 17 رکورد میباشد.در اینجا یک گراف معمولی و جدول مسیریابی مربوط به A ارائه شده است.
|
Destination |
Line |
Weight |
|
A |
- |
- |
|
B |
B |
1 |
|
C |
C |
1 |
|
D |
B |
2 |
|
E |
B |
3 |
|
F |
B |
3 |
|
G |
B |
4 |
|
H |
B |
5 |
|
I |
C |
5 |
|
J |
C |
6 |
|
K |
C |
5 |
|
L |
C |
4 |
|
M |
C |
4 |
|
N |
C |
3 |
|
O |
C |
4 |
|
P |
C |
2 |
|
Q |
C |
3 |
در مسیریابی سلسله مراتبی،روترها در گروههایی به نام regions طبقه بندی میشوند.هر روتر دارای اطلاعاتی فقط در مورد روترهایی که در region آنها قرار دارد در اختیار داشته و هیچ گونه اطلاعاتی در مورد region های دیگر ندارند.
در این مثال ما شبکه خود را به پنج region تقسیم میکنیم.اگر A بخواهد بسته ها را به هر روتر در region2 ارسال کند،آنها را به B ارسال میکند و الی آخر.
|
Destination |
Line |
Weight |
|
A |
- |
- |
|
B |
B |
1 |
|
C |
C |
1 |
|
Region 2 |
B |
2 |
|
Region 3 |
C |
2 |
|
Region 4 |
C |
3 |
|
Region 5 |
C |
4 |
در این نوع مسیریابی،جداول را میتوان خلاصه نمود بنابراین راندمان شبکه بهبود مییابد.مثال بالا مسیریابی سلسله مراتبی دو سطحی را نشان میدهد همچنین میتوان از مسیریابی سلسله مراتبی 3 سطحی و 4 سطحی استفاده کرد.در مسیریابی سلسله مراتبی 3سطحی،شبکه به تعدادی کلاستر تقسیم بندی میشود.هر کلاستر متشکل از تعدادی region و هر region دارای تعدادی روتر میباشد.مسیریابی سلسله مراتبی به طور وسیعی در مسیریابی اینترنت مورد استفاده قرار میگیرد و استفاده از چندین پروتکل مسیریابی را ممکن می سازد.
