الگوريتم هاي مسيريابي Routing algorithm

[farzadho]

الگوريتم هاي مسيريابي در شبکه هاي کوچک، و در نقاطي که انتقال اطلاعات معمولا مستقيم است، مسيريابي چندان جدي گرفته نمي شود. اما هنگامي که شبکه ها از حالت هاي ايستگاه هاي کاري خارج مي شوند و کمي پيچيده تر مي شوند، در اين حالت، مسيريابي و انتخاب مسير بهينه براي ارسال بسته هاي اطلاعاتي، به يک امر مهم بدل مي شود. در شبکه هاي بزرگ، دستگاه هايي به عنوان مسيرياب1 وجود دارند که عمل مسيريابي را انجام مي دهند.


الگوريتم مسيريابي اي مناسب است که 6 ويژگي زير را داشته باشد: صحت عملکرد2، سادگي3، قابليت اطمينان4، پايداري5، عدالت6 و بهينگي7.


بديهي است که الگوريتمي بهتر است که صحت عملکرد بالايي داشته باشد و در عين حال ساده باشد، اما چه الگوريتمي قابليت اتکاي خوبي دارد؟ الگوريتمي مناسب است که در گذشت زمان، با تغيير نرم افزارها و سخت افزارهاي شبکه و تغيير پروتکل ها، همچنان مسيريابي درستي ارائه دهد. همچنين مهم است که بعد از يک مدت زمان خاص، الگوريتم مسيريابي به حالتي پايدار برسد و همزمان با آن، مسيريابي بهينه اي داشته باشد و در ارسال بسته ها عدالت را رعايت کند.


الگوريتم کوتاه ترين مسير


ساده ترين روش مسيريابي، روش کوتاه ترين مسير است. هدف اصلي از اين الگوريتم، اين است که گراف زيرشبکه را طوري تشکيل بدهيم که در آن هر گره را يک مسيرياب فرض کنيم و هر يال را يک خط ارتباطي ميان دو مسيرياب. در اين حالت، هر يال يک وزن خواهد داشت و با توجه به الگوريتم کوتاه ترين مسير دايجسترا8 مي توان کوتاه ترين مسير ممکن را محاسبه کرد.


الگوريتم سيل آسا


در اين روش، هر بسته ورودي که به يک مسيرياب مي رسد، از تمام کانال هاي خروجي مسيرياب خارج مي شود. بدين ترتيب تعداد زيادي بسته تکراري وجود خواهد داشت و عملا ميزان آن بي نهايت خواهد بود. بنابراين بايد براي خاتمه اين تعداد بسته ها راهکاري انديشيد. راهکارهاي پيشنهادي براي اين روش، استفاده از يک شمارنده گام است. بدين صورت که در سرآيند9 هر بسته يک شمارنده بگذاريم و در هر گام يک شماره از آن کم کنيم تا به صفر برسد و بسته حذف شود. در اين صورت مبدا بايد طول شبکه را بداند و در بدترين حالت، طول شبکه را طولاني ترين فاصله در نظر بگيرد.


يک روش ديگر، استفاده از حالتي نيمه منطقي است. مسيرياب در اين روش، بسته را به تمام کانال هاي خروجي نمي فرستد. بلکه به کانال هايي مي فرستد که احتمال رسيدن آنها به مقصد وجود دارند. در اين صورت اگر بسته اي به سمت غرب بخواهد برود، نبايستي از کانال هاي شرقي مسيرياب استفاده کرد، مگر اينکه مسيرياب از ساختار شبکه مطلع باشد و بداند که اين کانال ها به کجا منتهي مي شوند.


الگوريتم سيل آسا به جز چند مورد خاص، از جمله سيستم هاي توزيعي که عملکردهاي موازي در آنها نياز است، کاربرد علمي ديگري ندارد.


الگوريتم بردار فاصله


در اين روش، مسيرياب ها در خود جدولي (برداري) ذخيره مي کنند با عنوان بردار فاصله که در آن بهترين فاصله تا هر مسيرياب ديگر در شبکه را ذخيره مي کنند. در اين صورت، تصميم گيري بهتري هنگام مسيريابي اتخاذ مي شود. اين جدول ها با اطلاعات مسيرياب هاي همسايه به روز مي شود. هر يک از عناصر اين جدول ها يک درايه دوبخشي دارند که يکي از آنها نشانگر خط خروجي مناسب براي رسيدن به مسيرياب مورد نظر و ديگري تخمين فاصله زماني تا آن مسيرياب است.


الگوريتم حالت لينک


مسيريابي بردار فاصله مسيريابي خوبي بود و حتي در شبکه آرپانت10 تا سال 1979 نيز عملياتي بود، اما دو مشکل اساسي داشت. نخست اينکه معيار تاخير در اين الگوريتم، طول صفي از مسيرياب ها بود و دوم اينکه پهناي باند هر يک از خطوط در محاسبات دخالت داده نمي شد. بنابراين حتي اگر جاي فاصله را با پهناي باند در جداول مسيرياب عوض مي کردند، زمان همگرايي اين مسيرياب ها به يک نتيجه درست، به بي نهايت ميل مي کرد.


الگوريتم حالت لينک، ساده است و مي توان به صورت زير آن را بيان کرد:


1. هر مسيرياب بايد همسايه هاي خود را شناسايي کرده و آدرس هاي شبکه شان را داشته باشد.


2. ميزان هزينه و يا تاخير همسايه هاي خود را بداند.


3. اطلاعاتي که از همسايه ها بدست آورده است را براي تمام مسيرياب هاي ديگر بفرستد.


4. کوتاه ترين مسير براي رسيدن به ديگر مسيرياب ها را محاسبه کند.


شناسايي همسايه ها به اين صورت انجام مي گيرد که پس از راه اندازي مسيرياب (بوت شدن) يک بسته سلام11 به تمام همسايه ها ارسال مي شود. مسيرياب هاي همسايه مشخصات خود را براي اين مسيرياب مي فرستند.


براي تخمين هزينه و تاخير همسايه ها، از بسته اي به نام Echo استفاده مي شود. وقتي مسيرياب اين بسته را براي همسايه مي فرستد، آن مسيرياب فورا بايد پاسخ آن را ارسال کند، پس از محاسبه زمان رفت و برگشت و تقسيم آن بر عدد 2، ميزان نسبي تاخير بدست مي آيد. سپس اين اطلاعات را در قالب بسته اي براي ديگر مسيرياب ها ارسال مي کند تا آنها نيز از وضعيت اين مسيرياب مطلع باشند.


بدين ترتيب هر مسيرياب با دريافت اطلاعات کامل از تمام مسيرياب هاي شبکه، مي تواند همواره بهترين مسير را انتخاب کند و کوتاه ترين مسير ممکن را براي ارسال بسته ها در نظر بگيرد و شش شرط يک الگوريتم را رعايت کند. روش هاي ديگر مسيريابي نيز وجود دارند که به آنها نيز خواهيم پرداخت.


منابع
Andrew S. Tanenbaum, Computer Networks, 4th Edition, Prentice Hall, 2002