UC Irvine

In this thesis, we study intersession coding for multiple unicasts in wired and wireless network settings. In particular, we apply alignment techniques and investigate the effect of structure of the transfer matrix to their performance. In addition, we also look at the coded caching problem and we propose an efficient delivery scheme that outperforms state-of-the-art.

The thesis is divided into three parts. In the first part, we consider the problem of network coding across three unicast sessions over a directed acyclic graph, where each unicast session has a min-cut of 1. We consider a network model in which the middle of the network can only perform random linear network coding. We adapt interference alignment technique, originally developed for the wireless interference channel, to construct a precoding-based linear scheme, which we refer to as precoding-based network alignment (PBNA). The primary difference between this setting and the wireless interference channel is that the network topology can introduce dependencies among the elements of the transfer matrix and can potentially affect the achievable rate of PBNA.

We identify all these dependencies and we interpret them in terms of network topology. We also show that, depending on these network topologies, the optimal symmetric rate achieved by any precoding-based linear scheme can take only three possible values, all of which can be achieved by PBNA.

In the second part, we consider the interference channel with $K$ transmitters and $K$ receivers all having a single antenna, wherein the $K \times K$ transfer matrix representing this channel has rank $D$ (less than $K$). The degrees of freedom of such channels are not known as the rank-deficient transfer matrix creates algebraic dependencies between the channel coefficients. We present a modified version of the alignment scheme, to handle these dependencies while aligning interference, and derive the sufficient conditions for achieving half rate per user using this scheme. We show the difficulties in proving these sufficient condition for $K=4$ and $K=5$ and we also show that these sufficient conditions are not satisfied for $K \ge 6$.

Finally, we study the coded caching problem: a network with several users trying to access a database of files stored at a server through a shared bottleneck link is considered. Each user is equipped with a cache, where files can be prefetched according to a caching policy, which is mainly based on the popularities of the files. Coded caching tries to exploit coding opportunities created by cooperative caching and has been shown to significantly reduce the load on the shared link. Most prior work focused on optimizing the caching policy so as to minimize this expected load. Given the caching policy and the user demands, the problem of minimizing the load over the shared link is essentially an index coding problem. In this part of the thesis, we design a novel delivery scheme, Heterogeneous Coded Delivery (HCD), that builds on a prior scheme for the uniform demand case, but performs better in the non-uniform demand case. We evaluate this delivery scheme for different caching policies.