الگوریتمهای Ls

[nibble]

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

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

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

برای انجام این كار ،روترها بسته های echo را روی شبكه ارسال میكنند. هر روتری كه این بسته ها را دریافت میكند با یك بسته echo reply به آن پاسخ میدهد.با تقسیم زمان مسیر رفت و برگشت به دو،روترها میتوانند زمان تاخیر را محاسبه كنند.(زمان مسیر رفت و برگشت،سنجشی از تاخیر فعلی روی یك شبكه میباشد)توجه داشته باشید كه این زمان شامل زمانهای ارسال و پردازش میباشد.

اطلاعات خود را در مورد شبكه،برای استفاده سایر روترها منتشر نموده و اطلاعات روترهای دیگر را دریافت كند.

در این مرحله همه روترها دانش خود را با روتر های دیگر به اشتراك گذاشته و اطلاعات مربوط به شبكه را با یكدیگر مبادله میكنند.با این روش هر روتر میتواند در مورد ساختار و وضعیت شبكه اطلاعات كافی بدست آورد.

با استفاده از این الگوریتم مناسب،بهترین مسیر بین هر دو گره از شبكه راشناسایی كند.

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

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

روتر گرافی از شبكه را ایجاد نموده و گره های منبع و مقصد(برای مثال V1 وV2)را شناسایی میكند.سپس یك ماتریس به نام ماتریس adjacency را میسازد.در این ماتریس یك مختصه مبین Weight میباشد.برای مثا
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 دارای تعدادی روتر میباشد.مسیریابی سلسله مراتبی به طور وسیعی در مسیریابی اینترنت مورد استفاده قرار میگیرد و استفاده از چندین پروتكل مسیریابی را ممكن می سازد.