- Algoritmul vector Distanță este un algoritm dinamic.
- Este folosit în principal în ARPANET și RIP.
- Fiecare router menține un tabel de distanțe cunoscut ca Vector .
Trei chei pentru a înțelege funcționarea algoritmului de rutare vectorială la distanță:
Algoritmul de rutare vectorială de distanță
Fie dX(y) să fie costul căii cu cel mai mic cost de la nodul x la nodul y. Cele mai mici costuri sunt legate de ecuația Bellman-Ford,
d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} Unde minv este ecuația luată pentru toți vecinii x. După călătoria de la x la v, dacă luăm în considerare calea cu cel mai mic cost de la v la y, costul căii va fi c(x,v)+dîn(y). Cel mai mic cost de la x la y este minimul lui c(x,v)+dîn(y) a preluat toți vecinii.
Cu algoritmul de rutare vectorială distanță, nodul x conține următoarele informații de rutare:
- Pentru fiecare vecin v, costul c(x,v) este costul căii de la x la vecinul direct atașat, v.
- Vectorul distanță x, adică DX= [ DX(y): y în N ], cuprinzând costul său către toate destinațiile, y, în N.
- Vectorul distanță al fiecăruia dintre vecinii săi, adică Dîn= [ Dîn(y): y în N ] pentru fiecare vecin v al lui x.
Rutarea vectorului distanță este un algoritm asincron în care nodul x trimite copia vectorului distanță către toți vecinii săi. Când nodul x primește noul vector de distanță de la unul dintre vectorul său vecin, v, salvează vectorul de distanță al lui v și folosește ecuația Bellman-Ford pentru a-și actualiza propriul vector de distanță. Ecuația este dată mai jos:
linie nouă în python
d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N Nodul x și-a actualizat propriul tabel vector de distanță folosind ecuația de mai sus și trimite tabelul actualizat tuturor vecinilor săi, astfel încât aceștia să își poată actualiza propriii vectori de distanță.
Algoritm
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> Notă: În algoritmul vectorial de distanță, nodul x își actualizează tabelul atunci când fie vede orice modificare a costurilor într-un nod direct legat, fie primește orice actualizare vectorială de la un vecin.
Să înțelegem printr-un exemplu:
Partajarea informațiilor
- În figura de mai sus, fiecare nor reprezintă rețeaua, iar numărul din interiorul norului reprezintă ID-ul rețelei.
- Toate rețelele LAN sunt conectate prin routere și sunt reprezentate în casete etichetate ca A, B, C, D, E, F.
- Algoritmul de rutare vectorială de distanță simplifică procesul de rutare presupunând că costul fiecărei legături este de o unitate. Prin urmare, eficiența transmisiei poate fi măsurată prin numărul de legături pentru a ajunge la destinație.
- În rutarea vectorului la distanță, costul se bazează pe numărul de hop.
În figura de mai sus, observăm că routerul trimite cunoștințele vecinilor imediati. Vecinii adaugă aceste cunoștințe la propriile cunoștințe și trimite tabelul actualizat propriilor vecini. În acest fel, routerele obțin propriile informații plus noile informații despre vecini.
Tabel de rutare
Au loc două procese:
- Crearea Tabelului
- Actualizarea tabelului
Crearea Tabelului
Inițial, tabelul de rutare este creat pentru fiecare router care conține cel puțin trei tipuri de informații, cum ar fi ID-ul rețelei, costul și următorul hop.
- În figura de mai sus, tabelele de rutare originale sunt afișate pentru toate routerele. Într-un tabel de rutare, prima coloană reprezintă ID-ul rețelei, a doua coloană reprezintă costul conexiunii, iar a treia coloană este goală.
- Aceste tabele de rutare sunt trimise tuturor vecinilor.
De exemplu:
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.
Actualizarea tabelului
- Când A primește o tabelă de rutare de la B, atunci își folosește informațiile pentru a actualiza tabelul.
- Tabelul de rutare al lui B arată cum se pot muta pachetele în rețelele 1 și 4.
- B este un vecin cu routerul A, pachetele de la A la B pot ajunge într-un singur hop. Deci, 1 se adaugă la toate costurile date în tabelul lui B și suma va fi costul pentru a ajunge la o anumită rețea.
- După ajustare, A combină apoi acest tabel cu propriul său tabel pentru a crea un tabel combinat.
- Tabelul combinat poate conține unele date duplicat. În figura de mai sus, tabelul combinat al routerului A conține datele duplicate, deci păstrează doar acele date care au cel mai mic cost. De exemplu, A poate trimite datele către rețeaua 1 în două moduri. Primul, care nu folosește următorul router, deci costă un hop. Al doilea necesită două sărituri (A la B, apoi B la Rețeaua 1). Prima variantă are cel mai mic cost, prin urmare se păstrează, iar a doua este abandonată.
- Procesul de creare a tabelului de rutare continuă pentru toate routerele. Fiecare router primește informații de la vecini și actualizează tabelul de rutare.
Tabelele finale de rutare ale tuturor routerelor sunt prezentate mai jos:
