مسیریابی سلسله مراتبی

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

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

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

شکل 11 یک مثال کمی از مسیریابی در سلسله  مراتب دو سطحی با پنج ناحیه را نشان می‌دهد. جدول مسیریابی کامل مربوط به مسیریاب1A دارای 17 وارده است(َ(شکل 11)(ب) وقتی مسیریابی‌های محلی،وارده‌های ،وجود دارد،اما ناحیه‌های دیگر در یک مسیر باب جمع شده‌اند لذا کل ترافیک ناحیه 2 از طریق خط 1B-2A منتقل می‌شود اما بقیه ترافیک از راه دور ،از طریق خط 1C-3B   منتقل خواهد شد مسیر یابی‌ها در هر ناحیه،صرفه جویی در فضای جدول بیشتر می‌شود.

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

 

وقتی شبکه منفردی بسیار بزرگ می‌شود این سوال مطرح است: سلسله مراتب چند سطح باید داشته باشد؟ بعنوان مثال زیر شبکه‌ای با 720 مسیریاب را در نظر بگیرید. اگر سلسله مراتبی وجود نداشته باشد، هر مسیریاب به 72 وارده جدول نیاز دارد اگر زیر شبکه به 24 ناحیه 30 مسیریابی تقسیم شود هر مسیریاب نیازمند 30 وارده محلی و 23 وارده راه دور است که مجموع آن 53 وارده است. اگر سلسله مراتب سه سطحی انتخاب شود، با هشت دسته که هر کدام حاوی 9 ناحیه از مسیریاب‌ها باشند هر مسیریاب برای مسیریابی محلی به 10 وارده نیاز دارد و برای مسیریابی به سایر نواحی در دسته خود به 8 وارده نیاز دارد و برای خوشه‌های راه دور به 7 وراده نیاز دارد که در مجموع برابر با 25 است. کامون و کلینراک (1979) کشف کردند که بهترین تعداد سطوح در زیر شبکه‌ای با N ln است که به ازا هر مسیریاب به N  ln وارده نیاز دارد. آنها همچنین نشان دادند که افزایش میانگین طول مسیر در اثر مسیریابی سلسله مراتبی اندک است و اغلب قابل قبول خواهد بود.

مسیریابی پخشی

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

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

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

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

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

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

نمونه‌ای از الگوریتم پیشروی مسیر معکوس در شکل 12 آمده است. قسمت (الف) زیرشبکه را نشان میدهد، قسمت (ب) درخت بایگانی مربوط به مسیریاب I آن زیر شبکه را نشان می‌دهد و قسمت (ج) چگونگی عملکرد الگوریتم مسیر معکوس را نشان می‌هد در جهش اول U بسته هایی را به N , H , H , F می‌فرستد (که در سطر دوم درخت نشان داده شده است). هر کدام از این بسته‌ها از مسیر بهینه به I دریافت می‌شونهد (با فرض اینکه مسیر بهینه در درخت بایگانی باشد) و دور حرف آن دایره‌ای کشیده شده است. در جهش دوم هشت بسته تولید می‌شوند؛ هر مسیریابی که در جهش اول بسته‌ای را دریافت کرد، دو بسته تولید می‌کند. ضمن تولید تمام این هشت بسته به مسیریاب‌های ملاقات نشده قبلی می‌رسند که پنج بسته از آنها در امتداد خط بهینه به مقصد می‌رسد. از شش بسته‌ای که در جهتش سوم تولید می‌شود فقط سه تا از مسیر بهینه می‌رسند (در K , E , C) و بقیه تکراری‌اند. پس از پنج جهش و 24 بسته، پخش خاتمه می‌یابد در حالی که اگر درخت بایگانی دنبال می‌شد چهار جهش و 14 بسته لازم بود.

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