INF3190 - Vår 2010

INF3190/4190 Ukeoppgave 8: Nettlaget (forts.)

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.