Bias Reduction in Traceroute Sampling – Towards a More Accurate Map of the Internet

DOI10.1007/978-3-540-77004-6_1MaRDI QIDQ5458296zbMATHOpenAlexFDO

Authors Abraham D. Flaxman, Juan Vera

Publication date 11 April 2008

Published in Algorithms and Models for the Web-Graph (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.3243

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10)

Abstract: Traceroute sampling is an important technique in exploring the internet router graph and the autonomous system graph. Although it is one of the primary techniques used in calculating statistics about the internet, it can introduce bias that corrupts these estimates. This paper reports on a theoretical and experimental investigation of a new technique to reduce the bias of traceroute sampling when estimating the degree distribution. We develop a new estimator for the degree of a node in a traceroute-sampled graph; validate the estimator theoretically in Erdos-Renyi graphs and, through computer experiments, for a wider range of graphs; and apply it to produce a new picture of the degree distribution of the autonomous system graph.

Recommendations

• On the bias of traceroute sampling
• On the bias of traceroute sampling
• Exploring networks with traceroute-like probes: Theory and simulations
• Bounding the bias of tree-like sampling in IP topologies
• Sampling networks by the union of \(m\) shortest path trees

Cited in

(8)

• A fast algorithm to find all high-degree vertices in graphs with a power-law degree sequence
• Graph sampling for Internet topologies using normalized Laplacian spectral features
• On the bias of traceroute sampling
• Exploring networks with traceroute-like probes: Theory and simulations
• Relevance of massively distributed explorations of the internet topology: qualitative results
• On the bias of traceroute sampling
• Bounding the bias of tree-like sampling in IP topologies
• Detection, understanding, and prevention of traceroute measurement artifacts

This page was built for publication: Bias Reduction in Traceroute Sampling – Towards a More Accurate Map of the Internet

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458296)