Datacommunicatie in informatica/Routing

Inleiding

Wat is routing?

Routing is een verzameling van methodes om het pad te bepalen dat een datapakket dient te volgen in een netwerk om zijn bestemming te bereiken.

Routing-componenten

Routing bestaat uit twee basisactiviteiten:

• Bepaling optimale route.

Routing-protocollen maken gebruik van metrieken (bijv. bandbreedte) om het optimale pad naar een ontvanger te bepalen. Routing-protocollen houden ook routing-tabellen bij waarin de routing-informatie wordt opgeslagen. Om de routing-tabellen up-to-date te houden sturen routers regelmatig update messages naar elkaar. Soms kan een de optimale route een statische route zijn (bijvoorbeeld op een thuiscomputer zal alle data gerouteerd worden naar de interface verbonden met het Internet), in dit geval wordt een statische routingtabel gebruikt en worden geen berichten met betrekking tot de routering uitgewisseld.

• Het versturen van datapakketten door het netwerk (packet switching)

Een host wil data versturen naar een ontvanger. De host zoekt het adres van de volgende host/router in het pad en stuurt het pakket naar het MAC-adres van de volgende host/router. Het netwerkadres (OSI laag 3) is dat van de uiteindelijke ontvanger. De router bekijkt het layer 3 destination address en beslist of hij weet wat de volgende hop is of niet. Indien hij zelf eigenaar is van het IP-adres in kwestie, zal hij het bericht natuurlijk niet doorsturen. Indien hij een route kent, zal hij het uitgepakte IP-pakket terug in een layer 2 (bvb ethernet)-frame stoppen met het destination MAC-adres van de volgende hop (dit kan terug een router zijn of de ontvanger). Dus: het MAC-adres wijzigt tussen verschillende hops, het netwerkprotocoladres blijft altijd ongewijzigd. Dit is natuurlijk zo omdat routers op laag drie van het OSI-model werken.

Routing-algoritmen

Kenmerken van routing-algoritmen

• Optimaliteit: mogelijkheid van het algoritme om de beste route te kiezen.
• Eenvoud en lage overhead: algoritme moet zo simpel mogelijk zijn, efficiënt werken.
• Robuustheid en stabiliteit: in geval van hardwareproblemen, hoge load, enz.
• Convergentie: alle routers hebben alle routing-info verwerkt, moet snel gebeuren (anders gevaar voor loops)
• Flexibiliteit: snel aanpassen aan veranderende netwerkomstandigheden (bvb. down gaan van een link).

Typen routing-algoritmen

• Statisch - dynamisch

Statische routes worden ingesteld door de netwerkbeheerder en blijven ongewijzigd tot de netwerkbeheerder ze wijzigt. Gebruik: kleine, simpele netwerken.

Dynamische routes vangen veranderingen in het netwerk op door inkomende routing update messages te analyseren. Gebruik: grote netwerken, netwerken die regelmatig wijzigen.

• Single-path - multipath

Sommige routingprotocollen laten multiplexering van verkeer toe over meerdere lijnen.

Voordelen: betere throughput en betrouwbaarheid.

• Flat - hierarchical

Bij flat routing zijn alle routers peers van elkaar.

Bij hierarchical routing vormen sommige routers een backbone. Pakketjes van non-backbone routers reizen dan naar de backbone routers. Ze gaan zo verder over de backbone tot ze aankomen bij het doelnetwerk. Daar gaan ze van de backbone router door één of meerdere non-backbone routers tot aan hun uiteindelijke eindbestemming.

• Host-intelligent - router-intelligent

Host-intelligent: De bron host bepaalt de volledige route. Routers zijn in deze situatie enkel store-and-forward devices.

Router-intelligent: Routers bepalen het path door het netwerk.

• Intradomain – interdomain

Routing binnen een domain of tussen domeinen.

• Link-state – distance vector

Link-state: routing informatie wordt naar alle nodes in het internetwerk verzonden. Vb. OSPF

