Network Coding Rates and Edge-Cut Bounds

Network coding has recently become a rapidly evolving area in Information Theory. We will begin by examining the basic concept behind network coding and contrast it to the conventional routing approach in existing networks. We highlight the capacity gain by allowing each node in a network to re-encode its input information instead of simply storing and forwarding data. We then discuss some recent progress in network coding. A bound on network coding rates is presented that generalizes an edge-cut bound on routing rates. The bound, called a progressive d-separating edge set (or PdE) bound, involves progressively removing edges from a network graph and checking whether certain strengthened d-separation conditions are satisfied. We show that the PdE bound and one of its extensions proves that routing is rate-optimal for multiple unicast sessions on bidirectional ring networks. We further show that the PdE bound improves on a standard cut-set bound for networks with broadcasting, interference, and noise.

This work was done jointly with Serap A. Savari from the University of Michigan, Ann Arbor.