Autocast: automatische optimalisatie van anycastlocaties

Anycast, anywhere

Anycast is een routeringsmechanisme waarbij serviceproviders hun dienst uitvoeren via meerdere, over de hele wereld verspreide locaties die hetzelfde IP-adres gebruiken. Dat betekent dat clients overal ter wereld verbinding maken met hetzelfde IP-adres, maar naar verschillende servers kunnen worden gerouteerd. Hierdoor wordt de verkeersbelasting gespreid en neemt de latentie tussen client en server af.

Internetverkeer wordt gerouteerd via routers die BGP gebruiken, een op beleidsregels gebaseerd routeringsprotocol dat op het eerste gezicht tamelijk onvoorspelbaar en ondoorzichtig is. In theorie leidt BGP-internetverkeer via het kortste beschikbare pad naar de bestemming, wat in het geval van anycast neerkomt op de topologisch dichtstbijzijnde locatie. In de praktijk is dat niet altijd het geval. Het eigen routeringsbeleid van providers en verborgen interne netwerken maken het onmogelijk om met zekerheid te zeggen naar welke anycastlocatie een client zal worden gerouteerd.

SIDN beheert een anycastplatform voor .nl, dat zich uitstrekt over 10 locaties verspreid over de hele wereld. Dit platform bedient onze clients: DNS-resolvers op het internet die .nl-domeinnamen opvragen. Net als veel andere DNS-operators draaien we onze nameservers op een bare-metalinfrastructuur van een externe aanbieder. Hierdoor zijn we in staat om de capaciteit dynamisch te schalen als de situatie daarom vraagt, bijvoorbeeld tijdens een DDoS-aanval. De aanbieders van zulke infrastructuren beschikken doorgaans over tientallen, zo niet honderden PoP's wereldwijd. Dat roept een belangrijke vraag op: welke PoP's kiezen we voor het hosten van de autoritatieve nameservers van .nl om goede dekking, lage latentie en een hoge mate van robuustheid te garanderen? Vooral de client-latentie – de round-trip time (RTT) van client naar server – is moeilijk te voorspellen, terwijl het essentieel is om deze zo laag mogelijk te houden als we overal ter wereld een soepele .nl-ervaring willen bieden.

Probleem: wat is de beste combinatie van anycastlocaties?

Er doet zich een onmiskenbaar probleem voor bij het selecteren van een goede combinatie van anycastlocaties uit alle PoP's die bij onze infrastructuuraanbieder(s) beschikbaar zijn: we weten niet met zekerheid welke clients naar welke anycastlocatie worden gerouteerd (wat het zogeheten 'catchment' van die locatie bepaalt) en met welke latentie. Om te kunnen kwantificeren hoe goed een selectie anycastlocaties is, zouden we deze eigenlijk moeten uitrollen om vervolgens de prestaties te meten. Het is volstrekt onhaalbaar om dit voor veel, laat staan alle mogelijke selecties te doen: een selectie van 10 uit in totaal 40 PoP's levert 847 miljoen mogelijke combinaties op! Daarom moeten we op de een of andere manier een inschatting maken van de verwachte prestaties van een selectie anycastlocaties, zonder die selectie te hoeven uitrollen.

Op dit moment kiezen we onze initiële anycastlocaties handmatig, gebaseerd op de meest beproefde technische werkwijzen uit de literatuur en kennis van onze klantbasis. Daarna blijven we de selectie voortdurend bijstellen om de prestaties te verbeteren. Zo kiezen we bijvoorbeeld op elk continent 1 of 2 PoP's, een gangbare strategie om wereldwijde dekking te realiseren. Hoewel het selecteren van PoP's op basis van hun geografische spreiding een solide strategie is, is het geen ultieme maatstaf voor succes. Uit experimenten blijkt namelijk dat geografische afstand een slechte voorspellende factor is voor de verbindingslatentie (Pearsons r = 0,45).

Een andere strategie voor het selecteren van anycastlocaties is om simpelweg alle PoP's van een infrastructuuraanbieder te gebruiken. Dit brengt echter hoge kosten met zich mee, en de wereldwijde latentie kan zelfs hoger uitvallen dan bij een zorgvuldig gekozen kleiner aantal PoP's, vanwege een grotere kans dat verkeer door het vaak politiek of commercieel gemotiveerde BGP-beleid naar een ver weg gelegen PoP wordt geleid.

Anycast-serviceproviders kunnen daarom sneller en met meer zekerheid tot een meer optimale anycastopstelling komen door een datagedreven methode te hanteren.

Autocast: selectie van anycastlocaties op basis van metingen

