الگوریتم مسیریابی بردار فاصله

الگوریتم مسیریابی بردار فاصله – Distance Vector Routing– آموزش شبکه درس 28

الگوریتم مسیریابی بردار فاصله (Distance Vector Routing Algorithm) یک الگوریتم تکرار شونده (Iterative)، غیرهمزمان (Asynchronous) و توزیع شده (Distributed) است. هر کدام از ویژگی‌های این الگوریتم را در بخش زیر توضیح داده ایم:

  • توزیع شده (Distributed): معنای «توزیع شده» در این الگوریتم اشاره به آن دارد که هر کدام از گره‌ها (Nodes) موجود بر روی این الگوریتم اطلاعات خود را از یک و یا چند گره دیگر که در همسایگی آن قرار دارند دریافت می‌کند، پردازش‌های لازم را بر روی آن‌ها انجام می‌دهد و سپس پاسخ را به بین گره‌هائی که در همسایگی خود قرار دارند توزیع می‌کند.
  • تکرار شونده (Iterative): معنای «تکرار شوند» اشاره به آن دارد که هر کدام از گره‌ها تا زمانی که یک یا چند گره در همسایگی خود داشته باشد، به صورت دائمی به پردازش اطلاعات دریافت شده از آن‌ها ادامه می‌دهد. این کار برای بارها و بارها تکرار می‌شود تا اطلاعات همیشه به روز شده باشند و در عین حال تبادل‌های لازم انجام شوند.
  • غیر همزمان (Asynchronous): معنای «غیر همزمانی» اشاره به این مفهوم دارد که تمام گره‌ها در زمانی که در تبادل با همدیگر هستند، لینک را قفل می‌کنند و اجازه دسترسی دیگر گره‌ها به آن را نمی‌دهند. پس از انجام ارتباط و تبادل گره از حالت قفل خارج شده و اطلاعات گره‌های دیگر را دریافت می‌کند. این کار سبب می‌شد که برخی از پک‌های اطلاعاتی در زمان ارسال در حالت انتظار باقی بمانند، لذا ارتباطات به صورت آنی و در لحظه نیست و بسته به شلوغی شبکه ممکن است تاخیر اتفاق بیفتد.

الگوریتم بردار فاصله یکی از الگوریتم‌های دینامیکی شبکه (Dynamic Algorithm) به شما می‌رود. اصلی‌ترین زمینه کاربرد این الگوریتم در پروژه ARPANET و RIP بوده است.

هر کدام از روترهایی که در جدول فواصل را در خود نگهداری می‌کنند به عنوان «بردار -Vector» شناخته می‌شوند.

درک کارکرد الگوریتم مسیر یابی بردار فاصله

برای درک کارکرد درست الگوریتم مسیریابی بردار فاصله لازم است که به این نکات دقت داشته باشیم:

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

آشنائی فرمول با الگوریتم بردار فاصله

در اینجا فرض کنید که dx(y) هزینه محاسبه شده حداقلی برای مسیر طی شده از گره X به Y است. حداقل هزینه با استفاده از فرمول بلمان-فورد (Bellman-Ford) به صورت زیر محاسبه می‌شود:

dx(y) = minv{c(x,v) + dv(y)}

در این جا مقدار minv برای تمام گره‌هائی که در همسایگی گره X هستند محاسبه می‌شود. بعد از طی مسافت از X به V اگر ما هزینه حداقل مسیر از V به Y را محاسبه کنیم، معادله ما به صورت c(x,v)+dv(y) خواهد بود. هزینه حداقل از X به Y مقدار حداقلی به دست آمده از معادله c(x,v)+dv(y) است که بر روی تمام همسایه‌ها انجام می‌شود.

با استفاده از الگوریتم مسیریابی بردار فاصله، گره X حاوی اطلاعات مسیریبای به شرح زیر است:

  • برای هر کدام از گره‌های V که در همسایگی وجود دارند، هزینه c(x,v) در اینجا برابر با هزینه مسیر از گره X به گره V است که مستقیماً در همسایگی آن قرار دارد.
  • فاصله بردارد X در اینجا Dx= [ Dx(y) : y in N ] شامل تمام هزینه‌ها آن برای مقاصد Y در N می‌شود.
  • بردار فاصله هر کدام از همسایه‌ها یعنی Dx = [ Dx(y) : y in N ] برای هر کدام از گره‌های V از X است.

الگوریتم مسیریابی بردار فاصله یک الگوریتم غیرهمزمان است که در آن هر کدام از گره‌های X یک کپی از بردار فاصله خود را به تمام همسایه‌هایش ارسال می‌کند. هنگامی که گره X یک بردار فاصله جدید راا از یکی از بردارهای همسایگی خود دریافت می‌کند، گره V آن بردار فاصله v را ذخیره می‌کند و از معادله بلمان-فورد برای به روز رسانی بردار فاصله خودش استفاده می‌کند. معادله ای که در اینجا به دست می‌آید به شرح زیر خواهد بود:

