پروتکل مسیریابی بردار فاصله (Distance vector routing) چیست و چگونه کار می‌کند؟

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

در شبکه‌های رایانه‌ای، دو نوع مسیریابی اصلی تعریف شده است که یکی مسیریابی ثابت یا استاتیک (Static routing) و دیگری مسیریابی پویا یا داینامیک (Dynamic routing) است. البته مسیریابی دیگری موسوم به مسیریابی پیش‌فرض (Default routing) نیز تعریف شده که در اصل نوعی مسیریابی ثابت یا استاتیک است. در مسیریابی ثابت، مدیر شبکه مسیرهای شبکه را دستی در جدول مسیریابی هر روتر ثبت می‌کند. اما در مسیریابی پویا هر روتر با استفاده از پروتکل‌ها و الگوریتم‌های مسیریابی، مسیرها را خودکار در حافظه‌اش ذخیره می‌کند و هر بار که تغییری در مسیرهای شبکه پدید می‌آید، جدول‌های مسیریابی‌اش را بسته به تغییرات جدید نوسازی می‌کند. برای مسیریابی پویا دو دسته پروتکل متفاوت ارائه شده است، که به‌کارگیری هر کدام‌شان به نوع شبکه بستگی دارد: پروتکل‌های درون‌دامنه‌ای (گیت‌وی درونی) و پروتکل‌های بین‌دامنه‌ای (گیت‌وی بیرونی). پروتکل مسیریابی بردار فاصله (که گاهی به آن پروتکل مسیریابی بردار مسافت نیز می‌گویند) نوعی پروتکل درون‌دامنه‌ای محسوب می‌شود (تصویر 1).

تصویر 1. پروتکل‌های مسیریابی شبکه: پروتکل‌های مسیریابی بردار فاصله (Distance vector) ذیل پروتکل‌های گیت‌وی درونی یا درون‌دامنه‌ای دسته‌بندی می‌شوند. پروتکل اطلاعات مسیریابی یا RIP (مخفف Routing Information Protocol) نوعی پروتکل مسیریابی بردار فاصله است. 

پروتکل مسیریابی بردار فاصله چیست؟

مسیریابی بردار فاصله (Distance vector routing) نوعی پروتکل مسیریابی پویا (داینامیک) است. در این پروتکل، هر روتر در حافظه خود یک جدول مسیریابی تشکیل می‌دهد که کمکش می‌کند کوتاه‌ترین مسیر از گره‌ای به گره دیگر را در شبکه بیابد. هر روتر در شبکه با دیگر روترهای همسایه‌اش در تعامل است. وقتی یکی از روترها درباره تغییرات شبکه یا مسیرهای جدید اطلاعات تازه‌ای به دست می‌آورد آن را به دیگر روترهای همسایه، یعنی روترهایی که مستقیما با آن‌ها اتصال دارد نیز اطلاع می‌دهد. روترهای همسایه پس از دریافت این اطلاعات، جدول مسیریابی‌شان را به‌روزرسانی و کوتاه‌ترین مسیر در شبکه را محاسبه می‌کنند. سپس آن‌ها نیز اطلاعات جدول مسیریابی‌شان را با روترهای مجاور خود به اشتراک می‌نهند و این رویه همچنان تکرار و اطلاعات تمام روترها مرتبا همگرا می‌شود (convergence). ضمنا در مسیریابی بردار فاصله، حتی وقتی تغییری در شبکه رخ نداده است نیز همه روترها در فواصل زمانی معین اطلاعات جدول مسیریابی‌شان را با روترهای مجاورشان به اشتراک می‌نهند. مثلا طبق پروتکل RIP که نوعی پروتکل مسیریابی بردار فاصله است، روترها هر 30 ثانیه اطلاعات جدول مسیریابی‌شان را به روترهای مجاور اعلام می‌کنند. 

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

الگوریتم بلمن-فورد چیست؟

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

1. ابتدا هزینه یا فاصله یک گره با خودش 0 در نظر گرفته می‌شود.
2. اگر یک گره‌ مستقیما به گره دیگری متصل نباشد، هزینه آن بی‌نهایت فرض می‌شود.

کمترین فاصله بین دو گره در یک گراف چنین به دست می‌آید:

Dij = min {(Ci1 + D1j), (Ci2 + D2j),… (CiN + DNj)}|

• منظور از Dij کوتاه‌ترین فاصله از گره i تا گره j است
• منظور از Ci1 هزینه گره i تا گره 1 است

این الگوریتم آن‌قدر تکرار می‌شود تا کوتاه‌ترین بردار فاصله بین دو گره پیدا شود.

