moji5
27th July 2010, 09:04 PM
Active Topology Inference using Network Coding
Pegah Sattari (http://arxiv.org/find/cs/1/au:+Sattari_P/0/1/0/all/0/1), Christina Fragouli (http://arxiv.org/find/cs/1/au:+Fragouli_C/0/1/0/all/0/1), Athina Markopoulou (http://arxiv.org/find/cs/1/au:+Markopoulou_A/0/1/0/all/0/1)
(Submitted on 20 Jul 2010)
Our goal, in this paper, 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 tree topologies, we design hierarchical clustering algorithms, building on our prior work. For directed acyclic graphs (DAGs), first we decompose the topology into a number of two source, two receiver subnetwork components and then we merge these components to reconstruct the topology. Our approach for DAGs builds on prior work on tomography, 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.
Download:
PDF (http://arxiv.org/pdf/1007.3336v1)
PostScript (http://arxiv.org/ps/1007.3336v1)
Other formats (http://arxiv.org/format/1007.3336v1)
Pegah Sattari (http://arxiv.org/find/cs/1/au:+Sattari_P/0/1/0/all/0/1), Christina Fragouli (http://arxiv.org/find/cs/1/au:+Fragouli_C/0/1/0/all/0/1), Athina Markopoulou (http://arxiv.org/find/cs/1/au:+Markopoulou_A/0/1/0/all/0/1)
(Submitted on 20 Jul 2010)
Our goal, in this paper, 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 tree topologies, we design hierarchical clustering algorithms, building on our prior work. For directed acyclic graphs (DAGs), first we decompose the topology into a number of two source, two receiver subnetwork components and then we merge these components to reconstruct the topology. Our approach for DAGs builds on prior work on tomography, 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.
Download:
PDF (http://arxiv.org/pdf/1007.3336v1)
PostScript (http://arxiv.org/ps/1007.3336v1)
Other formats (http://arxiv.org/format/1007.3336v1)