Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Bigfoot, Sasquatch, the Yeti and other missing links: what we don't know about the AS graph
Author: Roughan, M.
Tuke, S.
Maennel, O.
Citation: Proceedings of the 8th ACM SIGCOMM conference on Internet measurement, 2008:pp.325-330
Publisher: IEEE
Publisher Place: USA
Issue Date: 2008
ISBN: 9781605583341
Conference Name: Internet Measurement Conference (2008 : Vouliagmeni, Greece)
Abstract: Study of the Internet's high-level structure has for some time intrigued scientists. The AS-graph (showing interconnections between Autonomous Systems) has been measured, studied, modelled and discussed in many papers over the last decade. However, the quality of the measurement data has always been in question. It is by now well known that most measurements of the AS-graph are missing some set of links. Many efforts have been undertaken to correct this, primarily by increasing the set of measurements, but the issue remains: how much is enough? When will we know that we have enough measurements to be sure we can see all (or almost all) of the links. This paper aims to address the problem of estimating how many links are missing from our measurements. We use techniques pioneered in biostatistics and epidemiology for estimating the size of populations (for instance of fish or disease carriers). It is rarely possible to observe entire populations, and so sampling techniques are used. We extend those techniques to the domain of the AS-graph. The key difference between our work and the biological literature is that all links are not the same, and so we build a stratified model and specify an EM algorithm for estimating its parameters. Our estimates suggest that a very significant number of links (many of thousands) are missing from standard route monitor measurements of the AS-graph. Finally, we use the model to derive the number of monitors that would be needed to see a complete AS-graph with high-probability. We estimate that 700 route monitors would see 99.9% of links.
Keywords: Matthew Roughan; Jonathan Tuke; Olaf Maennel [sor]
Description: Copyright © 2008 ACM
RMID: 0020085177
DOI: 10.1145/1452520.1452558
Published version:
Appears in Collections:Mathematical Sciences publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.