Network Discovery and Verification
Top Cited Papers
- 30 November 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 24 (12), 2168-2181
- https://doi.org/10.1109/jsac.2006.884015
Abstract
Due to its fast, dynamic, and distributed growth process, it is hard to obtain an accurate map of the Internet. In many cases, such a map-representing the structure of the Internet as a graph with nodes and links-is a prerequisite when investigating properties of the Internet. A common way to obtain such maps is to make certain local measurements at a small subset of the nodes, and then to combine these in order to "discover" (an approximation of) the actual graph. Each of these measurements is potentially quite costly. It is thus a natural objective to minimize the number of measurements which still discover the whole graph. We formalize this problem as a combinatorial optimization problem and consider it for two different models characterized by different types of measurements. We give several upper and lower bounds on the competitive ratio (for the online network discovery problem) and the approximation ratio (for the offline network verification problem) in both models. Furthermore, for one of the two models, we compare four simple greedy strategies in an experimental analysisKeywords
This publication has 18 references indexed in Scilit:
- Exploring networks with traceroute-like probes: Theory and simulationsTheoretical Computer Science, 2006
- On the bias of traceroute samplingPublished by Association for Computing Machinery (ACM) ,2005
- Statistical theory of Internet explorationPhysical Review E, 2005
- Robust monitoring of link delays and faults in IP networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- An analysis of Internet inter-domain topology and route stabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Size-dependent degree distribution of a scale-free growing networkPhysical Review E, 2001
- Emergence of Scaling in Random NetworksScience, 1999
- Some optimal inapproximability resultsPublished by Association for Computing Machinery (ACM) ,1997
- Landmarks in graphsDiscrete Applied Mathematics, 1996
- Probabilistic computations: Toward a unified measure of complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977