Scalable Topology Discovery and Link State Detection Using Routing Events

Discovering the topology of a network and detecting link state changes (e.g.: link failures) is an essential element for various network management and monitoring tasks. In this paper, we investigate scalable mechanisms to monitor the topology and link states of networks based on information available in network nodes' routing tables. We first present an algorithm that infers the network topology based on the full or partial information about network distances between nodes, based on which we obtain a scalable network topology discovery solution via a novel use of random walk in graphs. We then present scalable algorithms to detect the state changes of remote links by monitoring the routing tables of a small fraction of the routers, where the routers to be monitored are selected by a greedy approach to an NP-complete Tree Cover problem. We show the efficacy and scalability of our topology monitoring algorithms through experimental evaluation performed both on synthetic topologies and on a large topology data-set from a real enterprise network.