- Algoritem vektorja razdalje je dinamičen algoritem.
- Uporablja se predvsem v ARPANET in RIP.
- Vsak usmerjevalnik vzdržuje tabelo razdalj, znano kot Vektor .
Trije ključi za razumevanje delovanja algoritma za usmerjanje vektorjev razdalje:
Algoritem za usmerjanje vektorja razdalje
Naj dx(y) strošek poti z najmanjšimi stroški od vozlišča x do vozlišča y. Najmanjši stroški so povezani z Bellman-Fordovo enačbo,
d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} Kje minv je enačba za vse x sosede. Po potovanju od x do v, če upoštevamo pot z najmanjšimi stroški od v do y, bodo stroški poti c(x,v)+dv(y). Najmanjši strošek od x do y je najmanjši c(x,v)+dv(y) prevzel vse sosede.
Z algoritmom za usmerjanje vektorja razdalje vozlišče x vsebuje naslednje informacije o usmerjanju:
- Za vsakega soseda v je strošek c(x,v) strošek poti od x do neposredno priključenega soseda, v.
- Vektor razdalje x, tj. Dx= [Dx(y) : y v N ], ki vsebuje njegove stroške do vseh destinacij, y, v N.
- Vektor razdalje vsakega od njegovih sosedov, tj. Dv= [Dv(y) : y v N ] za vsakega soseda v od x.
Usmerjanje vektorja razdalje je asinhroni algoritem, v katerem vozlišče x pošlje kopijo svojega vektorja razdalje vsem svojim sosedom. Ko vozlišče x prejme nov vektor razdalje od enega od svojih sosednjih vektorjev v, shrani vektor razdalje v in uporabi Bellman-Fordovo enačbo za posodobitev lastnega vektorja razdalje. Enačba je podana spodaj:
kaj je poseben znak
d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N Vozlišče x je posodobilo lastno tabelo vektorjev razdalje z uporabo zgornje enačbe in pošlje posodobljeno tabelo vsem svojim sosedom, da lahko posodobijo svoje vektorje razdalje.
Algoritem
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) = ∞ 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> Opomba: V vektorskem algoritmu razdalje vozlišče x posodobi svojo tabelo, ko opazi kakršno koli spremembo stroškov v enem neposredno povezanem vozlišču ali prejme kakršno koli posodobitev vektorja od soseda.
Razumejmo na primeru:
Skupna raba informacij
- Na zgornji sliki vsak oblak predstavlja omrežje, številka v oblaku pa ID omrežja.
- Vsa omrežja LAN so povezana z usmerjevalniki in so predstavljena v poljih, označenih z A, B, C, D, E, F.
- Algoritem usmerjanja z vektorjem razdalje poenostavlja postopek usmerjanja s predpostavko, da je cena vsake povezave ena enota. Zato lahko učinkovitost prenosa merimo s številom povezav, ki dosežejo cilj.
- Pri usmerjanju vektorja razdalje strošek temelji na številu skokov.
Na zgornji sliki opazimo, da usmerjevalnik pošilja znanje neposrednim sosedom. Sosedje to znanje dodajo svojemu znanju in posodobljeno tabelo pošljejo svojim sosedom. Na ta način dobijo usmerjevalniki lastne informacije in nove informacije o sosedih.
Usmerjevalna tabela
Pojavi se dva procesa:
- Ustvarjanje tabele
- Posodabljanje tabele
Ustvarjanje tabele
Na začetku se usmerjevalna tabela ustvari za vsak usmerjevalnik, ki vsebuje vsaj tri vrste informacij, kot so ID omrežja, cena in naslednji skok.
- Na zgornji sliki so prikazane originalne usmerjevalne tabele vseh usmerjevalnikov. V usmerjevalni tabeli prvi stolpec predstavlja ID omrežja, drugi stolpec predstavlja ceno povezave, tretji stolpec pa je prazen.
- Te usmerjevalne tabele so poslane vsem sosedom.
Na primer:
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.
Posodabljanje tabele
- Ko A prejme usmerjevalno tabelo od B, uporabi njene podatke za posodobitev tabele.
- Usmerjevalna tabela B prikazuje, kako se lahko paketi premikajo v omrežji 1 in 4.
- B je sosed usmerjevalnika A, paketi od A do B lahko dosežejo v enem skoku. Torej se 1 doda vsem stroškom, podanim v tabeli B, in vsota bo strošek doseganja določenega omrežja.
- Po prilagoditvi A nato to tabelo združi s svojo tabelo, da ustvari kombinirano tabelo.
- Kombinirana tabela lahko vsebuje nekaj podvojenih podatkov. Na zgornji sliki kombinirana tabela usmerjevalnika A vsebuje podvojene podatke, zato hrani samo tiste podatke, ki imajo najnižjo ceno. Na primer, A lahko pošlje podatke v omrežje 1 na dva načina. Prvi, ki ne uporablja naslednjega usmerjevalnika, zato stane en skok. Drugi zahteva dva skoka (od A do B, nato od B do omrežja 1). Prva možnost ima najnižje stroške, zato jo obdržimo, drugo pa opustimo.
- Postopek ustvarjanja usmerjevalne tabele se nadaljuje za vse usmerjevalnike. Vsak usmerjevalnik prejme informacije od sosedov in posodobi usmerjevalno tabelo.
Končne usmerjevalne tabele vseh usmerjevalnikov so podane spodaj:
