Network coding has emerged as a new paradigm for communication in networks, allowing packets to be algebraically combined at internal nodes, rather than simply routed or replicated. The very nature of packet-mixing, however, makes the system highly sensitive to error propagation. Classical error correction approaches are therefore insufficient to solve the problem, which calls for novel techniques and insights. The main portion of this work is devoted to the problem of error control assuming an adversarial or worst-case error model. We start by proposing a general coding theory for adversarial channels, whose aim is to characterize the correction capability of a code. We then specialize this theory to the cases of coherent and noncoherent network coding. For coherent network coding, we show that the correction capability is given by the rank metric, while for noncoherent network coding, it is given by a new metric, called the injection metric. For both cases, optimal or near-optimal coding schemes are proposed based on rank-metric codes. In addition, we show how existing decoding algorithms for rank-metric codes can be conveniently adapted to work over a network coding channel. We also present several speed improvements that make these algorithms the fastest known to date. The second part of this work investigates a probabilistic error model. Upper and lower bounds on capacity are obtained for any channel parameters, and asymptotic expressions are provided in the limit of long packet length and/or large field size. A simple coding scheme is presented that achieves capacity in both limiting cases. The scheme has fairly low decoding complexity and a probability of failure that decreases exponentially both in the packet length and in the field size in bits. Extensions of the scheme are provided for several variations of the channel. A final contribution of this work is to apply rank-metric codes to a closely related problem: securing a network coding system against an eavesdropper. We show that the maximum possible rate can be achieved with a coset coding scheme based on rank-metric codes. Unlike previous schemes, our scheme has the distinctive property of being universal: it can be applied on top of any communication network without requiring knowledge of or any modifications on the underlying network code. In addition, the scheme can be easily combined with a rank-metric-based error control scheme to provide both security and reliability.

The fundamental insight of use of coding in computer networks is that information to be transmitted from the source in a session can be inferred, or decoded, by the intended receivers, and does not have to be transmitted verbatim. Several coding techniques have gained popularity over the recent years. Among them is random network coding with random linear codes, in which a node in a network topology transmits a linear combination of incoming, or source, packets to its outgoing links. Theoretically, the high computational complexity of random linear codes (RLC) is well known, and is used to motivate the application of more efficient codes, such as the traditional Reed-Solomon (RS) codes and, more recently, fountain codes (LT codes). Factors like computational complexity, network overhead, and deployment flexibility can make one coding schemes more attractive for one application than the others. While there is no one-fit-all coding solution, random linear coding is very flexible, well known to be able to achieve optimal flow rates in multicast sessions, and universally adopted in all proposed protocols using network coding. However, its practicality has been questioned, due to its high computational complexity. Unfortunately, to date, there has been no commercial real-world system reported in the literature that take advantage of the power of network coding. This research represents the first attempt towards a high-performance design and implementation of network coding. The objective of this work is to explore the computational limits of network coding in off-the-shelf modern processors, and to provide a solid reference implementation to facilitate commercial deployment of network coding. We promote the development of new coding-based systems and protocols through a comprehensive toolkit with coding implementations that are not just reference implementations. Instead, they have attained high-performance and flexibility to find widespread adoption. The final work, packaged as a toolkit code-named Tenor, includes high-performance implementations of a number of coding techniques: random linear network coding (RLC), fountain codes (LT codes), and Reed-Solomon (RS) codes in CPUs (single and multi core(s) for both Intel x86 and IBM POWER families), GPUs (single and multiple), and mobile/embedded devices based on ARMv6 and ARMv7 cores. Tenor is cross-platform with support on Linux, Windows, Mac OS X, and iPhone OS, and supports both 32-bit and 64-bit platforms. The toolkit includes some 23K lines of C++ code. In order to validate the effectiveness of the Tenor toolkit, we build coding-based on-demand media streaming systems with GPU-based servers, thousands of clients emulated on a cluster of computers, and a small number of actual iPhone devices. To facilitate deployment of such large experiments, we develop Blizzard, a high-performance framework, with the main goals of: 1) emulating hundreds of client/peer applications on each physical node; 2) facilitating scalable servers that can efficiently communicate with thousands of clients. Our experiences offer an illustration of Tenor components in action, and their benefits in rapid system development. With Tenor, it is trivial to switch from one coding technique to another, scale up to thousands of clients, and deliver actual video to be played back even on mobile devices.

