yoel caspersen blog bloghoved

Software-router del 5: Linux som BNG

Sidste gang kiggede vi på, hvilke udfordringer man som netværkstekniker støder på, når man vil anvende en Linux-server som Border Network Gateway, også kendt som en BNG.

Den største udfordring er, at Linux anvender et virtuelt netværksinterface for hvert VLAN-tag, BNG'en skal håndtere, og det skalerer ikke særlig godt. I dag skal vi derfor se på, hvordan man kan løse det problem ved at udvikle et program, der kan fjerne og indsætte VLAN-tags.

Kernel eller user space?

Når man som softwareudvikler skal bygge et Linux-baseret serverprogram, har det i mange år været god latin at lade kernen håndtere det beskidte arbejde, når der skal skrives til eller læses fra en disk eller et netkort.

Det reducerer stort set al I/O til varianter af systemkaldene read(2) og write(2), idet socket descriptors og file descriptors i mange henseender kan behandles ens.

Linux-kernen kommer med en komplet netværksstak, der både kan håndtere alle tænkelige og utænkelige protokoller, herunder TCP og UDP, og der findes et par tricks, man kan bruge, hvis man skal flytte bits fra et sted i kernen til et andet uden context switching, herunder sendfile(2) og splice(2).

Et godt eksempel på en klassisk server-arkitektur finder man i webserveren Apache, som forker et antal worker-processer ved opstart. Hver brugers forespørgsel mod webserveren håndteres af sin egen worker-proces, og det giver i sagens natur en flaskehals, når man skal håndtere mange samtidige forespørgsler, da hver proces medfører overhead og skal dele sin CPU-tid med andre processer på serveren.

Det ledte i 1999 til Dan Kegels glimrende skriv The C10K problem, der handlede om, hvilke teknikker, man kunne bruge for at komme op på 10.000 samtidige brugere på en webserver.

Konklusionen kunne i korte træk koges ned til følgende:

  • Anvend asynkrone I/O-kald (undgå blocking)
  • Tilpas antallet af processer/tråde til antallet af CPU-kerner
  • Lad flere brugere dele samme proces/tråd

Og dermed også et farvel til Apache-modellen - man havde brug for en ny webserver, der kunne skalere bedre, og det ledte i 2004 til lanceringen af Nginx, der som bekendt har fortrængt Apache fra store dele af markedet.

I 2013 kom Robert Graham på banen med en interessant nyfortolkning af C10K-problemet: C10M, eller hvordan vi får en server til at håndtere 10 millioner samtidige brugere ved at bypasse Linux-kernen, da den i sig selv udgør en flaskehals.

Grahams løsningsforslag er interessant, fordi han foreslår, vi opdeler en Linux-server i et control plane, som er Linux, som vi kender det, og et data plane, som er dedikerede user space applikationer, der får tildelt dedikerede ressourcer uden om kernen, herunder CPU og netkort.

Det minder om noget, vi har set før: Langt de fleste ISP-routere består af et control plane i form af en lille server, der håndterer BGP, SNMP og SSH, og et data plane i form af et ASIC, der forwarder netværkspakker.

Ved at tilpasse en Linux-server efter Grahams model, kan vi opnå en performance, der minder om den, vi ser i dedikeret hardware, men til gengæld har vi stadigvæk en fleksibel Linux-server, vi kan bruge til management og debugging, og vi skærer den dyre specialhardware ud af ligningen og erstatter den med special-software.

Hvis man vil bygge et user space program, som kan tilgå netkortet uden om kernen, findes der en række frameworks, der gør det relativt nemt, herunder Intels DPDK og ntops PF_RING.

Man bør også optimere sit program, så memory lookups på tværs af CPU'er så vidt muligt undgås - allerhelst skal man holde programmet på samme CPU-kerne og anvende CPU'ens cache så meget som overhovedet muligt.

Nu handler C10M primært om webservers, men principperne kan genbruges i software-routing, som i de senere år har gennemgået en voldsom udvikling, ikke mindst drevet af datacenter-markedet og den stigende brug af virtualisering.

