Demands for multimedia content, one form of digital content, are continuously increasing at a phenomenal pace, as video features are commonly available on personal devices, such as iPod, cell phone, laptop, PDA, and Blackberry. The streaming service poses unique bandwidth and delay challenges to application designers. The size of a typical video content is usually orders of magnitude larger than that of any other type of content, resulting in high demands for bandwidth contribution from the content providers. Even more challenging, the content must be delivered to end hosts in real time to maintain smooth playback, i.e., the content must be transmitted at a satisfactory rate. In this thesis, we present our research towards a high-quality peer-to-peer live streaming system that utilizes network coding, a novel technique that permits coding at every peer, which has proven benefits in file dissemination applications. To ensure the practicality of our work, it is our imperative objective to conduct all experiments under realistic settings.

Multi-hop Wireless Networks (MWNs) represent a class of networks where messages are forwarded through multiple hops of wireless transmission. Applications of this newly emerging communication paradigm include asset monitoring wireless sensor networks (WSNs), command communication mobile ad hoc networks (MANETs), community- or campus-wide wireless mesh networks (WMNs), etc. Information security is one of the major barriers to the wide-scale deployment of MWNs but has received little attention so far. On the one hand, due to the open wireless channels and multi-hop wireless transmissions, MWNs are vulnerable to various information security threats such as eavesdropping, data injection/modification, node compromising, traffic analysis, and flow tracing. On the other hand, the characteristics of MWNs including the vulnerability of intermediate network nodes, multi-path packet forwarding, and limited computing capability and storage capacity make the existing information security schemes designed for the conventional wired networks or single-hop wireless networks unsuitable for MWNs. Therefore, newly designed schemes are highly desired to meet the stringent security and performance requirements for the information security of MWNs. In this research, we focus on three fundamental information security issues in MWNs: efficient privacy preservation for source anonymity, which is critical to the information security of MWNs; the traffic explosion issue, which targets at preventing denial of service (DoS) and enhancing system availability; and the cooperative peer-to-peer information exchange issue, which is critical to quickly achieve maximum data availability if the base station is temporarily unavailable or the service of the base station is intermittent. We have made the following three major contributions. Firstly, we identify the severe threats of traffic analysis/flow tracing attacks to the information security in network coding enabled MWNs. To prevent these attacks and achieve source anonymity in MWNs, we propose a network coding based privacy-preserving scheme. The unique “mixing” feature of network coding is exploited in the proposed scheme to confuse adversaries from conducting advanced privacy attacks, such as time correlation, size correlation, and message content correlation. With homomorphic encryption functions, the proposed scheme can achieve both privacy preservation and data confidentiality, which are two critical information security requirements. Secondly, to prevent traffic explosion and at the same time achieve source unobservability in MWNs, we propose a network coding based privacy-preserving scheme, called SUNC (Source Unobservability using Network Coding). Network coding is utilized in the scheme to automatically absorb dummy messages at intermediate network nodes, and thus, traffic explosion induced denial of service (DoS) can be naturally prevented to ensure the system availability. In addition to ensuring system availability and achieving source unobservability, SUNC can also thwart internal adversaries. Thirdly, to enhance the data availability when a base station is temporarily unavailable or the service of the base station is intermittent, we propose a cooperative peer-to-peer information exchange scheme based on network coding. The proposed scheme can quickly accomplish optimal information exchange in terms of throughput and transmission delay. For each research issue, detailed simulation results in terms of computational overhead, transmission efficiency, and communication overhead, are given to demonstrate the efficacy and efficiency of the proposed solutions.

