Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2013 | Submitted
Journal Article Open

Topology discovery of sparse random graphs with few participants

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. 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.

Additional Information

© 2012 Wiley Periodicals, Inc. Issue online: 20 June 2013; Version of record online: 27 April 2012; Manuscript Accepted: 17 February 2012; Manuscript Received: 23 March 2011. Supported in part by the setup funds at UCI and the AFOSR Award (FA9550-10-1-0310). A shorter version appears in Proceedings of ACM SIGMETRICS, June 2011.

Attached Files

Submitted - 1102.5063.pdf

Files

1102.5063.pdf
Files (368.6 kB)
Name Size Download all
md5:018f3bb5dfb3cc45949df59549309193
368.6 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 17, 2023