Tag Archives: Metrology

Papers

Evaluation of a new method for measuring the internet degree distribution: Simulation results

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 |
Papers

Impact of Sources and Destinations on the Observed Properties of the Internet Topology

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 procedures to 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 , |
Papers

Estimating properties in dynamic systems: the case of churn in P2P networks

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 , |
Papers

Rigorous measurement of IP-level neighborhood of Internet core routers

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 |
Plots

Accurate characterizing of session lengths in P2P system

Accurate characterizing of session lengths in P2P system

> 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 , |
Videos

Complex network measurement with link queries

Complex network measurement with link queries

> 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 |
Plots

Evaluation of the real degree of IP routers

Evaluation of the real degree of IP routers

> 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 |
Plots

Measuring clustering coefficient with different strategies

Measuring clustering coefficient with different strategies

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 |
Videos

Evolution of degree distribution during measurement

Evolution of degree distribution during measurement

> 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 , |
Papers

Efficient Measurement of Complex Networks Using Link Queries

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 |