Computernetwerken III: Reeks A A1. Configuratie van de netwerkinterface – Bridging a. Bespreek alle (ook meer recente) opdrachten, inclusief hun opties en output, die onder Linux voor de configuratie van de netwerkinterface kunnen gebruikt worden, zowel op de subnetwerklaag als op de internetlaag. Behandel eveneens eventuele configuratiebestanden (inclusief locatie en inhoud). Vergeet in het bijzonder de opstartbestanden niet. • Netwerkinterfaces ∗ Dynamisch gecreëerd vanuit de software (bij opstarten of door toepassingsprog (vb PPP)) ∗ Normaal slechts 1 IP-adres per interface ∗ IP-aliasing/virtual hosting → Meerdere IP-adressen worden toegekend aan 1 interface → Toekennen: eth0 xxx.xxx.xxx.xxx eth0:0 xxx.xxx.xxx.xxx eth0:1 xxx.xxx.xxx.xxx ∗ Voorstelling interface: afkorting van de naam (eth, ppp, fddi, tr, lo) + nummer ∗ Loopback interface (lo, 127.0.0.1 (=klasse-A adres)) → Stelt de computer in staat connecties te maken met zichzelf → Nuttig om vb. client-server-programma te testen zonder netwerk te belasten ∗ Gekoppeld aan een device driver → = Besturingssysteemssoftware die speciale functies van de Linux kernel groepeert → Linux omvat verschillende device drivers voor verschillende types netwerkkaarten → Aan elke netwerkinterface is een device driver gekoppeld → Een device driver kan meerdere netwerkinterfaces ondersteunen → insmod (of modprobe) commando - aanvullende of recentere drivers eenmalig laden - vb: insmod 3c90x.o → install commando - Aanvullende of recentere drivers permanent laden - vb: install -m 644 3c90x.o /lib/modules/'uname -r'/kernel/drivers/net ° /lib/…/'uname -r'/…/net: bevat de beschikbare drivers (uname -r = release-nr v/d kernel) → lsmod commando (of /proc/modules) - Toont welke drivers effectief geladen zijn ∗ Dmesg commando (of /var/log/dmesg) → Toont de naam, type, MAC adres en interrupt- en I/O poort bronnen van geïnstalleerde interfaces ∗ Auto probing → Linux kernel tast geheugen en I/O poorten af of er een netwerkkaart is geïnstalleerd → Zorgt ervoor dat het netwerkkaarttype tijdens het opstarten automatisch wordt gedetecteerd ∗ Manueel instellen van een interface → /etc/modules.conf, /etc/conf.modules, /etc/modprobe.conf of 1 v/d conf files in /etc/modprobe.d → Doorgaans enkel wijzigen indien het toestel: - Niet 100%-compatibele klonen bevat - Interface kaarten bevat die men met verschillende device drivers moet aanspreken ° Soms wordt auto probing gestopt als een driver werd gedetecteerd - ISA interface kaarten bevat Thomas Stubbe & Christophe Sysmans
• ifrename (of /etc/modules.conf) ∗ om de defaultnaamgeving van de interfaces (vb eth0) te veranderen • Ifconfig (interface configure) ∗ Voor wireless analoog: iwconfig ∗ IP-adressen configureren → Vb: ifconfig eth0 193.190.172.3 netmask 255.255.192 ∗ Status van een bepaalde interface na te gaan (vb: ifconfig eth0) (instellingen van + verkeer via deze interface) → O.a. IP-adres, broadcast-adres v/h subnet, subnetmasker v/h subnet, het MAC-adres v/d interface,… → Melding indien interface niet herkend, verkeerde driver aanwezig of verkeerd geconfigureerd ∗ Opties (# ifconfig interfacenaam sleutelwoord argument) → Zonder parameters (of /proc/net/dev) - info over alle geconfigureerde interfaces → Alternatief hiervoor: netstat -i commando - de vlaggen B, L, R en U stellen resp. broadcast-adres, loopback interface, running en up voor → ifconfig -a of netstat -ia - Info over alle interfaces (ook niet-actieve) → IP-adres in dotted-decimal notatie, eventueel voorafgegaan door het sleutelwoord inet - Om toekennen van een IP-adres aan een interface → up/down - Activeert of deactiveert een interface (configuratie informatie gaat niet verloren bij down) - down kan ook gebruikt worden om een IP alias te verwijderen → netmask gevolgd door dotted-decimaal adres - Specificeert het subnetmasker → broadcast gevolgd door dotted-decimaal adres - Wordt anders automatisch afgeleid uit IP-adres en subnetmasker ° Als ook subnetmasker niet gegeven: auto gekozen (komt overeen met de klasse v/h IP-adres) → multicast (-multicast om uit te schakelen) - Laadt de interface toe om multicast berichten te versturen en te ontvangen → promisc (-promisc om uit te schakelen) - Schakelt de promiscuous mode in → pointtopoint gevolgd door het adres van de andere kant van de verbinding - Point-to-point verbinding instellen (zoals PPP) ° vb ifconfig ppp0 193.190.88.17 pointtopoint 193.190.88.18 netmask 255.255.255.252 - In praktijk echter meestal specifieke software waardoor dit bijna niet wordt gebruikt ∗ Alternatief (recenter): ip addr → Zonder opties - overzicht alle interfaces + corresponderende MAC en IP-adressen → ip addr add IP-adres/prefix dev naamdeviceX - vb. ip addr add 192.168.134.1/24 dev eth0 - Stelt IP-adres en subnetmasker in van een interface
Thomas Stubbe & Christophe Sysmans
• ifcfg-InterfaceaamX in /etc/sysconfig/network-scripts (Fedora) ∗ vb. ifcfg-eth0 of ifcfg-lo ∗ Maak dit bestand aan indien je niet iedere keer opnieuw dezelfde instelling wilt invullen ∗ vb van inhoud: → DEVICE=eth0 IPADDR=198.258.46.1 NETMASK=255.255.255.192 ONBOOT=yes ∗ Wordt door het opstartscript /etc/rc.d/int.d/network ingelezen ∗ Ifdown xxx/ifup xxx → Om deze interfaces af te sluiten/activeren b. Bespreek het equivalent onder Windows Server, zowel via de Command Prompt, als via de grafische interface. • Grafisch ∗ Plug and Play creëert vr elke netwerkkaart auto een interface (=verbinding) in de map Network Connections → Control Panel -> Network connections ∗ Krijgt standaard de naam Local Area Connection X (1, 2, …) ∗ Rechtermuisknop op interface → Rename - Nieuwe naam toewijzen aan interface → Properties - Hardware/software instellingen van de interface controleren/wijzigen - Configure ° Tabbladen General, Advanced, Driver of Resources (Om vb. de driver aan te passen) - Selecteer Internet Protocol Version 4 (TCP/IPv4) in 'This connection uses the following items' ° Klik Properties -> Use the following IP address aanvinken IP, subnet mask, default gateway, en DNS kunnen ingesteld worden ° IP aliasing Advanced -> IP Settings tabpagina -> Add (zo elke alias toevoegen) → Status - Om het netwerkverkeer te monitoren (duur verbinding + aantal pakketen verstuurd/ontvangen) → Disable - Verbinding verbreken • Command Prompt ∗ netstat → Statistieken over het netwerkverkeer → Opties - -e ° Ethernet-statistieken - -s ° Ook statistieken voor elk van de TCP, UDP, ICMP en IP protocollen - -p <protocol> (met protocol een van de 4 hierboven) ° Statistieken voor het ene opgegeven procol Thomas Stubbe & Christophe Sysmans
∗ ipconfig /all → Toont info TCP/IP netwerkconfiguratie van alle netwerkinterfaces → Handig om problemen op te sporen - vb: als pc geconfigureerd met IP-adres dat kopie is van bestaand IP-adres ° Dan wordt subnetmasker als 0.0.0.0 weergegeven ∗ netsh → Enkel volledig ondersteund indien de Routing and Remote Access service is geactiveerd → Om IP-adres en subnetmasker van een interface te wijzigen - vb netsh interface ip set address "Local Area Connection" static 193.190.170.3 255.255.255.192 → Om een overzicht te bekomen van alle interfaces en hun corresponderende IP-adressen - vb netsh interface ip show ipaddress c. In welke opeenvolgende stappen bepalen een verzameling bridges, die diverse netwerksegmenten tot één enkel subnetwerk groeperen, welke van hun poorten moeten geblokkeerd worden? • Elke verbinding tussen 2 bridges heeft een kost ∗ Kost = getal afhankelijk van 1 of meerdere factoren(omgekeerd evenredig met de performantie) • Elke poort heeft een kost ∗ = De kleinste sommatie van de kost van de verbindingen om de root te bereiken • Werking: ∗ Stap 1: Er wordt 1 rootbridge gekozen → Bridge met laagste prioriteit ∗ STAP 2: Poortkost bepalen → De poortkost is het kortste pad om tot de rootbridge te komen ∗ STAP 3: Rootpoort per bridge bepalen → Dit is de poort met kleinste kost (dus goedkoopste om de root te bereiken) → Elke poort precies één (behalve rootbridge, deze heeft er geen) ∗ STAP 4: Designated poorten bepalen → Ieder segment heeft één designated port → Deze wordt gekozen op basis van cumulatieve Root Path Cost - Beschouw alle poorten verbonden met een segment, en selecteer de poort met de kleinste kost om tot de root te geraken ∗ STAP 5: Blokkeren van de niet-designated- en niet-rootpoorten
Thomas Stubbe & Christophe Sysmans
d. Hoe kun je, via de uitvoer van één enkele opdracht, op een als bridge geconfigureerd Linux toestel op diverse manieren controleren dat de juiste poorten geblokkeerd zijn, en om welke reden de andere poorten geactiveerd moeten blijven? • Commando: brctl showstp
| less/more • Output (vb.)
•
Interpretatie van output: ∗ Rootpoort bepalen: → Bij bridge output staat de index van de rootport → Per interface de designated cost + path cost berekenen - Kleinste is de rootport ∗ Designatedpoort bepalen → De poort waarbij designated bridge = huidige bridge
Thomas Stubbe & Christophe Sysmans
A2. Statische routing a. Bespreek het doel van routing, de werking, en de belangrijkste componenten ervan. Behandel de terminologie en problematiek die het routing proces kenmerkt. • Doel van routing ∗ Aan eindgebruikers de illusie creëren dat ze allen verbonden zijn via één en hetzelfde netwerk, ook al zijn ze fysiek aangesloten op verschillende netwerken met uiteenlopende technologieën. ∗ Het is de gezamenlijke taak van alle routers van het internetwerk om er voor te zorgen dat het bericht doorgestuurd wordt naar een router die zich op het subnetwerk van de eindbestemming bevindt • Werking van routing ∗ 1) Op zoek naar alle regels in routingtabel waar IP-adres v/ bestemming deel uitmaakt van netwerkadres → Prefixlengte: bits IP-adres = bits netwerkadres of IP-adres AND-en met subnetmasker ∗ 2) Kies de meeste specifieke regel die hieraan voldoet (meest aantal bits overeenstemmen) ∗ 3) Kies deze met kleinste metriek ∗ 4) Indien geen gevonden ' ICMP-Destination Unreachable bericht gestuurd naar oorspronkelijke afzender → Internet Control Message Protocol: doel is niet om IP-datagrammen betrouwbaarder te maken maar om afzender op de hoogte te stellen van netwerkproblemen. → ICMP-bericht kan zelf geen ICMP-bericht tot gevolg hebben ' stortvloed vermijden. • Componenten van routing ∗ Gateway (of software router) → = computers die tegelijkertijd deel uitmaken van meerdere LAN en/of WAN netwerken → Zijn bereid zijn om berichten van het enen netwerk naar het andere door te geven. → Gateway-functie zorgt meestal voor zware belasting - meestal complexe bedrijfsystemen als Unix of Windows Server - vaak opteert men voor een (hardware) router ∗ Router (hardware) → Toestel met specifieke hardware/software voor deze taken • Routingproces ∗ Terminologie → Routing - Doorsturen van berichten van ene router naar andere → Hops - De routers die het bericht achtereenvolgend doorloopt om bij zijn bestemming te raken → Hopafstand - Minimum aantal routers nodig om een bericht tussen twee willekeurige toestellen v/h internetwerk te zenden (direct delivery ' hopafstand = 0) → Diameter - Maximale hopafstand in het internetwerk → Routingtabel - Lijst die voor elk netwerk in het internetwerk (waarvan de router zelf geen deel uitmaakt) aangeeft naar welke volgende router (forwarding address) hij het bericht moet doorsturen, en van welke interface hij hierbij gebruik moet maken. Bevat netwerkadres, forwarding address, interface, metriek, lifetime veld.
Thomas Stubbe & Christophe Sysmans
→ Netwerkadres - Unieke identificatie voor elk netwerk in internetwerk, vergezeld van subnetmasker of prefixlengte → Metriek - Getal dat voor elk pad naar een eindbestemming via een bepaalde router de kost aanduidt om die eindbestemming te bereiken (verschillende mogelijkheden om waarde te kiezen: hopafstand, bandbreedte, … ' TOS routing) → Lifetime veld - Houdt bij hoe lang de route als geldig wordt beschouwd → TOS routing - Op basis van het Type Of Service veld in een IP-datagram wordt de juiste berekeningswijze voor de metriek gekozen ∗ Problematiek → Routing loops - Wanneer routingtabellen voor een bepaalde eindbestemming een pad construeren dat terugverwijst naar één van de intermediaire routers v/h pad (gaat door tot levensduur bericht verstreken is). → Black holes - Wanneer een router op het pad naar de eindbestemming niet meer functioneert en dit falen nog niet is opgenomen in de routingtabel van de vorige router op het pad. ° Routingtabellen van alle routers moeten meestal aangepast worden na elke topologiewijziging v/h internetwerk.
b. Vergelijk statische en dynamische routing, zonder in detail in te gaan op specifieke routingprotocollen. • Statische Routing ∗ Netwerkbeheerder maakt de routingtabellen voor elke router manueel aan. ∗ Nadeel: enorm werk + zeer foutgevoelig. Bij elke topologiewijziging moet dit werk opnieuw gebeuren! → Routing loops en black holes • Dynamische routing ∗ Routers communiceren met elkaar d.m.v. routingprotocollen. Alle routers melden (=adverteren) aan alle andere routers met welke netwerken ze rechtstreeks verbonden zijn, en/of welke ze onrechtstreeks kunnen bereiken. Hiermee construeren alle routers hun eigen routingtabel. ∗ Voordeel: configuratie past zichzelf aan bij elke topologiewijziging ∗ Route flapping = bij uitvallen/terugkeren van router wisselen de routers opnieuw routingprotocol berichten uit en wordt er naar oorspronkelijke of nieuwe stabiele toestand teruggekeerd.
Thomas Stubbe & Christophe Sysmans
c. Geef de diverse (inclusief de meest eenvoudige) alternatieven om de routingtabel van niet-routers (o.a. toestellen die slechts op één subnetwerk zijn aangesloten) te configureren. Indien er hiertoe op Linux of Windows bijzondere componenten moeten geïnstalleerd of geconfigureerd worden, bespreek hoe dit moet gebeuren. • Algemeen ∗ Computers binnen hetzelfde subnetwerk → Geen gateway instellen ∗ Andere computers op het internetwerk → Minimum de gegevens bijhouden van de router waaraan hij het bericht moet afgeven • Default Gateway ∗ Hier worden alle berichten standaard naar toe gestuurd ∗ Deze gateway verdeelt de berichten verder over het internetwerk ∗ Vereenvoudigd de configuratie van niet-routers aanzienlijk ∗ Niet optimaal voor subnetwerken met meerdere routers -> host routing • Host routing ∗ Windows Server en Linux laten toe dat afh. van de eindbestemming een andere router als intermediaire bestemming ingesteld wordt dan de default gateway ∗ Host routing: net als op de routers, wordt een routingtabel opgebouwd op werkpost (nietrouter) zelf • Statisch ∗ Computers binnen het subnetwerk → Handmatig alle computers binnen het subnetwerk ingeven ∗ Computers op het internetwerk, niet binnen het subnetwerk → Default gateway instellen → Of per computer de juiste gateway instellen • Dynamisch ∗ Router-discovery met ICMP → Internet Control Message Protocol → 2 soorten ICMP-berichten - ICMP-Router Sollicitation ° Wordt verstuurd naar 224.0.0.2 (multicast adres voor alle routers) ° Om de routers te ontdekken ° Routers hiervoor geconfigureerd sturen periodiek een ICMP-Router Advertisement als reactie Periodiek om te laten weten dat de router nog steeds beschikbaar is - ICMP-Router Advertisement ° Een op deze manier aangeleerde standaardgateway heeft een beperkte lifetime veld (30 min) → Standaard aangeschakeld op Windows - Echter tenzij 'Routing and Remote Access Service' ingeschakeld is genereert Windows Server router geen ICMP-Router Advertisement.
Thomas Stubbe & Christophe Sysmans
∗ ICMP-Redirect berichten → Indien de router merkt dat het verkeer afkomstig is van een computer die de volgende hop rechtstreeks kon bereiken (zie vb p 14-15) dan stuurt hij een ICMP-Redirect bericht → Wijst de computer op een beter alternatief → Computer kan op basis van deze techniek zijn routingtabel optimaliseren → Afgeraden te gebruiken - Gelijk wie kan routingtabellen v/h hele internetwerk in de war sturen (fake ICMPRedirect berichten) - Zo goed als onmogelijk authenticiteit te achterhalen (info in de velden makkelijk te vervalsen) → Zowel Linux als Windows houden hiermee rekening - Echter voegen enkel host routes (routers naar individuele toestellen) toe - Lifetime beperkt tot enkele minuten ∗ Op basis van broadcasts op het subnetwerk → Eavesdropping / wiretapping - Andere toestellen kunnen passief meeluisteren en hun routing tabel aanpassen - Gewone werkposten kunnen hierdoor precies dezelfde info als de routers bezitten - Indien de berichten RIP berichten zijn wordt dit 'Silent RIP' genoemd ° Men kan alle Linux en Windows toestellen voor Silent RIP Configureren Op Linux activeren met routed -q Op windows moet een bijkomende service RIP listener geïnstalleerd worden Add/Remove programs -> Add/Remove Windows components -> Networking Services -> RIP Listener ° Zowel Linux als Windows: luisteren enkel naar RIPv1 berichten • Instellen ∗ Linux → Statisch - Met behulp van de route-opdracht - Zonder parameters: overzicht - Route add -net xxx.xxx.xxx.xxx/XX gw xxx.xxx.xxx.xxx ° Pakketen voor dat ip via de opgegeven gateway versturen - Route add -net xxx.xxx.xxx.xxx netmask xxx.xxx.xxx.xxx dev ethx ° Route add -net xxx.xxx.xxx.xxx/XX dev ethx ook toegestaan ° Indien op het zelfde subnetwerk: geen gateway, maar een interface - Indien je dit niet altijd na elke boot opnieuw wil doen: static-routes bestand in /etc/sysconfig ° Voor elke route: ethx net|host netwerkadres netmask subnetmasker gw gateway - Route add default gw xxx.xxx.xxx.xxx ° Standaard gateway instellen - Route del -net xxx.xxx.xxx.xxx/XX gw xxx.xxx.xxx.xxx om een route te verwijderen ∗ Windows → Route add xxx.xxx.xxx.xxx mask xxx.xxx.xxx.xxx xxx.xxx.xxx.xxx - Het laatste adres (zonder sleutelwoord) is de gateway → Route -p add xxx.xxx.xxx.xxx mask xxx.xxx.xxx.xxx xxx.xxx.xxx.xxx - Optie -p maakt de route persistent (blijvend) → Route delete xxx.xxx.xxx.xxx → Route -f: alle gatewayvermeldingen ineens uit de routingtabellen verwijderen
Thomas Stubbe & Christophe Sysmans
A3. Dynamische routing a. Bespreek het doel en de voordelen van dynamische routing. Behandel de terminologie en de problematiek die dynamische routing kenmerkt. • Doel ∗ Statisch geconfigureerde routers weinig foutbestendig (vb. tijdelijk uitvallen router = wijzigen topologie) → Dynamische invulling routingtabellen is goed alternatief . • Voordelen ∗ Tijdelijk falen van router vlugger vastgesteld + doorgegeven → Routes hebben beperkte lifetime → Continu zenden van berichten tss routers - Formaat en betekenis bepaald door het routingprotocool ∗ Nauwelijks manueel onderhoud (enkel initialisatie v/d router) ' geschikt voor grote internetwerken • Terminologie ∗ Geconvergeerd → Alle routingtabellen correct ingevuld ' internetwerk is geconvergeerd naar stabiele toestand ' optimaal pad voor elke verbinding. ∗ Route flapping → Verbinding/router uitvalt ' routers zenden gewijzigde gegevens onderling door en er wordt terug naar een stabiele toestand gegaan ∗ Convergentieperiode → Tijd nodig om tot stabiele toestand terug te keren nadat router/verbinding uitvalt, hangt af van diverse factoren. • Problematiek ∗ Bijkomend netwerkverkeer (vooral in WAN merkbaar). ∗ Tijdens de onstabiele toestand van het internetwerk (route flapping) kunnen routing loops of black holes voorkomen. → Routing loops - Wanneer routingtabellen voor een bepaalde eindbestemming een pad construeren dat terugverwijst naar één van de intermediaire routers v/h pad (gaat door tot levensduur bericht verstreken is). → Black holes - Wanneer een router op het pad naar de eindbestemming niet meer functioneert en dit falen nog niet is opgenomen in de routingtabel van de vorige router op het pad. ° Routingtabellen van alle routers moeten meestal aangepast worden na elke topologiewijziging v/h internetwerk. b. Beschrijf het routing proces op Internet schaal (inclusief de relatie tot ISPs). • Auonomous Systems (ASs) ∗ Internet = zeer groot internetwerk -> opdelen ASs. ∗ Routers binnen AS wisselen volledige routinginformatie uit met elkaar ∗ AS Border Routers (ASBR) → wisselen die informatie uit met ASBRs v ander AS via verbindingen die tot geen AS behoren (niemandsland of gedemilitariseerde zone) ∗ Elke router behoort tot één AS -> makkelijk voor beheerders.
Thomas Stubbe & Christophe Sysmans
∗ Verschillende ASs wisselen zo weinig mogelijk gedetailleerde info uit → Adresbereiken zoveel mogelijk aggregeren (groeperen)-> Globale adresbereiken → Gedetailleerde structuur binnen een AS verborgen voor ander AS - Route nr geaggregeerd adresbereik = route nr alle subnetten die er deel v uitmaken → Aaneengesluitende blokken adresruimte: als 1 geheel naar andere AS geadverteerd - Grootte routingtabellen beperkt. → Let wel: aggregeren van subnetten enkel mogelijk als de hoogste orde bits van subnetten in AS overeenstemmen en niet voorkomen in een subnet van een ander AS. • Internet Service Provider (ISP) ∗ beheer van routers, netwerken & verbindingen van één AS. ∗ Tier-1 ISPs → Beheren internetwerken met enorme capaciteit, uitstrekkend over alle continenten ∗ Tier-2 ISPs → Meestal beperkt tot 1 land of een deel van een continent → Wisselen dikwijls rechtstreeks data uit met een aantal tier-1 ISPs → Onderling data uitwisselen met andere tier-2 ISPs kan op 2 manieren: - Op regional peering points - Beroep doen (tegen betaling) op diensten van een tier-1 ISP → Verkopen hun diensten door aan tier-3 ISPs ∗ Peering Points/Regional Exchanges → Hier ontmoeten ISP's van verschillende niveau's elkaar → Alle tier-1 ISPs zijn nagenoeg op al deze points aanwezig → Enkel via deze punten kunnen ISPs van lagere niveaus info uitwisselen met tier-1 ISPs ∗ Private peering points → Tier-1 ISPs moeten zoveel info uitwisselen dat ze elkaar ook op deze punten ontmoeten ∗ Internetwerk beheerd door dezelfde ISP vormt één enkel AS.
c. Maak een classificatie van routingprotocollen, volgens twee criteria. Omschrijf de terminologie die je hierbij invoert. Geef ondermeer aan op welk niveau (cfr. deelvraag b) hetzelfde routingprotocol actief kan zijn, en hoe aan schaalbeperking kan worden gedaan. Geef van elke klasse de meest courante vertegenwoordigers. Het is niet de bedoeling in te gaan op een gedetailleerde vergelijking tussen de verschillende klassen en hun specifieke vertegenwoordigers. • Op basis van Routingprotocollen: ∗ Interior Gateway Protocollen(IGP's)/Intradomain routingprotocollen → Opvullen routingtabellen binnen zelfde AS → Berekenen beste route naar om het even welke eindbestemming en verspreiden deze info over alle routers van het AS → Moeten zich enkel richten op construeren van optimale paden met minimale kost → Vertegenwoordigers: - Routing Information Protocol (RIP) - Enhanced Interior Gateway Routing Protocol (E-IGRP) - Open Shortest Path First Protocol (OSPF) - Intermediate System to System Protocol (IS-IS) → Routingdomein: verzameling subnetwerken (binnen één AS) waarin routers onderling de gedetailleerde routinginformatie uitwisselen op basis van hetzelfde IGP (schaalbeperking) - Sommige routers behoren tot verschillende, of zelfs tot alle routingdomeinen en moeten dan ook meerdere IGPs ondersteunen Thomas Stubbe & Christophe Sysmans
∗ Exterior Gateway Protocollen(EGPs)/Inter-domain routingprotocollen → Mogelijk om routing info uit te wisselen tussen verschillende ASs - Maakt verkeer tussen die ASs mogelijk → Enkel voor ASBRs (=AS Border Routers) → Rekening houden met routing policy - Filtert specifiek verkeer (commerciële en politiek bilaterale overeenkomsten tse ISPs) → Vertegenwoordigers: - Exterior Gateway Protocol (EGP) - Gateway to Gateway Protocol (GGP) - Border Gateway Protocol (BGPv4) ° Vereist dat elk AS een uniek autonomous system number heeft (ASN, < 64512) ° Wordt praktisch uitsluitend gebruikt • Op basis van technologie ∗ Distance vector protocollen → Vereist dat een router zijn buren periodiek informeert over topologie veranderingen → Vertegenwoordigers: - BGPv4: Border Gateway Protocol - RIP - EIGRP ∗ Link state protocollen → Elke router construeert een 'map' van de connecties in het netwerk en berekent de beste weg naar elke mogelijke bestemming. De verzameling van de beste paden = routingtabel → Vertegenwoordigers: - OSPF - IS-IS ∗ Deze twee classificaties verschillen in welke routing informatie uitgewisseld wordt en de manier waarop..
Thomas Stubbe & Christophe Sysmans
A4. RIP (Routing Information Protocol) a. Geef een gedetailleerde beschrijving van de werking van RIP. Bespreek de mogelijkheden, beperkingen, en problemen. Bespreek in het bijzonder de gehanteerde metriek, en hoe RIP berichten verpakt worden (cfr. het OSI 7-lagen model). • Werking: ∗ RIP is een interior, distance vector routing protocol ∗ Routers adverteren hun route-vectoren via UDP-pakketten op een broadcast adres → Naar alle routers die op subnetwerk-niveau rechtstreeks te bereiken zijn → Andere routers kunnen zo hun routingtabellen bijwerken → Slaan enkel het pad met de laagste metriek op ∗ Berichten worden periodiek en asynchroon verstuurd → Standaard om de 30 seconden → Eveneens indien network reeds tot een stabiele toestand geconvergeerd is • Metriek: ∗ Standaard wordt de hop afstand gebruikt ∗ Bij ontvangen van advertisement wordt de metriek met 1 verhoogd ∗ Routes met metriek >= 16 worden onbereikbaar beschouwd • Mogelijkheden/beperkingen/problemen: ∗ Maximale diameter internetwerk = 15 → Op voorwaarde dat alle verbindingen een metriek 1 krijgen ∗ Veel bandbreedte verbruikt door de broadcasts bij RIP ∗ Alle mogelijke paden dienen in de routetabbellen opgeslagen te worden → Wordt meestal van afgeweken om routetabellen te verkleinen - Enkel pad met kleinste metriek bijhouden ∗ Trage convergentie bij topologiewijzigingen, 3 oorzaken: → Indien enkel de kleinste metrieken bijgehouden worden, worden meldingen van alternatieve paden met een hogere metriek genegeerd - Metriek van beste route wordt wel verhoogd, indien van de eerste intermediare hop een dergelijke melding ontvangen wordt → Lifetime parameter van RIP routes is standaard 3 minuten - = 6 keer de default periode tussen opeenvolgende advertisements - Route wordt pas verwijderd na vier periodieke advertisements waarbij route metriek van 16 heeft → Doordat routers periodiek en asynchroon adverteren, is er een willekeur in het uitwisselingsproces - Resultaat afhankelijk van de volgorde van verzending
Thomas Stubbe & Christophe Sysmans
∗ Twee problemen: → Count-To-Infinity - Dit komt voor als een router, die merkt dat een verbinding onbeschikbaar geworden is en de metriek dus op oneindig zet, een advertering van een buur ontvangt vooraleer die wijziging kunnen doorgestuurd te hebben. Hierdoor wordt de juist ingestelde metriek vervangen door de vorige metriek + 1, met de adverterende router als volgende hop. Dit proces herhaalt zich bij elke advertentie, waardoor de metriek gestaag toeneemt. Om dit probleem ietwat te reduceren, wordt de maximale metriek vastgelegd op 16, waardoor dit probleem nooit meer dan enkele minuten in beslag zal nemen. - vb. Subnetwerk 3 is onbeschikbaar. Router 2 stelt zijn metriekwaarde voor subnetwerk 3 in op 16. Wanneer router 1 nu een advertisement stuurt voordat router 2 een advertisement stuurt (50% kans) dan zal router 2 merken dat router 1 subnetwerk 3 wel nog kan bereiken en zijn metriekwaarde aanpassen. Hierna zal router 2 een advertisement sturen. Router 1 zal daardoor zijn metriekwaarde voor subnetwerk 3 met 1 verhogen, enz. Na een tijdje (meer dan 3 minuten) zullen beide routers een metriekwaarde 16 hebben voor subnetwerk 3. Pas dan zijn beide routers geconvergeerd naar een stabiele toestand. → Routing Loop - Kan optreden tijdens de convergentieperiode - (in bovenstaand voorbeeld) Berichten voor network 3 worden heen en weer gepingponged tijdens de convergentieperiode ° Stopt indien ttl-veld van IP datagram = 0 - Kan leiden tot overbelasting van het network ° Verlies van pakketten • Verpakking ∗ RIP berichten worden ingekapseld in UDP segmenten (met poortnummers 520) ∗ Pakketten woden niet bevestigd door ontvanger b. Wat wordt bedoeld met reductie van de convergentieperiode (inclusief oorzaken) ? Bespreek de verschillende technieken om dit te verwezenlijken. • Reductie van convergentieperiode ∗ = Verkleinen van de tijd om bij wijzigingen in het internetwerk, opnieuw tot een stabiele toestand te komen. • Oorzaken: ∗ Indien enkel de kleinste metrieken bijgehouden worden, worden meldingen van alternatieve paden met een hogere metriek genegeerd → Metriek van beste route wordt wel verhoogd, indien van de eerste intermediare hop een dergelijke melding ontvangen wordt ∗ Lifetime parameter van RIP routes is standaard 3 minuten → = 6 keer de default periode tussen opeenvolgende advertisements → Route wordt pas verwijderd na vier periodieke advertisements waarbij route metriek van 16 heeft
Thomas Stubbe & Christophe Sysmans
∗ Doordat routers periodiek en asynchroon adverteren, is ere en willekeur in het uitwisselingsproces → Resultaat afhankelijk van de volgorde van verzending • Technieken: ∗ Split horizon → Routers adverteren routes niet meer op het subnetwerk waarlangs ze deze routes vernomen hebben → Vermijdt count-to-infinity en routing loop in situaties waar er slechts één pad bestaat voor elke bestemming → Geen bescherming tegen alle vormen van lussen (reductie van kans fout, maar geen exclusie) → Beperkt de belasting van RIP protocol op het netwerk ∗ Poison reverse → Agressievere variant van Split horizon → Blijft adverteren op alle netwerken, maar vermeldt routes op subnetwerk langs waar ze vernomen zijn met een metriek van 16 → Meer reductie van kans op count-to-infinity en routing (dan bij Split horizon) → Geen beperking van de belastign op het netwerk ∗ Triggered updates → Routers die dit ondersteunen adverteren niet enkel periodiek, maar ook telkens de metriek van een route verandert. → Een triggered update dient enkel de wijziging te adverteren → Als lifetime veld van een route 0 is, wordt deze route bijna onmiddelijk met metriek 16 gebroadcast (na kleine pauze om boardcastlawine te vermijden) - Verkleint de kans op count-to-infinity probleem → Aanzienlijke reductie convergentieperiode → Wel mogelijkheid tot lussen → Meer broadcastberichten ∗ General RIP request → Nieuwe routers kunnen een dergelijke request sturen → Ondersteunende routers beantwoorden met hun volledige routingtabel → Wordt niet gebroadcast, maar gericht gestuurd
c. Bespreek de verschillende verbeteringen van RIPv2 ten opzichte van RIPv1. • Multicasting ∗ Bij RIPv1 worden berichten gebroadcast (want enkel voordeel is bij Silent RIP= passief luisteren naar RIP berichten) maar zorgt voor meer netwerkverkeer ( + alle aangesloten computers moeten broadcastberichten tot op UDP niveau verwerken) ∗ Bij RIPv2 worden berichten gemulticast naar adres 224.0.0.9 (stoort de routers niet) • Subnetmasker binnen route-vectoren: ∗ Bij RIPv1 wordt uitsluitend gebruikt gemaakt van zelfidentificerende adressen (A, B, C) ∗ Bij RIPv1 wordt prefixlengte of subnetmasker niet in de RIPv1 berichten opgenomen ∗ Bij RIPv2 wordt het subnetmasker expliciet mee opgenomen (om CIDR mogelijk te maken) Thomas Stubbe & Christophe Sysmans
• Next-hop veld: ∗ Bij RIPv2 wordt het Next-hop veld gebruikt om het adres van de eerste intermediaire hop aan te duiden → Zo kunnen routers bij ontvangst van een route-vector eerst kijken of de hop niet rechtstreeks te bereiken is → Zo worden dubbele hops vermeden (dus enkel optimale routes) ∗ Bij RIPv1 is deze altijd 0 • Eenvoudige authentificatie: ∗ Bij RIPv1 is er geen beveiligingsmechanisme om authenticiteit van berichten te garanderen ∗ Bij RIPv2 is er ondersteuning voor eenvoudige authenticatie (met wachtwoorden), zoals bv Message Digest 5 (MD5) → Bij authentificatie: eerste 20 bytes na header zijn authentificatiegegevens
Thomas Stubbe & Christophe Sysmans
A5. OSPF a. Geef een gedetailleerde beschrijving van de werking van OSPF, inclusief de diverse mechanismen van berichtenuitwisseling en de OSPF routers met een bijzondere functie, maar zonder in te gaan op de uitwerking van het algoritme van Dijkstra en het concept van OSPF area's. • Algemeen: ∗ OSPF (Open Shortest Path First) is een interior, link state routing protocol ∗ Stuurt informatie over de bereikbare buren (via link state advertisements of LSAs) naar alle routers binnen het netwerk ∗ Berichten: → Niet gebroadcast → Enkel verstuurd bij: - Opstarten van de router - Detectie van wijzing binnen de topologie → Elk bericht dient expliciet bevestigd te worden door de ontvanger - Anders periodiek opnieuw sturen ∗ Autonomous System Border Routers (ASBR) → Zijn routers in het routingdomein, die ook aangesloten zijn op subnetwerken die niet tot het domein behoren → Vermelden in hun LSA ook routes buiten het routing domein die via hen bereikbaar zijn (rechstreeks en onrechtstreeks) - = external route LSAs - Dikwijls geaggregeerd tot één enkele default route LSA • Werking: ∗ Alle routers compileren apart een link state database (LSDB): → Bevat alle toegankelijke subnetwerken → Elke LSA bevat een lolly number om onderscheiden te kunnen worden van nieuwere gegevens → Bevat 1 LSA per router - Daarom per router een router ID ° = unieke ID in hele AS, identificeerd een router (en niet een interface) → Na synchronisatie bevatten alle routers dezelfde LSDB (1) ∗ Na compilatie berekent elke router op basis van de LSDB een routingtabel → Meestal met behulp van het algoritme van Dijkstra, om de paden met laagste metriek te berekenen per subnetwerk → Met deze paden wordt een shortest path first (SPF) tree opgebouwd (met zichzelf als root) - Tree bevat pad met minimale kost voor elk netwerk en elke router als eindbestemming → Hieruit wordt tenslotte het routingtabel afgeleid ∗ Synchronisatie van LSDB’s (1), 2 fasen: → Fase 1: Flooding - LSA’s worden verpreid via flooding - Elke router stuurt LSA met eigen configuratie, alsook ontvangen LSAs door naar zijn eigen buren - Na korte tijd heeft elke router alle LSAs van de andere routers binnen het routing domein - Er worden groepen van naburige routers (adjacencies) gevormd ° Vermijden dat elke router met elke andere router van het routing domein zou moeten controleren of ze gesynchroniseerd zijn Thomas Stubbe & Christophe Sysmans
°
Adjacency is gevormd zodra routers van elkaar bewust zijn en dezelfde gecompileerde LSDB hebben - Adjecencies worden dynamisch gevormd ° Een OSPF router stuurt tijdens initialisatie een Hello-pakket om zijn bestaan aan te kondigen ° Dit pakket bevat ID van eigen router + ID’s van routers waarvan hij Hello pakket ontvangen heeft ° Veronderstellen transitiviteit (= beschouwen routers die vermeld staan in Hellopakketten van andere routers, ook als rechtstreekse buren (ook indien van hen nog geen Hello-pakket ontvangen is) → Fase 2: Database Exchange Proces: - Elk koppel routers van een (nog te construeren) adjacency vormt een master/slave verhouding - Deze wisselen Database Description pakketten uit ° Beschrijven de LSAs en hun lolly number binnen de LSDB - Met behulp van Database Description pakketten kan een router detecteren of zijn LSDB verouderde informatie bevat ° Indien data verouderd, wordt met behulp van Link State Request pakketten gevraagd naar Link State Update pakketten (en expliciet bevestigd) - Adjecency is gevormd wanneer er alle koppels Link State Request en Link State Update pakketten uitgewisseld en bevestigd hebben ° Geen nood meer aan uitwisseling LSDB, tenzij bij topologiewijzigingen ∗ Periodiek worden er Hello-pakketten uitgewisseld om aan te tonen dat de router nog steeds actief is → Indien geen Hello-pakket (default 40s) wordt router aanzien als uitgevallen ∗ Bij topologiewijzigingen worden opnieuw Link State Update pakketten verstuurd → Conform met flooding: doorgestuurd naar alle buren → Enkel wijzigingen worden doorgesturd (in tegenstelling tot distance-vector protocol) ∗ Om de hoeveelheid adjacencies nog wat te beperken is er een extra optimalisatie: → Voor elk subnetwerk voor een DR (=Designated Router) voorzien → Elke router in dit subnetwerk vormt een adjacency met de DR → Zo dienen wijzigingen in het netwerk enkel doorgegeven moeten worden aan de DR (die luistert op multicast adres 224.0.0.6) en DR zal deze wijzing propageren naar de andere routers (via multicast 224.0.0.5) → DR functie is eigenschap van de interface van de router en niet van de router zelf → Netwerkbelasting neemt zo lineair toe i.p.v. kwadratisch → Eveneens Backup Designated Router (BDR) gekozen, die enkel luistert op het multicast adres, als backup indien de DR zou wegvallen → DR/BDR gekozen tijdens het uitwisselen van Hello-pakketten op basis van router prioriteit - Indien prioriteit gelijk => router met hoogste ID - Indien prioriteit van interface = 0 => nooit DR of BDR
b. Beschrijf, o.a. aan de hand van een figuur, wat er precies gebeurt indien er een nieuwe router in een door OSPF gestuurd internetwerk wordt opgenomen. • Router 1 komt op het netwerk en stuurt Hello-pakket uit • Nadat router 1 en router 2 van elkaar op de hoogte zijn, vormen ze een adjacency (1) Thomas Stubbe & Christophe Sysmans
• Ze wisselen Database Description pakketten uit ∗ De Database Description pakketten van router 1 bevatten enkel de LSA van zichzelf ∗ De Database Description pakketten van router 2 bevatten de LSAs van alle routers (behalve 1) • Router 1 vraagt in een Link State Request aan router 2 om alle LSAs van de routers in het internetwerk (en krijgt antwoord via Link State Update pakketten) • Router 2 vraagt (analoog) aan router 1 om diens LSA ∗ Hier bevatten router 1 en router 2 een gesynchroniseerde LSDB ∗ Kunnen vervolgens een nieuwe SPF tree en nieuwe routingtabel berekenen • Router 2 stuurt een Link State Update pakket naar alle routers waarmee hij een adjacency vorm (2) ∗ Dit pakket bevat enkel de LSA vanwege router 1 • Router 3 en 4 bevestigen na ontvangst en kunnen eveneens nieuwe routingtabel construeren • Router 3 en 4 sturen de LSA van router 1 in een Link State Update door naar routers 5 en 6 (3) • enz...
c. Hoe worden OSPF berichten verpakt (cfr. het OSI 7-lagen model)? • OSPF pakketten worden rechstreeks ingekapseld in IP-datagrammen • In tegenstelling tot RIP wordt er gewacht op ontvangstbevestiging ∗ Meermaals uitblijven van een antwoord wordt geïnterpreteerd als het falen van een verbinding d. Wat is TOS routing, en in hoeverre ondersteunt OSPF dit ? • TOS routing = Type Of Service routing • Door het instellen van de TOS velden (in ip datagram) kan een router een andere metriek berekenen afhankelijk van de voorkeuzen van de afzender • De LSA kan voor elke TOS een aparte metriek bevatten • Een router die geen TOS ondersteunt, zal enkel een metriek hebben voor een TOS die gelijk is aan 0 ∗ een dergelijke waarde dient altijd vermeld te zijn! • Een router die wel TOS ondersteunt, dient een SPF tree te berekenen voor elke legale TOS-waarde ∗ Bij het berekenen van de SPF tree voor een niet-nul TOS mogen geen routers opgenomen worden die geen TOS-routing ondersteunen → Gevolg is dat bepaalde bestemmingen niet bereikbaar zijn voor bepaalde TOS-waarde → Deze pakketten worden dan doorgestuurd via TOS nul routes
Thomas Stubbe & Christophe Sysmans
A6. RIP , OSPF en EIGRP a. Van welke categorieën routingprotocollen zijn RIP en OSPF typische vertegenwoordigers? • RIP: Interior Gateway, Distance Vector Protocol • OSPF: Interior Gateway, Link State Protocol
b. Maak een gedetailleerde vergelijking tussen de mogelijkheden en beperkingen van deze twee categorieën. • Distance Vector Protocol (RIP): ∗ Algemeen → RIP-berichten van de volledige routingtabel broadcasten naar alle route vectoren van zijn routingtabel ∗ Voordelen → Eenvoudiger te begrijpen: één type bericht, één tabel, eenvoudig mechanisme - Op basis van advertisments(aankondigingen) die een router ontvangt van andere routers past hij zijn routingtabel systematisch aan (standaard elke 30 seconden een RIP-bericht) - Dit gebeurt niet gesynchroniseerd en de RIP berichten worden niet bevestigd → Eenvoudig te configureren: daemon (unix) of service (win) opstarten op routers → Geen complexe verwerking van de advertisements → Goede resultaten, voorwaarde: netwerktopologie relatief eenvoudig en verbindingen vallen zelden uit ∗ Nadelen → Grote routingtabellen door verschillende paden - Minder geschikt voor grote routing domeinen. - Diameter maximaal 15. - RIP standaard: alle paden opnemen ° Meeste implementaties behouden enkel de route met kleinste metriek (routetabel beperken) → Veel netwerk verkeer door periodieke advertisement (volledige routingtabel!, standaard elke 30 sec) - Veel redundante informatie - Niet echt geschikt voor WAN → Trage convergentie - Meeste RIP implementaties bewaren enkel de route met kleinste metriek ° Meldingen met een hogere metriek worden genegeerd ° Metriek van de beste route wordt wel verhoogt als van de eerste intermediaire hop op dit pad een dergelijke melding ontvangen wordt - De lifetime parameter van via RIP aangeleerde routes wordt standaard ingesteld op 3 min ° Factor 6 keer de default periode tussen opeenvolgende advertisements ° Dit komt omdat het erg nadelig zou zijn indien de route verdwijnt als enkele advertisements verloren zouden gaan ° Vooraleer de route effectief verwijderd wordt uit de routingtabel, worden 4 periodieke advertisements gestuurd waarin men de route aankondigt met een metriek van 16 Thomas Stubbe & Christophe Sysmans
-
Routers adverteren hun berichten slechts periodiek en onafhankelijk van elkaar ° Willekeur in het uitwisselingsproces ° Resultaat wordt beïnvloed door de volgorde van verzending door verschillende routers → Klassiek probleem hierdoor: count-to-infinity - (zie vraag 4) - Om dit fenomeen te beperkten: diameter max 15! → Ook routing loop problemen kunnen in deze periode optreden: A -> B, B -> A, … - Aantal keer heen en weer bepaald door ttl veld van het IP datagram - Dit belast het netwerk nog meer ° Kan op zijn beurt leiden tot verlies van pakketten, ook routingberichten -> nog langer
• Link State Protocol (OSPF): ∗ Algemeen → Elke router meldt enkel op welke subnetwerken hij rechtstreeks toegang heeft - = Link State Advertisements (LSAs) - Worden naar alle routers van het internetwerk verpreid - Enkel na heropstarten van router, of nadat een router een wijziging in topologie heeft gedetecteerd - Het doorstromen gebeurt synchroon - Ontvanger bevestigd elk bericht expliciet → Autonomous System Border Routers (ASBRs) - Routers binnen routing domein die ook zijn aangesloten op subnetwerken buiten het routing domein - Vermelden in hun LSA ook de routes buiten het routing domein die via hen bereikbaar zijn ° Rechtstreeks en onrechtstreeks ° Dit noemt men external route LSAs ° Dikwijls worden deze external route LSAs geaggregeerd tot 1 enkele default route LSA → Elke router verzameld (compileert) de LSAs in een Link State DataBase (LSDB) - = een volledige inventaris van alle routers en van alle subnetwerken waarop deze aansluiting hebben → Als alles uitgewisseld is bezitten alle routers dezelfde LSDB ∗ Voordelen → Kleinere routingtabellen want slechts één enkele router per eindbestemming → Minder netwerkbelasting tijdens convergentiefase: enkel gewijzigde LSAs doorsturen. Toch is belasting niet te verwaarlozen, vooral bij route flapping (verbinding uitvalt ' tweemaal flooding van een LSA naar alle routers + herberekening van alle routingtabellen) → Minder netwerkbelasting na convergentie: enkel periodiek Echo-pakketten (bevatten router ID en geen LSA info ' beperkte lengte) ' geschikt voor LAN en WAN → Voor grote tot zeer grote routingdomeinen: al dan niet nog opsplitsen in verschillende areas → Kortere convergentieperioden: geen routing loops of count-to-infinity want elke router zelfde LSDB → Alle routers hebben exact beeld van de topologie van het internetwerk Thomas Stubbe & Christophe Sysmans
∗ Nadelen → Complexer: 5 soorten berichten en 3 soorten procedures (Hello, database exchange, flooding van LSA) → Meer werk voor netwerkbeheerder: nood aan planning, configuratie en opvolging tenzij slechts één area (backbone). Netwerkbeheerder moet grenzen definiëren (= toekennen Area ID), aggregeren van external route LSAs, … → Berekening van routingtabel uit LSDB is geheugen- en processorintensief.
c. Tot welke categorie behoort EIGRP ? Bespreek de meerwaarde van dit protocol in vergelijking tot de andere vertegenwoordiger in deze klasse, en (in detail) hoe dit gerealiseerd wordt. • Algemeen ∗ Enhanced Interior Gateway Routing Protocol ∗ Interior Gateway, Distance Vector Protocol (net als RIP) ∗ Net als RIPv2 gebaseerd op periodiek multicasten van routingtabel naar al zijn buren. → Werkt met lagere frequentie voor periodieke updates: 90s t.o.v. 30s voor RIP. ∗ Eveneens toepassing split horizon en triggered updates → Kans op het ontstaan van lussen daalt. • Twee belangrijkste verbeteringen t.o.v. RIP ∗ Advertisements bevatten voor elke route vier metrische waarden: → Statisch: afgeleid uit type subnetwerk of ingesteld door beheerder v/ router - d (delay): 3 bytes: som transmissie oponthoud in de verbindingen tussen router en bestemming - b (bandwith): 3 bytes: bandbreedte zwakste verbinding in pad naar bestemming → Dynamisch: verkregen door verkeer in verbindingen statistisch te analyseren - r (reliability): 1 byte: percentage pakketten dat bij bestemming aankomt, r=255 ' 100% aangekomen - l (load): 1 byte: bezettingsgraad van drukste verbinding ∗ Berekening van samengestelde metriek ∆
→ Elke EIGRP router i berekent metriek ∆ij naar om het even welke eindbestemming j door alternatief pad in overweging te nemen met elk van zijn naburen x als eerste intermediaire hop. Metriek van elk van zijn alternatieve paden kan als samengesteld beschouwd worden uit ∆xj (van de buur naar eindbestemming) + δix (verbinding met buur). Pad met kleinste metriek bepaalt route die router i in routingtabel opneemt. → ∆ij = min(over x) (δix + ∆xj) ∗ Implementatie Diffusing Update (DUAL) algoritme → Vermijdt routing loops. → Stel: router i krijgt van nabuur y nieuwe waarde ((δiy of ∆iy). Als δiy ' + ∆iy ' < ∆ij, dan wordt router y de eerste intermediaire hop voor router i naar eindbestemming j. Router i werkt routingtabel bij en zendt triggered update nr alle buren. - Nooit kans op routing loops want er wordt een kleinere metriek gekozen. Thomas Stubbe & Christophe Sysmans
-
Is de nieuw berekende metriek groter: niets doen tenzij buur die de update gegenereerd heeft de eerste intermediaire hop is naar de eindbestemming is (y=x): ° 2 mogelijkheden: (Afh. van of de nabuur z acceptabel is (als ∆zj < ∆ij (oude waarde))) Ten minste één acceptabele buurman: Router i selecteert diegene die aanleiding geeft tot de kleinste metriek, ∆iy' = min(over z) (δiz + ∆zj) als nieuwe intermediaire hop Router i werkt onmiddellijk zijn routingtabel bij, en stuurt een triggered update Geen acceptabele buurman: router i doet diffusieberekening zolang berekening niet klaar -> route naar bestemming j bevroren = activeren van route -> geen routing loops, wel black hole en tijdelijke onbereikbaarheid van bestemmeling duurt echter niet langer dan de duur van de diffusieberekening Stap 1 van diffusieproces: router i zendt query (bijzondere vorm van update) naar alle naburen z (behalve deze waarvan update ontvangen) met z≠x. In query: bestemming j + aangepaste metriek: ∆ij' = (δix' + ∆xj'). Als reactie wordt nieuwe metriek vanuit standpunt van buurman verwacht ∆zj'. Stap 2 van diffusieproces: Buren houden route in passieve toestand (vb. omdat router i niet eerste intermediaire hop of andere buurman kan geselecteerd worden) -> onmiddellijk antwoord met aangepaste metriek in routingtabel. OF: ze moeten route activeren -> sturen zelf queries naar alle buren (= DUAL de diffusie van de update), als router van alle buren antwoord ontvangen -> stuurt antwoord naar router waarvan query ontvangen zodar diffusie wegebt. Uiteindelijk antwoord bij eerste router -> stabiele toestand.
Thomas Stubbe & Christophe Sysmans