ویکی‌کتاب

شبکه‌های کامپیوتری/مسیریابی: تفاوت میان نسخه‌ها

نمایش تاریخچه به صورت تعاملی
→ تفاوت با ویرایش قدیمی‌ترتفاوت با ویرایش جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
بدون خلاصۀ ویرایش
بدون خلاصۀ ویرایش
خط ۴۴:
 
 
الگوریتم فاصله راس ها از متریک به عنوان هزینه مسیر برای مشخص کردن بهترین مسیر (مسیری با کمترین هزینه) به مقصد استفاده می کند. زمانی که روتر از الگوریتم فاصله راس ها استفاده میکند ، هزینه ها توسط هر روتر جمع آوری میشودمی شود. این هزینه ها میتواند به صورت واحدهای دلخواهقرار دادی باشند و یا به صورت پویا و در حال تغییر جمع آوری شود مانند مقدار تاخیر در ارسال اطلاعات از طریق یک مسیر به یک روتر دیگر. تمام هزینه ها در جدول مسیریابی روتر قرار می گیرند و سپس توسط الگوریتم مسیریابی جستجو شده تا بهترین مسیر برای هر نوع استفاده از شبکه را محاسبه باشدکنند.<br />##
 
تمام هزینه ها در جدول مسیریابی روتر قرار می گیرند و سپس توسط الگوریتم استفاده  می شود تا بهترین مسیر برای هر نوع شبکه ای را محاسبه کنند. اگر چه منابع زیادی وجود دارد که نمایهفرمول های ریاضی پیچیده ای از الگوریتم های بردار فاصله و نحوه تصمیم گیری آنها را محاسبه مینمایش کنند،میدهند، اما مفهوم هستهاساسی باقیآن می ماند.که با اضافه کردن معیارهایمتریک هر مسیر اختیاری در یک شبکه، شما حداقل یک بهترین مسیر را خواهید یافتیافت، در تمامی فرکول ها یکسان است. نمایه آن به شکل زیر است:
 
<math>M(i,k) = min [M(i,t) + M(t,k)]</math>
 
این فرمول بیان می دارد که بهترین مسیر بین دو شبکه ((M (i، k) را می توان با پیدا کردن کمترین (min) مقدار مسیرها  بین تمام نقاط شبکه پیدا کرد. توجه داشته باشید که i به معنای مبدا و k به معنای مقصد است. بیایید دوباره در اطلاعات مسیریابی در جدول بالا نگاه کنیم. این اطلاعات را به فرمول اضافه می کنیم،کنیم. می بینیم که مسیر A از B به C هنوز بهترین مسیر است:
 
<math>5(A,C) = min[2(A,B) + 3(B,C)]</math>
خط ۵۸:
<math>6(A,C) = min[6(A,C)]</math>
 
این مثال نشان می دهد که چگونه الگوریتم های بردار فاصله از اطلاعات منتقل شده به آنها برای تصمیم گیری مسیریابی آگاه استفاده می کنند. الگوریتم های استفاده شده توسط روترها و پروتکل های مسیریابی قابل تنظیم نیستند و نمی توان آنها را تغییر داد.یکی دیگر از تفاوت های عمده بین الگوریتم های بردار فاصله و پروتکل های حالت پیوند این است که وقتی پروتکل های مسیریابی بردار فاصله این است که داده های یکدیگر را به روز می کنند، این داده ها ممکن است تمام بخشیو یا تمام بخشی از جدول مسیریابی (بسته به نوع بروز رسانی) از یک روتر به دیگری فرستاده می شود. با استفاده از این فرآیند، هر روتر اطلاعات موجود در جدول خود را به  روترهای دیگر نمایش میدهد،می دهد، به این ترتیب هر روتر یک نمای  کامل تر از محیط شبکه را بدست می آورد و آنها را قادر می سازد تا تصمیمات مسیریابی بهتر را اتخاذ کنند. نمونه هایی پروتکلازپروتکل های محبوبه امروزههایی که ازالگوریتم های بردار فاصله استفاده میکنند RIP و BGP است. دیگر پروتکل های محبوب مانند OSPF نمونه هایی از پروتکل هایی هستند که از الگوریتم مسیریابی حالت پیوند استفاده می کنند. الگوریتم های Bellman-Ford و Ford-Fulkerson جزو الگوریتم های بردار فاصله  شناخته می شوند. در این الگوریتم ها، هر روتر یک جدول مسیریابی دارد که بهترین مسیر را برای هر مقصد نشان می دهد. یک جدول گراف و جدول مسیریابی برای روتر J در زیر نشان داده شده است.
 
[[Image:Dijkstra algorithm example 5.svg]]
خط ۱۰۵:
 
[[Image:Pic DV 1.svg]]
 
 
هزینه هر پیوند 1 تنظیم شده است. بنابراین، مسیری با کمترین هزینه، تنها مسیری است که هزینه آن کمترین باشد . جدول زیر نشان دهنده دانش هر گره از فاصله به تمام گره های دیگر است:<br />
سطر ۱۲۸ ⟵ ۱۲۷:
! G || <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 1 || <math>\infty</math> || 1 || 0
|}
 
 
در ابتدا، هر گره هزینه 1 را به گره هایی که مستقیما به آن متصل هستند و مقدار بی نهایت به تمامی گره های دیگر می دهد. در زیر جدول مسیریابی اولیه در گره A نشان داده شده است:<br />
خط ۱۴۷:
|}
 