Vi har således et valg, vi skal træffe, hvis vi skal bygge en Linux-baseret BNG:

  • Brug Linux-kernen som den er
  • Bypass Linux-kernen

Og som foreslået i kommentarsporet på sidste indlæg er der også en mellemvej:

  • Brug XDP, hvor vi injecter vores logik i kernens netværksstak via et såkaldt XDP-program

At bruge Linux-kernen, som vi har gjort indtil nu, er ikke nødvendigvis en dårlig løsning, for der er også sket meget inden for udviklingen af Linux-kernen de senere år, og det sparer os for megen tid og besvær, hvis vi kan bruge den til forwarding af pakker.

Vi kan muligvis leve med, at vi ikke udnytter hardwaren til det yderste, hvis det til gengæld kan spare os for mange timers udviklingsarbejde.

Vi skal dog stadig have håndteret vores VLANs på en fornuftig måde, og det giver således mening at lave et program, der fjerner VLAN-tags fra pakker, der kommer fra vores brugere, indsætter VLAN-tags på pakker, der skal sendes til vores brugere, og samtidig filtrerer trafikken, så brugerne isoleres fra hinanden på layer 2-niveau.

Kort fortalt, vi skal bruge et VLAN-filter.

En prototype

I første omgang skal vi have afklaret, om konceptet overhovedet holder. Kan vi bygge et VLAN-filter, der virker i praksis - og sidenhen optimere programmets performance?

Til vores prototype vil jeg tillade mig at se stort på antallet af context switches, og vores VLAN-filter skal derfor køre i user space.

Vi bruger to Linux-bridges, som vi forbinder vha. vores VLAN-filter, der installerer et TAP-interface i hver bridge:

Illustration: Yoel Caspersen

TAP-interfaces tillader vores program at modtage og sende hele ethernet frames, hvor vi kan manipulere med VLAN headers.

Den første bridge, br0, er bruger-trafik, der indeholder VLAN-tags. Der er kun to interfaces i br0, så den skal ikke spilde tid på at lære MAC-adresser.

Den anden bridge, br1, er trafik, der er renset for VLAN-tags, og br1 har en IP-adresse og agerer således default gateway for vores brugere. br1 skal anvende ARP, og det er vores opgave at filtrere forespørgslerne, så de kun sendes ud til de relevante brugere.

Vores VLAN-filter skal derfor hente en liste med bruger-VLANs og tilhørende IP-adresser fra vores management-system.

I prototypen, som er skrevet i C++, loader vi listen fra en tekst-fil, og i første omgang koncentrerer vi os om IPv4.

VLAN-filter starter tre tråde - en til trafik den ene vej, en til trafik den anden vej og en tråd, der løbende opdaterer VLAN-listen.

VLAN-listen omsættes til et kompakt hashmap, der kan nå at ligge i CPU'ens cache:

unordered_map<uint32_t, uint32_t> ipv4_incoming;

I ipv4_incoming er nøglen en IP-adresse, og værdien er outer og inner VLAN, der pakkes i en variabel af typen uint32_t.

Pakker, der modtages fra br1 og skal sendes til en bruger via br0, matches mod ipv4_incoming vha. pakkens destinations-IP, og de to VLAN-tags indsættes i pakkens header, hvorefter pakken sendes ud på br0.

Pakker, der modtages fra en bruger via br0, strippes for VLAN-tags og sendes ud på br1. I prototypen undlader vi i første omgang at checke pakkens source IP, men det bør indføres i en senere iteration af programmet, så vores BNG beskyttes mod forsøg på IP spoofing.

DHCP

I dag indsætter vores BNG DHCP Option 82, når den relayer en DHCP Discover-forespørgsel til vores DHCP-servere. DHCP Option 82 indeholder blandt andet outer og inner VLAN-tags, og det bruger vi til at finde brugeren i vores database, hvorefter vi uddeler den korrekte IP-adresse.

Derfor skal vi enten lade vores VLAN-filter agere DHCP relay i sig selv, eller også skal det indsætte en DHCP Option 82 inklusive outer og inner VLAN-tags i en DHCP Discover-forespørgsel, der kommer fra en bruger.

ARP

