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

لینک دانلود و خرید پایین توضیحات

فرمت فایل word  و قابل ویرایش و پرینت

تعداد صفحات: 14

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

طراحی الگوریتم

اصول عملکرد

روترها از الگوریتمهای مسیریابی،برای یافتن بهترین مسیر تا مقصد استفاده مینمایند هنگامی که ما در مورد بهترین مسیر صحبت میکنیم،پارامترهایی همانند تعداد 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 به