On Average Throughput Benefits and Alphabet Size in Network Coding. Chekuri, C., Fragouli, C., & Soljanin, E. IEEE Trans. Inform. Theory, 2006.
abstract   bibtex   
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 \${\textbackslash}sqrtN\$. 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.
@article{chekuri_average_2006,
 abstract = {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 \${\textbackslash}sqrtN\$. 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.},
 type={4},
 author = {Chekuri, C. and Fragouli, C. and Soljanin, E.},
 journal = {IEEE Trans. Inform. Theory},
 tags = {network_coding},
 title = {On {Average} {Throughput} {Benefits} and {Alphabet} {Size} in {Network} {Coding}},
 year = {2006}
}

Downloads: 0