Diagnosing and Repairing Distributed Routing Configurations Using Selective Symbolic Simulation

Dit paper introduceert S^2Sim, een nieuw systeem dat automatisch fouten in gedistribueerde routingconfiguraties diagnoseert en repareert door selectieve symbolische simulatie te gebruiken om intentie-conforme varianten te vinden.

De kern

Stel je voor dat een groot computernetwerk (zoals het internet van een grote bedrijf of een provider) een enorm complex recept is. Dit recept bestaat uit duizenden instructies voor elke router (de "postbodes" van het internet) over hoe ze berichten moeten verwerken, welke routes ze moeten kiezen en welke ze moeten blokkeren.

Soms gaat er iets mis in dit recept. Een verkeerd getypt getal of een vergeten regel kan ervoor zorgen dat data vastloopt, verkeerd wordt gestuurd of dat bepaalde delen van het netwerk onbereikbaar worden.

Tot nu toe was het vinden en repareren van deze fouten een tijdrovende klus voor menselijke netwerkbewakers. Ze moesten als detectives door duizenden regels bladeren om te raden wat er mis was.

Dit paper introduceert S2Sim, een slimme, geautomatiseerde "reparatie-robot" die dit proces volledig overneemt. Hier is hoe het werkt, vertaald naar simpele beelden:

1. Het Probleem: De "Wat als?"-Dilemma

Stel je voor dat je een verkeerde route hebt ingevoerd in je GPS. De GPS zegt: "Je bent aangekomen, maar je bent op de verkeerde plek."

• Oude methoden: Ze zeggen alleen: "Je bent fout." Ze geven je misschien een voorbeeld van een verkeerde route, maar ze zeggen niet waar je in je instructies hebt gefout. Je moet zelf al die mogelijke routes uitproberen om de fout te vinden. Dat is als proberen te raden welk woord in een boek van 1000 pagina's verkeerd staat door het hele boek te herschrijven.
• S2Sim's aanpak: In plaats van te proberen te raden wat er mis is, denkt S2Sim: "Laten we eerst bedenken hoe het recept er had moeten uitzien om perfect te werken. Dan vergelijken we dat met wat je nu hebt. Het verschil tussen 'had moeten' en 'is' is precies waar de fout zit."

2. De Kern: De "Contracten" (De Regels van het Spel)

S2Sim werkt met een slim idee: Contracten.
Stel je voor dat elke router een speler is in een spel met strikte regels (contracten).

• Voorbeeld van een contract: "Als je een brief van router B krijgt, moet je die altijd doorsturen naar router C, tenzij er een brand is."
• S2Sim berekent eerst een perfecte versie van het netwerk (waar alle doelen worden bereikt). Uit die perfecte versie haalt het de regels (contracten) die nodig zijn om dat te bereiken.
• Vervolgens kijkt het naar je huidige, gebrekkige netwerk en simuleert het wat er gebeurt. Zodra een router een regel (contract) breekt, schreeuwt S2Sim: "Stop! Hier is de fout!" en corrigeert het direct in de simulatie om verder te gaan.

3. De Werkwijze: De "Symbolische Simulatie"

Dit is de magische techniek. In plaats van het netwerk één voor één te testen (wat eeuwen duurt), gebruikt S2Sim symbolische simulatie.

• De Metafoor: Stel je voor dat je een treinroute tekent. In plaats van een echte trein te sturen die van station A naar B rijdt, tekent S2Sim een "spooktrein" die tegelijkertijd alle mogelijke routes aflegt.
• Als de spooktrein ergens vastloopt omdat een verkeerslicht (de configuratie) verkeerd staat, weet S2Sim direct: "Ah, bij station X is het verkeerslicht verkeerd ingesteld."
• Het systeem is zo slim dat het alleen de delen van de route simuleert waar het nodig is (selectief), waardoor het razendsnel is, zelfs in netwerken met duizenden routers.

4. Complexe Situaties: Netwerken in Netwerken

Veel moderne netwerken hebben lagen: een "onderlaag" (fysieke kabels) en een "bovenlaag" (virtuele routes).

• De Metafoor: Stel je voor dat je een vrachtwagen (data) moet vervoeren. De onderlaag is de weg (OSPF), en de bovenlaag is de vrachtwagen die daarover rijdt (BGP). Als de weg kapot is, kan de vrachtwagen niet rijden.
• S2Sim lost dit op door laag voor laag te werken. Het doet eerst alsof de wegen perfect zijn en repareert de vrachtwagen-regels. Daarna gebruikt het de gerepareerde vrachtwagen-regels als basis om de wegen zelf te repareren. Zo voorkomt het dat het in de war raakt door de complexiteit.

