Handling the complexity of BGP [Elektronische Ressource] : via characterization, testing and configuration management / Olaf Maennel

Sujets

• Informatik

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2005
• Nombre de lectures: 16
• Langue: Deutsch
• Poids de l'ouvrage: 2 Mo

Extrait

Lehrstuhl f r Netzwerkarchitekturen
Fakult t f r Informatik
Technische Universit t M nchen
Handling the complexity of BGP
via characterization, testing and
con guration management
Olaf Maennel
Vollst ndiger Abdruck der von der Fakult t f r Informatik
der Technischen Universit t M nchen zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Bernd Br gge, Ph.D.
Pr fer der Dissertation: 1. Univ.-Prof. Anja Feldmann, Ph.D.
2. Univ.-Prof. Timothy G. Grif n, Ph.D.,
Univ. of Cambridge / UK
Die Dissertation wurde am 29. 6. 2005 bei der Technischen Universit t M nchen
eingereicht und durch die Fakult t f r Informatik
am 11. 10. 2005 angenommen.Kurzfassung
In der heutigen Zeit hat das Internet eine berw ltigende kommerzielle und soziale Bedeu-
tung eingenommen; dennoch mangelt es an einem Verst ndnis der grundlegenden Routing-
protokolle, wie des Border-Gateway-Protokolls (BGP). Komplexit ten entstehen zum einen
dadurch, dass man das Problem globale Erreichbarkeit an vielen r umlich weit verteil-
ten Komponenten l sen muss, zum anderen haben sie den Ursprung in der Tatsache, dass
die Verkehrslenkungsstrategien (routing policies) eines autonomen Systems (AS) st ndigen
Ver nderungen unterworfen sind, aus Gr nden wie Verkehrskapazit tsplanung (traf c engi-
neering) oder um kundenspezi sche W nsche zu erf llen – ein fehleranf lliges Vorgehen.
In dieser Arbeit behandeln wir diese Probleme in mehrfacher Hinsicht:
Um das Problem der Netzwerkkon gurationen zu l sen, haben wir ein System entwickelt,
mit dem man die AS-weiten Verkehrslenkungsstrategien eines ASes umsetzen kann – im
Gegensatz zum herk mmlichen Verfahren, wo die Strategien auf Komponentenbene umge-
setzt wird. Damit wird eine Abstraktionsebene geschaffen, die auch viele Vorteile im oper-
ationalen Betrieb aufweist. Dies zeigt sich an unseren Erfahrung, die wir beim Einsatz des
Systems im Netz der Deutschen Telekom gewonnen haben.
Da allerdings die Ausdrucksm glichkeiten den Verkehr zu lenken sehr vielf ltig sind, f hrt
dies zu komplexen Interaktionen und Dynamiken, die sich auf das gesamte Internet auswirken.
Um diese Dynamiken zu verstehen, stellen wir Methoden vor, die Administratoren helfen
k nnen, problematische Routingzust nde zu identi zieren und zu lokalisieren.
W hrend die meisten der heutigen Verkehrslenkungsprobleme aus solchen Interaktion entste-
hen, so gibt es andere, die direkt von der Router-Software/Hardware ausgel st werden –
solche Problem h tte man in einem geeigneten Test-Labor beheben sollen, bevor das Ger t in
das Produktionsnetzwerk aufgenommen wurde. Wir beschreiben einen BGP-Lastgenerator,
welcher in einer Vielzahl von Ger tetests eingesetzt werden kann. Wir illustrieren seine
F higkeiten exemplarisch daran, dass wir erkl ren, wie man komplexe Tests aufsetzt, ohne
dass sich der Anwender in Details verliert.
iiAbstract
Even today, given the widespread usage and critical importance of the Internet, its basic
routing protocols such as the Border Gateway Protocol (BGP) are poorly understood. This
is in part an artifact of the complex interactions that arise from a distributed system that is
administered locally to achieve a global task: reachability. In another part it has its origin
in the fact that inter-domain routing policies of autonomous systems (ASes) often undergo
constant adjustments for reasons of traf c engineering and/or to address speci c customer
wishes, an error prone approach.
In this thesis we address these problems in multiple ways:
The problem of policy con gurations by developing a system that allows us to manage the
overall routing architecture rather than each individual router. With this we raise the abstrac-
tion level from individual BGP con guration statements to an AS-wide routing policy.
The richness of policy expressions leads to complex interactions and dynamics that can be
observed throughout the Internet. We present a methodology that helps operators to detect
problematic routing conditions, and we discuss how to identify that AS which is responsible
for an instability.
While we nd that some of todays routing issues are stemming from protocol interactions,
others are coming from router software/hardware problems that should have been detected
in a test-lab before deployment in the operational network. We describe a BGP workload
generator that can help in a wide variety of equipment testing. We illustrate the capabilities of
the tool by showing how complex tests can be instantiated, without of losing the test engineer
in the intricacies of the test setup.
iiiContents
Contents iv
1 Introduction 1
1.1 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Vorver ffentlichte Teile der Dissertation (Previously Published Work) . . . . 4
2 Internet Routing Architecture 7
2.1 BGP basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 BGP path selection and ltering . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Passive BGP data collection architectures . . . . . . . . . . . . . . . 15
2.2 Router con guration and RPSL . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 State of the art and related work . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1 Con guration management . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 BGP dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.3 Router testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 AS-Wide Inter-Domain Routing Policies 25
3.1 Network-wide routing policy . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 System design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Concepts underlying the con gurator input . . . . . . . . . . . . . . 27
3.2.2 Enabling abstract routing policy speci cation . . . . . . . . . . . . . 30
3.2.3 Design alternatives for the con gurator . . . . . . . . . . . . . . . . 31
3.2.4 Advantages of the approach . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Data model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.1 Network Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.2 Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.3 Back-end module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
ivCONTENTS
3.3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4 Con gurator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 Operational considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.5.1 Generated con glets: Examples . . . . . . . . . . . . . . . . . . . . 45
3.5.2 Experiences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 BGP Dynamics 49
4.1 Instability creators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3 BGP Convergence Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.5 Data sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.6 BGP Beacons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.6.1 Prevalent behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.6.2 Slow convergence events . . . . . . . . . . . . . . . . . . . . . . . . 57
4.7 BGP dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5 Locating Internet Routing Instabilities 63
5.1 Ideal methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1.1 Basic methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1.2 Cautions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.1.3 Identifying link changes . . . . . . . . . . . . . . . . . . . . . . . . 68
5.1.4 Consideration of multiple pre xes . . . . . . . . . . . . . . . . . . . 69
5.2 Adopted methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.1 Candidate sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2.2 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.2.3 Correlated events . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.3 Data sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.4 What if – simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.4.1 Controlled experiments . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.5 What is – data analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
vCONTENTS
5.5.1 Update bursts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5.2 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5.3 Instability candidates . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.5.3.1 Beacons . . . . . . . . . . . . . . . . . . . . . . . . . . .