Amazon.com, Inc.
Network analysis using forwarding table information

Abstract:

A monitoring system is disclosed that achieves the benefits of active monitoring by providing a holistic view of the network, while obtaining the granularity of a passive monitoring system by testing a large majority or all of the prefixes. In one embodiment, streaming updates of a forwarding plane are captured for devices in a network. Additionally, an initial state of the forwarding plane can be captured for each device. A time-series graph of the forwarding plane can be constructed. In the graph, each node can represent a device and each edge can represent a possible path for a prefix at a given point in time. Graph analysis techniques can be used to analyze the graph and detect errors. For example, cycle detection algorithms can be used on the forwarding plane data to detect microloops. Other techniques can be used to find black holes or capacity bottlenecks.