 Main
Active Learning of Multiple Source Multiple Destination Topologies
Published Web Location
https://doi.org/10.1109/tsp.2014.2304431Abstract
We consider the problem of inferring the topology of a network with M sources and N receivers (an M byN network), by sending probes between the sources and receivers. Prior work has shown that this problem can be decomposed into two parts: first, infer smaller subnetwork components (1byN 's or 2by2's) and then merge them to identify the M byN topology. We focus on the second part, which had previously received less attention in the literature. We assume that a 1byN topology is given and that all 2by2 components can be queried and learned using endtoend probes. The problem is which 2by2's to query and how to merge them with the given 1byN, so as to exactly identify the 2byN topology, and optimize a number of performance metrics, including the number of queries (which directly translates into measurement bandwidth), time complexity, and memory usage. We provide a lower bound, [N], on the number of 2by2's required by any active learning algorithm and propose two greedy algorithms. The first algorithm follows the framework of multiple hypothesis testing, in particular Generalized Binary Search (GBS). The second algorithm is called the Receiver Elimination Algorithm (REA) and follows a bottomup approach. It requires exactly N1 steps, which is much less than all N possible 2by2's. Simulation results demonstrate that both algorithms correctly identify the 2byN topology and are nearoptimal, but REA is more efficient in practice. © 19912012 IEEE.
Many UCauthored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
Enter the password to open this PDF file:













