Routing and Network Coding on Lines, Stars, and Rings

February 21, 2008
Time: 11:00am-12:00pm
EE Conference room (Mudd 1302)
Hosted by: Prof. Xiaodong Wang
Speaker: Gerhard Kramer, Bell Laboratories Alcatel-Lucent


Network coding allows each node in a network to combine its input information instead of simply storing, copying, and forwarding data. We present several recent results. The first is a new upper bound on network coding rates that applies to wireline, wireless, and mixed wireline/wireless networks. The bound, called a progressive d-separating edge set (or PdE) bound, involves progressively removing edges from a network graph and checking whether certain strengthened d-separation conditions are satisfied. Second, we consider line networks that are elements of larger networks. We show that under both edge and node capacity constraints the optimal code is a combination of rate-splitting, copying, routing, and "butterfly" binary linear network coding. Third, we consider star and ring networks and develop related results.

Speaker Biography

Gerhard Kramer received the B.Sc. and M.Sc. degrees in electrical engineering from the University of Manitoba, Winnipeg, MB, Canada, in 1991 and 1992, respectively, and the Dr. sc. techn. (Doktor der Technischen Wissenschaften) degree from the Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, in 1998. From July 1998 to March 2000, he was with Endora Tech AG, Basel, Switzerland, as a communications engineering consultant. Since May 2000 he has been with Bell Laboratories, Alcatel-Lucent, Murray Hill, NJ, USA.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University