A Network Coding Approach to Loss 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 and multicast and/or unicast end-to-end probes are typically used. Independen...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2013-03, Vol.59 (3), p.1532-1562
Main Authors: Sattari, P., Markopoulou, A., Fragouli, C., Gjoka, M.
Format: Article
Language:English
Subjects:
Applied sciences
Coding theory
Estimation
Exact sciences and technology
Information theory
Information, signal and communications theory
Link loss inference
Network coding
network tomography
Network topology
Probes
Receivers
Switching and signalling
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Tomography
Topology
Transmission and modulation (techniques and equipments)
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 and multicast and/or unicast end-to-end probes are typically used. Independently, recent advances in network coding have shown that there are advantages from allowing intermediate nodes to process and combine, in addition to just forward, packets. In this paper, we study the problem of loss tomography in networks with network coding capabilities. We design a framework for estimating link loss rates, which leverages network coding capabilities, and we show that it improves several aspects of tomography, including the identifiability of links, the trade-off between estimation accuracy and bandwidth efficiency, and the complexity of probe path selection. We discuss the cases of inferring link loss rates in a tree topology and in a general topology. In the latter case, the benefits 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. Overall, this work makes the connection between active network tomography and network coding.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2012.2236916