- Het afstandsvectoralgoritme is een dynamisch algoritme.
- Het wordt voornamelijk gebruikt in ARPANET en RIP.
- Elke router houdt een afstandstabel bij, bekend als Vector .
Drie sleutels om de werking van het Distance Vector Routing Algorithm te begrijpen:
Afstandsvectorrouteringsalgoritme
Laat dX(y) de kosten zijn van het goedkoopste pad van knooppunt x naar knooppunt y. De laagste kosten worden gerelateerd aan de Bellman-Ford-vergelijking,
d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} Waar de minv is de vergelijking voor alle x buren. Als we na de reis van x naar v het goedkoopste pad van v naar y beschouwen, zijn de padkosten c(x,v)+din(y). De laagste kosten van x tot y zijn het minimum van c(x,v)+din(y) alle buren overgenomen.
Met het Distance Vector Routing-algoritme bevat het knooppunt x de volgende routeringsinformatie:
- Voor elke buur v zijn de kosten c(x,v) de padkosten van x naar direct gekoppelde buur v.
- De afstandsvector x, dat wil zeggen DX= [DX(y) : y in N ], met de kosten voor alle bestemmingen, y, in N.
- De afstandsvector van elk van zijn buren, d.w.z. Din= [Din(y) : y in N ] voor elke buur v van x.
Afstandsvectorroutering is een asynchroon algoritme waarin knooppunt x de kopie van zijn afstandsvector naar al zijn buren verzendt. Wanneer knooppunt x de nieuwe afstandsvector ontvangt van een van zijn aangrenzende vectoren, v, slaat het de afstandsvector van v op en gebruikt het de Bellman-Ford-vergelijking om zijn eigen afstandsvector bij te werken. De vergelijking wordt hieronder gegeven:
volledig optelcircuit
d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N Het knooppunt x heeft zijn eigen afstandsvectortabel bijgewerkt met behulp van de bovenstaande vergelijking en stuurt zijn bijgewerkte tabel naar al zijn buren, zodat zij hun eigen afstandsvectoren kunnen bijwerken.
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> Opmerking: In het afstandsvectoralgoritme werkt knooppunt x zijn tabel bij wanneer het een kostenverandering ziet in een direct gekoppeld knooppunt of een vectorupdate ontvangt van een buur.
Laten we het begrijpen aan de hand van een voorbeeld:
Het delen van informatie
- In de bovenstaande afbeelding vertegenwoordigt elke wolk het netwerk en vertegenwoordigt het nummer in de wolk de netwerk-ID.
- Alle LAN's zijn verbonden door routers en worden weergegeven in vakken met de aanduiding A, B, C, D, E, F.
- Het afstandsvectorrouteringsalgoritme vereenvoudigt het routeringsproces door aan te nemen dat de kosten van elke link één eenheid zijn. Daarom kan de efficiëntie van de transmissie worden gemeten aan de hand van het aantal verbindingen om de bestemming te bereiken.
- Bij afstandsvectorroutering zijn de kosten gebaseerd op het aantal hops.
In bovenstaande figuur zien we dat de router de kennis naar de directe buren stuurt. De buren voegen deze kennis toe aan hun eigen kennis en sturen de bijgewerkte tabel naar hun eigen buren. Op deze manier krijgen routers hun eigen informatie plus de nieuwe informatie over de buren.
Routeringstabel
Er vinden twee processen plaats:
- De tabel maken
- De tabel bijwerken
De tabel maken
In eerste instantie wordt voor elke router een routeringstabel gemaakt die ten minste drie soorten informatie bevat, zoals netwerk-ID, de kosten en de volgende hop.
- In de bovenstaande afbeelding worden de originele routeringstabellen van alle routers weergegeven. In een routeringstabel vertegenwoordigt de eerste kolom de netwerk-ID, vertegenwoordigt de tweede kolom de kosten van de link en is de derde kolom leeg.
- Deze routeringstabellen worden naar alle buren verzonden.
Bijvoorbeeld:
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.
De tabel bijwerken
- Wanneer A een routeringstabel van B ontvangt, gebruikt hij de informatie ervan om de tabel bij te werken.
- De routeringstabel van B laat zien hoe de pakketten naar de netwerken 1 en 4 kunnen worden verplaatst.
- De B is een buur van de A-router, de pakketten van A naar B kunnen in één hop worden bereikt. Er wordt dus 1 opgeteld bij alle kosten in tabel B en de som is de kosten om een bepaald netwerk te bereiken.
- Na aanpassing combineert A deze tabel vervolgens met zijn eigen tabel, zodat er een gecombineerde tabel ontstaat.
- De gecombineerde tabel kan enkele dubbele gegevens bevatten. In de bovenstaande afbeelding bevat de gecombineerde tabel van router A de dubbele gegevens, zodat alleen de gegevens worden bewaard die de laagste kosten met zich meebrengen. A kan de gegevens bijvoorbeeld op twee manieren naar netwerk 1 sturen. De eerste, die geen volgende router gebruikt, dus het kost één hop. De tweede vereist twee hops (A naar B, dan B naar Netwerk 1). De eerste optie heeft de laagste kosten, daarom wordt deze behouden en de tweede wordt geschrapt.
- Het proces van het maken van de routeringstabel gaat door voor alle routers. Elke router ontvangt de informatie van de buren en werkt de routeringstabel bij.
De definitieve routeringstabellen van alle routers worden hieronder gegeven:
