- Avstandsvektoralgoritmen er en dynamisk algoritme.
- Den brukes hovedsakelig i ARPANET og RIP.
- Hver ruter opprettholder en avstandstabell kjent som Vektor .
Tre nøkler for å forstå hvordan Distance Vector Routing Algoritmen fungerer:
Avstandsvektorrutingsalgoritme
La dx(y) være kostnaden for den laveste kostnadsveien fra node x til node y. De minste kostnadene er knyttet til Bellman-Ford-ligningen,
d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)}
Hvor minv er ligningen tatt for alle x naboer. Etter å ha reist fra x til v, hvis vi vurderer den billigste veien fra v til y, vil banekostnaden være c(x,v)+di(y). Den minste kostnaden fra x til y er minimum av c(x,v)+di(y) overtatt alle naboer.
Med Distance Vector Routing-algoritmen inneholder noden x følgende rutinginformasjon:
- For hver nabo v, er kostnaden c(x,v) veikostnaden fra x til direkte tilknyttet nabo, v.
- Avstandsvektoren x, dvs. Dx= [Dx(y) : y i N ], som inneholder kostnadene for alle destinasjoner, y, i N.
- Avstandsvektoren til hver av naboene, dvs. Di= [Di(y): y i N] for hver nabo v av x.
Avstandsvektorruting er en asynkron algoritme der node x sender kopien av avstandsvektoren til alle naboene. Når node x mottar den nye avstandsvektoren fra en av dens nabovektorer, v, lagrer den avstandsvektoren til v og bruker Bellman-Ford-ligningen til å oppdatere sin egen avstandsvektor. Ligningen er gitt nedenfor:
freddie mercury
d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N
Noden x har oppdatert sin egen avstandsvektortabell ved å bruke ligningen ovenfor og sender sin oppdaterte tabell til alle naboene slik at de kan oppdatere sine egne avstandsvektorer.
Algoritme
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>
Merk: I Avstandsvektoralgoritme oppdaterer node x tabellen når den enten ser kostnadsendring i en direkte koblet node eller mottar vektoroppdatering fra en nabo.
La oss forstå gjennom et eksempel:
Dele informasjon
- I figuren ovenfor representerer hver sky nettverket, og nummeret inne i skyen representerer nettverks-IDen.
- Alle LAN er koblet sammen med rutere, og de er representert i bokser merket som A, B, C, D, E, F.
- Avstandsvektorrutingsalgoritme forenkler rutingprosessen ved å anta at kostnaden for hver kobling er én enhet. Derfor kan overføringseffektiviteten måles ved antall lenker for å nå destinasjonen.
- I Avstandsvektorruting er kostnaden basert på hopptelling.
I figuren ovenfor observerer vi at ruteren sender kunnskapen til de nærmeste naboene. Naboene legger denne kunnskapen til sin egen kunnskap og sender den oppdaterte tabellen til sine egne naboer. På denne måten får rutere sin egen informasjon pluss den nye informasjonen om naboene.
Rutetabell
To prosesser skjer:
- Opprette tabellen
- Oppdaterer tabellen
Opprette tabellen
Til å begynne med opprettes rutetabellen for hver ruter som inneholder minst tre typer informasjon som nettverks-ID, kostnaden og neste hopp.
- I figuren ovenfor vises de originale rutetabellene for alle ruterne. I en rutingtabell representerer den første kolonnen nettverks-IDen, den andre kolonnen representerer kostnaden for koblingen, og den tredje kolonnen er tom.
- Disse rutetabellene sendes til alle naboene.
For eksempel:
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.
Oppdaterer tabellen
- Når A mottar en rutetabell fra B, bruker den informasjonen til å oppdatere tabellen.
- Rutingtabellen til B viser hvordan pakkene kan flytte til nettverkene 1 og 4.
- B-en er nabo til A-ruteren, pakkene fra A til B kan nå i ett hopp. Så 1 legges til alle kostnadene gitt i B-tabellen og summen vil være kostnaden for å nå et bestemt nettverk.
- Etter justering kombinerer A så denne tabellen med sin egen tabell for å lage en kombinert tabell.
- Den kombinerte tabellen kan inneholde noen dupliserte data. I figuren ovenfor inneholder den kombinerte tabellen for ruter A dupliserte data, så den beholder bare de dataene som har den laveste kostnaden. For eksempel kan A sende dataene til nettverk 1 på to måter. Den første, som ikke bruker noen neste ruter, så den koster ett hopp. Den andre krever to hopp (A til B, deretter B til Network 1). Det første alternativet har den laveste kostnaden, derfor beholdes det og det andre droppes.
- Prosessen med å lage rutetabellen fortsetter for alle rutere. Hver ruter mottar informasjonen fra naboene, og oppdaterer rutetabellen.
De endelige rutetabellene for alle ruterne er gitt nedenfor: