多速率多播最大吞吐量问题研究

该文研究了利用network coding的多速率多播最大吞吐量问题.与以往研究重点集中在单速率多播中的network coding研究工作不同,该文考虑了链路的异构性问题并采用多速率多播来解决该问题.文中形式化地描述了多速率多播最大可得吞吐量问题,并证明了在分层独立和层速率固定条件下,利用network coding的多速率多播最大吞吐量问题是NP-hard类问题,同时给出了最大吞吐量的上界.该文同时还研究了分层相关和层速率可变情况下的最大吞吐量问题,并提出了一种满足公平性的近似算法.

On the Optimal Multi-rate Throughput for Multicast

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.