Pålitelig dataoverføring
Steg for steg fra en perfekt kanal til en realistisk verden med bitfeil, tap og forsinkelse — og protokollene som mestrer dem.
Pålitelig over upålitelig
Applikasjoner vil ha en pålitelig kanal. Nettverket gir dem alt annet. Transportlagets jobb er å bygge bro mellom drøm og virkelighet.
Tenk deg to prosesser som kommuniserer. Applikasjonen ser det slik: data sendes inn i en magisk pipe på den ene siden og kommer ut, uforandret og i riktig rekkefølge, på den andre. Ingen tap, ingen feil, ingen forsinkelse. Det er abstraksjon — en tjeneste som transportlaget tilbyr oppover.
Men under denne abstraksjonens overflate ligger virkeligheten: et nettverk som kan flippe bits, miste pakker og levere ting i feil rekkefølge. Kompleksiteten til protokollen vi trenger avhenger direkte av hvor ille den underliggende kanalen oppfører seg.
Sender og mottaker kjenner ikke hverandres tilstand — de vet ikke om den andre har mottatt noe som helst, med mindre de eksplisitt kommuniserer det via meldinger. Det er derfor vi trenger en protokoll.
Grensesnittene — fire funksjoner
Uansett hvor kompleks protokollen blir, bruker vi alltid de samme fire grensesnittene:
| Funksjon | Rolle |
|---|---|
| rdt_send() | Kalles fra applikasjonen ovenfor. Overleverer data som skal sendes pålitelig. |
| udt_send() | Kalles av protokollen for å sende en pakke over den upålitelige kanalen. |
| rdt_rcv() | Kalles når en pakke ankommer mottakersiden fra den upålitelige kanalen. |
| deliver_data() | Kalles av protokollen for å levere data opp til mottaker-applikasjonen. |
Nå bygger vi opp protokollen steg for steg — fra det trivielle til det realistiske. Hvert steg legger til én ny komplikasjon, og vi ser nøyaktig hva som kreves for å håndtere den.
Perfekt kanal — trivielt
Utgangspunktet: en kanal som aldri gjør feil. Protokollen trenger ikke gjøre noe spesielt.
Vi starter med den enkleste modellen: den underliggende kanalen er perfekt. Ingen bitfeil, ingen pakketap. I denne utopien er protokollen triviell.
Mottar data fra applikasjonen (rdt_send). Lager en pakke (make_pkt). Sender den ned (udt_send). Ferdig.
Mottar pakken (rdt_rcv). Trekker ut dataene (extract). Leverer dem opp (deliver_data). Ferdig.
Poenget med rdt 1.0 er ikke at den er nyttig — det er at den etablerer grunnlinjen. Alt som følger handler om hva som skjer når vi fjerner antakelsen om en perfekt kanal.
Bitfeil — ACK og NAK
Kanalen kan nå flippe bits i pakker. Vi trenger en mekanisme for at mottakeren kan si «fikk den» eller «fikk den ikke».
Forestill deg at du dikterer en tekst over telefon. Etter hvert ord sier lytteren enten «OK» eller «gjenta det». Det er nøyaktig det rdt 2.0 gjør: mottakeren bruker en sjekksum for å oppdage bitfeil, og svarer med ACK (alt vel) eller NAK (feil oppdaget — send på nytt).
Feildeteksjon: Sjekksum i hver pakke lar mottakeren oppdage korrupte data.
Tilbakemelding: ACK og NAK fra mottaker til sender.
Retransmisjon: Ved NAK sender senderen pakken på nytt.
Protokollen er stop-and-wait: senderen sender én pakke, og venter deretter på respons fra mottakeren før den sender neste.
Hva skjer hvis selve ACK/NAK-en blir korrupt? Senderen vet ikke om mottakeren fikk pakken eller ei. Å bare sende på nytt kan gi duplikater som mottakeren ikke kan skille fra nye data. rdt 2.0 er ødelagt.
Hva er det fundamentale problemet med rdt 2.0?
Sekvensnumre — håndtere duplikater
Løsningen på det fatale problemet: legg til et sekvensnummer slik at mottakeren kan gjenkjenne og kaste duplikater.
Ideen er enkel men kraftfull: senderen merker hver pakke med et sekvensnummer. Hvis ACK/NAK er korrupt, retransmitterer senderen uansett. Mottakeren sjekker sekvensnummeret — er det det hun forventer, leverer hun data opp. Er det et duplikat, kaster hun det stille og sender ACK på nytt.
For stop-and-wait trenger vi bare to sekvensnumre: 0 og 1. Hvorfor? Fordi senderen aldri har mer enn én ubekreft pakke ute om gangen. Mottakeren trenger bare skille mellom «den pakken jeg venter på» og «den forrige pakken (duplikat)».
Hva endret seg?
| Komponent | Endring fra rdt 2.0 |
|---|---|
| Sender | Legger til seq# (0 eller 1) i pakken. Ved korrupt eller NAK: retransmitterer med samme seq#. Dobbelt så mange tilstander — må huske om forventet seq# er 0 eller 1. |
| Mottaker | Sjekker seq# mot forventet. Hvis riktig: lever data opp, send ACK. Hvis duplikat: kast data, send ACK likevel (senderen trenger bekreftelsen). |
NAK-fri — bare ACK
Vi dropper NAK helt. I stedet sender mottakeren alltid en ACK — men med sekvensnummeret til den siste pakken hun mottok korrekt.
Ideen er elegant: i stedet for å si «den var feil» (NAK), sier mottakeren «den forrige var OK» (duplikat-ACK). Effekten er den samme, men vi eliminerer en hel meldingstype.
Mottaker: Send alltid ACK med sekvensnummeret til den sist korrekt mottatte pakken.
Sender: Hvis ACK-ens sekvensnummer ikke matcher det hun nettopp sendte, behandler hun det som en NAK — retransmitter.
Eksempel: Senderen sender pakke med seq=0. Mottakeren finner bitfeil. I stedet for NAK sender hun ACK(1) — altså «den siste pakken jeg fikk korrekt hadde seq# 1». Senderen ser at hun ventet på ACK(0), men fikk ACK(1) — tolker det som feil og retransmitterer.
I rdt 2.2, hva gjør mottakeren når hun mottar en korrupt pakke?
Tap og timeout — den komplette protokollen
Den underliggende kanalen kan nå også miste pakker helt — både datapakker og ACK-er. Sjekksum og sekvensnumre alene er ikke nok.
Med bitfeil og duplikathåndtering på plass, gjenstår én stor utfordring: pakker kan forsvinne sporløst. Senderen sender en pakke, og det kommer rett og slett aldri noe svar. Uten en ny mekanisme ville senderen ventet evig.
Senderen starter en timer etter å ha sendt en pakke. Hvis ACK ikke kommer innen en «rimelig» tid, antar senderen at pakken (eller ACK-en) er tapt, og retransmitterer.
Men hva om pakken bare var forsinket, ikke tapt? Da vil retransmisjonen skape et duplikat — men det er greit! Sekvensnumrene fra rdt 2.1/2.2 lar mottakeren gjenkjenne og kaste duplikater. Mottakeren sender bare ACK med riktig sekvensnummer.
Fire scenarier
rdt 3.0 håndterer alle disse situasjonene korrekt:
rdt 3.0 — også kalt alternating-bit protocol — er en funksjonelt korrekt protokoll for pålitelig overføring over en kanal med bitfeil og tap. Men den er katastrofalt treg. Det skal vi se i neste seksjon.
Hva skjer i rdt 3.0 hvis senderen timer ut men pakken bare var forsinket (ikke tapt)?
Stop-and-wait er forferdelig
rdt 3.0 er korrekt. Den er også så treg at den sløser bort nesten all tilgjengelig båndbredde.
La oss regne på et realistisk eksempel: en 1 Gbps lenke med 15 ms forsinkelse i hver retning (30 ms RTT), og pakker på 8000 bit.
Dtrans = L/R = 8000 bit / 109 bit/s = 8 μs
Usender = L/R ÷ (RTT + L/R)
= 0,008 ms / 30,008 ms
= 0,00027 = 0,027 %
Senderen bruker bare 0,027 % av lenkens kapasitet. Resten av tiden — 99,97 % — sitter hun og venter på ACK. En gigabit-lenke oppfører seg som en 267 kbps-lenke. Protokollen er den dominerende flaskehalsen, ikke nettverket.
Fyll røret — send flere pakker
Løsningen på stop-and-wait-problemet: la senderen sende flere pakker uten å vente på ACK for den forrige.
Pipelining er konseptuelt enkelt: i stedet for å vente på ACK etter hver pakke, sender vi flere pakker før noen ACK har kommet tilbake. Akkurat som et samlebånd — vi skyver kontinuerlig nye enheter inn, i stedet for å vente til den første er ferdig før vi starter den neste.
1. Vi trenger et større rom av sekvensnumre — to (0 og 1) er ikke lenger nok.
2. Senderen og/eller mottakeren trenger buffere for å holde styr på pakker som er sendt men ikke bekreftet, eller mottatt men ikke levert.
3. Vi trenger nye regler for hvordan vi håndterer tap og retransmisjon når mange pakker er «i flukt» samtidig.
Effekten
Hvis vi sender 3 pakker i pipeline i stedet for 1:
Usender = 3 × L/R ÷ (RTT + L/R)
= 0,024 ms / 30,008 ms
= 0,00081 = 0,081 %
Tredoblet utnyttelse med bare 3 pakker i pipeline! Med et større vindu nærmer vi oss 100 % utnyttelse.
To fundamentalt forskjellige tilnærminger til pipelining har vokst fram: Go-Back-N og Selective Repeat. De gjør ulike avveininger mellom enkelhet og effektivitet.
Hvorfor trenger pipelining mer enn to sekvensnumre (0 og 1)?
Kumulativ ACK og vinduet
Go-Back-N (GBN) er den enkleste pipelining-protokollen: mottakeren buffrer ingenting, og senderen går tilbake og sender alt på nytt fra der det gikk galt.
I GBN har senderen et vindu av størrelse N: hun får lov til å ha opptil N pakker «i flukt» (sendt men ikke bekreftet) samtidig. Vinduet glir framover etterhvert som ACK-er kommer. Mottakeren er enkel — hun godtar bare pakker i riktig rekkefølge.
Senderens vindu
■ ACK-et ■ Sendt, venter på ACK ■ Kan sendes (vindu ledig) ■ Kan ikke sendes ennå
Nøkkelregler
| Egenskap | GBN-regelen |
|---|---|
| ACK-type | Kumulativ: ACK(n) bekrefter alle pakker opp til og med n. |
| Timer | Én timer for den eldste ubekreftede pakken. |
| Timeout | Ved timeout: retransmitter alle pakker i vinduet — fra den eldste ubekreftede og utover. |
| Mottaker | Godtar bare neste forventede sekvensnummer. Alt annet kastes. Sender ACK for siste korrekte. |
Én tapt pakke kan føre til at mange korrekt mottatte pakker kastes og må sendes på nytt. Med et stort vindu (f.eks. N=1000) kan et enkelt tap utløse retransmisjon av hundrevis av pakker — en enorm sløsing med båndbredde.
I Go-Back-N med vinduestørrelse N=4, hva gjør mottakeren når hun mottar pkt5 men venter på pkt3?
Individuell ACK og buffring
Selective Repeat (SR) unngår unødvendig retransmisjon: mottakeren buffrer out-of-order pakker og senderen retransmitterer bare den ene pakken som faktisk gikk tapt.
GBN kaster alt som kommer ute av rekkefølge. Det er enkelt, men i et nettverk med lave tapsnivåer er det vanvittig sløsete. Selective Repeat tar en annen tilnærming: mottakeren buffrer pakker som kommer ut av rekkefølge, og sender individuelle ACK-er for hver pakke hun mottar korrekt — uavhengig av rekkefølge.
Nøkkelforskjeller fra GBN
| Egenskap | Go-Back-N | Selective Repeat |
|---|---|---|
| ACK-type | Kumulativ | Individuell per pakke |
| Timer | Én for eldste | Én per uACK-et pakke |
| Mottaker-buffer | Nei — kast out-of-order | Ja — buffr out-of-order |
| Retransmisjon | Alt fra tap-punktet | Bare den tapte |
| Kompleksitet | Lav | Høyere |
Sender- og mottakerregler
Data ovenfra: Hvis neste seq# er innenfor vinduet, send pakken og start en timer for den.
Timeout(n): Retransmitter bare pakke n, restart dens timer.
ACK(n): Merk pakke n som mottatt. Hvis n er den eldste ubekreftede, skyv vinduet fram til neste ubekreftede.
Pakke n i [rcvbase, rcvbase+N-1]: Send ACK(n). Hvis ut av rekkefølge: buffr. Hvis in-order: lever alle sammenhengende buffrede pakker opp, skyv vinduet.
Pakke n i [rcvbase-N, rcvbase-1]: Send ACK(n) likevel — senderen trenger kanskje bekreftelsen.
Ellers: Ignorer.
SR-dilemmaet: sekvensnummerrom og vinduestørrelse
Selective Repeat har en subtil felle: hvis sekvensnummerrommet er for lite i forhold til vinduestørrelsen, kan mottakeren ikke skille mellom en ny pakke og en retransmisjon av en gammel.
Sekvensnumre: 0, 1, 2, 3 (4 mulige). Vinduestørrelse: 3.
Scenario A: Sender sender pkt0, pkt1, pkt2. Alle ACK-er kommer fram. Sender sender pkt3, pkt0 (ny data), pkt1. Alt er bra — mottakeren vet at den nye pkt0 er ny data.
Scenario B: Sender sender pkt0, pkt1, pkt2. Alle tre ACK-er går tapt. Sender timeouter og resender pkt0. Mottakeren har allerede mottatt pkt0, pkt1, pkt2 og venter nå på pkt3 — men hun ser pkt0 komme og tror det er ny data med seq# 0.
Mottakeren kan ikke se forskjell! Oppførselen hennes er identisk i begge scenarier.
For å unngå dette dilemmaet må vinduestørrelsen N oppfylle:
Selective Repeat: N ≤ 2k-1 (der k = antall bits i seq#-feltet)
Go-Back-N: N ≤ 2k - 1
Hva er den viktigste forskjellen mellom Go-Back-N og Selective Repeat når en pakke går tapt?
Oppsummering: evolusjon av pålitelig overføring
Triviell: send og motta. Ingen mekanismer nødvendig.
+ Sjekksum, ACK/NAK, retransmisjon. Fatalt problem: korrupte ACK/NAK.
+ Sekvensnumre (0/1). Mottaker kaster duplikater.
− NAK fjernet. Duplikat-ACK erstatter NAK. TCP gjør dette.
+ Countdown timer. Korrekt, men stop-and-wait = forferdelig ytelse.
+ Flere pakker i flukt. Krever større seq#-rom og buffring. → GBN eller SR.
Denne seksjonen har bygget opp hele det konseptuelle grunnlaget for pålitelig overføring. Hvert prinsipp vi har sett — sekvensnumre, ACK-er, timer, kumulative bekreftelser, vindu, pipelining — dukker opp igjen i TCP. Forskjellen er at TCP kombinerer alle disse mekanismene i én protokoll, tilpasset den virkelige verdens behov.
Neste steg: TCP i praksis — segmentstruktur, pålitelig levering, flytkontroll og forbindelsesstyring.
Se også: Transportlagets tjenester, multipleksing og UDP — grunnlaget vi bygger videre på.