Network Coding is a technique which looks beyond traditional store-and-forward approach followed by routers and switches in communication networks, and as an extension introduces maps termed as ‘local encoding kernels’ and ‘global encoding kernels’ defined for each communication link in the network. The purpose of both these maps is to define rules as to how to combine the packets input on the node to form a packet going out on an edge. The paradigm of network coding was formally and for the first time introduced by Ahlswede et al. in [1], where they also demonstrated its use in case of single-source multiple-sink network multicast, although with use of much complex mathematical apparatus. In [1], examples of networks are also presented where it is shown that network coding can improve the overall throughput of the network which can not otherwise be realized by the conventional store-and-forward approach. The main result in [1], i.e. the capacity of single-source multiple-sinks information network is nothing but the minimum of the max-flows from source to each sink, was again proved by Li, Yeung, and Cai in [2] where they showed that only linear operations suffice to achieve the capacity of multicast network. The authors in [2] defined generalizations to the multicast problem, which they termed as linear broadcast, linear dispersion, and Generic LCM as strict generalizations of linear multicast, and showed how to build linear network codes for each of these cases. For the case of linear multicast, Koetter and Medard in [3] developed an algebraic framework using tools from algebraic geometry which also proved the multicast max-flow min-cut theorem proved in [1] and [2]. It was shown that if the size of the finite field is bigger than a certain threshold, then there always exists a solution to the linear multicast, provided it is solvable. In other words, a solvable linear multicast always has a solution in any finite field whose cardinality is greater than the threshold value. The framework in [3] also dealt with the general linear network coding problem involving multiple sources and multiple sinks with non-uniform demand functions at the sinks, but did not touched upon the key problem of finding the characteristic(s) of the field in which it may have solution. It was noted in [5] that a solvable network may not have a linear solution at all, and then introduced the notion of general linear network coding, where the authors conjectured that every solvable network must have a general linear solution. This was refuted by Dougherty, Freiling, Zeger in [6], where the authors explicitly constructed example of a solvable network which has no general linear solution, and also networks which have solution in a finite field of char 2, and not in any other finite field. But an algorithm to find the characteristic of the field in which a scalar or general linear solution(if at all) exists did not find any mention in [3] or [6]. It was a simultaneous discovery by us(as part of this thesis) as well as by Dougherty, Freiling, Zeger in [7] to determine the characteristics algorithmically. Applications of Network Coding techniques to wireless networks are seen in literature( [8], [9], [10]), where [8] provided a variant of max-flow min-cut theorem for wireless networks in the form of linear programming constraints. A new architecture termed as COPE was introduced in [10] which used opportunistic listening and opportunistic coding in wireless mesh networks.

The aim of this thesis is to conduct performance investigation of a combined system of Network Coding (NC) technique with Ant-Colony (ACO) routing protocol. This research analyses the impact of several workload characteristics, on system performance. Network coding is a significant key development of information transmission and processing. Network coding enhances the performance of multicast by employing encoding operations at intermediate nodes. Two steps should realize while using network coding in multicast communication: determining appropriate transmission paths from source to multi-receivers and using the suitable coding scheme. Intermediate nodes would combine several packets and relay them as a single packet. Although network coding can make a network achieve the maximum multicast rate, it always brings additional overheads. It is necessary to minimize unneeded overhead by using an optimization technique. On other hand, Ant Colony Optimization can be transformed into useful technique that seeks imitate the ant’s behaviour in finding the shortest path to its destination using quantities of pheromone that is left by former ants as guidance, so by using the same concept of the communication network environment, shorter paths can be formulated. The simulation results show that the resultant system considerably improves the performance of the network, by combining Ant Colony Optimization with network coding. 25% improvement in the bandwidth consumption can be achieved in comparison with conventional routing protocols. Additionally simulation results indicate that the proposed algorithm can decrease the computation time of system by a factor of 20%.