In deze sectie beschrijven we Autocast (Automating anycast), onze voorgestelde methode om op basis van unicast-meetresultaten tot een combinatie van anycastlocaties te komen die de wereldwijde client-latentie optimaliseert.

We stellen 3 eisen aan onze selectiemethode:

• Snelle resultaten: Het algoritme genereert binnen enkele minuten een aanbeveling.

• Nauwkeurige voorspellingsfactor: De voorspelde clientlatentie komt nauw overeen met de prestaties in de praktijk.

• Operationeel verankerd: onze DNS-operators moeten de methode willen gebruiken.

Onze aanpak is uniek omdat de door ons voorgestelde methode maar één enkele unicastmeting vereist. Dat bespaart tijd en is kostenefficiënt, aangezien infrastructuuraanbieders extra in rekening kunnen brengen voor het aankondigen van anycast-IP-ruimte in een bepaalde regio. Door deze eigenschappen onderscheidt onze methode zich van eerder werk op het gebied van de optimalisatie van anycastlocaties, waarbij meerdere anycastmetingen nodig zijn om locaties paarsgewijs te vergelijken en zo tot een voorkeursvolgorde te komen waarop de PoP-aanbevelingen worden gebaseerd.

Aannames bij Autocast

Om een voorspelling te kunnen doen over de prestaties van een anycastopstelling, gaan we uit van 2 aannames die gebaseerd zijn op de eigenschappen van BGP. We toetsen en onderbouwen deze aannames in de resultatensectie.

Aanname 1: clients worden gerouteerd naar de anycastlocatie met de laagste latentie. Deze aanname is gebaseerd op het 'kortste pad'-beleid in BGP, wat we vertalen naar 'kleinste round-trip time (RTT) van client naar server'. We weten dat deze aanname niet altijd klopt – het is meer een bestcasescenario – maar het is de beste vuistregel die we hebben. We illustreren deze aanname in figuur 1. Daar nemen we aan dat de client in Italië naar de server in Amsterdam wordt gerouteerd, omdat die de laagste latentie heeft.

Aanname 2: de anycast- en unicastlatentie naar dezelfde anycastlocatie zijn gelijk. Deze aanname betekent dat we de latentie naar een anycastlocatie kunnen achterhalen door de latentie naar het unicast-IP-adres van die locatie te meten. Die latentie zou gelijk moeten zijn, omdat het verkeer naar hetzelfde eindpunt op het internet wordt geleid. Het is echter mogelijk dat BGP dit verkeer toch anders routeert. Figuur 2 visualiseert dit: de latentie naar 2 verschillende IP-adressen van dezelfde server zou gelijk moeten zijn.

Methodologisch overzicht: het onmeetbare meten

Met deze aannames in gedachten is het tijd om het onmeetbare te meten: de prestaties van een denkbeeldige anycastopstelling. We kunnen de prestaties van een selectie anycastlocaties in 2 stappen inschatten:

1. Eerst meten we de latentie van al onze clients naar alle mogelijke anycast-PoP's die bij de aanbieder (of aanbieders) van een infrastructuur beschikbaar zijn. Dit zijn de potentiële locaties waar we onze ge-anycaste .nl-nameservers kunnen uitrollen. Dit levert een dataset op met de latentie tussen alle resolvers en alle PoP's.

2. Vervolgens kunnen we oneindig veel 'denkbeeldige' anycastopstellingen simuleren door willekeurige combinaties van PoP's te selecteren. Om de prestaties van een denkbeeldige anycastopstelling in te schatten, verwijderen we alle gemeten latentiewaarden uit stap 1 die niet gerelateerd zijn aan de geselecteerde PoP's. Op basis van aanname 1 voorspellen we dat elke client verbinding maakt met de PoP die in onze denkbeeldige opstelling de laagste latentie heeft. Aan de hand van het voorspelde catchment van elke PoP maken we een inschatting van de algemene mediane latentie van de opstelling, zonder die daadwerkelijk te hoeven uitrollen.

Stap 1: de unicastlatentie meten

In het geval van onze autoritatieve DNS-service weten we wie de clients zijn: de resolvers die .nl-domeinnamen opvragen. Die gegevens hebben we in ons DNS-analyseplatform ENTRADA. Als we niet weten wie de clients zijn, kunnen we een generieke IP-hitlist gebruiken om veel netwerken te bereiken en zo wereldwijde dekking van het internet te realiseren. Om de latentie van elke client naar elke mogelijke PoP te meten, spinnen we bij al die PoP's een virtuele machine (VM) op en sturen we vanaf elk van die locaties een ICMP-ping naar elke client. De meettool MAnycastR automatiseert dit proces, dus dat is heel gemakkelijk. Omdat de meeste infrastructuuraanbieders een API beschikbaar stellen waarmee je resources kunt starten en stoppen, kunnen we binnen enkele minuten – en vrijwel zonder kosten – alle VM's opspinnen, onze metingen uitvoeren en de VM's weer verwijderen.

