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

الگوریتم های مسیریابی روترها از الگوريتمهاي مسيريابي،براي يافتن بهترين مسير تا مقصد استفاده مينمايند هنگامي كه ما در مورد بهترين مسير صحبت ميكنيم،پارامترهايي همانند تعداد hopها (مسيري كه يك بسته از يك روتر ديگر در شبكه منتقل ميشود).زمان تغيير و هزينه ارتباطي ارسال بسته را در نظر ميگيريم. مبتني بر اينكه روترها چگونه اطلاعاتي در مورد ساختار يك شبكه جمع آوري مينمايند و نيز تحليل آنها از اطلاعات براي تعيين بهترين مسير،ما دو الگوريتم مسير يابي اصلي را در اختيار داريم:الگوريتم مسير يابي عمومي و الگوريتمهاي مسير يابي غير متمركز. در الگوريتم هاي مسير يابي غير متمركز،هر روتر اطلاعاتي در مورد روترهايي كه مستقيما به آنها متصل ميباشند در اختيار دارد. در اين روش هر روتر در مورد همه روتر هاي موجود در شبكه،اطلاعات در اختيار ندارد.اين الگوريتمها تحت نام الگوريتمهاي (DV (distance vectorمعروف هستند.در الگوريتمهاي مسيريابي عمومي،هر روتر اطلاعات كاملي در مورد همه روترهاي ديگر شبكه و نيز وضعيت ترافيك شبكه در اختيار دارد.اين الگوريتمها تحت نام الگوريتمهاي(LS(Link state معروف هستند.ما در ادامه مقاله به بررسي الگوريتمهاي LS ميپردازيم. 1-6- روش‌های مسیریابی در شبکه‌های حسگر در مسیریابی در شبکه‌های ادهاک نوع حسگر سخت‌افزار محدودیت‌هایی را بر شبکه اعمال می‌کند که باید در انتخاب روش مسیریابی مد نظر قرار بگیرند ازجمله اینکه منبع تغذیه در گره‌ها محدود می‌باشد و در عمل، امکان تعویض یا شارژ مجدد آن مقدور نیست؛ لذا روش مسیریابی پیشنهادی در این شبکه‌ها بایستی از انرژی موجود به بهترین نحو ممکن استفاده کند یعنی باید مطلع از منابع گره باشد و اگر گره منابع کافی نداشت بسته را به آن برای ارسل به مقصد نفرستد. *روش سیل آسا در این روش یک گره جهت پراکندن قسمتی از داده‌ها در طول شبکه، یک نسخه از داده مورد نظر را به هر یک از همسایگان خود ارسال می‌کند. هر وقت یک گره، داده جدیدی دریافت کرد، از آن نسخه برداری می‌کند و داده را به همسایه‌هایش (به جز گرهی که داده را از آن دریافت کرده‌است) ارسال می‌کند. الگوریتم زمانی همگرا می‌شود یا پایان می‌یابد که تمامی گره‌ها یک نسخه از داده را دریافت کنند. زمانی که طول می‌کشد تا دسته‌ای از گره‌ها مقداری از داده‌ها را دریافت و سپس ارسال کنند، یک دور نامیده می‌شود. الگوریتم سیل آسا در زمان O(d) دور، همگرا می‌شود که d قطر شبکه‌است چون برای یک قطعه داده d دور طول می‌کشد تا از یک انتهای شبکه به انتهای دیگر حرکت کند. سه مورد از نقاط ضعف روش ارسال ساده جهت استفاده از آن در شبکه‌های حسگر در زیر آورده شده‌است :

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

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

1. ADV: برای تبلیغ داده‌های جدید استفاده می‌شود. وقتی یک گره SPIN، داده‌هایی برای به اشتراک گذاشتن در اختیار دارد، این امر را می‌تواند با ارسال شبه داده مربوطه تبلیغ کند.
2. REQ: جهت درخواست اطلاعات استفاده می‌شود. یک گره SPIN می‌تواند هنگامی که می‌خواهد داده حقیقی را دریافت کند از این پیغام استفاده کند.
3. DATA: شامل پیغام‌های داده‌ای است. پیغام‌های DATA محتوی داده حقیقی جمع آوری شده توسط حسگرها هستند.

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

1. در وقوع حوادث ناگوار همچود زمین لرزه , سیل و … که امکان آسیب دیدگی station های ثابت وجود دارد (در شبکه با ساختار ثابت در صورت آسیب دیدن station اصلی ممکن است کل شبکه از کار بیافتد).
2. عملیات جستجو و نجات
3. و موارد نظامی
4. پروتوکل های مسیر یابی (Routing Protocols) : همان طور که پیش از این نیز اشاره شد در شبکه های Mobile Ad hoc عمل مسیر یابی به دلایلی همچون متحرک بودن و نبود سیستم کنترلی متمرکز از اهمیت بالایی بر خوردار بوده و مطالعه و بررسی بیشتری را می طلبد . قبل از بررسی این پروتوکل ها باید توجه کنیم که هدف از الگوریتم ها و استراتژی های مسیریابی جدید کاهش سربار ناشی از مسیریابی در کل شبکه , یافتن مسیرهای کوتاه تر و انتقال صحیح داده ها و اطلاعات می باشد.

* الگوریتم بردار فاصله در این الگوریتم از الگوریتم bellman – ford استفاده می‌شود و می‌توان یک رقم و هزینه را برای هر لینک بین گروه‌های شبکه تعیین نمود. گره‌ها می‌توانند اطلاعات را از A به B بفرستند. و این از طریق مسیر کم هزینه عملی است. این الگوریتم خیلی ساده عمل می‌کند. ابتدا باید راه اندازی انجام شود. بخش‌های همجوار نیز باید شناخته شوند. هر گره به طور منظم می‌تواند هزینه کل را به مقصد بفرستد. گره‌های همجوار به بررسی اطلاعات و مقایسه یافته‌ها می‌پردازند. این عامل پیشرفت در جداول مسیریابی خواهد بود. تمام گره‌ها بهترین حلقه را کشف می‌کنند. وقتی یکی از گره‌ها کاهش یافت آنهایی که در همجوار هستند می‌توانند ورودی را خالی کنند و به مقصد بروند. به این طریق اطلاعات جدول ارائه خواهند شد. آنها می‌توانند اطلاعات را در اختیار گره‌های مجاور قرار دهند. در نهایت اطلاعات ارتقا یافته دریافت می‌شوند و مسیر جدید شناخته خواهد شد. * الگوریتم حالت لینک وقتی از این الگوریتم استفاده می‌شود هر گره از داده‌های اصلی در الگوی شبکه‌ای استفاده خواهد نمود. در این شرایط تمام گره‌ها وارد شبکه می‌شوند و اطلاعات با یکدیگر در ارتباط خواهند بود. این گره‌ها می‌توانند اطلاعات را وارد نقشه کنند. به این طریق هر مسیریاب تعیین کننده مسیر کم هزینه به سمت دیگر گره‌ها خواهد بود. در نهایت یک الگوریتم با کوتاهترین مسیر به وجود می‌آید. این درخت می‌تواند ماحصل ترکیب این گره‌ها باشد. در این شرایط بهتر است این درخت در طراحی جدول استفاده شود و حلقه بعدی گره نیز مشخص گردد. 2-6- مقایسه الگوریتم مسیریابی پروتکلهای مسیریابی بردار-فاصله در شبکه‌های کوچک، ساده و کارآمد بوده و به مدیریت اندکی نیازمند هستند. با این وجود آلگوریتمهای اولیه بردار-فاصله از نظر مقیاس پذیری خوب نیستند و قابلیتهای همگرایی آنها ضعیف است که این امر منجر به توسعه الگوریتمهای پیچیده تر با مقیاس پذیری بهتر جهت شبکه‌های بزرگ شده‌است. بدین جهت اغلب پروتکلهای مسیریابی درونی از پروتکل‌های وضعیت لینک مانند OSPF و IS-IS استفاده می‌کنند. یکی از توسعه‌های اخیر در پروتکل‌های بردار فاصله، قابلیت بدون حلقه یا loop-free می‌باشد که بطور مثال در EIGRP پیاده سازی شده‌است. این پروتکل ضمن داشتن تمام قابلیتهای پروتکلهای بردار فاصله، مشکل count-to-infinity را حل کرده و از این جهت زمان همگرایی پروتکل را بهبود بخشیده‌است. 3-6- انتخاب مسیر یک اصل مسیریابی توسط آلگوریتم مسیریابی معرفی شده‌است که تعیین کننده عملکرد آنها است. این اصول می‌توانند مربوط به پهنای باند، تاخیر، تعداد حلقه‌ها، هزینه مسیر بار و MTU، اعتبار پذیری و هزینه ارتباطی باشند. این جداول عامل ذخیره بهترین مسیرها هستند ولی پایگاه‌های حالت لینک و توپولوژیکی نیز نقش ذخیره دارند. وقتی اصل مسیر یابی در یک پروتکل خاص استفاده شود مسیریاب‌های چند پروتکلی از یک روش اکتشافی خارجی استفاده می‌کنند و به این ترتیب مسیرهای آموخته شده را انتخاب خواهند کرد. به عنوان مثال مسیریاب Cisco یک ارزش به صورت فاصله اجرایی دارد. در این فاصله مسیرها می‌توانند پروتکل معتبر تولید کنند.   4-6- عوامل چندگانه در بعضی از شبکه‌ها، مسیریابی تحت اثر این واقعیت است که هیچ عامل واحدی علت انتخاب مسیر نمی‌باشد. این عوامل در انتخاب مسیر و بخش‌هایی از آن کاربرد دارند. پیچیدگی و یا عدم وجود راندمان کافی می‌تواند یک عامل مهم در بهینه سازی اهداف باشد. در این شرایط یک تناقض با اهداف دیگر شرکت کننده‌ها به وجود می‌آید. یک مثال از این شامل ترافیک در سیستم جاده‌ای است. در این حالت هر راننده به دنبال یک مسیر است که زمان کمتری داشته باشد. با این وجود مسیر تعادلی می‌تواند برای تمام آنها مطلوب باشد. تناقض braess نشان می‌دهد که افزایش جاده جدید می‌توان زمان سفر را طولانی کند. اینترنت به سیستم ناشناخته مانند Isp تقسیم می‌شود که هر یک دارای کنترل مسیر شبکه هستند. مسیرهای سطح AS می‌توانند از طریق پروتکل BGP انتخاب شوند. این عامل تولید یک توالی AS ازطریق بسته‌های جریان یافته‌است. هر AS دارای چند مسیر است که در خدمت ASهای مجاور قرار گرفته‌است. تصمیم گیری در این زمینه شامل ارتباط تجاری با این بخش‌های همجوار است. البته این ارتباط با کیفیت مسیر کمتر است. دوم آنکه وقتی مسیر سطح AS انتخاب شد چند مسیر سطح ردیاب به وجود می‌آید و دو IS می‌توانند در چند محل به هم متصل باشند. در انتخاب این مسیر واحد باید هر ISP ازمسیریابی داغ استفاده کند که شامل ارسال ترافیک در مسیر و کاهش فاصله از طریق شبکه ISP است حتی اگر آن مسیر فاصله کل مقصد را افزایش دهد. دو تا ISP به نام B،A را در نظر بگیرید. هر یک در نیویورک با یک لینک سریع در ارتباط هستند و فضای پنهان ۵ms دارند. آنها در لندن با لینک ۵ms مرتبط می‌شوند. فرض کنید که آنها لینک خارج از قاره دارند و لینک A دارای ms ۱۰۰ و لینک B دارای ms ۱۲۰ حافظه‌است. وقتی مسیریابی از یک منبع در شبکه A صورت گیرد پیام به B درلندن خواهد رفت. این عامل ذخیره A در لینک فرا قاره‌ای است ولی پیام وارد لینک ms ۱۲۵ خواهد شد که تا ms ۲۰ سریع تر است. مطالعه سال ۲۰۰۳ نشان داد که بین جفت‌های IPS همجوار، بیش از ۳۰% مسیر دارای حافظه پنهان است و ۵% آن حداقل ms ۱۲ تاخیر دارد. این مشکل ناشی از انتخاب مسیر سطح AS می‌باشد ولی می‌تواند به عدم وجود مکانیزم بهینه سازی BGP اشاره کند. گفته می‌شود که در یک مکانیزم مناسب ISP می‌تواند در مشارکت قرار گیرد و حافظه پنهان را کاهش دهد. 5-6- سایر الگوریتم های مسیریابی *الگوريتمهاي LS در الگوريتمهاي LS ،هر روتر ميبايست مراحل ذيل را به انجام رساند: روترهاي را كه به لحاظ فيزيكي به آنها متصل ميباشد را شناسايي نموده و هنگامي كه شروع به كار ميكند آدرسهايIP آنها بدست آورد. اين روتر ابتدا يك بسته HELLO را روي شبكه ارسال ميكند. هر روتري كه اين بسته را دريافت ميكند از طريق يك پيام كه داراي آدرس IP خود اين روتر ميباشد به پيام HELLO پاسخ ميدهد. زمان تاخير مربوط به روترهاي مجاور را اندازه گيري نمايد(يا هر پارامتر مهم ديگري از شبكه همانند ترافيك متوسط) براي انجام اين كار ،روترها بسته هاي echo را روي شبكه ارسال ميكنند. هر روتري كه اين بسته ها را دريافت ميكند با يك بسته echo reply به آن پاسخ ميدهد.با تقسيم زمان مسير رفت و برگشت به دو،روترها ميتوانند زمان تاخير را محاسبه كنند.(زمان مسير رفت و برگشت،سنجشي از تاخير فعلي روي يك شبكه ميباشد)توجه داشته باشيد كه اين زمان شامل زمانهاي ارسال و پردازش ميباشد. اطلاعات خود را در مورد شبكه،براي استفاده ساير روترها منتشر نموده و اطلاعات روترهاي ديگر را دريافت كند. در اين مرحله همه روترها دانش خود را با روتر هاي ديگر به اشتراك گذاشته و اطلاعات مربوط به شبكه را با يكديگر مبادله ميكنند.با اين روش هر روتر ميتواند در مورد ساختار و وضعيت شبكه اطلاعات كافي بدست آورد. با استفاده از اين الگوريتم مناسب،بهترين مسير بين هر دو گره از شبكه راشناسايي كند. در اين مرحله،روترها بهترين مسير تا هر گره را انتخاب ميكنند.آنها اين كار را با استفاده از يك الگوريتم همانند الگوريتم كوتاهترين مسير Dijkstra انجام ميدهند.در اين الگوريتم،يك روتر مبتني بر اطلاعاتي كه از ساير روترها جمع آوري نموده است،گرافي از شبكه را ايجاد مينمايد.اين گراف مكان روترهاي موجود در شبكه و نقاط پيوند آنها را به يكديگر نشان ميدهد.هر پيوند با يك شماره به نام Costياweight مشخص ميشود.اين شماره تابعي از زمان تاخير،متوسط ترافيك و گاهي اوقات تعداد hopهاي بين گره ها ميباشد.براي مثال اگر دو پيوند بين يك گره و مقصد وجود داشته باشد،روتر پيوندي با كمترين Weight را انتخاب ميكند. الگوريتم Dijkstra داراي مراحل ذيل ميباشد: روتر گرافي از شبكه را ايجاد نموده و گره هاي منبع و مقصد(براي مثال V1 وV2)را شناسايي ميكند.سپس يك ماتريس به نام ماتريس adjacency را ميسازد.در اين ماتريس يك مختصه مبين Weight ميباشد.براي مثال[i,j]،وزن يك پيوند بين Viو Vj ميباشد.در صورتي كه هيچ پيوند مستقيمي بين Vi وVj وجود نداشته باشد اين وزن (ويت) بصورت infinity در نظر گرفته ميشود. روتر يك مجموعه ركورد وضعيت را براي هر گره روي شبكه ايجاد مينمايد اين ركورد داراي سه فيلد ميباشد: فيلد Predecessor:اولين فيلدي كه گره قبلي را نشان ميدهد. فيلد Length:فيلد دوم كه جمع وزنهاي از منبع تا آن گره را نشان ميدهد. فيلد Label:آخرين فيلد كه وضعيت گره را نشان ميدهد.هر گره ميتواند داراي يك مود وضعيت باشد:tentative يا permanent روتر،پارامترهاي مجموعه ركورد وضعيت براي همه گره ها را آماده سازي اوليه نموده و طول آنها را در حالت infinity و Labelآن را در وضعيت tentative قرار ميدهد. روتر،يك گره T را ايجاد ميكند.براي مثال اگر V1 ميبايست گره T منبع باشد،روتر برچسب V1را در وضعيت permanent قرار ميدهد.هنگامي كه يك Label به حالت permanent تغيير ميكند ديگر هرگز تغيير نخواهد كرد. يك گره T در واقع يك agent ميباشد. روتر،مجموع ركورد وضعيت مربوط به همه گره هاي Tentative را كه مستقيما به گره T منبع متصل هستند،روز آمد مينمايد. روتر همه گره هاي Tentative را بررسي نموده و گرهاي را كه وزن آن تا V1 كمترين مقدار را دارد انتخاب ميكند.سپس اين گره،گره Tمقصد خواهد بود اگر اين گره،V2 نباشد(گره مقصد)روتر به مرحله 5باز ميگردد. اگر اين گره V2 باشد،روتر گره قبلي آن را از مجموع ركورد وضعيت استخراج نموده و اين كار را انجام ميدهد تا به V1 برسد،اين فرست از گره ها،بهترين مسير از V1تاV2را نشان ميدهد.   *الگوريتمهاي DV الگوريتمهاي DVبا نامهاي الگوريتمهاي مسيريابي Bellman-Ford و ford-fulkerson نيز ياد ميشوند.در اين الگوريتمها،هر روتر داراي يك جدول مسيريابي ميباشد كه بهترين مسير تا هر مقصد را نشان ميدهد. همانطور كه در جدول مشاهده ميكنيد،اگر روتر G بخواهد بسته هايي را به روتر D ارسال كند،ميبايست آنها را به روتر H ارسال نمايد.هنگامي كه بسته ها به روتر H رسيدند،اين روتر جدول خود را بررسي نموده و روي چگونگي ارسال بسته ها به D تصميم گيري مي كند

Destination	Weight	Line
A	8	A
B	20	A
C	28	I
D	20	H
E	17	I
F	30	I
G	18	H
H	12	H
I	10	I
J	0	–
K	6	K
L	15	K

جدول 1-6-الگوریتم مسیریابی DV در الگوريتمهاي DV،هر روتر ميبايست مراحل ذيل را انجام دهد: وزن لينكهاي مستقيما متصل به آن را اندازه گرفته و اين اطلاعات را در جدول خود ذخيره كند. در يك دوره زماني خواص،روتر جدول خود را به روترهاي مجاور ارسال نموده و جدول مسيريابي هر يك از روترهاي مجاور خود را دريافت ميكند. مبتني بر اطلاعات بدست آمده از جداول مسيريابي روترهاي مجاور،جدول خود را روز آمدسازي مينمايد. يكي از مهمترين مشكلات،هنگام كار با الگوريتمهاي DV،مشكل ‍Count to infinity اجازه بدهيد اين مشكل را با ذكر يك مثال روشن كنيم. همانطور كه در قسمت ذيل نشان داده شده است يك شبكه را در ذهن خود تصور كنيد.همانطور كه در اين جدول ميبينيد،فقط يك پيوند بين A و ساير بخشهاي شبكه وجود دارد.در اينجا شما ميتوانيد،اين گراف و جدول مسيريابي همه گره ها را مشاهده كنيد:

	A	B	C	D
A	0,-	1,A	2,B	3,D
B	1,B	0,-	2,C	3,D
C	2,B	1,C	0,-	1,C
D	3,B	2,C	1,D	0,-

جدول 2-6- جدول مسیریابی گره های گراف اكنون تصور كنيد كه پيوند بين A و B قطع شود.در اين هنگام، B جدول خود را تصحيح ميكند بعد از يك مدت زمان خاص،روترها جداول خود را مبادله نموده و بنابراين B جدول مسيريابي C را دريافت ميكند. از آنجايي كه C نميداند چه اتفاقي براي پيوند بين A و B رخ داده است اين اطلاعات را حفظ ميكند.B اين جدول را دريافت نموده و فكر ميكند كه يك پيوند جداگانه بين Cو A وجود دارد،بنابراين جدول خود را تصحيح نموده مقدار infinity را به 3 تغيير ميدهد.به همين شكل دوباره روترها جداول خود را مبادله ميكنند.هنگامي كه C،جدول مسيريابي B را دريافت ميكند،مشاهده ميكنيد كه B وزن پيوند خود تا A را از 1به 3 تغيير داده است،بنابراين C ،جدول خود را روزآمد نموده و وزن پيوند خود تا Aرا به 4 تغيير ميدهد.اين پروسه تكرار ميشود تا همه گره ها وزن پيوند خود را تا A در وضعيت infinity قرار دهند.اين وضعيت در جدول زير نشان داده شده است.

	B	C	D
Sum of weight to A after link cut	∞,A	2,B	3,C
Sum of weight to B after 1st updating	3,C	2,B	3,C
Sum of weight to A after 2nd updating	3,C	4,B	3,C
Sum of weight to A after 3rd updating	5,C	4,B	5,C
Sum of weight to A after 4th updating	5,C	6,B	5,C
Sum of weight to A after 5th updating	7,C	6,B	7,C

جدول 3-6- مسیرهای گره های گراف با استفاده از الگوریتم DV در اين روش متخصصين ميگويند،الگوريتمهاي DV داراي يك سرعت همگرايي پايين هستند.يك روش براي حل اين مشكل در مورد روترها،ارسال اطلاعات فقط به روترهايي ميباشد كه داراي پيوند انحصاري تا مقصد نيستند.براي مثال در اين مورد،C نميبايست هيچ اطلاعاتي را به گره B در مورد A ارسال كند زيرا B فقط يك مسير تا A را در اختيار دارد. 6-6- مسيريابي سلسله مراتبي همانطور كه شما ميبينيد،در هر دو الگوريتم LS و DV،هر روتر مجبور به ذخيره نمودن اطلاعات مربوط به روترهاي ديگر ميباشد.هنگامي كه اندازه شبكه رشد ميكند،تعداد روترهاي شبكه افزايش مي يابد در نتيجه اندازه جداول مسيريابي نيز افزايش مي يابد و روترها نميوانند ترافيك شبكه را به طور موثر كنترل كنند.ما از مسيريابي سلسله مراتبي براي برطرف كردن اين مشكل استفاده ميكنيم.اجازه بدهيد اين موضوع با ذكر يك مثال روشن كنيم: ما از الگوريتمهاي DV براي يافتن بهترين مسير بين گره ها استفاده ميكنيم در وضعيت نشان داده شده در ذيل،هر گره از شبكه مجبور به نگهداري يك جدول مسيريابي با 17 ركورد ميباشد.در اينجا يك گراف معمولي و جدول مسيريابي مربوط به A ارائه شده است.

Destination	Line	Weight
A	–	–
B	B	1
C	C	1
D	B	2
E	B	3
F	B	3
G	B	4
H	B	5
I	C	5
J	C	6
K	C	5
L	C	4
M	C	4
N	C	3
O	C	4
P	C	2
Q	C	3

جدول 4-6- جدول مسیریابی با 17 رکورد در مسيريابي سلسله مراتبي،روترها در گروههايي به نام regions طبقه بندي ميشوند.هر روتر داراي اطلاعاتي فقط در مورد روترهايي كه در region آنها قرار دارد در اختيار داشته و هيچ گونه اطلاعاتي در مورد region هاي ديگر ندارند. در اين مثال ما شبكه خود را به پنج region تقسيم ميكنيم.اگر A بخواهد بسته ها را به هر روتر در region2 ارسال كند،آنها را به B ارسال ميكند و الي آخر.

Destination	Line	Weight
A	–	–
B	B	1
C	C	1
Region 2	B	2
Region 3	C	2
Region 4	C	3
Region 5	C	4

در اين نوع مسيريابي،جداول را ميتوان خلاصه نمود بنابراين راندمان شبكه بهبود مييابد.مثال بالا مسيريابي سلسله مراتبي دو سطحي را نشان ميدهد همچنين ميتوان از مسيريابي سلسله مراتبي 3 سطحي و 4 سطحي استفاده كرد.در مسيريابي سلسله مراتبي 3سطحي،شبكه به تعدادي كلاستر تقسيم بندي ميشود.هر كلاستر متشكل از تعدادي region و هر region داراي تعدادي روتر ميباشد.مسيريابي سلسله مراتبي به طور وسيعي در مسيريابي اينترنت مورد استفاده قرار ميگيرد و استفاده از چندين پروتكل مسيريابي را ممكن مي سازد. شکل 1-6- پدیده چند مسیری   7-6- پدیده چند مسیری شکل 1-6 مسیری را نشان میدهد . در این پدیده مسیر و زمان بندی سیگنال در اثر بر خورد با موانع و انعکاس تغییر می کند . پیاده سازی های اولیه از استاندارد b802.11 از تکنیک FHSS در لایه فیزیکی استفاده می کردند . از ویژگی های قابل توجه این تکنیک مقاومت قابل توجه آندر برابر پدیده چند مسیری است . در این تکنیک از کانال های متعددی (79 کانال )با پهنای باند نسبتا کوچک استفاده شده و فرستنده و گیرنده به تناوب کانال فرکانسی خود را تغییر می دهند . این کانال هر 400 میلی ثانیه بروز می کند لذا مشکل چند مسیری به شکل قابل ملاحظه ای منتفی می شود. زیرا گیرنده سیگنال اصلی (که سریع تر از سایرین رسیده و عاری از تداخل است ) را دریافت کرده و کانال فرکانسی خود را عوض می کند و سیگنال های انعکاسی زمانی به گیرنده می رسد که کانال فرکانسی قبلی خود را عوض کرده و در نتیجه توسط گیرنده احساس و در یافت نمی شود .