Je leest:

Routing op internet

Routing op internet

Auteur: | 31 oktober 1997

Hoe vindt een bestandje dat ik aanklik de weg naar mijn computer als ik via Internet verbinding heb met een computer in Amerika? Wat is de route geweest en wie bepaalt die route? Wat gebeurt er als onderweg een computer uitvalt? Kan een berichtje verdwalen?

Een computernetwerk is wiskundig gezien een graaf: een verzameling van knopen (de computers) en kanten (de electronische verbindingen ertussen). In het dagelijks leven komen je meer grafen tegen: de NS-plattegrond van Nederland is een goed voorbeeld. De stations zijn de knopen en de spoorverbindingen de kanten. Het vinden van de kortste route tussen twee stations is een wiskundig probleem dat je kunt oplossen met behulp van kennis van de graaf van het NS-net.

Twee standaardvormen van grafen die we tegenkomen bij computernetwerken zijn de ster, die één middelpunt heeft waarmee alle andere knopen verbonden zijn, en de kring, waarin alle knopen met precies twee andere knopen verbonden zijn.

Figuur 1: Een sternet en een kringnet

Ook het internet is een graaf. Elke op het internet aangesloten computer (server) kan verbinding maken met een willekeurig andere computer. Het internet is oorspronkelijk opgezet door het Ministerie van Defensie van de Verenigde Staten. Het heette toen nog het ARPAnet. Toen niet-militaire instellingen toegelaten werden, is de naam veranderd in internet. Vanuit militair oogpunt was het belangrijk dat het ARPAnet onder slechte omstandigheden kon blijven functioneren, zelfs als een paar knopen of kanten er niet meer waren. Deze zogeheten robuustheid was bijvoorbeeld nodig als het netwerk onder vijandelijk vuur zou komen te liggen. Ook in onze moderne wereld haperen computers nog regelmatig: ze raken overbelast of crashen. Het succes van internet is mede te danken aan de robuuste structuur ervan.

Robuustheid

De meest betrouwbare netwerkstructuur is natuurlijk die waarbij elke computer direct met elke andere verbonden is. Het zal echter duidelijk zijn dat dit veel te duur is. Vanuit beheersoogpunt moet de aansluiting van een nieuwe computer juist zo eenvoudig en goedkoop mogelijk zijn. Eén kabel zou eigenlijk voldoende moeten zijn om een nieuwe computer op een bestaand net aan te sluiten. Robuustheid en lage kosten lijken tegenstrijdige eisen.

Voor de gateways van internet zijn de ster- en kringnetwerken niet robuust genoeg. Bij een ster ligt het netwerk plat als de centrale machine uitvalt. De kring is in elk geval bestand tegen het uitvallen van één knoop, maar een tweede uitvaller kan al maken dat de graaf niet meer samenhangend is, dat wil zeggen, uiteenvalt in afzonderlijke stukken die niet meer met elkaar in contact staan.

Als na twee uitvallers de graaf nog samenhangend moet zijn, moeten er minimaal 3 kanten aan een knoop zitten. Hoe zit dit bij n uitvallers? Stel we hebben een graaf met 4 knopen. Hoeveel kanten hebben we minimaal nodig om te zorgen dat na het uitvallen van 2 willekeurige knopen, het overblijvende netwerk nog steeds samenhangend is? En bij 5? En bij 6?

In de praktijk zien we dat een locaal netwerk van een bedrijf of een provider één centrale machine heeft die als poort naar buiten fungeert: deze computer heet een gateway. De gateways zijn op hun beurt in een robuuster netwerk georganiseerd.

Bij het ontwerp van een computernetwerk heb je een grote mate van vrijheid hoe je de verbindingen aanlegt. De geografische omstandigheden zijn niet zo belangrijk, omdat de reistijd de milliseconden niet te boven gaat. De capaciteiten van de gateways (de knopen) zijn veel belangrijker.

Route en afstand

