אלגוריתם וקטור המרחק הוא איטרטיבי, אסינכרוני ומפוזר.
מופץ:הוא מופץ בכך שכל צומת מקבל מידע מאחד או יותר מהשכנים המחוברים ישירות שלו, מבצע חישוב ואז מפיץ את התוצאה חזרה לשכנים שלו.איטרטיבי:זה איטרטיבי בכך שהתהליך שלו נמשך עד שלא יהיה מידע נוסף זמין להחלפה בין שכנים.אסינכרוני:זה לא מחייב שכל הצמתים שלו יפעלו בשלב הנעילה אחד עם השני.
• אלגוריתם וקטור המרחק הוא אלגוריתם דינמי.
• הוא משמש בעיקר ב- ARPANET ו- RIP.
• כל נתב שומר על טבלת מרחק המכונה וֶקטוֹר .

שלושה מפתחות להבנת פעולתו של אלגוריתם ניתוב וקטור מרחק:

ידע על כל הרשת:כל נתב חולק את הידע שלו דרך הרשת כולה. הנתב שולח את הידע שנאסף על הרשת לשכניו.ניתוב רק לשכנים:הנתב שולח את הידע שלו על הרשת רק לאותם נתבים שיש להם קישורים ישירים. הנתב שולח את כל מה שיש לו על הרשת דרך היציאות. המידע מתקבל על ידי הנתב ומשתמש במידע כדי לעדכן את טבלת הניתוב שלו.שיתוף מידע במרווחי זמן קבועים:תוך 30 שניות, הנתב שולח את המידע לנתבים השכנים.

אלגוריתם ניתוב וקטור מרחק

תן ד_איקס(y) תהיה העלות של הנתיב בעל העלות הנמוכה ביותר מהצומת x לצומת y. העלויות הנמוכות ביותר קשורות במשוואת בלמן-פורד,

 d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} 

איפה ה-minv הוא המשוואה שנלקחה עבור כל x השכנים. לאחר נסיעה מ-x ל-v, אם ניקח בחשבון את הנתיב בעל העלות הנמוכה ביותר מ-v ל-y, עלות הנתיב תהיה c(x,v)+d_ב(y). העלות הנמוכה ביותר מ-x עד y היא המינימום של c(x,v)+d_ב(י) השתלט על כל השכנים.

עם אלגוריתם ניתוב וקטור מרחק, הצומת x מכיל את מידע הניתוב הבא:

• עבור כל שכן v, העלות c(x,v) היא עלות הנתיב מ-x לשכן מחובר ישירות, v.
• וקטור המרחק x, כלומר, D_איקס= [ ד_איקס(y) : y ב-N ], המכיל את העלות שלו לכל היעדים, y, ב-N.
• וקטור המרחק של כל אחד מהשכנים שלו, כלומר D_ב= [ ד_ב(y) : y ב-N ] עבור כל שכנה v של x.

ניתוב וקטור מרחק הוא אלגוריתם אסינכרוני שבו הצומת x שולח את העותק של וקטור המרחק שלו לכל שכנותיו. כאשר הצומת x מקבל את וקטור המרחק החדש מאחד הווקטורים הסמוכים לו, v, הוא שומר את וקטור המרחק של v ומשתמש במשוואת בלמן-פורד כדי לעדכן את וקטור המרחק שלו. המשוואה ניתנת להלן:

git pull origin master

 d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N 

הצומת x עדכן את טבלת וקטור המרחק שלו באמצעות המשוואה שלעיל ושולח את הטבלה המעודכנת שלו לכל שכנותיו כדי שיוכלו לעדכן את וקטורי המרחק שלהם.

