A Study of Communication Networks through the Lens of Reduction

Citation

Wong, Ming Fai (2017) A Study of Communication Networks through the Lens of Reduction. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9348HFK. https://resolver.caltech.edu/CaltechTHESIS:06072017-154010713

Abstract

A central goal of information theory is to characterize the capacity regions of communication networks. Due to the difficulty of the general problem, research is primarily focused on families of problems defined by various classifiers. These classifiers include the channel transition function (i.e., noisy, deterministic, network coding), demand type (i.e., single-source, 2-unicast), network topology (i.e. acyclic network coding, index coding). To date, the families of networks that are fully solved remain limited. Moreover, results derived for one specific family often do not extend easily to other families of problems.

Our work shifts from the traditional focus on solving example networks to one that builds connections between problem solutions so that we can say where and when solving a problem in one domain would also solve a corresponding problem in another domain. Central to our approach is a technique called "reduction", in which we connect the solutions and results of communication problems. We say that problem A reduces to problem B when A can be solved by first transforming it to B and then applying a solution for B. We focus on two notions of reduction: reduction in code design and reduction in capacity region.

Our central results demonstrate reductions with respect to a variety of classifiers. We show that finding multiple multicast network capacity regions reduces to finding multiple unicast network capacity regions both when capacity is defined as the maximal rate over all possible codes and when capacity is defined as the optimal rate over linear codes. As a corollary to this result, we show that the same capacity reduction holds for when network types are limited to either network coding networks or index coding networks. In several instances, we show that a reduction in code design extends to a reduction in capacity region if and only if the edge removal conjecture holds. Here, the edge removal conjecture states that removing an edge of negligible capacity from a network does not change its capacity region.

One of the key challenges in network coding research is how to handle networks containing cycles. As a result, many papers on network coding restrict attention to acyclic networks and some results derived for acyclic networks do not extend to networks containing cycles. We consider a streaming model for network communication where information is streamed to its destination under a constraint on maximal delay at the decoder. Restricting our attention to this scenario enables us to prove a code reduction from network coding to index coding in both acyclic and cyclic networks. Since index coding networks are acyclic, a consequence of this reduction is that under the streaming model, there is no fundamental difference between acyclic and cyclic networks.

Thesis Files