ARP-forespørgsler kan både komme fra en bruger og fra BNG'en selv. Når vi modtager en ARP-pakke fra en bruger via br0, stripper vi VLAN-tags og sender pakken videre ud på br1. Når vi modtager en ARP-pakke via br1, finder vi modtageren af svaret i vores hashmap og indsætter de korrekte VLAN-tags, hvorefter vi sender pakken ud på br0.

På den måde vil ARP-pakker kun blive sendt til de relevante brugere. I en senere iteration af VLAN-filteret skal ARP-pakker, der modtages via br0, også checkes for korrekt source IP - det er dog udeladt i vores første prototype.

Unicast

Almindelig unicast-trafik, der modtages fra en bruger via br0, sendes videre ud på br1 uden VLAN-tags. Når vi modtager unicast-trafik via br1, finder vi brugeren i vores hashmap, sætter korrekte VLAN-tags på pakken og sender den ud på br0.

Også her gælder det, at en senere version af filteret skal filtrere for korrekt source IP, når der kommer en pakke fra en bruger.

IPv6

IPv6 er mere tricky end IPv4. Dels skal vi tage hensyn til, at brugeren har mere end en enkelt IP-adresse, og dels skal vi også tage højde for link-local-adresser, som vi ikke kender, før udstyret tilsluttes. Vi venter derfor med at indbygge IPv6-support, til vi ved, om konceptet virker i praksis.

Performance

Vores prototype er på nuværende tidspunkt ca. 80 % klar, og vi ved derfor endnu ikke, hvor godt VLAN-filteret vil performe, når det udsættes for rigtig trafik.

Der er dog en god sandsynlighed for, at vi relativt hurtigt rammer loftet, da IP-pakker modtages i kernel space, behandles i user space og sendes videre i kernel space igen.

Vi kan derfor muligvis hente en forbedring, hvis vi bygger et kernemodul, så al behandling kan foregå i kernel space - men den bedste løsning er nok at kigge lidt nærmere på XDP.

Det er dog et projekt, vi gemmer til en regnvejrsdag.

Relateret indhold

Kommentarer (18)
Jesper Brouer

Din userspace løsning kommer ikke til at skalere eller performe.

Skal jeg ikke bare hjælpe dig med at kode et XDP program?...
(Det er ikke så svært ... sagde opfinderen af XDP ;-))

Et super simpelt eksempel (der parser Q-in-Q) og håndtere IPv6:
https://github.com/torvalds/linux/blob/master/samples/bpf/xdp1_kern.c

Et mere avanceret eksempel, der også load-balancere over CPUerne, og håndtere Q-inQ og IPv6:
https://github.com/torvalds/linux/blob/master/samples/bpf/xdp_redirect_c...

Yoel Caspersen Blogger

I en perfekt verden ville man starte med supportere IPv6 også kan man kigge på legacy protokoller som IPv4 :-P

Damn you business case.

Du har naturligvis ret.

Lad os se på, hvad der skal til for at understøtte IPv6.

En IPv6-enabled CPE starter med at forhandle en /64 point-to-point-adresse vha. Stateless Address Autoconfiguration (SLAAC).

Det indebærer, at CPE'en først sender et link-local router solicitation request, som vores BNG (br1) svarer på. For at sikre, at svaret når ud til det rigtige bruger-VLAN og dermed den rigtige CPE, og kun den, skal vi vedligeholde en cache over observerede link-local-adresser.

Derefter spørger den efter flere IPv6-adresser vha DHCPv6. CPE'en modtager en /64 IPv6-adresse til sig selv samt et /48 delegated prefix, som den kan subnette og uddele til klienter på LAN-siden.

Ligesom for IPv4 har vores DHCPv6-server brug for at vide, hvilket VLAN en forespørgsel kommer fra. Derfor skal vores VLAN-filter enten indsætte DHCPv6 option 18 (interface ID, modsvarer Option 82 for DHCP) og sende pakken videre til br1, eller også skal vores VLAN-filter selv agere DHCPv6 relay.

Ud over at vi skal vedligeholde en cache med observerede link-local-adresser, er der en anden afgørende forskel på IPv4-filtering og IPv6-filtrering.

