مسئله بی نهایت گرایی

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

برای مشاهده چگونگی  انتشارخبرهای  خوب، زیر شبکه پنج گره‌ای خطی شکل 6 رادر نظر بگیرید،که درآن تعداد جهش‌ها به عنوان مقیاس است فرض کنید A از همان  اول از کار افتاد و تمام مسیر یاب‌های دیگر این را می‌دانند به عبارت دیگر تمام آنها تاخیرهای رسیدن به A رت بخ صورت بی نهایت ضبط کرده اند

 وقتی A را به کار می‌افتد . سایر مسیر یاب‌ها از طریق مبادله بردار ، آگاه مس شوند برای سهولت فرض کنیم زنگ بزرگی وجود دارد که برای شروع همزمان مبادله بردار در تمام مسیر یاب‌ها به صدا در می‌آید در زمان مبادله نخست B می‌فهمد که همسایه چپ آن تا A آن را تاخیری ندارد صفراست سپس B در جدول مسیر یابی خود ثبت می‌کند که A تا همسایه چپ ، یک جهش فاصله دارد سایر مسیر یاب‌ها فکر می‌کنند  که A هنوز از کار افتاده است در این لحظه وارده هایی جدول مسیر یابی A در سطر  دوم شکل 6 برابر است الف لذا جدول مسیر یابی را بازسازی  می‌کند تا مسیری به طول 2 را نشان دهد اما D و E تاکنون خبرهای جدید را نشنیده اندن بدیهی است که خبرهای جدید با سرعت یک جهش درهر مبادله بخش می‌شود در زیرشبکه‌های که طولانی ترین مسیر که ان به طول N جهش است. در N مبادله هرکسی از خطوط از خطوط و مسیریاب هایی که تازه فعال شده‌اند باخبر می‌شود.

اکنون وضعیت شکل 6 (ب) را در نظر می‌گیریم در این شکل تمام خطوط و مسیریاب‌ها در آغاز فعال‌اند وفاصله  مسیر یاب‌های Aتا, E,D,C,B به ترتیب عبارتند از 1و2.3و4 ناگهان A  از کار می‌افتد یا خط بین A, B قطع می‌شود از دید B فرقی نمی‌کند که کدامیک اتفاق افتاده است.

در مبادله اولین بسته، B  چیزی از A نمی‌شنود خوشبختانه C می‌گوید نگران نباشید من مسیری به طول 2 به A دارم لذا B می‌داندکه مسیر C از طریق خود B می‌داند که C ممکن است ده خط خروجی داشته باشد .که هر کدام دارای مسیرهای مستقلی به A هستند که طول آنها 2 است در نتیجه B فکر می‌کند که می‌تواند از طریق C به A برسد با مسیرهای به طول 3 در مبادله اول E,D وارده‌های خود را برای A را بازسازی میکنند.

در مبادله دوم C در می‌یابدکه هریک از همسایه هایش ادعا میکنند که طول مسیر انها را به A برابر با 3 است یکی از آنها به طور تصادفی انتخاب می‌کندو فاصله جدید به A را برابر با 4 منظور می‌کند سطر سوم از شکل 6 الف مبادله‌های بعدی نتایج بقیه شکل 6 الف را تولید میکنند.

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

مسیر یابی حالت پیوند

مسیر یابی فاصله تا سال 1979 در ARPANET مورد استفاده قرار گرفت و از ان پس جای  خود را به مسیر یابی حالت پیوند داد. و مشکل عمده موجب مرگ آن شد. یکی از این که مقیاس تاخیر، طول صف بود و هنگام انتخاب مسیریاب‌ها پهنای باند را در نظر نمی‌گرفت در آغاز تمام خطها 56KBPS بودند لذا پهنای باند موضوع مهمی نبود اما وقتی بعضی از خطوط به 235KBPS وبعضی دیگر به MBPS 55/1 تغییر یافتند عدم توجه به پهنای باند را به عنوان مقیاس در نظر گرفت اما مشکل  دوم نیز وجود داشت، یعنی الگوریتم برای همگرا شدن به زمان زیادی نیاز دارد . بی نهایت گرایی به این دلایل الگوریتم دیگری به نام مسیریابی حالت پیوند جای ان را گرفت اکنون شکلهای گوناگونی از مسیر یابی حالت پیوند مورد استفاده قرار میگیرد.

ایده مسیر یابی حالت پیوند ساده است ودر پنج بخش بیان می‌شود هر مسیریابباید:

1-همسایه هایش را تشخیص داده و آدرس شکبه‌ها آنها را بداند.

2-تاخیر با هزینه تا همسایه هایش را اندازه گیری کند.