الگوریتم مسیریابی بردار فاصله چیست؟

الگوریتم بلمن-فورد فرض می‌کند که شما تمام اطلاعات اولیه همه گره‌ها را یک‌جا دارید. لذا الگوریتم بلمن-فورد می‌توانست هم‌زمان (synchronous) برای هر گره مسیری تعیین کند. اما در الگوریتم مسیریابی بردار فاصله باید برای روترها در سامانه خودگردان، جدول مسیریابی ایجاد شود. ممکن است در سامانه خودگردان تغییراتی رخ دهد؛ مثلا روتر جدیدی به شبکه اضافه شود یا یکی از شبکه‌ها خدماتش به یکی از روترها را متوقف کند یا یکی از لینک‌ها دچار نقص شود. در چنین مواقعی، جدول مسیریابی همه روترها باید غیرهم‌زمان (asynchronous) یعنی یکی پس از دیگری به‌روزرسانی شود، چون هر روتر باید جدول مسیریابی خود را بر پایه اطلاعات دریافتی از روترهای مجاور به‌روزرسانی کند. لذا با ایجاد تغییراتی در الگوریتم بلمن-فورد، الگوریتم جدیدی موسوم به الگوریتم مسیریابی بردار فاصله طراحی شد.

در الگوریتم مسیریابی بردار فاصله:

• برای محاسبه هزینه هر مسیر، تعداد هاپ‌ها (hop) شمرده می‌شود؛ منظور از تعداد هاپ، تعداد روترها یا دستگاه‌های واسطه‌‌ دیگری نظیر روتر است که برای رسیدن به مقصد باید از آن‌ها عبور شود (تصویر 2). لذا هزینه پیمایش مسیر بین دو روتر مجاور، 1 در نظر گرفته می‌شود.
• هر روتر وقتی از روترهای مجاورش اطلاعات جدیدی می‌گیرد، جدول مسیریابی خود را به‌روزرسانی می‌کند.
• آن روتر سپس جدول مسیریابی به‌روزرسانی شده خود را برای روترهای مجاورش ارسال می‌کند. نتیجتاً روترهای مجاور نیز جدول‌شان را بر پایه اطلاعات جدید به‌روزرسانی می‌کنند.
• هر روتر در جدول مسیریابی خود سه گونه اطلاعات ذخیره می‌کند: شبکه مقصد، هزینه (فاصله)، هاپ بعدی (بردار)
• روتر اطلاعات هر مسیر را به‌شکل یک رکورد (R) برای روترهای مجاورش ارسال می‌کند.

نحوه مسیرگزینی در پروتکل مسیریابی بردار فاصله

پروتکل مسیریابی بردار فاصله هنگام تعیین بهترین مسیر تا مقصد، دو نوع اطلاعات ذخیره می‌کنند:

1. فاصله (مثلا تعداد هاپ‌هایی که باید پیموده شود)
2. بردار (یعنی هاپ بعدی) که جهت حرکت را مشخص می‌کند

برای مثال، همه روترهای تصویر 2 با پروتکل RIP کار می‌کنند که نوعی پروتکل مسیریابی بردار فاصله است. در تصویر، روتر 2 می‌خواهد به شبکه الف داده‌ای ارسال کند. یعنی روتر 2 گره مبدا و شبکه الف گره مقصد است. روتر 2 برای ارسال داده به شبکه الف، دو مسیر پیش رو دارد:

• یکی از مسیرها به‌ترتیب از روتر 3، روتر 4 و روتر 5 می‌گذرد، لذا فاصله یا اصطلاحا هزینه پیمایش آن 3 هاپ است (چون گفته شد که منظور از هاپ، تعداد روترها یا دستگاه‌های واسطه‌‌ دیگری نظیر روتر است که داده‌ها برای رسیدن به مقصد باید از آن‌ها عبور کنند).
• مسیر بعدی از روتر 1 و روتر 5 می‌گذرد، پس فاصله یا هزینه پیمایش آن 2 هاپ است.

