On capacity bounds for networks containing two-way channels

In earlier work, Koetter, Effros, and Medard introduce a technique for bounding network capacities. The approach involves bounding the capacity of a network of independent stochastic channels by the capacity of a network of noiseless links. The noiseless network is derived by replacing each channel by a noiseless bounding model. In this paradigm, a lower-bounding model for a given channel has the property that replacing the channel by the given model yields a new network whose capacity region is a subset of the capacity region of the original network. Similarly, replacing the channel by its upper bounding model yields a new network whose capacity region is a superset of the capacity region of the original network. The technique is useful since it bounds the capacity of a stochastic network by the network coding capacity of a noiseless network, and computational tools are available for deriving network coding capacities. To date, bounding models have been derived for point-to-point, broadcast, multiple access, and interference channels. Deriving bounding models for new channels increases the family of networks for which capacity bounds can be derived. This paper derives upper and lower bounding models for the two-way channel. Among the channels for which bounding models have been derived, the two-way channel is the first for which the set of input nodes and the set of output nodes have a non-empty intersection.