الگوریتمهای DV

از ویکی جامع پردیس دانشگاهی دانشگاه قم
پرش به: ناوبری، جستجو
مهندسی اینترنت
مقاله بعدی:مسیریابی سلسله مراتبی
مقاله قبلی:الگوریتمهای LS


در جدول مسیریابی مربوط به این روش پویای در مسیریابی دو فیلد وجود دارد. یکی فیلد مسیر که واسط خروجی مناسب برای رسیدن به یک مسیریاب خاص در شبکه را مشخص میکند و فیلد مقدار تقریبی هزینه که هزینه ی تقریبی رسیدن یک بسته تا مسیریاب مقصد را تعیین میکند. در این روش بر خلاف الگوریتمهای LS ، جدول مسیریابی بدون اطلاع از هزینه ی مربوط به کل لینک های ارتباطی در شبکه تکمیل میگردد. شکل 3 نمایش دهنده ی یک شبکه ی فرضی و جدول مسیریابی الگوریتم DV برای یکی از گرههای آن (گره J ) است. منظور از خط در شکل همان واسط خروجی است. واحد هزینه میتواند تأخیر یا تعداد گام ( Hop ) در نظر گرفته شود. Mef4sh4.PNG

روش تکمیل جداول مسیریابی در یک الگوریتم DV بدین صورت است که ابتدا هر مسیریاب هزینه تا هر کدام از مسیریاب های همسایه ی خود را یافته و در جدول درج مینماید. گام بعدی به این مسیریابها برابر با شناسه ی خود آنها است. مسیریابها موظفند در بازه های زمانی مشخص (هر T ثانیه)، ستون هزینه ( Distance Vector) از جدول مسیریابی خود را برای مسیریاب های همسایه ی خود ارسال نمایند (فقط مسیریاب های همسایه و نه تمام مسیریابهای حاضر در شبکه). هر مسیریاب بر اساس اطلاعات دریافت شده جدول مسیریابی خود را به روزرسانی میکند. به روزرسانی جدول هر مسیریاب بدین صورت است که با مشاهده ی مقادیر جدید در ستونّهای هزینه ی دریافت شده از طرف همسایه ها، هزینه تا این گره جدید به صورت محاسبه ی مجموع هزینه تا هر کدام از همسایه ها که گره مورد نظر را در اطلاعات ارسالی ذکر کرده اند و هزینه از آن همسایه تا گره جدید و سپس، انتخاب حداقل هزینه ی حاصل شده محاسبه میشود. به طور مثال، ستونهای هزینه ی نمایش داده شده در شکل 4 برای تکمیل جدول مسیریابی نشان داده شده در شکل 3 مورد استفاده قرار میگیرند. به عنوان نمونه مشاهده میشود که هزینه ی گره J تا گره گره G برابر است با 18 که از مجموع هزینه های 12 (هزینه تا گره H) و 6 (هزینه از گره H تا گره G ) بدست می آید. مشاهده میشود در صورتی که برای رسیدن به یک گره مشخص چند هزینه ی مختلف از چند مسیریاب مختلف (به عنوان گام بعد) فراهم بود، مقدار هزینه ی حداقل انتخاب میشود. جدول حاصل شده تا به روزرسانی بعدی مورد استفاده قرار میگیرد. حجم جدول مورد نظر در این روش بسیار کمتر از جدول نگهداری شده در روش LS است. Mef4sh3.PNG

یک مشکل موجود در این روش مسیریابی "عدم همگرایی سریع جداول مسیریابی"پس از خروج یک مسیریاب یا یک لینک از شبکه است (مثلاً در اثر خرابی) که به آن شمارش تا بینهایت هم گفته میشود. به عنوان مثال، شکل 5 نمایش دهنده ی یک شبکه ی فرضی و جدول مسیریابی هر کدام از مسیریاب ها پیش از ایجاد خرابی در شبکه است و شکل ۶ نمایش دهنده ی خروج لینک بین مسیریابهای A و B و روند ایجاد تغییرات در جدول مسیریابی هر کدام از مسیریابها است. یکی از راه حلها برای این مشکل بدین صورت است که مسیریابها در ستون هزینه ی ارسال شده به هر مسیریاب، مدخلهایی که مسیر رسیدن به آنها از مسیریاب دریافت کننده ی پیام است را حذف میکند و یا آن را برابر با مقدار بینهایت ∞ قرار میدهد.

Mef4sh5.PNG Mef4sh6.PNG