Routeringsalgoritme
Een routeringsalgoritme is een methode die gehanteerd wordt door de netwerklaag van een computer wanneer er data verstuurd moet worden naar een andere computer. Deze methode is nodig omdat de communicatie tussen twee computers over een netwerk vaak gebruikmaakt van verschillende tussenstations(routers). Om te kunnen beslissen via welke route de communicatie het beste (snelst, veiligst, etc.) verloopt heeft men routeringsalgoritmen nodig. De enige uitzondering op het gebruik van routeringsalgoritmen is bij een broadcast binnen hetzelfde netwerk. Wanneer een broadcast ook een ander netwerk aandoet dan datgene vanwaar het verstuurd wordt zijn er opnieuw routeringsalgoritmen nodig.
Statische en Dynamische Routeringsalgoritmen[bewerken | brontekst bewerken]
Routeringsalgoritmen kunnen opgedeeld worden in twee categorieën, statische en dynamische algoritmen.
Statische Algoritmen[bewerken | brontekst bewerken]
Bij statische routeringsalgoritmen wordt de route die een pakket moet volgen om van verzender naar ontvanger te geraken op voorhand berekend. Ze worden vaak gebruikt bij login-sessies en houden geen rekening met bepaalde parameters die de gekozen route kunnen beïnvloeden zoals congestie. Statische routering wordt ook wel niet-adaptieve routering, sessieroutering of virtueel circuit genoemd.
Dynamische Algoritmen[bewerken | brontekst bewerken]
Bij dynamische routeringsalgoritmen wordt de route die een bepaald pakket moet volgen berekend aan de hand van bepaalde parameters die invloed hebben op de functionaliteit van de verbinding. Deze parameters zijn onder andere congestie, afstand, reistijd en verandering in topologie van het netwerk.
Eigenschappen van Routeringsalgoritmen[bewerken | brontekst bewerken]
Correctheid[bewerken | brontekst bewerken]
Wanneer er een route wordt berekend tussen een verzender en een ontvanger dan moeten beide ook zijn opgenomen als start- en eindpunt van deze route. Als dat niet zo is dan zal er geen correcte verbinding tot stand gebracht worden.
Eenvoud[bewerken | brontekst bewerken]
Het spreekt voor zich dat er steeds getracht wordt om de eenvoudigste route te nemen en zo geen overbodig dataverkeer te gaan genereren op datalijnen die niet noodzakelijk zijn in de opstelling.
Robuustheid[bewerken | brontekst bewerken]
Wanneer grotere netwerken online gaan moet men er zeker van kunnen zijn dat ze jarenlang meegaan en allerlei problemen zoals het uitvallen van hops en overvloedig dataverkeer aankunnen.
Stabiliteit[bewerken | brontekst bewerken]
Een stabiel routingsalgoritme brengt evenwicht in een netwerk.
Rechtvaardigheid en Optimalisering[bewerken | brontekst bewerken]
Deze waarden worden tegelijk behandeld omdat ze zowel vanzelfsprekend als moeilijk te combineren zijn. Wanneer twee datalijnen voor een gedeelte samenlopen is het een hele klus om beide verbindingen gelijk te behandelen terwijl er gestreefd wordt naar optimale bandbreedte voor iedere verbinding apart.
Het Optimaliteitsbeginsel[bewerken | brontekst bewerken]
Ieder routeringsalgoritme maakt gebruik van het optimaliteitsbeginsel. Dit stelt dat wanneer een router Y op het ideale pad ligt tussen de routers X en Z, het ideale pad van Y naar Z ook via ditzelfde pad verloopt. Wanneer we vanuit dit optimaliteitsbeginsel kijken naar alle routers in een netwerk zien we dat dit een boomstructuur vormt met de bestemming als wortel, deze boomstructuur wordt ook wel de Sink Tree genoemd. Het is voor alle routingsalgoritmen de bedoeling om de Sink Tree te zoeken voor iedere router en deze vervolgens te gebruiken.
De Routeringsalgoritmen[bewerken | brontekst bewerken]
| Klasse | Naam |
|---|---|
| Statisch | Shortest Path Routing (vb. Dijkstra) |
| Flooding | |
| Selective Flooding | |
| Dynamisch | Distance Vector Routing (Bellman-Ford-routeringsalgoritme, Ford-Fulkerson-algoritme) |
| Link State Routing | |
| Hierarchical Routing |
Shortest Path Routing[bewerken | brontekst bewerken]
Shortest Path Routing (Kortste Pad Routering) is een veelvuldig gebruikte techniek omdat hij vrij eenvoudig te implementeren en te begrijpen valt. Het algoritme kan een aantal factoren gebruiken om het kortste pad te bepalen tussen twee nodes. Eerst kan het algoritme rekening houden met het aantal hops die nodig zijn om naar de bestemming te geraken, hoe minder routers er gepasseerd moeten worden, hoe korter het pad. Er kan ook rekening gehouden worden met de geografische afstand tussen de verschillende nodes om het pad te berekenen. Andere factoren die mee in rekening gebracht kunnen worden zijn de bandbreedte, congestie, kosten en vertraging. Een veelgebruikte methode van de Kortste Pad Routering is de methode van Edsger Dijkstra.
Flooding[bewerken | brontekst bewerken]
Bij Flooding wordt ieder pakket dat bij een router aankomt doorgestuurd over alle datalijnen die verbonden zijn met die router behalve de datalijn vanwaar het pakket binnenkwam. Deze methode zou zonder inperkingen de pakketten oneindig veel keren door het netwerk blijven sturen. Een van deze inperkingen is een hopteller die meegestuurd wordt vanuit de bron en na elke hop verlaagd wordt. De hopteller wordt dan geïnitialiseerd op het aantal hops dat gepasseerd moet worden voordat de bestemming bereikt kan worden of als men dat niet weet op de diameter van het netwerk. Als de hopteller nul is dan wordt het pakket door alle routers weggeworpen.
Selective Flooding[bewerken | brontekst bewerken]
Bij deze methode wordt de impact van Flooding op het hele netwerk verlaagd door elk inkomend pakket enkel door te sturen over de datalijnen die ongeveer in de richting van de bestemming lopen.
Distance Vector Routing[bewerken | brontekst bewerken]
Bij routing met Distance Vector houdt iedere router een tabel bij met twee gegevens voor iedere andere router in het netwerk. Enerzijds de datalijn die best gekozen wordt voor communicatie met de router en anderzijds de afstand tot de router. Afstand kan ook hier weer verschillende betekenissen hebben zoals aantal hops, geografische afstand of reistijd. De tabel wordt steeds vernieuwd met informatie van de buren van de router. Wanneer de afstandsmaat tijd bedraagt kan de router zijn eigen tabel vernieuwen door ECHO-pakketten te sturen naar de buren.
Link State Routing[bewerken | brontekst bewerken]
Link State Routing is een geoptimaliseerd algoritme van Distance Vector Routing. Het principe van deze routing kan in 5 stappen worden samengevat.
- Alle aangrenzende routers vinden en de netwerkadressen verzamelen;
- De afstand en andere parameters met betrekking tot de buren meten;
- Alle informatie samenbrengen in een pakket;
- Het informatie-pakket versturen door het netwerk;
- Het kortste pad berekenen op basis van al deze informatie naar alle andere routers.
Om de berekening van het kortste pad te maken kan er gebruikgemaakt worden van een kortstepadalgoritme.
Hierarchical Routing[bewerken | brontekst bewerken]
Wanneer er gewerkt wordt met grote netwerken zullen er ook meer informatiepakketten verstuurd worden tussen de routers en de routingtabellen groeien navenant. Dit is van negatieve invloed op de bandbreedte van het netwerk. Om dit probleem op te lossen maken we gebruik van Hierarchical Routing(Hiërarchische Routering). Met dit algoritme houdt elke router enkel rekening met de routers die in dezelfde zone liggen en negeert alle andere routers. Er is nog maar één tabelwaarde nodig om naar een andere zone te geraken in plaats van tientallen voor elke router die daar aanwezig is.