Degree Type


Date of Award


Degree Name

Doctor of Philosophy


Electrical and Computer Engineering

First Advisor

Aditya Ramamoorthy


In a network that supports multiple unicast, there are several source terminal pairs; each source wishes to communicate with its corresponding terminal. Multiple unicast connections form bulk of the traffic over both wired and wireless networks. Thus, network coding schemes that can help improve network throughput for multiple unicasts are of considerable interest.

In this dissertation, we consider the multiple unicast problem over directed acyclic networks with unit-capacity edges when there are three source terminal pairs and two source terminal pairs. For three unicast problem, we assume that the three s_i-t_i pairs wish to communicate at unit-rate via network coding. We define the connectivity level vector [k_1 k_2 k_3] such that there exist k_i edge-disjoint paths between s_i and t_i. We attempt to classify networks based on the connectivity level. We identify certain feasible and infeasible connectivity levels [k_1 k_2 k_3] for unit rate transmission. For the feasible cases, we construct schemes based on linear network coding. For the infeasible cases, we provide counter-examples, i.e., instances of graphs where the multiple unicast cannot be supported under any (potentially nonlinear) network coding scheme.

For two unicast problem, we assume that we only know certain minimum cut values for the network, e.g., mincut(S_i, T_j), where S_i is a subset of (s_1, s_2) and T_j is a subset of (t_1, t_2) for different subsets S_i and T_j. Based on these values, we propose an achievable rate region for this problem using linear network codes. Towards this end, we begin by defining a multicast region where both sources are multicast to both the terminals. Following this we enlarge the region by appropriately encoding the information at the source nodes, such that terminal t_i is only guaranteed to decode information from the intended source s_i, while decoding a linear function of the other source.The rate region depends upon the relationship of the different cut values in the network.


Copyright Owner

Shurui Huang



File Format


File Size

89 pages