Failure Microscope: Precisely Diagnosing Routing Instability

Hongjun LIU  Baokang ZHAO  Xiaofeng HU  Dan ZHAO  Xicheng LU  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D    No.4    pp.918-926
Publication Date: 2013/04/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.918
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Information Network
Keyword: 
root cause analysis,  BGP,  event identifying,  closed loop,  

Full Text: PDF>>
Buy this Article


Summary: 
Root cause analysis of BGP updates is the key to debug and troubleshoot BGP routing problems. However, it is a challenge to precisely diagnose the cause and the origin of routing instability. In this paper, we are the first to distinguish link failure events from policy change events based on BGP updates from single vantage points by analyzing the relationship of the closed loops formed through intersecting all the transient paths during instability and the length variation of the stable paths after instability. Once link failure events are recognized, their origins are precisely inferred with 100% accuracy. Through simulation, our method is effective to distinguish link failure events from link restoration events and policy related events, and reduce the size of candidate set of origins.