dx(y) = minv{ c(x,v) + dv(y)}     for each node y in N

گره X در اینجا جدول بردار فاصله خودش را با استفاده از معادله بالا به روز رسانی می‌کند و جدول به روز رسانی شده خودش را به تمام گره‌هائی که در اطرافش هستند ارسال می‌کند تا آن‌ها نیز جدول بردار فاصله خودشان را به روز رسانی کنند. در بخش بعدی الگوریتم این موضوع به شکل کامل ارائه شده است.

الگوریتم بردار فاصله

At each node x,

Initialization




for all destinations y in N:

Dx(y) = c(x,y)     // If y is not a neighbor then c(x,y) = ∞

for each neighbor w

Dw(y) = ?     for all destination y in N.

for each neighbor w

send distance vector Dx = [ Dx(y)  : y in N ] to w

loop

wait(until I receive any distance vector from some neighbor w)

for each y in N:

Dx(y) = minv{c(x,v)+Dv(y)}

If Dx(y) is changed for any destination y

Send distance vector Dx = [ Dx(y) : y in N ] to all neighbors

forever

 

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

برای درک موضوع و کارکرد این الگوریتم بهتر است که به مثال زیر دقت کنید:

اشتراک گذاری اطلاعات

مدل مفهومی شبکه، برای الگوریتم مسریابی بردار فاصله

مدل مفهومی شبکه، برای الگوریتم مسریابی بردار فاصله

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

تمام شبکه‌های محلی (LAN) در این تصویر به وسیله روترها به همدیگر متصل شده اند و هر کدام از این روترها هم در مربع‌هائی که با حروف A، B، C، D، E و F علامت گذاری شده اند، مشخص گردیده اند.

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

در مسیریابی بردار فاصله هزینه بر اساس تعداد‌هاپ (Hop Count) محاسبه می‌شود.

محاسبه تعداد هاپ ها در الگوریتم بردار فاصله

محاسبه تعداد هاپ ها در الگوریتم بردار فاصله

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

جدول مسیریابی

دو فرایند در اینجا رخ می‌دهد:

  • ساختن جدول
  • به روز رسانی جدول‌ها

ساختن جدول

در ابتدای کار، جدول مسیریابی برای هر کدام ز روترهائی که دارای حداقل سه نوع از اطلاعات یعنی ID شبکه (Network ID)، هزینه (Cost) و‌هاپ بعدی (Next Hop) باشند، ساخته می‌شود.

جدول الگوریتم مسیریابی بردار فاصله

جدول الگوریتم مسیریابی بردار فاصله

  • ID شبکه: تعریف کننده مقصد نهائی پک‌های اطلاعاتی است؛
  • هزینه: نشان دهنده تعداد‌هاپ‌هائی است که پک‌های اطلاعاتی باید طی کنند تا به مقصد نهائی خودشان برسند؛
  • هاپ بعدی: نیز روتری است که باید پک‌های اطلاعاتی را دریافت کند؛
جدول توزیع شده در شبکه

جدول توزیع شده در شبکه

در تصویر بالا، جدول‌های مسیریابی اصلی تمام روترها نشان داده شده اند. در یک جدول مسیریابی، اولین ستون نشان دهنده ID شبکه است، دومین ستون نشان دهنده هزینه ای است که هر لینک دارد و در نهایت سومین ستون اغلب خالی است.

این جداول مسیریابی برای تمامی گره‌هائی که در همسایگی یک گره وجود دارند ارسال می‌شوند.

برای درک بهتر به مثالی که در زیر آمده است دقت کنید:

A sends its routing table to B, F & E.

B sends its routing table to A & C.

C sends its routing table to B & D.

D sends its routing table to E & C.

E sends its routing table to A & D.

F sends its routing table to A.

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

به روز رسانی جداول مسیر یابی در هاپ ها

به روز رسانی جداول مسیر یابی در هاپ ها

بعد از انجام تنظیمات، گره A این جدول را با جدول خودش ترکیب می‌کند تا بتواند یک جدول ترکیبی بهتر به دست بیاورد.

ایجاد داده های تکراری در جداول مسیریابی الگوریتم

ایجاد داده های تکراری در جداول مسیریابی الگوریتم

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

ایجاد جداول ترکیبی برای مسیریابی

ایجاد جداول ترکیبی برای مسیریابی

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

نتیجه نهائی این مسیریابی‌ها به شرح زیر است:

ایجاد جداول ترکیبی و مسیریابی در الگوریتم بردار فاصله

ایجاد جداول ترکیبی و مسیریابی در الگوریتم بردار فاصله

No votes yet.
Please wait...

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد.

منو اصلی

question