On Average Throughput Benefits and Alphabet Size in Network Coding

We examine the throughput benefits that network coding offers with respect to the average through- put achievable by routing, where the average throughput refers to the average of the rates that the indi- vidual 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 √N. We also discuss other throughput measures in networks, and show how in certain classes of networks, the average throughput can be achieved uniformly by all receivers 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.

Published in:
Special issue on Networking and Information Theory and the IEEE/ACM Transactions on Networking, 52, 6, 2410-2424

 Record created 2012-02-21, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)