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

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

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

الگوریتم های وفقی(Adaptive):

در اینگونه از الگوریتم ها امکان تغییر مسیر وجود دارد و یک بسته ممکن است پس از رسیدن به یک نود،با توجه به شرایط،مسیر بعدی خود را تغییر دهد

الگوریتم های غیر وفقی( no Adaptive):

در این الگوریتم ها مسیر یک بسته از گره اول مشخص می شود و تا رسیدن به گره مقصد ، همان مسیر را دنبال می کند(مسیریابی در مبدا یا همان Source Routing)


نکته
اگر شبکه ی ما پویا است و تغییر می کند بهتر است از الگوریتم وفقی استفاده شود.



نکته
نکته ی قابل توجه این است که در الگوریتم های مسیر یابی عمدتا از روش های هوشمند استفاده می شود.همچنین در صورتی که الگوریتم به گونه ای باشد که هر نود داده های خود را از نود های همسایه جمع کند آنگاه خطر اینکه نود همسایه اطلاعات اشتباه در اختیار آن نود قرار دهد زیاد است و این یکی ز راه های نفوذ دشمن است.



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

  • صحت عملکرد(Correctness)
  • سادگی(Simplicity)
  • قابلیت تحمل/مقاومت(Robustness)
  • پایداری(Stability)
  • عدالت(Fairness)
  • بهینگی(Optimality)


الگوریتم پیشنهادی برای یافتن کوتاه ترین مسیر

الگوریتم کوتاه ترین مسیر کم ترین تابع هزینه و یا به عبارتی،بهترین مقدار تابع هدف را در نظر می گیرد.


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

مسیر را از ابتدا به انتها مشخص می کنیم.برای هر نود این کار را انجام می دهیم.از یک نود شروع می کنیم،یک بسته را به نود های مجاور خود می فرستد.از هر نودی که میگذرد یک تگ به بسته اضافه می شود.این کار ادامه می یابد تا زمانی که نود مقصد اولین بسته را دریافت می کند که برچسب مبدا به مقصد را داراست و برچسب نود های در طول مسیر را هم داراست و بهترین مسیر را نشان می دهد.