Algorithms for Large-Scale Topology Discovery

ISBN-13: 9783639164312 / Angielski / Miękka / 2009 / 176 str.

Benoit Donnet

Opis

There is a growing interest in discovery of internettopology at the interface level. A new generation of highly distributed measurement systemsis currently being deployed. Unfortunately, prior to this thesis, the researchcommunity has not examined the problem of how to perform such measurements efficiently andin a network-friendly manner. In this book, we make several contributions toward that end. First, we show that standard topology discovery methods are quite inefficient,repeatedly probing the same interfaces. This is a concern, because when scaled up, suchmethods will generate so much traffic that they will begin to resemble DDoS attacks. As it isnot unusual for a route tracing monitor to operate in isolation, we next propose and evaluatestrategies for reducing redundancy within a single monitor. We third propose andevaluate Doubletree, a cooperative algorithm that reduces redundancy simultaneously on routers andend systems. Finally, we also provide a generalization of Bloom filters, calledretouched Bloom filters, that permits false negatives in addition to false positives and allows atrade-off between the two.

O autorze

Benoit Donnet received his Ph.D. degree in computer science from
the Université Pierre
et Marie Curie in 2006. He is currently FNRS fellow at the
Université catholique de
Louvain. His research interests are in Internet measurements,
focusing on scalable
measurement techniques, Bloom filters, and traffic engineering
techniques.