Tag Archives: Metrology

Plots

Life duration of peers in a P2P system

Life duration of peers in a P2P system

> By Lamia Benamara and Clémence Magnien In a P2P system, we study the time users stay connected to the system, which we approximate by the time elapsed between the first and the last query made by a given user. This plot shows the inverse cumulative distribution of this life-duration: the x axis represents the […]

Posted in Plots | Also tagged , |
Plots

Moving nodes along routes

Moving nodes along routes

> By Elie Rotenberg and Christophe Crespelle This plot shows how distance between hosts seen among traceroute outputs and the targets of these traceroutes are likely to be multiple regarding to their average distance. The data is gathered as follows. We first pick up 60 random, ping-answering IP addresses. We then send successively one traceroute […]

Posted in Plots | Also tagged , |
Plots

Efficient Measurement of Complex Networks Using Link Queries

Efficient Measurement of Complex Networks Using Link Queries

> By 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 […]

Posted in Plots | Also tagged |
Plots

Relevance of observed properties

Relevance of observed properties

> By Matthieu Latapy and Clémence Magnien In practice, most complex networks are not directly available: we know them through a measurement procedure only. Such measurements generally give partial samples, which may moreover be biased. However, one generally assumes that the properties observed on the obtained samples are representative of the ones of the actual […]

Posted in Plots | Also tagged , |
Plots

Reliability of observations of the internet’s topology

Reliability of observations of the internet's topology

> By Frédéric Ouédraogo and Clémence Magnien It is possible to explore the internet’s topology by tracing the paths between some source machines and some destination machines. In this way one obtains a subset of this topology. We study here the reliability of the observed properties of this topology, i.e. whether the properties of the […]

Posted in Plots | Also tagged , |
Papers

Detection, Understanding, and Prevention of Traceroute Measurement Artifacts

Fabien Viger, Brice Augustin, Xavier Cuvellier, Clémence Magnien, Matthieu Latapy, Timur Friedman, and Renata Teixeira

Traceroute is widely used: from the diagnosis of network problems to the assemblage of internet maps. Unfortunately, there are a number of problems with traceroute methodology, which lead to the inference of erroneous routes. This paper studies particular structures arising in nearly all traceroute measurements. We characterize them as "loops", "cycles", and "diamonds". We identify load balancing as a possible cause for the appearance of false loops, cycles and diamonds, i.e., artifacts that do not represent the internet topology. We provide a new publicly-available traceroute, called Paris traceroute, which, by controlling the packet header contents, provides a truer picture of the actual routes that packets follow. We performed measurements, from the perspective of a single source tracing towards multiple destinations, and Paris traceroute allowed us to show that many of the particular structures we observe are indeed traceroute measurement artifacts.

Fabien Viger, Brice Augustin, Xavier Cuvellier, Clémence Magnien, Matthieu Latapy, Timur Friedman, and Renata Teixeira

Posted in Papers | Also tagged , |
Papers

Complex Network Measurements: Estimating the Relevance of Observed Properties

Matthieu Latapy and Clémence Magnien

Complex networks, modeled as large graphs, received much attention during these last years. However, data on such networks is only available through intricate measurement procedures. Until recently, most studies assumed that these procedures eventually lead to samples large enough to be representative of the whole, at least concerning some key properties. This has crucial impact on network modeling and simulation, which rely on these properties. Recent contributions proved that this approach may be misleading, but no solution has been proposed. We provide here the first practical way to distinguish between cases where it is indeed misleading, and cases where the observed properties may be trusted. It consists in studying how the properties of interest evolve when the sample grows, and in particular whether they reach a steady state or not. In order to illustrate this method and to demonstrate its relevance, we apply it to data-sets on complex network measurements that are representative of the ones commonly used. The obtained results show that the method fulfills its goals very well. We moreover identify some properties which seem easier to evaluate in practice, thus opening interesting perspectives.

Matthieu Latapy and Clémence Magnien

Posted in Papers | Also tagged , , , |
Papers

Distance distribution in random graphs and application to network exploration

Vincent D. Blondel, Jean-Loup Guillaume, Julien M. Hendrickx, and Raphaël M. Jungers

We consider the problem of determining the proportion of edges that are discovered in an Erdős–Rényi graph when one constructs all shortest paths from a given source node to all other nodes. This problem is equivalent to the one of determining the proportion of edges connecting nodes that are at identical distance from the source node. The evolution of this quantity with the probability of existence of the edges exhibits intriguing oscillatory behavior. In order to perform our analysis, we introduce a different way of computing the distribution of distances between nodes. Our method outperforms previous similar analyses and leads to estimates that coincide remarkably well with numerical simulations. It allows us to characterize the phase transitions appearing when the connectivity probability varies.

Vincent D. Blondel, Jean-Loup Guillaume, Julien M. Hendrickx, and Raphaël M. Jungers

Posted in Papers | Tagged |
Papers

Complex Network Metrology

Jean-Loup Guillaume and Matthieu Latapy

In order to study some complex networks like the Internet, the Web, social networks or biological networks, one first has to explore them. This gives a partial and biased view of the real object, which is generally assumed to be representative of the whole. However, up to now nobody knows how and how much the measure influences the results. Using the example of the Internet and a rough model of its exploration process, we show that the way a given complex network is explored may strongly influence the observed properties. This leads us to argue for the necessity of developing a science of metrology of complex networks. Its aim would be to study how the partial and biased view of a network relates to the properties of the whole network.

Jean-Loup Guillaume and Matthieu Latapy

Posted in Papers | Also tagged |
Papers

Relevance of Massively Distributed Explorations of the Internet Topology: Qualitative Results

Jean-Loup Guillaume, Matthieu Latapy and Damien Magoni

Internet maps are generally constructed using the traceroute tool from a few sources to many destinations. It appeared recently that this exploration process gives a partial and biased view of the real topology, which leads to the idea of increasing the number of sources to improve the quality of the maps. In this paper, we present a set of experiments we have conducted to evaluate the relevance of this approach. It appears that the statistical properties of the underlying network have a strong influence on the quality of the obtained maps, which can be improved using massively distributed explorations. Conversely, some statistical properties are very robust, and so the known values for the Internet may be considered as reliable. We validate our analysis using real-world data and experiments, and we discuss its implications.

Jean-Loup Guillaume, Matthieu Latapy and Damien Magoni

Posted in Papers | Also tagged , |