A basic problem in network coding is to choose a field to perform the encoding and decoding operations in. The main message we wish to deliver in this talk is that while unboundedly large fields are required in arbitrary networks, very small finite fields may be sufficient for networks in practice. We use planar networks as a representative example of a practical network, which usually has a linear number of links, and exhibits a topology that is planar or close to planar. Focusing on a basic scenario of multicasting two source information flows, we prove that coding over GF(3) is sufficient for all planar networks. We further show that GF(3) is also necessary, by constructing two new planar multicast networks, one of which is a bipartite, that require coding over GF(3) for achieving the maximum throughput. For the special case of outerplanar networks, we prove that network coding is always equivalent to routing. Our results also invite a renewed look at the choice of deterministic vs. randomized network coding in practical networks.
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 algorithms, network coding and network game theory. 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.