Stap 2: de optimale PoP's selecteren

Met de gemeten latentiewaarden in handen kunnen we de prestaties van elke virtuele anycastopstelling simuleren. Zo evalueren we bijvoorbeeld de anycastopstelling [Amsterdam, New York, Singapore] door alleen de in stap 1 verkregen latentiewaarden van en naar die locaties te behouden en voor elke client de snelste locatie te selecteren. Daarna nemen we de mediane latentie over alle clients als verwachte (optimistische) prestatiescore. We kunnen deze maatstaf zelfs wegen op basis van het aantal DNS-query's dat elke resolver verstuurt, zodat belangrijkere clients zwaarder meetellen.

Op dit punt staan we voor een optimalisatieprobleem: miljoenen mogelijke oplossingen (combinaties van potentieel geschikte anycastlocaties) binnen onze zoekruimte, en een methode om elke oplossing te evalueren (de mediane client-latentie). Onze taak is om de oplossing te vinden met de laagste mediane latentie. Uit aanname 1 volgt dat het toevoegen van een extra locatie aan onze selectie de geschatte prestaties van de denkbeeldige anycastopstelling alleen maar kan verbeteren en nooit verslechteren. Maar dat is niet altijd het geval: vanwege de complexiteit van BGP kan een ongelukkig gekozen PoP de wereldwijde prestaties wel degelijk schaden, door verkeer weg te kapen bij een PoP met een lagere latentie. Om die beperking te omzeilen, limiteren we onze zoekruimte tot een vast aantal locaties, want anders zou de oplossing altijd zijn: gebruik ze gewoon allemaal! We kunnen het optimalisatieproces herhalen voor elk gewenst aantal locaties dat we in een anycastopstelling willen opnemen.

Zelfs het simpelweg inschatten van de prestaties voor elke mogelijke combinatie van anycastlocaties – bedenk dat er miljoenen zijn – zou al een gigantische rekenkundige opgave zijn. Daarom moeten we de optimale oplossing benaderen met behulp van een optimalisatiealgoritme. Om het optimalisatieprobleem op te lossen – dus de combinatie van anycastlocaties te vinden met de snelste algemene responsetijd – gebruiken we een probabilistische methode die Simulated Annealing wordt genoemd. Bij elke stap van het algoritme wordt de selectie van PoP's aangepast door een van de PoP's te vervangen door een andere. Als de nieuwe oplossing beter is dan de vorige, wordt die behouden voor de volgende stap. Slechtere oplossingen worden soms toch geaccepteerd, gebaseerd op een waarschijnlijkheid die bij elke stap afneemt. Dit stimuleert verkenning van de zoekruimte en voorkomt dat het algoritme vastloopt in lokale minima. De uitkomst van het algoritme is de beste anycastconfiguratie (een selectie van locaties) die het kon vinden, met de bijbehorende voorspelde algemene latentie vanaf de clients.

Onze DNS-operators krijgen de voorgestelde anycastopstellingen te zien en kunnen er naar eigen inzicht voor kiezen om nameservers op de betreffende locaties uit te rollen. De door Autocast voorgestelde opstellingen worden niet automatisch in productie genomen.

Onze methode getest met Vultr

Tijd om onze methode op de proef te stellen! We lieten ons inspireren door onze productieopstelling voor het DNS van .nl, zodat we automatisch een groot aantal anycastopstellingen konden uitrollen en testen op ons eigen anycasttestbed. We testten onze methode met Vultr, een infrastructuuraanbieder die klanten de mogelijkheid biedt om hun eigen IP-prefixen op het internet aan te kondigen. Vultr heeft wereldwijd 32 PoP's en een API waarmee we met behulp van een vooraf gedefinieerd configuratiebestand programmatisch virtuele machines kunnen aanmaken en verwijderen. Onze software voor het implementeren en beheren van deze infrastructuur is beschikbaar op GitHub.

