CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20170925-095252031

[img] PDF - Submitted Version
See Usage Policy.

862Kb

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:
URLURL TypeDescription
https://doi.org/10.1109/CISS.2013.6552253DOIArticle
http://ieeexplore.ieee.org/document/6552253PublisherArticle
http://resolver.caltech.edu/CaltechAUTHORS:20170925-101553300Related ItemJournal Article
https://arxiv.org/abs/1212.2310arXivDiscussion Paper
Additional Information:© 2013 IEEE. This work was supported by AFOSR grant FA9550-10-1-0310.
Funders:
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-10-1-0310
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:03 Oct 2019 18:47

Repository Staff Only: item control page