L?sningsforslag uke 11

1. Metningskontroll (congestion control)

1. Definer begrepene 'metning' og 'metningskontroll' i forhold til nettverk. Hvor og hvordan oppst?r metning i et nettverk? Hva er hovedprinsippene for metningskontroll?

   Metning er en tilstand i (en del av) et nettverk hvor det er s? mange pakker p? et gitt tidspunkt at det reduserer ytelsen. Kort sagt er ressursene overbelastet. Dette oppst?r hovedsaklig i switcher/rutere n?r det samles (aggregeres) trafikk fra flere linker som skal inn p? en og samme link (pakker legges i samme utbuffer), eller n?r det er uoverensstemmelse mellom b?ndbredden p? link inn og ut av en ruter langs pakkens path (linkspeed mismatch) slik at pakkene kommer inn raskere enn ruteren kan sende dem videre. Pakkene vil i begge tilfeller gradvis fylle opp tilgjengelig bufferkapasitet i ruteren, og i verste tilelle m? overskuddspakker det ikke er plass til, kastes. Metningskontroll er mekanismer for ? hindre/kontrollere metningen.

   Hovedprinsippene for metningskontroll er 1) unng? situasjoner hvor metning oppst?r ved gjennomtenkt nettverksdesign og kontrollert trafikkm?nster. 2) lett p?trykket n?r metning er i ferd med ? bygge seg opp: a) send info til noden som er opphavet til pakkene som skaper problem (the bad guy, oversv?mmer nettet med pakker), b) send info til alle nabonoder og be dem alle ta det litt roligere (sprer metningen litt utover i nettet). Man kan iverksette tiltak som ? ?ke kapasiteten til buffer og linker, endre forwardingstabeller for bedre balanse i trafikken, og/eller redusere senderaten. Det er uansett viktig ? unng? at konrollen introduserer svingene oppf?rsel; bedre med en jevn str?m pakker enn situasjon som veksler mellom stille og oversv?mmelse.

2. Er det noen forskjell p? metningskontroll i hhv. forbindelsesorienterte og -fire nettverk?

   Ved oppstart av en forbindelse i forbindelesorienterte nett allokeres det ofte ressurser. Denne allokeringen vil unng? metning (forutsatt at man har anta riktig ang. forventet ressursbruk). P? den annen siden er det da potensiale for ? sl?se med ressursene i situasjonene hvor forbindelsen ikke utnytter sin reserverte del maksimalt (eks venter p? ack/retransmisjon). Det er imidlertid ogs? en del forbindelsesorienterte nett hvor det ikke reserveres, men kun settes opp forbindelse, og i slike tilfeller vil man kunne se metning. I forbindelsesl?se pakkesvitsjede nettverk (Internett) preallokeres det ikke noen ressurser, og man m? forvente og h?ndtere situasjoner med metning i ruterne.

3. Forklar begrepene back pressure og soft state

   Back pressure: man bruker en mekanisme som holder tilbake pakker i buffre i oppstr?ms noder, sett fra den ruteren som har metningsproblemer. Man skyver alts? problemer bort fra og bakover i nettverket, og bruker selve nettet (og dets kollektive bufferressurser) til ? bufre pakkene istedenfor i kun ¨¨n node. Alternativet er ? kaste pakker hvis man ikke klarer ? redusere belastningen for den aktuelle ruteren.

   Soft state: Ressursallokeringen i ruterne er dynamisk, basert p? informasjon om dataflyter. I et forbindelsesfritt pakkesvitsjet nettverk blir alle pakker i prinsippet svitsjet uavhengig av hverandre, men i praksis utveksler to kommuniserende noder en str?m av meldinger. Tilstandsinformasjonen endres alts? over tid, og gj?r at man kan ta mer velbegrunnede avgj?relser, i motsetning til ved 'hard state' hvor info er hardkodet p? forh?nd.

4. Redegj?r for hvilke lag i OSI-modellen vi finner metningskontroll, hvordan mekanismen fungerer p? disse lagene, og evt hvordan de samspiller (utnytter tjenester).

   Datalinklaget: Retransmisjon, kvittering, (hop-by-hop) flytkontroll, caching av out-of-order pakker. Nettverkslaget: Rutingalgoritmer, k?mekanismer, betjeningsrekkef?lge, kastepolitikk, h?ndtering av pakkelivssyklus( TTL etc).Transportlaget: Retransmisjon, kvittering, (ende-til-ende) flytkontroll, timeoutverdier, cacing av out-of-order pakker.

   Linklaget og transportlaget h?ndterer omtrent de samme elementene av metningskontrollen, forskjellen ligger i at linklaget styrer i utgangspunktet den enkelte link, og er best egnet til ? ta seg av kortvarige metningssituasjoner og kontroll av bufferutnyttelse, mens transportlaget h?ndterer metning p? et ende-til-ende niv? og dermed kan ta seg av mer langvarige metningssituasjoner og "permanent" redusere senderaten til aggressive kilder. Nettverkslaget h?ndterer veivalg og selve skeduleringen i den enkelte ruter, og er p? en m?te en mer lokal del av metningskontrollen enn lagene over og under (selv om topologi og overordnet rutingtabell selvf?lgelig ogs? ang?r samtlige noder).

