In classical network information theory, information packets are treated as commodities, and the nodes of the network are only allowed to duplicate and forward the packets. The new paradigm of network coding, which was introduced by Ahlswede et al., states that if the nodes are permitted to combine the information packets and forward a function of them, the throughput of the network can dramatically increase. In this dissertation we focused on the design and analysis of low complexity network coding schemes for different topologies of wired and wireless networks. In the first part we studied the routing capacity of wired networks. We provided a description of the routing capacity region in terms of a finite set of linear inequalities. We next used this result to study the routing capacity region of undirected ring networks for two multimessage scenarios. Finally, we used new network coding bounds to prove the optimality of routing schemes in these two scenarios. In the second part, we studied node-constrained line and star networks. We derived the multiple multicast capacity region of node-constrained line networks based on a low complexity binary linear coding scheme. For star networks, we examined the multiple unicast problem and offered a linear coding scheme. Then we made a connection between the network coding in a node-constrained star network and the problem of index coding with side information. In the third part, we studied the linear deterministic model of relay networks (LDRN). We focused on a unicast session and derived a simple capacity-achieving transmission scheme. We obtained our scheme by a connection to the submodular flow problem through the application of tools from matroid theory and submodular optimization theory. We also offered polynomial-time algorithms for calculating the capacity of the network and the optimal coding scheme. In the final part, we considered the multicasting problem in an LDRN and proposed a new way to construct a coding scheme. Our construction is based on the notion of flow for a unicast session in the third part of this dissertation. We presented randomized and deterministic polynomial-time versions of our algorithm.

Network Coding is a new possibility to transmit data through a network. By combining different packets instead of simply forwarding, network coding offers the opportunity to reach the Min-Cut/Max-Flow capacity in multicast data transmissions. However, the basic schemes are vulnerable to so-called pollution attacks, where an attacker can jam large parts of the transmission by infiltrating only one bogus message. In the literature we found several approaches which aim at handling this kind of attack with different amounts of overhead. Though, the cost for a specific secure network coding scheme highly depends on the underlying network. The goal of this paper is on the one hand to describe which network parameters influence the efficiency of a certain scheme and on the other hand to provide concrete suggestions for selecting the most efficient secure network coding scheme considering a given network. We will illustrate that there does not exist “the best” secure network scheme concerning efficiency, but all selected schemes are more or less suited under certain network topologies.

The popularity of the great variety of Internet usage brings about a significant growth of the data traffic in telecommunication network. Data transmission efficiency will be challenged under the premise of current network capacity and data flow control mechanisms. In addition to increasing financial investment to expand the network capacity, improving the existing techniques are more rational and economical. Various cutting-edge researches to cope with future network requirement have emerged, and one of them is called network coding. As a natural extension in coding theory, it allows mixing different network flows on the intermediate nodes, which changes the way of avoiding collisions of data flows. It has been applied to achieve better throughput and reliability, security, and robustness in various network environments and applications. This dissertation focuses on the use of network coding for multicast in fixed mesh networks and distributed storage systems. We first model various multicast routing strategies within an optimization framework, including tree-based multicast and network coding; we solve the models with efficient algorithms, and compare the coding advantage, in terms of throughput gain in medium size randomly generated graphs. Based on the numerical analysis obtained from previous experiments, we propose a revised multicast routing framework, called strategic network coding, which combines standard multicast forwarding and network coding features in order to obtain the most benefit from network coding at lowest cost where such costs depend both on the number of nodes performing coding and the volume of traffic that is coded. Finally, we investigate a revised transportation problem which is capable of calculating a static routing scheme between servers and clients in distributed storage systems where we apply coding to support the storage of contents. We extend the application to a general optimization problem, named transportation problem with degree constraints, which can be widely used in different industrial fields, including telecommunication, but has not been studied very often. For this problem, we derive some preliminary theoretical results and propose a reasonable Lagrangian decomposition approach

