INF3190/4190 Løsningsforslag 5: Linklaget (forts.)

1. Linklaget - Funksjonalitet forts.

• a) Forklar prinsippet bak CRC og FEC, ta med hva forkortelsene står for. Hvilke faktorer påvirker beslutningen om å korrigere feil ved hjelp av CRC-metoden for deteksjon kombinert med retransmittering av forkastede pakker vs bruk av FEC? Hvorfor legges CRC-sjekken nesten alltid sist i rammen på linklaget?

Ideen bak begge teknikkene er å oppdage feil, forskjellen ligger i at mens CRC kun detekterer, så kan FEC også rette feil til en viss grad. Cyclic Redundancy Check er en polynomisk kode, basert på å behandle bitstrenger som representasjoner av polynom med kun koeffisientene 0 og 1. En sekvens av k bit, er således listen over koeffisienter for et polynom av grad k-1, eks 110001 gir x^5+x^4+1 (husk at x^0 = 1). Polynomisk aritmetikk utføres modulo 2, både addisjon og subtraksjon tilsvarer bitvis XOR. Partene enes om et generatorpolynom G(x) med grad r. For å sende en melding med m bit, legg til r antall 0 i den minst signifikante enden av opprinnelig bitsekvens. Utfør polynomdivisjon av den utvidede sekvensen med G(x), se eksempel side 196 i Tanenbaum. XOR inn resten fra divisjonen i den utvidede sekvensen (på plassen der de ekstra 0bitene ble lagt til). Resultatet er T(x) som sendes over linken. Hvis mottaker kan utføre divisjonen T(x) på G(x) og få 0 i rest, er overføringen feilfri. Mengden feil CRC kan oppdage er avhengig av polynomet.

Forward Error Correction benytter seg av å sende redundant info sammen med data. FEC er således egentlig ikke èn teknikk, men en samling teknikker, hvor den enkleste formen er å sende med koplett duplikat av originaldata. De feilrettende egenskapene avhenger av Hamming distansen (antall bitposisjoner hvor to kodeord (m databit + r redundante bit) er ulike). For å oppdage d feil, trengs en distanse kode d+1, fordi det da ikke er noen måte at d enkle bitfeil kan endre et gyldig kodeord til et annet gyldig kodeord. For å rette opp d feil, kreves imidlertid distansekode 2d+1 fordi da er kodeordene så lang fra hverandre at selv ikke d feil kan blande sammen to gyldige kodeord. se side 193-195 i Tanenbaum.

Faktorer som påvirker valget er: linkens kvalitet(hyppig forekommende 1-bitsfeil peker i retning av FEC), linkens RTT(ved lav RTT bruk CRC og retransmisjon hvis mulig, ellers FEC hvis kostnaden ved retransmisjon blir for høy eller du bare har ett forsø pr ramme). Husk bevaring av rammerekkefølge.

For å få sendt data ut på linken så raskt som mulig, er det praktisk å regne ut CRC-koden mens bitene sendes (on-the-fly), og sette koden sist i rammen. Hvis koden skal settes i header, må hele rammen først buffres mens koden beregnes, noe som krever både mer tid og bufferkapasitet, og øker forsinkelsen gjennom nettet.

• b) En bitsekvens 10011101 overføres ved å benytte standard CRC som beskrevet i læreboka. Generatorpolynomet er x^3 +1. Vis hvilken bitsekvens som overføres. Anta at det tredje bitet fra venstre inverteres under overføringen, og vis så at denne feilen oppdages på mottagersiden.

Polynomet blir 1001, og vi hekter på tre 0bit i den minst signifikante enden av bitsekvensen og får 10011101000. Den utvidede bitsekvensen divideres så på polynomet og vi får rest 100 som XORes inn i bitsekvensen slik at det som overføres blir 10011101100. Sekvensen som mottas med feil er således 10111101100, og ved divisjon med polynomet gir dette rest hos mottaker på 100 som er ulik 0, hvilket betyr at feil er oppdaget og retransmisjon kan bli trigget.

• c) Gi en kort definisjon av begrepet 'flytkontroll'. Hvordan håndteres flytkontroll på linklaget?

Flytkontroll regulerer trafikken over en kanal ved å gjøre det mulig for mottaker å justere hvor mye data den til enhver tid er i stand til å motta. Dette kan oppnås ved at mottaker sender en egen melding som ber sender stanse eller redusere raten den sender data med. Sliding window mekanismen kan også benyttes til dette ved at mottaker ikke sender ACK når den ikke har ledig kapasitet. Riktignok vil dette resultere i unødvendige retransmisjoner, men på linklaget kan linken uansett ikke benyttes til noe annet mellom et gitt sender-mottaker par når mottaker er opptatt.