Multi-hop Wireless Networks (MWNs) represent a class of networks where messages are forwarded through multiple hops of wireless transmission. Applications of this newly emerging communication paradigm include asset monitoring wireless sensor networks (WSNs), command communication mobile ad hoc networks (MANETs), community- or campus-wide wireless mesh networks (WMNs), etc. Information security is one of the major barriers to the wide-scale deployment of MWNs but has received little attention so far. On the one hand, due to the open wireless channels and multi-hop wireless transmissions, MWNs are vulnerable to various information security threats such as eavesdropping, data injection/modification, node compromising, traffic analysis, and flow tracing. On the other hand, the characteristics of MWNs including the vulnerability of intermediate network nodes, multi-path packet forwarding, and limited computing capability and storage capacity make the existing information security schemes designed for the conventional wired networks or single-hop wireless networks unsuitable for MWNs. Therefore, newly designed schemes are highly desired to meet the stringent security and performance requirements for the information security of MWNs. In this research, we focus on three fundamental information security issues in MWNs: efficient privacy preservation for source anonymity, which is critical to the information security of MWNs; the traffic explosion issue, which targets at preventing denial of service (DoS) and enhancing system availability; and the cooperative peer-to-peer information exchange issue, which is critical to quickly achieve maximum data availability if the base station is temporarily unavailable or the service of the base station is intermittent. We have made the following three major contributions. Firstly, we identify the severe threats of traffic analysis/flow tracing attacks to the information security in network coding enabled MWNs. To prevent these attacks and achieve source anonymity in MWNs, we propose a network coding based privacy-preserving scheme. The unique “mixing” feature of network coding is exploited in the proposed scheme to confuse adversaries from conducting advanced privacy attacks, such as time correlation, size correlation, and message content correlation. With homomorphic encryption functions, the proposed scheme can achieve both privacy preservation and data confidentiality, which are two critical information security requirements. Secondly, to prevent traffic explosion and at the same time achieve source unobservability in MWNs, we propose a network coding based privacy-preserving scheme, called SUNC (Source Unobservability using Network Coding). Network coding is utilized in the scheme to automatically absorb dummy messages at intermediate network nodes, and thus, traffic explosion induced denial of service (DoS) can be naturally prevented to ensure the system availability. In addition to ensuring system availability and achieving source unobservability, SUNC can also thwart internal adversaries. Thirdly, to enhance the data availability when a base station is temporarily unavailable or the service of the base station is intermittent, we propose a cooperative peer-to-peer information exchange scheme based on network coding. The proposed scheme can quickly accomplish optimal information exchange in terms of throughput and transmission delay. For each research issue, detailed simulation results in terms of computational overhead, transmission efficiency, and communication overhead, are given to demonstrate the efficacy and efficiency of the proposed solutions.

In order to achieve the storage QoS and power saving, we proposed a fast data migration/transmission scheme and a power saving algorithm for Dataenode management. The fast data migration/ transmission scheme consists of three mechanisms. First, it uses multicast to improve the network bandwidth and solve the I/O and bandwidth bottlenecks. Then, a network coding is used to increase the network throughput and retain high fault tolerance. Third, it uses a user/Dataenode connection management to prevent missing the important message and collocates with CPU & I/O bound scheduling to make data evenly stored in the system. Experimental results show the proposed fast data migration/transmission improves 56% and 85% efficiency in the upload bandwidth and the response time. The proposed power saving algorithm applies the Kalman filter first and then add with the pattern analysis to predict the system workload to adjust the number of Dataenodes dynamically in order to save power. Experimental results show that the proposed power saving algorithm for Dataenode management achieves more than 92.97% accuracy in the workload prediction and improves 52.25% in power consumption with 3.82% error rate.

