On the Optimal Multi-rate Throughput for Multicast
Zhang Mu①②; Zhang Shun-yi①; Liu Wei-yan①
①Jiangsu Province Engineering Research Center of Telecommunication & Network Technology, Nanjing University of Posts and Telecommunications, Nanjing 210003, China; ②Department of Computer Science and Technology, Guiyang University, Guiyang 550005, China
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.
2008, Vol. 30 
