Active topology inference using network coding |
| |
| Institution: | 1. Calit2 Building, Suite 4100, UC Irvine, Irvine, CA 92697-2800, United States;2. EPFL IC ARNI, Building BC, Station 14, CH - 1015 Lausanne, Switzerland;1. Instituto de Ciencias Matemáticas, Consejo Superior de Investigaciones Científicas, C/ Nicolás Cabrera, no. 13-15, 28049 Madrid, Spain;3. Department of Electrical and Computer Engineering, George Mason University, Fairfax, VA 22030, USA;1. School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China;2. Department of Electrical and Computer Engineering, Utah State University, UT 84322, USA;3. School of Mathematics, Southwest Jiaotong University, Sichuan 610031, China;1. School of Automation, Northwestern Polytechnical University, 127 West Youyi Road, 710 072 Xi''an Shaanxi, PR China;2. Institute of Information Theory and Automation of the CAS, Pod Vodárenskou věží4, 182 08 Prague 8, Czech Republic;1. Department of Mathematics, University of Trier, Germany;2. Department of Mathematics, Baylor University, TX, USA;3. Department of Mathematics, KU Leuven, Belgium;1. Stanford University, Department of Electrical Engineering, Stanford, CA 94305, United States;2. Stanford University, Department of Mathematics and Statistics, Sequoia Hall, 390 Serra Mall, Stanford, CA 94305-4065, United States;3. University of California, San Diego, Department of Mathematics, 9500 Gilman Drive #404, La Jolla, CA 92093, United States;4. Center for Communications Research, Princeton, NJ 08540, United States |
| |
| Abstract: | Our goal, is to infer the topology of a network when (i) we can send probes between sources and receivers at the edge of the network and (ii) intermediate nodes can perform simple network coding operations, i.e., additions. Our key intuition is that network coding introduces topology-dependent correlation in the observations at the receivers, which can be exploited to infer the topology. For undirected tree topologies, we design hierarchical clustering algorithms, building on our prior work in Fragouli et al. (2006). For directed acyclic graphs (DAGs), first we decompose the topology into a number of two-source, two-receiver (2-by-2) subnetwork components and then we merge these components to reconstruct the topology. Our approach for DAGs builds on prior work on tomography in Rabbat et al. (2006), and improves upon it by employing network coding to accurately distinguish among all different 2-by-2 components. We evaluate our algorithms through simulation of a number of realistic topologies and compare them to active tomographic techniques without network coding. We also make connections between our approach and alternatives, including passive inference, traceroute, and packet marking. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