Hoe weet een computer via welke gateways een berichtje verstuurd moet worden? Dit gaat met routeringstabellen: elke computer heeft een tabel met daarin vermeld waar pakketjes met een bepaald achtervoegsel heen moeten. In de routeringstabel staat wat lokaal behandeld dient te worden, en naar welke gateway de rest moet. De gateway heeft op zijn beurt weer een routeringstabel en op een hoger niveau herhaalt hetzelfde zich. De niveau’s kun je grofweg indelen: eigen computer, locaal netwerk, landelijk net, internationaal net. Dit systeem is vergelijkbaar met de post: als de post in het postkantoor verzameld is, wordt de lokale post wordt apart gehouden van de rest. De rest gaat door naar een hoger niveau. De postbode in je eigen stad kent niet alle straten van Parijs, maar een brief daarheen komt toch aan. In de laatste paragraaf van dit artikel staat een voorbeeld van een internet-route van Amsterdam naar Bordeaux. Merk de verschillende Europese landen op die aangedaan worden. Als reiziger zou je zo’n route niet snel kiezen.

Figuur 2: Surfnet, het netwerk van de Nederlandse universiteiten en Hogescholen.

Hoe worden routeringstabellen gemaakt? Belangrijk is dat de route zo kort mogelijk is, maar wat is kort? Voor het internet is niet de geografische lengte van de verbindingen doorslaggevend, maar het aantal tussenstations. Vandaar dat we de afstand tussen twee knopen van internet aangeven in hops. Één ‘hop’ is een sprong van een knoop naar een andere knoop zonder tussenstation (een hop is dus een kant van de internet-graaf). De afstand tussen twee knopen op internet is het kleinste aantal hops dat nodig is voor een route van de ene knoop naar de andere. Voor het bepalen van de kortste weg in een graaf is geen algemene formule. Wel zijn er methoden om dit efficiënt uit te zoeken. Zo’n methode heet een algoritme.

Hoe zou jij zoiets aanpakken? Hoe vind je de korste weg tussen twee gegeven knopen in een graaf? (Een algoritme kun je vinden op internet. Bijvoorbeeld op:http://wan.neep.net/)

Overbelasting

Als een gateway overbelast raakt, raken alle inkomende berichten verloren. Hetzelfde gebeurt bij een crash van een gateway. De laatste doorsturende knoop merkt dit, want elk berichtje dat goed aankomt wordt beantwoordt met een tegenberichtje “ik heb het ontvangen”. Als zo’n bevestiging niet aankomt, dan merkt de laatste doorsturende knoop dit en concludeert dat het pakketje niet aangekomen is. Deze computer zal dan de routeringstabel raadplegen waarin ook alternatieve gateways vermeld staan. Het eerste alternatief uit de routeringstabel wordt gebruikt. Dus bij overbelasting of uitval van een computer ‘weet’ het netwerk toch hoe het berichtje verstuurd moet worden.

Rondzingen

Routeringstabellen zijn niet feilloos. Een pakketje kan verdwalen. Het komt niet op zijn bestemming aan en wordt van de ene computer naar de andere rondgestuurd. Dat zo’n pakketje niet aankomt is niet zo erg, want iemand die het echt nodig heeft trekt wel aan de bel. Maar pakketjes die blijven ‘rondzingen’ kunnen een rampzalige overbelasting van het netwerk veroorzaken. Om dit te voorkomen wordt aan elk pakketje een getal geplakt, het maximale aantal af te leggen hops. Als een pakketje één hop maakt, wordt dit getal door de ontvangende computer met één verlaagd. Als dit getal kleiner dan nul wordt, wordt het pakketje weggegooid door de computer waar het pakketje op dat moment is. Die maximaal af te leggen afstand wordt de levensduur van het pakketje genoemd. Door alle pakketjes een beperkte levensduur mee te geven wordt rondzingen voorkomen.

Traceroute

Er zijn verscheidene programma’s die de internet-route van je eigen computer naar een andere computer bepalen. Je kunt ze vinden op www.softseek.com (zoek naar ‘traceroute’. Eén van die programma’s is CyberKit, gemaakt door Luc Neijens uit België.

Om deze programma’s te gebruiken, heb je een naam nodig van computers elders in de wereld. Achter machinenamen kun je komen door wat te surfen op internet en het computerdeel uit een URL (internet-adres) te nemen. De computernaam is het gedeelte tussen de // en de daaropvolgende / in een URL. Bijvoorbeeld, de URL van Pythagoras is http://www.wins.uva.nl/misc/pythagoras en de naam van de server is dus www.wins.uva.nl.

Dit artikel is een publicatie van Pythagoras (KWG).
© Pythagoras (KWG), alle rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 31 oktober 1997

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.