Network Coding for Engineers
Description
Understand the fundamentals of network coding from an engineering perspective with this accessible guide
Network Coding is a method of increasing network throughput and efficiency by encoding and decoding transmitted data packets instead of simply forwarding them. It was mainly a body of information theory until the rise of random linear networking coding (RLNC), a method ideally suited to wireless networks and other cooperative environments. The ease of introducing network coding to legacy systems and the resulting gains in efficiency have made this a widely applied technology with the potential to revolutionize networked communications.
Network Coding for Engineers introduces the fundamentals of this exciting subject from an engineering perspective. Beginning with the basics, including step-by-step details for implementing network coding and current applications, it also highlights potential uses of network coding in the communications technologies of the future. The result is an innovative and accessible introduction to a subject quickly becoming indispensable.
Network Coding for Engineers readers will also find:
- A structure that facilitates gradual deepening of knowledge, ideal for students and new readers
- Follows a semester-long course curriculum structure, making it suitable for direct adaptation for academic purposes
- Detailed discussion of future applications in technology areas including post-quantum cryptography, 6G, and more
- Design principles for different network models, such as multi-path and mesh networks
Network Coding for Engineers is ideal for electrical engineering and computer science students, particularly those studying advanced networking and communications and related subjects.
More details
Other editions
Additional editions
Persons
Muriel Médard, PhD, is NEC Professor of Software Science and Engineering in the Electrical Engineering and Computer Science (EECS) Department and Head of the Network Coding and Reliable Communications Group in the Research Laboratory of Electronics at the Massachusetts Institute of Technology (MIT), USA. She is a member of the US National Academy of Engineering and a Fellow of the US National Academy of Inventors and the Institute of Electrical and Electronics Engineers, among other organizations, and is a past president of the IEEE Information Theory Society.
Vipindev Adat Vasudevan, PhD, is a Postdoctoral Associate in the Network Coding and Reliable Communications Group in the Research Laboratory of Electronics, Massachusetts Institute of Technology (MIT), USA. He has previously worked as an MSCA Fellow in the Wireless Telecommunications Laboratory of the University of Patras, Greece, and has researched extensively into network coding, network security, 5G, and related subjects.
Morten Videbæk Pedersen, PhD, is co-founder and Chief Technology Officer of Steinwurf APS, a company specializing in industrial-grade high-performance content distribution systems, where he focuses on low-complexity network coding algorithms and cooperative networking programs. He is a member of the Mobile Devices Research Group, Aalborg, Denmark, and a past recipient of the Forum Nokia Developer Champion Award.
Ken R. Duffy, PhD, is a Professor of Electrical and Computer Engineering, and a Professor of Mathematics, at Northeastern University (NU), USA. He leads the Engineering Probability Information and Communications Laboratory and is core faculty at NU's Institute for the Wireless Internet of Things. He was previously the Director of the Hamilton Institute at the National University of Ireland, Maynooth, and a co-director of the Science Foundation Ireland Centre for Research Training in Foundations of Data Science.
Content
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