Stap 1: De eerste stap is het verkrijgen van de RTT's (latentie) van alle 32 PoP's van Vultr naar alle clients. We definiëren onze clients als alle DNS-resolvers die de dag ervoor minstens 100 DNS-query's naar .nl hebben verstuurd. Dit levert ongeveer 230.000 IPv4-adressen en 73.000 IPv6-adressen op. We rollen onze vooraf geconfigureerde virtuele meetmachines programmatisch uit op alle PoP's van Vultr en starten een ping-meting naar onze clientlijst. We beperken de MAnycastR-tool tot maximaal 1.000 probes per seconde. Na ongeveer 10 minuten is de meting voltooid en hebben we 7 miljoen responses ontvangen, wat neerkomt op een responsepercentage van ongeveer 73%.

Stap 2: Met behulp van de via unicast gemeten latentiewaarden voeren we ons optimalisatiealgoritme uit om de optimale anycastopstellingen te benaderen voor 3, 5, 7, 11, 13, 15 en 17 PoP's. Uit onze empirische tests blijkt dat het toevoegen van meer dan 17 PoP's aan onze anycastopstelling in de praktijk geen verbetering van de globale latentie oplevert. Voor onze optimalisatie vermenigvuldigen we de mediane latentie van alle resolvers met de logaritme van hun query-aantallen, om zo een evenwicht te vinden tussen het gemeten relatieve belang van resolvers en een brede dekking.

Opstellingen evalueren: Om onze methode te evalueren, rollen we de resulterende configuraties een voor een uit en voeren we opnieuw een pingmeting uit naar onze clients, dit keer met de gedeelde ge-anycaste IP-adressen van de meetmachines als bron van de pings. Hierdoor reageren de clients op een van de aangekondigde locaties en worden de catchments en de werkelijke latentie van de opstelling zichtbaar.

Ter vergelijking herhalen we onze experimenten met anycastopstellingen die bestaan uit willekeurige PoP-selecties.

Resultaten: Locatieselectie door Autocast

Figuur 3 toont per geteste anycastopstelling de voorspelde mediane RTT – berekend op basis van de via unicast gemeten latentie met alle 32 PoP's van Vultr – en de daadwerkelijk waargenomen anycastlatentie. Ook laten we de mediane latentie zien wanneer het aantal door een resolver verstuurde query's wordt meegewogen (in oranje).

https://www.sidnlabs.nl/downloads/b8BZadViWmT2qC93PF6Jy/12bceb065d2c8bad58fc019b00fd18b2/Predicted_vs._observed_median_round-trip_times.png

We zien dat de voorspelde RTT's nauw overeenkomen met de waargenomen RTT's. Het gemiddelde verschil tussen de voorspelde en waargenomen RTT's bedraagt 1,57 ms. Wanneer we het aantal DNS-query's dat door de resolvers wordt verstuurd meewegen, is het verschil tussen de voorspelde en waargenomen RTT's een verwaarloosbare -0,19 ms. Deze resultaten tonen aan dat we onze methode inderdaad kunnen gebruiken om anycastopstellingen met lage RTT's te realiseren en zelfs om te bepalen hoeveel locaties we willen uitrollen zonder te maken te krijgen met afnemende meeropbrengsten. Dit geldt des te meer wanneer we weten wie onze clients zijn en wat hun relatieve belang is. Uit de resultaten blijkt dat het gebruik van meer dan 11 of 13 PoP's weinig tot geen verbetering oplevert, wat erop wijst dat de extra kosten vermoedelijk niet opwegen tegen de baten.

Ter vergelijking herhaalden we onze experimenten met willekeurige PoP-selecties. We evalueerden willekeurige selecties van 3, 5, 7, 9, 11, 13, 15 en 17 PoP's elk 5 keer (in totaal 40 configuraties) en tonen de voorspelde en waargenomen mediane RTT's in Figuur 4. De anycastopstellingen met willekeurige PoP-selecties presteren aanzienlijk slechter dan de geoptimaliseerde opstellingen, wat volgens verwachting is. Wat opvalt, is dat de fout tussen de voorspelde en waargenomen latentie bij deze opstellingen aanzienlijk groter is dan bij de optimale PoP-selecties. Bij willekeurig gekozen selecties is dus sprake van een groter verschil tussen de voorspelde en de daadwerkelijke wereldwijde latentie. Dit duidt erop dat de aanname waarop we onze voorspellingen voor catchment en latentie baseren, in mindere mate standhoudt voor anycastopstellingen die niet goed zijn geoptimaliseerd. Denk bijvoorbeeld aan een anycastopstelling met onvoldoende wereldwijde dekking of zonder aanwezigheid in regio's met veel clients.

https://www.sidnlabs.nl/downloads/5fiMtNc0UaRSSr4xHTBy4Y/c053cc864d3325e477d8b441c4ea9026/Predicted_vs._observed_median_round-trip_times_for_random_anycast_configurations.png

