الگوریتم انتشار به‌روز

الگوریتم انتشار به روز (DUAL)، الگوریتم مورد استفاده توسط پروتکل مسیریابی EIGRP مربوط به شرکت سیسکو سیستمز است و برای اطمینان حاصل کردن از این امر است که یک مسیر معین به طور کلی، زمانی که ممکن است یک حلقه مسیریابی شود دوباره محاسبه شده‌است. بر طبق گفته Cisco، نام کامل الگوریتم DUAL، ماشین حالت متناهی(DUAL FSM) می‌باشد.

EIRGP مسئولیت مسیر یابی در درون یک سیستم مستقل و واکنش‌های دو طرفه برای تغییر در توپولوژی مسیر یابی را به عهده دارد و به‌طور پویا جدول مسیر یاب را به‌طور خودکار تنظیم و تعدیل می‌کند. EIRGP از یک سری شرایط امکان‌سنجی استفاده می‌کند برای تضمین اینکه تنها حلقه مسیرهای آزاد همواره انتخاب شده‌اند. شرایط سنجش، محافظه کار است: هنگامی که شرایط درست است، هیچ حلقه و چرخشی نمی‌تواند اتفاق بیفتد اما امکان دارد تحت برخی شرایط، همه مسیرها به یک مقصد را نپذیرد اگر چه برخی از آنها حلقه‌های آزاد باشند.

در هنگامی که هیچ مسیر ممکنی، برای یک مقصد در دسترس نباشد الگوریتم DUAL (دوگانه) یک محاسبه انتشار برای تضمین اینکه همه آثار و ردپای مسیرهای مشکل ساز از شبکه حذف شده‌اند را در خواست می‌کند.

در این نقطه، الگوریتم نرمال بلمن-فورد (Bellman-Ford) برای بازیابی یک مسیر جدید مورد استفاده است.

عملکرد

DUAL از سه جدول جداگانه برای محاسبه مسیر استفاده می‌کند. این جداول با استفاده از اطلاعات مبادله شده در میان روترهایEIRGP ایجاد می‌شوند. این اطلاعات، نسبت به اطلاعاتی که توسط پروتکل‌های مسیر یابی ارتباطی link-state مبادله می‌شوند، متفاوت است. در EIRGPاطلاعات رد وبدل شده شامل: مسیرها، "طول مسیر" یا هزینه هر مسیر و اطلاعات مورد نیاز برای تشکیل یک رابطه نزدیک به هم (مثل تعدادAS، زمان و ارزش k)می‌باشد. این ۳جدول با عملکرد و جزئیاتشان در زیر آمده‌است:

• جدول مجاور (همسایه): شامل اطلاعات مربوط به همه روترهایی است که به طور مستقیم به دیگر روترها متصل هستند. یک جدول جداگانه برای هر یک از پروتکل‌های پشتیبانی شده (IP,IPX و غیره) وجود دارد. هر ورودی با توصیفی از آدرس و رابط شبکه با جدول مجاور تطابق دارد. علاوه بر این، یک زمان‌سنج برای تعیین متناوب راه اندازی، مقداردهی اولیه شده‌است که آیا ارتباط برقرار است یا نه؟. این اطلاعات از طریق بسته‌های "Hello" بدست می‌آید. اگر بسته "Hello" از یک جدول مجاور در طول یک دوره زمانی مشخص دریافت نشود، روتر از جدول مجاور حذف می‌شود.
• جدول توپولوژی: شامل طول مسیر (اطلاعات هزینه)، از همه مسیرها به هر مقصدی در دورن سیستم مستقل است. این اطلاعات از روترهای مجاور موجود در جدول مجاور دریافت می‌شوند. مسیرهای اولیه (جایگزین) و ثانویه (جایگزین امکان‌پذیر) به یک مقصد، با اطلاعاتی در جدول توپولوژی تعیین خواهد شد. در میان بقیه چیزها، هر ورودی در جدول توپولوژی شامل موارد زیر است:

" FD(فاصله امکان پذیر)": طول مسیر محاسبه شده از یک مسیر به مقصد، درون سیستم مستقل

