Network information flow

TLDR

The model subsumes all previously studied models along the same line. The authors introduce network information flow, a new class of problems inspired by computer network applications, and aim to characterize the admissible coding rate region. They consider a point‑to‑point communication network with mutually independent information sources to be multicast to specified destination sets. For a single source, they provide a simple characterization of the admissible coding rate region equivalent to a max‑flow min‑cut theorem, showing that network coding can save bandwidth and that treating multicast information as a fluid is suboptimal, potentially impacting future switching system design.

Abstract

We introduce a new class of problems called network information flow which is inspired by computer network applications. Consider a point-to-point communication network on which a number of information sources are to be multicast to certain sets of destinations. We assume that the information sources are mutually independent. The problem is to characterize the admissible coding rate region. This model subsumes all previously studied models along the same line. We study the problem with one information source, and we have obtained a simple characterization of the admissible coding rate region. Our result can be regarded as the max-flow min-cut theorem for network information flow. Contrary to one's intuition, our work reveals that it is in general not optimal to regard the information to be multicast as a "fluid" which can simply be routed or replicated. Rather, by employing coding at the nodes, which we refer to as network coding, bandwidth can in general be saved. This finding may have significant impact on future design of switching systems.