آبجی
21st November 2009, 01:02 PM
در شبکههاي کوچک، و در نقاطي که انتقال اطلاعات معمولا مستقيم است، مسيريابي چندان جدي گرفته نميشود. اما هنگامي که شبکهها از حالتهاي ايستگاههاي کاري خارج ميشوند و کمي پيچيدهتر ميشوند، در اين حالت، مسيريابي و انتخاب مسير بهينه براي ارسال بستههاي اطلاعاتي، به يک امر مهم بدل ميشود. در شبکههاي بزرگ، دستگاههايي بهعنوان مسيرياب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
الگوريتم مسيريابياي مناسب است که 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