direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Marco Caninis's Publications

Misleading Stars: What Cannot Be Measured in the Internet?
Citation key PTS-MSWCBMITI-11
Author Pignolet, Yvonne Anne and Trédan, Gilles and Schmid, Stefan
Title of Book Proceedings of the 25th International Symposium on Distributed Computing (DISC '11)
Pages 311–325
Year 2011
ISBN 978-3-642-24099-7
ISSN 0302-9743
Online ISSN 1611-3349
DOI http://dx.doi.org/10.1007/978-3-642-24100-0_29
Location Rome, Italy
Address Berlin / Heidelberg, Germany
Volume 6950
Month September
Editor David Peleg
Publisher Springer
Series Lecture Notes in Computer Science (LNCS)
Organization EATCS
Abstract Traceroute measurements are one of our main instruments to shed light onto the structure and properties of today's complex networks such as the Internet. This paper studies the feasibility and infeasibility of inferring the network topology given traceroute data from a worst-case perspective, i.e., without any probabilistic assumptions on, e.g., the nodes' degree distribution. We attend to a scenario where some of the routers are anonymous, and propose two fundamental axioms that model two basic assumptions on the traceroute data: (1) each trace corresponds to a real path in the network, and (2) the routing paths are at most a factor 1/α off the shortest paths, for some parameter α ∈ (0, 1]. In contrast to existing literature that focuses on the cardinality of the set of (often only minimal) inferrable topologies, we argue that a large number of possible topologies alone is often unproblematic, as long as the networks have a similar structure. We hence seek to characterize the set of topologies inferred with our axioms. We introduce the notion of star graphs whose colorings capture the differences among inferred topologies; it also allows us to construct inferred topologies explicitly. We find that in general, inferrable topologies can differ significantly in many important aspects, such as the nodes' distances or the number of triangles. These negative results are complemented by a discussion of a scenario where the trace set is best possible, i.e., ''complete''. It turns out that while some properties such as the node degrees are still hard to measure, a complete trace set can help to determine global properties such as the connectivity.
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions