On the Optimal Multi-rate Throughput for Multicast

Zhang Mu; Zhang Shun-yi; Liu Wei-yan

doi:10.3724/SP.J.1146.2006.00958

Volume 30 Issue 1

Jan. 2011

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2008 > 30(1): 16-20

Zhang Mu, Zhang Shun-yi, Liu Wei-yan. On the Optimal Multi-rate Throughput for Multicast[J]. Journal of Electronics & Information Technology, 2008, 30(1): 16-20. doi: 10.3724/SP.J.1146.2006.00958

Citation:

Zhang Mu, Zhang Shun-yi, Liu Wei-yan. On the Optimal Multi-rate Throughput for Multicast[J]. Journal of Electronics & Information Technology, 2008, 30(1): 16-20. doi: 10.3724/SP.J.1146.2006.00958

Zhang Mu, Zhang Shun-yi, Liu Wei-yan. On the Optimal Multi-rate Throughput for Multicast[J]. Journal of Electronics & Information Technology, 2008, 30(1): 16-20. doi: 10.3724/SP.J.1146.2006.00958

Citation:

Zhang Mu, Zhang Shun-yi, Liu Wei-yan. On the Optimal Multi-rate Throughput for Multicast[J]. Journal of Electronics & Information Technology, 2008, 30(1): 16-20. doi: 10.3724/SP.J.1146.2006.00958

PDF( 190 KB)

On the Optimal Multi-rate Throughput for Multicast

doi: 10.3724/SP.J.1146.2006.00958

Received Date: 2006-07-03
Rev Recd Date: 2007-01-08
Publish Date: 2008-01-19

Abstract

Abstract

The maximal achievable multi-rate throughput problem of a multicast session at the presence of network coding is investigated in this paper. Deviating from previous works which focus on single-rate network coding, the heterogeneity of sinks is taken into account and multiple data layers to address the problem is provided in this paper. Firstly formulated is the maximal achievable throughput problem with the assumption that the data layers are independent and layer rates are static. It is proved that the problem in this case is, unfortunately, NP-hard. In addition, the formulation is extended to the problems with dependent layers and dynamic layers. Furthermore, the approximation algorithm which satisfies certain fairness is proposed.

FullText(HTML)

References(1)

References

[1] Menger K. Zur allgemeiner Kurventheories. Fund. Math.,1927, 10: 96-115. [2] Edmonds J. Edge-Disjoint Brachings, in CombinatorialAlgorithms. Rustin R Ed. New York: Academic Press, 1973:91-96. [3] Jain K, Mahdian M, and Salavatipour M. Packing Steinertrees. in the 14th ACM-SIAM Symposium on DiscreteAlgorithms 2003, Baltimore, MD, Jan 2003: 448-453. [4] Ahlswede R, Cai N, Li S R, and Yeung R. Networkinformation flow[J].IEEE Trans. on Information Theory.2000,46(4):1204-1216 [5] Koetter R and Medard M. An algebraic approach to networkcoding[J].IEEE/ACM Trans. on Networking.2003, 11(5):782-795 [6] Li S, Yeung R and Cai N. Linear network coding[J].IEEE Trans.on Information Theory.2003, 49(2):371-381 [7] Sanders P, Egner S, and Tolhuizen L. Polynomial timealgorithms for network information flow. in Proc. of the 5thAnnual ACM Symposium on Parallel Algorithms andArchitectures, San Diego, California, June 2003: 286-294. [8] McCanne S, Jacobson V, and Vetterli M. Receiver-drivenlayered multicast. in Proc. of ACM SIGOMM 1996, Stanford,CA, August 1996: 117-130. [9] Ford L R and Fulkerson D R. Maximal flow through anetwork[J].Canadian Journal of Mathematics.1956, 8(3):399-404

Relative Articles

Supplements(0)

Cited By

Proportional views