A Caltech Library Service

Active learning of multiple source multiple destination topologies

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.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription ItemJournal Article Paper
Additional Information:© 2013 IEEE. This work was supported by AFOSR grant FA9550-10-1-0310.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-10-1-0310
Record Number:CaltechAUTHORS:20170925-095252031
Persistent URL:
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81802
Deposited By: Tony Diaz
Deposited On:25 Sep 2017 17:04
Last Modified:15 Nov 2021 19:46

Repository Staff Only: item control page