Project Overview

BGP updates are triggered by a variety of events such as link failures, session resets, router crashes, policy or configuration changes. Making sense of BGP update streams and inferring their underlying causes is important in trouble-shooting BGP and improving its performance. In this paper we propose a novel methodology to identify BGP updates associated with major events-- affecting network reachability to multiple ASes-- and separating them (statistically) from those attributable to minor events, which individually generate few updates, but collectively form the persistent background noise observed at BGP vantage points. Our methodology is based on principal component analysis (PCA), which enables us to transform and reduce the BGP updates into different AS clusters that are likely affected by distinct major events. We also perform ``spatial correlation'' and ``type-of-change'' analysis based on AS PATH attributes to further validate and corroborate our findings. We demonstrate the accuracy and effectiveness of our methodology through simulations, and subsequently apply it to real BGP data. In addition, we corroborate our approach by analyzing updates corresponding to periods in which well-known routing events took place.

Publications

• Kuai Xu, Jaideep Chandrashekar, and Zhi-Li Zhang, "A First Step Towards Understanding Inter-domain Routing". In Proceedings of SIGCOMM Workshop on Mining Network Data, Philadelphia, PA, August 2005.
  
  
• Kuai Xu, Jaideep Chandrashekar, and Zhi-Li Zhang, "Inferring Major Events from BGP Update Streams". University of Minnesota, Department of Computer Science, Technical Report TR-04-043, November 2004.
  
  

Talks

Software