Network tomography via network coding

In this work we show how existing network coding algorithms can be used to perform network tomography, i.e., estimate network topology. We first examine a simple variant of the popular distributed random network codes proposed by Ho et al. [14], and show how it can enable each network node to passively estimate the network topology upstream of it at no cost to throughput. The delays introduced by each upstream node and link can also be similarly estimated. We then consider the scenario wherein an adversary hidden in the network wishes to disrupt the estimation of network topology. We show how network error-correcting codes can be used to reliably perform network tomography if the network has sufficient connectivity, and demonstrate that network tomography is impossible otherwise.