Inferring the Origin of Routing Changes using Link Weights
The global Internet routing infrastructure is a large and complex distributed system where routing changes occur constantly. Our objective in this paper is to develop a simple and effective inference solution that can identify the AS or inter-AS link failures that trigger large scale routing changes in near realtime. We achieve this goal through a novel approach based on link weights. We measure the weight of each inter-AS link by the number of routes carried over that link, and keep track of its expected value and variance. We then correlate the weight changes of adjacent links and use a min-cut heuristic to find candidates for the origin of change. This work makes three contributions. First, we keep track of link weights rather than the routes of individual prefixes and thus our analysis is based on an aggregate view. Second, we use expected value and mean deviation of the link weights to identify routing events and distinguish route changes caused by failures from those by recoveries. Finally we use a min-cut heuristic based on the classification of routing events to accurately identify the AS or inter-AS link most likely responsible for the observed route changes. We verified our design using BGP data collected from operational Internet. Our efficient and accurate routing diagnosis solution can greatly help us gain better understanding of the dynamics in the operational Internet.
Mohit Lad Ricardo Oliveira Dan Massey Lixia Zhang
Computer Science Department, University of California, Los Angeles CA 90095 Computer Science Department, Colorado State University, Fort Collins, CO 80523
国际会议
The 15th IEEE International Conference on Network Protocols(ICNP 2007)(第15届IEEE国际网络协议大会)
北京
英文
93-102
2007-10-16（万方平台首次上网日期，不代表论文的发表时间）