Linear algebraic approaches to coding for multiple unicast networks

Abstract

The multiple unicast network coding problem is a classical open problem in network information theory, whose applications rapidly increase especially with the occurrences in models of distributed storage and content delivery systems. In this thesis, we explore the ideas of linear algebraic techniques and algorithms in the multiple unicast scenarios. In particular, we are interested in wireline networks that are representable as directed acyclic graphs, especially in the context of capacity characterization and achievable coding schemes of two-unicast communications, as two-unicast models capture the complexity of general multiple unicast networks. The results of the thesis are categorized into three main areas that aligned with main intuition behind our approaches. We start with careful examination of the algebraic framework of network coding, which forms the foundation of many important theoretic and practical network coding results. Our results on atomic decomposition of network transfer matrix and the edge reduction lemma substantiate the original algebraic framework proposed in [1], further facilitating its application in the non-multicast scenarios. We dissect the transfer matrices - the most important entities in the network coding framework to bring new tools and concepts into the algebraic framework of network coding. Next, utilizing these linear algebraic tools and concepts, combined with insights from interference channels, we construct achievable regions for two-unicast networks and make connections between ranks of transfer matrices and graph theoretic entities. We highlight various achievable schemes based on the linear algebraic scheme. In particular, making use of the connections between rates and ranks of the transfer matrices, we are able to fully characterize some achievable regions using various minimum cut set values between the sources and destinations. Finally the cascaded decomposition of transfer matrices also allows us adopt a dynamic programming approach to coding for these networks. We revisit the original settings of the max-flow min-cut theorem and provide an alternative proof that is based purely on linear algebraic coding constructions. Using the same intuition, we devise a recurisve coding algorithm for two-unicast-Z networks. We hope that our approaches do not only help making progress in the core problem of multiple unicasts, but also provide some novel perspectives to other tightly connected problems, such as coding for distributed storage and index coding.