مسیر دوم کم‌هزینه‌تر (کوتاه‌تر) است و روتر 2 قاعدتاً همین مسیر را برمی‌گزیند. اما اگر روتر 1 و مسیر آن به‌سمت شبکه الف قطع شود، ارتباط روتر 2 با شبکه الف نیز تماما قطع می‌شود. روتر 2 پس از سه دوره انتظار 30 ثانیه‌ای (مجموعا 90 ثانیه)، مسیر معیوب را در جدول مسیریابی‌اش لغو می‌کند. سپس طبق روال پروتکل RIP که در آن روترها هر 30 ثانیه یک‌بار وضعیت جدول مسیریابی‌شان را به روترهای مجاور اعلام می‌کنند، روتر 3 نیز مانند دیگر روترها مسیرهایش را مجددا به روترهای مجاورش از جمله روتر 2 اعلام می‌کند. بدون احتساب زمان انتظار برای بازگشت احتمالی روتر 1 به مدار (که اصطلاحا به آن زمان hold-down می‌گویند)، 90 تا 120 ثانیه طول می‌کشد تا روتر 2 مسیرش را از سمت روتر 1 (که از مدار خارج شده است) به‌سمت روتر 3 تغییر دهد و به‌ناچار مسیر طولانی‌تر را برگزیند. 

تصویر 2. شبکه‌ای فرضی که با پروتکل مسیریابی بردار فاصله RIP کار می‌کند: روتر 2 برای ارسال بسته‌های داده به شبکه الف، دو مسیر دارد که هزینه پیمایش یکی از مسیرها 2 هاپ و هزینه پیمایش مسیر دیگر 3 هاپ است.

مثالی برای توضیح نحوه مسیریابی با پروتکل بردار فاصله

تصویر 3 شبکه‌ای فرضی را نشان می دهد. ابتدا هر روتر جدول مسیریابی خاص خود را دارد. اما این جدول‌های مسیریابی، یک‌باره و هم‌زمان ایجاد نشده‌اند. هر کدام از روترها که روشن می‌شوند ابتدا جدول مسیریابی مخصوص خود را ایجاد می‌کنند. و مثلا روتر A رکوردهای جدول مسیریابی خود را با دیگر روترهای مجاورش یعنی روترهای B و C و D به اشتراک می‌نهد. در این مثال برای تمرکز بیشتر، فقط نحوه نو شدن جدول مسیریابی روتر B باتوجه به اطلاعات روتر A توضیح داده خواهدشد. 

تصویر 3. جدول مسیریابی روترهای A و B و C و D پیش از آن‌که اطلاعات‌شان را با روترهای مجاورشان به اشتراک نهاده باشند.

تصویر 4 نشان می‌دهد که روتر B چگونه پس از دریافت رکوردهای جدید از روتر A، جدول مسیریابی خود را نوسازی می‌کند. پیش از توضیح این مورد باید توجه شود که در این مثال:

• منظور از Net، شبکه است و هر شبکه با شماره‌ای مشخص شده است.
• هر R یک رکورد اطلاعاتی است که از جدول مسیریابی روتر استخراج و برای دیگر روترهای مجاور ارسال می‌شود. محتوای هر رکورد، شماره شبکه و فاصله آن شبکه تا روتر موردنظر را نشان می‌دهد؛ مثلا Net 2, 1 یعنی فاصله شبکه Net 2 از روتر موردنظر 1 هاپ است. 
• منظور از Cost فاصله یا اصطلاحا هزینه پیمایش هر روتر تا روتر بعدی است. اگر دو روتر مستقیما به هم متصل باشند، هزینه پیمایش آن‌ها 1 خواهدبود.
• منظور از Next، روتر یا هاپ بعدی (Next hop) است. در شبکه‌های به‌هم پیوسته گاهی بسته‌های داده باید از چند روتر عبور کنند تا نهایتا به مقصد برسند. لذا هاپ بعدی، جهت یا بردار ارسال داده را مشخص می‌کند؛ یعنی مشخص می‌کند که روتر فعلی داده‌ها را باید به‌سمت کدام روتر ارسال کند، تا داده‌ها در مسیر درست به مقصد برسند.

تصویر 4. جدول مسیریابی روتر B پس از آن‌که رکوردهای R1 و R2 و R3 و R4 را از روتر A دریافت و جدول مسیریابی خود را باتوجه به اطلاعات آن رکوردها نوسازی کرده است. 

اکنون جدول مسیریابی روتر A و روتر B را در تصویر 3 و تصویر 4 مقایسه کنید. وقتی روتر B اولین رکورد یعنی Net 1, 1 را از روتر A دریافت می‌‌دارد، مسیر منتهی به شبکه Net 1 را در جدول مسیریابی‌اش جستجو می‌کند و چون آن را نمی‌یابد، شبکه Net 1 را به جدول مسیریابی خود اضافه می‌کند. روتر A مستقیما به شبکه Net 1 متصل است و لذا در جدول مسیریابی آن، فاصله یا اصطلاحا هزینه پیمایش (cost) مسیر، 1 است. اما روتر B برای دسترسی به شبکه Net 1 باید از روتر A یعنی از یک هاپ عبور کند. پس، هزینه یا فاصله روتر B تا شبکه Net 1 در جدول مسیریابی‌اش 2 خواهدبود. در قسمت هاپ بعدی (Next) نیز نام روتر A را درج می‌کند، بدین معنا که برای دسترسی به شبکه Net 2 باید از روتر A عبور کند.

