The Cost Advantage of Network Coding in Uniform Combinatorial Networks

The coding advantage refers to the potential for network coding to improve end-to-end throughput or reduce routing cost. How large can the coding advantage be? The authors investigate this fundamental question in the classic undirected network model. After almost a decade of research in network coding, so far all known networks where such potential exists are based on a special class of topologies known as combinatorial networks. They try to prove a rather small upper-bound (close to 1) for the coding advantage for the class of combinatorial networks and its variations.