Random linear network coding is widely proposed as the solution for practical network coding applications due to the robustness to random packet loss, packet delays as well as network topology and capacity changes. In order to implement random linear network coding in practical scenarios where the encoding and decoding methods perform efficiently, the computational complex coding algorithms associated with random linear network coding must be overcome. This research contributes to the field of practical random linear network coding by presenting new, low complexity coding algorithms with low decoding delay. In this thesis we contribute to this research field by building on the current solutions available in the literature through the utilisation of familiar coding schemes combined with methods from other research areas, as well as developing innovative coding methods. We show that by transmitting source symbols in predetermined and constrained patterns from the source node, the causality of the random linear network coding network can be used to create structure at the receiver nodes. This structure enables us to introduce an innovative decoding scheme of low decoding delay. This decoding method also proves to be resilient to the effects of packet loss on the structure of the received packets. This decoding method shows a low decoding delay and resilience to packet erasures, that makes it an attractive option for use in multimedia multicasting. We show that fountain codes can be implemented in RLNC networks without changing the complete coding structure of RLNC networks. By implementing an adapted encoding algorithm at strategic intermediate nodes in the network, the receiver nodes can obtain encoded packets that approximate the degree distribution of encoded packets required for successful belief propagation decoding. Previous work done showed that the redundant packets generated by RLNC networks can be used for error detection at the receiver nodes. This error detection method can be implemented without implementing an outer code; thus, it does not require any additional network resources. We analyse this method and show that this method is only effective for single error detection, not correction. In this thesis the current body of knowledge and technology in practical random linear network coding is extended through the contribution of effective decoding techniques in practical network coding networks. We present both analytical and simulation results to show that the developed techniques can render low complexity coding algorithms with low decoding delay in RLNC networks. / Thesis (PhD (Computer Engineering))--North-West University, Potchefstroom Campus, 2013

Random linear network coding is widely proposed as the solution for practical network coding applications due to the robustness to random packet loss, packet delays as well as network topology and capacity changes. In order to implement random linear network coding in practical scenarios where the encoding and decoding methods perform efficiently, the computational complex coding algorithms associated with random linear network coding must be overcome. This research contributes to the field of practical random linear network coding by presenting new, low complexity coding algorithms with low decoding delay. In this thesis we contribute to this research field by building on the current solutions available in the literature through the utilisation of familiar coding schemes combined with methods from other research areas, as well as developing innovative coding methods. We show that by transmitting source symbols in predetermined and constrained patterns from the source node, the causality of the random linear network coding network can be used to create structure at the receiver nodes. This structure enables us to introduce an innovative decoding scheme of low decoding delay. This decoding method also proves to be resilient to the effects of packet loss on the structure of the received packets. This decoding method shows a low decoding delay and resilience to packet erasures, that makes it an attractive option for use in multimedia multicasting. We show that fountain codes can be implemented in RLNC networks without changing the complete coding structure of RLNC networks. By implementing an adapted encoding algorithm at strategic intermediate nodes in the network, the receiver nodes can obtain encoded packets that approximate the degree distribution of encoded packets required for successful belief propagation decoding. Previous work done showed that the redundant packets generated by RLNC networks can be used for error detection at the receiver nodes. This error detection method can be implemented without implementing an outer code; thus, it does not require any additional network resources. We analyse this method and show that this method is only effective for single error detection, not correction. In this thesis the current body of knowledge and technology in practical random linear network coding is extended through the contribution of effective decoding techniques in practical network coding networks. We present both analytical and simulation results to show that the developed techniques can render low complexity coding algorithms with low decoding delay in RLNC networks. / Thesis (PhD (Computer Engineering))--North-West University, Potchefstroom Campus, 2013

No description available.

No / Abstract: Error control techniques are designed to ensure reliable data transfer over unreliable communication channels that are frequently subjected to channel errors. In this paper, the effect of applying a convolution code to the Scattered Random Network Coding (SRNC) scheme over a multi-hop wireless channel was studied. An interleaver was implemented for bit scattering in the SRNC with the purpose of dividing the encoded data into protected blocks and vulnerable blocks to achieve error diversity in one modulation symbol while randomising errored bits in both blocks. By combining the interleaver with the convolution encoder, the network decoder in the receiver would have enough number of correctly received network coded blocks to perform the decoding process efficiently. Extensive simulations were carried out to study the performance of three systems: 1) SRNC with convolutional encoding, 2) SRNC; and 3) A system without convolutional encoding nor interleaving. Simulation results in terms of block error rate for a 2-hop wireless transmission scenario over an Additive White Gaussian Noise (AWGN) channel were presented. Results showed that the system with interleaving and convolutional code achieved better performance with coding gain of at least 1.29 dB and 2.08 dB on average when the block error rate is 0.01 when compared with system II and system III respectively.