The reliability of networking and communication systems is vital for the nation's economy and security. Optical and cellular networks have become a critical infrastructure and are indispensable in emergency situations. This dissertation outlines methods for analyzing such infrastructures in the presence of catastrophic failures, such as a hurricane, as well as accidental failures of one or more components. Additionally, it presents a method for protecting against the loss of a single link in a multicast network along with a technique that enables wireless clients to efficiently recover lost data sent by their source through collaborative information exchange. Analysis of a network's reliability during a natural disaster can be assessed by simulating the conditions in which it is expected to perform. This dissertation conducts the analysis of a cellular infrastructure in the aftermath of a hurricane through Monte-Carlo sampling and presents alternative topologies which reduce resulting loss of calls. While previous research on restoration mechanisms for large-scale networks has mostly focused on handling the failures of single network elements, this dissertation examines the sampling methods used for simulating multiple failures. We present a quick method of nding a lower bound on a network's data loss through enumeration of possible cuts as well as an efficient method of nding a tighter lower bound through genetic algorithms leveraging the niching technique. Mitigation of data losses in a multicast network can be achieved by adding redundancy and employing advanced coding techniques. By using Maximum Rank Distance (MRD) codes at the source, a provider can create a parity packet which is e ectively linearly independent from the source packets such that all packets may be transmitted through the network using the network coding technique. This allows all sinks to recover all of the original data even with the failure of an edge within the network. Furthermore, this dissertation presents a method that allows a group of wireless clients to cooperatively recover from erasures (e.g., due to failures) by using the index coding techniques.

Network coding and duty-cycling are two popular techniques for saving energy in wireless sensor networks. To the best of our knowledge, the idea to combine these two techniques, for even more aggressive energy savings, has not been explored. One explanation is that these two techniques achieve energy efficiency through conflicting means, e.g., network coding saves energy by exploiting overhearing, whereas dutycycling saves energy by cutting idle listening and, thus, overhearing. In this thesis, we thoroughly evaluate the use of network coding in duty-cycled sensor networks. We propose a scheme called DutyCode, in which a MAC protocol implements packet streaming and allows the application to decide when a node can sleep. Additionally, a novel, efficient coding scheme decision algorithm, ECSDT, assists DutyCode to reduce further energy consumption by minimizing redundant packet transmissions, while an adaptive mode switching algorithm allows smooth and timely transition between DutyCode and the default MAC protocol, without any packet loss. We investigate our solution analytically, implement it on mote hardware, and evaluate it in a 42-node indoor testbed. Performance evaluation results show that our scheme saves 30-46% more energy than solutions that use network coding, without using duty-cycling.

Unlike the traditional store-and-forward mechanism in packet-switching networks,network coding schemes could combine and modify the contents of a number of packets from different source before the packets are forwarded.It has been recently shown that network coding techniques can significantly increase the overall throughput of wireless networks by taking advantage of their broadcast nature. In wireless networks,each transmitted packet is broadcasted within a certain area and can be overheard by the neighboring nodes.When a node needs to transmit packets,it employs the coding approach that uses the knowledge of what the node's neighbors have heard in order to reduce the number of transmissions. In this thesis,I propose jointly designing the network coding scheme and the media access control scheme to improve the performance of wireless networks.

Opportunistic communication leverages communication opportunities arising by chance to provide significant performance benefit and even enable communication where it would be impossible otherwise. The goal of this dissertation is to optimize opportunistic communication to achieve good performance in wireless networks. A key challenge in optimizing opportunistic communication arises from dynamic and incidental nature of communication. Complicated wireless interference patterns, high mobility, and frequent fluctuations in wireless medium make the optimization even harder. This dissertation proposes a series of optimization frameworks that systematically optimizes opportunistic communication to achieve good performance in wireless mesh networks and vehicular networks. We make the following three major contributions: First, we develop novel algorithms, techniques, and protocols that optimize opportunistic communication of wireless mesh network to achieve good, predictable user performance. Our framework systematically optimizes end-to-end performance (e.g., total throughput). It yields significant improvement over existing routing schemes. We also show that it is robust against inaccuracy introduced by dynamic network conditions. Second, we propose a novel overlay framework to exploit inter-flow network coding in opportunistic routing. In this framework, an overlay network performs inter-flow coding to effectively reduce traffic imposed on the underlay network, and an underlay network uses optimized opportunistic routing to provide efficient and reliable overlay links. We show that inter-flow coding together with opportunistic routing and rate-limiting brings significant performance benefit. Finally, we develop a novel optimization framework in vehicular networks to effectively leverage opportunistic contacts between vehicles and access points (APs). We develop a new mobility prediction algorithm and an optimization algorithm to determine an efficient replication scheme that exploit the synergy among Internet connectivity, local wireless connectivity, mesh network connectivity, and vehicular relay connectivity. Based on our framework, we develop a practical system that enables high-bandwidth content distribution and demonstrate the effectiveness of our approach using simulation, emulation, and testbed experiments. / text

