مسیریابی چندراهی

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

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

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

 CMR واقعی 
شکل قدرتمندتر CMR (CMR واقعی) از صرفاً ارائهٔ مسیرهایی برای برنامه‌ها که می‌توانند به آنها متصل شوند فراتر می‌رود. CMR واقعی تمام مسیرهای موجود را در یک مسیر مجازی مجزا جمع می‌کند.

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

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

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

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

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

 منابع 
 802.1aq کوتاهترین مسیر اتصال
 مسیریابی چند راهی با هزینه برابر
 چند راهی TCP
 S. -J. لی و م. گرلا، «تقسیم مسیریابی چند راهی با مسیرهای کاملاً جدا از هم در شبکه‌های موقت»، Proc. ICC 2001، جلد. ۱۰، ص. ۳۲۰۱–۳۲۰۵، ژوئن ۲۰۰۱.
 A. Nasipuri , R. Castaneda و SR Das، «عملکرد مسیریابی چند راهی برای پروتکل‌های تقاضا در شبکه‌های موقت تلفن همراه»، شبکه‌های موبایل و برنامه‌ها، جلد. ۶، نه ۴، ص. ۳۳۹–۳۴۹، آگوست ۲۰۰۱.
 MK Marina و SR Das «مسیریابی بردار از راه دور مسیری چند منظوره در شبکه‌های موقت»، Proc. ICNP 2001، صص. ۱۴–۲۳، نوامبر ۲۰۰۱.
 A. Tsirigos و ZJ Haas، «مسیریابی چند راهی در حضور تغییرات توپولوژیک مکرر»، مجله ارتباطات IEEE، جلد ۱. ۳۹، نه ۱۱، ص. ۱۳۲–۱۳۸، نوامبر ۲۰۰۱.
 H. Lim , K. Xu و M. Gerla، «عملکرد TCP در مسیریابی چند راهی در شبکه‌های Ad Hoc موبایل»، Proc. ICC 2003، جلد. ۲، ص. ۱۰۶۴–۱۰۶۸، مه ۲۰۰۳.
 A. Tsirigos و ZJ Haas، «تجزیه و تحلیل مسیریابی چند راهی - قسمت اول: تأثیر نسبت تحویل بسته ها»، IEEE ترانس. ارتباطات بی‌سیم، جلد ۱ ۳، نه ۱، ص. ۱۳۸–۱۴۶، ژانویه ۲۰۰۴.
 S. Card, F. Tims، «مسیریابی همزمان چند مسیره و حمل و نقل در یک درگاه بی سیم تلفن همراه»، مقاله غیر طبقه‌بندی شده ارائه شده در جلسه طبقه‌بندی شده MILCOM 2004، در صورت درخواست پشتیبانی در سایت www.critical.com.
 N. Kammenhuber، «مسیریابی تطبیقی ترافیکی»، فصل ۶٫۲ «کار مرتبط»، http://mediatum.ub.tum.de/doc/635601/635601.pdf

برای بهبود امنیت شبکه:
 W. Lou و Y. Fang، "" رویکرد مسیریابی چند راهی برای تحویل امن داده‌ها "،" Proc. MILCOM 2001، جلد. ۲، صص ۱۴۶۷–۱۴۷۳، اکتبر ۲۰۰۱.
 CK-L لی، X. -H. لین، و Y. -K. Kwok، "رویکرد مسیریابی چند راهی Ad Hoc برای مبارزه با عدم امنیت لینک بی سیم"، Proc. ICC 2003، جلد. ۱، ص. ۴۴۸–۴۵۲، مه ۲۰۰۳.
 S. Bouam و J. Ben-Othman، "امنیت داده‌ها در شبکه‌های موقت با استفاده از مسیریابی چند راهی"، Proc. PIMRC 2003، جلد ۲، ص. ۱۳۳۱–۱۳۳۵، سپتامبر ۲۰۰۳.
 P. Papadimitratos و ZJ Haas، "انتقال امن اطلاعات در شبکه‌های تلفن همراه موقت"، Proc. ACM WiSe 2003، pp. 41–50، سپتامبر ۲۰۰۳.
 Zhi Li و Yu-Kwong Kwok، "رویکرد مسیریابی جدید چند راهی برای افزایش امنیت TCP در شبکه‌های بی سیم Ad Hoc" , Proc. کارگاه‌های آموزشی ICPP، ص. ۳۷۲–۳۷۹، ژوئن ۲۰۰۵.

 پیوند به بیرون 
 کتابشناسی مسیریابی چند راهی پروفسور دیجیانگ هوانگ: 
رده:الگوریتم‌های مسیریابی