الگوريتم هاي مسيريابي Routing algorithm
- مجموعه: مقالات مهندسي > مهندسي كامپيوتر | کلمات کلیدی : الگوريتم+هاي+مسيريابي+Routing+algorithm+
الگوريتم هاي مسيريابي Routing algorithm
الگوریتم های مسیریابی در شبکه های کوچک، و در نقاطی که انتقال اطلاعات معمولا مستقیم است، مسیریابی چندان جدی گرفته نمی شود. اما هنگامی که شبکه ها از حالت های ایستگاه های کاری خارج می شوند و کمی پیچیده تر می شوند، در این حالت، مسیریابی و انتخاب مسیر بهینه برای ارسال بسته های اطلاعاتی، به یک امر مهم بدل می شود. در شبکه های بزرگ، دستگاه هایی به عنوان مسیریاب1 وجود دارند که عمل مسیریابی را انجام می دهند.
الگوریتم مسیریابی ای مناسب است که 6 ویژگی زیر را داشته باشد:
1- صحت عملکرد
2- سادگی
3- قابلیت اطمینان
4- پایداری
5- عدالت
6- بهینگی
بدیهی است که الگوریتمی بهتر است که صحت عملکرد بالایی داشته باشد و در عین حال ساده باشد، اما چه الگوریتمی قابلیت اتکای خوبی دارد؟ الگوریتمی مناسب است که در گذشت زمان، با تغییر نرم افزارها و سخت افزارهای شبکه و تغییر پروتکل ها، همچنان مسیریابی درستی ارائه دهد. همچنین مهم است که بعد از یک مدت زمان خاص، الگوریتم مسیریابی به حالتی پایدار برسد و همزمان با آن، مسیریابی بهینه ای داشته باشد و در ارسال بسته ها عدالت را رعایت کند.
الگوریتم کوتاه ترین مسیر
ساده ترین روش مسیریابی، روش کوتاه ترین مسیر است. هدف اصلی از این الگوریتم، این است که گراف زیرشبکه را طوری تشکیل بدهیم که در آن هر گره را یک مسیریاب فرض کنیم و هر یال را یک خط ارتباطی میان دو مسیریاب. در این حالت، هر یال یک وزن خواهد داشت و با توجه به الگوریتم کوتاه ترین مسیر دایجسترا8 می توان کوتاه ترین مسیر ممکن را محاسبه کرد.
الگوریتم سیل آسا
در این روش، هر بسته ورودی که به یک مسیریاب می رسد، از تمام کانال های خروجی مسیریاب خارج می شود. بدین ترتیب تعداد زیادی بسته تکراری وجود خواهد داشت و عملا میزان آن بی نهایت خواهد بود. بنابراین باید برای خاتمه این تعداد بسته ها راهکاری اندیشید. راهکارهای پیشنهادی برای این روش، استفاده از یک شمارنده گام است. بدین صورت که در سرآیند9 هر بسته یک شمارنده بگذاریم و در هر گام یک شماره از آن کم کنیم تا به صفر برسد و بسته حذف شود. در این صورت مبدا باید طول شبکه را بداند و در بدترین حالت، طول شبکه را طولانی ترین فاصله در نظر بگیرد.
یک روش دیگر، استفاده از حالتی نیمه منطقی است. مسیریاب در این روش، بسته را به تمام کانال های خروجی نمی فرستد. بلکه به کانال هایی می فرستد که احتمال رسیدن آنها به مقصد وجود دارند. در این صورت اگر بسته ای به سمت غرب بخواهد برود، نبایستی از کانال های شرقی مسیریاب استفاده کرد، مگر اینکه مسیریاب از ساختار شبکه مطلع باشد و بداند که این کانال ها به کجا منتهی می شوند.
الگوریتم سیل آسا به جز چند مورد خاص، از جمله سیستم های توزیعی که عملکردهای موازی در آنها نیاز است، کاربرد علمی دیگری ندارد.
الگوریتم بردار فاصله
در این روش، مسیریاب ها در خود جدولی (برداری) ذخیره می کنند با عنوان بردار فاصله که در آن بهترین فاصله تا هر مسیریاب دیگر در شبکه را ذخیره می کنند. در این صورت، تصمیم گیری بهتری هنگام مسیریابی اتخاذ می شود. این جدول ها با اطلاعات مسیریاب های همسایه به روز می شود. هر یک از عناصر این جدول ها یک درایه دوبخشی دارند که یکی از آنها نشانگر خط خروجی مناسب برای رسیدن به مسیریاب مورد نظر و دیگری تخمین فاصله زمانی تا آن مسیریاب است.
الگوریتم حالت لینک
مسیریابی بردار فاصله مسیریابی خوبی بود و حتی در شبکه آرپانت10 تا سال 1979 نیز عملیاتی بود، اما دو مشکل اساسی داشت. نخست اینکه معیار تاخیر در این الگوریتم، طول صفی از مسیریاب ها بود و دوم اینکه پهنای باند هر یک از خطوط در محاسبات دخالت داده نمی شد. بنابراین حتی اگر جای فاصله را با پهنای باند در جداول مسیریاب عوض می کردند، زمان همگرایی این مسیریاب ها به یک نتیجه درست، به بی نهایت میل می کرد.
الگوریتم حالت لینک، ساده است و می توان به صورت زیر آن را بیان کرد:
1. هر مسیریاب باید همسایه های خود را شناسایی کرده و آدرس های شبکه شان را داشته باشد.
2. میزان هزینه و یا تاخیر همسایه های خود را بداند.
3. اطلاعاتی که از همسایه ها بدست آورده است را برای تمام مسیریاب های دیگر بفرستد.
4. کوتاه ترین مسیر برای رسیدن به دیگر مسیریاب ها را محاسبه کند.
شناسایی همسایه ها به این صورت انجام می گیرد که پس از راه اندازی مسیریاب (بوت شدن) یک بسته سلام11 به تمام همسایه ها ارسال می شود. مسیریاب های همسایه مشخصات خود را برای این مسیریاب می فرستند.
برای تخمین هزینه و تاخیر همسایه ها، از بسته ای به نام Echo استفاده می شود. وقتی مسیریاب این بسته را برای همسایه می فرستد، آن مسیریاب فورا باید پاسخ آن را ارسال کند، پس از محاسبه زمان رفت و برگشت و تقسیم آن بر عدد 2، میزان نسبی تاخیر بدست می آید. سپس این اطلاعات را در قالب بسته ای برای دیگر مسیریاب ها ارسال می کند تا آنها نیز از وضعیت این مسیریاب مطلع باشند.
بدین ترتیب هر مسیریاب با دریافت اطلاعات کامل از تمام مسیریاب های شبکه، می تواند همواره بهترین مسیر را انتخاب کند و کوتاه ترین مسیر ممکن را برای ارسال بسته ها در نظر بگیرد و شش شرط یک الگوریتم را رعایت کند. روش های دیگر مسیریابی نیز وجود دارند که به آنها نیز خواهیم پرداخت.
منابع:
Andrew S. Tanenbaum, Computer Networks, 4th Edition, Prentice Hall, 2002
الگوريتم هاي مسيريابي Routing algorithm
کلمات کلیدی : الگوريتم,هاي,مسيريابي,Routing,algorithm,الگوريتم هاي مسيريابي Routing algorithm , مقالات مهندسي , مهندسي كامپيوتر , کامپیوتر، مکانیک، برق، عمران، شیمی، پزشکی الگوريتم+هاي+مسيريابي+Routing+algorithm+
- آخرین مطالب مشاهده شده توسط کاربران :
نویسنده پست : علي
عنوان پست : الگوريتم هاي مسيريابي Routing algorithm
منبع اصلی مطلب سایت :
- الگوريتم هاي مسيريابي Routing algorithm
- زغال فعال شده (Activated Carbon) چیست؟
- جوشكاری ترمیت (Thermit Welding)
- سیستم پایداری الكترونیكی خودرو Electronic Stability Programm...
- آشنایی با پروتکل SSL و عملکرد آن – Secure Socket Layer
- آموزش بازگرداندن ایمیل ارسال شده در Gmail
- از اين راه قارچ ها به پاي شما نفوذ مي کنند!
- نکات مفید برای بالا بردن پیج رنک و افزایش رتبه در موتورهای ج...
- انگور قرمز ضد کلسترول
- دسر شکلاتی با کاکائو
- دردهای قاعدگی بعد از روز سوم را جدی بگیرید
- Captain Shahbazi’s international campaign and his stat...
- آشنایی با پهپاد پرودیتور
- اجزاء، مکانیزم، سیستم، ماشین
- واقعیترین ربات انساننما رونمایی شد
- مغز انسان و آینده صنعت رباتیك
- Subnetting به زبان ساده
- ترکهای سطوح بتنی Cracks in concrete surfaces
- درخواست پیشنهاد یا RFQ چیست؟ Request for Quotation
- رباتها ناجی بیماران اختلال اعصاب
- ثبت پتنت جدید اپل
- دو ابزار هوشمند به درد بخور
- سوسك جاسوس، یك ربات زنده!
- اهمیت پرورش گیاهان دارویی در فضای سبز شهری
- مروری بر پیشینه آلودگی هوا، منابع و راههای پیشگیری
- عیوب ناشی از ماسه داغ در خطوط قالبگیری با ماسه تر
- خوردگی فلزات در تجهیزات و ماشین آلات صنعتی و روش های جلوگیری از آن
- آشنایی با شبكههای لرزهنگاری مركز لرزهنگاری كشوری + اطلاعات آنلاین زمین لرزه های ایران
- آشنایی با انواع پلیمرها، كاربرد و خواص آنها
- فارس من| اهمیت شبکه ملی اطلاعات در افزایش کیفیت و قیمت پایین خدمات است
- اختتامیه یازدهمین جشنواره بینالمللی فارابی برگزار شد/ 4 توصیه وزیر علوم به متخصصان علوم انسانی و اسلامی
- تلفن همراه مخصوص نابینایان
- فنجانی که موسیقی پخش می کند
- موسی که با تنفس کار می کند
- معرفی یک باگ جدید در ویندوز 7
- نحوه گرفتن عکس پانوراما
- عینک متاپرو چیست؟
- گوشی های هوشمند جدید
- لپ تاپ لمسی با نمایشگر معلق به بازار وارد شد
- گوشی Elife E7 mini
- آشنایی با گجت های تحسینبرانگیز
- فبلت Fonepad Note 6 ایسوس وارد بازار ایران شد
- علت فروش ضعیف LG G2 چیست ؟
- چگونه امنیت مودم ها را افزایش دهیم ؟
- زندگینامه نیکی کریمی
- تزیین هندوانه شب یلدا
- خواص اناردربهبود بیماری ها
- دسر شکلاتی با کاکائو
- قانون سینوسها
- تازههایی از دنیای دانش و فناوری
- نامگذاری و شناسایی گریس
- Subnetting به زبان ساده
- مغز انسان و آینده صنعت رباتیك
- چرا خداوند از حق الناس نمی گذرد؟
- سوسك جاسوس، یك ربات زنده!
- فارس من| اهمیت شبکه ملی اطلاعات در افزایش کیفیت و قیمت پایین...
- موسی که با تنفس کار می کند
- دسر شکلاتی با کاکائو
- ترکهای سطوح بتنی Cracks in concrete surfaces
- درخواست پیشنهاد یا RFQ چیست؟ Request for Quotation
- مقياس هاي سنجش قدرت و شدت زلزله
- علت فروش ضعیف LG G2 چیست ؟
- شب قدر در نگاه علامه طباطبایى
- معرفی یک باگ جدید در ویندوز 7
- واقعیترین ربات انساننما رونمایی شد
- شب قدر
- Captain Shahbazi’s international campaign and his stat...
- قانون سینوسها
- فنجانی که موسیقی پخش می کند
برترین های ماه
- تازههایی از دنیای دانش و فناوری
- نامگذاری و شناسایی گریس
- دعاى روز نهم ماه مبارك رمضان
- نکات مثبت و منفی نوشیدن قهوه
- آشنایی با مدار فلوتاسیون در کارخانه کانه آرایی چادرملو
- سیستم های کنترل هوشمند موتورخانه
- Subnetting به زبان ساده
- مدیریت بازیافت خودرو
- زندگینامه نیکی کریمی
- درخواست پیشنهاد یا RFQ چیست؟ Request for Quotation
- بیانیه و کمپین جهاني كاپيتان هوشنگ شهبازی
- قانون سینوسها
- مقياس هاي سنجش قدرت و شدت زلزله
- Captain Shahbazi’s international campaign and his stat...