مجموعه آموزشی پی استور - https://programstore.ir

الگوریتم های مسیریابی شبکه | آموزش جامع انواع الگوریتم مسیریابی در شبکه

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

مقدمه

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

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

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

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

الگوریتم های مسیریابی شبکه عمدتاً برای پیشرفت کیفیت شبکه های کامپیوتری [2] کار می‌کنند. این الگوریتم‌ها روی پروتکل‌های خاصی کار می‌کنند و مسیر را می‌توان با استفاده از روش‌های مختلف الگوریتم‌ها محاسبه کرد. بر اساس نوع شبکه و همچنین کاربرد آن، هر الگوریتم را می‌توان اعمال کرد. این الگوریتم‌ها باید ویژگی‌های متعددی مانند ثبات، صحت، کارایی، سادگی، مقاوم در برابر نفوذ [3] و استحکام را داشته باشند.

انواع الگوریتم های مسیریابی

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

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

الگوریتم های مسیریابی تطبیقی (Adaptive routing algorithms)

الگوریتم های مسیریابی تطبیقی  یا Adaptive routing algorithms [5] الگوریتم‌هایی هستند که تغییرات به‌صورت خودکار در مسیریابی اعمال می‌شود و دیگر لازم نیست خودمان دستی تغییرات را به الگوریتم بدهیم. الگوریتم های مسیریابی تطبیقی که با نام الگوریتم‌های مسیریابی پویا نیز شناخته می‌شوند، بسته به شرایط شبکه تصمیمات مسیریابی را به‌صورت پویا اتخاذ می‌کنند، همچنین جدول مسیریابی را بسته به ترافیک شبکه و توپولوژی می‌سازند. آنها سعی می‌کنند مسیر بهینه‌شده را بسته به تعداد گام یا پرش، زمان عبور و مسافت محاسبه کنند.

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

مزیت پروتکل‌های سودآور به شرح زیر است:

  1. منجر به ایجاد یک مسیر با حداقل طول می‌شوند.
  2. می‌توان آن‌ها را برای اثبات رها شدن از بن‌بست موجود ایجاد کرد.
  3. زمانی که کانال‌های معیوب در شبکه وجود دارند، پروتکل‌های مسیریابی نادرست سودمند هستند. چراکه تحت چنین شرایطی، پروتکل‌های مسیریابی نادرست شانس بیشتری برای یافتن مسیر مناسب دارند.

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

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

  1. مسیریابی سودآور پیش‌رونده منتظر می‌ماند تا یک کانال سودآور آزاد شود.
  2. یک پروتکل مسیریابی نادرست پیش‌رونده یک کانال آزاد غیر سودآور را امتحان می‌کند.
  3. مسیریابی عقب‌گرد به‌عقب رفته و دوباره در گره قبلی شروع می‌شود.

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

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

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

1) یک فرآیند به‌عنوان هماهنگ‌کننده (Coordinator) انتخاب می‌شود.

2) فرآیندی که می‌خواهد منبع را در اختیار بگیرد پیامی به هماهنگ‌کننده می‌فرستد که تعیین می‌کند چه منبعی را می‌خواهد.

3) اگر فرآیند دیگری منبع را در دسترس نداشته باشد، هماهنگ‌کننده با ارسال یک پیام جواب دهی، منبع را به آن فرآیند می‌دهد.

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

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

1) Hot potato: الگوریتم مسیریابی سیب‌زمینی داغ الگوریتمی است که در آن روترهای یک شبکه هیچ بافری برای ذخیره بسته‌ها قبل از انتقال به آخرین مقصد از پیش تعیین‌شده خود ندارند. در یک موقعیت مسیریابی معمولی، هنگامی‌که بسته‌های متعدد به یک کانال خروجی می‌روند، بسته‌هایی که بافر نیستند برای جلوگیری از تراکم رها می‌شوند. بسته در همه‌جا پرتاب می‌شود، مانند یک “سیب‌زمینی داغ” که ممکن است به‌دوراز مقصد منتقل شود. در این حالت الگوریتم بسته‌ها را رها نمی‌کند بلکه به حرکت خود ادامه می‌دهد.

2) Hot potato + SR: در این روش علاوه بر خلوت بودن مسیر وزن مسیر را نیز در نظر می‌گیریم. وزن مسیر عددی بین 0و 1 است. این الگوریتم مسیری را انتخاب می‌کند که هم کوتاه باشد و هم زیاد شلوغ نباشد یعنی وزن مسیر مساعد باشد.

3) Backward Learning: یک فرستنده با یک گیرنده پیغامی را ردوبدل می‌کند. فرض کنیم فرستنده سه مسیر را می‌شناسد یعنی در جدول مسیریابی خود تا گیرنده موردنظر سه مسیر دارد که به نظر خودش بهترین مسیرهایی بوده که می‌توانسته تا مقصد موردنظر انتخاب کند. حالا گیرنده یک پاسخ می‌دهد، وقتی فرستنده پاسخ را دریافت می‌کند و مسیر آن را با مسیرهای ذخیره‌شده در جدول خود مقایسه می‌کند، می‌بیند این مسیر از سه مسیر قبلی کوتاه‌تر است پس این مسیر جدید را جایگزین یکی از مسیرهای خود می‌کند.

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

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

الگوریتم های مسیریابی غیر تطبیقی (Non_ Adaptive routing algorithms)

نوع دوم الگوریتم های مسیریابی شبکه، الگوریتم های مسیریابی غیر تطبیقی یا Non_ Adaptive routing algorithms [8] هستند که به‌عنوان الگوریتم های مسیریابی استاتیک نیز شناخته می‌شوند، یک جدول مسیریابی استاتیک برای تعیین مسیر ارسال بسته‌ها ایجاد می‌کنند. جدول مسیریابی استاتیک بر اساس اطلاعات مسیریابی ذخیره‌شده در مسیریاب‌ها هنگام راه‌اندازی شبکه ساخته می‌شود.

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

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

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

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

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

اعداد دنباله ای

هر بسته با شماره ترتیبی ارائه می‌شود. هنگامی‌که یک گره‌بسته را دریافت می‌کند، شماره مبدأ و مقصد آن را مشاهده می‌کند، اگر گره متوجه شود که قبلاً بسته مشابهی را ارسال کرده است، بسته را ارسال نمی‌کند و آن را کنار می‌گذارد.

گام شمارش

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

درخت پوشا

در این روش هر بسته با ایجاد یک درخت پوشا [10] در مبدأ، تنها در یک اتصال که به مقصد منتهی می‌شود، منتقل می‌گردد. این روش از ایجاد حلقه‌ها در انتقال جلوگیری می‌کند اما تنها زمانی امکان‌پذیر است که تمام گره‌های انتقالی توپولوژی شبکه را بدانند.

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

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

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

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

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

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

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

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