BGP-tabel bereikt 512k-limiet in oudere routers

▼ Het is nooit een goed tegen wanneer de gewone pers schrijft over een BGP-gerelateerd probleem, zoals vorige week: Omvangrijke storing internet legt websites wereldwijd plat (de Volkskrant). Het probleem is dat de BGP-tabel de FIB-limiet van 512k in sommige oudere routers bereikte. Een flink aantal onbereikbaarsheids- en vertragingsproblemen werden aan het routerprobleem gekoppeld, maar het is niet duidelijk in hoeverre dat terecht is.

Wat is een FIB en waarom is die gelimiteerd tot 512k (524288) prefixen?

BGP-routers hebben (minimaal) drie verschillende tabellen war IP-adresprefixen opgeslagen worden, tezamen met het "next hop" adres waar de pakketten naartoe moeten. (Een prefix is het gedeelte van een IP-adres dat alle adressen in een reeks gemeen hebben, dus bij de reeks 192.168.0.0 - 192.168.255.255 is de prefix 192.168.0.0/16, waarbij de 16 aangeeft dat de eerste 16 bits tot de prefix behoren.)

Die drie tabellen zijn: de BGP RIB, de hoofdroutingtabel / RIB en de FIB. De BGP Routing Information Base verzamelt alle informatie ontvangen over BGP die niet direct uitgefilterd wordt. Dus als je twee ISPs hebt, dan sturen beide alle prefixen van alle netwerken in de wereld die momenteel bereikbaar zijn. Dat wil zeggen dat je router twee exemplaren van iedere prefix heeft, één met een next-hopadres dat verwijst naar ISP A en één met een next hop die verwijst naar ISP B.

Voor iedere prefix bepaalt BGP dan welk pad beter is en stuurt de prefix en het next-hopadres dat naar A of B wijst naar de hoofdroutingtabel. De hoofdroutingtabel bevat ook niet-BGP routinginformatie. In grote netwerken kunnen interne routes en routes naar klanten in de duizenden of tienduizenden lopen.

Als laatste is er de Forwarding Information Base (FIB), die samengesteld wordt uit de informatie in de hoofdroutingtabel. De FIB wordt gebruikt om pakketten daadwerkelijk naar het juiste next-hopadres te versturen. Sommige routers gebruiken RAM om de FIB in op te slaan, andere gebruiken Ternary Content Addressable Memory. RAM kan aardig groot zijn tegenwoordig, en er is normaal niet een vaste limiet aan hoeveel prefixen erin passen, dit hangt af van welke andere processen binnen de router ook geheugen gebruiken. Maar TCAMs zijn speciale geheugens met een klein beetje rekenkracht. Het komt erop neer dat je een prefix kan laten zien aan een TCAM en dan vertelt de TCAM op welk adres die prefix opgeslagen is—je hoeft niet stap voor stap het hele geheugen door te zoeken. Dit betekent dat TCAMs heel snel zijn, maar ze zijn ook duurder dan RAM en worden vrij heet. Zodoende is de grootte van een TCAM beperkt.

Niks nieuws onder de zon

Ooit hadden Cisco 6500 en 7600 modulaire routers/switches supervisormodules met een TCAM-limiet van 256k. Dus toen in 2008 de routingtabel groeide tot 256k moesten mensen snel upgraden. Als ze destijds nieuwe supervisormodules gekocht hebben die 512k aankunnen, dan hebben ze zes jaar nut van die nieuwe modules gehad. Vandaar ook Geoff Huston's opmerking “Niks in BGP ziet eruit alsof het aan het smelten is”.

Omdat ieder netwerk een ander aantal interne prefixen heeft en er ook kleine verschillen zijn in de aantallen prefixen die verschillende ISPs via BGP aan hun klanten adverteren krijgen verschillende mensen op verschillende momenten last van dit probleem. Daarnaast worden TCAMs vaak in verschillende delen onderverdeeld (gepartitioneerd), bijvoorbeeld één deel voor de IPv4-routingtabel, één voor de IPv6-routingtabel, één voor MPLS, één om te filteren... In sommige gevallen kan het probleem op de lange baan geschoven worden door de TCAM anders te partitioneren.