5. Redegj?r for ulike typer k?disiplin (relatert til switcher/rutere) , og diskuter fordeler/ulemper ved disse typene.

   FIFO: First in first out .. kun ¨¨n k?, hvor det ikke tas hensyn til hvilken flyt en pakke tilh?rer. Vanlig ? implementere fifo med taildrop, dvs at pakker kastes fortl?pende n?r k?en er full. RED og DECbit algoritmene er imidlertid merkompliserte n?r det gjelder valg av hvilken pakke som skal kastes. 
   FQ: Fair queuing .. De ulike flyter plasseres i ulike k?er som behandles round robin. Hvis det med denne k?mekanismen sendes data for raskt i en flyt, vil problemet v?re isolert til den ene k?en, og ikke ramme de andre flytene. Det er et designsp?rsm?l hvor mange slike del-k?er man skal tillate, og det er mulig at flere flyter m? dele en og samme k?, feks hvis en sorterer flyter etter destinasjonsadresse. En variant av FQ (weighted fq) tillater at del-k?ene har ulik vekt basert p? prioriteten til de data som ligger i k?en

6. Beskriv ulike strategier for ? unng? metning.

   DECbit: Ruteren gir tilbakemelding til noder f?r metning intreffer ved at det settes et bit i pakkene som passerer ruteren. Mottaker kopierer s? dette bitet inn i ACK slik at avsender tilslutt f?r beskjed om at metning er under oppbygging. Kriterier for ? sette bitet er ofte at den gjennomsnitlige k?lengden er st?rre en 1 p? det tidspunktet pakken passerer ruteren.

   RED: Random Early Detection (brukt sammen med TCP) gir tilbakemelding etter samme prinsipp som over, men istedenfor ? sette et bit (eksplisiv feedback), gis det kun implisitt feedback i form av pakketap. Dvs at det kastes en pakke i ruteren f?r det strengt talt er behov for det. TCP avsenderen vil detektere pakketapet ved uteblitt ack p? aktuelt sekvensnummer og justere senderaten sin. Fordelen er at det advarende pakkekastet medf?rer at en kan iverksette tiltak tidligere og om mulig unng? massivt pakketap som er alternative n?r man venter p? full metning f?r noe skjer.

   Alternative mekanismer overv?ker RTTverdier, og tolker ?kning i gjennomsnittlig RTT som indikasjon p? at en eller flere rutere er i ferd med ? bli overbelastet. Et alternativ er ? sammenlikne n?v?rende RTT med snittet av min og max RTT, og redusere metningsvindu med 1/8 hvis st?rre. Alternatvt kan en sammenlikne throughput for hver RTT.

7. Forklar hvordan metningskontroll er implementert i TCP, og knytt din forklaring til begrepene .

   Implementert som kontroll av avsendervinduet(congestion window) ved hjelp av additiv increase / multiplicative decrease, slow start, fast retransmission, fast recovery osv. Slow start brukes for ? ?ke metningsvinduet raskt fra en "kald start". ?kningen er eksponensiell istedenfor line?r, slik at vinduet fordobles per RTT inntil pakketap, hvorp? det halveres og man g?r over ? fortsette med additiv increase. Denne mekanismen benyttes b?de etter oppkobling av en forbindelse, og etter at at en metning har opph?rt. Additiv increase vil si at for hver burst(fullt vindu med pakker i l?pet av en RTT) ?kes vinduet med 1, imotsetning til slowstart hvor hver enkeltpakke medf?rer denne ?kningen.

   Fast retransmit vil si ? resende pakker med det samme det oppdages at de er borte, fremfor ? vente p? ack en hel RTT f?rst. Mottaker vil sende ack p? pakke n-1 (sist mottatte pakke i sekvens) p? hver mottatte pakke n+1 helt til n mottas. Det er alts? det h?yeste pakkenummeret som til envher tid har ankommet korrekt som settes i ack, imotsetning til det ? ack'e med sekvensnummer tilsvarende pakken som kom. Gjentagende "gamle" ack-verdier vil da signalisere til avsender at pakken er savnet/borte.

   Fast recovery: iverksettes ved metning ved at metningsvinduet halveres etterfulgt av additiv increase.

8. Anta at vi har en rundetid p? 10 msec og ingen metning. Mottakervinduet er p? 24 KB og maksimumssegmentet (maximum segment size/MSS) er 2 KB. Hvor lang tid tar det f?r det f?rste fulle vinduet blir sendt?
   
   F?rste runde sendes 2 KB (MSS), deretter 4KB, 8KB, 16KB og til slutt 24 KB (avsenderen sender aldri mer enn mottakervindet). En rundetid p? 10ms og 4 runder for ? komme opp i 24 KB skulle gi 40 ms.