The prime wireless spectrum is inherently a critical yet scarce resource. As the demand of wireless bandwidth grows exponentially, it becomes a crucial issue to improve the spectrum utilization for the development and deployment of any new wireless technologies. In this thesis, we seek to address this problem through cooperative diversity and dynamic spectrum trading, in the context of the envisioned primary-secondary dynamic spectrum sharing paradigm. For an OFDMA-based cellular primary network which owns an exclusive right to access a certain spectrum band, we propose XOR-assisted cooperative diversity to improve the spectral efficiency of the allocated band, as well as an optimization framework to address the resource allocation problem. For the secondary network that utilizes cognitive radios to opportunistically exploit the spectrum white spaces, we establish a spectrum secondary market, design the market institution based on double auctions, and solve the decision making problem using reinforcement learning, to improve spectrum utilization via trading among secondary users.

The prime wireless spectrum is inherently a critical yet scarce resource. As the demand of wireless bandwidth grows exponentially, it becomes a crucial issue to improve the spectrum utilization for the development and deployment of any new wireless technologies. In this thesis, we seek to address this problem through cooperative diversity and dynamic spectrum trading, in the context of the envisioned primary-secondary dynamic spectrum sharing paradigm. For an OFDMA-based cellular primary network which owns an exclusive right to access a certain spectrum band, we propose XOR-assisted cooperative diversity to improve the spectral efficiency of the allocated band, as well as an optimization framework to address the resource allocation problem. For the secondary network that utilizes cognitive radios to opportunistically exploit the spectrum white spaces, we establish a spectrum secondary market, design the market institution based on double auctions, and solve the decision making problem using reinforcement learning, to improve spectrum utilization via trading among secondary users.

Network coding has emerged as a new paradigm for communication in networks, allowing packets to be algebraically combined at internal nodes, rather than simply routed or replicated. The very nature of packet-mixing, however, makes the system highly sensitive to error propagation. Classical error correction approaches are therefore insufficient to solve the problem, which calls for novel techniques and insights. The main portion of this work is devoted to the problem of error control assuming an adversarial or worst-case error model. We start by proposing a general coding theory for adversarial channels, whose aim is to characterize the correction capability of a code. We then specialize this theory to the cases of coherent and noncoherent network coding. For coherent network coding, we show that the correction capability is given by the rank metric, while for noncoherent network coding, it is given by a new metric, called the injection metric. For both cases, optimal or near-optimal coding schemes are proposed based on rank-metric codes. In addition, we show how existing decoding algorithms for rank-metric codes can be conveniently adapted to work over a network coding channel. We also present several speed improvements that make these algorithms the fastest known to date. The second part of this work investigates a probabilistic error model. Upper and lower bounds on capacity are obtained for any channel parameters, and asymptotic expressions are provided in the limit of long packet length and/or large field size. A simple coding scheme is presented that achieves capacity in both limiting cases. The scheme has fairly low decoding complexity and a probability of failure that decreases exponentially both in the packet length and in the field size in bits. Extensions of the scheme are provided for several variations of the channel. A final contribution of this work is to apply rank-metric codes to a closely related problem: securing a network coding system against an eavesdropper. We show that the maximum possible rate can be achieved with a coset coding scheme based on rank-metric codes. Unlike previous schemes, our scheme has the distinctive property of being universal: it can be applied on top of any communication network without requiring knowledge of or any modifications on the underlying network code. In addition, the scheme can be easily combined with a rank-metric-based error control scheme to provide both security and reliability.

