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.