אַלגוֹרִיתְם

 At each node x, <p> <strong>Initialization</strong> </p> for all destinations y in N: D<sub>x</sub>(y) = c(x,y) // If y is not a neighbor then c(x,y) = &#x221E; for each neighbor w D<sub>w</sub>(y) = ? for all destination y in N. for each neighbor w send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to w <strong>loop</strong> <strong>wait</strong> (until I receive any distance vector from some neighbor w) for each y in N: D<sub>x</sub>(y) = minv{c(x,v)+D<sub>v</sub>(y)} If D<sub>x</sub>(y) is changed for any destination y Send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to all neighbors <strong>forever</strong> 

הערה: באלגוריתם וקטור מרחק, צומת x מעדכן את הטבלה שלו כאשר הוא רואה כל שינוי בעלויות בצמתים מקושרים ישירות או מקבל עדכון וקטור כלשהו מהשכן.

בואו נבין באמצעות דוגמה:

לשתף מידע

• באיור שלמעלה, כל ענן מייצג את הרשת, והמספר בתוך הענן מייצג את מזהה הרשת.
• כל ה-LAN מחוברים על ידי נתבים, והם מיוצגים בתיבות המסומנות כ-A, B, C, D, E, F.
• אלגוריתם ניתוב וקטור מרחק מפשט את תהליך הניתוב על ידי הנחה שהעלות של כל קישור היא יחידה אחת. לכן, ניתן למדוד את יעילות השידור לפי מספר הקישורים להגיע ליעד.
• בניתוב וקטור למרחק, העלות מבוססת על ספירת הופ.

באיור לעיל, אנו רואים שהנתב שולח את הידע לשכנים המיידיים. השכנים מוסיפים את הידע הזה לידע שלהם ושולחים את הטבלה המעודכנת לשכנים שלהם. בדרך זו, נתבים מקבלים מידע משלהם בתוספת המידע החדש על השכנים.

טבלת ניתוב

מתרחשים שני תהליכים:

• יצירת הטבלה
• מעדכן את הטבלה

יצירת הטבלה

בתחילה, טבלת הניתוב נוצרת עבור כל נתב המכילה לפחות שלושה סוגי מידע כגון מזהה רשת, העלות והקפיצה הבאה.

מזהה NET:מזהה הרשת מגדיר את היעד הסופי של החבילה.עֲלוּת:העלות היא מספר הקפצות שהחבילה צריכה לקחת כדי להגיע לשם.תחנה הבאה:זה הנתב שאליו יש להעביר את החבילה.

• באיור לעיל, טבלאות הניתוב המקוריות מוצגות של כל הנתבים. בטבלת ניתוב, העמודה הראשונה מייצגת את מזהה הרשת, העמודה השנייה מייצגת את עלות הקישור, והעמודה השלישית ריקה.
• טבלאות ניתוב אלו נשלחות לכל השכנים.

לדוגמה:

 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 מראה כיצד החבילות יכולות לעבור לרשתות 1 ו-4.
• ה-B הוא שכן לנתב A, החבילות מ-A ל-B יכולות להגיע בקפיצה אחת. אז, 1 מתווסף לכל העלויות המפורטות בטבלה של B והסכום יהיה העלות להגיע לרשת מסוימת.

• לאחר ההתאמה, A משלב טבלה זו עם טבלה משלה כדי ליצור טבלה משולבת.

• הטבלה המשולבת עשויה להכיל כמה נתונים כפולים. באיור שלמעלה, הטבלה המשולבת של נתב A מכילה את הנתונים הכפולים, כך שהיא שומרת רק את הנתונים שהעלות הנמוכה ביותר. לדוגמה, A יכול לשלוח את הנתונים לרשת 1 בשתי דרכים. הראשון, שאינו משתמש בנתב הבא, כך שהוא עולה קפיצה אחת. השני דורש שתי דילוגים (A ל-B, ואז B לרשת 1). לאפשרות הראשונה יש את העלות הנמוכה ביותר, לכן היא נשמרת והשנייה נמחקת.

• תהליך יצירת טבלת הניתוב ממשיך עבור כל הנתבים. כל נתב מקבל את המידע מהשכנים, ומעדכן את טבלת הניתוב.

להלן טבלאות ניתוב סופיות של כל הנתבים: