Christophe Crespelle and Fabien Tarissan
Many contributions rely on the degree distribution of the Internet topology. However, current knowledge of this property is based on biased and erroneous measurements and is subject to much debate. Recently, a new approach, referred to as the Neighborhood Flooding method, was proposed to avoid issues raised by classical measurements. It aims at measuring the neighborhood of Internet core routers by sending traceroute probes from many monitors distributed in the Internet towards a given target router. In this paper, we investigate the accuracy of this method with simulations. Our results show that Neighborhood Flooding is free from the bias highlighted in the classical approach and is able to observe properly the exact degree of a vast majority of nodes in the core of the network. We show how the quality of the estimation depends on the number of monitors used and we carefully examine the influence of parameters of the simulations on our results. We also point out some limitations of the Neighborhood Flooding method and discuss their impact on the observed distribution.
Posted in Papers Also tagged internet
Frédéric Ouédraogo, Clémence Magnien
Maps of the internet topology are generally obtained by measuring the
routes from a given set of sources to a given set of destinations
(with tools such as traceroute). It has been shown that this
approach misses some links and nodes. Worse, in some cases it can
induce a bias in the obtained data, i.e. the properties of
the obtained maps are significantly different from those of the real
topology. In order to reduce this bias, the general approach
consists in increasing the number of sources. Some works have
studied the relevance of this approach. Most of them have used
theoretical results, or simulations on network models. Some papers
have used real data obtained from actual measurement
evaluate the importance of the number of sources and
destinations, but no work to our knowledge has studied extensively
the importance of the choice of sources or destinations.
Here, we use real data from internet topology measurements to study this question: by comparing partial measurements to
our complete data, we can evaluate the impact of adding sources or
destinations on the observed properties.
We show that the number of sources and destinations used plays a
role in the observed properties, but that their choice, and not only
their number, also has a strong influence on the observations. We
then study common statistics used to describe the internet topology,
and show that they behave differently: some can be trusted once the
number of sources and destinations are not too small, while others
are difficult to evaluate.
Posted in Papers Also tagged internet, radar
Lamia Benamara and Clémence Magnien
In many systems, such as P2P systems, the dynamicity of participating elements, or churn, has a strong impact. As a consequence, many efforts have been made to characterize it, and in particular to capture the session length distribution. However in most cases, estimating it rigorously is difficult. One of the reasons is that, because the observation window is by definition finite, parts of the sessions
that begin before the window and/or end after it are missed. This induces a bias. Although it tends to decrease when the observation window length increases, it is difficult to quantify its importance, or how fast it decreases.
Here, we introduce a general methodology that allows us to know if the observation window is long enough to characterize a given property. This methodology is not specific to one study case and may be applied to any property in a dynamic system. We apply this methodology to the study of session lengths in a massive measurement of P2P activity in the eDonkey system. We show that the measurement needs to last for at least one week in order to obtain representative results. We also show that our methodology allows us to precisely characterize the shape of the session length distribution.
Posted in Papers Also tagged dynamics, p2p
Christophe Crespelle, Matthieu Latapy, Elie Rotenberg
Many contributions use the degree distribution of IP-level internet topology. However, current knowledge of this property relies on biased and erroneous measurements, and so it is subject to much debate. We introduce here a new approach, dedicated to the core of the internet, which avoids the issues raised by classical measurements. It is based on the measurement of IP-level neighborhood of internet core routers, for which we design and implement a rigorous method. It consists in sending traceroute probes from many monitors distributed in the internet towards a given target router and carefully selecting the relevant information in collected data. Using simulations, we provide strong evidence of the accuracy of our approach. We then conduct real-world measurements illustrating the practical effectiveness of our method. This constitutes a significant step towards reliable knowledge of the IP-level degree distribution of the core of the internet.
Posted in Papers Also tagged internet
> Lamia Benamara et Clémence magnien When trying to characterize the dynamics of a system, we are faced with two problems. First, the observation window must be long enough to be representative. Second, the fact that it is finite still induces a bias in the observations, sessions beginning/ending before/after the measurement window are not seen […]
Posted in Plots Also tagged dynamics, p2p
> By Fabien Tarissan, Matthieu Latapy and Christophe Prieur Download In many cases, complex networks are not directly available: one has to conduct an expensive measurement procedure in order to collect information on their structure. One then obtains a sample of the network under concern, which is in general only a small part of the […]
Posted in Videos Tagged Metrology
> By Elie Rotenberg, Christophe Crespelle and Matthieu Latapy Here, we aim at measuring the IP-level neighborhood of internet core routers in a rigorous way. We proceed as follows. First, we send traceroute probes from many monitors distributed in the internet towards a given target router. Then we consider the last but one IP adress […]
Posted in Plots Also tagged internet
By Fabien Tarissan, Matthieu Latapy and Christophe Prieur In a previous study presented in Efficient Measurement of Complex Networks Using Link Queries, we showed that different measurement strategies behave very differently as regard the rapidity for retrieving existing links in large complex networks. It appeared in particular that the strategies based on the degree distribution […]
Posted in Plots Also tagged clustering
> By Clémence Magnien and Matthieu Latapy Download When one wants to study a complex network, one generally first has to conduct an intricate and expensive measurement. This measurement gives a sample of the network which is generally partial and may be biased. In Complex Network Measurements: Estimating the Relevance of Observed Properties we propose […]
Posted in Videos Also tagged measurement, p2p
Fabien Tarissan, Matthieu Latapy and Christophe Prieur
Complex networks are at the core of an intense research activity. However, in most cases, intricate and costly measurement procedures are needed to explore their structure. In some cases, these measurements rely on link queries: given two nodes, it is possible to test the existence of a link between them. These tests may be costly, and thus minimizing their number while maximizing the number of discovered links is a key issue. This is a challenging task, though, as initially no information is known on the network. This paper studies this problem: we observe that properties classically observed on real-world complex networks give hints for their efficient measurement; we derive simple principles and several measurement strategies based on this, and experimentally evaluate their efficiency on real-world cases. In order to do so, we introduce methods to evaluate the efficiency of strategies. We also explore the bias that different measurement strategies may induce.
Posted in Papers Tagged Metrology