• d) Forklar virkemåten til 'Stop-and-wait' (SAW). Hvordan håndteres feilsituasjoner som feks. tapte/forsinkede rammer? Hva slags funksjonalitet tilbyr denne protokollen?

SAW sender ut en pakke og venter så på kvittering (ACK/NACK) før den sender neste pakke. Feilsituasjoner løses ved timeout: hvis kvittering (ACK) ikke er mottatt når tiden utløper, retransmitteres pakken. Ved bitfeil sendes enten NACK, eller så kastes pakken stille og man venter på at timeout skal trigge retransmisjon. Denne protokollen besørger pålitelig overføring over linken samt bevaring av pakkerekkefølgen.

• e) En kanal har en bitrate på 4kbps og propagasjonsforsinkelse på 20ms. For hvilket område av rammestørrelser gir SAW en effektivitet på minst 50%?

Effektiviteten vil være 50% når tiden det tar å overføre rammen er lik RTT (propagasjonsforsinkelse). Ved en overføringshastighet på 4 bit pr millisekund, vil en kunne sende 160 bit på 40ms (RTT, 2x enveis delay). For rammestørrelse over 160bit vil derfor SAW være rimelig effektiv.

• f) Forklar virkemåten til 'Sliding window'. Hva slags funksjonalitet tilbyr denne protokollen? Redegjør kort for problemstillinger knyttet til sekvensnummer i Sliding window

Sliding window sender pakker og venter ikke på kvittering for hver enkelt pakke, men tillater et gitt antall pakker utestående samtidig før ACK må mottas. Se side 211 i Tanenbaum. Denne protokollen besørger, på samme måte som SAW, pålitelig overføring over linken og bevaring av pakkerekkefølge, men i tillegg har sliding window også støtte for flytkontroll. Hovedproblemet med sekvensnummer i sliding window protokollen er at man må sørge for at det ikke er overlapp mellom sekvensnummer for å kunne skille mellom nye og duplikate pakker. For selectiv repeat løses dette ved å benytte et sendevindu som er mindre enn (max sekvensnr +1)/2. Når båndbredden øker kan sekvensnummerintervallet bli for lite.

2. Ethernet - Egenskaper

• a) Beskriv kort den historiske utviklingen av Ethernet slik vi kjenner det i dag. Hva er forskjellen på de facto standarden Ethernet og ISO's CSMA/CD standard? Er det mulig for dem å sameksistere i et nett, og i så fall hvordan?

Stikkord for utviklingen: Norman Abramson, Hawaii ALOHANET, Bob Metcalfe, Ethernet 1976, coax, multidrop cable, 2.94Mbps, DIX standard 1978 10Mbps, IEEE802.3 1983
Forskjellen på standardene ligger tolkningen av rammens 2 byte felt mellom adresser og data. de facto standarden bruker dette som et Type-felt som forteller mottaker hva som skal gjøres med rammen, dvs hvilken prosess den skal leveres til. IEEE-standarden som ISO benytter tolker dette som et lengdefelt. Siden payload i den første standarden var 1500B eksakt, og mindre datamengder måtte paddes til å fylle ut disse 1500, så kan de to versjonene sameksistere ved at Eternet standarden ikke benytter type verdier under 1500, og 802.3 kan angi lengder opptil 1500.

• b) Redegjør for hvordan et Ethernet er bygd opp og hvilke fysiske begrensninger som gjelder. Hvilke rammer kan et ethernet adapter motta?

Ethernet benytter CSMA/CD teknologi, se oppgave 3 for detaljer. Dette innebærer at det er et delt medium hvor det kan forekomme kollisjoner hvis flere stasjoner forsøker sende data samtidig. Fakta: 48bits adresser, rammene må inneholde minst 46B og maks 1500B data, rammene har en 32bits CRC, standarden er generelt bitorientert, det benyttes coaksialkabel med typisk impedans 50 ohm, minimum 2.5 meter mellom hver host, maks 1024 hoster, maks 4 repeatere mellom 2 vilkårlige hoster, maks utstrekning 2500 meter når det benyttes 4 repeatere, hvert segment kan være på maks 500meter.

