در قالب 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 در نظر گرفته ميشود.