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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم انتشار به روز (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
    + - - - - - + - - - - - +
                |           |
             (2)|        (3)|
                |           |
                + - - - - - +
                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(۳ ==> مسیر جایگزین امکان پذیر

منابع[ویرایش]