Network discovery and verification

Beerliova, Zuzana

doi:10.1109/JSAC.2006.884015

Network discovery and verification

2006-12-01

253

OA

AI

DOI：10.1109/JSAC.2006.884015

Original

Original request for help

Save

Abstract

En 中文

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 maker 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 analysis.

Keywords:

approximation algorithms

complex networks

Internet discovery

online algorithms

random graphs

Network discovery and verification

Abstract

Journal

Organization