Network Inference with Network Coding

Collaborators:

Christina Fragouli, EPFL, Lausanne.

Problem Statement

Monitoring is an important component for the operation of any network. We are particularly interested in a family of monitoring techniques, known as network tomography, which aim at inferring internal network characteristics by sending and collecting probe packets from the edge of the network. Prior work on network tomography considered networks that implement multicast and unicast forwarding. Independently, the network coding community advocates that additional functionality should be added to network nodes, to allow for processing of incoming packets before forwarding them. This functionality comes at the cost of additional processing but also brings the potential of significant performance benefits, as it has already been demonstrated in the context of peer-to-peer and wireless multi-hop networks.

In this work, we consider networks where internal nodes implement network coding and we re-visit two network tomography problems: (i) link loss inference and (ii) topology inference. We develop new techniques that make use of the network coding capabilities and we show that they improve several aspects of interest (including identifiability of links, accuracy of estimation, and complexity of probe path selection) over traditional techniques. Our rationale is that if network coding is to be deployed in some networks in the near future, then one can exploit this opportunity to also improve other operations, such as network monitoring.

Talks

An overview of this work can be found in this talk presented at UCR, in Dec. 2006.

Publications

Topology Inference: Link Loss Inference:

Last updated: Dec. 06