Download
  PowerPoint [191KB]
  PDF [545KB]

Abstract
Despite significant efforts in engineering and plentiful experimentation, the complex behavior of large, heterogeneous networks is not always readily explicable. Routing instability, defined as the rapid change of network reachability and topology information, is one such behavior which has proven to be troublesome. In order to rectify this instability, its causes must be determined and their behaviors well-understood. The complex nature of the global Internet makes formal analysis an inviable approach, and we present simulation as an alternative.

With fast parallel discrete event simulators as our primary tool, we aim to model a complex, heterogeneous network in enough detail so as to reproduce routing instability. Having done so, we shall modify specific attributes of the network which are suspected causes of the instability, observing the response in network behavior. With this method we can determine the degree to which several network characteristics contribute to routing instability. Furthermore, we propose to test specific alternatives to certain network components and behaviors which we suspect as contributors.

Slide List
01.  Investigating the Causes of Inter-Domain Routing Instability
02.  Overview: PART I: Background
03.  The Complexity of Large Internetworks
04.  Internetworks and Routing
05.  Autonomous System example
06.  AS connectivity example
07.  Routing Instability
08.  Border Gateway Protocol [1 of 2]
09.  BGP between ASes
10.  Border Gateway Protocol [2 of 2]
11.  Observed Pathological Behaviors of Inter-Domain Routing [1 of 2]
12.  Observed Pathological Behaviors of Inter-Domain Routing [2 of 2]
13.  Overview: PART II: Hypotheses
14.  Modeling Routing Instability
15.  Suspected Causes [1 of 3]
16.  Suspected Causes [2 of 3]
17.  Suspected Causes [3 of 3]
18.  Coping Strategies [1 of 2]
19.  Coping Strategies [2 of 2]
20.  Overview: PART III: Investigation
21.  Network Experimentation Techniques
22.  Feasibility of Simulating Instability [1 of 3]
23.  Feasibility of Simulating Instability [2 of 3]
24.  Feasibility of Simulating Instability [3 of 3]
25.  Model Requirements [1 of 3]
26.  Model Requirements [2 of 3]
27.  Model Requirements [3 of 3]
28.  Model Implementation: Suspected Causes [1 of 2]
29.  Model Implementation: Suspected Causes [2 of 2]
30.  Model Implementation: Coping Strategies
31.  Identifying and Measuring Instability
32.  Summary