Voordeel: minder vatbaar voor loops dan distance vector algoritmen.

Nadeel: meer CPU kracht en geheugen nodig.

Distance-vector: routing informatie (volledige routing tabel) wordt enkel naar aangrenzende routers verstuurd. Vb. RIP

• Metrics

Metrics worden gebruikt door routing algoritmen om de beste route te kunnen selecteren.

Een of meerdere van volgende metrics kunnen worden gebruikt:

• Path length: meest voorkomende metric, bvb. hop count -> aantal hops (routers) tussen source en destination.
• Reliability: beschikbaarheid van een netwerk link, sommige links gaan sneller down dan andere.
• Delay: tijd nodig om een pakket van source naar destination te krijgen.
• Bandwith: de capaciteit van een netwerk link.
• Load: de load op een router.
• Communication Cost: public lines kosten geld om te gebruiken (beter over eigen lijnen sturen).

Netwerkprotocollen

• Routed protocol: protocollen die geroutet worden, worden getransporteerd door een routing-protocol en zijn netwerkprotocollen.

Vb. IP, IPX, AppleTalk.

• Routing-protocol: gebruikt tussen routers om routing tables op te bouwen of aan te passen.

Vb. RIP, OSPF, IGRP, EIGRP, EGP, BGP.

RIP

Routing information protocol version 1
Is een distance-vector gebaseerd op het bellman-ford algoritme.
Bij dit UDP(port 520) gebaseerd protocol dat de volledige routing tabel broadcasts uit al zijn active interfaces dit elke 30 seconden. We maken bij RIP gebruik van HOP count (METRIC) om te bepalen wat de beste weg is naar een netwerk, met hierbij rekening houdend dat de maximale hop count 15 bedraagt.

Dit werkt echter zeer goed in kleine netwerkjes met weinig routers geïnstalleerd, maar is uitermate niet geschikt voor grote netwerken.

RIP versie 1 gebruikt "classful routing" d.w.z. dat alle netwerkapparaten hetzelfde subnet mask moeten hebben.
Dit omdat rip geen informatie verzendt met de subnetinformatie in verwerkt, RIP v2 doet dit wel en is dus "classless".

Nadeel:

• Enorm verbruik van CPU of bandbreedte
  
• Trage convergentie tijd wat aanleiding geeft tot routing tabellen die niet up-to-date geraken
  

Wanneer routers niet gelijktijdig de nodige informatie ontvangen of geüpdatet worden, kunnen er routing loops ontstaan. Hier spreken we van "counting to infinity", veroorzaakt door de broadcasts van het protocol

oplossing:

• Maximum HOP count:

15 hops is de maximale hop count bij het RIP protocol, m.a.w. na 15 routing loops zal het packet verdwijnen.

• Split Horizon:

Dit routing informatie kan niet meer verzonden worden langs de interface waar de routing informatie vandaan kwam.

• Route poisoning:

• Hold down Timers:

RIP maakt gebruik van verschillende timers:

• Route update timer: bepaalt wanneer de routing tabel zal verzonden worden (30 seconden).
  
• Route invalid timer: bepaalt de tijd die moet verstrijken voordat een route onbruikbaar wordt (180 seconden). Wanneer de route onbruikbaar is geworden zal een router dit laten weten aan al zijn buur routers.
• Hold down timer: Een router zal in Hold down status gaan wanneer hij een packet ontvangt met een route die onbereikbaar is deze route informatie word dan onderdrukt en niet verzonden. De router zal deze status aanhouden totdat hij een update packet ontvangt met een betere hop count (METRIC) of totdat de hold down timer verlopen is (180 seconden).
  
• Route flush timer: Bepaalt de tijd tussen wanneer een route onbruikbaar is geworden en wanneer deze wordt verwijderd uit de routing tabel (240 seconden). Wanner de route verwijderd zal worden van de routing tabel zal de router eveneens laten weten aan al zijn buur routers.

Routing information protocol version 2

Cisco commands:

• controleren van de routing tabel: show ip route
  

