INF3190/4190 Ukeoppgave 11: Metningskontroll
1. Metningskontroll (congestion control)
- 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.
- 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.
- 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.
- 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).
- 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 - 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.
- Forklar hvordan metningskontroll er implementert i TCP, og knytt din forklaring til begrepene
slow start, fast retransmit og fast recovery.
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.
2. RPC
- 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:
- Lag IDL'en. Definisjoner i denne er tilgjengelig for klienter.
- Kompiler IDL'en. Produserer headerfiler samt stubs for klient og tjener.
- Programmer tjenerens kode. De prosedyrene som spesifiseres i IDL m� n� implementeres. Kompileres sammen med headerfiler og tjenerstub.
- Programmer klientens kode. Her kan man invokere fjernprosedyrekallene. Kompileres sammen med headerfiler samt klientstub.
- 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.
3. Oppgaver fra Tanenbaum
6-27
Selv om brukeren skriver i et uniformt tempo, vil tegnene echoes i bursts. Brukeren kan trygge flere taster uten at noe skjer p� skjermen, og plutselig innhenter skjermen seg igjen og tegnene str�mmer ut. Folk flest har en tendens til � synest dette er plagsomt. (se Tanenbaum s. 545-547)
6-28
De f�rste bursts inneholder hhv. 2,4,8 og 16 KB. Det neste er 24KB, og inntrer etter 40msec.
6-29
Den neste transmisjonen vil v�re 1 max segment size, deretter hhv. 2,4 og 8. Dvs at etter 4 suksesser vil det v�re 8KB