" RD(فاصله انتشار یافته)": طول مسیر مقصد آنچنان که توسط روترهای مجاور اعلام شده‌است.RD برای محاسبه FD مورد استفاده قرار می‌گیرد و تعیین می‌کند که آیا مسیر با "شرایط امکان سنجی" تلاقی پیدا می‌کند.

وضعیت مسیر: یک مسیر به یکی از حالت‌های "فعال " یا "منفعل" علامت گذاری می‌شود. مسیرهای منفعل با ثبات و پایدار هستند و می‌توانند برای انتقال اطلاعات مورد استفاده قرار گیرند. مسیرهای فعال، دوباره مورد محاسبه قرار می‌گیرند و در دسترس یا غیرقابل دسترس می‌باشند.

• جدول مسیر یابی: شامل بهترین مسیرها برای رسیدن به مقصد (در اصطلاح کمترین "طول مسیر") می‌باشد که این مسیرها جانشین یا جایگزینی از جدول توپولوژی می‌باشند. DUAL اطلاعات دریافت شده از دیگر مسیر یاب‌ها در جدول توپولوژی را ارزیابی می‌کند و مسیرهای اولیه (جایگزین) و ثانویه (جایگزین امکان‌پذیر) را محاسبه می‌کند. مسیر اولیه معمولاً مسیری با کمترین طول مسیر برای رسیدن به مقصد می‌باشد؛ و مسیر اضافی یا فرعی، مسیری با کمترین هزینه (اگر مطابق با شرایط امکان‌سنجی باشد) می‌باشد. ممکن است مسیرهای جایگزین و جایگزین امکان‌پذیر متعدد وجود داشته باشد. مسیرهای جایگزین و جایگزین امکان‌پذیر هر دو، در جدول توپولوژی نگه داشته می‌شوند ولی فقط مسیرهای جایگزین به جدول مسیر یابی اضافه می‌شوند و در بسته‌های مسیر مورد استفاده قرار می‌گیرند.

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

مثال

علائم و اختصارات:

+: روتر

- یا |: پیوند

(x): طول مسیر پیوند

 A (2) B (1) C
 + - - - - - + - - - - - +
 | |
 (۲)| (۳)|
 | |
 + - - - - - +
 D (1) E

اکنون یک Client (سرویس گیرنده) در روتر E می‌خواهد با یک سرویس گیرنده در روتر A ارتباط برقرار کند. این به این معنی است که مسیر بین، روتر A و روتر E باید در دسترس باشد. این مسیر به صورت زیر محاسبه می‌شود:

همسایه‌های مجاور و پهلوی روتر E، مسیریاب‌های C و D می‌باشند. DUAL در مسیریاب E درخواست فاصله انتشار یافته از مسیریاب‌های به ترتیب C و D به مسیریاب A را می‌کند. نتایج بدین صورت است:

مقصد: روتر A

از راه Dء:(RD(۴

از راه Cء:(RD(۳

بنابراین مسیر از راه C، کم هزینه‌ترین مسیر است. در گام بعدی، فاصلهٔ روتر E با روترهای مجاور، به فاصله انتشار یافته اضافه می‌شود تا فاصلهٔ امکان‌پذیر (FD) به دست آید:

مقصد: روتر A

از راه Dء: (FD(۵ و (RD(۴

از راه Cء: (FD(۶ و (RD(۳

بنابراین DUAL به این نتیجه می‌رسد که مسیر از راه D، کمترین هزینه کلی را دارا می‌باشد. پس مسیر از راه D به عنوان «مسیر جایگزین» با وضعیت منفعل علامت دار می‌شود و در جدول مسیریابی ثبت می‌شود. مسیر از راه C، به عنوان «مسیر جایگزین امکان پذیر» نگه داشته می‌شود زیرا RD آن کمتر از FD مسیر جایگزین می‌باشد.

مقصد: روتر A

از راه Dء: (FD(۵ و (RD(۴ ==> مسیر جایگزین

از راه Cء: (FD(۶ و (RD(۳ ==> مسیر جایگزین امکان‌پذیر