While network data transmission was traditionally accomplished via routing, network coding (NC) broke this rule by allowing network nodes to perform linear combinations of the upcoming data packets. Network operations are performed in a specific Galois field of fixed size q. Decoding only involves a Gaussian elimination with the received network-coded packets. However, in practical wireless environments, NC might be susceptible to transmission errors caused by noise, fading, or interference. This drawback is quite problematic for real-time applications, such as multimediacontent delivery, where timing constraints may lead to the reception of an insufficient number of packets and consequently to difficulties in decoding the transmitted sources. At best, some packets can be recovered, while in the worst case, the receiver is unable to recover any of the transmitted packets.In this thesis, we propose joint source-network coding and decoding schemes in the purpose of providing an approximate reconstruction of the source in situations where perfect decoding is not possible. The main motivation comes from the fact that source redundancy can be exploited at the decoder in order to estimate the transmitted packets, even when some of them are missing. The redundancy can be either natural, i.e, already existing, or artificial, i.e, externally introduced.Regarding artificial redundancy, we choose multiple description coding (MDC) as a way of introducing structured correlation among uncorrelated packets. By combining MDC and NC, we aim to ensure a reconstruction quality that improves gradually with the number of received network-coded packets. We consider two different approaches for generating descriptions. The first technique consists in generating multiple descriptions via a real-valued frame expansion applied at the source before quantization. Data recovery is then achieved via the solution of a mixed integerlinear problem. The second technique uses a correlating transform in some Galois field in order to generate descriptions, and decoding involves a simple Gaussian elimination. Such schemes are particularly interesting for multimedia contents delivery, such as video streaming, where quality increases with the number of received descriptions.Another application of such schemes would be multicasting or broadcasting data towards mobile terminals experiencing different channel conditions. The channel is modeled as a binary symmetric channel (BSC) and we study the effect on the decoding quality for both proposed schemes. Performance comparison with a traditional NC scheme is also provided.Concerning natural redundancy, a typical scenario would be a wireless sensor network, where geographically distributed sources capture spatially correlated measures. We propose a scheme that aims at exploiting this spatial redundancy, and provide an estimation of the transmitted measurement samples via the solution of an integer quadratic problem. The obtained reconstruction quality is compared with the one provided by a classical NC scheme.

In networks, using large buffers tend to increase end-to-end packet delay and its deviations, conflicting with real-time applications such as online gaming, audio-video services, IPTV, and VoIP. Further, large buffers complicate the design of high speed routers, leading to more power consumption and board space. According to Moore's law, switching speeds double every 18 months while memory access speeds double only every 10 years. Hence, as memory requirements increasingly become a limiting aspect of router design, studying networks in finite-buffer regime seems necessary for network engineers. This work focuses on both practical and theoretical aspects of finite-buffer networks. In Chapters 1-7, we investigate the effects of finite buffer sizes on the throughput and packet delay in different networks. These performance measures are shown to be linked to the stationary distribution of an underlying irreducible Markov chain that exactly models the changes in the network. An iterative scheme is proposed to approximate the steady-state distribution of buffer occupancies by decoupling the exact chain to smaller chains. These approximate solutions are used to analytically characterize network throughput and packet delay, and are also applied to some network performance optimization problems. Further, using simulations, it is confirmed that the proposed framework yields accurate estimates of the throughput and delay performance measures and captures the vital trends and tradeoffs in these networks. In Chapters 8-10, we address the problem of modeling and analysis of the performance of finite-memory random linear network coding in erasure networks. When using random linear network coding, the content of buffers creates dependencies which cannot be captured directly using the classical queueing theoretical models. A careful derivation of the buffer occupancy states and their transition rules are presented as well as decodability conditions when random linear network coding is performed on a stream of arriving packets.