IGRP

Interior gateway routing protocol.
Dit is een distance-vector protocol.
Bij dit protocol dat de volledige routing tabel broadcasts uit al zijn active interfaces, maken we gebruik van bandbreedte en vertraging (samengestelde METRIC) om te bepalen wat de beste weg is naar een netwerk, met hierbij rekening houdend dat de maximale hop count 255 bedraagt.
Als metric kan ook gebruik gemaakt worden van load, MTU(maximum transfer unit) maar dit is niet default. Dit is ontworpen door cisco zelf om de bestaande problemen van RIP te voorkomen.
Omdat dit protocol ontworpen is door cisco kan het alleen gebruikt worden tussen routers van cisco zelf anderen kunnen dit niet gebruiken.
IGRP wordt aangeven met een AS nummer(autonomous system), deze moet bij alle routers gelijk zijn willen zijn IGRP informatie uitwisselen.
Dit protocol werkt echter goed voor grote netwerken met allemaal cisco routers.

OSPF

Inleiding

• OSPF staat voor Open Shortest Path First (RFC2328) en is een IGP (Interior Gateway Protocol).
• OSPF maakt rechtstreeks gebruik van IP via protocol 89.
• Bij OSPF zal de router zelf een route bepalen op basis van de kostprijs.
• OSPF is een Link State protocol.
• OSPF kan overweg met CIDR.
• Routers die OSPF gebruiken en zich in hetzelfde netwerk bevinden wordt het AS (Autonome System) genoemd.
• Elk AS kan in meerdere “areas” opgedeeld worden om de schaalbaarheid te vergroten – men spreekt dan van OSPF Multiple Area – zal bijgevolg een hiërarchische structuur hebben.
• OSPF kan gebruikt worden tussen routers van verschillende merken

Werking

De router zal bij OSPF detecteren welke andere routers er zich op de andere kant van zijn interfaces bevinden. Dit gebeurt door middel van “hello” pakketjes die verstuurd worden, de router (neighbor) die zich aan de andere kant van de interface bevind zal hierop antwoorden. Nu kunnen de 2 routers informatie met elkaar uitwisselen, men zegt dan dat de routers “adjacent” zijn met elkaar. Nu zullen beide routers hun LSA's (Link State Advertisements) uitwisselen met elkaar, zo komt Router A informatie te weten over Router B. Elke router zal de LSA's die hij ontvangt van de andere routers in het netwerk opslaan in een Link State Database (LSDB). Elke router zal ook naast zijn eigen LSA, ook alle ontvangen LSA's doorsturen naar alle andere routers in het netwerk. Na een tijdje hebben alle routers dezelfde LSDB en weten ze hoe de topologie van het netwerk eruitziet. Vanaf dit moment kan de router een routetabel opbouwen door eerst zijn Shortest Path Tree te berekenen met zichzelf als root ervan. Dit gebeurt volgens het SPF (Shortest Path First) algoritme (Dijkstra Algoritme).De Shortest Path Tree zal door de router gebruikt worden om zijn routes in de routetabel te plaatsen.

Eigenschappen

Synchronistatie van de LSADB

• In multi-access netwerken (ethernets) zal één router dmv electie verkozen worden als Designated Router (DR). De DR zal de LSADB bijhouden voor het area waarin hij zich bevindt.
• Er zal ook een Backup Designated Router verkozen worden om bij uitval van de DR niet opnieuw de gehele LSADB op te bouwen. Bij het eventueel wegvallen van de BDR zal er terug een electie plaatsvinden
• Routers die als DR of BDR functioneren, krijgen een hogere CPU load omdat zij alle gegevens moeten ontvangen en terug doorsturen naar de andere routers binnen dezelfde “Area”.
• Alle routers zijn adjacent met de DR en de BDR.
• Het overbrengen van de LSADB naar andere routers gebeurt d.m.v. “flooding”.
• Updates zullen gebeuren van het ogenblik dat er wijzigingen plaatsvinden.
• Diegene met de hoogste ospf priority word verkozen tot DR daarna word er gekeken naar het hoogste ID-address(MAC-address)

