Rutere og videresending

Hva nettverkslaget gjør

Transportlaget gir deg en illusjon av en direkte forbindelse mellom to prosesser. Nettverkslaget er den som faktisk må flytte pakkene over et mylder av forskjellige nettverk for å opprettholde den illusjonen.

Nettverkslaget kjører i hvert eneste Internett-tilkoblet apparat — ikke bare i routere, men også i endesystemer. På sendersiden tar det imot segmenter fra transportlaget, kapsler dem inn i datagrammer, og leverer dem til lenkelaget under. På mottakersiden gjør det det motsatte: trekker ut segmentet fra datagrammet og leverer det opp til transportlaget.

Men den virkelige jobben skjer i routerne. En router undersøker headerfelter i hvert eneste datagram som passerer gjennom den, og bestemmer — på nanosekunder — hvilken utport pakken skal sendes videre på. Denne prosessen gjentas i router etter router helt til pakken når målet.

To helt forskjellige jobber

Forwarding er det du gjør i hvert veikryss: «gitt at målet er Roma, tar jeg høyre.» Routing er å planlegge hele turen fra Trondheim til Roma før du setter deg i bilen.

Forskjellen mellom forwarding og routing er det første virkelige innsiktet i dette kapittelet, og hele resten av stoffet organiseres rundt det.

Forwarding er den lokale, per-pakke-operasjonen: en router mottar et datagram på en innport, slår opp destinasjonsadressen i en forwarding-tabell, og sender pakken videre ut på riktig utport. Dette må skje ekstremt raskt — på nanosekunder — fordi en 100 Gbps-lenke ikke venter på noen.

Routing er den nettverksglobale prosessen som bestemmer hvilke ruter som eksisterer i nettverket, og som fyller forwarding-tabellen med oppføringer. Rutingalgoritmer (OSPF, BGP) kjører i bakgrunnen og oppdaterer tabellene når topologien endres. Routing er langsomt — millisekunder til sekunder — men det er greit, fordi det skjer sjelden sammenlignet med forwarding.

To plan i en router

Det samme forwarding/routing-skillet manifesterer seg som en arkitektonisk deling inne i enhver moderne router: data plane for rask pakkeflytting, control plane for rutinglogikk.

Data plane er maskinvaren som faktisk flytter pakker fra innport til utport. Det opererer på nanosekunder, med dedikerte kretser som gjør tabelloppslag og switching uten å involvere routerens CPU.

Control plane er programvaren som bestemmer hva som skal stå i forwarding-tabellen. To modeller finnes:

• Per-router kontroll — Hver router kjører sin egen rutingalgoritme og snakker med naboene via protokoller som OSPF og BGP. Den tradisjonelle modellen.
• SDN (sentralisert) — En fjernkontroller beregner rutene for hele nettverket og pusher forwarding-tabeller ned til routerne. Dominerer i datasentre.

Hvorfor Internett er så «dumt»

Man kunne tenkt seg et nettverk som garanterer levering, båndbredde og lav forsinkelse. Internett gjør ingen av delene. Det er «best effort» — og det er med vilje.

Internetts nettverkslag lover ingenting. Ingen garanti for at pakken kommer fram. Ingen garanti for rekkefølge, timing, eller båndbredde. IP-modellen er best effort: vi prøver å levere pakken din, men vi lover ingenting.

Dette stod i skarp kontrast til ATM-nettverkene som ble utviklet på 1990-tallet, som forsøkte å gi rike garantier. Men historien ga Internett rett:

Tre ting forklarer hvorfor best effort fungerer:

• Enkelhet skalerer. Routere som bare slår opp en destinasjon og sender videre kan bygges billig og raskt av hvem som helst.
• Overprovisjonering fungerer. Båndbredde har blitt billig nok til at real-time-applikasjoner som video og tale fungerer «godt nok, mesteparten av tiden.»
• CDN-er og congestion control hjelper. Innhold replikeres nær brukerne, og TCP forhindrer nettverket fra å kollapse.

Anatomien til en router

En router består av fire hoveddeler: innporter, en switching fabric, utporter, og en routing-prosessor. De tre første er data plane; den fjerde er control plane.

En innport gjør tre ting før en pakke går videre. Først linjeavslutning (mottak av bits fra fiberen). Så link-lag-prosessering (pakke bits ut som Ethernet-rammer). Til slutt det viktige: oppslag i forwarding-tabellen for å bestemme utport. Dette siste skjer lokalt i innporten, uten å involvere CPU-en.

