Proof confirms routing matches coding rates in undirected networks
A Proof of the Langberg-Médard Conjecture
Information Theory
Summary
Communication networks often send data using special coding techniques at nodes, which can be faster than just routing data along fixed paths. But in some specific settings, it was unclear how much better coding was than routing. This paper proves a long-standing idea called the Langberg-Médard conjecture, showing that for networks made undirected, routing can match the speed of coding when all messages travel at the same rate. The authors provide a clear condition that tells when routing can deliver all messages simultaneously, confirming the conjecture for any network size and setup.
What this means in practice
- •For network schedulers: Determine when routing algorithms can achieve the same delivery rates as network coding by checking a precise cut-capacity condition in undirected network scenarios.
- •For telecommunications engineers: Use the proof to guide the design of network routing protocols that avoid the complexity of coding while maintaining maximum data flow in symmetric-rate multiple unicast setups.
A theory result. No direct application yet.
Authors
Sirui Liu, Zongpeng Li, Baochun Li
Abstract
In communication networks, network coding allows intermediate nodes to combine messages, achieving transmission rates unattainable by routing alone in many multicast settings. In multiple unicast, where each source sends a message only to its prescribed destination, the precise capability boundary between coding and fractional routing has long remained unresolved. In this context, the Langberg-Médard conjecture asserts that if all sources in a directed network transmit independent messages at a common rate and every destination can recover all source messages by network coding, then replacing every arc by an undirected edge of equal capacity yields a network in which fractional routing can simultaneously deliver each source's message to its prescribed destination at the same common rate. We prove the Langberg-Médard conjecture for any number of source-destination pairs and arbitrary network topology. More generally, for an undirected network with a given source set and a disjoint set of allowed destinations, we establish a necessary and sufficient cut-capacity condition for simultaneous unit-rate fractional routing under every assignment of an allowed destination to each source. Networks satisfying the hypothesis of the Langberg-Médard conjecture necessarily satisfy this cut condition, so the conjecture follows as a direct corollary.