دانلود رایگان مقاله اندازه گیری رویدادهای BGP در مقیاس بزرگ

Abstract

Measurement on the Border Gateway Protocol (BGP) system is important for understanding the Internet. Many attempts have been made to detect anomalous Internet events through dissecting BGP updates and tables. We notice that most works in this field either deploy/use few monitors or analyze aggregated statistics. Such practices may result in overestimating the impact of monitor-local events, which can be viewed by only a small area. We propose Large-scale BGP Event (LBE), which affects many IP prefixes (high impact) and is widely observable (non-local). To detect LBE, we propose the Update Visibility Matrix (UVM) to record the prefix and monitor related to each update. We formulate the problem of identifying LBE in UVM, which is NP-hard. Then we propose a heuristic algorithm to solve it. We apply the scheme to 2.18 TB of BGP updates and find that the identified LBEs are highly correlated with many well-known disruptive incidents. Besides, we identify 101 LBEs that have never been investigated before. By conducting case studies, we find that the LBEs have high impact and are caused by various reasons. Our work can assist in network/Internet management tasks such as problem prevention, diagnosis, and recovery.

7. Conclusion

Most of the traditional works on detecting and analyzing anomalies in the BGP system are prone to the artifact related to monitor-local events. To cope with the issue, we propose the concept of Update Visibility Matrix (UVM) and Large-scale BGP Event (LBE). We formulate the problem of identifying LBE in UVM, then propose an algorithm to solve it. Our method explicitly avoids the detection of monitor-local and low-impact events. We apply the method to the updates related to twelve famous incidents and observe a strong correlation between the incidents and the identi- fied LBEs. We also analyze ten months’ data in 2013 and identify 101 LBEs that have never been detected and investigated before. The analysis of these identified LBEs validates the effectiveness of our method and basic idea. Finally, we conduct case studies on three incidents in the 2013 data set, which involve 23 LBEs. The detailed examination shows the high impact and cause of these incidents, which further enhance the importance of our work. The measurement results suggest that our study could be helpful in network/Internet operation, management, and monitoring tasks.