network information theory

Network Coding and Multicast Capacity

Information Theory65 minDifficulty

You should know: channel capacity, mutual information, error correcting codes

Overview

Network coding is a paradigm in which intermediate network nodes are allowed to combine (encode) incoming packets before forwarding, rather than merely storing and forwarding them. The central result, due to Ahlswede, Cai, Li, and Yeung (2000), is that network coding achieves the max-flow min-cut bound for multicast: the information rate from a source to a set of receivers equals the minimum cut capacity in the network graph. Linear network coding (using operations over finite fields) suffices for multicast, and random linear network coding achieves capacity with high probability.

Intuition

Consider two packets A and B that must cross a bottleneck link. If a node simply forwards one packet, the other must wait. But if the node sends A XOR B, both receivers who already have one packet can recover the other. This seemingly simple trick achieves the maximum possible throughput. The insight generalizes: by treating packets as vectors over a finite field and having intermediate nodes compute linear combinations, a single multicast session can saturate every min-cut in the network simultaneously.

Formal Definition

Definition

A network is a directed acyclic graph (DAG) G = (V, E) with a source s and receivers T = {t_1, ..., t_k}. Each edge e has capacity C(e). The max-flow min-cut theorem for networks states:

\text{mincut}(s, t) = \min_{S: s \in S, t \notin S} \sum_{e: S \to \bar{S}} C(e)

Min-cut capacity from source s to terminal t

R^* = \min_{t \in T} \text{mincut}(s, t)

Multicast capacity: minimum over all receivers

\mathbf{y}_e = \sum_{e' \in \text{In}(\text{head}(e))} k_{e'e} \cdot \mathbf{y}_{e'}

Linear network code: edge output as linear combination over GF(q)

\Pr[\text{decoding fails}] \leq \frac{|T| \cdot |E|}{q}

Random linear network coding failure probability bound over GF(q)

Notation

Notation	Meaning
$G = (V, E)$	Directed network graph with vertices V and edges E
$\text{mincut}(s,t)$	Maximum flow (equivalently, minimum cut) from source s to terminal t
$\mathrm{GF}(q)$	Finite field (Galois field) with q elements
$k_{e'e}$	Local coding coefficient: scalar multiplier from edge e' to edge e

Theorems

Theorem 1: Max-Flow Min-Cut Theorem for Multicast (Ahlswede-Cai-Li-Yeung)

For a directed network G with source s and receivers T, the information-theoretic multicast capacity equals the minimum over all t in T of mincut(s, t). This capacity is achievable by linear network coding over sufficiently large finite fields.

Theorem 2: Linear Sufficiency for Multicast

For multicast over acyclic networks, linear network codes over GF(q) suffice to achieve capacity, provided q is larger than the number of receivers |T|.

Theorem 3: Random Linear Network Coding Achieves Capacity

If each node independently selects coding coefficients uniformly at random from GF(q), then each receiver can decode with probability at least 1 -- |T| * |E| / q. For q growing with the network, this probability approaches 1.

Worked Examples

1
The butterfly network has source s, a bottleneck edge with capacity 1, and two receivers t1, t2. Without coding, only one of two packets (A, B) can reach both receivers — giving rate 1 per receiver.
$\text{Max-flow to each receiver} = 2,\quad \text{but naive routing gives rate} \leq 1$
2
With coding: the node at the bottleneck sends A XOR B on the bottleneck edge.
$z = A \oplus B$
3
Receiver t1 also receives A directly and computes B = z XOR A.
$B = z \oplus A = (A \oplus B) \oplus A$
4
Receiver t2 also receives B directly and computes A = z XOR B.
$A = z \oplus B = (A \oplus B) \oplus B$
5
Both receivers decode both packets, achieving rate 2. This matches the min-cut.
$\text{Rate} = 2 = \text{mincut}(s, t_1) = \text{mincut}(s, t_2)$

✓ Answer

Network coding (XOR at the bottleneck node) achieves the min-cut capacity of 2, which simple routing cannot reach.

Practice Problems

Mediumfree response

Why does simple routing fail in the butterfly network but network coding succeeds?

Hardapplication

What is the advantage of random linear network coding over deterministic coding?

Common Mistakes

Common Mistake

Network coding increases the total information capacity of the network.

Network coding does not increase capacity beyond the min-cut bound. It achieves what is already theoretically possible — simple routing leaves capacity on the table in multicast scenarios.

Common Mistake

Random linear network coding always succeeds.

It fails with probability bounded by |T|*|E|/q. Over large finite fields, this probability is very small but nonzero. Practical systems use sufficiently large GF(q) to make failure negligible.

Quiz

Network coding allows intermediate nodes to:

Only store and forward packets unchangedCompute algebraic combinations of incoming packets before forwardingIncrease channel capacity beyond the physical limitEliminate the need for error correction

The multicast capacity in a network equals:

The sum of all edge capacitiesThe maximum cut across all source-receiver pairsThe minimum over all receivers of the max-flow from source to that receiverThe average edge capacity

Historical Background

Classical network theory treated routers as switches: packets are copied and forwarded but never mixed. Shannon's capacity theory applied to point-to-point links. The question of what rates are achievable in networks remained open. In 2000, Ahlswede, Cai, Li, and Yeung proved that allowing nodes to perform XOR or general linear combinations of received packets achieves the max-flow min-cut bound for multicast — a rate that simple routing cannot always achieve. This launched the field of network coding theory, with applications in distributed storage, peer-to-peer networks, and wireless networks.

1956
Ford and Fulkerson prove the max-flow min-cut theorem for network flows.
L.R. Ford, D.R. Fulkerson
2000
Ahlswede, Cai, Li, and Yeung prove that network coding achieves max-flow min-cut for multicast.
Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Raymond Yeung
2003
Li, Yeung, and Cai show linear network coding suffices for multicast over acyclic networks.
Shuo-Yen Robert Li, Raymond Yeung, Ning Cai
2006
Ho et al. introduce random linear network coding, achieving capacity with high probability.
Tracey Ho, Muriel Medard, Ralf Koetter
2010
Network coding applied to distributed storage (regenerating codes) by Dimakis et al.
Alexandros Dimakis

Summary

Network coding allows intermediate nodes to algebraically combine packets, achieving the max-flow min-cut bound for multicast — impossible with simple routing.
The butterfly network is the canonical example: XOR coding at a bottleneck node allows two receivers to each decode two packets.
Linear network coding over finite fields GF(q) suffices for multicast; random linear network coding achieves capacity with probability 1 -- |T|*|E|/q.
Applications include distributed storage, peer-to-peer file sharing, wireless relay networks, and satellite broadcasting.

References

PaperAhlswede, R., Cai, N., Li, S.-Y. R., Yeung, R. W. (2000). Network Information Flow. IEEE Transactions on Information Theory, 46(4), 1204-1216.
PaperLi, S.-Y. R., Yeung, R. W., Cai, N. (2003). Linear Network Coding. IEEE Transactions on Information Theory, 49(2), 371-381.
BookYeung, R. W. (2008). Information Theory and Network Coding. Springer.
WebsiteWikipedia — Network coding