قبل از شروع به خواندن این مقاله، ما به شما توصیه می کنیم خود را با مواد مربوط به محاسبه مسیر با توجه به الگوریتم Bellman - Ford آشنا کنید.
الگوریتم به روز رسانی انتشار (الگوریتم به روز رسانی منتشر شده - Dual) یکی از دو الگوریتم مورد بحث در اینجا است که در ابتدا برای پیاده سازی در یک شبکه توزیع شده مورد بحث قرار گرفته است. این منحصر به فرد است که همچنین اطلاعات مربوط به قابلیت دستیابی و توپولوژی موجود در اتوماتیک نهایی الگوریتم را حذف می کند. الگوریتم های دیگر بحث شده در اینجا حذف اطلاعات را در اختیار اجرای پروتکل قرار می دهند و این جنبه از کار الگوریتم را در خود الگوریتم در نظر نمی گیرند.
تا سال 1993، Bellman-Ford و Dijkstra به عنوان الگوریتم های توزیع شده در چندین پروتکل مسیریابی اجرا شدند. این تجربه به عنوان یک نتیجه از این پیاده سازی ها و استقرار اولیه به دست آمد، منجر به "موج دوم" تحقیق و انعکاس بر مشکل مسیریابی در شبکه های سوئیچینگ شبکه شد، که منجر به ظاهر بردار مسیر و دوگانه شد.
از آنجا که دوگانه به عنوان یک الگوریتم توزیع شده طراحی شده است، بهتر است که کار خود را در شبکه توصیف کنید. برای این منظور، ارقام 8 و 9 استفاده می شود. برای توضیح دوگانه، این مثال در جریان سه مقصد ردیابی می شود و سپس تغییرات در حالت موجود در دسترس برای موارد مشابه مقصد پردازش می شود. در مثال اول، مورد زمانی که یک مسیر جایگزین وجود دارد، مورد توجه قرار می گیرد، اما هیچ همسایه پایین دست وجود ندارد، دوم این مورد را در نظر می گیرد که یک مسیر جایگزین و همسایه پایین دست وجود دارد.
در شکل 8، مطالعه D از نقطه نظر A:
- یک دو راه برای D را یاد می گیرد:
- A مسیر را از طریق B تشخیص نمی دهد، زیرا B از یک جانشین آن استفاده می کند:
- مسیرهای موجود را مقایسه می کند و کوتاه ترین مسیر را بدون حلقه انتخاب می کند:
- چک کردن مسیرهای باقی مانده برای تعیین اینکه آیا هر یک از آنها همسایگان پایین دست وجود دارد:
A این را می داند زیرا C مسیر را به D با متریک محلی برابر با 3 اعلام می کند.
یک متریک محلی C را در جدول توپولوژی خود حفظ می کند.
در نتیجه، مقدار محلی را در C و ارزش محلی در A می داند
- 3 (هزینه در C) = 3 (هزینه در A)، بنابراین این مسیر ممکن است حلقه باشد، بنابراین C شرایط امکان سنجی را برآورده نمی کند. C به عنوان همسایگان پایین دست نیست.
همسایگان پایین دست در دوگانه، جانشینان احتمالی نامیده می شود. فرض کنید کانال [a، h] کار نمی کند. دوگانه به به روز رسانی های دوره ای تکیه نمی کند، بنابراین نمی تواند فقط به روز رسانی دیگری با اطلاعات قابل اعتماد صبر کند. در عوض، باید به طور فعال یک مسیر جایگزین را دنبال کند. بنابراین، این یک فرآیند تشخیص پراکنده از یک مسیر جایگزین است. اگر کانال [a، h] کار نمی کند، با توجه به تنها D:
- یک جدول محلی خود را برای جانشینان احتمالی (همسایگان پایین دست) چک می کند.
- هیچ جانشین احتمالی وجود ندارد، بنابراین باید یک مسیر جایگزین را بدون حلقه به D (اگر وجود داشته باشد) پیدا کنید.
- یک درخواست برای هر همسایه ارسال می کند تا تعیین کند آیا هر مسیر جایگزین بدون حلقه به D.
- در C:
- در ب:
- این پاسخ ها را می گیرد:
در شکل 9، مقصد (D) مورد با H به E منتقل شد. این در مثال دوم استفاده می شود.
در این مثال، یک جانشین احتمالی (همسایه پایین دست) وجود دارد.
مطالعه D از نقطه نظر A:
- یک دو راه برای D را یاد می گیرد:
- A هیچ راهی را از طریق B به رسمیت نمی شناسد:
- مسیرهای موجود را مقایسه می کند و کوتاه ترین مسیر را بدون حلقه انتخاب می کند:
- چک کردن مسیرهای باقی مانده برای تعیین اینکه آیا هر یک از آنها همسایگان پایین دست وجود دارد:
اگر کانال [a، c] کار نمی کند، به سادگی با توجه به:
- یک جدول از توپولوژی محلی را برای یک جانشین احتمالی بررسی می کند.
- جانشین احتمالی از طریق H.
- یک جدول محلی خود را در H به عنوان بهترین راه تغییر می دهد.
- یک به روز رسانی به همسایگان خود می فرستد، با توجه به این که هزینه آن دستاورد D از 3 تا 4 تغییر کرده است.
همانطور که می بینید، پردازش زمانی که یک جانشین احتمالی وجود دارد، بسیار سریع تر و راحت تر از آن است. در شبکه هایی که پروتکل مسیریابی با استفاده از دوگانه (به ویژه EIGRP) مستقر شد، یکی از اهداف اصلی طراحی، حجم هر گونه درخواست تولید شده در غیاب یک جانشین احتمالی را محدود می کند. منطقه درخواست عامل اصلی تعیین کننده این است که چگونه الگوریتم دوگانه به سرعت تکمیل می شود و بنابراین، چگونه به سرعت شبکه همگام سازی می شود.
شکل 10 دستگاه پایه دوگانه را به پایان رسانده است.
چیزهایی که در مسیر گنجانده می شود، بدتر می شود (تخریب مسیر) ممکن است:
- شکست کانال متصل یا همسایه
- به دست آوردن به روز رسانی برای یک مسیر با متریک بالاتر
- گرفتن پرس و جو از جانشین کنونی
- گرفتن یک مسیر جدید از یک همسایه
- یک همسایه جدید پیدا شد، و همچنین مسیرهایی که می توان آن را دریافت کرد
- دریافت تمام درخواست ها به همسایگان ارسال می شود زمانی که مسیر بدتر می شود