På IPv4 kan vi tillade os den luksus at gå ud fra, vores klient kun har en enkelt IP-adresse, eller i hvert fald har så få, at de alle sammen kan få lov at ligge i vores hashmap ipv4_incoming.

På IPv6 er adresserummet så stort, at det er udelukket at have alle klientens IPv6-adresser liggende.

Alene fordi klienten har fået et /48 delegated prefix, er der 2^(128-48) = 1,20892582*10E24 mulige kombinationer.

Men der findes en løsning: Vi kan have et hashmap, hvor vi kun gemmer de første 48 bit i klientens /48 delegated prefix, og et andet hashmap, hvor vi gemmer de første 64 bit i klientens /64 point-to-point-adresse.

Når vi så modtager en IPv6-pakke, kan vi nøjes med at søge på de første 48 bit af destinationsadressen i det første hashmap, og hvis det ikke giver et match, søger vi på de første 64 bit i det andet hashmap.

Vi kan yderligere reducere størrelsen på vores hashmaps, hvis vi kan lave nogle antagelser omkring de tildelte scopes og point-to-point-adresser - hvis de fx alle sammen kommer fra den samme /29 IPv6-blok fra RIPE, kan vi nøjes med at matche bits fra 29 til 48 hhv. 29 til 64.

Det er muligt, vores hashmap kan komprimeres yderligere, hvis vi kan lave nogle flere antagelser omkring de forskellige typer trafik.

Hvis en BNG skal håndtere fx 5.000 kunder, vil et hashmap med delegated prefixes have en størrelse på ((48-29 bits) / 8) * 5000 ~ 20 KB, hvilket fint kan ligge i cachen på CPU'en.

Så vidt jeg kan se, burde ovenstående være nok til at få VLAN-filteret til at understøtte IPv6.

Yoel Caspersen Blogger

Skal jeg ikke bare hjælpe dig med at kode et XDP program?...
(Det er ikke så svært ... sagde opfinderen af XDP ;-))

Den regnvejrsdag kom hurtigere end forventet. Jeg må hellere skynde mig at sige ja tak til dit tilbud ;-)

Tak for det fine eksempel - jeg har haft lidt svært ved at opstøve up-to-date dokumentation for XDP under research til dette indlæg. Har du et godt bud på dette - eller skal det primært findes i kildekoden til Linux-kernen?

Næste spørgsmål:

Hvis vi bygger en BNG med XDP, giver det så mening at strippe outer og inner VLAN-tags (hvilket jo vil inkludere flytning af header-data i den ene eller den anden retning på hver eneste pakke), bør man blot nulstille VLAN-tags til en kendt værdi (fx outer VLAN 1 og inner VLAN 1), eller kan man sende pakkerne videre til forwarding uden at røre ved VLAN-tags overhovedet?

Jesper Brouer

Hvis vi bygger en BNG med XDP, giver det så mening at strippe outer og inner VLAN-tags (hvilket jo vil inkludere flytning af header-data i den ene eller den anden retning på hver eneste pakke), bør man blot nulstille VLAN-tags til en kendt værdi (fx outer VLAN 1 og inner VLAN 1), eller kan man sende pakkerne videre til forwarding uden at røre ved VLAN-tags overhovedet?
Yoel Caspersen

Jeg skal lige forstå funktionen af din BNG enhed... jeg læser lige din anden blog-post, og så tager vi diskussionen via email (da jeg skal have en masse detaljer omkring versioner af kernen og LLVM-compileren).

Vi bør nok fjerne nogle VLAN tags før vi laver forwarding. Men i princippet kan man blot indsætte VLAN 0, ihvertfald for enkelt-tagged VLANs. Jeg er ret parktisk orienteret, så lad os prøve os frem...

Yoel Caspersen Blogger
Yoel Caspersen Blogger

Er det en antagelse eller har du testet det (tænker performance-wise)?
Jeg synes heller ikke det er optimalt, men kunne det fungere?

