Topology Discovery of Sparse Random Graphs With Few Participants
Venue
ACM International Conference on Measurement and Modeling of Computer Systems SIGMETRICS (2011), Best Paper Award
Publication Year
2011
Authors
Animashree Anandkumar, Avinatan Hassidim, Jonathan Kelner
BibTeX
Abstract
We consider the task of topology discovery of sparse random graphs using end-to-end
random measurements (e.g., delay) between a subset of nodes, referred to as the
participants. The rest of the nodes are hidden, and do not provide any information
for topology discovery. We consider topology discovery under two routing models:
(a) the participants exchange messages along the shortest paths and obtain
end-to-end measurements, and (b) additionally, the participants exchange messages
along the second shortest path. For scenario (a), our proposed algorithm results in
a sub-linear edit-distance guarantee using a sub-linear number of uniformly
selected participants. For scenario (b), we obtain a much stronger result, and show
that we can achieve consistent reconstruction when a sub-linear number of uniformly
selected nodes participate. This implies that accurate discovery of sparse random
graphs is tractable using an extremely small number of participants. Our algorithms
are simple to implement, computationally efficient, and exploit the locally
tree-like property of sparse random graphs. We finally obtain a lower bound on the
number of participants required by any algorithm to reconstruct the original random
graph up to a given edit distance. We also demonstrate that while consistent
discovery is tractable for sparse random graphs using a small number of
participants, in general, there are graphs which cannot be discovered by any
algorithm even with a significant number of participants, and with the availability
of end-to-end information along all the paths between the participants.
