الگوریتم‌های مسیریابی

الگوریتم‌های مسیریابی مسیرهایی را که بسته‌ها از طریق یک شبکه طی می‌کنند، محاسبه می‌کنند. این کار معمولاً با یافتن کم‌هزینه‌ترین مسیرها بر روی گرافی از مسیریاب‌ها و پیوندها، با استفاده از دیدگاه جهانی وضعیت پیوند یا محاسبه توزیع‌شده و همسایه به همسایه بردار فاصله، انجام می‌شود.

Definition

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

Scope

این موضوع الگوریتم‌هایی را پوشش می‌دهد که جداول ارسال را پر می‌کنند: مدل گرافی یک شبکه با هزینه‌های پیوند؛ مسیریابی وضعیت پیوند با استفاده از الگوریتم کوتاه‌ترین مسیر دایکسترا با توپولوژی مشترک جهانی؛ مسیریابی بردار فاصله با استفاده از محاسبه توزیع‌شده بلمن-فورد با تبادلات همسایه؛ رفتار همگرایی و آسیب‌شناسی‌های آن‌ها مانند مشکل شمارش تا بی‌نهایت؛ و مسیریابی سلسله‌مراتبی برای مقیاس‌پذیری. این موضوع الگوریتم‌ها را به صورت انتزاعی بررسی می‌کند و پروتکل‌های بتنی (OSPF, RIP, BGP) و سازماندهی درون/بین‌دامنه‌ای آن‌ها را به موضوع پروتکل‌های مسیریابی واگذار می‌کند.

Core questions

• چگونه یک شبکه به عنوان یک گراف وزن‌دار برای مسیریابی مدل می‌شود؟
• چگونه یک الگوریتم وضعیت پیوند کوتاه‌ترین مسیرها را از یک نمای توپولوژی کامل محاسبه می‌کند؟
• چگونه یک الگوریتم بردار فاصله با استفاده از تنها تبادلات همسایه همگرا می‌شود؟
• مشکلات همگرایی و پایداری، مانند شمارش تا بی‌نهایت، چه هستند و چگونه کاهش می‌یابند؟
• چرا مسیریابی سلسله‌مراتبی می‌شود و چگونه بر بهینگی مسیر تأثیر می‌گذارد؟

Key concepts

• گراف شبکه وزن‌دار
• مسیرهای کم‌هزینه
• مسیریابی وضعیت پیوند
• الگوریتم دایکسترا
• مسیریابی بردار فاصله
• معادله بلمن-فورد
• مشکل شمارش تا بی‌نهایت
• افق تقسیم و معکوس مسموم
• مسیریابی سلسله‌مراتبی

Key theories

مسیریابی وضعیت پیوند (دایکسترا)

هر مسیریاب هزینه‌های پیوند خود را منتشر می‌کند تا همه مسیریاب‌ها توپولوژی کامل را به اشتراک بگذارند، سپس به طور مستقل الگوریتم دایکسترا را برای محاسبه کوتاه‌ترین مسیرها اجرا می‌کند؛ این روش به سرعت و به طور قابل پیش‌بینی همگرا می‌شود اما نیاز به تبادل اطلاعات جهانی دارد.

مسیریابی بردار فاصله (بلمن-فورد)

مسیریاب‌ها تخمین‌های فعلی خود از کم‌هزینه‌ترین مسیر به هر مقصد را با همسایگان خود مبادله می‌کنند و از طریق معادله بلمن-فورد به‌روزرسانی می‌کنند؛ محاسبه توزیع‌شده است و فقط از اطلاعات محلی استفاده می‌کند اما می‌تواند به آرامی همگرا شود و از مشکل شمارش تا بی‌نهایت رنج ببرد.

مسیریابی سلسله‌مراتبی

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

Clinical relevance

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

History

الگوریتم‌های کوتاه‌ترین مسیر که در قلب مسیریابی قرار دارند، پیش از شبکه‌های کامپیوتری وجود داشته‌اند: کار بلمن و فورد بر روی مسائل مسیریابی در اواخر دهه ۱۹۵۰ و الگوریتم کوتاه‌ترین مسیر دایکسترا در سال ۱۹۵۹. با رشد شبکه‌های بسته‌ای، این الگوریتم‌ها به مسیریابی بردار فاصله و وضعیت پیوند تطبیق داده شدند و ساختار سلسله‌مراتبی به سیستم‌های خودمختار، مسیریابی را در اینترنت جهانی مقیاس‌پذیر کرد.

Debates

مسیریابی وضعیت پیوند در مقابل مسیریابی بردار فاصله

مسیریابی وضعیت پیوند به سرعت همگرا می‌شود و از مشکل شمارش تا بی‌نهایت جلوگیری می‌کند اما نیاز دارد که هر مسیریاب توپولوژی کامل را نگه دارد و محاسبات بیشتری انجام دهد، در حالی که بردار فاصله ساده‌تر و محلی‌تر است اما می‌تواند به آرامی همگرا شود و حلقه‌های گذرا ایجاد کند؛ شبکه‌های واقعی هر دو ایده را در مقیاس‌های مختلف ترکیب می‌کنند.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford

Seminal works

• dijkstra1959
• bellman1958
• kurose2021

Frequently asked questions

مشکل شمارش تا بی‌نهایت چیست؟

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

چرا هم وضعیت پیوند و هم بردار فاصله استفاده می‌شوند؟

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