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

مقدمه

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

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

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

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

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

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

• بهینه سازی مسیریابی در شبکه های سیار موردی با استفاده از الگوریتم های ترکیبی مبتنی بر دلیوج — کلیک کنید.

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

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

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

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

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

• چالش‌ های مسیریابی در Vanet (سمینار در مورد چالش‌های مسیریابی و برنامه‌های کاربردی) — کلیک کنید.

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

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

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

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

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

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

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

• الگوریتم متمرکز (Centralized)

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

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

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

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

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

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

• الگوریتم مستقل (Isolated)

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

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

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

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

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

• الگوریتم توزیع شده (Distributed)

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

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

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

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

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

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

• سیل آسا (Flooding)

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

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

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

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

گام شمارش

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

درخت پوشا

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

• پاورپوینت در مورد درخت پوشای کمینه — Minimum spanning tree — کلیک کنید.

• پیاده روی تصادفی (Random walk)

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

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

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

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

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