Een andere oplossing is het uitfilteren van prefixen in BGP. Het probleem daarmee is dat je dan connectiviteit naar de betreffende prefixen kwijtraakt. Als je netwerk niet enorm is dan is dat op te lossen door een defaultroute naar je ISP / één van je ISPs in te stellen als veiligheidsnet. Wat ik lang geleden deed toen ik BGP runde op eigenlijk veel te kleine routers was simpelweg alle AS-paden langer dan vijf ASen uitfilteren van allebei onze ISPs. Als dan één ISP een kort pad heeft en de andere een lang pad werd het lange pad uitgefilterd en ging het verkeer via het korte pad, wat toch al de bedoeling was. Als beide een lang pad hadden dan werden beide gefilterd en ging het verkeer via de defaultroute. In dat geval was er weinig kans dat het een belangrijke bestemming was die door de defaultroute via een omweg trager werd.

Maar grote netwerken hebben niemand waarnaar ze een defaultroute kunnen laten wijzen. Dus die moeten recentere routers gebruiken, wat ze gewoonlijk ook doen. Het is echter niet ongehoord dat oudere apparatuur in een ver hoekje van het netwerk z'n laatste jaren slijt, dus ook grotere netwerken kunnen tot op zekere hoogte problemen hebben.

Mea culpa

Tijdens mijn BGP-cursussen waarschuw ik de cursisten altijd dat ze routers moeten kopen die groot genoeg zijn om de voorziene groei van de BGP-tabel bij te kunnen houden. Maar ik had duidelijker moeten zijn en op BGPexpert.com een waarschuwing moeten zetten. Cisco deed dit gelukkig wel: The Size of the Internet Global Routing Table and Its Potential Side Effects.

De toekomst

Geoff Huston verwacht dat de IPv4-routingtabel de 1 miljoen prefixen zal bereiken in 2019 en beveelt aan om routers te kopen die minstens 2 miljoen prefixen aankunnen. Helaas is het niet altijd duidelijk hoeveel prefixen een router aankan, vooral wanneer de TCAM gebruikt wordt voor meer dan alleen de IPv4 FIB. Zorg dat je hier goede informatie over hebt voordat je je geld uitgeeft. En hou het wekelijkse routing table report in de gaten zodat je op tijd actie kan ondernemen wanneer de BGP-tabel in de buurt van de limieten van je routers begint te komen.

Zie ook:

• Global Internet Routing Table Reaches 512k Milestone (Cisco blog)
• What caused today's Internet hiccup (BGPmon)
• Internet Touches Half Million Routes: Outages Possible Next Week (Renesys blog)

Permalink - posted 2014-08-19 - 🇺🇸 English version

"Niks in BGP ziet eruit alsof het aan het smelten is"

▼ Een deel van de lezers van ISP Today zal wel eens naar een RIPE meeting geweest zijn, waar medewerkers van ISPs en internet-experts van verschillend pluimage bij elkaar komen om het wel en wee van het internet te bespreken. In Amerika vervullen de bijeenkomsten van de North American Network Operators Group (NANOG) een soortgelijke functie. Een bekend gezicht bij zowel RIPE als NANOG is Geoff Huston, Chief Scientist van APNIC, de Aziatisch/Australische tegenhanger van RIPE.

Op de NANOG-meeting in februari presenteerde Geoff "BGP in 2013", een overzicht van hoe het Border Gateway Protocol ervoor stond vorig jaar. BGP is het routingprotocol dat de routers van verschillende ISPs met elkaar spreken zodat de pakketten van een klant van ISP A zich een weg weten te vinden naar een klant van ISP B. Iedere ISP "adverteert" dus zijn IP-adresreeksen in BGP, wat een totaal van ongeveer een half miljoen adresblokken (prefixen) oplevert die de BGP-routers van verschillende ISPs met elkaar uitwisselen.

Toen ik in 1995 met BGP begon was dit nog 30 duizend. De groei van de BGP-tabel is al lang een punt van zorg. In 2006 organiseerde de Internet Architecture Board, een soort technische raad van toezicht van de IETF, een bijeenkomst over dit onderwerp in Amsterdam. Geoff Huston ziet echter geen problemen op de korte/middellange termijn: "Niks in BGP ziet eruit alsof het aan het smelten is."

Opmerkelijk genoeg was de groei in het aantal BGP-prefixen in 2013 met 11% niet noemenswaardig lager dan in voorgaande jaren, ondanks het feit dat APNIC en het RIPE NCC al in respectievelijk 2011 en 2012 door hun normale voorraden IPv4-adressen heen waren en ISPs alleen nog één laatste blok van 1024 adressen konden krijgen. Maar als je kijkt naar het aantal losse adressen dat in BGP geadverteerd wordt is de groei wel minder. De adresblokken zijn dus kleiner geworden met het opraken van de IPv4.

