Failure Microscope: Precisely Diagnosing Routing Instability

Hongjun Liu, Baokang Zhao, Xiaofeng Hu, Dan Zhao, Xicheng LuIEICE Trans. Information and Systems 2013 · OpenReview

Introduction

The Border Gateway Protocol (BGP) serves as the fundamental mechanism for inter-domain routing on the Internet, enabling Autonomous Systems (ASes) to exchange reachability information. Despite its critical role, BGP is characterized by significant instability. When network events such as link failures or policy reconfigurations occur, routers engage in "path exploration"—a process of advertising and withdrawing multiple transient routes before converging on a new stable path. This "chattiness" complicates the task of network diagnosis.

The Challenge of Root Cause Analysis

For network operators, identifying the precise origin of routing instability is a formidable challenge. Traditional diagnostic tools often produce a broad "candidate set" of potential failure locations, typically encompassing four or more links, which lacks the precision required for rapid remediation. Furthermore, distinguishing between a physical link failure and a logical routing policy change (e.g., a local preference adjustment) is notoriously difficult when restricted to data from a single vantage point.

Various routing events such as link failures, recoveries, and local preference changes that complicate BGP diagnosis.

Methodology: The Failure Microscope

The "Failure Microscope" approach treats BGP update sequences as a geometric problem rather than a simple chronological list of path changes. The methodology is built upon three analytical pillars:

1. Closed Loop Analysis

During path exploration, the transient routes explored by a router often intersect, forming "closed loops." The spatial relationship between these loops—whether they are disjoint, intersecting, or contained within one another—serves as a unique fingerprint for the underlying event.

The formation of closed loops (Loop 1, 2, and 3) during the path exploration process following a link failure between AS 1 and AS 2.

2. Path Length Variation

The system utilizes mathematical theorems to correlate changes in the final stable path length with the characteristics of transient loops. For instance, a specific combination of path shortening and loop containment rules can definitively signal a link failure as opposed to a policy shift.

3. Path Exploration Modeling

By employing the Simple Path Vector Protocol (SPVP), the researchers model update propagation to identify "path increasing instances." This allows the system to filter out background noise from link restorations or routine local preference changes, focusing solely on the instability of interest.

Experimental Evaluation

The effectiveness of the Failure Microscope was validated using a combination of simulation and real-world data:

  • SSFNET: A standard BGP simulator for controlled event generation.
  • CAIDA AS-level Topology: Real-world maps from 2009 involving over 31,000 ASes.
  • Scalability Testing: Custom topologies ranging from 200 to 800 ASes were used to evaluate performance in increasingly complex environments.

Key Results

The Failure Microscope demonstrates unprecedented precision in routing diagnosis:

  • Absolute Accuracy: For events identified as link failures, the algorithm pinpoints the exact link with 100% accuracy, reducing the candidate set from the typical 4-7 links down to one.
  • Zero False Positives: In over 700 simulations of policy changes, the system never incorrectly flagged a policy shift as a link failure.
  • Positive Scalability: Interestingly, the identification rate improved as the network grew, rising from 24% in a 200-AS topology to 40% in an 800-AS environment.

Conclusion and Future Work

The Failure Microscope proves that a single vantage point can provide sufficient information to precisely diagnose remote network failures by analyzing the "messy middle" of transient path exploration. While currently limited by an identification rate of 15-40%—as not all failures trigger the necessary path exploration patterns—the system provides a blueprint for high-fidelity network monitoring. Future research aims to extend this precision to link weight changes and adapt the model to handle real-world noise like Route Flap Damping.

Summary updated

BibTeX
@article{liu2013failure,
  author = {Hongjun Liu and Baokang Zhao and Xiaofeng Hu and Dan Zhao and Xicheng Lu},
  title = {{Failure Microscope: Precisely Diagnosing Routing Instability}},
  journal = {IEICE Trans. Information and Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=hkA0UtxaOG_},
}
Figure