On average throughput and alphabet size in network coding

Chandra Chekuri, Christina Fragouli, Emina Soljanin

Research output: Contribution to journalArticlepeer-review


We examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the individual receivers experience. We relate these benefits to the integrality gap of a standard linear programming formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with N receivers where network coding offers benefits proportional to √N. We also discuss other throughput measures in networks, and show how in certain classes of networks, average throughput bounds can be translated into minimum throughput bounds, by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.

Original languageEnglish (US)
Pages (from-to)2410-2424
Number of pages15
JournalIEEE Transactions on Information Theory
Issue number6
StatePublished - Jun 2006
Externally publishedYes


  • Linear programming integrality gap
  • Multicast
  • Network coding
  • Routing
  • Throughput

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'On average throughput and alphabet size in network coding'. Together they form a unique fingerprint.

Cite this