Book Description

The classical store-and-forward routing has and will continue to be the most important routing architecture in many modern packet-switched communication networks. In a packet-switched network, data is sent in the form of discrete packets that traverse hop-by-hop from a source to a destination. At each intermediate hop, the router stores and examines the packets it receives then forwards them to the next hop until they reach the correct destinations according to some pre-defined routing algorithms. Importantly, the intermediate routers do not modify but simply store and forward the contents of the packets. In contrast, a new generalized approach to routing called Network Coding (NC) allows the intermediate routers to modify and combine packets from different sources and destinations in such a way that increases the overall throughput. The core idea of NC allowing the intermediate nodes in a network to perform data processing has a wide range of applications well beyond its initial application to routing, impacting different disciplines from distributed data storage and security to energy efficient sensor networks and Internet media streaming. To that end, this dissertation aims to develop the theories and applications of NC via four main thrusts: 1) Energy efficient NC techniques for sensor networks, 2) Novel NC techniques and protocols for Internet video streaming, 3) Stochastic data replenishment for large scale NC-based distributed storage systems, 4) Real-world implementation of NC-based distributed video streaming system. In thrust one, we describe a novel cross-sensor coding technique that combines network topology and coding techniques to maximize the life-time of a sensor network, by addressing the uneven energy consumption problem in data gathering sensor networks where the nodes closer to the sink tend to consume more energy than those of the farther nodes. Our approach is based on the following observation from the sensor networks using On-Off Keying and digital transmission: transmitting bit "1" consumes much more energy than bit "0". Our proposed coding technique exploits this difference to reduce the communication energy by limiting the number of bits "1" in the output codeword (low-weight codeword) and to use NC-based cross-sensor coding technique to equalize the communication energy among the nodes. This cross-sensor coding scheme can significantly extend the network lifetime as compared with traditional (binary) coding by solving the energy-consumption unfairness problem. The theoretical and experimental results confirm that transmission energy can be reduced substantially (e.g., a factor of 15) and the unequal energy consumption among nodes can be practically eliminated. In thrust two, we describe a rate distortion aware hierarchical NC technique and transport protocol for Internet video streaming. We begin by proposing a NC-based multi-sender streaming framework that reduces the overall storage, eliminates the complexity of sender synchronization, and enables TCP streaming. Furthermore, we propose a Hierarchical Network Coding (HNC) technique that facilitates scalable video streaming to combat bandwidth fluctuation on the Internet. This HNC technique enables receiver to recover the important data gracefully in the presence of limited bandwidth which causes an increase in decoding delay. Simulations demonstrate that under certain scenarios, our proposed NC techniques can result in bandwidth saving up to 60% over the traditional schemes. In thrust three, we present a theory of NC-based data replenishment to automate the process of data maintenance for large scale distributed storage systems. The data replenishment mechanism is the core of these systems that promises to reduce the coordination complexity and increases performance scalability. The data replenishment automates the process of maintaining a sufficient level of data redundancy to ensure the availability of data in presence of peer departures and failures. The dynamics of peers entering and leaving the network is modeled as a stochastic process. We propose a novel analytical time-backward technique to bound the expected time, the longer the better, for a piece of data to remain in P2P systems. Both theoretical and simulation results are in agreement, indicating that our proposed data replenishment via random linear network coding (RLNC) outperforms other popular strategies that employ repetition and channel coding techniques. Specifically, we show that the expected time for a piece of data to remain in a P2P system is exponential in the number of peers used to store the data for the RLNC-based strategy, while they are quadratic for other strategies. Furthermore, the time-backward technique can be applied to problems in other disciplines such as gene population modeling in theoretical biology. Finally in thrust four, we present the architecture, design, and experimental results of an actual NC-based distributed video streaming system. We first implement random linear network coding (RLNC) library and show the feasibility of using RLNC in P2P video streaming applications. Then we design, implement and analyze RESnc - a resilient P2P video storage and streaming over the Internet using network coding. RESnc increases the streaming throughput and data resiliency against peer departures and failures using peer diversity. These improvements are based on three architectural elements: 1) The RLNC scheme that breaks a video stream into multiple smaller pieces, codes, and disperses them throughout peers in the network, in such a way to maximize the probability of recovering the original video under peer departures and failures; 2) The scalable mechanism for automating the data replenishment process using RLNC to maintain a sufficient level of redundancy for video stored in the system; 3) The path-diversity streaming protocol for a client to simultaneously stream a video from multiple peers with minimal coordination. Experimental results demonstrated that our system adapts well with bandwidth fluctuation, provides significant playback quality improvement and bandwidth saving.