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 multiple sources and receivers at the edge of the network, while intermediate nodes locally combine incoming probes before forwarding them. In previous tomography work, the correlation between the observed packet loss patterns has been used to infer the underlying topology. In contrast, our main idea behind using network coding is to introduce correlations among probe packets in a topology dependent manner and also develop algorithms that take advantage of these correlations to infer the network topology from end-host observations. Preliminary simulations illustrate the performance benefits of this approach. In particular, in the absence of packet loss, we can deterministically infer the topology, with very few probes; in the presence of packet loss, we can rapidly infer topology, even at very small loss rates (which was not the case in previous tomography techniques).
展开▼
