logo

Algoritam za usmjeravanje vektora udaljenosti

    Algoritam vektora udaljenosti je iterativan, asinkroni i distribuiran.
      Distribuirano:Distribuira se tako da svaki čvor prima informacije od jednog ili više svojih izravno povezanih susjeda, izvodi izračun i zatim distribuira rezultat natrag svojim susjedima.Iterativno:Iterativan je utoliko što se njegov proces nastavlja sve dok više informacija nije dostupno za razmjenu između susjeda.Asinkrono:Ne zahtijeva da svi njegovi čvorovi međusobno rade u koraku zaključavanja.
  • 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:

    Znanje o cijeloj mreži:Svaki usmjerivač dijeli svoje znanje kroz cijelu mrežu. Usmjerivač šalje svoje prikupljeno znanje o mreži svojim susjedima.Usmjeravanje samo prema susjedima:Usmjerivač šalje svoje znanje o mreži samo onim usmjerivačima koji imaju izravne veze. Usmjerivač šalje sve što ima o mreži kroz portove. Podatke prima usmjerivač i koristi ih za ažuriranje vlastite tablice usmjeravanja.Razmjena informacija u redovitim intervalima:Unutar 30 sekundi usmjerivač šalje informacije susjednim usmjerivačima.

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) = &#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> 

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

Algoritam za usmjeravanje vektora udaljenosti
  • 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.
Algoritam za usmjeravanje vektora udaljenosti

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.

Algoritam za usmjeravanje vektora udaljenosti
    NET ID:Mrežni ID definira konačno odredište paketa.Cijena:Trošak je broj skokova koji paket mora proći da stigne tamo.Sljedeći skok:To je usmjerivač na koji se paket mora isporučiti.
Algoritam za usmjeravanje vektora udaljenosti
  • 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 &amp; E. B sends its routing table to A &amp; C. C sends its routing table to B &amp; D. D sends its routing table to E &amp; C. E sends its routing table to A &amp; 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.
Algoritam za usmjeravanje vektora udaljenosti
  • Nakon prilagodbe, A zatim kombinira ovu tablicu sa svojom vlastitom tablicom kako bi stvorio kombiniranu tablicu.
Algoritam za usmjeravanje vektora udaljenosti
  • 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.
Algoritam za usmjeravanje vektora udaljenosti
  • 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:

Algoritam za usmjeravanje vektora udaljenosti