首页 | 本学科首页   官方微博 | 高级检索  
     


Exploring networks with traceroute-like probes: Theory and simulations
Authors:Luca Dall&rsquo  Asta,Ignacio Alvarez-Hamelin,Alain Barrat,Alexei Vá  zquez,Alessandro Vespignani
Affiliation:1. Laboratoire de Physique Théorique (UMR 8627 du CNRS), Bâtiment 210, Université de Paris-Sud, 91405 Orsay, Cedex, France;2. Nieuwland Science Hall, University of Notre Dame, Notre Dame, IN 46556, USA;3. School of Informatics and Department of Physics, Indiana University, Bloomington, IN 47408, USA
Abstract:Mapping the Internet generally consists in sampling the network from a limited set of sources by using traceroute-like probes. This methodology, akin to the merging of different spanning trees to a set of destination, has been argued to introduce uncontrolled sampling biases that might produce statistical properties of the sampled graph which sharply differ from the original ones. In this paper, we explore these biases and provide a statistical analysis of their origin. We derive an analytical approximation for the probability of edge and vertex detection that exploits the role of the number of sources and targets and allows us to relate the global topological properties of the underlying network with the statistical accuracy of the sampled graph. In particular, we find that the edge and vertex detection probability depends on the betweenness centrality of each element. This allows us to show that shortest path routed sampling provides a better characterization of underlying graphs with broad distributions of connectivity. We complement the analytical discussion with a throughout numerical investigation of simulated mapping strategies in network models with different topologies. We show that sampled graphs provide a fair qualitative characterization of the statistical properties of the original networks in a fair range of different strategies and exploration parameters. Moreover, we characterize the level of redundancy and completeness of the exploration process as a function of the topological properties of the network. Finally, we study numerically how the fraction of vertices and edges discovered in the sampled graph depends on the particular deployements of probing sources. The results might hint the steps toward more efficient mapping strategies.
Keywords:Traceroute   Internet exploration   Topology inference
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号