logo

Avstandsvektorrutingsalgoritme

    Avstandsvektoralgoritmen er iterativ, asynkron og distribuert.
      Distribuert:Den fordeles ved at hver node mottar informasjon fra en eller flere av sine direkte tilknyttede naboer, utfører beregninger og deretter distribuerer resultatet tilbake til sine naboer.Iterativ:Det er iterativt ved at prosessen fortsetter til det ikke er mer tilgjengelig informasjon som kan utveksles mellom naboer.Asynkron:Det krever ikke at alle nodene opererer i låsetrinn med hverandre.
  • 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:

    Kunnskap om hele nettverket:Hver ruter deler sin kunnskap gjennom hele nettverket. Ruteren sender sin innsamlede kunnskap om nettverket til sine naboer.Ruting kun til naboer:Ruteren sender sin kunnskap om nettverket kun til de ruterne som har direkte koblinger. Ruteren sender det den har om nettverket gjennom portene. Informasjonen mottas av ruteren og bruker informasjonen til å oppdatere sin egen rutetabell.Informasjonsdeling med jevne mellomrom:I løpet av 30 sekunder sender ruteren informasjonen til naboruterne.

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

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

Algoritme for avstandsvektorruting
  • 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.
Algoritme for avstandsvektorruting

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.

Algoritme for avstandsvektorruting
    NET ID:Nettverks-IDen definerer den endelige destinasjonen for pakken.Koste:Kostnaden er antall hopp pakken må ta for å komme dit.Neste hopp:Det er ruteren som pakken skal leveres til.
Avstandsvektorrutingsalgoritme
  • 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 &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. 

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.
Algoritme for avstandsvektorruting
  • Etter justering kombinerer A så denne tabellen med sin egen tabell for å lage en kombinert tabell.
Algoritme for avstandsvektorruting
  • 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.
Avstandsvektorrutingsalgoritme
  • 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:

Algoritme for avstandsvektorruting