The Langberg-Medard multiple unicast conjecture claims that for a strongly reachable k-pair network, there exists a multi-flow with rate (1,1,...,1). In this paper, we show that the conjecture holds true for stable 3-pair networks.
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. Three known bounds on the symmetric rate in undirected unicast information networks are the sparsest cut, the LP bound and the partition bound. In this paper, we present three results on the partition bound. We show that the decision version problem of computing the partition bound is NP-complete. We give complete proofs of optimal routing schemes for two classes of networks that attain the partition bound. Recently, the 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 are elements of this class. We show the existence of a network for which the partition bound is tight, achievable by routing and is not an element of this new class of networks.
The capacity of line networks with buffer size constraints is an open, but practically important problem. In this paper, the upper bound on the achievable rate of a class of codes, called batched codes, is studied for line networks where the channels have 0 zero-error capacity. Batched codes enable a range of buffer size constraints, and are general enough to include special coding schemes studied in the literature for line networks. Existing works have characterized the achievable rates of batched codes for several classes of parameter sets, but leave the cut-set bound as the best existing general upper bound. In this paper, we provide upper bounds on the achievable rates of batched codes as functions of line network length for these parameter sets. Our upper bounds in order of the network length match with the existing achievability results.
We consider linear network error correction (LNEC) coding when errors may occur on the edges of a communication network of which the topology is known. In this paper, we first revisit and explore the framework of LNEC coding, and then unify two well-known LNEC coding approaches. In LNEC coding, LNEC maximum distance separable (MDS) codes are a type of most important optimal codes. However, the minimum required field size for the existence of LNEC MDS codes is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we obtain an improved lower bound on the required field size by developing a graph-theoretic approach. The improvement over the existing results is in general significant. Furthermore, by applying the graph-theoretic approach to the framework of LNEC coding, we obtain a significantly enhanced characterization of the capability of an LNEC code in terms of its minimum distance.