Generalized Network Sharing bound and Two-Unicast Networks


<p>Sudeep Kamath<br /> University of California at Berkeley<br /> Department of Electrical Engineering and<br /> Computer Science<br /> California 94720<br /> United States of America</p>


Wednesday, 14 December 2011, 14:00 to 15:00


  • AG-69


The talk will be in two parts.

In the first part, we consider the two-unicast problem in wireline networks, i.e. the problem of communication over a network with two sources and two destinations, each source with a message for its own destination. Our interest is in investigating the network coding capacity region for this problem. We develop a new outer bound that is a simple improvement over an existing bound in the literature called the Network Sharing bound [Yan, Yang, Zhang]. We call our bound the Generalized Network Sharing (GNS) bound. We discover some interesting properties of this bound with regard to two-unicast networks (oint work with Prof. David Tse and Prof. Venkat Anantharam).

In the second part, we consider two-unicast in linear deterministic networks. The linear deterministic model has been very successful in characterizing approximately capacity regions of Gaussian networks. By developing a GNS bound for layered linear deterministic networks, we find an interesting analogue of a result obtained for two-unicast wireline networks by Chih-Chun Wang and Ness Shroff. Further, by providing achievable schemes and matching outer bounds, we completely characterize the capacity region of a class of two-unicast layered linear deterministic networks (joint work with I-Hsiang Wang and Prof. David Tse).