Irritant genoeg bestaat de helft van de half miljoen prefixen die BGP-routers in hun tabellen moeten bewaren uit kleine adresblokken (lange prefixen) die vallen binnen een groter blok (korte prefix) die ook in de BGP-tabel aanwezig is. Een beetje alsof er onder het bord "Noord-Holland" ook nog bordjes "Amsterdam" en "Alkmaar" zitten. Nogal overbodig, maar het neemt wel schaarse ruimte in. Vervolgens blijkt dat van de BGP updates, de pakketten die BGP-routers elkaar sturen als er wat verandert, 80% gaat over die gedeaggregeerde prefixen!

Maar de grafiek uit Geoff Huston's presentatie die me echt versteld deed staan is deze, die de Wet van Moore laat zien versus de groei in BGP:

Gordon Moore, één van de oprichters van Intel, stelde in 1965 dat het aantal transistors in een chip iedere twee jaar zou verdubbelen. Met twee keer zo veel transistors kan je in principe twee keer zoveel werk in dezelfde tijd doen, of hetzelfde werk twee keer zo snel.

Zolang de BGP-tabel minder snel groeit dan de chips sneller worden zitten we dus goed, zou je zeggen. Maar die gedachte gaat uit van de aanname dat twee keer zoveel prefixen in de BGP-tabel twee keer zoveel werk betekent. Voor de CPU die het BGP-protocol runt is dat wel (ongeveer) waar, maar dit geldt niet voor de hardware die voor het daadwerkelijk doorsturen van IP-pakketten zorgt. Dit is vaak een ASIC (application specific integrated circuit, een chip gemaakt voor een specifieke taak) die voor ieder pakketje de hele tabel door moet om te vinden binnen welke prefix het bestemmingsadres van het pakket valt. Het doorzoeken van een twee keer zo grote tabel kost niet zo heel veel extra tijd, maar die grotere tabel neem wel twee keer zoveel speciaal, snel geheugen in beslag. Hierin wordt de zogenaamde "forwarding information base" (FIB) opgeslagen.

Het probleem is echter dat als de router sneller wordt en meer pakketten per seconde moet routeren/forwarden, het FIB-geheugen ook sneller moet worden. Groter en sneller is natuurlijk geen goede (of goedkope) combinatie. Het lijkt er niet op dat we op korte termijn in de problemen zullen raken door deze ontwikkelingen, maar het zou toch wel erg prettig zijn om van al die onnodig gedeaggregeerde prefixen af te komen, om te voorkomen dat routers onnodig snel veel duurder worden.

Tot zover IPv4. Hoe zit het met IPv6? Dat groeit, iets sneller dan IPv4, maar niet overdreven hard. In het huidige tempo haalt IPv6 IPv4 in in het jaar 2030. Wel neemt de deaggregatie in IPv6 toe richting de 50% waarop IPv4 al een tijd zit.

Geoff's presentatie is hier te vinden, een video van zijn verhaal op de NANOG website, of lees Addressing 2013 en vooral BGP in 2013 - The Churn Report op zijn blog, waar hij maandelijks een gedegen verhaal plaatst.

Dit artikel is ook geplaatst op ISP Today.

Permalink - posted 2014-07-17 - 🇺🇸 English version

Nu de IPv4 ook op is in Noord-Amerika, gaan we IPv4 verhandelen, vertalen of toch overstappen op IPv6?

▼ Ook ARIN, de instantie die in Noord-Amerika IP-adressen uitdeelt, is door z'n normale voorraad IPv4-adressen heen. IP-adressen worden uitgedeeld door vijf regionale internetregistreerders (RIRs), waarvan APNIC, wat Azië bedient, drie jaar geleden als eerste door z'n voorraad IPv4-adressen heen was. Het Europese RIPE NCC volgde anderhalf jaar geleden, en vorige week was het de beurt aan het Noord-Amerikaanse ARIN. LACNIC (Latijns Amerika en de Cariben) volgt naar verwachting over een maand. Dan blijft over het Afrikaanse AfriNIC, dat nog bijna 50 miljoen IPv4-adressen in voorraad heeft, die met 5 tot 10 miljoen per jaar uitgegeven worden.

Betekent dit dat degenen die een bedrijf runnen dat afhankelijk is van een regelmatige toevoer van nieuwe IP-adressen nu maar naar Afrika moeten verhuizen? Hopelijk niet.

De Internet Engineering Task Force zag dit alles twintig jaar geleden al aankomen—en dat mag ook wel, zij waren het die TCP/IP met een magere 32-bit adresruimte opgezadeld hebben, waarmee maar maximaal 4 miljard IPv4-adressen mogelijk zijn. Maar IPv6 lost dat op door de adreslengte te vergroten naar 128 bits, wat een nagenoeg oneindig aantal adressen geeft.

