Diagnosing Network Disruptions with Network-wide Analysis

Authors: Yiyi Huang, Nick Feamster, Anukool Lakhina, Jun (Jim) Xu

Complete Citation

Yiyi Huang, Nick Feamster, Anukool Lakhina, and Jun (Jim) Xu. Diagnosing Network Disruptions with Network-wide Analysis. SIGMETRICS '07 Conference Proceedings, Pages: 61 - 72. DOI=http://doi.acm.org/10.1145/1269899.1254890

Abstract

To maintain high availability in the face of changing network conditions, network operators must quickly detect, identify, and react to events that cause network disruptions. One way to accomplish this goal is to monitor routing dynamics, by analyzing routing update streams collected from routers. Existing monitoring approaches typically treat streams of routing updates from different routers as independent signals, and report only the "loud" events (i.e., events that involve large volume of routing messages). In this paper, we examine BGP routing data from all routers in the Abilene backbone for six months and correlate them with a catalog of all known disruptions to its nodes and links. We find that many important events are not loud enough to be detected from a single stream. Instead, they become detectable only when multiple BGP update streams are simultaneously examined. This is because routing updates exhibit network-wide dependencies.

This paper proposes using network-wide analysis of routing information to diagnose (i.e., detect and identify) network disruptions. To detect network disruptions, we apply a multivariate analysis technique on dynamic routing information, (i.e., update traffic from all the Abilene routers) and find that this technique can detect every reported disruption to nodes and links within the network with a low rate of false alarms. To identify the type of disruption, we jointly analyze both the network-wide static configuration and details in the dynamic routing updates; we find that our method can correctly explain the scenario that caused the disruption. Although much work remains to make network-wide analysis of routing data operationally practical, our results illustrate the importance and potential of such an approach.

Annotations

First, this paper studies the relationship between BGP update information and network disruptions (including node, link, and peer session failures). Then, it proposes using network-wide analysis of routing information (rather than the information in a single router) to diagnose network disruptions. Specifically, it applies a multivariate analysis technique, Principal Component Analysis (PCA), to routing message streams across the routers in a single network (Abilene).

Findings:

• Many network disruptions cause only low volumes of routing messages at any single router.
• About 90% of local network disruptions are visible in BGP routing streams. (?)
• The number of updates resulting from a disruption may vary by several orders of magnitude.
• About 75% of network disruptions result in near simultaneous BGP routing messages at two or more routers.
• The PCA-based subspace method detects 100% of node and link disruptions and about 60% of disruptions to peering links, with a low rate of false alarms.
• The identification algorithm based on hybrid static and dynamic analysis correctly identifies 100% of node disruptions, 74% of link disruptions, and 93% of peer disruptions.

-- YingxinJiang - 10 Oct 2007