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

روترها از الگوریتمهای مسیریابی,برای یافتن بهترین مسیر تا مقصد استفاده مینمایند هنگامی كه ما در مورد بهترین مسیر صحبت میكنیم,پارامترهایی همانند تعداد hopها مسیری كه یك بسته از یك روتر دیگر در شبكه منتقل میشود زمان تغییر و هزینه ارتباطی ارسال بسته را در نظر میگیریم

اصول عملكرد

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

---