Matthew Caesar, Lakshminarayanan Subramanian and Randy H. Katz

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1292
2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1292.pdf

Today, we lack a clear understanding of the dynamics of the Border Gateway Protocol (BGP) and this has largely restricted our ability to address BGP's shortcomings. To gain more insight into BGP's dynamics, this paper proposes the design of a BGP health inferencing system that localizes the root causes of routing changes. Specifically, the inference system addresses two questions: What is the cause of a routing change? Where does a routing change originate? The inference system correlates routing updates across multiple vantage points to narrow down the suspect set of AS's that might have triggered routing changes. Our methodology is primarily targeted towards analyzing events affecting relatively stable prefixes (composing roughly 80% of the routing table), which are known to be the most popular destinations of Internet traffic. For 70% of observed updates to these prefixes, our approach can pinpoint the location of origin to a single inter-AS link. We analytically and empirically argue correctness of several key steps of our methodology and additionally show that our technique can correctly pinpoint the source of several well-known/documented routing events.

BibTeX citation:

@techreport{Caesar:CSD-03-1292,
    Author = {Caesar, Matthew and Subramanian, Lakshminarayanan and Katz, Randy H.},
    Title = {Towards Localizing Root Causes of BGP Dynamics},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/6364.html},
    Number = {UCB/CSD-03-1292},
    Abstract = {Today, we lack a clear understanding of the dynamics of the Border Gateway Protocol (BGP) and this has largely restricted our ability to address BGP's shortcomings. To gain more insight into BGP's dynamics, this paper proposes the design of a BGP health inferencing system that localizes the root causes of routing changes. Specifically, the inference system addresses two questions: What is the cause of a routing change? Where does a routing change originate? The inference system correlates routing updates across multiple vantage points to narrow down the suspect set of AS's that might have triggered routing changes. Our methodology is primarily targeted towards analyzing events affecting relatively stable prefixes (composing roughly 80% of the routing table), which are known to be the most popular destinations of Internet traffic. For 70% of observed updates to these prefixes, our approach can pinpoint the location of origin to a single inter-AS link. We analytically and empirically argue correctness of several key steps of our methodology and additionally show that our technique can correctly pinpoint the source of several well-known/documented routing events.}
}

EndNote citation:

%0 Report
%A Caesar, Matthew
%A Subramanian, Lakshminarayanan
%A Katz, Randy H.
%T Towards Localizing Root Causes of BGP Dynamics
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1292
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/6364.html
%F Caesar:CSD-03-1292