Inferring Logical Topologies using Network Coding. Sattari, P., Markopoulou, A., & Fragouli, C. N/A, 2010.
abstract   bibtex   
The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity, etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network by sending probes between a given set of multiple sources and multiple receivers and by having intermediate nodes perform network coding operations. Our main idea behind using network coding is to introduce topologydependent correlation, which can be exploited at the receivers to infer the topology. We explored this idea in [33] for trees. We also combined network coding and tomographic techniques to infer the topology of a Directed Acyclic Graph (DAG), under specific routing assumptions, in [34]. The supporting idea in [34] was to decompose a traditional (i.e., without network coding) multiple source, multiple receiver tomography problem into multiple two source, two receiver subproblems, as shown in [12]. In this paper, we unify and extend our two previous pieces of work. Our main contribution is that when intermediate nodes perform network coding, topological information contained in network coded packets allows to uniquely identify a tree topology, or to accurately distinguish among all different 2-by-2 subnetwork components in a general DAG; this knowledge can then be used to merge the subnetworks and reconstruct the general topology. Our approach is applicable to any general Internet-like topology, and is robust to the presence of delay variability and packet loss.
@article{sattari_inferring_2010,
 abstract = {The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity, etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network by sending probes between a given set of multiple sources and multiple receivers and by having intermediate nodes perform network coding operations. Our main idea behind using network coding is to introduce topologydependent correlation, which can be exploited at the receivers to infer the topology. We explored this idea in [33] for trees. We also combined network coding and tomographic techniques to infer the topology of a Directed Acyclic Graph (DAG), under specific routing assumptions, in [34]. The supporting idea in [34] was to decompose a traditional (i.e., without network coding) multiple source, multiple receiver tomography problem into multiple two source, two receiver subproblems, as shown in [12]. In this paper, we unify and extend our two previous pieces of work. Our main contribution is that when intermediate nodes perform network coding, topological information contained in network coded packets allows to uniquely identify a tree topology, or to accurately distinguish among all different 2-by-2 subnetwork components in a general DAG; this knowledge can then be used to merge the subnetworks and reconstruct the general topology. Our approach is applicable to any general Internet-like topology, and is robust to the presence of delay variability and packet loss.},
 type={4},
 author = {Sattari, P. and Markopoulou, Athina and Fragouli, C.},
 journal = {N/A},
 tags = {network_coding},
 title = {Inferring {Logical} {Topologies} using {Network} {Coding}},
 year = {2010}
}

Downloads: 0