5. Wat als er iets kapot gaat? (Fouttolerantie)

S2Sim kan ook rekening houden met ongelukken.

• De Metafoor: Je wilt niet alleen dat je route werkt, maar ook dat je alternatieve routes hebt als er een brug instort (een kabel kapot gaat).
• S2Sim berekent niet één perfecte route, maar een netwerk van veilige routes. Als er één brug wegvalt, zorgt het systeem ervoor dat er altijd nog een andere weg open is. Als je huidige configuratie dit niet garandeert, wijst S2Sim precies aan welke instelling je moet aanpassen om die extra veiligheid te creëren.

6. Het Resultaat: Snel en Accuraat

In tests met echte netwerken van grote providers (met honderden routers) en met nagemaakte netwerken (met duizenden routers) bleek S2Sim:

• Snel: Het vond en repareerde fouten in netwerken van 100 routers in slechts 20 seconden.
• Krachtig: Het kon zelfs grote netwerken van 1000 routers repareren in ongeveer 15 minuten.
• Betrouwbaar: Het vond fouten die andere geavanceerde tools over het hoofd zagen, zoals fouten in complexe filters of voorkeursregels.

Samenvattend

S2Sim is als een super-intelligente auto-correctie voor netwerkbewaking. In plaats van dat een mens urenlang moet zoeken naar een naald in een hooiberg, bouwt S2Sim eerst een model van hoe de hooiberg er had moeten uitzien, en wijst dan direct met een laser aan waar de naald zit en hoe je hem moet verplaatsen. Het maakt het netwerk veiliger, sneller en veel minder afhankelijk van menselijke fouten.

Technische samenvatting

Probleemstelling

Hoewel er aanzienlijke vooruitgang is geboekt in het automatisch verifiëren van gedistribueerde routingconfiguraties (ofwel Control Plane Verification - CPV) om te controleren of ze voldoen aan bepaalde intenties (zoals bereikbaarheid, loopvrijheid, etc.), blijft het diagnosticeren en repareren van configuratiefouten een handmatig, tijdrovend en foutgevoelig proces.

• Bestaande tools kunnen vaak wel aangeven dat een configuratie foutief is (vaak met een tegenvoorbeeld), maar ze kunnen de exacte bron van de fout niet lokaliseren of een correcte reparatie voorstellen.
• Bestaande oplossingen zoals Minesweeper (SMT-gebaseerd) of CPR (constraint programming) hebben beperkingen: ze kunnen bijvoorbeeld geen AS-path filters ondersteunen door "path explosion", of ze kunnen lokale voorkeuren (local preference) niet modelleren. Andere tools vereisen vaak trial-and-error of zijn afhankelijk van testcoverage die echte fouten kan missen.

Methodologie: S2Sim

De auteurs stellen S2Sim voor, een systeem dat automatisch routingconfiguraties diagnoseert en repareert. De kern van de aanpak is een verschuiving in mindset: in plaats van te proberen te begrijpen wat er mis is in de gegeven configuratie, probeert het systeem een variant van de configuratie te vinden die wel voldoet aan de intenties en vergelijkt deze met de originele configuratie om de verschillen (de fouten) te identificeren.

De methodologie bestaat uit drie hoofdfasen:

1. Afleiding van Intentie-Conforme Contracten:

   • Het systeem berekent eerst een "intentie-conforme data plane" die zo dicht mogelijk bij de originele (foutieve) data plane ligt, maar wel voldoet aan de netwerkwensen (intenties).
   • Op basis van deze ideale data plane worden een reeks contracten afgeleid. Een contract is een Booleaanse voorspelling die het gedrag van een router beschrijft (bijv. "is deze route geëxporteerd?", "wordt deze route verkozen boven een andere?", "is er een peer-sessie?").
   • Als een configuratie aan al deze contracten voldoet, is deze per definitie intentie-conform.

2. Selectieve Symbolische Simulatie:

   • S2Sim voert een symbolische simulatie uit van de originele, foutieve configuratie.
   • Tijdens de simulatie wordt gecontroleerd of het gedrag van de routers overeenkomt met de afgeleide contracten.
   • Als een contract wordt geschonden, wordt de simulatie gedwongen om zich te gedragen volgens het contract (het "selectieve" aspect). De simulatie schakelt over naar een symbolische variant van de configuratie waarbij de fout wordt gecorrigeerd.
   • Alle geschonden contracten worden gelogd. Omdat de simulatie uiteindelijk leidt tot de intentie-conforme data plane, kunnen de geschonden contracten direct worden gekoppeld aan de specifieke configuratiefragmenten die de fout veroorzaken.

