21.04.23 1

Routing Instabilitäten

Lokalisierung von Routing Instabilitäten

Vortrag:

Daniel Weber

Betreuer:

Olaf Maennel

21.04.23 2

Ablauf

1.Begriffsdefinitionen

2.Motivation

3.Ursachen von Instabilitäten

4.Einfacher Ansatz• Fehlerquellen

5.Verbesserter Ansatz• Gruppierung von Updates

6.Fazit

21.04.23 3

Begriffsdefinitionen

Instabilitäten• jegliche Veränderungen eines AS-Pfads zu einem bestimmten Präfix

Störungsstellen• das AS oder die Kante zwischen zwei ASen, das/die die Instabilität

verursacht hat

Beobachtungspunkte• passiv am BGP teilnehmende Systeme, die die eingehenden BGP-Updates für

eine spätere Auswertung aufzeichnen

21.04.23 4

Motivation zur Lokalisierung

Relativ junges Forschungsgebiet• erst mit komplexem Internet entstanden• BGP-Dynamik teilweise als „schwarze Magie“ missverstanden

Beeinflussung der Erreichbarkeit• kurzzeitiger oder längerer Verlust der Konnektivität• Performanceverlust der Anbindung durch häufige Updates• Beeinträchtigung des globalen Routings

Vereinfacht die Behebung von Fehlern• Fehlerquelle muss bekannt sein um das Problem zu lösen• „Schuldfrage“ einfacher zu klären

21.04.23 5

Ursachen von Instabilitäten

Konfigurationsänderungen• Neue Peering- oder Upstream-Beziehungen• Einrichtung von Filtern• Veränderung interner Metriken

Konfigurationsfehler• oszillierende Routen• „schwarze Löcher“

Fehlfunktionen von Hardware, Software, usw.• Ausfälle von Leitungen oder Routern

21.04.23 6

Einfacher Ansatz

• Vergleich von altem und neuem Pfad• gemeinsame Abschnitte beider Pfade ausschließen• der „bessere“ Pfad enthält die Instabilität

AS 1 AS 3 AS 5 AS 7

AS 4 AS 6

21.04.23 7

Mögliche Fehlentscheidungen

Ausschluß gemeinsamer Abschnitte im Pfad kann zu einem falschen Ergebnis führen:

AS 1

AS 3

AS 5 AS 7

AS 9

AS 6vermutete

Störungsstelle

tatsächliche Störungsstelle

21.04.23 8

Mögliche Fehlentscheidungen

Induzierte Updates:

AS 1 AS 2 AS 3 AS 4 AS 5

vermutete Störungsstelle

tatsächliche Störungsstelle

AS 8

AS 6 AS 7

Bevorzugung von1-2-3-4 vor 1-8-4

manuell Konfiguriert

21.04.23 9

Verbesserter Ansatz

• Keine vorschnellen Ausschlüsse gemeinsamer Abschnitte der AS-Pfade

• Keine falschen Ergebnisse durch induzierte Updates

• Keine Beeinflussung durch teilweise nicht erkennbare Instabilitäten

• Nutzung bisher nicht ausgewerteter Informationen

21.04.23 10

Einschub: Stabile AS-Pfade

• für beide Verfahren notwendig• stabile AS-Pfade werden nicht sofort erreicht

sondern erst nach einer Konvergenzzeit

Wie das „Ende“ der Update-Bursts erkennen?

21.04.23 11

Einschub: Stabile AS-Pfade

Drei mögliche Verfahren zur Erkennung zusammengehöriger Updates:

• statischer Timeout

• relativer Timeout

• adaptiver Timeout

21.04.23 12

Einschub: Stabile AS-Pfade

Erkennung der Bursts: statischer Timeout

Zeit

BG

P-P

eers

Timeout

• geeigneter Timeout für ein Präfix kann für ein anderes absolut ungeeignet sein

21.04.23 13

Einschub: Stabile AS-Pfade

Erkennung der Bursts: relativer Timeout

Zeit

BG

P-P

eers

Timeout

• Updates in Folge eines anderen Ereignisses werden möglicherweise diesem zugeordnet

21.04.23 14

Einschub: Stabile AS-Pfade

Erkennung der Bursts: adaptiver Timeout

Zeit

BG

P-P

eers

relativer Timeout von t/2

• über eine Zeitspanne t wird ein relativer Timeout von t/2 verwendet

• führt dies zu keinem „Ende“, werden nur noch die laufenden Updates abgewartet

t

statischer Timeout mit t* = 0

21.04.23 15

Verbesserter Ansatz (cont‘d)

1. Schritt: UNION-Heuristiknach Zeit

Alle ASe auf dem alten wie auch auf dem neuen Pfad werden als mögliche Störungsquelle berücksichtig.

Beobachtungs-punkt 1

PräfixA

21.04.23 16

Verbesserter Ansatz (cont‘d)

2. Schritt: INTERSECT-Heuristiknach Beobachtungspunkt

Die Schnittmenge verschiedener Beobachtungs-punkte wird als Kandidatenmenge verwendet

Beobachtungs-punkt 1

Beobachtungs-punkt 2

PräfixA

21.04.23 17

Verbesserter Ansatz (cont‘d)

3. Schritt: GREEDY-Heuristiknach Präfixen

Die am häufigsten auftretenden Elemente aller Kandidatenmengen werden als Kandidaten gewählt.

PräfixA

PräfixB

Beobachtungs-punkt 1

Beobachtungs-punkt 2

21.04.23 18

Fazit

• Lokalisierung einer Instabilität nicht trivial aber relativ genau möglich

• je mehr Beobachtungspunkte desto besser

• die „Stelle“ der Instabilität beeinflusst deren Sichtbarkeit

Ausbreitung von Instabilitäten ideale Standorte für Beobachtungspunkte

21.04.23 19

Ende

Danke!