9. Anta at TCP sitt metningsvindu er p? 18 KB og en timeout forekommer. Hvor stort vil vinduet v?re hvis de neste 4 tranmisjonene er vellykkede?
   
   N?r en timeout forekommer vil TCP anta at nettet er mettet og vil dermed g? inn i en ny slow start fase. Dette vil si at f?rste transmisjon etter en timeout vil v?re p? st?rrelse med MSS (maximum segment size). Hvis vi antar at MSS er 2KB vil vi f?rste runde sende 2KB, deretter 4KB, 8KB og etter 4 transmisjoner 16KB.

10. En TCP maskin sender fulle vinduer p? 65.535 bytes over en 1-Gbps linje med en 10 msec forsinkelse. Hva er maksimal gjennomstr?mning (throughput)? Hvor mye av linjen utnyttes?
    
    Her tar det 10ms ? sende et fullt vindu over til mottakeren, og deretter 10ms for ? vente p? ACK. Dvs. at vi kan sende ett vindu per 20ms. Da rekker vi 50 vinduer p? 1 sekund. 50 vinduer * 65.535 bytes = 3,3 millioner bytes.
    3,3 millioner bytes regnet om til Mbit skulle gi 26,4 Mbit. S? med en vindusst?rrelse p? 65.535 bytes kan vi maksimalt sende 26,4 Mbit/sec data. Vi kan tydelig se at vindusst?rrelsen begrenser hvor mye data vi kan sende. 26,4/1000 * 100 gir oss svaret som sier at vi kun utnytter 2,6% av linja.

2. RPC

1. Hva er RPC, og beskriv hvordan det fungerer.

   Remote Procedure Call er en teknikk som muliggj?r det ? kalle en prosedyre i et annet adresserom (feks. i en annen maskin). Hensiktet er at RPC skal minne mest mulig om vanlige prosedyrekall, dvs med parametre, returverdi og mulige exceptions, og det skal v?re s? enkelt som mulig for programmereren. Mest mulig av kommunikasjonsdetaljene skal skjules (transperent). Kall som skal v?re tilgjengelige som RPC, m? spesifiseres vha. et interface definition language(IDL) som er et deklarativt spr?k best?ende av grensesnitt til prosedyrene. IDL inneholder ikke implementasjonsdetaljer.

   En IDL kompilator vil lage stubs for klient og tjener. N?r en klient kaller en fjernprosedyre vil kallet g? til klientstubben, hvor kallet endres til et passende nettverksformat. En egnet protokoll (eks TCP/IP) brukes til ? overf?re kallet til tjenerstubben, hvor meldingen konverteres tilbake til et lokalt prosedyrekall som eksekveres p? tjeneren. Selv om all kommunikasjon g?r via stubbene, er dette skjult for programmerer.

   Stegene for ? lage en RPCapplikasjon er som f?lger:

   1. Lag IDL'en. Definisjoner i denne er tilgjengelig for klienter.
   2. Kompiler IDL'en. Produserer headerfiler samt stubs for klient og tjener.
   3. Programmer tjenerens kode. De prosedyrene som spesifiseres i IDL m? n? implementeres. Kompileres sammen med headerfiler og tjenerstub.
   4. Programmer klientens kode. Her kan man invokere fjernprosedyrekallene. Kompileres sammen med headerfiler samt klientstub.
   se man rpc for mer info om hvordan rpc benyttes sammen med C.
2. Redegj?r for de fire ulike kallsemantikkene RPC kan operere med .

   En RPCimplementasjon kan ha ulike leveringsgarantier, ogs? kalt RPCsemantikk. Hvilken semantikk-form RPCimplementasjonen st?tter er sv?rt viktig ? vite. Det som skiller semantikkene fra hverandre er 1) om man fors?ker retransmittere meldinger til det kommer svar, eller antar at tjeneren er d?d. 2) om man filtrerer ut duplikate meldinger ved retransmisjon 3) om man holder oversikt over svarene tjeneren har sendt, slik at disse kan retransmitteres ved behovuten ? m?tte utf?re det originale prosedyrekallet p? nytt.

   exactly-once:et prosedyrekall fra klient til tjener ugf?res n?yaktig 1 gang, noe som er vanskelig, hvis ikke umulig, ? garantere for. Problemet er at en klient ikke ser forskjell p? en feil i nettverket (pakkekast ved metning) og feil i tjeneren (core dumped). Man kan garantere denne semantikken hvis tjeneren ikke kr?sjer og klienten mottar resultatet av kallet.

   at-most-once: er den vanligste semantikken, og inneb?rer at kallet fra klient til tjener utf?res eller ikke(0 eller 1 gang). Tjeneren filterer ut duplikate meldinger fra klienten.

   at-least-once: vil si at kallet fra klient til tjener utf?res en eller flere ganger. Meldinger retransmitteres, uten at tjeneren filtrerer duplikater.

   maybe: Prosedyrekallet fra klient til tjener utf?res kanskje, dvs at klienten ved timeout ikke retransmitterer meldinger. Man kan ikke si med sikkerhet om kallet ble utf?rt: hvis meldingen ble borte eller at tjeneren kr?sjet, ble ikke kallet utf?rt. Imidlertid hvis det var svarmeldingen som ble borte, s? kan kallet ha forekommet.