شبکه‌های کامپیوتری/مسیریابی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
added Category:شبکه‌های کامپیوتری با استفاده از رده‌ساز |
بدون خلاصۀ ویرایش |
||
خط ۱۰۶:
3. براساس اطلاعاتی که روتر از جداول مسیریابی همسایگان خود دریافت می کند، خود را به روز می کند.
بیایید یک نمونه دیگر (شکل زیر را نشان بدهیم) را در نظر بگیریم.<br />
سطر ۱۱۴ ⟵ ۱۱۲:
هزینه هر پیوند 1 تنظیم شده است. بنابراین، مسیری با کمترین هزینه، تنها مسیری است که هزینه آن کمترین باشد . جدول زیر نشان دهنده دانش هر گره از فاصله به تمام گره های دیگر است:<br />
<br />▼
{| border=1 cellpadding=5 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
! rowspan="2" | Information <br/> stored at node
سطر ۱۳۷ ⟵ ۱۳۳:
! G || <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 1 || <math>\infty</math> || 1 || 0
|}
در ابتدا، هر گره هزینه 1 را به گره هایی که مستقیما به آن متصل هستند و مقدار بی نهایت به تمامی گره های دیگر می دهد. در زیر جدول مسیریابی اولیه در گره A نشان داده شده است:<br />
<br />▼
{| border=1 cellpadding=5 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
سطر ۱۵۸ ⟵ ۱۵۲:
|}
در مرحله بعد، هر گره یک پیام را به گره های متصل ارسال می کند. این پیام حاوی لیستی از فاصله هر گره تا گره های دیگر است. به عنوان مثال، گره F به گره A می گوید که می تواند با هزینه 1 به گره G برسد. گره A همچنین می داند که با هزینه ی 1 می تواند به F برسد، بنابراین این هزینه را برای هزینۀ رسیدن به G با استفاده از F می افزاید. از آنجائیکه هزینه فعلی بی نهایت است و 2 کمتر، بنابراین گره A می گوید که می تواند از طریق F به G با هزینه 2 برسد. گره A از گره C می آموزد که گره B را می توان از گره C با هزینه ی 1 رد کرد، بنابراین نتیجه می شود که هزینه رسیدن به B از طریق گره C هزینه 2 در بردارد. از آنجا که این هزینه ، بهینه تر ازهزینه فعلی رسیدن به B که در حال حاضر1 است نمی باشد، اطلاعات جدید نادیده گرفته می شود. جدول نهایی نهایی در گره A در زیر نشان داده شده است:
{| border=1 cellpadding=5 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
سطر ۲۰۲ ⟵ ۱۹۶:
|}
ی
یکی از مشکلات با الگوریتم های بردار فاصله، "شمارش تا بی نهایت" نامیده می شود. بگذارید مشکل زیر را با یک مثال بررسی کنیم: ▼
▲
یک شبکه را با یک گراف در زیر نشان دهید. تنها یک اتصال بین D و سایر قسمت های شبکه وجود دارد. ▼
▲یک شبکه را با یک گراف در زیر نشان دهید. تنها یک اتصال بین D و سایر قسمت های شبکه وجود دارد.
[[Image:Dijkstra algorithm example 13.svg]]
سطر ۲۲۴ ⟵ ۲۱۹:
! D
| 3 || 2 || 1 || 0
|}
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
سطر ۲۴۶ ⟵ ۲۳۹:
| <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 0
|}
گره C گره B را به عنوان بهترین مسیر به گره D با هزینه 3 میشناسد، زمانی که گره C بردارهای خود را به گره B ارسال میکند، گره B می فهمد که انتخاب قبلی خود برای ارسال اطلاعات به گره D از طریق گره C هزینه بیشتری دربر دارد بنابراین گره B باید بردارهای خود را دوباره محاسبه کند.
▲<br />
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
|-
سطر ۲۶۶ ⟵ ۲۶۲:
با توجه به سطر گره B می توان نتیجه گرفت که مسیریابی به گره D می تواند از طریق گره A یاگره C با هزینه مساوی انجام شود بنابراین گره B بردار خودرا به روزرسانی و ارسال می کند. هر دو گره A وC بردار به روز شده گره B را دریافت می کنند و متوجه میشوند که مسیرترجیحی خود به گره D در حال حاضر دارای هزینه بالایی است، بنابراین بردارهای خود را مجددا محاسبه میکنند.
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
سطر ۲۸۷ ⟵ ۲۸۳:
سپس گره A و C بردارهای خود را ارسال می کنند وگره B باید بردار خود را با توجه به بردارهای دریافتی دوباره به روزرسانی کند، و سپس اطلاعات خودرا برای آنها می فرستند که در اینجا با یک حلقه مواجح میشویم.
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
سطر ۳۰۷ ⟵ ۳۰۳:
|}
توجه داشته باشید که همچین برداری در واقعیت به ندرت پیش می آید:
<math>d[x][D] = \infty
\quad for \quad x = A \quad or \quad x = B \quad or \quad x = C
</math>
این حلقه تا زمانی که تمام گره ها متوجه شوند وزن لینک به گره D بی نهایت است ادامه پیدا میکند. به این ترتیب، کارشناسان می گویند که الگوریتم های بردار فاصله یک نرخ همگرایی آهسته دارند. در نتیجه، الگوریتم بردار فاصله الگوریتم کاملی (در حلقه گیر میکند و جواب درستی نمی دهد) نیست. یکی از راه حل های این مشکل این است که روترها اطلاعات را فقط برای همسایگان ارسال کنند که لینک منحصر به فردی به مقصد نداشته باشند. به عنوان مثال، در این مورد، گره B نباید به گره C اطلاعات مربوط به گره D را ارسال کند، زیرا گره C تنها راه برای رسیدن به گره D است.
▲<br />
[[رده:شبکه‌های کامپیوتری]]
| |||