Network coding is a technique used to increase the capacity of a network by combining messages sent over the network. The combined messages could be separated by using sufficient original messages which were used to combine the messages. Network coding can be implemented in different layers of the 051 stack, but to date a complete comparison between different implementations of network coding has not been done. The goal of this dissertation is to implement a wireless node model with network coding in the MAC layer and evaluate the performance characteristics of reference networks that implement the new node model. This will serve as the first step of a greater goal, namely finding the most favourable position in the 051 stack to implement network coding. The characteristics of the different implementations of network coding are presented in this dissertation. Simulations were done in OPNET® to find further attributes concerning the implementation of network coding in the MAC layer. The simulation process used is presented and explained, and the results from the simulations are analysed. Network coding in the simulations was implemented opportunistically. The results show that the more often different nodes send frames to the coding node, the better network coding performs. The work contributes to finding the best layer for implementing network coding for its increased throughput. A benchmark network was created so that network coding could be implemented in all the layers of the 051 stack, and then be compared to each other. An implementation of network coding in the MAC layer was simulated and analyzed. We conclude that, because there are so many different purposes for which networks are used, a single instance of network coding is unlikely to be similarly beneficial to all purposes. There still remains work to find the most favourable position for network coding in the 051 stack for all the different types of network coding. / Thesis (M. Ing. (Computer and Electronical Engineering))--North-West University, Potchefstroom Campus, 2011

