Sattari, Pegah and Kurant, Maciej and Anandkumar, Animashree and Markopoulou, Athina and Rabbat, Michael (2013) Active learning of multiple source multiple destination topologies. In: 47th Annual Conference on Information Sciences and Systems. IEEE , Piscataway, NJ, pp. 1-6. ISBN 978-1-4673-5237-6. https://resolver.caltech.edu/CaltechAUTHORS:20170925-095252031
![]() |
PDF
- Submitted Version
See Usage Policy. 883kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170925-095252031
Abstract
We consider the problem of inferring the topology of an M-by-N network by sending probes between M sources and N receivers. Prior work has shown that this problem can be decomposed into two parts: first, infer smaller subnetwork components (i.e., 1-by-N's or 2-by-2's) and then merge these components to identify the M-by-N topology. In this paper, we focus on the second part. In particular, we assume that a 1by-N topology is given and that all 2-by-2 components can be queried and learned using end-to-end probes. The problem is which 2-by-2's to query and how to merge them with the 1-byN, so as to exactly identify the 2-by-N topology, and optimize a number of performance metrics including measurement traffic, time complexity, and memory usage. We provide a lower bound, ⌈N/2⌉, on the number of 2-by-2's required by any active learning algorithm and we also propose a greedy algorithm that is nearoptimal and efficient in practice. It follows a bottom-up approach: at every step, it selects two receivers, queries the corresponding 2-by-2, and merges it with the given 1-by-N. The algorithm requires exactly N - 1 steps, which is much less than all (N:2) possible 2-by-2's, and it correctly identifies the 2-by-N topology.
Item Type: | Book Section | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||||||||
Additional Information: | © 2013 IEEE. This work was supported by AFOSR grant FA9550-10-1-0310. | |||||||||||||||
Funders: |
| |||||||||||||||
DOI: | 10.1109/CISS.2013.6552253 | |||||||||||||||
Record Number: | CaltechAUTHORS:20170925-095252031 | |||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170925-095252031 | |||||||||||||||
Official Citation: | P. Sattari, M. Kurant, A. Anandkumar, A. Markopoulou and M. Rabbat, "Active learning of multiple source multiple destination topologies," 2013 47th Annual Conference on Information Sciences and Systems (CISS), Baltimore, MD, 2013, pp. 1-6. doi: 10.1109/CISS.2013.6552253 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6552253&isnumber=6552191 | |||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||||||||
ID Code: | 81802 | |||||||||||||||
Collection: | CaltechAUTHORS | |||||||||||||||
Deposited By: | Tony Diaz | |||||||||||||||
Deposited On: | 25 Sep 2017 17:04 | |||||||||||||||
Last Modified: | 15 Nov 2021 19:46 |
Repository Staff Only: item control page