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
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.