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

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

هیچ اعتنایی به شرایط توپولوژیکی و ترافیک لحظه ای شبکه نمی شود و معمولاً هر مسیریاب برای هدایت بسته از جداولی استفاده می کند که در صورت وقوع هرگونه مشکل درزیر ساخت ارتباطی شبکه به صورت دستی تنظیم می گردند و در طول زمان ثابت می باشند که ترافیک لحظه ای هم به دلیل سریع بودن الگوریتم متغیر می باشد .

الگوریتم مسیریابی پویا :

مسیریابی براساس آخرین وضعییت توپولوژیکی و ترافیک شبکه انجام می شود و هرثانیه یکبار بروز می شوند،تصمیم گیری این الگوریتم براساس وضعییت فعلی شبکه می باشد ولی ممکن است به دلیل پیچیدگی بالای این الگوریتم زمان انتخاب بهترین مسیرطولانی شود و نهایتاً به ازدحام بینجامد که جهت رفع این مشکل از تکنیکهای چند پردازنده ای و پردازش موازی استفاده می گردد .

الگوریتم متمرکز یا :Link State

دراین الگوریتم هرمسیریاب باید5عمل زیر را انجام دهد:

1- آگاهی مسیریاب از اطلاعات کامل زیرساخت ارتباطی شبکه

2-شناسایی تمام مسیریابهای دیگر، ارتباطات بین آنها و هزینه ی هر خط توسط مسیریاب

3-جمع آوری اطلاعات کامل و تشکیل ساختمان داده ی مربوط به هرگراف زیرساخت ارتباطی

4-استفاده از الگوریتم کوتاهترین مسیر نظیر بهترین مسیر موجود بین دومسیریاب (دایجکسترا)

5-محاسبه مسیرهای جدید

1- شناسایی مسیریاب های مجاور :

با شروع به کار مسیریاب، اولین کاری که مسیریاب انجام می دهد شناسایی مسیریاب هاي مجاور با ارسال یک بسته ی خاص به نام بسته ی سلام یا Hello Packet روی تمام خروجی های خود می باشد . مسیریاب ضمن پاسخ به این بسته آدرس جهانی خود را اعلام می نمایند و بعد از دریافت بسته های پاسخ ، این اطلاعات را در جدول خود درج می كنند .

2-اندازه گیری هزینه :

* اندازه گیری تاخیر هریک از خطوط خروجی توسط هر مسیریاب با ارسال یک بسته ی خاص با نام Echo Packet بر روی تمام خطوط خروجی

* پاسخ هر مسیریاب با بسته ی Echo Reply درصورت دریافت بسته ی Echo Packet

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

* تشخیص مسیر بهینه همانند CF توسط مسیریاب ها و هدایت تمامی بسته ها از شبکه 1 و 2

* تبدیل شدن مسیر CF به بدترین مسیر با گزارش تاخیر و ترافیک بالا در عرض چند ثانیه

* انتخاب مسیر بهینه EI با داشتن ترافیک و تاخیر کمتر و هدایت بسته ها از این مسیر

* تبدیل دوباره این مسیر به بدترین مسیر با گزارش تاخیر و ترافیک بالا در عرض چند ثانیه ی دیگر

* تکرار روند نوسان تا بی نهایت

3- تشکیل بسته Link State Packed

هر مسیریاب بعد از جمع آوری اطلاعات لازم از مسیریاب های مجاور اقدام به تشکیل بسته Ls می دهد که هر بسته اطلاعات زیر را دارا می باشد که عبارتند از :

آدرس جهانی (IP) مسیریاب تولید کننده بسته

2- شماره ترتیب (تا بسته های تکراری از بسته های جدید تشخیص داده شوند)

3- طول عمر بسته

4- آدرس جهانی مسیریاب های مجاور و هزینه ی تخمین

۴- توزیع بسته های LS روی شبکه :

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

5-محاسبه مسیرهای جدید :

با دریافت بسته های LS از تمامی مسیریاب های شبکه ، مسیریاب می تواند ساختمان داده ی گراف زیرشبکه را تشکیل داده و براساس آن اقدام به پیدا کردن بهترین مسیر با کمترین هزینه بین دو مسیریاب از طریق الگوریتم دایجکسترا می کند .

روش غیرمتمرکز یا بردار مسافت Distance Vector :

1- نداشتن اطلاعات کامل اززیر ساخت ارتباطی شبکه توسط هر مسیریاب

2- محاسبه و ارزیابی هزینه ی ارتباط با مسیریاب مجاور توسط هرمسیریاب

3- ارسال جداول مسیریابی برای مسیریاب های مجاور در فواصل زمانی منظم

4- به روز شدن هر مسیریاب بایک الگوریتم ساده با توجه به دریافت جداول مسیریاب های مجاور برای هدایت هر بسته

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

مزیت : حجم پردازش آن کم می باشد

عیب : کندبودن انتشار اطلاعات در زمان خرابی یک کانال ارتباطی

طریقه ارسالدر روش سیل آسا :

هر مسیریاب با دریافت بسته های همگانی موظف است بسته ها را دوباره به تمامی مسیرهای خروجی خود به غیر از مسیری که دریافت کرده ارسال نماید

مزیت :

هر بسته اطلاعاتی به تمام مسیریاب های زیرشبکه می رسد .

هربسته اطلاعاتی در سریعترین زمان ممکن به مقصد می رسد .

معایب :

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

راه حلی برای رفع این مشکل :

1- قراردادن شماره شناسایی منحصر به فرد برای هر بسته :

مسیریاب با دریافت این بسته ابتدا شماره ی آنرا در جدولی ثبت می کند و بادریافت یک بسته ی همگانی جدید دیگر شماره شناسایی آنرا در جدول جستجو و در صورت وجود آنرا حذف می نماید .

2- قراردادن طول عمر برای بسته ها :

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

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

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

مطالب مشابه :

انواع الگوریتم search

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

مسیریابی شبکه های کامپیوتری

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

الگوریتم کلونی مورچگان

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

الگوریتم و فلوچارت

دانلود جزوه و نمونه سوالات طراحی الگوریتم ها