Recently, erasure networks have received significant attention in the literature as they are used to model both wireless and wireline packet-switched networks. Many packet-switched data networks like wireless mesh networks, the Internet, and Peer-to-peer networks can be modeled as erasure networks. In any erasure network, path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. Our analysis of diversity over erasure networks studies the problem of rate allocation (RA) across multiple independent paths, coding over erasure channels, and the trade-off between rate and diversity gain in three consecutive chapters. In the chapter 2, Forward Error Correction (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. We prove that the probability of irrecoverable loss (P_E) decays exponentially with the number of paths. Furthermore, the RA problem across independent paths is studied. Our objective is to find the optimal RA, i.e. the allocation which minimizes P_E. Using memoization technique, a heuristic suboptimal algorithm with polynomial runtime is proposed for RA over a finite number of paths. This algorithm converges to the asymptotically optimal RA when the number of paths is large. For practical number of paths, the simulation results demonstrate the close-to-optimal performance of the proposed algorithm. Chapter 3 addresses the problem of lower-bounding the probability of error (PE) for any block code over an input-independent channel. We derive a lower-bound on PE for a general input-independent channel and find the necessary and sufficient condition to meet this bound with equality. The rest of this chapter applies this lower-bound to three special input-independent channels: erasure channel, super-symmetric Discrete Memoryless Channel (DMC), and q-ary symmetric DMC. It is proved that Maximum Distance Separable (MDS) codes achieve the minimum probability of error over any erasure channel (with or without memory). Chapter 4 addresses a fundamental trade-off between rate and diversity gain of an end-to-end connection in erasure networks. We prove that there exist general erasure networks for which any conventional routing strategy fails to achieve the optimum diversity-rate trade-off. However, for any general erasure graph, we show that there exists a linear network coding strategy which achieves the optimum diversity-rate trade-off. Unlike the previous works which suggest the potential benefit of linear network coding in the error-free multicast scenario (in terms of the achievable rate), our result demonstrates the benefit of linear network coding in the erasure single-source single-destination scenario (in terms of the diversity gain).

This thesis investigates channel-coded physical layer network coding, in which the relay directly transforms the noisy superimposed channel-coded packets received from the two end nodes, to the network-coded combination of the source packets. This is in contrast to the traditional multiple-access problem, in which the goal is to obtain each message explicitly at the relay. Here, the end nodes $A$ and $B$ choose their symbols, $S_A$ and $S_B$, from a small non-binary field, $\mathbb{F}$, and use non-binary PSK constellation mapper during the transmission phase. The relay then directly decodes the network-coded combination ${aS_A+bS_B}$ over $\mathbb{F}$ from the noisy superimposed channel-coded packets received from two end nodes. Trying to obtain $S_A$ and $S_B$ explicitly at the relay is overly ambitious when the relay only needs $aS_B+bS_B$. For the binary case, the only possible network-coded combination, ${S_A+S_B}$ over the binary field, does not offer the best performance in several channel conditions. The advantage of working over non-binary fields is that it offers the opportunity to decode according to multiple decoding coefficients $(a,b)$. As only one of the network-coded combinations needs to be successfully decoded, a key advantage is then a reduction in error probability by attempting to decode against all choices of decoding coefficients. In this thesis, we compare different constellation mappers and prove that not all of them have distinct performance in terms of frame error rate. Moreover, we derive a lower bound on the frame error rate performance of decoding the network-coded combinations at the relay. Simulation results show that if we adopt concatenated Reed-Solomon and convolutional coding or low density parity check codes at the two end nodes, our non-binary constellations can outperform the binary case significantly in the sense of minimizing the frame error rate and, in particular, the ternary constellation has the best frame error rate performance among all considered cases.

Dans le domaine des réseaux satellitaires, l'apparition de terminaux interactifs à bas-prix nécessite le développement et la mise en œuvre de protocoles d'accès multiple capables de supporter différents profils d'utilisateurs. En particulier, l'Agence Spatiale Européenne (ESA) et le centre d'étude spatial allemand (DLR) ont récemment proposé des protocoles d'accès aléatoires basés sur le codage réseau couche physique et l'élimination itérative des interférences pour résoudre en partie le problème de collisions sur une voie de retour du type Slotted ALOHA. C'est dans ce contexte que s'inscrit cette thèse qui vise à fournir une amélioration dans des méthodes d'accès aléatoires existantes. Nous introduisons Multi-Slot Coded Aloha (MuSCA) comme une nouvelle généralisation of CRDSA. Au lieu de transmettre des copies du même paquet, l'émetteur envoie plusieurs parties d'un mot de code d'un code correcteur d'erreurs ; chaque partie étant précédée d'un entête permettant de localiser les autres parties du mot de code. Au niveau du récepteur, toutes les parties envoyées par le même utilisateur, y compris celles qui sont interférées par d'autres signaux, participent au décodage. Le signal décodé est ensuite soustrait du signal total. Ainsi, l'interférence globale est réduite et les signaux restant ont plus de chances d'être décodés. Plusieurs méthodes d'analyse de performance basées sur des concepts théoriques (calcul de capacité, évolution des densités) et sur des simulations sont proposées. Les résultats obtenus montrent un gain très significatif de débit global comparé aux méthodes d'accès existantes. Ce gain peut encore être augmenté en variant le taux de découpe des mots de code. En modifiant certains de ces concepts, nous proposons également une application du codage réseau couche physique basée sur la superposition de modulations pour l'accès déterministe à la voie retour des communications par satellite. Une amélioration du débit est aussi obtenue par rapport à des stratégies plus classiques de multiplexage temporal. / In the domain of satellite networks, the emergence of low-cost interactive terminals motivates the need to develop and implement multiple access protocols able to support different user profiles. In particular, the European Space Agency (ESA) and the German Aerospace Center (DLR) have recently proposed random access protocols such as Contention Resolution Diversity Coded ALOHA (CRDSA) and Irregular Repetition Slotted ALOHA (IRSA). These methods are based on physical-layer network coding and successive interference cancellation in order to attempt to solve the collisions problem on a return channel of type Slotted ALOHA.This thesis aims to provide improvements of existing random access methods. We introduce Multi-Slot Coded Aloha (MuSCA) as a new generalization of CRDSA. Instead of transmitting copies of the same packet, the transmitter sends several parts of a codeword of an error-correcting code ; each part is preceded by a header allowing to locate the other parts of the codeword. At the receiver side, all parts transmitted by the same user, including those are interfered by other signals, are involved in the decoding. The decoded signal is then subtracted from the total signal. Thus, the overall interference is reduced and the remaining signals are more likely to be decoded. Several methods of performance analysis based on theoretical concepts (capacity computation, density evolution) and simulations are proposed. The results obtained show a significant gain in terms of throughput compared to existing access methods. This gain can be even more increased by varying the codewords stamping rate. Following these concepts, we also propose an application of physical-layer network coding based on the superposition modulation for a deterministic access on a return channel of satellite communications. We observe a gain in terms of throughput compared to more conventional strategies such as the time division multiplexing.

Orientador: Prof. Dr. Murilo Bellezoni Loiola / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Engenharia da Informação, 2017.