3. Reparatie via Constraint Programming:

   • De gelokaliseerde fouten worden gerepareerd met behulp van constraint programming.
   • Om conflicten te voorkomen (bijvoorbeeld als twee verschillende contracten op dezelfde regel van de configuratie van toepassing zijn), gebruikt S2Sim contract-specifieke sjablonen. Hierbij wordt een nieuwe regel toegevoegd die specifiek is voor de betreffende route (bijv. op basis van prefix of AS-path), zodat de reparatie alleen de gewenste route beïnvloedt en geen andere.

Uitbreidingen voor complexiteit:

• Meerdere protocollen: Voor netwerken met een overlay/underlay architectuur (bijv. BGP over OSPF) gebruikt S2Sim een "assume-guarantee" aanpak. Eerst wordt de overlay gerepareerd (onder de aanname dat de underlay werkt), en vervolgens wordt de underlay gerepareerd met de overlay-intenties als input.
• Fouttolerantie (k-link failure): Het systeem kan configuraties repareren zodat ze bestand zijn tegen $k$ willekeurige linkstoringen. Dit wordt gedaan door $k+1$ kant-onafhankelijke paden te berekenen en contracten af te leiden die garanderen dat ten minste één pad altijd beschikbaar blijft.
• Complexiteit: Het systeem ondersteunt ACL's, route-aggregatie en multi-path routing (ECMP).

Belangrijkste Bijdragen

1. Nieuwe Paradigma: De introductie van het concept van "intentie-conforme contracten" als tussenlaag tussen de intenties en de configuratie, wat het diagnosticeren van fouten mogelijk maakt zonder volledige enumeratie van alle mogelijke configuraties.
2. Selectieve Symbolische Simulatie: Een efficiënte methode om fouten te lokaliseren door de simulatie te sturen naar een correcte staat en de afwijkingen te traceren.
3. Contract-specifieke Sjablonen: Een innovatieve techniek om constraint programming toe te passen zonder dat er conflicten ontstaan tussen verschillende regels in dezelfde configuratie, wat leidt tot garandeerbaar oplosbare reparaties.
4. Omvangrijke Ondersteuning: Het systeem is ontworpen voor complexe, real-world scenario's, waaronder multi-protocol netwerken, grote schaal (tot 1000+ knopen), en fault-tolerantie.

Resultaten

De auteurs hebben S2Sim geïmplementeerd als een plugin voor Batfish en geëvalueerd met:

• Real-world data: Configuratiebestanden van twee grote providers (een Data Center WAN en IP Radio Access Networks).
• Gesynthetiseerde data: Netwerken van verschillende schalen (van 10 tot 1000 knopen) met geïntroduceerde fouten gebaseerd op real-world patronen.

Kernbevindingen:

• Nauwkeurigheid: S2Sim kan alle geteste fouttypes (zoals ontbrekende redistributie, verkeerde filters, incorrecte local preference) correct diagnosticeren en repareren. Bestaande tools (CPR, CEL) faalden bij veel van deze specifieke fouttypes (bijv. AS-path filters).
• Efficiëntie:
  • In realistische netwerken van ~100 knopen duurt de diagnose en reparatie maximaal 20 seconden.
  • In gesynthetiseerde netwerken van ~1000 knopen duurt het maximaal 15 minuten.
  • S2Sim is >10x sneller dan de state-of-the-art tools (CPR en CEL) bij het diagnosticeren en repareren van fouten, vooral bij grotere netwerken en scenario's met linkstoringen.
• Schalbaarheid: De runtime toont een kwadratische groei met de netwerkschaal (voor de tweede simulatie), wat acceptabel is voor grote netwerken. Het aantal fouten heeft een verwaarloosbaar effect op de runtime.

Betekenis

S2Sim vult een kritieke lacune in het netwerkbeheer. Het transformeert het proces van configuratieverificatie van een puur "ja/nee"-check (is dit fout?) naar een automatisch herstelproces. Door de complexiteit van moderne netwerken (multi-protocol, fault-tolerance, complexe policies) te kunnen hanteren, biedt S2Sim netwerkbeheerders een krachtig hulpmiddel om de betrouwbaarheid van hun netwerken te vergroten en de tijd die wordt besteed aan het handmatig opsporen van fouten drastisch te verkorten. Het systeem is een belangrijke stap richting volledig geautomatiseerd en zelfherstellend netwerkbeheer.