This dissertation examines the design and application of network coding (NC) strategies to enhance the performance of communication networks. With its ability to combine information packets from different, previously independent data flows, NC has the potential to improve the throughput, reduce delay and increase the power efficiency of communication systems in ways that have not yet been fully utilized given the current lack of processing power at relay nodes. With these motivations in mind, this dissertation presents three main contributions that employ NC to improve the efficiency of practical communication systems. First, the integration of NC and erasure coding (EC) is presented in the context of wired networks. While the throughput gains from utilizing NC have been demonstrated, and EC has been shown to be an efficient means of reducing packet loss, these have generally been done independently. This dissertation presents innovative methods to combine these two techniques through cross-layer design methodologies. Second, three methods to reduce or limit the delay introduced by NC when deployed in networks with asynchronous traffic are developed. Also, a novel opportunistic approach of applying EC for improved data reliability is designed to take advantage of unused opportunities introduced by the delay reduction methods proposed. Finally, computationally efficient methods for the selection of relay nodes and the assignment of transmit power values to minimize the total transmit power consumed in cooperative relay networks with NC are developed. Adaptive power allocation is utilized to control the formation of the network topology to maximize the efficiency of the NC algorithm. This dissertation advances the efficient deployment of NC through its integration with other algorithms and techniques in cooperative communication systems within the framework of cross-layer protocol design. The motivation is that to improve the performance of communication systems, relay nodes will need to perform more intelligent processing of data units than traditional routing. The results presented in this work are applicable to both wireless and wired networks with real-time traffic which exist in such systems ranging from cellular and ad-hoc networks to fixed optical networks.

Infrastructure wireless mesh networks (IWMNs) provide inexpensive deployment, flexible extension of wireless infrastructure, and easy access to the Internet. With multiple radios at each node, a capacity per node improves by transmitting over these radios simultaneously using orthogonal channels. However, without properly addressing the problem of channel assignment and routing for those nodes that form wireless infrastructures, the resulting network throughput and reliability are unlikely to meet the requirements of those highly demanding, media distribution applications. On a particular channel, poor resource allocation at a given access point/gateway of the underlying IWMN can amplify the problem even further. Motivated by these problems, we develop, based on the theory of network coding, a set of alternative solutions that addresses the above issues. We first introduce a sub-optimal solution to the joint problem of network coding, channel assignment and link scheduling for throughput optimization in the multi-channel multi-radio IWMN. We mathematically formulate the problem as a linear program, taking into account opportunistic overhearing, among other constraints. Based on this formulation, we develop a sub-optimal, auction-based algorithm for network throughput optimization. Simulation results reveal the effectiveness of our algorithm in exploiting multiple radios and channels while coping with fairness issues arising from auctions. The proposed solution also shows promising gains over traditional routing solutions. Our experimental results on an 802.11 testbed further confirm these results. The second part of this thesis then presents three AP/gateway-oriented solutions that address the link-level issues related to radio resource allocation at a particular AP/gateway node of the underlying IWMN, which operates on a given channel serving a set of wireless clients. Since the last-hop wireless link is normally a bottleneck of the IWMN, the key idea underlying all the proposed solutions is to use a version of network coding at the bottlenecked AP/gateway. We use Markov chains and the probability theory to derive several performance measures related to media distribution for both uplink and downlink applications. Via extensive simulations, we show the promising delay and reliability gains of the network-coding based schemes over the traditional schemes without network coding.