Scalable Topology Discovery and Link State Detection using Routing Events
Authors
Mudhakar Srivatsa, Bong-Jun Ko, Alina Beygelzimer and Venkateshwara Madduri
Abstract
In 27th IEEE Symposium on Reliable Distributed Systems (SRDS), 2008
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.
Publication Date
October, 2008
Venue
27th IEEE Symposium on Reliable Distributed Systems (SRDS)
Published To
Conference
Publication Type
Externally published
ITA Area
Project 2, Technical area 1
Download a copy of the paper here
srivatsaMScalable.pdf
Return to main page