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

مثال
الگوريتم Dijkstra
در اينجا ما ميخواهيم بهترين مسير بين گره هاي A و E را پيدا كنيم همانطور كه ميبينيد ۶ مسير بين 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 تغيير كرده است.