The fundamental insight of use of coding in computer networks is that information to be transmitted from the source in a session can be inferred, or decoded, by the intended receivers, and does not have to be transmitted verbatim. Several coding techniques have gained popularity over the recent years. Among them is random network coding with random linear codes, in which a node in a network topology transmits a linear combination of incoming, or source, packets to its outgoing links. Theoretically, the high computational complexity of random linear codes (RLC) is well known, and is used to motivate the application of more efficient codes, such as the traditional Reed-Solomon (RS) codes and, more recently, fountain codes (LT codes). Factors like computational complexity, network overhead, and deployment flexibility can make one coding schemes more attractive for one application than the others. While there is no one-fit-all coding solution, random linear coding is very flexible, well known to be able to achieve optimal flow rates in multicast sessions, and universally adopted in all proposed protocols using network coding. However, its practicality has been questioned, due to its high computational complexity. Unfortunately, to date, there has been no commercial real-world system reported in the literature that take advantage of the power of network coding. This research represents the first attempt towards a high-performance design and implementation of network coding. The objective of this work is to explore the computational limits of network coding in off-the-shelf modern processors, and to provide a solid reference implementation to facilitate commercial deployment of network coding. We promote the development of new coding-based systems and protocols through a comprehensive toolkit with coding implementations that are not just reference implementations. Instead, they have attained high-performance and flexibility to find widespread adoption. The final work, packaged as a toolkit code-named Tenor, includes high-performance implementations of a number of coding techniques: random linear network coding (RLC), fountain codes (LT codes), and Reed-Solomon (RS) codes in CPUs (single and multi core(s) for both Intel x86 and IBM POWER families), GPUs (single and multiple), and mobile/embedded devices based on ARMv6 and ARMv7 cores. Tenor is cross-platform with support on Linux, Windows, Mac OS X, and iPhone OS, and supports both 32-bit and 64-bit platforms. The toolkit includes some 23K lines of C++ code. In order to validate the effectiveness of the Tenor toolkit, we build coding-based on-demand media streaming systems with GPU-based servers, thousands of clients emulated on a cluster of computers, and a small number of actual iPhone devices. To facilitate deployment of such large experiments, we develop Blizzard, a high-performance framework, with the main goals of: 1) emulating hundreds of client/peer applications on each physical node; 2) facilitating scalable servers that can efficiently communicate with thousands of clients. Our experiences offer an illustration of Tenor components in action, and their benefits in rapid system development. With Tenor, it is trivial to switch from one coding technique to another, scale up to thousands of clients, and deliver actual video to be played back even on mobile devices.

Computation problems, such as network coding and averaging consen- sus, have become increasingly central to the study of wireless networks. Network coding, in which intermediate terminals compute and forward functions of others’ messages, is instrumental in establishing the capacity of multicast networks. Averaging consensus, in which terminals compute the mean of others’ measurements, is a canonical building block of dis- tributed estimation over sensor networks. Both problems, however, are typically studied over graphical networks, which abstract away the broad- cast and superposition properties fundamental to wireless propagation. The performance of computation in realistic wireless environments, there- fore, remains unclear. In this thesis, I seek after near-optimal computation strategies under realistic wireless models. For both network coding and averaging con- sensus, cooperative communications plays a key role. For network cod- ing, I consider two topologies: a single-layer network in which users may signal cooperatively, and a two-transmitter, two-receiver network aided by a dedicated relay. In the former topology, I develop a decode-and- forward scheme based on a linear decomposition of nested lattice codes. For a network having two transmitters and a single receiver, the proposed scheme is optimal in the diversity-multiplexing tradeo↵; otherwise it pro- vides significant rate gains over existing non-cooperative approaches. In the latter topology, I show that an amplify-and-forward relay strategy is optimal almost everywhere in the degrees-of-freedom. Furthermore, for symmetric channels, amplify-and-forward achieves rates near capacity for a non-trivial set of channel gains. For averaging consensus, I consider large networks of randomly-placed nodes. Under a path-loss wireless model, I characterize the resource de- mands of consensus with respect to three metrics: energy expended, time elapsed, and time-bandwidth product consumed. I show that existing con- sensus strategies, such as gossip algorithms, are nearly order optimal in the energy expended but strictly suboptimal in the other metrics. I propose a new consensus strategy, tailored to the wireless medium and cooperative in nature, termed hierarchical averaging. Hierarchical averaging is nearly order optimal in all three metrics for a wide range of path-loss exponents. Finally, I examine consensus under a simple quantization model, show- ing that hierarchical averaging achieves a nearly order-optimal tradeo↵ between resource consumption and estimation accuracy.