وقتی روتر B رکورد دوم یعنی Net 2, 1 را از روتر A دریافت می‌کند، باز جدول مسیریابی‌اش را جستجو می‌کند و این‌بار درمی‌یابد که اطلاعات رکورد R2 یعنی Net 2, 1 پیش‌تر در جدول مسیریابی خودش موجود بوده است. اگر رکورد R2 را بپذیرد، باید هزینه مسیر را یک واحد افزایش دهد، اما آنچه از پیش در جدول خودش موجود بود، هزینه کمتری داردو پس روتر B رکورد R2 دریافتی از روتر A را لغو می‌کند و اطلاعات جدول خودش را نگاه می‌‌دارد. 

وقتی روتر B رکورد R3 یعنی Net 4, 1 را دریافت می‌کند، باز به جدول مسیریابی خود سر می‌زند اما مسیر منتهی به Net 4 را آن‌جا نمی‌یابد، پس Net 4 را به جدول مسیریابی خود اضافه می‌کند. مانند رکورد اول، هزینه را یک واحد افزایش می‌دهد تا 2 شود و در بخش هاپ بعدی (Next)، نام روتر A را درج می‌کند، زیرا دسترسی به شبکه Net 4 نیز با عبور از روتر A ممکن است.

همین روند با رکورد R4 نیز تکرار می‌شود. شبکه Net 5 در جدول مسیریابی روتر B نیست. پس روتر B آن را به جدول مسیریابی‌‌اش اضافه می‌کند، در بخش هزینه، عدد 2 و در بخش هاپ بعدی، نام روتر A را درج می‌کند.

روتر B اطلاعات روتر C را نیز با همین شیوه دریافت و بررسی می‌کند. روترهای A و C و D نیز با همین رویه جدول مسیریابی‌شان را به‌روزرسانی می‌کنند و اطلاعات جدید را به روترهای مجاورشان نیز می‌فرستند. جدول‌های نهایی مسیریابی تمام روترها برای سناریو فرضی این مثال، مانند تصویر 5 خواهدبود.

تصویر 5. جدول مسیریابی نهایی روترهای A و B و C و D پس از آن‌که جدول مسیریابی‌شان را باتوجه به اطلاعات دریافتی از یکدیگر به‌روزرسانی کرده‌اند.

در پروتکل‌های مسیریابی بردار فاصله، یک روتر اطلاعات مربوط به هم‌بندی (توپولوژی) تمام شبکه را نمی‌داند، بلکه بر اطلاعات دریافتی از روترهای مجاورش متکی است و به‌ همین سبب، مسیریابی بردار فاصله را «مسیریابی مبتنی بر شایعه» نیز می‌گویند. اما برای مثال، در پروتکل‌های مسیریابی حالت پیوند (Link-state routing)، روترها اطلاعات کامل هم‌بندی شبکه را می‌دانند. 

مزایای مسیریابی بردار فاصله

پیاده‌سازی پروتکل مسیریابی بردار فاصله در شبکه‌های کوچک ساده است. رفع عیب آن نیز بسیار ساده است.

پروتکل مسیریابی بردار فاصله در شبکه‌های کوچک افزونگی بسیار محدودی دارد.

معایب مسیریابی بردار فاصله

اگر یکی از لینک‌های بین روترها معیوب شود، همه روترهای دیگر در شبکه باید فورا اطلاعات‌شان را درباره مسیرهایی که در اثر معیوب شدن لینک تغییر یافته‌اند، به‌روزرسانی کنند. این مشکل را شمارش تا بی‌نهایت (count-to-infinity) نیز می‌نامند.

زمان لازم برای این‌که همه روترهای یک شبکه جدول مسیریابی دقیق و هماهنگی بسازند را زمان همگرایی (convergence time) می‌گویند. در شبکه‌های بزرگ و پیچیده، تشکیل و هماهنگ شدن جدول‌ها زیاد طول می‌کشد.

هر تغییری در جدول مسیریابی متناوبا به دیگر روترهایی نیز که در شبکه ترافیک ایجاد می‌کنند، مخابره می‌شود.

خلاصه نکات

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