Seminario Interdipartimentale di Algoritmica  

Monday, November 28, 2005, 12:00 noon
Traceroute-Like Exploration of Unknown Networks: A Statistical Analysis
Alain Barrat, Université de Paris-Sud

DIS - Department of Computer and System Sciences
Room C3, second floor

Abstract:

The general methodology used to construct Internet maps consists in merging all the discovered paths obtained by sending data packets from a set of active computers to a set of destination hosts, obtaining a graph-like representation of the network. This technique, sometimes referred to as Internet tomography, spurs the issue concerning the statistical reliability of such empirical maps. We tackle this problem by modeling the network sampling process and by using a mean-field approximation to obtain expressions for the probability of edge and vertex detection in the sampled graph. This allows a general understanding of the origin of possible sampling biases.

Moreover, the inference of many of the most basic topological quantities from traceroute measurements is in fact a version of the so-called `species problem' in statistics, which are often quite challenging.  We focus on the most fundamental example of a traceroute internet species: the number of nodes in a network.  We use statistical subsampling principles to derive two proposed estimators, and we illustrate the performance of these estimators on networks with various topological characteristics.

References: cs.NI/0510007, cs.NI/0412007, Phys. Rev. E 71 (2005) 036135.