Fulcrum: Versatile Network Codes for Heterogeneous Communication Networks

Two main approaches to achieve reliable data transfer over error-prone networks are retransmission and Forward Error Correction (FEC). Retransmission techniques retransmit packets when they are lost or despaired, causing significant delays, especially on multihop connections. On the contrary, to reduce latency FEC sends redundant data together with the original one. In particular, FEC through Random Linear Network Coding (RLNC) reduces the number of distinct packet transmissions in a network and minimizes packet transmissions due to poor network conditions. Consequently, RLNC has the potential to both improve energy efficiency and reduce the overall latency in a network. Fulcrum network coding (FNC), proposed as an RLNC's variation, has partly solved the challenge of heterogeneous communication networks by providing two-layer coding, enabling the destinations to decode packets based on their computing capabilities. However, coding parameters are statically chosen before data transmission, while using feedback or retransmission is impractical in rapidly changing network conditions. FNC is unadaptable to the available capabilities of nodes in a network and thus negatively impacts the coding performance. The main objective of this thesis is to design a versatile network coding scheme supporting heterogeneous communication networks that allow a node to adjust and adapt the coding process depending on the network condition and computing capabilities of the node. The research also focuses on reducing computational complexity in nodes while maintaining a high successful decoding probability and employing as simple operations as possible in intermediate nodes. Particularly, three main approaches are investigated in a source, intermediate, and destination node to achieve the objectives. First, the research examines both static and dynamic combinations of original packets in the encoding process by proposing dynamic sparsity and expansion packets (DSEP). This scheme significantly increases the coding throughput at both source and destination. Second, a new recoding scheme is proposed to manage the number of packets stored and recoded. Thus, this recoding scheme reduces memory usage and computing complexity at intermediate nodes, processing huge traffic. Finally, the research proposes adaptive decoding algorithms, which allow the destinations to choose the proper decoder depending on the network conditions. These algorithms improve the decoding probability in an unreliable network while reducing the computational complexity in a reliable network. For each proposed approach, both mathematical analysis and practical implementation were performed. Especially, the implementation leverages Kodo, a well-known network coding library for simulation and real-time implementation using during the last decade.:Abstract Acknowledgements List of Tables List of Figures Abbreviations and Symbols 1 Introduction 1.1 Fundamentals 1.2 Research motivation 1.3 Objectives 1.4 Methodology 1.5 Main contributions 1.5.1 Summary 1.5.2 List of publications 1.6 Thesis organization 2 Background and Related Work 2.1 RLNC and its variations 2.2 FNC: General principles and coding specification 2.2.1 General principles 2.2.2 Encoding specification 2.2.3 Decoding specification 2.3 Related work 2.4 Analysis of FNC performance 2.4.1 Preliminaries: MDS outer code property for theoretical analysis 2.4.2 Delay modelling: Number of required packet receptions for decoding 2.4.3 Decoding probability 2.4.4 Decoding probability for broadcast to heterogeneous destinations 2.4.5 Overhead 2.4.6 Throughput 2.5 Summary and discussion 3 Sparse Fulcrum Network Coding 3.1 Introduction 3.2 Encoding and decoding implementations 3.2.1 Encoding implementation 3.2.2 Decoding implementation 3.3 Integrating sparsity into FNC 3.3.1 Sparse inner and outer encoding 3.3.2 Sparse recoding and decoding 3.3.3 Evaluation setup 3.3.4 Throughput results 3.3.5 Decoding probability results 3.4 Summary 4 DSEP Fulcrum: Dynamic Expansion Packets and Sparsity 4.1 Introduction 4.2 Probability of linearly independent coded packets 4.3 Dynamic sparsity and expansion packets 4.3.1 Dynamic sparsity 4.3.2 Dynamic expansion packets 4.3.3 Sparsity level as a function of number of expansion packets and decoder rank 4.4 DSEP schemes 4.4.1 Example scheme: Dynamic sparsity with expansion packets region-based 4.4.2 Example scheme: Dynamic sparsity with expansion packets stepping up 4.5 Evaluation of DSEP schemes 4.5.1 Throughput results 4.5.2 Decoding probability results 4.5.3 Impact of feedback and packet losses 4.5.4 Energy consumption in IoT devices 4.6 Summary 5 Exploring Benefits of Recoding 5.1 Introduction 5.2 Recoding principle 5.3 Recoding scheme 5.3.1 General idea 5.3.2 An unlimited buffer recoding 5.3.3 A limited buffer recoding 5.4 Evaluation 5.4.1 Coding overhead 5.4.2 Recoding and decodinEvaluation.5 Summary 6 Adaptive Decoding for Fulcrum Codes 6.1 Introduction 6.2 Adaptive Fulcrum decoder 6.2.1 Motivating example 6.2.2 Adaptive Fulcrum decoding algorithm 6.3. Advanced adaptive Fulcrum decoder 6.3.1 Principles 6.3.2 Advanced adaptive Fulcrum decoding algorithm 6.4 Analysis 6.4.1 Decoding delay 6.4.2 Decoding probability 6.4.3 Overhead 6.5 Evaluation of adaptive Fulcrum decoding algorithms 6.5.1 Performance metrics 6.5.2 Evaluation results 6.6 Summary 7 Conclusion and Future Work 7.1 Summary and main contributions 7.2 Future work A Reed-Solomon Outer Code: Proof of Full Rank Property of Remapped Packets Bibliograph