Local network coding on packet erasure channels – From Shannon capacity to stability region

Network Coding (NC) has emerged as a ubiquitous technique of communication networks and has extensive applications in both practical implementations and theoretical developments. While the Avalanche P2P file system from Microsoft, the MORE routing protocol, and the COPE coding architecture from MIT have implemented the idea of NC and exhibited promising performance improvements, a significant part of the success of NC stems from the continuing theoretic development of NC capacity, e.g., the Shannon capacity results for the single-flow multi-cast network and the packet erasure broadcast channel with feedback. However, characterizing the capacity for the practical wireless multi-flow network setting remains a challenging topic in NC. For example, the difficulties of finding the optimal NC strategy over multiple flows under varying-channel qualities and the rate adaption scenarios hinder any further advancement in this area. Despite the difficulty of characterizing the full capacity for large networks, there are evidences showing that even when using only local operations, NC can still recover substantial NC gain. We believe that a deeper understanding of multi-flow local network coding will play a key role in designing the next-generation high-throughput coding-based wireless network architecture. This thesis consists of three parts. In the first part, we characterize the full Shannon capacity region of the COPE principle when applied to a 2-flow wireless butterfly network with broadcast packet erasure channels. The capacity results allow for random overhearing probabilities, arbitrary scheduling policies, network-wide channel state information (CSI) feedback after each transmission, and potential use of non-linear network codes. We propose a theoretical outer bound and a new class of linear network codes, named the Space-Based Linear Network Coding (SBLNC), that achieves the capacity outer bound. Numerical experiments show that SBLNC provides close-to-optimal throughput even in the scenario with opportunistic routing. In the second part, we further consider the complete network dynamics of stochastic arrivals and queueing and study the corresponding stability region. Based on dynamic packet arrivals, the resulting solution would be one step closer to practical implementation, when compared to the previous block-code-based capacity study. For the 2-flow downlink scenario, we propose the first opportunistic INC + scheduling solution that is provably optimal for time-varying channels, i.e., the corresponding stability region matches the optimal Shannon capacity. Specifically, we first introduce a new binary INC operation, which is distinctly different from the traditional wisdom of XORing two overheard packets. We then develop a queue-length-based scheduling scheme, which, with the help of the new INC operation, can robustly and optimally adapt to time-varying channel quality. We then show that the proposed algorithm can be easily extended for rate adaptation and it again robustly achieves the optimal throughput. In the third part, we propose an 802.11-based MAC layer protocol which incorporates the rate adaption solution developed in the second part. The new MAC protocol realizes the promised intersession network coding gain for two-flow downlink traffic with short decoding delay. Furthermore, we delicately retain the CSMA-CA distributed contention mechanism with only 17 bits new header field changes, and carefully ensure the backward compatibility. In summary, the new solution demonstrates concrete throughput improvement without alternating the too much packet-by-packet traffic behavior. Such a feature is critical in practical implementation since it allows the network coding solution to be transparent to any arbitrary upper layer applications