Vanligvis vil et ethernet adapter ta imot rammer som har mottaker adresse som enten matcher det enkelte adapters egen adresse, eller en kringkastingsadresse. Det er også mulig å instruere adapteret til å ta imot ulike multikastaderesser, eller også til å fange opp alle rammer, noe som kalles promiscous mode.

• c) Ethernet er også implementert for datarater på 100Mbps og 1Gbps. Beskriv eventuelle problemer med å øke bitraten fra 10Mbps til disse, og forklar mulige løsninger på problemene.

Ved å øke senderaten fra 10 til 100 Mbps, må også kravene til transmisjonsmediet økes. Legging av ny kabel er kostbart, så man ønsker å benytte eksisterende kabler så sant det lar seg gjøre. Kollisjonsdeteksjonsalgoritmen er basert på at enhver stasjon skal kunne oppdage en kollisjon mens en stasjon sender ut en ramme. For 10Mbps Ethernet med maksimal utstrekning 2500m, og dermed minimums rammestørrelse 512bit, har hvert bit en utstrekning på 100ns. Ved å øke raten til hhv 100Mbps og 1Gbps, reduseres utstrekningen til hhv 10 el. 1 ns. Dvs at hvis man skal holde utstrekningen konstant, vil delay*bandwidth produktet øke med en faktor 10 / 100.

For 100Mbps er dette løst ved å kreve at det brukes TP- eller fiber-kabler. For TP gjelder da kat3 med 4 par og maks-segment på 100m, eller kat5 med 2 par og 200m utstrekning. Fiberkabelens utstrekning her er satt til maks 2000. I praksis implementeres 100Mbps med kat3. Alle slike systemer benytter hubs, enten shared eller switched ( i det siste tilfellet har hver stasjon sitt kollisjonsdomene). For å kunne detektere kollisjoner med en shared hub kan man enten redusere maks utstrekning slik at 512bit igjen er nok til å fylle mediet, eller å øke minimum rammestørrelse, hvilket ikke er særlig praktisk med tanke på sameksistens av systemer.

3. Ethernet - CSMA/CD

Forklar virkemåten til CSMA/CD protokollen. Hva forbindes med 51.2 microsec? Hva ligger i følgende begrep: (non)persistent, kollisjonsvindu, eksponensiell back-off

Carrier Sence Multiple Access with Collision Detection
Mottakersiden av et ethernet adapter er relativt enkelt, det er senersiden som inneholder kompleksiteten. Algoritmen er som følger: hvis mediet er ledig kan enhver stasjon begynne å sende umiddelbart. Siden protokollen tillater maks 1500B data + 27B header (12216 bit) vil en sender ved 10Mbps legge beslag på mediet i ca 1.2ms Etter transmisjon må adapteret vente 51.2microsec før neste ramme kan sendes for å forhindre at et enkelt adapter kan beslaglegge mediet kontinuerlig. I denne pausen har andre adaptere som venter, en sjanse til å starte sin sending. Med en maksimal utstrekning på 2500m og 10Mbps, er delay*bandwidth produktet 512 bit (14B header, 46B data, 4B CRC). Dersom flere stasjoner starter å sende data ut på mediet i løpet av et intervall, kollisjonsvinduet, vil samtlige stasjoner oppdage dette og avslutte transmisjonen etter at minst 512 bit er sendt. Disse 512 bitene fyller vinduet og sikrer at alle stasjoner ser kollisjonen, og det er også derfor et adapter må vente den spesifikke pausen mellom rammer.

Etter at en kollisjon er oppdaget, og alle involverte sendere har trukket seg tilbake, benyttes en eksponensiell backoff algoritme for å avgjøre når det muligens er trygt å starte sending igjen. Formelen er 2^n * 51.2microsec, hvor n er et tilfeldig tall mellom 0 og det antall kollisjoner som hittil har forekommet for den gitte rammen. Dvs at ventetiden for det første alltid er et multiplum av kollisjonsvinduet, for det andre potensielt øker for hver kollisjon som skjer, og for det tredje ikke endres likt for alle stasjoner slik at sannsynligheten for at èn av partene skal klare å sende uforstyrret øker for hver kollisjon som oppstår. k-persistent betyr at stasjonen begynner å sende med det samme mediet blir ledig med en sannsynlighet k. non-persistent betyr at stasjonen ikke lytter kontinuerlig på mediet for å finne ut når det blir ledig, men istedenfor sjekker linjen på tilfeldige tidspunkt, og hvis den da er ledig så startes transmisjon.