Space Information Flow

Prof. Zongpeng LI
University of Calgary
Wednesday, 17 August, 2011
2:30 - 3:30 pm
Room 833, Ho Sin Hang Engineering Building The Chinese University of Hong Kong

Network information flow emerged as a fertile research ground over a decade ago, with the advent of network coding that allows information flows to be encoded when they meet within a data network. In this talk, I will introduce `space information flow' --- the transmission of information flows in free space, instead of in a fixed, existing network topology. Information flows are free to propagate along any trajectories in space, and may be encoded wherever they meet. The goal is to minimize a natural bandwidth-distance sum- product, while sustaining end-to-end unicast and multicast communication demands among terminals at known coordinates. We show that space information flow models the fundamental problem of information network design, which deserves renewed research attention for taking into account the unique encodable property of information flows. We relate space information flow to network information flow, and compare the benefits of network coding in them. We prove the multiple unicast conjecture, a well known conjecture in network information flow, in the space information flow paradigm. For multicast communication demands, we show that designing an information network is indeed different from designing a transportation network. In particular, an optimal multicast network does not necessarily correspond to a Steiner tree, as assumed in past literature. We prove such a difference by demonstrating that the cost advantage (ratio of min network cost without coding over that with coding) can be strictly larger than 1 in the space model. We further prove upper-bounds for the cost advantage in different scenarios of multicast network design.


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, where he is currently an Associate Professor. 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.