On Achieving Optimal End-to-End Throughput in Data Networks: Theoretical and Empirical Studies
Zongpeng Li, Baochun Li, Dan Jiang, Lap Chi Lau · 2004
With the constraints of network topologies and link capacities, achieving the optimal end-to-end throughput in data networks has been known as a fundamental but computationally hard problem. In this paper, we seek efficient solutions to the problem of achieving optimal throughput in data networks, with single or multiple unicast, multicast and broadcast sessions. Towards this objective, we first investigate upper and lower bounds of such optimal throughput in the case of a single multicast session, and show that it is computationally hard to compute these bounds. We then show the surprising result that, facilitated by the recent advances of network coding, computing the strategies to achieve the optimal end-to-end throughput can be performed in polynomial time, using the algorithm we propose. In addition, we extend our results to the cases of multiple sessions of unicast, multicast, broadcast and group communication, as well as the model of overlay networks. In all these cases, we also show that the optimal achievable throughput is independent from the selection of data sources within each session. Finally, supported by empirical studies, we present the surprising observation that in most topologies, applying network coding may not improve the achievable optimal throughput; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality. I.