- Algoritam vektora udaljenosti je dinamički algoritam.
- Uglavnom se koristi u ARPANET-u i RIP-u.
- Svaki usmjerivač održava tablicu udaljenosti poznatu kao Vektor .
Tri ključa za razumijevanje rada algoritma za usmjeravanje vektora udaljenosti:
Algoritam za usmjeravanje vektora udaljenosti
Neka dx(y) biti trošak puta s najmanjim troškovima od čvora x do čvora y. Najmanji troškovi povezani su Bellman-Fordovom jednadžbom,
d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)}
Gdje minv je jednadžba uzeta za svih x susjeda. Nakon putovanja od x do v, ako uzmemo u obzir put s najmanjim troškovima od v do y, cijena puta će biti c(x,v)+du(y). Najmanji trošak od x do y je minimum c(x,v)+du(y) preuzeti svi susjedi.
Uz algoritam za usmjeravanje vektora udaljenosti, čvor x sadrži sljedeće informacije o usmjeravanju:
- Za svakog susjeda v, trošak c(x,v) je trošak puta od x do izravno priključenog susjeda, v.
- Vektor udaljenosti x, tj. Dx= [ Dx(y) : y u N ], koji sadrži njegovu cijenu za sva odredišta, y, u N.
- Vektor udaljenosti svakog od njegovih susjeda, tj. Du= [ Du(y) : y u N ] za svaki susjed v od x.
Usmjeravanje vektora udaljenosti je asinkroni algoritam u kojem čvor x šalje kopiju svog vektora udaljenosti svim svojim susjedima. Kada čvor x primi novi vektor udaljenosti od jednog od svojih susjednih vektora, v, sprema vektor udaljenosti od v i koristi Bellman-Fordovu jednadžbu za ažuriranje vlastitog vektora udaljenosti. Jednadžba je dana u nastavku:
kada je izašao win 7
d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N
Čvor x je ažurirao vlastitu tablicu vektora udaljenosti korištenjem gornje jednadžbe i šalje svoju ažuriranu tablicu svim svojim susjedima kako bi mogli ažurirati vlastite vektore udaljenosti.
Algoritam
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>
Napomena: U vektorskom algoritmu udaljenosti, čvor x ažurira svoju tablicu kada vidi bilo kakvu promjenu troškova u jednom izravno povezanom čvoru ili primi bilo kakvo ažuriranje vektora od nekog susjeda.
Razumimo kroz primjer:
Dijeljenje informacija
- Na gornjoj slici svaki oblak predstavlja mrežu, a broj unutar oblaka predstavlja ID mreže.
- Svi LAN-ovi povezani su usmjerivačima, a predstavljeni su u okvirima označenim s A, B, C, D, E, F.
- Algoritam za usmjeravanje vektora udaljenosti pojednostavljuje proces usmjeravanja pretpostavljajući da je cijena svake veze jedna jedinica. Stoga se učinkovitost prijenosa može mjeriti brojem veza do odredišta.
- U vektorskom usmjeravanju udaljenosti trošak se temelji na broju skokova.
Na gornjoj slici vidimo da usmjerivač šalje znanje neposrednim susjedima. Susjedi to znanje dodaju vlastitom znanju i ažuriranu tablicu šalju svojim susjedima. Na taj način usmjerivači dobivaju vlastite informacije plus nove informacije o susjedima.
Tablica usmjeravanja
Događaju se dva procesa:
- Stvaranje tablice
- Ažuriranje tablice
Stvaranje tablice
U početku se kreira tablica usmjeravanja za svaki usmjerivač koja sadrži najmanje tri vrste informacija kao što su ID mreže, cijena i sljedeći skok.
- Na gornjoj slici prikazane su originalne tablice usmjeravanja svih usmjerivača. U tablici usmjeravanja, prvi stupac predstavlja ID mreže, drugi stupac predstavlja cijenu veze, a treći stupac je prazan.
- Ove se tablice usmjeravanja šalju svim susjedima.
Na primjer:
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žuriranje tablice
- Kada A primi tablicu usmjeravanja od B, tada koristi svoje podatke za ažuriranje tablice.
- Tablica usmjeravanja B pokazuje kako se paketi mogu kretati prema mrežama 1 i 4.
- B je susjed A rutera, paketi od A do B mogu stići u jednom skoku. Dakle, 1 se dodaje svim troškovima navedenim u tablici B i zbroj će biti trošak za postizanje određene mreže.
- Nakon prilagodbe, A zatim kombinira ovu tablicu sa svojom vlastitom tablicom kako bi stvorio kombiniranu tablicu.
- Kombinirana tablica može sadržavati neke duple podatke. Na gornjoj slici, kombinirana tablica usmjerivača A sadrži duplicirane podatke, tako da čuva samo one podatke koji imaju najnižu cijenu. Na primjer, A može poslati podatke mreži 1 na dva načina. Prvi, koji ne koristi sljedeći usmjerivač, pa košta jedan skok. Drugi zahtijeva dva skoka (A do B, zatim B do mreže 1). Prva opcija ima najnižu cijenu, stoga se zadržava, a druga se odbacuje.
- Proces kreiranja tablice usmjeravanja nastavlja se za sve usmjerivače. Svaki usmjerivač prima informacije od susjeda i ažurira tablicu usmjeravanja.
Konačne tablice usmjeravanja svih usmjerivača dane su u nastavku: