Measurement of large-scale BGP events: Definition, detection, and analysis
Measurement of large-scale BGP events: Definition, detection, and analysis
复制标题
大规模 BGP 事件的测量：定义、检测和分析
DOI：
10.1016/j.comnet.2016.09.018
复制
发表时间：
2016
影响因子：
5.6
通讯作者：
Yang Yuan
中科院分区：
文献类型：
--
作者：
Chen Meng;Xu Mingwei;Li Qing;Yang Yuan
边界网关协议（BGP）系统的测量对于理解互联网具有重要意义。已经进行了许多尝试来通过剖析BGP更新和表来检测异常Internet事件。我们注意到，在这个领域的大多数作品要么部署/使用很少的监视器或分析汇总的统计数据。这种做法可能会导致高估的影响，监测本地事件，这可以被视为只有一个小区域。我们提出了大规模的BGP事件（LBE），它会影响许多IP前缀（高影响）和广泛观察（非本地）。为了检测LBE，我们提出了更新可见性矩阵（UVM）来记录前缀和监视器相关的每个更新。我们制定的问题，识别LBE的UVM，这是NP难的。然后提出了一种启发式算法来解决该问题，并将该算法应用于2.18 TB的BGP更新，发现所识别的LBE与许多已知的破坏性事件高度相关。此外，我们还确定了101个以前从未调查过的LBE。通过案例分析，我们发现，地方性企业的影响力是很大的，其产生的原因是多方面的。我们的工作可以协助网络/Internet管理任务，如问题预防，诊断和恢复。
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.