Grunnleggende og medietilgang

Hva lenkelaget egentlig gjør

Før vi snakker om Ethernet, svitsjer eller ARP — la oss forstå hvorfor vi i det hele tatt trenger et eget lag under nettverkslaget.

Tenk deg at du sender en pakke fra laptopen din i Trondheim til en webserver i California. Nettverkslaget (IP) er flink til én ting: det finner veien på tvers av internett. Det bestemmer at pakken skal gjennom router A, så router B, så router C, og så videre. Men IP bryr seg ikke om hvordan pakken fysisk kommer fra A til B. Er det en fiberkabel? En WiFi-link? En satellitt? IP vet ikke, og IP bryr seg ikke.

Det er jobben til lenkelaget. For hver enkelt «hopp» på veien — altså hver lenke mellom to naboer i nettverket — er det lenkelaget som sørger for at dataene faktisk overføres som signaler på et medium og kommer frem i andre enden. Hver lenke kan være forskjellig teknologi, og hver teknologi har sine egne regler.

Noen ord du må vite

Noder er alle enheter som kjører protokollstabelen — verter (PC-er, servere, telefoner) og routere. Lenker er kommunikasjonskanalene som forbinder naboliggende noder. En lenke kan være trådbundet (twisted pair, koaks, fiber) eller trådløs (WiFi, 4G/5G, satellitt). Den innpakkede enheten på lag 2 kalles en ramme (frame) — den kapsler inn et IP-datagram akkurat som et datagram kapsler inn et TCP-segment.

Hvilke tjenester tilbyr lenkelaget?

Ikke alle lenkelagsteknologier gjør alt, men her er tjenestekatalogen de kan tilby:

• Framing og lenketilgang. Pakker datagrammet inn i en ramme med hode og hale. Hvis mediet deles med andre (som på WiFi), må det også styre hvem som får sende når.
• Pålitelig levering. Enkelte lenker, særlig trådløse med mye feil, kjører retransmisjon på lenkenivå. Dette er sjeldent på pålitelige kabler — der lar man TCP gjøre jobben ende-til-ende.
• Flytkontroll. Pacing mellom nabonoder slik at mottakeren ikke drukner.
• Feildeteksjon og feilretting. Signaldemping og støy kan snu bits. Mottakeren må merke det.
• Half- eller full-duplex. Kan begge sidene sende samtidig, eller må de bytte på?

Når bits snur på veien

Støy, demping og elektromagnetisk interferens kan flippe en bit fra 0 til 1 eller omvendt. Mottakeren må kunne merke det. Løsningen: send med litt ekstra informasjon som røper feilen.

Grunnideen er enkel. Du har d databits du vil sende. Før du sender, regner du ut noen ekstra redundans-bits (EDC — Error Detection and Correction) basert på innholdet. Du sender begge deler. Mottakeren regner ut redundansen på nytt fra dataene den faktisk mottok, og sammenligner med den som lå ved. Stemmer ikke de to — er det noe galt underveis.

Feildeteksjon er aldri hundre prosent. Det finnes alltid feilmønstre som tilfeldigvis gir samme redundansverdi som den opprinnelige. Men med riktig valg av algoritme blir sannsynligheten for å gå glipp av en feil forsvinnende liten. Jo flere redundansbits, jo bedre deteksjon.

Paritetsbit — den aller enkleste ideen

Legg til én bit som gjør at det totale antallet 1-ere blir et partall. Slik ser det ut for 16 databits:

  data (16 bit)       paritet
  0111000110101011    1    → ni 1-ere i data, pariteten gjør det til ti (partall)

Om én bit snur under overføring, blir antall 1-ere odde, og mottakeren oppdager det umiddelbart. Problemet: om to bits snur, blir antallet partall igjen, og feilen går under radaren. Enkelpariteten fanger bare et odde antall feilbits.

Todimensjonal paritet — en pekepinn mot noe smartere