The development of Unmanned Aerial Vehicles (UAVs) and fifth-generation (5G) wireless technology provides more possibilities for wireless networks. The application of UAVs is gradually evolving from individual UAVs performing tasks to UAV swarm performing tasks in concert. A UAV swarm network is when many drones work cooperatively in a swarm mode to achieve a particular goal. Due to the UAV swarm's easy deployment, self-organization, self-management, and high flexibility, it can provide robust and efficient wireless communications in some unique scenarios, such as emergency communications, hotspot region coverage, sensor networks, and vehicular networks. Therefore, UAV networks have attracted more and more attention from commercial and military; however, many problems need to be resolved before UAV cellular communications become a reality. One of the most challenging core components is the routing protocol design in the UAV swarm network. Due to the high mobility of UAVs, the position of each UAV changes dynamically, so problems such as high latency, high packet loss rate, and even loss of connection arise when UAVs are far apart. These problems dramatically reduce the transmission rate and data integrity for traditional routing protocols based on path discovery. This thesis focuses on developing, emulating, and optimizing a flooding-based routing protocol for UAV swarm using Random Linear Network Coding (RLNC) to improve the latency and bit rate and solve the packet loss problem without routing information and network topology. RLNC can reduce the number of packets demand in some hops. Due to this feature of RLNC, when relay transmitter UAVs or the destination receiver UAV receive sufficient encoded packets from any transmitter UAVs, the raw data can be decoded. For those relay transmitter UAVs in the UAV swarm network that already received some encoded packets in previous hops but not enough to decode the raw data, only need to receive the rest of the different encoded packets needed for decoding. Thus, flooding-based routing protocol significantly improves transmission efficiency in the UAV swarm network. / Master of Science / People are used to using fiber, 4G, and Wi-Fi in the city, but numerous people still live in areas without Internet access. Moreover, in some particular scenarios like large-scale activities, remote areas, and military operations, when the cellular network cannot provide enough bandwidth or good signal, UAV wireless network would be helpful and provide stable Internet access. Successful UAV test flights can last for several weeks, and researchers' interest in high-altitude long-endurance (HALE) UAVs are booming. HALE UAVs will create Wi-Fi or other network signals for remote areas, including polar regions, which will allow millions of people to enter the information society and connect to the Internet. The development of UAV and 5G provides more possibilities for wireless networks. UAV applications have evolved from individual UAV performing tasks to UAV swarm performing tasks. A UAV swarm network is where multiple drones work in tandem to achieve a particular goal. It can provide robust and efficient wireless communications in unique scenarios. As a result, UAVs are receiving attention from both commercial and military. However, there are still many problems that need to be resolved before the actual use of UAVs. One of the biggest challenges is routing protocol which is how UAVs communicate with each other and select routes. As the location of UAVs is constantly changing, this leads to delays, data loss, or complete loss of connectivity. Ultimately these issues can lead to slow transmission speed and lack of data integrity for traditional routing protocols based on path discovery. This thesis focuses on developing, emulating, and optimizing a flooding-based routing protocol for the UAV swarm. Specifically, this protocol uses RLNC, which can reduce the number of packets demand in some hops so that the latency and transmission speed will be improved, and the data loss problem will also be solved. Due to this feature of RLNC, when any receiver receives enough encoded packets from any transmitter, the original data can be decoded. Some receivers that already received some encoded packets in the previous transmission only need to receive the rest of the different encoded packets needed for decoding. Therefore, flooding-based routing protocol significantly improves transmission efficiency for UAV swarm networks.

Mobile Ad hoc NETworks (MANETs) aim at making communication between mobile nodes feasible without any infrastructure support. Sparse MANETs fall into the class of Delay Tolerant Networks which are intermittently connected networks and where there is no contemporaneous end-to-end path at any given time. We first, propose a new reliable transport scheme for DTNs based on the use of ACKnowledgments and random linear coding. We model the evolution of the network under our scheme using a fluid-limit approach. We optimize our scheme to obtain mean file transfer times on certain optimal parameters obtained through differential evolution approach. Secondly, we propose and study a novel and enhanced ACK to improve reliable transport for DTNs covering both unicast and multicast flows. We make use of random linear coding at relays so that packets can reach the destination faster. We obtain reliability based on the use of so-called Global Selective ACKnowledgment. We obtain significant improvement through G-SACKs and coding at relays. Finally, we tackle the problem of estimating file-spread in DTNs with direct delivery and epidemic routing. We estimate and track the degree of spread of a message in the network. We provide analytical basis to our estimation framework alongwith insights validated with simulations. We observe that the deterministic fluid model can indeed be a good predictor with a large of nodes. Moreover, we use Kalman filter and Minimum- Mean-Squared-Error (MMSE) to track the spreading process and find that Kalman filter provides more accurate results as compared to MMSE

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).

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.