Jeg har ikke testet det personligt, for målet er at se, om vi i sidste ende kan lave en bedre løsning end den, vi har. Umiddelbart synes jeg bedre om vores hardware-løsning, med dens fejl og mangler, end en løsning baseret på > 1000 VLAN-interfaces på Linux.

Baldur Norddahl har vist tidligere fortalt om nogle forsøg med mange VLAN-interfaces, og derudover er der på sidste indlæg en kommentar fra Benny Lyne Amorsen, der scriptede en hurtig test og identificerede i hvert fald to programmer, der ikke bryder sig om mange interfaces.

Mit gæt er, at det muligvis ville fungere, hvis man tweaker sit setup og holder sig fra bestemte user space-programmer (som fx NetworkManager).

Jeg gætter dog på, man løber ind i nogle gevaldige performance-problemer, når en pakke skal ind gennem Linux-kernen hvis der er mange interfaces på maskinen, men det er et rent gæt, og det er muligt, jeg tager fejl.

Benny Lyne Amorsen

Jeg er overbevist om at en løsning baseret på rigtige VLANs vil fungere i al fald til 5-cifrede antal VLANs. Jeg er især overbevist om at Linux-kernelen ikke har problemer med at håndtere sådanne antal.

Der er simpelthen for mange som bruger den slags i dag, til virtualisering o.lign., til at Linux kan tillade sig at performe dårligt med mange interfaces.

Men ja, man skal ikke køre NetworkManager eller lade systemd håndtere interfaces.

Baldur Norddahl

Kernen begynder simpelthen at fejle. Nye interface kan ikke oprettes medmindre man forsøger gentagne gange og tilsvarende når de skal nedlægges. Jeg har ikke målt på om den kan flytte trafikken, men vil pointere at man er ude i noget ebtables magik for at simulere den nødvendige funktionalitet. Kernen er ikke bygget til det her.

Mange VM på en maskine er typisk implementeret med openvswitch og selv da er det bestemt ikke smertefrit, hvis du skal have tusinder kørende.

Baldur Norddahl

Tænk lidt over følgende problemstilling. Du skal angive de nødvendige kommandoer (ip link add, ip addr add, iptables, ebtables etc) for at opnå følgende:

Der er fire kunder der deler subnet 10.0.0.0/26. Default gateway er 10.0.0.1.

Kunde A har outer vlan 100 inner vlan 2 og ip adresse 10.0.0.2.

Kunde B har outer vlan 100 inner vlan 3 og ip adresse 10.0.0.3.

Kunde C har outer vlan 101 inner vlan 2 og ip adresse 10.0.0.4.

Kunde D har outer vlan 101 inner vlan 3 og ip adresse 10.0.0.5.

Kunderne må ikke kunne kommunikere direkte med hinanden. Linux må ikke sende trafik til den forkerte, herunder ikke arp trafik. DHCP skal have option82 på og sendes videre (Den er tarvelig for ingen af de gængse DHCP løsninger kan dette).

Der skal endvidere etableres en ipv6 løsning, der supporter DHCPv6-PD samt statisk opsætning.

Der er en årsag til at Yoel kigger på at udvikle software.

Baldur Norddahl

Hvis det er opgaven, så virker det mere oplagt at vælge RFC3069 og gøre det hele på layer-3. Det gør samtidigt IPv6 enkelt; IPv6 behøver ingen krumspring i det design.

Du har misset at blogindlæg og debattråd handler om hvordan man kan implementere RFC3069 på en skalerbar måde på Linux. IPv6 er desværre ikke nemmere end IPv4 her, tværtimod.

Benny Lyne Amorsen

RFC3069 er baseret på at BNG kører layer 3 og evt. faker layer 2 med proxy-arp hvis man har behov for kommunikation direkte mellem CPE'er.

Det sættes op ved bare at lave en hel masse interfaces i Linux-kernelen og så lade den gøre hvad den er bedst til. Der skal ikke bøvles med bridging eller vlan-oversættelse eller arp-guard eller dhcp-guard eller noget som helst.

IPv6 er trivielt i den løsning fordi proxy-arp-delen bliver overflødig. Det er bare IPv6 med nogle tusinde interfaces på.

Log ind eller Opret konto for at kommentere