Emina Soljanin

On Average Throughput and Alphabet Size in Network Coding

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 LP 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 the square root of N. We also discuss other throughput measures in networks, and show how in certain classes networks, the average throughput can be achieved uniformly by all receivers by employing vector routing and channel coding. Finally, we look into issues concerning the network code alphabet size as a tradeoff between routing and coding as well as between deterministic and randomized coding for certain classes of networks.

Joint work with C. Chekuri, Bell Labs, and C. Fragouli, EPFL.