多速率多播最大吞吐量问题研究
doi: 10.3724/SP.J.1146.2006.00958
On the Optimal Multi-rate Throughput for Multicast
-
摘要: 该文研究了利用network coding的多速率多播最大吞吐量问题。与以往研究重点集中在单速率多播中的network coding研究工作不同，该文考虑了链路的异构性问题并采用多速率多播来解决该问题。文中形式化地描述了多速率多播最大可得吞吐量问题，并证明了在分层独立和层速率固定条件下，利用network coding的多速率多播最大吞吐量问题是NP-hard类问题，同时给出了最大吞吐量的上界。该文同时还研究了分层相关和层速率可变情况下的最大吞吐量问题，并提出了一种满足公平性的近似算法。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.
-
[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 -
计量
- 文章访问数: 3417
- HTML全文浏览量: 69
- PDF下载量: 1091
- 被引次数: 0
下载:
