الگوریتمهای مسیریابی

از ویکی جامع پردیس دانشگاهی دانشگاه قم
پرش به: ناوبری، جستجو
مهندسی اینترنت
مقاله بعدی:رروش ارسال سیل آسا یا flooding
مقاله قبلی:NAT OR Network Address Translation (نَت)

به نوعی میتوان الگوریتمهای مسیریابی را به دو دستهی ایستا(Static) و پویا(Dynamic) تقسیم نمود. در روش ایستا، جدول پیشرانی/مسیریابی به صورت دستی و در زمان پیکربندی مسیریاب تنظیم میشود و درطول زمان ثابت میماند. هر گونه تغییر در این جدول نیز توسط مدیر شبکه اعمال میگردد. در روش پویا، جدول

مسیریابی هر T ثانیه و بر اساس عواملی همچون آخرین وضعیت توپولوژی (شکل اتصال دستگاه های شبکه و لینکهای آن) یا میزان ترافیک شبکه به روزرسانی میشوند.

از یک دیدگاه دیگر میتوان این الگوریتمها را به دو دسته ی "سراسری متمرکز(Global Routing Algorithm)" و"غیرمتمرکزتوزیع شده(Decentralized Routing Algorithm)"تقسیم نمود. در روش متمرکز هر مسیریاب لازم است اطلاعات تمام مسیریابهای موجود در شبکه و ارتباط بین آنها را جمعآوری نماید و پس از تشکیل گراف شبکه، به منظور یافتن بهترین مسیر بین دو مسیریاب از یک الگوریتم یافتن کوتاهترین مسیر مناسب (مثل الگوریتم دایجسترا(Dijkstra Shortest Path Algorithm)) استفاده کند. به این الگوریتم ها اصطلاحاً الگوریتم های( LS ( Link State Algorithm نیز گفته میشود.

در روش غیرمتمرکز، مسیریاب اطلاعات کاملی از زیرساخت شبکه ندارد و فقط قادر است هزینه ی ارتباط با مسیریابهایی که به طور مستقیم با آنها در ارتباط است (مسیریاب های همسایه) را محاسبه نماید. سپس، در فواصل زمانی منظم هر مسیریاب جداول مسیریابی خود را فقط برای مسیریابهای همسایه ارسال مینماید و در نتیجه این مسیریابها میتوانند با توجه به مقادیری که خود محاسبه کرده بودند، جدول خود را کامل کرده و مسیر بین مسیریابهای مختلف را تعیین کنند. این الگوریتمها پیچیدگی زمانی بسیار کمی دارند. به این الگوریتمها اصطلاحاً (DV ( Distance Vector Algorithm گفته میشود.