Network Coding for Engineers

List of Figures xiii List of Tables xvii About The Authors xix Preface xxiii Acknowledgments xxv Acronyms xxvii 1 Introduction 1 1.1 Vision and Outline 2 1.2 Coding 5 1.3 Data as Mutable – A Relaxation 6 1.3.1 Immutable Data 7 1.3.2 Mutable Data 8 1.4 Network Coding – Data as Equations 9 1.5 Use Cases and Examples 9 1.5.1 Addressing Bottlenecks 10 1.5.2 Addressing Packet Drops in a Point-to-Point Communication 11 1.5.3 Multiple Receivers – Reliable Broadcast 14 1.5.4 Recoding and Multi-hop Networks 15 1.5.5 Distributed Storage – Incast 16 1.5.6 Security 16 1.6 A Toolbox for Implementing Network Coding 17 1.6.1 Tool 1: The Python Programming Language 17 1.6.2 Getting Python (Step-by-Step)* 18 1.6.3 Tool 2: PyErasure – Erasure Correcting Algorithms in Python 19 1.7 Summary 22 Additional Reading Materials 22 References 22 2 Finite Field Arithmetic for Network Coding 25 2.1 (Not So) Brute Force Determination of Inverses 27 2.2 Division in the Integers and Greatest Common Divisors 28 2.3 Division with Modulo in the Integers – Why Primes 32 2.3.1 Existence of Multiplicative Inverses** 34 2.4 Prime Fields 37 2.5 Mathematical Aside: Beyond Linear Equations** 38 2.6 Extension Fields 40 2.6.1 Suitability for Binary Data 41 2.6.2 Basics of Extension Fields 43 2.6.3 Binary Extension Field 44 2.7 Polynomial Multiplication/Division 46 2.7.1 Binary Extension Field Multiplication 46 2.7.2 Binary Extension Field Division 48 2.8 Primitive Polynomials 48 2.9 Polynomials in Delay – Data Streams 50 2.10 Solutions 52 2.11 Summary 52 Additional Reading Materials 53 References 53 3 Finite Field Implementations for Network Coding* 55 3.1 Binary Field Implementations 57 3.2 Binary Extension Field Implementations 58 3.2.1 Runtime Addition and Subtraction 59 3.2.2 Runtime Multiplication and Division 59 3.2.3 Runtime Division Algorithm 63 3.2.4 Full Multiplication Table 66 3.2.5 Log and AntiLog Table 68 3.2.6 Extended Log and AntiLog Table 71 3.3 Extended Euclidean Algorithm** 76 3.3.1 Find Degree Function 82 3.4 Summary 83 Additional Reading Materials 83 References 83 4 Coding for Erasures 85 4.1 From Chunks to Packets 86 4.2 Erasure Resilience 89 4.3 Gauss–Jordan Elimination 89 4.4 Code Construction 92 4.4.1 Proportion of Non-invertible Matrices 92 4.4.2 Non-RLNC Erasure Codes 94 4.4.3 Simple Scenario to Evaluate Potential Gain 94 4.5 Innovative Packet and Acknowledgment 96 4.5.1 Innovative Packet 96 4.5.2 Role of Acknowledgments 98 4.6 Network Coding for Losses 100 4.6.1 Coding Until Completion 102 4.6.2 Coding Until Completion – Sliding Window 104 4.6.3 Semi-systematic Code with Feedback 107 4.7 Queueing and Network Coding 109 4.7.1 Managing Queue Size at the Sender 109 4.7.2 Feedback for Network Coding and Its Implications 109 4.7.3 A Quick Primer on Queueing Theory 111 4.7.4 The Magic of Independent Exponentials 114 4.7.5 Relating Average Queue Length to Average Waiting Time 117 4.7.6 Drop When Seen 119 4.7.7 Drop When Decoded 119 4.8 Summary 122 Additional Reading Materials 122 References 122 5 Designing of Protocols with Network Coding 125 5.1 TCP Variants 128 5.2 Logical Description of TCP/NC 129 5.3 Seen Packets and Congestion Control 130 5.4 Mechanisms of Use of Seen Packets 131 5.4.1 Source Side 134 5.4.2 Receiver Side 134 5.4.3 Soundness of the Protocol 135 5.5 Queueing Analysis for an Idealized Case of TCP/NC 136 5.5.1 System Model 136 5.5.2 Queue Update Mechanism 137 5.5.3 Queueing Analysis 138 5.6 Performance Analysis 141 5.6.1 A Model for Congestion Control 142 5.6.2 Intuition 144 5.6.3 Throughput Analysis for TCP* 145 5.6.4 Throughput Analysis for TCP/NC 148 5.6.5 TCP/NC Average Throughput 151 5.7 Summary 152 Additional Reading Materials 152 References 153 6 Implementation of Network Coding Protocols 155 6.1 A Real-World Implementation of TCP/NC 155 6.1.1 Sender-Side Module 155 6.1.2 Receiver-Side Module 160 6.1.3 Discussion of Implementation Parameters 162 6.1.4 Recoding Process 168 6.1.5 Feedback Mechanism 168 6.1.6 Implementation Strategies 169 6.2 Adaptive Sliding Window 172 6.2.1 Adaptive Coding Algorithm 173 6.3 Network Coding and QUIC 181 6.3.1 Flexible Erasure Correction (FlEC) 183 6.3.2 Bulk File Transfers 186 6.3.3 Buffer-limited File Transfers 187 6.3.4 Delay-constrained Messaging 189 6.4 Summary 193 Additional Reading Materials 194 References 194 7 Network as a Matrix 197 7.1 Mathematical Model 197 7.2 Routing 198 7.3 Algebraic Network Coding 199 7.3.1 Formulation 199 7.3.2 The Network as a Matrix 203 7.3.3 Multicast 207 7.3.4 Multiple Sources and Multiple Sinks** 209 7.4 Erasures 214 7.5 An Aside on Misapplication 215 7.6 Summary 216 Additional Reading Materials 217 References 217 8 Security and Network Coding 219 8.1 Information Theoretic Security – Quick Primer 220 8.2 Data Hiding 224 8.2.1 Hiding Equations 224 8.2.2 Hiding Coefficients 227 8.3 Pollution Attacks 228 8.3.1 Detection of Pollution After Decoding 228 8.3.2 Detection of Pollution Without Decoding** 230 8.4 Summary 232 Additional Reading Materials 232 References 232 Concluding Remarks 235 Appendix Sample List of Patents 237 Index 241