Oppslaget følger et mønster som er fundamentalt for hele nettverkslaget: match plus action. Se på felt i headeren, finn en matchende rad i tabellen, utfør handlingen (typisk «send ut på interface 3»). Denne strukturen finnes overalt — fra enkel destinasjonsbasert forwarding til mer avanserte regler i SDN.

Hvilken oppføring vinner?

Forwarding-tabellen inneholder prefikser, ikke enkeltadresser. Når flere prefikser matcher, vinner det lengste — fordi et lengre prefiks er mer spesifikt.

En forwarding-tabell har typisk en kvart million oppføringer. Hver oppføring er et prefiks — for eksempel 200.23.16.0/20 — som dekker alle adresser der de første 20 bitene matcher. Det store spørsmålet er: hva gjør routeren hvis en destinasjonsadresse matcher flere oppføringer?

Svaret: velg oppføringen med lengst prefiks. En /24 gjelder 256 adresser; en /28 gjelder bare 16. Hvis begge matcher, er /28 mer presis og vinner. Dette er longest prefix matching (LPM), og det er det som gjør hierarkisk adressering og rute-aggregering mulig.

I praksis gjøres LPM i maskinvare, i ternary content-addressable memory (TCAM). En TCAM slår opp en adresse på én klokkesyklus uansett tabellstørrelse, fordi alle oppføringer sammenlignes parallelt. Cisco Catalyst-svitsjer har rundt 1 million oppføringer i TCAM.

De tre generasjonene

Når innporten har bestemt utporten, må pakken fysisk flyttes dit. Switching fabric-en gjør dette, og det finnes tre hoveddesign — en evolusjon fra tregt til ekstremt raskt.

Generasjon 1: via minne. Pakken kopieres fra innport til systemminnet, CPU-en slår opp, og pakken kopieres til utporten. To busskrysninger per pakke — hastigheten begrenses av minnebåndbredden. Fungerte for noen få megabit i sekundet.

Generasjon 2: via buss. Pakker overføres direkte fra innport-minne til utport-minne over en delt buss, uten CPU-involvering. Men bussen er delt — bus contention — så bare én pakke kan krysse om gangen. Cisco 5600 bruker en 32 Gbps-buss.

Generasjon 3: sammenkoblingsnettverk. En crossbar eller flerstegs-svitsj lar flere pakker krysse parallelt, så lenge de går til forskjellige utporter. For enda høyere ytelse deler moderne routere pakker opp i celler og sender dem over flere parallelle fabric planes samtidig. Cisco CRS: 8 planes, hundrevis av Tbps.

Når pakker må vente

Selv med en perfekt switching fabric oppstår køer. Det som skjer i køene — hvem som droppes og hvem som går først — er der nettverksnøytralitet får teknisk innhold.

Input-køer og HOL-blokkering

Hvis switching fabric er tregere enn summen av innportene, kan køer bygge seg opp ved innportene. Det verste som da skjer er Head-of-Line (HOL) blocking: pakken først i køen venter på en opptatt utport, og blokkerer dermed pakkene bak seg — selv om deres utporter er ledige.

Output-køer

Den vanligste køtypen er ved utporten. Når tre innporter på 10 Gbps alle vil sende til samme utport, må noe vente. Her oppstår to spørsmål: (1) hva droppes når køen er full? (2) hvilken pakke sendes først?

Bufferstørrelse

En gammel tommelfingerregel (RFC 3439) sier at bufferen bør være omtrent RTT × C (for eksempel 250 ms × 10 Gbps = 2,5 Gbit). Nyere forskning anbefaler RTT·C / √N der N er antall flows — fordi for store buffere skaper bufferbloat og ødelegger latens for real-time-trafikk.

Buffer management

Tail drop: dropp pakken som nettopp ankom. RED (Random Early Detection): dropp pakker tilfeldig før køen er full for å signalisere congestion. ECN: marker pakker uten å droppe dem.

Scheduling — hvem går først?

Weighted Fair Queueing (WFQ) generaliserer round robin ved å gi hver klasse en vekt w_i, slik at klasse i får andelen w_i / Σw_j av lenkekapasiteten. Det er slik du kan garantere minimum båndbredde til en gitt trafikktype uten å sulte de andre.