Løsningsforslag uke 8

1. Ruting grunnlager

1. Hva er gode egenskaper for en ruting-algoritme?
   • korrekthet - få pakker fram til mottakeren
   • enkelthet - lett å implementere
   • robusthet - overleve mange feilende maskiner og linker, og klare å håndtere store endringer i topology og i vurdering av linkkvaliteter.
   • stabilitet - ikke noen store endring i rutingtabelle eller rutene som pakker ta etter en liten endring i linker som er tilstede eller i metrikken som vurderer linker.
   • fairness - kostnaderne for å overføre pakker mellom enhver par av sender og mottaker skal være omtrent like billig.
   • optimalitet - rute slikt at den samlete kostnaden for pakkeoverføring er minimalt. Kostnad i denne samheng er metrikken for ruter, f.eks. hvis kvalitetsmetrikken for ruter er antall hops, så er rutingalgoritmen optimalt som klarer å få pakker i gjennomsnittet fram over færrest mulig hops.
2. Gi et eksempel for motstridende gode egenskaper i en ruting-algoritme.
   • Fairness og optimalitet er de beste kandidatene for problemer, fordi den ene minimerer gjennomsnittet, den andre minimerer varians i kostnader for å overføre en pakke fra sendere til mottakere.
3. Hva er optimalitetsprinsippet i ruting?
   • Hvis ruter J ligger på den optimale veien V fra ruter I til ruter K, så er den optimale veien W fra J til K en del av V.
   • Og alle logiske variasjonene av dette.
4. Hva er et sink-tre, og hva er sammenheng mellom sink treet og optimalitetsprinsippet?
   • Gitt en ruter J i et nettverk, så vil sette av de optimale veiene fra alle andre rutere i nettverk være et tre. Hvis det ikke var tilfelle, men man kunne bruke en mer generisk graf, så hadde man en node I som ligger på de optimale veiene fra ruterene K og H til node J, men med forskjellige optimale delveier I-J for veien K-J og for veien H-J. Optimalitetsprinsippet sier at dette bare er mulig hvis begger veier I-J har samme kostnad. Men da kunne man også bruke av de to veiene I-J i begge tilfeller. Gjør man det for alle slike tilfeller, oppnår man en trestruktur.
5. Hva er grunnen for at sink-treer ikke bygges for å lage optimale ruting-tabeller i ekte nettverk?
   • Optimaliteten gjelder bare til et vist tidspunkt eller i et nettverk uten annen traffik.
   • Hvis kvalitetsmåling av linker med utvikling over tid inngår i algoritmen, så tar det bare for lang tid å utregne sink-treer.
   • I statiske nettverk (som sentral ruting med full statisk kunnskap over hele nettet og) kan man faktisk bruke sink treer på grunnlag av informasjon om det statisk nettverket uten noen last. Men også da ville optimaliteten være problematisk fordi noen linker måtte frakte mye mer pakker enn andre.

2. Ruting

1. Hva er hovedproblemet med Distance Vector Ruting (DVR) som gjør at LSR har blitt mer populær?
   • DVR har sitt count-to-infinity problem, som gjør at den veldig dårlig kan oppdage linkbrudd eller rutersvikt.
2. Hvordan har man forsøkt løse problemet til DVR?
   • Man har prøvd split-horizon tekniken. Der inkluderer man i rutingtabellen som settes sammen av avstandsmålinger og -estimeringen som man mottar fra direkte nabor også hvilken nabo som man har fått den siste estimeringen fra. Så vil en ruter A som sender en oppdateringspakke til naboruteren B slette alle de avstandsestimeringene fra oppdateringspakkene som sier at den beste ruten fører gjennom B.
3. Hvordan kan man bruke måle-trinnet i Link State Ruting (LSR) for å lage henholdsvis statiske og dynamiske ruting-tabeller?
   • Med å bruke tid som metrikk. Per linje holder rutere køer av pakker som må vente på overføring fordi linjen er opptatt. Vil man måle avstand til naboene kan man regne med tiden som målepakken venter i køen eller man kan tidsstemple pakken rett før den sendes på linjen. I den første situasjonen måler man avstand og ventetid og får en metrikk for hvor lasten på linjen forandrer seg dynamisk. I den andre situasjonen måler man den tiden som pakker trenger for selve overføringen uten ventetid, og siden overføringsforsinkelse i trådbundene nettverk er konstant, vil dette telle som statisk metrikk.
4. Hvorfor er det ikke kritisk for nettverk som bruker LSR at ikke alle rutere er perfekt oppdatert om tilstanden til alle andre noder når rutingtabellene bygges?
   • Rutere som snakker LSR med hverandre vil bruke flooding eller andre broadcast-mekanismer for å fordele den målte avstanden fra seg selv til alle direkte naboer til alle andre rutere i nettet. Dette tar tid og kan føre til at rutere med lang avstand bygger uaktuelle rutingtabeller.
   • Dette er ikke farlig fordi pakker vil sjekkes mot mer og mer aktuelle rutingtabeller jo nærmere pakken kommer målet. Nettet må oppleve veldig rare topologi-forandringer hvis ikke denne antakelsen holder.

3. Multicast ruting

1. Hvorfor ønsker man i noen tilfeller å bruke multicast ruting?
   • Multicast gjør det mulig å spare nettverksresurser med å sende en pakke en gang fra en sender til flere mottakere, slik at rutere kan kopiere pakken så sent som mulig.
2. Gi eksempler for en multicast-ruting protokoll som baseres på DVR og en multicast-ruting protokoll som baseres på LSR.
   • Spanning tree with LSR er en multicast-rutingsmekanisme som baserer seg på LSR. Oppdateringspakker inneholder informasjon om noen endesystemer tilknyttet ruteren som rapporterer er interessert i multicastgrupper. På den måten kan alle ruterer uavhengig bestemme for hver av sine linjer om en multcast-pakke er interessent for minst en ruter som nås på en unicast-strekning gjennom denne linjen.
   • Algoritmen er bra for store nett med små grupper fordi lite traffik er nødvendig til de delene av nettet som ikke har bruk for multicast-pakkene. Multicast mekanismen PIM-SM ("protocol independent multicast - sparse mode") virker likt.
   • Reserve Path Forwarding with Pruning bruker en backwards learning algoritme. DVR brukes til å finne ut om en pakke kommer inn over en linje som er en del av den korteste veien fra den noden som har sent pakker. Hvis ikke, droppes pakken. Ellers virker algoritmen som backwards learning med å sende alle multicast-pakker som kommer inn ut på alle andre linjer, hvis ikke prune-pakker for denne linje har tidligere blitt mottatt.
   • Algoritmen er bra for nett med store gruppen siden multicast-gruppene fordeles aggressivt og raskt over hele nettet. Multicast mekanismen DVMRP ("distance vector multicast routing protocol") virker likt.