On Benefits of Network Coding in Bidirected Networks and Hyper-networks

Prof. Zongpeng LI
University of Calgary
Wednesday, 14 December, 2011
3:00 pm - 4:00 pm
Room 833, Ho Sin Hang Engineering Building, CUHK

Network coding is a technique that allows information flows to be encoded while being routed across a data network. It has been shown that network coding helps increase the throughput and reduce the cost of data transmission, especially for one-to-many multicast applications. An important direction in network coding research is to understand and quantify the coding advantage and cost advantage, i.e., the potential benefits of network coding, as compared to routing, in terms of increasing throughput and reducing transmission cost, respectively. Two classic network models were considered in previous studies of the coding advantage: directed networks and undirected networks. The study of coding advantage in this work further focuses on two types of parameterized networks, including bidirected networks and hyper-networks, which generalizes the directed and the undirected network models, respectively. With proper parameter setting, more realistic modeling of networks in practice can be achieved. We prove upper-bounds and lower-bounds on the coding advantage for multicast in these models. Some of our bounds are new and unknown before, some improve upon previously proven bounds, and some answer open questions in the literature.


Zongpeng Li received his B.E. degree in Computer Science and Technology from Tsinghua University (Beijing) in 1999, his M.S. degree in Computer Science from University of Toronto in 2001, and his Ph.D. degree in Electrical and Computer Engineering from University of Toronto in 2005. Since August 2005, he has been working at the Department of Computer Science in the University of Calgary. His research interests are in computer networks, particularly in network optimization, multicast algorithm design, network game theory and network coding. Zongpeng was named an Edward S. Rogers Sr. Scholar in 2004, won the Alberta Ingenuity New Faculty Award in 2007, was nominated for the Alfred P. Sloan Research Fellow in 2007, and received the Best Paper Award at the Ninth Passive and Active Measurement Conference (PAM) in 2008.