Hoorcollege 13
Distance vector Algoritme:
Elke router houdt een tabel bij met afstand(bv router x bereiken via 5 stappen) tot andere routers
(en via welke). Tabellen worden geüpdate door informatie met buren uit te wisselen. Tabellen
worden telkens opnieuw uitgerekend. Reageert snel op verbeteringen, reageert langzaam op
verslechteringen (link uitval). Gedecentraliseerd algoritme (geen globale kennis van netwerk),
routers weten niet precies hoe netwerk eruit zien, wel wie hun buren zijn en de afstanden. Gebruikt
in RIP (Routing Information Protocol) RFC 1723.
Algoritme reageert op twee gebeurtenissen:
- Afstand tot een buur verandert
- Nieuwe lijst ontvangen van een buur
Bereken op grond van de nieuwe informatie de minimale afstand tot alle nodes in het netwerk. Als
de lijst veranderd is, stuur hem dan naar al je directe buren. Informatie propageert aan de hand van
veranderingen. Alleen informatie van de directe buren wordt gebruikt. Wanneer er geen
veranderingen optreden in een node slaapt het algoritme in deze node.
Belangrijk bij dit algoritme is dat je het pad kan splitsen in 2
kostencomponenten. Namelijk de afstand van jouw
router(knoop X) tot je buur (knoop V). Plus de afstand met het
kortste pad van jouw buur naar de bestemmingsknoop. Als je
wilt weten wat jouw kosten zijn om van jouw knoop( knoop X)
naar knoop Y, dan is dat de kosten van jouw naar je buur, en
van je buur naar knoop Y. Hierbij kijk je wat het kortste pad is wat
je kan vinden op basis van de informatie via je buren. Buur V kan
bijvoorbeeld zeggen, ik kan in dvy, knoop Y bereiken. Knoop W kan
zeggen dat hij Y kan bereiken in dwY. Stel dvy is kosten 3 en dwY is
kosten 6, kosten van X naar V is 7 en kosten X naar W is 3, dan kies
je voor het pad via buur W want daar zijn de kosten het minst.
Algoritme in node x:
Dx(y) is de schatting die x heeft over de kortste afstand tot y. Distance vector Dx is de vector van
afstanden die x heeft. Buren wisselen af en toe distance vectoren uit. Node x begint als volgt:
- Als je nog niks weet over afstanden met buren: Dx (y) = c(x, y) als y een buur van x is
- Als het geen vuur is dan Dx (y) = ∞ anders
- Alle buren van hun buren is afstand oneinding Dw (y) = ∞ voor al zijn buren w
Stuur jouw DV naar al je buren. Herberekening na ontvangst van DV of na wijziging van c(x, y):
Dx (y) minv c(x, v) + Dv (y) voor alle y ∈ N (N staat voor verzameling knopen in netwerk, en Y
behoort daar bij)
Als je eigen DV (distance vector) verandert, stuur hem dan naar de buren.
, Voorbeeld: We hebben netwerk met x, y & z. Als je begint ga
je als X zeggen: ik kan mijn directe buren bereiken in kosten
2 naar Y en kosten 7 naar Z en kan mezelf in kosten 0
bereiken. Dan ga je je tabel invullen. Dit doet Y en Z ook.
Deze informatie ga je vervolgens naar je buren sturen. Deze
worden ingevuld in de tabel in de afzonderlijke knopen.
Hierna ga je kijken of je die informatie kan gebruiken om
mijn paden te verbeteren. Waar je eerst dacht dat het bij
tabel Z, van X naar Z kosten 7 waren, blijkt dit nu maar 3 te
zijn. Dit komt omdat je van X via Y naar Z kan gaan en de
kosten maar 3 bedragen. De laatste 3 tabellen zijn nu klaar
want welke router is nogmaals berekenen en de kosten
kunnen niet meer lager.
Verslechteringen in Distance Vector:
Verslechteringen werken heel langzaam door en kunnen tot lussen
in de route leiden. In voorbeeld is X naar Z kosten 5 dus al het
verkeer zal via boven geleid worden. Stel verbinding tussen X en Y
wordt ineens heel slecht en kosten worden 60. Y zal het
doorhebben dan verbinding naar X 60 kost ipv de oorspronkelijke
4. Ik ga nu kijken wat mijn kortste pad is naar X. Hij ziet dat via Z
versturen naar X maar kosten 6 heeft, dus al het verkeer van Y gaat
vanaf nu via Z. Maar Z ziet dat om dit bericht naar X te sturen gaat dit via Y omdat dit in de tabel
staat. Waarbij Y weer zegt dat het via Z moet enzovoort. Er ontstaat ping pong effect. Het duurt erg
lang voordat de nieuwe informatie bekend is bij Z dat de lijn tussen X en Y veel duurder is geworden.
De tabellen van de knopen zijn bij ieder knoop anders gevuld met data en de data komt niet
overeen. Zodra dit allemaal rechtgetrokken is weten alle knopen weer wat de situatie is bij elke
buur.
De vorige berekening heeft tot gevolg dat pakketten tussen y en z gaan pingpongen. Gedeeltelijke
oplossing:
- Als Z’s route naar x via y loopt, vertelt hij aan y dat zijn afstand tot x oneindig is.
- Zodat y berichten naar x niet naar Z stuurt Z moet dan een andere route naar x vinden (in dit
geval rechtstreeks), (Poisoned reverse).
- Op deze manier voorkom je pingpongen, dit lost het probleem helaas niet altijd op.
In het Internet zijn teveel routers. Routeringstabellen worden te groot en algoritmes duren te lang.
Sommige netwerkbeheerders willen eigen algoritmes bepalen, wat je gaat zien is Hiërarchische
routering waarbij je het in lagen opdeelt en op elke laag het op een andere manier doet. Oplossing:
- Deel Internet in regio’s in (Autonome Systemen)
- Binnen AS kun je zelf bepalen welk eigen routeringsalgoritme je draait
- Tussen de AS gatewayrouters (routering tussen de verschillende Autonome Systemen te
doen.
- Routers in AS kennen alleen gateways en eigen routers:
o maar niet routers in andere AS
Distance vector Algoritme:
Elke router houdt een tabel bij met afstand(bv router x bereiken via 5 stappen) tot andere routers
(en via welke). Tabellen worden geüpdate door informatie met buren uit te wisselen. Tabellen
worden telkens opnieuw uitgerekend. Reageert snel op verbeteringen, reageert langzaam op
verslechteringen (link uitval). Gedecentraliseerd algoritme (geen globale kennis van netwerk),
routers weten niet precies hoe netwerk eruit zien, wel wie hun buren zijn en de afstanden. Gebruikt
in RIP (Routing Information Protocol) RFC 1723.
Algoritme reageert op twee gebeurtenissen:
- Afstand tot een buur verandert
- Nieuwe lijst ontvangen van een buur
Bereken op grond van de nieuwe informatie de minimale afstand tot alle nodes in het netwerk. Als
de lijst veranderd is, stuur hem dan naar al je directe buren. Informatie propageert aan de hand van
veranderingen. Alleen informatie van de directe buren wordt gebruikt. Wanneer er geen
veranderingen optreden in een node slaapt het algoritme in deze node.
Belangrijk bij dit algoritme is dat je het pad kan splitsen in 2
kostencomponenten. Namelijk de afstand van jouw
router(knoop X) tot je buur (knoop V). Plus de afstand met het
kortste pad van jouw buur naar de bestemmingsknoop. Als je
wilt weten wat jouw kosten zijn om van jouw knoop( knoop X)
naar knoop Y, dan is dat de kosten van jouw naar je buur, en
van je buur naar knoop Y. Hierbij kijk je wat het kortste pad is wat
je kan vinden op basis van de informatie via je buren. Buur V kan
bijvoorbeeld zeggen, ik kan in dvy, knoop Y bereiken. Knoop W kan
zeggen dat hij Y kan bereiken in dwY. Stel dvy is kosten 3 en dwY is
kosten 6, kosten van X naar V is 7 en kosten X naar W is 3, dan kies
je voor het pad via buur W want daar zijn de kosten het minst.
Algoritme in node x:
Dx(y) is de schatting die x heeft over de kortste afstand tot y. Distance vector Dx is de vector van
afstanden die x heeft. Buren wisselen af en toe distance vectoren uit. Node x begint als volgt:
- Als je nog niks weet over afstanden met buren: Dx (y) = c(x, y) als y een buur van x is
- Als het geen vuur is dan Dx (y) = ∞ anders
- Alle buren van hun buren is afstand oneinding Dw (y) = ∞ voor al zijn buren w
Stuur jouw DV naar al je buren. Herberekening na ontvangst van DV of na wijziging van c(x, y):
Dx (y) minv c(x, v) + Dv (y) voor alle y ∈ N (N staat voor verzameling knopen in netwerk, en Y
behoort daar bij)
Als je eigen DV (distance vector) verandert, stuur hem dan naar de buren.
, Voorbeeld: We hebben netwerk met x, y & z. Als je begint ga
je als X zeggen: ik kan mijn directe buren bereiken in kosten
2 naar Y en kosten 7 naar Z en kan mezelf in kosten 0
bereiken. Dan ga je je tabel invullen. Dit doet Y en Z ook.
Deze informatie ga je vervolgens naar je buren sturen. Deze
worden ingevuld in de tabel in de afzonderlijke knopen.
Hierna ga je kijken of je die informatie kan gebruiken om
mijn paden te verbeteren. Waar je eerst dacht dat het bij
tabel Z, van X naar Z kosten 7 waren, blijkt dit nu maar 3 te
zijn. Dit komt omdat je van X via Y naar Z kan gaan en de
kosten maar 3 bedragen. De laatste 3 tabellen zijn nu klaar
want welke router is nogmaals berekenen en de kosten
kunnen niet meer lager.
Verslechteringen in Distance Vector:
Verslechteringen werken heel langzaam door en kunnen tot lussen
in de route leiden. In voorbeeld is X naar Z kosten 5 dus al het
verkeer zal via boven geleid worden. Stel verbinding tussen X en Y
wordt ineens heel slecht en kosten worden 60. Y zal het
doorhebben dan verbinding naar X 60 kost ipv de oorspronkelijke
4. Ik ga nu kijken wat mijn kortste pad is naar X. Hij ziet dat via Z
versturen naar X maar kosten 6 heeft, dus al het verkeer van Y gaat
vanaf nu via Z. Maar Z ziet dat om dit bericht naar X te sturen gaat dit via Y omdat dit in de tabel
staat. Waarbij Y weer zegt dat het via Z moet enzovoort. Er ontstaat ping pong effect. Het duurt erg
lang voordat de nieuwe informatie bekend is bij Z dat de lijn tussen X en Y veel duurder is geworden.
De tabellen van de knopen zijn bij ieder knoop anders gevuld met data en de data komt niet
overeen. Zodra dit allemaal rechtgetrokken is weten alle knopen weer wat de situatie is bij elke
buur.
De vorige berekening heeft tot gevolg dat pakketten tussen y en z gaan pingpongen. Gedeeltelijke
oplossing:
- Als Z’s route naar x via y loopt, vertelt hij aan y dat zijn afstand tot x oneindig is.
- Zodat y berichten naar x niet naar Z stuurt Z moet dan een andere route naar x vinden (in dit
geval rechtstreeks), (Poisoned reverse).
- Op deze manier voorkom je pingpongen, dit lost het probleem helaas niet altijd op.
In het Internet zijn teveel routers. Routeringstabellen worden te groot en algoritmes duren te lang.
Sommige netwerkbeheerders willen eigen algoritmes bepalen, wat je gaat zien is Hiërarchische
routering waarbij je het in lagen opdeelt en op elke laag het op een andere manier doet. Oplossing:
- Deel Internet in regio’s in (Autonome Systemen)
- Binnen AS kun je zelf bepalen welk eigen routeringsalgoritme je draait
- Tussen de AS gatewayrouters (routering tussen de verschillende Autonome Systemen te
doen.
- Routers in AS kennen alleen gateways en eigen routers:
o maar niet routers in andere AS
