On the information flow in undirected unicast network (PhD)

Abstract

One of the important unsolved problems in information theory is the conjecture that network coding has no rate benefit over routing in undirected unicast networks. If the conjecture is true then the undirected unicast net- work information capacity is the same as the routing capacity. However, the conjecture is unsolved and the undirected unicast network information capacity is not characterized yet. Even upper bounding the symmetric information rate is a challenging problem. Only two explicit upper bounds on symmetric information rate are known for general undirected networks: (1) sparsest cut bound on symmetric rate is a trivial bound on both commodity and information flow and (2) the linear programming bound using Shannon-type inequalities is generally not used for evaluation due to prohibitively large problem size. In this work, we characterize an upper bound, called the partition bound, on the symmetric rate for information flow in general undirected unicast networks and present a partitioning technique to obtain converse results for undirected network information flow. We give two proof methods for the partition bound. This bound is further generalized for non-symmetric rates. We show that the partition bound is not tight in general and also demonstrate an approach to tighten the bound. As a result, we present an alternative proof of the undirected unicast network information capacity of the well known Hu’s 3-pairs network. We give explicit routing solutions achieving the partition bound for (1) two classes of complete n-partite networks called Type-I and Type-II n-partite networks, and (2) a class of 3-layer networks called Type-I 3-layer networks. These results prove that the undirected unicast network coding conjecture holds for these classes of networks. A parameter is defined as an optimal partition which delivers the partition bound. We present a procedure to compute a lower bound for this parameter. This lower bound renders a computable upper bound for the partition bound. We also show that the decision version problem of computing the partition bound is an N P-complete problem. Thus, both the upper bounds, the sparsest cut bound, and partition bound are not polynomial-time computable unless P=N P. Recently, the undirected unicast network coding conjecture was proved for a new class of networks and it was shown that all the network instances for which the conjecture is proved previously, and the cut based bound is not achievable by commodity flow, are elements of this class. The conjecture was also proved for all undirected unicast networks (1) with six or less number of nodes and (2) with up to three sessions and seven nodes except one particular network. We show the existence of a Type-I n-partite network for which the partition bound is tight and achievable by routing and is not an element of this class of networks. This result establishes that there exist networks outside of the class of networks with unverified conjecture such that the partition bound is tight and attainable by routing.