Als iemand die al ruim tien jaar bezig is met IPv6 had ik graag gezien dat de internetgemeenschap op de nieuwe versie van het IP-protocol was overgestapt voordat de IPv4-adressen opraakten. Het dak repareren als de zon schijnt dus. Maar net als politici die bezuinigingen alleen kunnen verkopen in een recessie zijn er maar weinig bedrijven die genegen zijn geld uit te geven aan nieuwe technologieën voordat het absoluut niet anders kan.

En met het opraken van de IPv4-adressen kan het absoluut niet anders, zou je denken. Maar nadat dit in Azië als eerste gebeurde bereikte ons uit het oosten eigenlijk alleen maar een oorverdovende stilte. Ook in de meeste Europese landen is er niet echt veel gebeurd op IPv6-gebied na het opraken van de IPv4 bij het RIPE NCC. Een aantal landen laten inmiddels wel een aanzienlijke IPv6-adoptie zien, maar het is bepaald niet zo dat IPv6 opgepakt wordt op plaatsen waar IPv4 schaars is: Azië is nog net geen hekkesluiter met minder dan een procent IPv6 in de meeste landen volgens Google na niet minder dan drie IPv4-loze jaren. Aan de andere kant zijn de IPv4-adressen in Noord-Amerika nog geen twee weken op en beschikt de VS over bijna de helft van alle uitgegeven IPv4-adressen, maar toch is de VS met 7% IPv6-gebruik vierde in de wereld, na België, Zwitserland en Duitsland.

Helaas kan een systeem dat alleen het IPv6 gebruikt niet direct communiceren met een systeem dat alleen IPv4 draait. Dus mensen alleen IPv6 geven betekent dat ze niet kunnen praten met de 97% van de internetgebruikers en de 90% van de top-500 websites die nog niet over het nieuwe protocol beschikken.

Maar ga nog niet gelijk op zoek naar een etage in Nairobi of Casablanca: het is ook mogelijk om IPv4-adressen te verhandelen. De grote vraag is echter: in hoeverre lost dat het gebrek aan IPv4-adressen op? We weten dat Microsoft en Amazon grote aantallen IPv4-adressen gekocht hebben, en er zijn ook grotere aantallen kleinere blokken van eigenaar gewisseld. De gemiddelde prijs lijkt zo'n $10 of € 10 te zijn, maar de verwachting is dat dit gaat stijgen naar $30.

Microsoft en Amazon opereren "cloud"-diensten waarbij grote aantallen virtuele machines een IP-adres nodig hebben, en daar konden ze waarschijnlijk niet op de gewone manier aankomen. In Azië en Australië zijn ook kleinere en middelgrote IPv4-blokken van eigenaar gewisseld. $2560 voor een /24 (256 adressen), het kleinste blok waar je wat mee kan, is uiteraard niet echt een probleem voor content-leveranciers.

Dat ligt wel wat anders voor de grote ISPs en telecombedrijven die IP-adressen met honderdduizenden of miljoenen gebruiken. De grote vraag is of zij ook bereid zijn om een tientje of meer per IPv4-adres te betalen. Kabelbedrijf Comcast in de VS heeft een blok van 12 miljoen IPv4-adressen, die misschien een paar cent per stuk kostten in het verleden. Stel je voor dat ze zometeen $30 miljoen moeten betalen voor het volgende blok van een miljoen. Erger nog, het jaar daarna kan het wel eens $60 per adres zijn, en dan $120 enzovoort. Zulke bedragen slaan een flinke bres in de winstmarge. (En dan heb ik het nog nieteens over de tijd en moeite die het kost om steeds kleinere blokken van steeds meer verschillende aanbieders van adressen aan te schaffen.)

In plaats van $30.000.000 betalen voor een miljoen IPv4-adressen kan een ISP waarschijnlijk voor een aanzienlijk lager bedrag Carrier Grade NAT (CGN) apparatuur aanschaffen waarmee het mogelijk is om meerdere gebruikers één IPv4-adres te laten delen. Dan hebben ze nog steeds iets van 100.000 IPv4-adressen nodig om een miljoen nieuwe klanten aan te sluiten, maar die adressen kunnen ze weghalen bij bestaande gebruikers en die dan ook achter de CGN plaatsen.

