On Networks of Two-Way Communication Channels

Information theory and network optimization theory are two disciplines which study aspects of communication networks. Recent work in network coding has demonstrated that a standard assumption of flow conservation from network optimization theory has imposed artificial restrictions on the workings of communication networks. Network information theory considers more general models of communication and offers some bounds on the limits of information transfer in a communication system involving multiple senders and receivers.

In this talk, we develop a model for analyzing network coding in the context of networks of bidirectional communication channels. We derive a bidirected cut-set bound for such networks that generalizes and improves upon a flow cut-set bound that is standard in network optimization theory and discuss some implications of this bound. We conclude by presenting an information-theoretic edge-cut bound which is sometimes tighter than the cut-set bounds. This is joint work with Gerhard Kramer, Bell Labs, Lucent Technologies.