On the Effects of Network Structure on the Achievable Rates for Multiple Unicasts.

摘要

In this dissertation, we consider the problem of multiple unicast sessions over directed acyclic graphs. Although characterizing the rate region of inter-session network coding is a well-known open problem, we consider three particular network models. We design schemes, characterize the rates they achieve, and highlight the relation between achievable rates and network structure.;First, we consider networks, where the core is simple and all intelligence lies at the edge. Each intermediate node can only perform random linear network coding. We apply a precoding-based inference alignment technique at the edge, and refer to it as precoding-based network alignment (or PBNA). This approach combines the simplicity of RLNC in the core of the network with the guarantees of alignment (rate 1/2 per session). We observe that network structure may introduce dependencies, which we refer to as coupling relations, between elements of the transfer matrix, which might affect the achievable rate of PBNA. We identify the minimal set of such coupling relations, and we interpret them in terms of network structure properties. We also present polynomial-time algorithms to check the existence of these coupling relations on a given directed acyclic graph.;Second, we consider networks, where each node can perform linear network coding (not necessarily random). We propose a constructive method: (i) the unicast sessions are first partitioned into multiple disjoint subsets of unicast sessions; (ii) each subset of unicast sessions is then mapped to a multicast session, for which a linear network coding scheme is constructed. Together, these serve as a linear network coding scheme for the original multiple unicast sessions, which we refer to as the multicast-packing coding scheme (MPC). We show that the rate region of MPC is characterized by a set of linear constraints. We also propose a practical simulated annealing algorithm for approximating the optimal performance of MPC. Using simulations, we demonstrate the benefits of MPC as well as the efficiency of the simulated annealing algorithm.;Third, we consider networks, where each node can perform network coding (linear or non-linear) or simple routing. There exist networks, for which network coding doesn't provide any benefit over routing, which we refer to as routing-optimal networks. We identify a class of routing-optimal networks, which we refer to as information-distributive networks, defined by three structural features. We show that information-distributive networks don't subsume all routing-optimal networks. We present examples of information-distributive networks, including some examples from index coding and a single unicast session with hard deadline constraints.