Fault Identification In The Internet Inter-domain Routing System

Fault management is deemed to be critical for the survivability and operability of the network. To develop an efficient fault identification mechanism for the Internet inter-domain routing system is the first step to the practical Internet-wide fault management. In the paper, we explicitly propose the problem of fault identification in the Internet inter-domain routing system for the first time, and develop a systematic and sophisticate algorithm to identify the BGP faults in the Internet inter-domain routing system. The algorithm fully utilizes the hidden temporal and topological correlations among the BGP routing updates to identify the common BGP faults that might trigger the routing updates. We first develop a novel BGP fault model, which provides an accurate and aggregate description of the dynamics of the Internet inter-domain routing system.We summarize the problem of identifying the topological correlations among the BGP routing path changes to a problem of BGP fault identification described in an optimization approach, and design an approximation algorithm to solve the problem.We propose a set of highly structured clustering-based algorithm framework to identify the BGP faults from the raw BGP routing updates. To capture the temporal correlations among the BGP routing path changes, we develop a sophisticated time-based clustering algorithm to cluster the BGP routing updates.To verify the correctness and accuracy of the algorithm, we implement the algorithm and design several systematic experiments to validate the algorithm. We examine the BGP routing data from several Internet vantage points with the algorithm. The analysis results show that, compared with the raw BGP routing updates, the inferred BGP faults describe the dynamics of the Internet in a more readable and concise manner; the change trends of the BGP faults precisely betray the characteristics of the dynamics of the Internet routing system. The validation demonstrates that the algorithm could capture the BGP faults with an accuracy of around 70%.