در مرحله بعد، هر گره یک پیام را به گره های متصل  ارسال می کند. این پیام حاوی لیستی از فاصله هر گره تا  گره های دیگر است. به عنوان مثال، گره F به گره A می گوید که می تواند با هزینه 1 به  گره G برسد. گره A همچنین می داند که با هزینه ی 1  می تواند به F  برسد، بنابراین این هزینه را برایبه هزینۀ رسیدن به G با استفاده از F می افزاید. از آنجائیکه 2  کمتر از هزینه فعلی  (بی نهایت است) و 2  کمتر،است، بنابراین  گره A می گوید که می تواند از طریق F به G با هزینه 2 برسد. گره A از گره C می آموزد که گره B را می توان از گره C با هزینه ی 1 رد کرد، بنابراین نتیجه می شود که هزینه رسیدن به B از طریق گره C هزینه 2 در بردارد. از آنجا که این هزینه ، بهینه تر ازهزینه فعلی رسیدن به B  که در حال حاضر1حاضر 1 است نمی باشد، اطلاعات جدید نادیده گرفته می شود. جدول نهایی نهایی در گره A ، در زیر نشان داده شده است:
 
{| border=1 cellpadding=5 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
خط ۱۶۵:
|}
 
فرایند دریافت اطلاعات مسیر یابی سازگار به تمام گره ها همگام سازی نامیده می شود. مجموعه نهایی هزینه ها از هر گره به تمام گره های دیگر در جدول زیر نشان داده شده است:<br />▼
 
▲فرایند دریافت اطلاعات مسیر یابی سازگار به تمام گره ها همگام سازی نامیده می شود. مجموعه نهایی هزینه ها از هر گره به تمام گره های دیگر در جدول زیر نشان داده شده است:
 
<br />▼
 
{| border=1 cellpadding=5 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
سطر ۱۹۱ ⟵ ۱۸۸:
|}
 
کییکی از مشکلات با الگوریتم های بردار فاصله، "شمارش تا بی نهایت" (count to infinity) نامیده می شود. بگذارید مشکلاین زیرمشکل را با یک مثال بررسی کنیم: ▼
ی
 
▲کی از مشکلات با الگوریتم های بردار فاصله، "شمارش تا بی نهایت" نامیده می شود. بگذارید مشکل زیر را با یک مثال بررسی کنیم:
 
یک شبکه را با یک گراف در زیر نشان دهید. تنها یک اتصال بین D و سایر قسمت های شبکه وجود دارد.
سطر ۲۱۶ ⟵ ۲۱۱:
|}
 
در حال حاضر لینک C به D  دچار تصادم است  زیرا برای ارسال  بسته با آدرس D باید از لینک  CD استفاده شود ، اما اگر گره D در حال ارسال اطلاعات باشد، هزینه ∞ = [C] [D]  میشود،بنابراین گره C باید بردار فاصله خود را مجددا محاسبه و مسیری را انتخاب کند . به همین ترتیب گره D باید بردارهای خود را بروزرسانی کند. پس از به روزرسانی بردارهای خود در C و D، ما داریم :
 
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
سطر ۲۳۴ ⟵ ۲۲۹:
| <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 0
|}
 
 
 
سطر ۲۵۶ ⟵ ۲۵۲:
|}
 
با توجه به سطر گره B می توان نتیجه گرفت که مسیریابی به گره D می تواند از طریق گره A یاگره  C با هزینه مساوی انجام شود بنابراین گره B بردار خودرا به روزرسانی و ارسال می کند. هر دو گره A وC بردار به روز شده گره B  را دریافت می کنند و متوجه میشوند که مسیرترجیحی خود به گره D در حال حاضر دارای هزینه بالایی است، بنابراین بردارهای  خود را مجددا محاسبه میکنند.▼
 
▲<br />
 
▲با توجه به سطر گره 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 باید بردار خود را با توجه به بردارهای دریافتی دوباره به روزرسانی کند، و سپس اطلاعات خودرا برای آنها می فرستند که در اینجا با یک حلقه مواجح میشویم.▼
 
<br />▼
 
▲سپس گره A و C بردارهای خود را ارسال می کنند وگره B باید بردار خود را با توجه به بردارهای دریافتی دوباره به روزرسانی کند، و سپس اطلاعات خودرا برای آنها می فرستند که در اینجا با یک حلقه مواجح میشویم.
 
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
سطر ۲۹۷ ⟵ ۲۹۳:
| <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 0
|}
 
 
توجه داشته باشید که همچین برداری در واقعیت به ندرت پیش می آید:
سطر ۳۰۵ ⟵ ۳۰۲:
 
این حلقه تا زمانی که تمام گره ها متوجه شوند وزن لینک به گره D بی نهایت است ادامه پیدا میکند. به این ترتیب، کارشناسان می گویند که الگوریتم های بردار فاصله یک نرخ همگرایی آهسته دارند. در نتیجه، الگوریتم بردار فاصله الگوریتم کاملی (در حلقه گیر میکند و جواب درستی  نمی دهد) نیست. یکی از راه حل های این مشکل این است که روترها اطلاعات را فقط برای همسایگان ارسال کنند که لینک منحصر به فردی به مقصد نداشته باشند. به عنوان مثال، در این مورد، گره B نباید به گره C اطلاعات مربوط به گره D را ارسال کند، زیرا گره C تنها راه برای رسیدن به گره D است.
 
▲<br />
 
== الگوریتم های حالت لینک (Link-State Algorithms) ==
برگرفته از «https://fa.wikibooks.org/wiki/شبکه‌های_کامپیوتری/مسیریابی»