Ondertussen rollen meer en meer ISPs IPv6 uit voor hun gebruikers. Op dit moment is alleen IPv6-connectiviteit niet voldoende om "gewone" IPv4-connectiviteit te vervangen, maar die dag komt gestaag dichterbij. Op dit moment is voor mij een uur of twee alleen IPv6 niet al te problematisch. Ik kan dan weliswaar niet bij de meeste nieuwssites, Twitter of ISPToday, maar ik kan wel mijn email ophalen over IPv6 en Google, Facebook en Wikipedia bezoeken.

Dus mijn advies aan HP: als jullie een miljard dollar kan krijgen voor die 33 miljoen IPv4-adressen waar je over beschikt (na de inlijving van DEC), pak het geld. Als je dat niet doet krijg je er nog spijt van zodra IPv6 kritische massa bereikt en mensen zich af gaan vragen waarom ze nog moeite doen een protocol uit de jaren '80 in de lucht te houden. Aan de andere kant, ik ben geen econoom, maar het lijkt me toch dat het op de markt verschijnen van miljoenen IPv4-adressen de prijs zal drukken.

Resumerend: kleine hoeveelheden IPv4-adresruimte zullen altijd wel beschikbaar zijn in enige vorm. Maar erop vertrouwen dat je op enig moment in de toekomst miljoenen adressen goedkoop kan kopen of duur kan verkopen is een riskante aanname.

Dit artikel verscheen ook op ISP Today

Permalink - posted 2014-05-06 - 🇺🇸 English version

België is wereldleider met 15% IPv6-gebruikers

▼ Het is alweer negen jaar geleden dat mijn boek over IPv6 uitkwam. Had je me destijds gevraagd of in maart 2014 in België 15% van de eindgebruikers IPv6 zou draaien, dan had ik vast "ja, tuurlijk" gezegd. En ruim 6% van de Amerikanen? Vast wel, daar hebben ze nog zoveel IPv4, die hebben minder haast. Maar dat het in Nederland maar 1,1% is en in China zelfs iets minder dan 1%? Nee, dat zou ik niet gedacht hebben. Nederland was tien jaar geleden immers een Europese voorloper op IPv6-gebied, en iedereen wist dat Azië het beloofde IPv6-land was. Vreemd hoe die dingen kunnen lopen.

In 2011 organiseerde de Internet Society World IPv6 Day en een jaar later World IPv6 Launch, twee dagen waarop een groot deel van de belangrijkste websites in de wereld IPv6 aanzetten. Sindsdien kunnen we Google, Facebook, Yahoo, Wikipedia en meer bereiken over IPv6. Maar het aantal mensen dat in 2011 daadwerkelijk het net op ging met IPv6 bleef op dat moment nog op een paar tienden van een procent steken volgens de statistieken die Google sinds eind 2008 bijhoudt. Eind 2012 was dit één procent en inmiddels in het weekeinde net boven de drie. Door de week is het wat minder, blijkbaar gebruiken meer mensen IPv6 thuis dan op het werk.

Maar dat zijn de wereldwijde gemiddelden. De verschillen per land zijn echter enorm. Ook kan een land zomaar uit het niks opkomen. Dit was het geval met België. Twee jaar geleden maakte ik nog de grap dat Nederland weliswaar achterbleef qua IPv6-adoptie bij landen als Frankrijk, maar dat we het in elk geval nog beter deden dan onze zuiderburen. Maar een aantal weken geleden was België het eerste land met meer dan 10% IPv6-gebruikers, en inmiddels is dit ruim 15%.

Ik waag het echter te betwijfelen of 15% van de Belgen überhaupt ooit van IPv6 gehoord heeft. De reden dat ze IPv6 draaien is simpelweg omdat hun kabel-ISP VOO het aangezet heeft. Eerder zagen we hetzelfde verschijnsel met Free in Frankrijk, en in mindere mate met het 4G-netwerk van Verizon Wireless in de Verenigde Staten. Eén of twee ISPs kunnen een land dus een flink eind opstuwen in de vaart der IPv6-volkeren.

Stel je eens voor hoe hoog Nederland volgend jaar zou scoren als Ziggo/UPC en KPN dit jaar IPv6 aan zouden zetten! Welingelichte kringen melden dat beiden nog altijd aan hun IPv6-uitrol werken, maar of dat inderdaad dit jaar nog gaat lukken vermeldt het verhaal niet. Het gaat dus wel de goede kant op met IPv6, maar of het snel genoeg zal zijn om de problemen die we gaan krijgen omdat de IPv4-adressen al sinds eind 2012 op zijn voor te zijn blijft de vraag.

Permalink - posted 2014-03-30