مسیریابی فرایند انتخاب مسیری برای ترافیک در یک شبکه یا بین یا از طریق چندین شبکه است. بطور گسترده ، مسیریابی در انواع مختلفی از شبکه ها انجام می شود ، از جمله شبکه های مداربسته ، مانند شبکه تلفنی عمومی (PSTN) ، و شبکه های رایانه ای ، مانند اینترنت .
در شبکه های تعویض بسته ای ، مسیریابی تصمیم گیری سطح بالاتری است که بسته های شبکه را از منبع خود به سمت مقصد خود از طریق گره های شبکه میانی توسط مکانیسم های ارسال بسته خاص هدایت می کند. حمل و نقل بسته ها انتقال از بسته های شبکه از یک رابط شبکه به دیگری است. گره های میانی به طور معمول دستگاه های سخت افزاری شبکه مانند روتر ، دروازه ، فایروال یا سوئیچ هستند . رایانه های دارای هدف عمومی بسته ها را نیز به جلو هدایت می کنند و مسیریابی را انجام می دهند ، اگرچه هیچ سخت افزار مخصوص بهینه ای برای انجام کار ندارند.
فرایند مسیریابی معمولاً بر اساس جداول مسیریابی هدایت را هدایت می کند . جداول مسیریابی رکوردی از مسیرها را به مقصد مقصد های مختلف شبکه را حفظ می کند. جداول مسیریابی ممکن است توسط یک مدیر مشخص شود که با مشاهده ترافیک شبکه آموخته شده یا با کمک پروتکل های مسیریابی ساخته شده است .
مسیریابی ، به معنای باریک تر این اصطلاح ، اغلب به مسیریابی IP اطلاق می شود و با پل زدن در تضاد است . مسیریابی IP فرض می کند که آدرس های شبکه ساختار یافته اند و آدرس های مشابه حاکی از نزدیکی درون شبکه هستند. آدرس های ساختار یافته اجازه ورود جدول مسیریابی را می دهند تا مسیر گروهی از دستگاه ها را نشان دهند. در شبکه های بزرگ ، آدرس دهی ساختار یافته (مسیریابی ، به معنای باریک) از آدرس دهی بدون ساختار (پل) فراتر می رود. مسیریابی به شکل غالب آدرس دهی در اینترنت تبدیل شده است. پل سازی هنوز هم به طور گسترده در شبکه های محلی استفاده می شود .
فهرست
طرح های تحویل [ ویرایش ]
طرح های مسیریابی در نحوه ارائه پیام ها متفاوت است:
- Unicast با استفاده از یک ارتباط یک به یک بین یک فرستنده و مقصد ، یک پیام را به یک گره خاص منتقل می کند : هر آدرس مقصد به طور منحصر به فرد یک نقطه انتهایی گیرنده را مشخص می کند.
- پخش برای همه گره های شبکه با استفاده از یک انجمن مشترک ، پیامی را ارائه می کند . یک داده داده از یک فرستنده به همه نقاط انتهایی احتمالاً مرتبط با آدرس پخش هدایت می شود. شبکه بطور خودکار داده های مورد نیاز را برای دسترسی به همه گیرندگان در محدوده پخش تکرار می کند ، که به طور کلی یک زیر شبکه کامل است.
- Multicast پیامی را به گروه گره هایی ارسال می کند که علاقه مند به دریافت پیام با استفاده از یک ارتباط یک به یک از بسیاری یا بسیاری از بسیاری از آنها هستند. داده ها به طور همزمان در یک انتقال به بسیاری از گیرندگان مسیریابی می شوند. Multicast با پخش متفاوت است از آنجا که آدرس مقصد یک زیر مجموعه ، و نه لزوما همه ، گره های قابل دسترسی را تعیین می کند.
- Anycast با استفاده از یک انجمن یک به یک از بسیاری از افراد در جایی که داده ها به هر یک از اعضای گروهی از گیرنده های بالقوه مسیریابی می شوند ، به هر یک از گروه های گره ای پیام ارسال می کنند. مشخص شده توسط همان آدرس مقصد. الگوریتم مسیریابی گیرنده منفرد را از گروه انتخاب می کند که براساس آن نزدیکترین بسته به اندازه گیری فاصله است.
- Geocast بر اساس موقعیت جغرافیایی آنها ، به گروهی از گره ها در شبکه پیامی ارسال می کند . این یک فرم تخصصی برای آدرس دهی چند مرحله ای است که توسط برخی پروتکل های مسیریابی برای شبکه های ad hoc تلفن همراه مورد استفاده قرار می گیرد.
Unicast شکل غالب ارسال پیام در اینترنت است. در این مقاله به الگوریتم های مسیریابی منحصر به فرد می پردازیم.
توزیع توپولوژی [ ویرایش ]
با مسیریابی استاتیک ، شبکه های کوچک ممکن است از جداول مسیریابی پیکربندی شده استفاده کنند. شبکه های بزرگتر دارای توپولوژی پیچیده ای هستند که می توانند به سرعت تغییر کنند ، و ساخت دستی جداول مسیریابی را غیر ممکن می کنند. با این وجود ، اکثر شبکه های تلفنی عمومی (PSTN) از جداول مسیریابی از پیش محاسبه شده استفاده می کنند ، در صورت مسدود شدن مستقیم ترین مسیر ، مسیرهای سقوط دارند ( مسیریابی را در PSTN ببینید ).
مسیریابی پویا تلاش می کند تا با ساخت جداول مسیریابی بطور خودکار و بر اساس اطلاعاتی که توسط پروتکل های مسیریابی انجام می شود ، این مشکل را حل کند و به شبکه اجازه دهد تا در جلوگیری از خرابی و انسداد شبکه ، تقریباً به طور مستقل عمل کند. مسیریابی پویا بر اینترنت حاکم است. نمونه هایی از پروتکل های مسیریابی پویا و الگوریتم ها عبارتند از پروتکل اطلاعات مسیریابی (RIP) ، کوتاهترین مسیر اول باز (OSPF) و پروتکل مسیریابی پیشرفته داخلی دروازه (EIGRP).
الگوریتم های بردار از راه دور [ ویرایش ]
مقاله اصلی: پروتکل مسیریابی بردار از راه دور
الگوریتم های وکتور فاصله از الگوریتم Bellman-Ford استفاده می کنند . این روش برای هر یک از پیوندهای بین هر گره در شبکه یک شماره هزینه اختصاص می دهد . گره ها اطلاعات را از نقطه A به نقطه B از طریق مسیری ارسال می كنند كه منجر به كمترین هزینه كل (یعنی مجموع هزینه های پیوندها بین گره های مورد استفاده) می شود.
هنگامی که یک گره برای اولین بار شروع می شود ، فقط از همسایگان نزدیک خود و هزینه مستقیم در دستیابی به آنها اطلاع دارد. (این اطلاعات - لیست مقصد ، کل هزینه برای هر یک ، و امید بعدی برای ارسال اطلاعات برای رسیدن به آنجا - جدول مسیریابی یا جدول مسافت را تشکیل می دهد .) هر گره ، به طور منظم ، به هر گره همسایه ارسال می کند. ارزیابی فعلی خود از کل هزینه برای رسیدن به تمام مقصدی که از آنجا می شناسد. گره های همسایه این اطلاعات را بررسی کرده و آن را با آنچه که قبلاً می دانستند مقایسه می کنند. هر چیزی که نشان دهنده پیشرفت در مورد آنچه در گذشته است باشد ، در جدول خود وارد می کنند. با گذشت زمان ، تمام گره های شبکه بهترین هاپ بعدی و هزینه کل را برای کلیه مقصد ها کشف می کنند.
هنگامی که یک گره شبکه فرو می رود ، هر گره ای که از آن به عنوان هاپ بعدی استفاده کرده است ، ورودی را دور می کند و اطلاعات مسیریابی به روز شده را به همه گره های مجاور منتقل می کند ، که به نوبه خود روند را تکرار می کنند. سرانجام ، تمام گره های شبکه به روزرسانی ها را دریافت می کنند و مسیرهای جدیدی را به تمام مقصدهایی که گره پایین را شامل نمی شوند ، کشف می کنند.
الگوریتم های حالت پیوند [ ویرایش ]
مقاله اصلی: پروتکل مسیریابی حالت پیوند
هنگام استفاده از الگوریتم های حالت پیوند ، نقشه گرافیکی شبکه داده های بنیادی است که برای هر گره استفاده می شود. برای تهیه نقشه خود ، هر گره با اطلاعاتی در مورد سایر گره هایی که می تواند به آن وصل شود ، کل شبکه را آب می کند. سپس هر گره به طور مستقل این اطلاعات را در نقشه جمع می کند. با استفاده از این نقشه ، هر روتر بطور مستقل با استفاده از الگوریتم کوتاهترین مسیرهای استاندارد مانند الگوریتم Dijkstra ، کمترین هزینه را از خود به هر گره دیگر تعیین می کند . نتیجه یک نمودار درخت استریشه در گره فعلی ، به گونه ای که مسیر عبور از درخت از ریشه به هر گره دیگر کمترین هزینه برای آن گره است. سپس این درخت برای ساخت جدول مسیریابی ، که بهترین هاپ بعدی برای دستیابی از گره فعلی به هر گره دیگر را مشخص می کند ، خدمت می کند.
الگوریتم مسیریابی حالت پیوند بهینه شده [ ویرایش ]
مقاله اصلی: پروتکل مسیریابی حالت پیوند بهینه شده
یک الگوریتم مسیریابی حالت پیوند بهینه شده برای شبکه های ad hoc همراه ، پروتکل مسیریابی بهینه شده لینک حالت (OLSR) است. [1] OLSR فعال است؛ از پیام های سلام و کنترل توپولوژی (TC) برای کشف و انتشار اطلاعات حالت پیوند از طریق شبکه تعاونی تلفن همراه استفاده می کند. با استفاده از پیام های سلام ، هر گره اطلاعات همسایگان 2 هاپ را کشف می کند و مجموعه ای از رله های چند منظوره (MPR) را انتخاب می کند. MPR ها OLSR را از سایر پروتکل های مسیریابی حالت پیوند متمایز می کنند.
پروتکل بردار مسیر [ ویرایش ]
مقاله اصلی: پروتکل مسیریابی-بردار مسیر
بردار مسافت و مسیریابی حالت پیوند هر دو پروتکل مسیریابی درون دامنه هستند. آنها در داخل یک سیستم خودمختار مورد استفاده قرار می گیرند ، اما بین سیستم های خودمختار نیستند. هر دو پروتکل مسیریابی در شبکه های بزرگ غیرقابل نفوذ می شوند و نمی توانند در مسیریابی درون دامنه مورد استفاده قرار گیرند . مسیریابی بردار از راه دور در صورتی که بیش از چند هاپ در دامنه وجود داشته باشد در معرض عدم ثبات است. مسیریابی حالت پیوند برای محاسبه جداول مسیریابی به منابع قابل توجهی نیاز دارد. همچنین به دلیل جاری شدن سیل ترافیک سنگینی ایجاد می کند.
مسیریابی بردار مسیر برای مسیریابی درون دامنه استفاده می شود. شبیه مسیریابی بردار مسافت است. مسیریابی بردار مسیر فرض می کند که در هر سیستم خودمختار یک گره (می تواند تعداد زیادی وجود داشته باشد) به نمایندگی از کل سیستم خودمختار عمل می کند. به این گره گره بلندگو گفته می شود. گره بلندگو یک جدول مسیریابی ایجاد می کند و آن را به گره بلندگوهای همسایه در سیستم های خودمختار همسایه تبلیغ می کند. ایده همان مسیریابی بردار مسافت است به جز اینکه فقط گره های بلندگو در هر سیستم خودمختار می توانند با یکدیگر ارتباط برقرار کنند. گره بلندگو مسیر و نه متریک گره های موجود در سیستم خودمختار یا سایر سیستم های خودمختار را تبلیغ می کند.
الگوریتم مسیریابی بردار مسیر شبیه به الگوریتم بردار مسافت است به این معنا که هر روتر مرزی مقصدهایی را که می تواند به روتر همسایه خود برسد تبلیغ می کند. با این حال ، به جای شبکه های تبلیغاتی از نظر یک مقصد و فاصله از آن مقصد ، شبکه ها به عنوان آدرس مقصد و شرح مسیر برای رسیدن به آن مقصد تبلیغ می شوند. مسیر ، از نظر دامنه ها (یا کنفدراسیون ها) که تاکنون پیموده شده ، بیان شده است در یک ویژگی ویژه مسیر انجام می شود که دنباله دامنه های مسیریابی را که از طریق آن اطلاعات دستیابی از آن گذشته است ، ثبت می کند. مسیری به عنوان یک جفت شدن بین یک مقصد و صفات مسیر آن مقصد ، بنابراین نام ، مسیریابی بردار مسیر مشخص می شود. روترها برداری دریافت می کنند که شامل مسیرهایی برای مجموعه مقصد است. [2]
انتخاب مسیر [ ویرایش ]
انتخاب مسیر شامل استفاده از متریک مسیریابی برای چندین مسیر برای انتخاب (یا پیش بینی) بهترین مسیر است. اکثر الگوریتم های مسیریابی فقط از یک مسیر شبکه همزمان استفاده می کنند. تکنیک های مسیریابی چند منظوره استفاده از چندین مسیر جایگزین را امکان پذیر می کند.
در شبکه های رایانه ای ، متریک توسط یک الگوریتم مسیریابی محاسبه می شود و می تواند اطلاعاتی مانند پهنای باند ، تأخیر شبکه ، تعداد هاپ ، هزینه مسیر ، بار ، MTU (واحد انتقال حداکثر) ، قابلیت اطمینان و هزینه ارتباط را پوشش دهد (برای مثال به این بررسی مراجعه کنید. لیستی از معیارهای مسیریابی پیشنهادی). جدول مسیریابی تنها بهترین مسیرهای ممکن را ذخیره می کند ، در حالی که پایگاه های داده پیوندی یا توپولوژیکی ممکن است سایر اطلاعات را نیز ذخیره کنند.
در صورت وجود مسیرهای همپوشانی یا مساوی ، الگوریتم ها عناصر زیر را در نظر می گیرند تا تصمیم بگیرند کدام مسیرها را در جدول مسیریابی نصب کنید (مرتب سازی بر اساس اولویت):
- پیشوند طول : جایی که ماسک های زیر شبکه دیگر ترجیح داده شود (مستقل از اینکه در پروتکل مسیریابی باشد یا در پروتکل مسیریابی متفاوت باشد)
- متریک : در جایی که یک متریک / هزینه کمتر ترجیح داده می شود (فقط در یک پروتکل مسیریابی یکسان معتبر است)
- فاصله اداری : در جایی که مسیری که از یک پروتکل مسیریابی معتبر تر آموخته می شود ترجیح داده شود (فقط بین پروتکل های مختلف مسیریابی معتبر است)
از آنجا که یک متریک مسیریابی مختص پروتکل مسیریابی مشخص است ، روترهای چند پروتکل برای انتخاب بین مسیرهای آموخته شده از پروتکل های مسیریابی مختلف باید از برخی اکتشافی خارجی استفاده کنند. برای مثال ، روترهای سیسکو مقداری را به عنوان فاصله اداری به هر مسیر نسبت می دهند ، جایی که مسافت های اداری کوچکتر مسیری را که از یک پروتکل ظاهرا قابل اطمینان تر یاد می شود ، نشان می دهند.
یک مدیر شبکه محلی ، در موارد خاص ، می تواند مسیرهای مخصوص میزبان را به یک دستگاه خاص تنظیم کند که کنترل بیشتری بر استفاده از شبکه ، اجازه آزمایش و امنیت کلی بهتر داشته باشد. این برای اشکال زدایی در اتصالات شبکه یا جداول مسیریابی مفید است.
در بعضی از سیستم های کوچک ، یک دستگاه واحد مرکزی تصمیم می گیرد مسیر کامل هر بسته را قبل از زمان تعیین کند. در برخی از سیستم های کوچک دیگر ، هر کدام از دستگاه های لبه بسته ای را به شبکه تزریق می کنند تصمیم می گیرند پیش از موعد مسیر کامل آن بسته خاص را تعیین کند. در هر دو سیستم ، آن دستگاه برنامه ریزی مسیر باید اطلاعات زیادی در مورد اتصال دستگاه ها به شبکه و نحوه اتصال آنها به یکدیگر کسب کند. پس از در اختیار داشتن این اطلاعات ، می تواند از الگوریتمی مانند الگوریتم جستجوی A * برای یافتن بهترین مسیر استفاده کند.
در سیستم های پر سرعت ، بسته های زیادی در هر ثانیه منتقل می شوند که برای یک دستگاه واحد غیرقابل دسترسی است تا بتواند مسیر کامل برای هر بسته را محاسبه کند. سیستم های پر سرعت اولیه با راه اندازی کانال رله سوئیچینگ مدار یک بار برای اولین بسته بین منبع و برخی از مقصد با این مسئله سر و کار داشتند. بسته های بعدی بین همان منبع و همان مقصد همچنان بدون محاسبه مجدد تا زمان ریزش کانال ، همان مسیر را دنبال می کنند . سیستم های پر سرعت بعد ، بسته های مختلفی را به شبکه تزریق می کنند بدون اینکه هیچ وسیله ای هنوز هم مسیری کامل را برای چندین بسته محاسبه کند.
در سیستم های بزرگ ، اتصالات زیادی بین دستگاه ها وجود دارد ، و آن اتصالات آنقدر دگرگون می شوند ، برای هر وسیله ای غیر ممکن است که حتی می داند چگونه تمام دستگاه ها به یکدیگر متصل هستند ، بسیار کمتر از یک مسیر کامل از طریق آنها محاسبه می کنند. چنین سیستمهایی معمولاً از مسیریابی بعدی هاپ استفاده می کنند .
اکثر سیستم ها از یک الگوریتم مسیریابی تعیین کننده پویا استفاده می کنند: وقتی یک وسیله مسیری را به مقصد نهایی خاص خود انتخاب می کند ، آن دستگاه همیشه مسیری را به همان مقصد منتقل می کند تا زمانی که اطلاعاتی دریافت کند که باعث می شود فکر می کند مسیر دیگری بهتر است. چند الگوریتم مسیریابی از الگوریتم قطعی برای یافتن پیوند "بهترین" برای یک بسته استفاده نمی کنند تا از مبدأ اصلی خود به مقصد نهایی خود برسد. در عوض ، برای جلوگیری از احتقان در سیستم های روشن یا نقاط داغ شبکه در سیستم های بسته ، چند الگوریتم از یک الگوریتم تصادفی parad پارادایم Valiant — استفاده می کند که مسیری را به یک مقصد متوسط به طور تصادفی انتخاب شده و از آنجا به مقصد نهایی واقعی خود می رساند. [3] [4] در بسیاری از سوئیچ های تلفن اولیه ، یک تصادف کننده استاغلب برای انتخاب شروع مسیر از طریق پارچه تعویض چند مرحله ای استفاده می شد .
بسته به کاربردی که انتخاب مسیر برای آن انجام شده است ، می توانید از معیارهای مختلفی استفاده کنید. به عنوان مثال ، برای درخواست های وب می توان از حداقل مسیرهای تأخیر استفاده کرد تا زمان بارگذاری صفحه وب به حداقل برسد ، یا برای انتقال داده های انبوه می توان کمترین مسیری را برای تعادل بار در شبکه و افزایش بازده انتخاب کرد. هدف انتخاب مسیر محبوب ، کاهش میانگین زمان اتمام گردش ترافیک و کل مصرف پهنای باند شبکه است که اساساً منجر به استفاده بهتر از ظرفیت شبکه می شود. اخیراً ، یک متریک انتخاب مسیر پیشنهاد شده است که تعداد کل بایتهای برنامه ریزی شده در لبه ها در هر مسیر را به عنوان یک معیار انتخاب محاسبه می کند. [5] تجزیه و تحلیل تجربی از چندین معیار انتخاب مسیر ، از جمله این پیشنهاد جدید ، در دسترس قرار گرفته است. [6]
عوامل متعدد [ ویرایش ]
در بعضی از شبکه ها مسیریابی با این واقعیت پیچیده است که هیچ نهاد واحد مسئول انتخاب مسیرها نیست. درعوض ، اشخاص متعدد در انتخاب مسیرها یا حتی قسمتهایی از یک مسیر واحد نقش دارند. اگر این نهادها مسیری را برای بهینه سازی اهداف خود انتخاب کنند ، ممکن است منجر به عوارض یا ناکارآمدی شود ، که ممکن است با اهداف سایر شرکت کنندگان مغایر باشد.
یک مثال کلاسیک شامل ترافیک در یک سیستم جاده ای است که در آن هر راننده مسیری را انتخاب می کند که زمان سفر خود را به حداقل می رساند. با چنین مسیریابی ، مسیرهای تعادل می تواند طولانی تر از بهینه برای همه رانندگان باشد. به ویژه ، پارادوکس Braess نشان می دهد که اضافه کردن یک جاده جدید می تواند زمان سفر را برای همه رانندگان طولانی کند.
به عنوان مثال در مدل دیگری که برای مسیریابی وسایل نقلیه هدایت خودکار (AGV) در ترمینال استفاده می شود ، برای هر وسیله نقلیه رزرو شده است تا از استفاده همزمان از همان قسمت از زیرساخت ها جلوگیری شود. این روش همچنین به عنوان مسیریابی آگاهی از متن گفته می شود. [7]
اینترنت به سیستمهای خودمختار (AS) مانند ارائه دهندگان خدمات اینترنتی (ISP) تقسیم می شود ، که هر کدام مسیرهای مربوط به شبکه خود را در چندین سطح کنترل می کنند. اول ، مسیرهای سطح AS از طریق پروتکل BGP انتخاب می شوند ، که توالی AS را تولید می کند که از طریق آن بسته ها جریان می یابند. هر AS ممکن است مسیرهای مختلفی داشته باشد ، که توسط AS همسایگان ارائه شده است ، که از آن می توانید انتخاب کنید. تصمیم آن اغلب شامل روابط تجاری با این AS های همسایه است ، [8]که ممکن است با کیفیت مسیر یا تأخیر ارتباط نداشته باشد. دوم ، هنگامی که یک مسیر سطح AS انتخاب شد ، غالباً چندین مسیر مربوط به سطح روتر وجود دارد ، در بخشی چون دو ISP ممکن است در چندین مکان متصل شوند. در انتخاب مسیر تک سطح روتر ، معمول است که هر ISP از مسیریابی سیب زمینی داغ استفاده کند : ارسال ترافیک در طول مسیر که مسافت را از طریق شبکه خود ISP به حداقل می رساند - حتی اگر آن مسیر مسافت کل را به مقصد برساند.
دو ISP ، A و B را در نظر بگیرید . هر کدام در نیویورک حضور دارند که با یک لینک سریع با تأخیر 5 میلی متر متصل می شوند و هر کدام در لندن با یک لینک 5 میلی متر متصل هستند. فرض کنید هر دو سرویس دهنده اینترنتی دارای پیوندهای اقیانوس اطلس هستند که دو شبکه خود را به هم متصل می کنند ، اما پیوند A دارای تأخیر 100 ms و B دارای تأخیر 120 ms است. هنگام مسیریابی پیام از یک منبع در شبکه لندن A به مقصدی در شبکه B نیویورک ، ممکن است A تصمیم بگیرد که بلافاصله پیام را در لندن به B ارسال کند . این موجب صرفه جویی در A می شود کار ارسال آن در امتداد یک لینک گرانقیمت اقیانوس اطلس ، اما باعث می شود که پیام هنگامی که مسیر دیگر 20 ms سریعتر باشد ، زمان تاخیر 125 میلی ثانیه را تجربه کند.
یک مطالعه اندازه گیری 2003 در مورد مسیرهای اینترنت نشان داد که ، بین جفت های ISP های همسایه ، بیش از 30٪ از مسیرها به دلیل مسیریابی سیب زمینی داغ دچار تأخیر می شوند ، 5٪ از مسیرها با حداقل 12 ms تأخیر دارند. تورم به دلیل انتخاب مسیر AS ، در حالی که قابل توجه است ، در درجه اول به عدم مکانیسم BGP نسبت به بهینه سازی مستقیم برای تأخیر ، نسبت به سیاست های مسیریابی خودخواه ، نسبت داده شد. همچنين پيشنهاد شده است كه اگر يك سازوكار مناسب وجود داشته باشد ، ISP ها به جاي استفاده از مسيرياب سيب زميني گرم ، مأموريت براي كاهش تأخير را دارند. [9]
چنین مکانیسمی بعدا توسط همان نویسندگان منتشر شد ، ابتدا برای پرونده دو ISP [10] و سپس برای پرونده جهانی. [11]
تجزیه و تحلیل مسیر [ ویرایش ]
با تبدیل شدن اینترنت و شبکه های IP به ابزارهای مهم تجارت ، ماموریت بیشتری پیدا می کند ، به تکنیک ها و روش هایی برای نظارت بر وضعیت مسیریابی شبکه ها علاقه بیشتری پیدا می کند. مسیریابی نادرست یا مسیریابی مسائلی باعث تخریب عملکرد نامطلوب ، ضربان و یا خرابی نمی شود. نظارت بر مسیریابی در یک شبکه با استفاده از ابزارها و تکنیک های تحلیل مسیر انجام می شود.
مسیریابی متمرکز [ ویرایش ]
در شبکه هایی که یک کنترل منطقی متمرکز بر روی حالت حمل و نقل در دسترس است ، برای مثال ، با استفاده از شبکه تعریف شده توسط نرم افزار ، می توان از تکنیک های مسیریابی استفاده کرد که هدف آنها بهینه سازی معیارهای عملکرد جهانی و شبکه است. این مورد توسط شرکتهای بزرگ اینترنتی استفاده شده است که بسیاری از مراکز داده را در مکانهای مختلف جغرافیایی متصل شده با استفاده از پیوندهای نوری خصوصی استفاده می کنند که نمونه آن شامل Global WAN مایکروسافت ، [12] Express Backbone ، [13] و Google B4 Google است. [14]معیارهای عملکرد جهانی برای بهینه سازی شامل حداکثر استفاده از شبکه ، به حداقل رساندن زمان تکمیل جریان ترافیک و به حداکثر رساندن ترافیک تحویل شده قبل از مهلت های خاص است. به ویژه ، به حداقل رساندن زمان تکمیل جریان از طریق WAN خصوصی ، مورد توجه زیادی از جامعه پژوهش قرار نگرفته است. با این حال ، با افزایش تعداد مشاغل که مراکز داده توزیع جهانی متصل به استفاده از شبکه های مرکز بین دیتای خصوصی ، به احتمال زیاد شاهد افزایش تلاش تحقیقاتی در این قلمرو هستند. [15] یک کار اخیر در مورد کاهش زمان اتمام جریان بیش از WAN خصوصی ، مسیریابی مدل سازی را به عنوان یک مشکل بهینه سازی نمودار با فشار دادن همه صف به نقاط انتهایی مورد بحث قرار می دهد. نویسندگان همچنین توصیه می کنند که ضمن فدا کردن عملکرد ناچیز ، مسئله را به طور موثر حل کنند.[16]
منبع
https://en.wikipedia.org/wiki/Routing#Path_selection
زمان در سال 1983 توسط Gallager و همکاران. ، 
تعداد رئوس های موجود در 
جایی که D شبکه یا قطر نمودار است. سرانجام پایین بودن پیچیدگی زمان راه حل نشان داده شده است 
شبکه ای در نظر گرفته می شود ، 
پیوندهای ارتباطی هستند پیوندها مانند مسئله کلاسیک وزن دارند.
، جایی که V تعداد گره ها باشد.
الگوریتم -approximation توسط Maleq Khan و Gopal Pandurangan ساخته شده است. 
زمان ، کجا 
قطر کوتاهترین مسیر محلی 
![[آیکون]](https://en.wikipedia.org/wiki/File:Wiki_letter_w_cropped.svg){kind=small}
(جایی که 
تعداد گره های موجود در شبکه) متشکل از احتمال گره برای مواجهه با هر یک از گره های دیگر شبکه است. هر یک از
، به این معنی که گره به همان اندازه احتمال دارد که هر گره بعدی را برآورده کند. وقتی گره با گره دیگری ملاقات کند ،
عنصر وکتور آن با 1 افزایش یافته است ، و سپس کل بردار 
، به هر بسته 
، که بر اساس بهینه سازی متریک استوار است. 
در اصل منفی میانگین تأخیر است. از این رو ، پروتکل بسته ای را تکرار می کند که منجر به بیشترین کاهش تأخیر می شود. RAPID مانند MaxProp مبتنی بر سیل است و بنابراین در صورت اجازه منابع شبکه سعی در تکثیر همه بسته ها خواهد کرد.
گره های مجزا که پس از ایجاد پیام با آن مواجه می شوید.
از نسخه های آن به اولین گره ای که با آن روبرو می شوید. سپس هرکدام از این گره ها نیمی از کل کپی های خود را به گره های آینده که در آن قرار دارند منتقل می کنند که هیچ نسخه ای از پیام ندارند. هنگامی که یک گره در نهایت تمام نسخه های خود را بجز یکی از آنها می دهد ، وارد مرحله انتظار می شود جایی که منتظر یک فرصت انتقال مستقیم با مقصد است. فایده Bary Spray و Wait این است که پیام ها سریعتر از نسخه وانیلی پخش می شوند. در حقیقت ، نویسندگان ثابت می كنند كه دودویی اسپری و انتظار از نظر حداقل تأخیر مورد انتظار در بین تمام طرح های اسپری و وایت ، بهینه هستند ، با فرض اینكه حركت گره 
رانندگان خواهند بود
. زمان لازم برای رانندگی مسیر Start-B-End با
. همانطور که 4000 راننده وجود دارد ، واقعیت این است
می تواند مورد استفاده قرار گیرد برای استنباط این واقعیت است
وقتی سیستم در تعادل است. بنابراین ، هر مسیر طول می کشد
دقایق. اگر هر مسیری زمان کمتری ببرد ، تعادل نش نخواهد بود: یک راننده منطقی از مسیر طولانی تر به مسیر کوتاه تر سوئیچ می کند.
دقیقه ، صرفه جویی تقریباً 25 دقیقه. به زودی تعداد بیشتری از 4000 راننده در این مسیر جدید تلاش می کنند. زمان لازم از 40.01 بالا می رود و صعود خود را ادامه می دهد. وقتی تعداد رانندگانی که مسیر جدید را امتحان می کنند به 2500 برسد ، با 1500 نفر همچنان در مسیر Start-B-End ، زمان آنها خواهد بود
دقیقه ، که هیچ پیشرفتی در مسیر اصلی ندارد. در همین حال ، آن 1500 راننده کم شده اند
دقیقه ، افزایش 20 دقیقه ای. آنها موظفند از طریق A نیز به مسیر جدید تغییر دهند ، بنابراین اکنون نیز طول می کشد
دقایق. هیچ کس مشکلی برای سفر A-End یا Start-B ندارد زیرا هر راننده ای که آنها را امتحان می کند 85 دقیقه طول می کشد. بنابراین ، باز شدن مسیر صلیب باعث تغییر غیرقابل برگشت برای آن توسط هر کس می شود و هزینه 80 دقیقه به جای 65 اصلی است. اگر هر راننده موافقت می کرد از مسیر AB استفاده نکند ، یا اگر این مسیر بسته بود ، هر راننده می شد. با کاهش 15 دقیقهای در زمان سفر سود ببرید.
فرمول زمان سفر هرکس است که در امتداد لبه سفر می کند 
مردم آن لبه را می گیرند فرض کنید نمودار ترافیکی وجود دارد
رانندگی در امتداد لبه
. اجازه دهید انرژی
، بودن
اجازه دهید 
) بگذارید کل انرژی نمودار ترافیک ، مجموع انرژی هر لبه در نمودار باشد.
در حالی که مسیر جدید است 
. اجازه دهید
حذف شده است. انرژی هر لبه
کاهش خواهد یافت 
و همینطور
. این فقط کل زمان سفر مورد نیاز برای طی کردن مسیر اصلی است. اگر مسیر جدید اضافه شود ،
برای برخی 
پس از آن در بدترین حالت ، ترافیک در تعادل به حداقل رساندن انرژی دو برابر اقتصادی مطلوب است. 
جریان ترافیکی بهینه اجتماعی و 
جریان ترافیک با کمترین انرژی است ، نابرابری حاکی از آن است
.