مسیر یابی بردار فاصله

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

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

الگوریتم مسیر یابی  بردار فاصله به اسامی دیگر نیز خوانده می‌شود. ازجمله الگوریتم مسیر یابی بلمن –فورد و الگوریتم و الگوریتم فورد – فورکرسون که نامگذاری آنها را نام مخترعین آنها بلمن 1975- فورد و فوکرسون، 1962 اقتباس شده است. این الگوریتم مسیر یابی ARPANET اولیه بود و تحت نام RIP در اینترنت مورد استفاده قرارگرفت.

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

 

 

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

به عنوان  مثال ، فرض کنید تاخیر به عنوان مقیاس به کار می‌رود و مسیریاب، تاخیر  به هر همسایه خودش را می‌داند . هر مسیریابدر هر T میلی ثانیه لیستی  از تاخیرهای تخمینی خود را به هر مقصد را ارسال می‌کند ولیست مشابهی از هر همسایه خود دریافت می‌کند فرض کنید  یکی از این جدول‌ها از همسایه‌ها X می‌رسد، به طوری که X زمان رسیدن به مسیریاب I باشد که X آن را تخمین  زده است اگر مسیریاببداند تاخیر تا X برابر با M میلی ثانیه باشد، می‌داند که اگر بخواهد  از طریق X به مسیریابI برسدX+M میلی ثانیه  طول می‌کشد. با انجام این محاسبات  برای هر همسایه‌های مسیریابمی‌تواند بهترین تخمین را تشخیص دهد و می‌تواند از این تخمین و خط متناظر در جدول مسیر یابی جدید استفاده نماید توجه داشته باشیدو که جدول مسیر یابی قبلی، در محاسبه  به کار نمی‌آید.

این فرآیند  بازسازی در شکل 5 آمده است بخش الف زیر شبکه‌ای را نشان می‌دهد چهار ستون اول بخش (ب) بردارهایی تاخیری  را که از همسایه هایی مسیریابJ آمده‌اند نشان می‌دهد تاخیر از A به B برابر با 12 میلی ثانیه و از A به C برابر با 25 میلی ثانیه و از A به D برابر 40 میلی ثانیه و غیره  است فرض کنید تاخیرهایی J به همسایه هایش A,H,I,A به ترتیب عبارتست از 8و10و12و6 میلی ثانیه .

 

 

چگونگی محاسبه مسیر جدید از J به G را در نظر بگیرید J می‌داند که می‌تواند با 8 میلی ثانیه تاخیر به A برسد و A با 18 میلی ثانیه به G می‌رسد لذا J می‌داندکه اگر بخواهد از طریق A به  G برسد 26 میلی ثانیه طول می‌کشد. به طور مشابه به تاخیر رسیدن به J را در جدول ،18 میلی ثانیه ثبت می‌کند و آن، از طریق H است محاسبه مشابهی برای تمام مقصدها صورت میگیرد به طوری که جدول مسیر یابی  جدید را به صورت آخرین به صورت اخرین ستون شکل در می‌آید.