Andrey Sapegin, Steve Uhlig

• The Border Gateway Protocol (BGP) is the core routing protocol in the Internet. It maintains reachability information towards IP networks, called prefixes. The adoption of BGP has come at a price: a steady growth in the routing table size (Meng et al., 2005) [1] as well as BGP updates (Cittadini et al., 2010)[2]. In this work, we take a different look at BGP updates, by quantifying the amount of prefix correlation in the BGP updates received by different routers in the Internet. We design a method to classify sets of BGP updates, called spikes, into either correlated or non-correlated, by comparing streams of BGP updates from multiple vantage points. Based on publicly available data, we show that a significant fraction of all BGP updates are correlated. Most of these correlated spikes contain updates for a few BGP prefixes only. When studying the topological scope of the correlated spikes, we find that they are relatively global given the limited AS hop distance between most ASs in the Internet, i.e., they propagate at least 2 or 3 ASThe Border Gateway Protocol (BGP) is the core routing protocol in the Internet. It maintains reachability information towards IP networks, called prefixes. The adoption of BGP has come at a price: a steady growth in the routing table size (Meng et al., 2005) [1] as well as BGP updates (Cittadini et al., 2010)[2]. In this work, we take a different look at BGP updates, by quantifying the amount of prefix correlation in the BGP updates received by different routers in the Internet. We design a method to classify sets of BGP updates, called spikes, into either correlated or non-correlated, by comparing streams of BGP updates from multiple vantage points. Based on publicly available data, we show that a significant fraction of all BGP updates are correlated. Most of these correlated spikes contain updates for a few BGP prefixes only. When studying the topological scope of the correlated spikes, we find that they are relatively global given the limited AS hop distance between most ASs in the Internet, i.e., they propagate at least 2 or 3 AS hops away. Most BGP updates visible from publicly available vantage points are therefore related to small events that propagate across multiple AS hops in the Internet, while a limited fraction of the BGP updates appear in large bursts that stay mostly localised. Our results shed light on a fundamental while often misunderstood aspect of BGP, namely the correlation between BGP updates and how it impacts our beliefs about the share of local and global BGP events in the Internet. Our work differs from the literature in that we try as much as possible to explicitly account in our methodology for the visibility of BGP vantage points, and its implication on the actual claims that can be made from the data. (C) 2013 Elsevier B.V. All rights reserved.…