Network coding beats routing in some undirected networks
Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks
Information Theory
Summary
Routing in computer networks typically moves data along established paths without changing it, but network coding lets devices mix data to increase efficiency. Some experts thought that in undirected networks, where connections share capacity both ways, coding couldn’t improve upon routing. The authors disproved this by creating a specific undirected network where clever coding sends more data than any routing method. They also built infinite families of such networks showing coding's advantage grows larger as network size increases.
What this means in practice
- •For network schedulers: Identify network topologies where network coding improves data throughput compared to routing in undirected multiple-unicast scenarios.
- •For distributed system engineers: Design communication protocols for distributed systems that leverage coding to outperform routing in undirected networks.
A theory result. No direct application yet.
Authors
Xindan Zhang, Baochun Li, Zongpeng Li
Abstract
Network coding lets the nodes of a network combine messages rather than merely forward them. In undirected networks, where the two directions of an edge share its capacity, Li and Li conjectured in 2004 that coding offers no advantage over fractional routing; the conjecture has been confirmed for many special classes but never settled in general. In this paper, we disprove it by constructing a finite connected simple undirected network with unit shared edge capacities, maximum degree three, and distinct leaf terminals, on which a binary linear block code achieves a common rate strictly above the maximum fractional routing rate. The construction turns a short completion-time code into a reversible circuit whose registers all carry independent messages, and a temporal metric on its wires yields the strict routing bound. The underlying integer-coefficient construction works over every finite field and every nontrivial finite abelian group; for deterministic fixed-schedule codes the common-rate supremum is one and the closure of the rate region is the unit cube. Amplifying the gap with a degree-preserving tensor construction and an even subdivision gives, for every $0<β<1$, an unbounded family of connected, simple, subcubic, bipartite networks with girth at least $n^β$ on which coding approaches rate one while routing is bounded by $K_β/(\log n)^c$, with one positive exponent $c$ independent of $β$. The finite counterexample and the family theorem are formalized in Lean.