الگوریتم مسیریابی آشنائی با الگوریتم‌های مسیریابی در شبکه – آموزش شبکه درس 27

الگوریتم مسیریابی در لایه شبکه

برای جابجا کردن پک‌های داده از منبع خودشان به سمت مقصد، لایه شبکه باید بهترین مسیری را که پک‌های داده می‌توانند از طریق آن جابجا شوند را مشخص کند. چه لایه شبکه ارائه کننده سرویس دیتاگرام باشد و یا آن یک سرویس مدار مجازی سازی شده را ارائه کند، اصلی‌ترین وظیفه لایه شبکه آن است که بتواند بهترین مسیر را به ما معرفی کند. پورتکل‌های مسیریابی اساساً برای انجام چنین کاری طراحی می‌شوند. یک پروتکل مسیریابی (Routing Protocol) در واقع یک الگوتریم مسیریابی (Routing Algorithm) است که می‌تواند بهترین مسیر از منبع به مقصد را مشخص کند. بهترین مسیر می‌تواند «کم هزینه‌ترین مسیر» از سمت منبع به مقصد باشد.

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

طبقه‌بندی یک الگوریتم مسیریابی

الگوریتم مسیریابی به دو دسته بندی کلی تقسیم می‌شود:

• الگوریتم مسیریابی تطابقی (Adaptive Routing Algorithm)؛
• الگوریتم مسیریابی غیرتطابقی (Non-Adaptive Routing Algorithm)؛

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

الگوریتم مسیریابی تطابقی (Adaptive Routing Algorithm)

یک الگوریتم مسیریابی تطابقی به عنوان «الگوریتم مسیریابی دینامیکی – Dynamic Routing Algorithm» نیز شناخته می‌شود. این الگوریتم بر مبنای‌ ترافیک و توپولوژی شبکه درباره مسیرهای موجود تصمیم گیری می‌کند. اصلی‌ترین پارامترهای مرتبط به الگوریتم شامل تعداد‌هاپ‌ها (Hop Count)، فاصله (Distance) و زمان انتقال داده (Transit Time) می‌شود.

یک الگوریتم مسیریابی تطابقی می‌تواند در یکی از سه دسته زیر قرار گرفته باشد:

• الگوریتم‌های مرکزی (Centralized Algorithm): این الگوریتم‌ها به عنوان «الگوریتم‌های مسیریابی عمومی – Global Routing Algorithm» نیز شناخته می‌شود و آن حداقل هزینه میانه منبع و مقصد را به وسیله دانش کامل و عمومی خودش درباره شبکه محاسبه می‌کند. این الگوریتم ارتباط میان گره‌های و هزینه لینک را به عنوان ورودی گرفته و از این اطلاعات پیش از هر محاسبه‌ای استفاده می‌کند. الگوریتم حالت لینک (Link State Algorithm)، یکی از الگوریتم‌های مرکزی به حساب می‌رود زیرا آن از هزینه هر کدام از لینک‌های موجود در شبکه آگاه است.
• الگوریتم‌های ایزوله شده (Isolation Algorithm): این دسته از الگوریتم‌ها اطلاعات مسیر را به جای به دست آوردن اطلاعات کلی از دیگر گره‌های در شبکه از طریق اطلاعات محلی به دست می‌آورد.
• الگوریتم‌های توزیع شده (Distributed Algorithm): این الگوریتم به این خاطر الگوریتم توزیع شده نامیده می‌شود که هزینه حداقلی میان منبع و مقصد را به شیوه توزیع شده و غیرتکراری به دست می‌آورد. در الگوریتم‌های غیرمتمرکز هیچ گره‌ای دانشی درباره کل شبکه و هزینه لینک‌های فی مابین ندارد. هر کدام از گره‌ها تنها حاوی اطلاعاتی درباره لینک‌هائی است که به صورت مستقیم به آن متصل شده است و در نتیجه همیشه یک فرایند تکراری برای محاسبه حداقل هزینه تا مقصد باید انجام شود. یک الگوریتم بردار فاصله (Distance Vector Algorithm)، یک الگوریتم غیرمتمرکز است که هرگز هزینه مسیر تا مقصد را به صورت کامل محاسبه نمی کند، بلکه در هر گره بر اساس دانش درباره کم هزینه‌ترین مسیر تصمیم گیری می‌کند. در نتیجه کم هزینه‌ترین مسیر را به صورت گام به گام استخراج می‌کند.

الگوریتم‌های مسیریابی غیرتطابقی (Non-adaptive Routing Algorithm)

یک الگوریتم مسیریابی غیرتطابقی به عنوان «الگوریتم مسیریابی استاتیک – Static Routing Algorithm» شناخته می‌شود. هنگامی که یک شبکه ایجاد می‌شود، اطلاعات مسیرها در درون روترها ذخیره می‌شوند. الگوریتم‌های مسیریابی غیرتطابقی بر اساس‌ترافیک موجود در شبکه و یا توپولوژی شبکه هیچ تصمیم گیری نمی کنند.

الگوریتم‌های مسیریابی غیرتطابقی دارای دو نوع کلی هستند:

• جریانی (Flooding): در این مورد هر پک ورودی اطلاعات به تمام لینک‌های خروجی فرستاده می‌شود و انتظار می‌رود که از یکی از آن‌ها پاسخی دریافت شود. عیب این روش در آن است که ممکن است در یک گره چندین پک اطلاعاتی مشابه وجود داشته باشند و در نتیجه کار ارسال اطلاعات با اختلال روبرو شود.
• پیمایش‌های تصادفی (Random Walks): در مورد الگوریتم پیمایش تصادفی، یک پک اطلاعات به وسیله یک گره و به صورت تصادفی به سمت گره‌های همسایه اش فرستاده می‌شود. مزیت این کار آن است که می‌توان از مسیرهای متنوع به شکل مفیدی استفاده کرد.

تفاوت میان الگوریتم‌های تطابقی و غیرتطابقی مسیریابی