Toronto Networking Seminar

Maximizing Throughput with Network Coding

Baochun Li
University of Toronto

Date:  October 14,  3pm
Location: BA1210 (Bahen Center)


With the constraints of network topologies and link capacities, achieving maximized end-to-end throughput in undirected networks has been known as a fundamental but computationally hard problem.  In this talk, we present efficient solutions to the problem of achieving optimal throughput in undirected data networks, with single or multiple unicast, multicast and broadcast sessions. Although previous approaches lead to solving NP-complete problems, we 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.  This result holds for one or more communication sessions, as well as in overlay networks. Supported by empirical studies, we present the 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.

This talk presents joint work with Zongpeng Li, University of Calgary.


Baochun Li received his B.Engr. degree in 1995 from Department of  Computer Science and Technology, Tsinghua University, China, and his  M.S. and Ph.D. degrees in 1997 and 2000 from the Department of  
Computer Science, University of Illinois at Urbana-Champaign. Since  2000, he has been with the Department of Electrical and Computer  Engineering at the University of Toronto, where he is currently an  Associate Professor. He currently holds the Bell University  Laboratories Endowed Chair in Computer Engineering.  In 2000, he was  the recipient of the IEEE Communications Society Leonard G. Abraham  Award in the Field of Communications Systems. His research interests include application-level Quality of Service provisioning, wireless and overlay networks. He is a senior member of IEEE, and a member of  ACM.