Skip to content

Network information flow

Rudolf Ahlswede, Raymond W. Yeung

IEEE Transactions on Information Theory · 2000 · 7,801 citations

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Ahlswede, R., Cai, N., Li, S.-Y., & Yeung, R. W. (2000). Network information flow. IEEE Transactions on Information Theory, 46(4), 1204–1216. https://doi.org/10.1109/18.850663

In text: (Ahlswede et al., 2000)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

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.

  1. Introduction to Algorithms1991
  2. A Formal Basis for the Heuristic Determination of Minimum Cost Paths1968
  3. Network Flows: Theory, Algorithms, and Applications.1994
  4. Depth-First Search and Linear Graph Algorithms1972
  5. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs1998

Metadata from OpenAlex (CC0). Citations are generated from the published record.