Les systèmes de stockage actuels font face à une explosion des données à gérer. A l'échelle actuelle, il serait illusoire d'imaginer une unique entité centralisée capable de stocker et de restituer les données de tous ses utilisateurs. Bien que du point de vue de l'utilisateur, le système de stockage apparaît tel un unique interlocuteur, son architecture sous-jacente est nécessairement devenue distribuée. En d'autres termes, le stockage n'est plus assigné à un équipement centralisé, mais est maintenant distribué parmi de multiples entités de stockage indépendantes, connectées via un réseau. Par conséquent, la bande passante inhérente à ce réseau devient une ressource à prendre en compte dans le design d'un système de stockage distribué. En effet, la bande passante d'un système est intrinsèquement une ressource limitée, qui doit être convenablement gérée de manière à éviter toute congestion du système. Cette thèse se propose d'optimiser l'utilisation de la bande passante dans les systèmes de stockage distribués, en limitant l'impact du churn et des défaillances. L'objectif est double, le but est d'une part, de maximiser la bande passante disponible pour les échanges de données, et d'une autre part de réduire la consommation de bande passante inhérente aux opérations de maintenance. Pour ce faire, nous présentons trois contributions distinctes. La première contribution présente une architecture pair-à-pair hybride qui tient compte de la topologie bas-niveau du réseau, c'est à dire la présence de gateways entre les utilisateurs et le système. La seconde contribution propose un mécanisme de timeout adaptatif au niveau utilisateur, basé sur une approche Bayésienne. La troisième contribution décrit un protocole permettant la réparation efficace de données encodées via des codes à effacement. Enfin, cette thèse se conclut sur la possibilité d'utiliser des techniques d'alignement d'interférence, communément utilisées en communication numérique afin d'accroître l'efficacité des protocoles de réparation de données encodées.

This research investigates cross-layer design in multi-hop wireless networks with random access. Due to the complexity of the problem, we study cross-layer design with a simple slotted ALOHA medium access control (MAC) protocol without considering any network dynamics. Firstly, we study the optimal joint configuration of routing and MAC parameters in slotted ALOHA based wireless networks under a signal to interference plus noise ratio based physical interference model. We formulate a joint routing and MAC (JRM) optimization problem under a saturation assumption to determine the optimal max-min throughput of the flows and the optimal configuration of routing and MAC parameters. The JRM optimization problem is a complex non-convex problem. We solve it by an iterated optimal search (IOS) technique and validate our model via simulation. Via numerical and simulation results, we show that JRM design provides a significant throughput gain over a default configuration in a slotted ALOHA based wireless network. Next, we study the optimal joint configuration of routing, MAC, and network coding in wireless mesh networks using an XOR-like network coding without opportunistic listening. We reformulate the JRM optimization problem to include the simple network coding and obtain a more complex non-convex problem. Similar to the JRM problem, we solve it by the IOS technique and validate our model via simulation. Numerical and simulation results for different networks illustrate that (i) the jointly optimized configuration provides a remarkable throughput gain with respect to a default configuration in a slotted ALOHA system with network coding and (ii) the throughput gain obtained by the simple network coding is significant, especially at low transmission power, i.e., the gain obtained by jointly optimizing routing, MAC, and network coding is significant even when compared to an optimized network without network coding. We then show that, in a mesh network, a significant fraction of the throughput gain for network coding can be obtained by limiting network coding to nodes directly adjacent to the gateway. Next, we propose simple heuristics to configure slotted ALOHA based wireless networks without and with network coding. These heuristics are extensively evaluated via simulation and found to be very efficient. We also formulate problems to jointly configure not only the routing and MAC parameters but also the transmission rate parameters in multi-rate slotted ALOHA systems without and with network coding. We compare the performance of multi-rate and single rate systems via numerical results. We model the energy consumption in terms of slotted ALOHA system parameters. We found out that the energy consumption for various cross-layer systems, i.e., single rate and multi-rate slotted ALOHA systems without and with network coding, are very close.

Network coding is a promising approach for increasing performance of multicast data transmission and reducing energy costs. Of course, it is essential to consider security aspects to ensure a reliable data transmission. Particularly, pollution attacks may have serious impacts in network coding since a single attacker can jam large parts of the network. Therefore, various approaches have been introduced to secure network coding against this type of attack. However, introducing security increases costs. Even though there are some performance analysis of secure schemes, to our knowledge there are no details whether these schemes are worthwhile to replace routing under the facet of efficiency. Thus, we discuss in this report parameters to assess the efficiency of secure network coding schemes. Using three network graphs, we evaluate parameters focusing on communication overhead for selected schemes. Our results show that there are still benefits in comparison to routing depending on the network topology.