Resultaten: toetsing van de aannames van Autocast

We kwantificeren in hoeverre aanname 1 standhoudt door te kijken hoe vaak resolvers daadwerkelijk naar de snelste anycast-PoP gaan. Bezien over alle optimale anycastconfiguraties die door Autocast zijn gegenereerd, wordt aanname 1 bij gemiddeld 26,8% van de resolvers geschonden. Als we kijken naar het aantal query's dat elke resolver verstuurt, komt dit neer op 11,8% van alle DNS-query's. Bij willekeurig geselecteerde opstellingen liggen deze percentages op respectievelijk 40,8% en 34,5%, wat inderdaad beduidend slechter is. Deze cijfers variëren afhankelijk van het aantal PoP's dat is meegenomen in de latentiemeting via unicast, en van de upstream- en transitproviders die de infrastructuuraanbieder gebruikt. Met meer PoP's is de kans groter dat een resolver naar een suboptimale PoP wordt gerouteerd, maar kan de fout in de voorspelde latentie ook kleiner zijn.

We zouden aanname 1 kunnen herformuleren door ervan uit te gaan dat clients geen verbinding maken met de server met de laagste latentie, maar met de server die – geschat op basis van het IP-TTL-veld in de response – via het kleinste aantal netwerkhops wordt bereikt. In onze experimenten was het kleinste geschatte aantal hops echter minder voorspellend voor het catchment dan de RTT. Dat kan verklaard worden door het feit dat internetpakketten meerdere interne netwerken kunnen doorkruisen die niet zichtbaar zijn in de TTL-waarde.

De eerste aanname blijft de grootste beperking van onze methode. Desondanks is het duidelijk dat we voor optimale anycastopstellingen die gegenereerd zijn door Autocast, de prestaties van de anycastopstelling als geheel nog steeds met vertrouwen kunnen voorspellen.

Aanname 2 houdt in alle gevallen goed stand, met een mediaan verschil tussen unicast- en anycast-RTT naar dezelfde locatie van 0,06 ms (μ=0,29 ms, σ=14,6 ms, Cohens d=0,02, steekproefomvang: 284.000).

Conclusies: Autocast kan anycastlocaties voor je selecteren

De resultaten van onze experimenten laten zien dat we met ons algoritme inderdaad in staat zijn om een optimale selectie van locaties voor anycastopstellingen te benaderen en de verwachte mediane latentie te voorspellen – louter op basis van de via unicast gemeten latentie naar alle beschikbare PoP's. Operators van anycastopstellingen kunnen met behulp van Autocast snel en nauwkeurig een selectie anycastlocaties genereren die goed presteert, zonder handmatig allerlei opstellingen empirisch te hoeven testen. Daarnaast kunnen ze de meettool en infrastructuur gebruiken om wijzigingen in hun huidige anycastopstellingen te simuleren en zo te kijken welke verbeteringen ze kunnen aanbrengen of wat er met catchments gebeurt wanneer anycastlocaties worden verwijderd of aan een opstelling worden toegevoegd.

En nu?

We blijven nauw samenwerken met ons DNS-operationsteam om deze methode in de praktijk toe te passen bij het opzetten van op anycast gebaseerde autoritatieve DNS-diensten voor .nl.

We willen ook testen hoe goed onze methode standhoudt wanneer we met meerdere infrastructuuraanbieders tegelijk werken. Het zou bijvoorbeeld kunnen dat aanname 1 vaker wordt geschonden bij een combinatie van infrastructuuraanbieders, omdat bepaalde upstreamproviders in BGP de voorkeur krijgen boven andere. Daarnaast gaan we onderzoeken of we de voorspellingen voor catchments en latentie kunnen verbeteren door anycast-latentiemetingen toe te voegen. Met die metingen kunnen we zien welke locaties clients 'wegkapen' bij locaties met een lagere latentie. Die informatie kan vervolgens gebruikt worden om de voorspellingen voor catchments te verbeteren, en daarmee ook de doeltreffendheid van onze methode.

Collega's van de Universiteit Twente schrijven momenteel een paper over de recent verbeterde meettool die de basis vormt voor alle metingen die we voor dit onderzoek hebben uitgevoerd. Wij dragen bij aan deze paper door de tool in de praktijk te valideren. Zodra de paper wordt gepubliceerd, wordt de tool beschikbaar gesteld.

Als je vragen hebt over Autocast, aarzel dan niet om contact met ons op te nemen via sidnlabs@sidn.nl!