Metric

OSPF zal de metric "cost" gebruiken

Areas

• Het AS kan opgesplitst worden in verschillende “Areas”. Dit wordt vooral toegepast in grote netwerken om de “overhead” die gegenereerd wordt door het versturen van de LSA's te beperken. Het verkleint ook de LSADB van de Designated Router.
• Alle routers binnen hetzelfde Area bevatten dezelfde LSADB.

EIGRP

Inleiding

Enhanced Interior gateway protocol is een hybride protocol die zowel van link state als distance vector eigenschappen gebruik maakt. Het is een cicso proprierty protocol d.w.z kan enkel gebruikt worden tussen cisco materiaal. EIGRP maakt o.a gebruik van DUAL (Diffusing Update Algorithm) om te bepalen of een route lussen bevat of lusvrij evenals het bepalen van alternatieve paden zonder dat de router moet wachten op de updates van zijn buren. EIGRP is volledig compatibel met IGRP.

Eigenschappen

• snelle convergentie
• classless routing (ondersteuning van subnets)

BGP

Inleiding

• Het Border gateway Protocol (BGP) is een routing protocol tussen verschillende autonome systemen of inter-autonoom.
• AS (Autonomous system): Een groep van netwerken die als 1 systeem algemeen beheerd/geadministreerd worden.
• Wanneer BGP gebruikt wordt tussen verschillende autonome systemen spreken we van EBGP (Exterior Border gateway protocol), indien BGP gebruikt wordt om routing informatie uit te wisselen binnen het zelfde AS dan spreken we van IBGP (interior Border Gateway Protocol).
• BGP is zeer robuust en schaalbaar omdat het gebruik maakt van verschillende attributen dit om een stabiele routing omgeving en beleid te onderhouden.
• BGP ondersteunt subnetting of is m.a.w. classless

Werking

• Wanneer er veranderingen in de routing tabel worden gedetecteerd zullen de BGP routers de updates naar hun buren met enkel de routes die veranderd zijn versturen.
• BGP verzend geen periodieke informatie zoals bv. RIP (30 sec).
• BGP adverteert enkel de meest optimale weg naar een bestemmingsnetwerk.

Attributen

• Weight:
  

Weight (gewicht) is een cisco gedefinieerd attribuut en is lokaal verbonden aan de router. Dit attribuut wordt niet doorgegeven aan de andere routers.

Wanneer een border router verschillende paden naar eenzelfde netwerk leert zal het pad met het hoogste gewicht verkozen worden.

• Local preference:
  

Het lokale preference attribuut wordt gebruikt om binnen een AS een buitengaande route aan te geven. Dit attribuut wordt meegegeven binnen het lokale AS.

Wanneer 2 border routers zich in hetzelfde AS bevinden en het gewicht attribuut is gelijk dan zal de hoogste local preference aanduiden welk pad verkozen zal worden om een ander AS te bereiken.

• Multi-exit discriminator (MED):
  

MED attribuut of Metric attribuut wordt gebruikt als suggestie naar een extern AS toe om aan te geven wat het beste pad is naar een netwerk hierbij zal de laagste MED bepalend zijn.

Dit attribuut wordt meegegeven binnen het lokale AS.

• Origin:
  

Origin attribuut duid aan hoe BGP aan informatie over een bepaalde route komt. Dit attribuut heeft 3 waarden:

• IGP: route is aangeleerd intern binnen hetzelfde AS
• EGP: route is aangeleerd via EBGP (exterior)
• Incomplete: route is aangeleerd via een onbekende weg (wanneer een route geredistribueerd wordt).
  
  

• AS_path:
  

bij het adverteren van een route zal bij elk AS het number worden bijgehouden

• Next hop:
  

Dit attribuut wordt het IP-adres opgeslagen om de adverterende router te bereiken.

Bij EBGP is dit de connectie tussen de gelijken.

