A Network Coding Approach to Network Tomography
Network tomography aims at inferring internal network characteristics based on measurements at the edge of the network. In loss tomography, in particular, the characteristic of interest is the loss rate of individual links. There is a signiﬁcant body of work dedicated to this problem using multicast and/or unicast end-to-end probes. Independently, recent advances in network coding have shown that there are several advantages from allowing intermediate nodes to process and combine, in addition to just forward, packets. In this paper, we re-visit the problem of loss tomography in networks that have network coding capabilities. We design a novel framework for estimating link loss rates, which leverages network coding capabilities to improve several aspects of the tomography problem, including the identiﬁability of links, the tradeoff between accuracy of estimation and bandwidth efﬁciency, and the complexity of probe path selection. We present ﬁrst the case of tree topologies and then the case of general graphs. In the latter case, the beneﬁts of our approach are even more pronounced compared to standard techniques but we also face novel challenges, such as dealing with cycles and multiple paths between sources and receivers.
Record created on 2009-11-12, modified on 2016-08-08