Analysis and design of intersession network coding in communication networks

Network coding extends the functionality of networking nodes beyond the traditional store-and-forward operations. It allows information from different packets/ flows to be mixed together at intermediate nodes using mathematical operations. There has been significant prior work that has explored “intrasession” network coding, where only packets of the same session or user are allowed to be mixed together. However, intrasession network coding, while providing substantial gains in the presence of multicast traffic, provides no performance gains for unicast traffic, which is the predominant traffic on the Internet. On the other hand, intersession network coding, where packets of different sessions or users are allowed to be mixed together, improves the capacity of the network in the presence of either unicast or multicast traffic. In this dissertation, we use optimization and information theoretic approaches to design intersession network coding schemes for both wireline and wireless networks. In wireline networks we design a distributed but joint rate control algorithm and coding scheme that are optimal when any coded symbol is formed by at most two original symbols. The proposed approach improves both the capacity and fairness over existing approaches. Due to their broadcast nature, wireless networks enjoy higher gains from network coding than their wireline counterpart. We explore two different wireless network settings in this dissertation and develop optimal intersession network coding schemes under these settings. The first setting is when channel conditions are known prior to transmission. In this case we develop a cross-layer framework that requires minimal interaction between layers and achieves the optimal solution when any coded symbol is formed by at most two original symbols. We also provide a coding scheme that uses only XOR operations and achieves the same throughput as the one developed for wireline networks. We study the performance loss of our framework when using non-optimal but distributed scheduling algorithms. This framework is also extended to include energy minimization. In the second setting we assume that channel conditions are unknown prior to transmission. Without network coding the optimal solution can be achieved using opportunistic routing. With network coding we study the problem of two-hop relay network where the encoding and decoding nodes are neighbors. For this problem we provide a coding scheme that achieves the capacity of the network with two flows. We also use this result to maximize the throughput of a general lossy wireless network