Bij IBGP wordt het next hop address rond gedragen binnen het AS, het is daarom belangrijk om een interior gateway protocol te hebben die next hop informatie kan doorgeven.

• Community:
  

Community attribuut geeft de mogelijkheid tot het op delen in gebieden. bv. public, private

De meest voorkomende community attributen zijn:

• no-export: de route niet doorgeven aan EBGP routers
• no-advertise: de route niet doorgeven naar geen enkele andere router.
• internet: de route doorgeven aan iedereen (the whole internet)
  
  

Pad keuze

Dit is de volgorde waarin BGP een keuze zal maken in het pad:

1) Indien het pad een next hop specificeert die niet bereikbaar is, drop the update.

2) Verkies het pad met het hoogst gewicht.

3) Indien de gewichten gelijk zijn, verkies het pad met de hoogste local preference.

4) Indien de local preferences gelijk zijn, verkies het pad dat word aangeduid door het origin attribuut.

5) Indien geen origin attribuut gevonden wordt, verkies het pad met het kortste AS pad.

6) Indien de AS paden gelijk zijn, verkies het pad met de laagste origin type, hierbij is IGP lager dan EGP enz..

7) Indien de origin codes gelijk zijn, verkies het pad met de laagste MED waarde.

8) Indien de MED waarden gelijk zijn, verkies het extern pad boven een intern pad

9) Indien de paden gelijk zijn, verkies het pad het dichts bij een IGP router.

10)Verkies het pad met het laagste ip-adres, aangegeven door de BGP ID.

OSI

Het OSI-model (of ISO-OSI) is de benaming voor ISO Reference Model for Open Systems Interconnection.

Het OSI-model is een verzameling afspraken over de manieren van communiceren tussen twee of meerdere computersystemen van eventueel verschillende merken. Dit model deelt de communicatie in in zeven lagen. Daarom wordt dit ook wel het Zevenlagenmodel genoemd.

De zeven lagen zijn (van laagste naar hoogste laag):

• Fysieke laag - Spanning (volt) en stroomsterkte (ampère), timing, medium (ook wel Fysische laag).
• Datalinklaag - Foutcorrectie, flow control
• Netwerklaag - Adressering, routing
• Transportlaag
• Sessielaag - Dialog control, token management
• Presentatielaag - Datastructuur abstraheren
• Toepassingslaag - Het protocol van het gebruikersprogramma

Het OSI-model is in 1977 voor het eerst bedacht, en in 1995 heeft het een herziening ondergaan. Oorspronkelijk waren er ook OSI-protocollen die voldeden aan het OSI-model, maar die waren niet echt succesvol door verscheidene factoren. TCP/IP werd het meest gebruikte protocol, maar voldoet totaal niet aan het OSI-model.

Technisch heeft het OSI-model dus zijn nut verloren, daarom wordt het tegenwoordig alleen nog maar gebruikt als een 'referentiemodel'. Zo schrijft het OSI-model bijvoorbeeld voor dat encryptie dient te gebeuren op de hogere netwerklagen; de verzameling TCP/IP-protocollen echter, een protocolstack uit de praktijk, laat encryptie toe op lagere lagen, zoals IPsec op de netwerklaag, of encryptie voor draadloze netwerken. Hierbij worden de 'lagen' van het OSI-model naast een ander protocol gelegd en bekeken welke componenten van dat andere protocol de functies uit het OSI-model uitvoeren.

De opsomming van de zeven OSI-netwerklagen, aangevuld met hun bijhorende functies, is een klassieke examenvraag op elk examen over computernetwerken. Het volgende ezelsbruggetje maakt het onthouden misschien wat makkelijker: All People Seem To Need Data Processing

of People Do Need To See Pamela Anderson ("A" van "Application" en de "P" van "Physical" in het Engels).

of People Do Not Trust Sales Peoples Advice.

OSI	TCP/IP
Application	Application
Presentation
Session
Transport	Transport
Network	Internetworking
Datalink	Host to Network
Physical