Hvis man arrangerer dataene i et rutenett og setter paritet både på hver rad og hver kolonne, kan man ikke bare oppdage en enkelt bitfeil — man kan rette den. Feilen ligger der den markerte raden og den markerte kolonnen krysser hverandre.

CRC — det som faktisk brukes

Ethernet, WiFi og nesten alle moderne lenkelagsteknologier bruker Cyclic Redundancy Check (CRC). Det er en smart konstruksjon basert på polynomdivisjon i modulo-2-aritmetikk (som i praksis er XOR-operasjoner), og den er både billig å implementere i maskinvare og veldig god på å fange burst-feil — der flere nabobits snur samtidig, noe som er typisk for elektrisk støy.

Grunnideen

Senderen og mottakeren er enige om en generator G — en bitsekvens på r+1 bits (hvor første og siste bit er 1). Senderen finner en redundans R på r bits slik at den kombinerte sekvensen <D,R> er nøyaktig delelig med G i modulo-2. Så sender senderen <D,R>. Mottakeren deler det mottatte på G. Blir resten null — alt bra. Blir resten noe annet — en feil har skjedd.

Formelen

Senderen regner ut R som resten av (D · 2ʳ) / G (modulo 2). Å gange med 2ʳ er det samme som å legge til r nuller til høyre — vi skyver dataene til venstre og lager plass for CRC-bitene. Deretter XOR-divideres dette skift-tallet med G, og resten som blir igjen er R.

Et konkret eksempel

La oss gå gjennom det trinn for trinn med data 100100 og generator G = 1101 (som tilsvarer polynomet x³ + x² + 1). Siden G er 4 bit, blir r = 3, så vi legger til tre nuller og XOR-deler:

  1 0 0 1 0 0 0 0 0   ← D skiftet tre posisjoner
⊕ 1 1 0 1             ← G
  ─────────
    1 0 0 0 0 0 0 0
  ⊕ 1 1 0 1
    ─────────
      1 0 1 0 0 0 0
    ⊕ 1 1 0 1
      ─────────
        1 1 1 0 0 0
      ⊕ 1 1 0 1
        ─────────
            1 1 0 0
          ⊕ 1 1 0 1
            ─────
                  0 0 1    ← R = 001 (resten, tre bit)

Så det som går på kabelen er <D,R> = 100100001. Mottakeren tar disse ni bitene, XOR-deler dem med den samme G = 1101, og skal få rest null. Hvis én eller flere bits har snudd underveis, blir resten forskjellig fra null, og mottakeren vet at rammen er korrupt — og kaster den.

Hvor bra er CRC?

En CRC med r bits fanger alle burst-feil kortere enn r+1 bits, alle feil med et odde antall bitflipp, og lengre burst-feil med sannsynlighet 1 − (½)ʳ. Ethernet bruker CRC-32 — en 32-bits CRC — så selv for en kjempelang burst er sjansen for å gå glipp av feilen omtrent én på fire milliarder.

Når mange deler samme kabel

Hvis bare to noder er koblet sammen av en kabel, er det ingen tvil om hvem som får sende. Men hvis ti eller hundre deler samme medium — hvem får ordet, og når?

To typer lenker finnes: punkt-til-punkt og broadcast. En punkt-til-punkt-lenke har akkurat to ender — som en fiberlenke mellom en svitsj og en server. Her trengs det ingen koordinering. Men i en broadcast-lenke — som gammelt Ethernet med koaks, WiFi i luften, eller kablene i et sjakkbrett-oppsett — deler alle det samme fysiske mediet. Sender to samtidig, overlapper signalene og blir uleselige. Det kalles en kollisjon.

Hva vi egentlig ønsker oss

Den ideelle multiple-access-protokollen ville ha fire egenskaper: når én node vil sende, kan den bruke hele kanalen R. Når M noder vil sende, deler de rettferdig med R/M til hver. Ingen sentralisert master. Og den må være enkel å implementere. Dessverre er det ingen protokoll som oppnår alle fire samtidig — alt er kompromisser. Det finnes tre brede klasser med tilnærminger.

Klasse 1 — Kanalpartisjonering