3- ایجاد بسته‌ای که اطلاعات به دست آمده از همسایه‌ها را نگهداری کند.

4-این بسته‌ها را به تمام مسیریاب‌ها ارسال نماید.

5-کوتاهترین مسیر به هر مسیر دیگر را محاسبه کند.

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

کسب اطلاعاتی راجع به همسایه‌ها

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

وقتی دو یا چند مسیریاببا شبکه‌های محلی را به هم متصل باشند. وضعیت کمی پیچیده تر است. شکل 7 الف شبکه محلی را با سه مسیریابA,C,F نشان می‌دهد که مستقیما به آن متصل‌اند هرکدام از این مسیریاب‌ها به یک یا چند مسیریاب دیگر متصل شده‌اند .

یک روش مدل سازی شبکه محلی این است که به عنوان یک گروه در نظر گرفته شود شکل( 7 ب )در اینجا گره جدید و مصنوعی  به نام N را معرفی می‌کردیم . که F,C,A به آن متصل ‌اند امکان  رفتن از A به C در شبکه محلی ، با مسیر ANC مشخص شده است.

اندازه گیری هزینه خط

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

 

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

هر دو روش بحث هایی را می‌طلبد معنای به حساب آوردن تاخیرهای مربوط به ترافیک ، این است که وقتی مسیریاب دو خط با پهنای باند مساوی را در پیش روا داشته باشد، به طوری که یکی از آنها  همواره تحت بار سنگین قراردارد و دیگری این این طور نباشد مسیر مربوط به خط فاقد بار را به عنوان مسیر کوتاهتر در نظر می‌گیرد. این روش کارایی بهتری دارد متاسفانه با در نظر گرفتن بار در محاسبات تاخیر مخالفت هایی صورت گرفت زیر شبکه شکل 8 را در نظر بگیرید که به دو بخش شرقی و غربی تقسیم  شده است و توسط دو خط CF-, EI به هم متصل  شده‌اند فرض کنید بیشترین ترافیک بین شرق  غرب از خط ترافیک شرقی – غربی از طریق EI منتقل می‌شودو بار ان افزون می‌گردد. در نتیجه در بازسازی بعدی، CF کوتاهترین مسیر خواهد بود. لذا امکان دارد جدول‌های مسیر یابی شدیدا تغییر می‌کنندو منجر به مسیر یابی غیر عادی و بسیاری از مشکلات  دیگر شوند. اگر از بار صرف نظر شودو فقط پنهای باند منظور گردد، این مشکل نمی‌آید از طرف دیگر بار می‌تواند در هر دو خط پخش شود. اما این راه حل ، بهترین مسیر را مورد استفاده قرار نمی‌دهد با این وجود برای اجتناب از برخورد در انتخاب بهترین  مسیر، معقول است که بار در چندین خط توزیع شود.

ساخت  بسته‌های حالت پیوند

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

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

توزیع بسته‌های حالت پیوند.

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

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

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

سوم اینکه  اگر شماره ترتیب خراب شود و 540،65 به جای 4(خطای یک بیتی ) دریافت شود ، بسته‌های 5 تا 540،65 به علت کهنگی رد می‌شوند زیرا فرض می‌شود که شماره ترتیب باید 540،65 باشد.

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

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

ساختمان داده‌ای که مسیریابB برای زیر شبکه شکل 13-5 الف استفاده می‌کند در شکل 10 آمده است هر سطر ، متناظر با بسته حالت پیوندی است که از راهع رسید و هنوز به طور کامل پردازش نشده است. جایی که بسته از انجا ارسال شد و شماره ترتیب وسن ، داده‌های ان درجدول ذخیره می‌شود به علاوه نشانگرهای ارسالی و اعلام وصول برای هر سه خط B وجود دارند به ترتیب به  F,C,A معنای نشانگرهای ارسالی این است که بسته باید به خط تعیین شده ارسال گرددو معنای نشانگرهای اعلام وصول این است که باید در آنجااعلام وصول شوند.

در شکل 10 بسته حالت پیوند مستقیما از A رسیده است. لذا همانطور که با بیت‌های نشانگر نشان داده شده است باید به  C, F ارسال شود. و به A اعلام  وصول گردد. به طور مشابه بسته‌ای از F باید به A و C ارسال شود و به F اعلام وصول گردد.

اما، وضعیت در بسته سوم  که از E می‌آید. این بسته دوباره می‌آید یک بار از طریق EAB و یک بار از طریق EFB در نتیجه فقط باید به C ارسال گردد، اما باید به A و F اعلام  وصول شود (همانطور که با بیت‌ها مشخص شده است.)

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

محاسبه مسیرهای جدید

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

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