Del kanalen i faste biter og gi hver node sin egen bit. I TDMA (Time Division Multiple Access) deles tiden i runder, og hver node får ett tidsluke i hver runde. I FDMA (Frequency Division) deles frekvensspekteret i bånd, og hver node får sitt eget bånd.

Dette er rettferdig ved høy last — ingen kollisjoner, garantert båndbredde. Men ved lav last er det sløsende. Hvis kun én av seks noder har noe å sende, må den vente på sitt tidsluke hver sjette gang, selv om de andre fem er tause. Den får bare R/6 selv om 5R/6 ligger ubrukt.

Klasse 2 — Random access

Motsatt filosofi: ikke del noe i det hele tatt. Når du har noe å sende, bare send det i full fart. Kolliderer det med noe annet — håndter det. Dette fungerer utmerket ved lav last, der en ensom node kan bruke hele kanalen. Men ved høy last øker kollisjonssannsynligheten, og stadig mer tid går til spille.

Slotted ALOHA — den enkleste random-access-ideen

Del tiden i like store slots, akkurat like lange som en ramme. Alle nodene er synkroniserte. Når en node har en ny ramme, sender den ved neste slot-start. Hvis bare den sender, er slot-et vellykket. Hvis to sender i samme slot, kolliderer de — og begge retransmitterer i en framtidig slot med sannsynlighet p til de lykkes.

Den maksimale effektiviteten til slotted ALOHA er 1/e ≈ 37%. Det betyr at selv i beste fall er 63 prosent av tiden enten kollisjoner eller tomme slots. Unslotted (ren) ALOHA er enda verre — bare 18 prosent.

CSMA — hør etter før du snakker

Den mest opplagte forbedringen: lytt på kanalen først. Hvis ingen snakker, send. Hvis noen snakker, vent. Carrier Sense Multiple Access. Den polite samtalemetoden.

Men selv med carrier sensing kan kollisjoner skje. Hvorfor? Propageringsforsinkelse. Signaler beveger seg raskt, men ikke uendelig raskt. Hvis node A begynner å sende, tar det en liten brøkdel av et sekund før signalet når node B i den andre enden av kabelen. I den tiden tror B at kanalen er ledig. B starter også å sende. Når signalene til slutt møtes — kollisjon. Jo lengre kabel, jo større vindu for denne typen feil.

CSMA/CD — og hør etter mens du snakker

Neste forbedring: oppdag kollisjonen mens den skjer, og avbryt sendingen. Collision Detection. Isteden for å fullføre en ramme som allerede er ødelagt, stopper du med en gang, sender et kort «jam-signal» slik at alle skjønner hva som skjedde, og prøver igjen senere. Det sparer masse tid, særlig på korte kabler.

Ethernet bruker CSMA/CD. Her er algoritmen i grove trekk:

1. NIC får et datagram fra nettverkslaget og lager en ramme.
2. Lytter på kanalen. Hvis ledig, begynner å sende. Hvis opptatt, venter til den blir ledig.
3. Om hele rammen går gjennom uten kollisjon — ferdig.
4. Om en kollisjon oppdages underveis, avbrytes sendingen og et jam-signal sendes.
5. NIC går inn i binær eksponentiell backoff: etter den m-te kollisjonen velges et tilfeldig tall K fra {0, 1, …, 2ᵐ−1}, og noden venter K · 512 bit-tider før den prøver på nytt. Flere kollisjoner → lengre forventet ventetid.

Klasse 3 — «Ta tur»

Prøv å få det beste fra begge verdener. I polling sender en master-node en invitasjon til hver slavenode etter tur: «Har du noe å sende? Vær så god.» I token passing sendes en spesiell liten melding (token) i ring mellom nodene, og du får bare sende når du har tokenet.

Disse metodene unngår både kollisjoner og sløsing ved lav last. Ulempene er polling-overhead, forsinkelse, og — mest kritisk — et single point of failure: mister du master-noden eller mister du tokenet, så stopper alt opp. Bluetooth og gammel Token Ring bruker varianter av dette.