118,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
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.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 393
Veröffentlichungsjahr: 2025
Ähnliche
Table of Contents
Cover
Table of Contents
Title Page
Copyright
Dedication
List of Figures
List of Tables
About the Authors
Preface
Acknowledgments
Acronyms
1 Introduction
1.1 Vision and Outline
1.2 Coding
1.3 Data as Mutable – A Relaxation
1.4 Network Coding – Data as Equations
1.5 Use Cases and Examples
1.6 A Toolbox for Implementing Network Coding
1.7 Summary
Additional Reading Materials
References
2 Finite Field Arithmetic for Network Coding
2.1 (Not So) Brute Force Determination of Inverses
2.2 Division in the Integers and Greatest Common Divisors
2.3 Division with Modulo in the Integers – Why Primes
2.4 Prime Fields
2.5 Mathematical Aside: Beyond Linear Equations**
2.6 Extension Fields
2.7 Polynomial Multiplication/Division
2.8 Primitive Polynomials
2.9 Polynomials in Delay – Data Streams
2.10 Solutions
2.11 Summary
Additional Reading Materials
References
3 Finite Field Implementations for Network Coding*
3.1 Binary Field Implementations
3.2 Binary Extension Field Implementations
3.3 Extended Euclidean Algorithm**
3.4 Summary
Additional Reading Materials
References
Note
4 Coding for Erasures
4.1 From Chunks to Packets
4.2 Erasure Resilience
4.3 Gauss–Jordan Elimination
4.4 Code Construction
4.5 Innovative Packet and Acknowledgment
4.6 Network Coding for Losses
4.7 Queueing and Network Coding
4.8 Summary
Additional Reading Materials
References
5 Designing of Protocols with Network Coding
5.1 TCP Variants
5.2 Logical Description of TCP/NC
5.3 Seen Packets and Congestion Control
5.4 Mechanisms of Use of Seen Packets
5.5 Queueing Analysis for an Idealized Case of TCP/NC
5.6 Performance Analysis
5.7 Summary
Additional Reading Materials
References
Notes
6 Implementation of Network Coding Protocols
6.1 A Real‐World Implementation of TCP/NC
6.2 Adaptive Sliding Window
6.3 Network Coding and QUIC
6.4 Summary
Additional Reading Materials
References
7 Network as a Matrix
7.1 Mathematical Model
7.2 Routing
7.3 Algebraic Network Coding
7.4 Erasures
7.5 An Aside on Misapplication
7.6 Summary
Additional Reading Materials
References
8 Security and Network Coding
8.1 Information Theoretic Security – Quick Primer
8.2 Data Hiding
8.3 Pollution Attacks
8.4 Summary
Additional Reading Materials
References
Concluding Remarks
Appendix Sample List of Patents
Index
End User License Agreement
List of Tables
Chapter 2
Table 2.1 The finite field consists of elements 0 and 1, which satisfy the...
Table 2.2 Example mapping between polynomial and binary representation for a...
Table 2.3 Field elements of the Galois field in polynomial and binary repr...
Chapter 3
Table 3.1 Different representations of the elements of the finite field .
Table 3.2 Logarithmic tables for the finite field .
Table 3.3 Extended AntiLog tables for the finite field .
Chapter 4
Table 4.1 An example of the drop‐when‐seen algorithm.
Chapter 6
Table 6.1 AC‐RLNC algorithm: symbol definition.
Table 6.2 Definition of and for the considered use cases.
List of Illustrations
Chapter 1
Figure 1.1 The introduction of network coding has created a new area within ...
Figure 1.2 Traditional view of data as immutable. This figure is inspired by...
Figure 1.3 Coding view of data as being manipulable. This figure is inspired...
Figure 1.4 Butterfly example. This figure is inspired from the work of Ahlsw...
Figure 1.5 TCP/IP. Left image is inspired from one by Brad Karp.
Chapter 3
Figure 3.1 Finite fields commonly used in network coding implementations.
Chapter 4
Figure 4.1 Mechanism for coding together packets. This figure is inspired by...
Figure 4.2 To encode bits in a prime field, one needs to represent them in...
Figure 4.3 Likelihood that a randomly chosen matrix in a prime‐ field is ...
Figure 4.4 For a binary extension field, the likelihood that a randomly chos...
Figure 4.5 Representation of ARQ. Source: This figure is inspired by joint w...
Figure 4.6 A broadcast channel with erasures. This figure is inspired by joi...
Figure 4.7 Coding versus not coding for three packets over a binary field. T...
Figure 4.8 Representation of coding until completion. With a delay of on e...
Figure 4.9 Representation of different scenarios of sliding window coding wi...
Figure 4.10 Representation of a sliding window with no delay in feedback and...
Figure 4.11 Representation of systematic coding with feedback with a delay o...
Figure 4.12 Decoded, seen, and unseen packets. This figure is inspired by jo...
Figure 4.13 Simulation of queue‐length evolution of the sender for
drop‐when
...
Figure 4.14 Average queue length (i.e. number of packets waiting) in an M/M/...
Figure 4.15 Arrivals, departures, and number in the system. Source: This fig...
Figure 4.16 Relating arrivals, departures, number in the system and time in ...
Figure 4.17 Average queue length as a function of load, .
Figure 4.18 Average waiting time, given , as a function of load, .
Chapter 5
Figure 5.1 Example of TCP, coding, and ACKs. Source: This figure is inspired...
Figure 5.2 New network coding layer in the protocol stack. This figure is in...
Figure 5.3 Topology: Daisy chain with perfect end‐to‐end feedback.
Figure 5.4 The effect of erasures: TCP experiences triple‐duplicate ACKs, an...
Figure 5.5 TCP's window size with a TD event and a TO event. In round , los...
Figure 5.6 TCP/NC's window size with erasures that would lead to a triple‐du...
Figure 5.7 Expected window size for TCP/NC where , . We usually assume ; ...
Chapter 6
Figure 6.1 The coding buffer. This figure is inspired by joint work with Jay...
Figure 6.2 The network coding header. This figure is inspired by joint work ...
Figure 6.3 Receiver‐side window management. This figure is inspired by joint...
Figure 6.4 Sliding window network coding – with and without recoder.
Figure 6.5 An example case of a 2‐hop network with SWNC. The packets lost in...
Figure 6.6 System model and encoding process of the coded RLNC combination. ...
Figure 6.7 The rows and columns of the coding matrix denote the time slot ...
Figure 6.8 Design of the solution: a general framework with two pluggable an...
Chapter 7
Figure 7.1 (a) A P2P connection in a simple network; (b) the same network wi...
Figure 7.2 The directed labeled line graph corresponding to the network de...
Figure 7.3 (a) A network with two source and two sink nodes. (b) The corresp...
Figure 7.4 A representation of the multicast problem for a general network w...
Figure 7.5 A representation of the multi‐source multicast problem for a gene...
Figure 7.6 (a) A network with two sources and two sink nodes. (b) The corres...
Chapter 8
Figure 8.1 Benign RLNC scenario.
Figure 8.2 Malicious scenario showing the spread of a polluted packet.
Guide
Cover
Table of Contents
Title Page
Copyright
Dedication
List of Figures
List of Tables
About the Authors
Preface
Acknowledgments
Acronyms
Begin Reading
Concluding Remarks
Appendix Sample List of Patents
Index
End User License Agreement
Pages
ii
iii
iv
v
xiii
xiv
xv
xvi
xvii
xix
xx
xxi
xxii
xxiii
xxv
xxvi
xxvii
xxviii
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
235
237
238
239
240
241
242
243
244
245
IEEE Press445 Hoes LanePiscataway, NJ 08854
IEEE Press Editorial BoardSarah Spurgeon, Editor-in-Chief
Moeness Amin
Jón Atli Benediktsson
Adam Drobot
James Duncan
Ekram Hossain
Brian Johnson
Hai Li
James Lyke
Joydeep Mitra
Desineni Subbaram Naidu
Tony Q. S. Quek
Behzad Razavi
Thomas Robertazzi
Diomidis Spinellis
Network Coding for Engineers
Muriel MédardMassachusetts Institute of Technologyand OptimumUnited States.
Vipindev Adat VasudevanMassachusetts Institute of TechnologyUnited States
Morten Videbæk PedersenSteinwurf APSDenmark
Ken R. DuffyNortheastern UniversityUSA
Copyright © 2025 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
Published by John Wiley & Sons, Inc., Hoboken, New Jersey.Published simultaneously in Canada.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per‐copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750‐8400, fax (978) 750‐4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748‐6011, fax (201) 748‐6008, or online at http://www.wiley.com/go/permission.
The manufacturer's authorized representative according to the EU General Product Safety Regulation is Wiley‐VCH GmbH, Boschstr. 12, 69469 Weinheim, Germany, e‐mail: [email protected].
Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates in the United States and other countries and may not be used without written permission. All other trademarks are the property of their respective owners. John Wiley & Sons, Inc. is not associated with any product or vendor mentioned in thisbook.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762‐2974, outside the United States at (317) 572‐3993 or fax (317) 572‐4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging‐in‐Publication Data Applied for:
Hardback ISBN 9781394217274
Cover Design: WileyCover Image: Courtesy of Vivian Conner
In memory of Ralf Kötter and Nuala Bennett Kötter.
List of Figures
Figure 1.1 The introduction of network coding has created a new area within coding theory that focuses on enhancing the reliability and efficiency of the network.
Figure 1.2 Traditional view of data as immutable. This figure is inspired by joint work with Michelle Effros.
Figure 1.3 Coding view of data as being manipulable. This figure is inspired by joint work with Michelle Effros.
Figure 1.4 Butterfly example. This figure is inspired from the work of Ahlswede et al. [6].
Figure 1.5 TCP/IP. Left image is inspired from one by Brad Karp.
Figure 3.1 Finite fields commonly used in network coding implementations.
Figure 4.1 Mechanism for coding together packets. This figure is inspired by joint work with Daniel Lucani.
Figure 4.2 To encode bits in a prime field, one needs to represent them in bits. As implied by the Bertrand–Chebyshev Theorem, , some of the binary strings of length go unused. Plotted is that fraction, , for the largest prime smaller than .
Figure 4.3 Likelihood that a randomly chosen matrix in a prime‐ field is not invertible, along with the approximation .
Figure 4.4 For a binary extension field, the likelihood that a randomly chosen matrix is not invertible decays exponentially in the number of bits.
Figure 4.5 Representation of ARQ. Source: This figure is inspired by joint work with Jason Cloud.
Figure 4.6 A broadcast channel with erasures. This figure is inspired by joint work with Atilla Eryilmaz.
Figure 4.7 Coding versus not coding for three packets over a binary field. This figure is inspired by joint work with Atilla Eryilmaz.
Figure 4.8 Representation of coding until completion. With a delay of on each transmission, there is some overhead in the receiver telling the sender that a generation of packets has been decoded. This figure is inspired by joint work with Jason Cloud.
Figure 4.9 Representation of different scenarios of sliding window coding with a delay in feedback. (a) With a window size of six packets and feedback delay of four slots and (b)with a window size of four packets and feedback delay of four slots. This figure is inspired by joint work with Jason Cloud.
Figure 4.10 Representation of a sliding window with no delay in feedback and a maximum window size of 2.
Figure 4.11 Representation of systematic coding with feedback with a delay of on each transmission. This figure is inspired by joint work with Jason Cloud.
Figure 4.12 Decoded, seen, and unseen packets. This figure is inspired by joint work with Jay Kumar Sundararajan [7].
Figure 4.13 Simulation of queue‐length evolution of the sender for and within the mathematical model described in this section.
Figure 4.14 Average queue length (i.e. number of packets waiting) in an M/M/1 queue as a function of load, .
Figure 4.15 Arrivals, departures, and number in the system. Source: This figure is inspired by [10, Fig. 3.8].
Figure 4.16 Relating arrivals, departures, number in the system and time in the system. Source: This figure is inspired by [10, Fig. 3.8].
Figure 4.17 Average queue length as a function of load, .
Figure 4.18 Average waiting time, given , as a function of load, .
Figure 5.1 Example of TCP, coding, and ACKs. Source: This figure is inspired by joint work with MinJi Kim [1].
Figure 5.2 New network coding layer in the protocol stack. This figure is inspired by joint work with Jay Kumar Sundararajan [5].
Figure 5.3 Topology: Daisy chain with perfect end‐to‐end feedback.
Figure 5.4 The effect of erasures: TCP experiences triple‐duplicate ACKs, and results in . However, TCP/NC masks the erasures using network coding, which allows TCP to advance its window. This figure depicts the sender's perspective; therefore, it indicates the time at which the sender transmits the packet or receives the ACK. This figure is inspired by joint work with MinJi Kim [1] and by[8].
Figure 5.5 TCP's window size with a TD event and a TO event. In round , losses occur resulting in triple‐duplicate ACKs. On the other hand, in round , losses occur; however, in the following round losses occur such that the TCP sender only receives two‐duplicate ACKs. As a result, TCP experiences time‐out. This figure is taken from [1], inspired from [8].
Figure 5.6 TCP/NC's window size with erasures that would lead to a triple‐duplicate ACKs event when using standard TCP. Note that unlike TCP, the window size is non‐decreasing. This figure is inspired by joint work with MinJi Kim [1] and by[8].
Figure 5.7 Expected window size for TCP/NC where , . We usually assume ; here we use to exemplify the effect of . Source: This figure is by joint work with MinJi Kim[1].
Figure 6.1 The coding buffer. This figure is inspired by joint work with Jay Kumar Sundararajan [2].
Figure 6.2 The network coding header. This figure is inspired by joint work with Jay Kumar Sundararajan [2].
Figure 6.3 Receiver‐side window management. This figure is inspired by joint work with Jay Kumar Sundararajan [2].
Figure 6.4 Sliding window network coding – with and without recoder.
Figure 6.5 An example case of a 2‐hop network with SWNC. The packets lost in transmission are highlighted with boxes in channel columns.
Figure 6.6 System model and encoding process of the coded RLNC combination. The adaptive causal encoding process and the effective window size are detailed in Section 6.2.1. In this example, for simplicity of notation . This figure is inspired by joint work with Alejandro Cohen [6].
Figure 6.7 The rows and columns of the coding matrix denote the time slot and the information packet indices, respectively. At a given time slot, a coded packet, which is a random linear combination of packets , is transmitted. The lost packets are shown with crossed marks. The last column shows how the decision to send posterior repair packets is made. This figure is inspired by joint work with Alejandro Cohen [6].
Figure 6.8 Design of the solution: a general framework with two pluggable anchors to redefine the reliability mechanism given the use case. This is inspired from [14].
Figure 7.1 (a) A P2P connection in a simple network; (b) the same network with nodes representing the processes to be transmitted in the network. This figure is inspired by joint work with Ralf Kötter.
Figure 7.2 The directed labeled line graph corresponding to the network depicted in Fig. 7.1. This figure is inspired by joint work with Ralf Kötter.
Figure 7.3 (a) A network with two source and two sink nodes. (b) The corresponding labeled line graph; labels in (b) are omitted for clarity. The edge does not feed into any other edge and no edge feeds into , which renders an isolated vertex in the labeled line graph. This figure is inspired by joint work with Ralf Kötter.
Figure 7.4 A representation of the multicast problem for a general network with three sinks. Each submatrix color corresponds to a sink node.
Figure 7.5 A representation of the multi‐source multicast problem for a general network with three sinks. Each submatrix color corresponds to a sink node.
Figure 7.6 (a) A network with two sources and two sink nodes. (b) The corresponding labeled line graph. This figure is inspired by joint work with Ralf Kötter.
Figure 8.1 Benign RLNC scenario.
Figure 8.2 Malicious scenario showing the spread of a polluted packet.
List of Tables
Table 2.1 The finite field consists of elements 0 and 1, which satisfy the addition () and multiplication () tables.
Table 2.2 Example mapping between polynomial and binary representation for a polynomial in .
Table 2.3 Field elements of the Galois field in polynomial and binary representation.
Table 3.1 Different representations of the elements of the finite field .
Table 3.2 Logarithmic tables for the finite field .
Table 3.3 Extended AntiLog tables for the finite field .
Table 4.1 An example of the drop‐when‐seen algorithm.
Table 6.1 AC‐RLNC algorithm: symbol definition.
Table 6.2 Definition of and for the considered use cases.
About the Authors
Muriel Médard
Muriel Médard is the NEC Professor of Software Science and Engineering in the Electrical Engineering and Computer Science (EECS) Department at the Massachusetts Institute of Technology (MIT), where she leads the Network Coding and Reliable Communications Group in the Research Laboratory for Electronics, and Chief Scientist for Steinwurf, which she has co‐founded. She obtained three Bachelor's degrees (EECS in 1989, Mathematics in 1989, and Humanities in 1991), as well as her M.S. (1991) and Sc.D. (1995), all from MIT. Muriel is a Member of the German National Academy of Sciences Leopoldina (elected in 2022), the American Academy of Arts and Sciences (elected in 2021), and the US National Academy of Engineering (elected in 2020); a Fellow of the US National Academy of Inventors (elected in 2018); and a Fellow of the Institute of Electrical and Electronics Engineers (elected in 2008). She holds Honorary Doctorates from the Technical University of Munich (2020), from the University of Aalborg (2022), and from the Budapest University of Technology and Economics (BME; 2023).
Muriel was co‐winner of the MIT 2004 Harold E. Edgerton Faculty Achievement Award and was named a Gilbreth Lecturer by the US National Academy of Engineering in 2007. She received the 2017 IEEE Communications Society Edwin Howard Armstrong Achievement Award and the 2016 IEEE Vehicular Technology James Evans Avant Garde Award. Muriel was awarded the 2022 IEEE Kobayashi Computers and Communications Award. She received the 2019 Best Paper Award for IEEE Transactions on Network Science and Engineering, the 2018 ACM SIGCOMM Test of Time Paper Award, the 2009 IEEE Communications Society and Information Theory Society Joint Paper Award, the 2009 William R. Bennett Prize in the Field of Communications Networking, the 2002 IEEE Leon K. Kirchmayer Prize Paper Award, as well as nine conference paper awards. Most of her prize papers are co‐authored with students from her group.
Muriel has served as technical program committee co‐chair of ISIT (twice), CoNext, WiOpt, and WCNC and of many workshops. She has chaired the IEEE Medals committee and served as a member and chair of many committees, including as inaugural chair of the Millie Dresselhaus Medal. She was Editor‐in‐Chief of the IEEE Journal on Selected Areas in Communications and of the IEEE Transactions on Information Theory. She has served as an editor or a guest editor of many IEEE publications, including the IEEE Transactions on Information Theory, the IEEE Journal of Lightwave Technology, and the IEEE Transactions on Information Forensics and Security. Muriel was on the inaugural steering committees for the IEEE Transactions on Network Science and for the IEEE Journal on Selected Areas in Information Theory. She was elected president of the IEEE Information Theory Society and served on its board of governors for a dozenyears.
Muriel received the inaugural MIT Excellence in Postdoctoral Mentoring Award (2022) and in 2013 the inaugural MIT EECS Graduate Student Association Mentor Award, voted by the students. She was recognized nationally as a Siemens Outstanding Mentor (2004) for her work with high school students. She set up the Women in the Information Theory Society (WithITS) and Information Theory Society Mentoring Program, for which she was recognized with the 2017 IEEE Aaron Wyner Distinguished Service Award. She served as an undergraduate Faculty in Residence for 7 years in two MIT dormitories (2002–2007). Muriel was elected by the faculty and served as a member and later chair of the MIT Faculty Committee on Student Life and as the inaugural chair of the MIT Faculty Committee on Campus Planning. She was chair of the Institute Committee on Student Life. She has served on the Board of Trustees of the International School of Boston, for which she was treasurer. She served on the Nokia Bell Labs Technical Advisory Board.
Muriel has over 80 US and international patents awarded, the vast majority of which have been licensed or acquired. For technology transfer, she has co‐founded CodeOn, Steinwurf, and Optimum.
Muriel has supervised over 40 master's students, over 20 doctoral students, and over 25 postdoctoral fellows.
Vipindev Adat Vasudevan
Vipindev Adat Vasudevan is a postdoctoral associate at the Massachusetts Institute of Technology (MIT) with the Network Coding and Reliable Communications Group. He received his B.Tech. degree in Electronics and Communication Engineering from the Mahatma Gandhi University, Kerala, India, in 2014; his M.Tech. degree in Computer Engineering (Cyber Security) from the National Institute of Technology, Kurukshetra, India, in 2017; and his Ph.D. in Information and Communication Technologies from the University of Vigo, Spain, in 2022. He has previously worked as a Marie Curie Fellow in the Wireless Telecommunications Laboratory of the University of Patras, Greece, and as a research officer in the Commission for Higher Education Reforms constituted by Kerala State Higher Education Council, India. His research interests include but are not limited to network coding, network security, 5G and beyond networks, and the Internet of Things. He is an active member of theIEEE.
Morten Videbæk Pedersen
Morten Videbæk Pedersen is the Chief Technology Officer (CTO) at Steinwurf ApS, a company he co‐founded in 2011 as a spin‐off from Aalborg University. Under his leadership, Steinwurf has developed high‐performance software solutions for communication and storage systems, bringing theoretical academic research into practical, commercial applications. As CTO, Morten has overseen software architecture, tooling, quality assurance, product development, technical sales, and team management.
Morten holds a Ph.D. in Wireless Communication from Aalborg University, where he also completed his M.Sc. with honors. He has experience as a postdoctoral researcher at the Department of Electronic Systems, Aalborg University, focusing on low‐complexity network coding algorithms and cooperative networking protocols. His academic journey included time as a visiting student at the Massachusetts Institute of Technology (MIT).
An avid software enthusiast, Morten has contributed to several scientific software libraries, including Kodo, a high‐performance network coding library used by industry and research institutions worldwide. He has received numerous accolades, including the Nokia Developer Champion award in 2010.
Morten is passionate about software engineering, staying updated with the latest developments, and enjoys building innovative solutions that push the boundaries of technology.
Ken R. Duffy
Ken R. Duffy is a professor at Northeastern University with a joint appointment in the Department of Electrical and Computer Engineering and the Department of Mathematics. His primary research focus is on the interdisciplinary application of probability and statistics in science and engineering. Algorithms he has developed have been implemented in digital circuits and in DNA. He received his B.A. (mod) in Mathematics in 1996 and his Ph.D. in Applied Probability in 2000, both awarded by Trinity College Dublin. He was previously a professor at the National University of Ireland, Maynooth, where he was the Director of the Hamilton Institute, an interdisciplinary research center, from 2016 to 2022. He was one of three co‐directors of the Science Foundation Ireland Centre for Research Training in Foundations of Data Science, which has funded more than 120 Ph.D. students. Heis a co‐founder of the Royal Statistical Society's Applied Probability Section (2011), co‐authored a cover article of Trends in Cell Biology (2012), is a winner of the best paper award at the IEEE International Conference on Communications (2015), the best paper award from IEEE Transactions on Network Science and Engineering (2019), the best research demo award from COMSNETS (2022), and the best demo award from COMSNETS (2023). He is an associate editor of IEEE Transactions on Information Theory and IEEE Transactions on Molecular, Biological, and Multi‐Scale Communications.
Preface
This book is the result of several years of research, teaching, and product design. The goal to have a book that can be a teaching tool at different levels and a real guide for the practitioner has had a slow genesis. Teaching tutorials, as well as networking, coding, algorithms and information theory classes at MIT and at Northeastern University, has shaped the understanding of the best way to present the material to balance didactic utility with depth. Working with companies implementing network coding has guided the selection of what concepts are necessary and what framing of architectural issues is truly useful to enable network coding to improve network performance. The result is a book where the main philosophical thread is that the material is curated in a way that we have ascertained to be beneficial for engineers, whether they be students or practising professionals. Indeed, one of the core joys of engineering is being involved in constant learning. We hope that this book fosters such learning.
January 6th, 2025
M.M., V.A.V., M.V.P., and K.R.D
.Massachusetts, USA & Aalborg, Denmark
Acknowledgments
This book has been in the works for many years, ever since the publication of the algebraic network coding work by Ralf Kötter and Muriel Médard. The insight and contributions of Ralf permeate this book and many of the key algebraic insights. The many tutorials he and Muriel undertook over the years before his untimely passing cemented the foundations on which this book is built.
We thank the many collaborators, colleagues, and students who have participated, directly or indirectly, in the journey of network coding or in the creation of the body of knowledge and understanding in this book, including Vitaly Abdrashitov, Szymon Acedanski, Varun Aggarwal, Ebad Ahmed, Chang Wook Ahn, Tor Aulin, Hari Balakrishnan, João Barros, Olivier Bonaventure, Viveck Cadambe, Ning Cai†, Flavio Calmon, Christopher Chang, Clifford Choute, Jason Cloud, Alejandro Cohen, Supratim Deb, Bikash Dey, Michelle Effros, Elona Erez, Attila Eryilmaz, Soheil Feizi, Frank Fitzek, Kerim Fouli, Christina Fragouli, Mario Gerla†, Steluta Gheorghiu, Andrea Goldsmith, Bernhard Haeupler, Keesook Han, Babak Hassibi, Janus Heide, Tracey Ho, Wenjun Hu, Siddarth Jaggi, Szymon Jakubczak, Coleen Josephson, Ton Kalker, David Karger, Mohammad Karzand, Dina Katabi, Sachin Katti, Minji Kim, Wonsik Kim, Michael Langberg, Hyunjoo Lee, Doug Leith, Ben Leong, Luisa Lima, Daniel Lucani, Desmond Lun, Nancy Lynch, Martin Maier, Ali Makhdoumi, Ivana Maric, Athina Markopoulou, Michael Mitzenmacher, Marie‐José Montpetit, Peter Musial, Rafael d'Oliveira, Una‐May O'Reilly, Asuman Ozdaglar, Payam Pakzad, Ali ParandehGheibi, Joon‐Sang Park, Giovanni Pau, Ilias Politis, Narayan Prakash, Nayak Ratnakar, Harihan Rahul, Arman Rezaee, Parastoo Sadeghi, Devavrat Shah, Jun Shi, Shirley Shi, Saurabh Shintre, Chres Sørensen, Fabio Soldo, Emina Soljanin, Alex Sprintson, Milica Stojanovic, Jay‐Kumar Sundararajan, Surat Teerapittayanon, Emre Telatar, Alberto Lopez Toledo, Danail Traskov, Christos Tselios, Tiago Vinhoza, Ming Xiao, Edmund Yeh, Yunjung Yi, Linda Zeger, Weifei Zeng, and FangZhao.
January 6th, 2025
M.M., V.A.V., M.V.P., and K.R.D
.Massachusetts, USA & Aalborg, Denmark
Acronyms
5G
Fifth Generation of Wireless Networks
AC‐RLNC
Adaptive and Causal Random Linear Network Coding
AES
Advanced Encryption Standard
AIMD
Additive Increase and Multiplicative Decrease
API
Application Programming Interface
ARQ
Automatic Repeat‐reQuest
BDP
Bandwidth‐Delay Product
CPU
Central Processing Unit
CRC
Cyclic Redundancy Check
CTCP
Coded TCP
D2D
Device‐to‐Device
DoF
Degree of Freedom
EW
Effective Window
FB‐FEC
Feedback‐Based Forward Erasure Correction
FEC
Forward Erasure Correction
FIFO
First In – First Out
FlEC
Flexible Erasure Correction
FPGA
Field Programmable Gate Array
Gbps
Gigabits per Second
GCD
Greatest Common Divisor
GF
Galois Field
GPU
Graphics Processing Unit
HTTP
Hyper Text Transfer Protocol
HUNCC
Hybrid Universal Network Coding Cryptosystem
IETF
Internet Engineering Task Force
i.l.c.
Integer Linear Combination
IP
Internet Protocol
kB
kilo Bytes
MB
Mega Bytes
Mbps
Megabits per Second
MIT
Massachusetts Institute of Technology
MTU
Maximum Transmission Unit
NC
Network Coding
P2P
Point‐to‐Point
PMF
Probability Mass Function
PQUIC
Pluginized QUIC
QUIC
Quick UDP Internet Connections
r.v.
random variable(s)
RLC
Random Linear Code
RLNC
Random Linear Network Coding
RREF
Reduced‐Row Echelon Form
RTT
Round Trip Time
SIMD
Single Instruction, Multiple Data
SR‐ARQ
Selective Repeat ARQ
SRTT
Effective Round Trip Time
SWNC
Sliding Window Network Coding
TCP
Transmission Control Protocol
TCP/NC
Network Coding with TCP
TD
Triple‐duplicate
TO
Time‐out
UDP
User Datagram Protocol
1Introduction
The objective of packet networks, such as the Internet, is to reliably transport information from sources to receivers. While data is packaged for communication, which may involve compressing it and adding headers describing destinations as well as other information, traditionally the data streams themselves are treated as immutable as they traverse the network, in the sense that the information of individual streams is kept separate and intact throughout their transit. The simple premise of Network Coding (NC) is that data can be readily algebraically manipulated and that making use of that fact results in a relaxation of many networking problems, which can be leveraged to vastly improve performance in a number of distinct dimensions.
As a basic thought experiment, if the network wishes to transport two pieces of information, and , it could instead transport and and allow the receiver to solve a basic set of linear equations, i.e. , to recover both. Why would that be useful? Think of a setting where three packets are transmitted across a network, but one will get lost in transit, as can happen in networks such as the Internet. If the network transmits , , and , no matter which two packets get through, the receiver can reconstruct the original data. The generalization and exploitation of this simple principle results in large, practically achievable gains in performance, as we shallsee.
NC remained in the realm of pure information theory until the advent of Random Linear Network Coding (RLNC) [1]. It has evolved from simple modulo additions of two packets to creating linear combinations of multiple packets in a finite field and communicating the digital result as doing so enables significant improvement in the bandwidth efficiency of networks. RLNC inherently generates robustness and adaptability in dynamic environments [2]. RLNC has proven suitable for distributed, dynamic environments such as wireless networks. Future networks, such as small cell environments featuring Device‐to‐Device (D2D) communication and cooperation between devices, will have to ensure that every user in thenetwork is fairly provided with services, where distinct metrics concerning the quality of service, such as throughput, delay, and latency, all have to be met. In cooperative environments, RLNC can achieve the upper bound of efficiency in multicasting. RLNC has been established to be a practical solution in these settings that can provide higher throughput and reliability with lower latency over unreliable network infrastructure. A key feature of RLNC is that it can be readily integrated into legacy systems, thanks to its compatibility with existing protocols and its ability to be implemented both in software as well as hardware. While RLNC seeks to achieve optimum efficiency in terms of bandwidth usage by sending coded packets over different channels, it also naturally provides erasure correction and imparts resistance to man‐in‐the‐middle attacks. While the use of NC by itself provides only weak protections security [3], it has been extensively studied how, with some augmentation, it is possible to harness more benefits such as increased security and privacy protection using RLNC in the challenging, quantum computing times ahead.
In a world with increasing demands on multiple fronts, it becomes a necessity to re‐envision communication protocols and RLNC has already been proven to be a way ahead. Different industrial adopters are already benefiting from coding principles and use RLNC in a variety of applications. It has found its way to standards and industrial deployments [4, 5] in line with the significant theoretical research that has been happening around the topic in the last couple of decades. There have been great resources, not only the large number of papers published in reputed conferences and journals but also great books introducing different dimensions of RLNC in the literature. However, a textbook that assists the adaptation of NC from its excellent results in the literature to engineering solutions has not materialized. This book tries to bridge the gap between the academic advancements in the area of NC to its practical realizations, from a complete engineering perspective.
1.1 Vision and Outline
This book walks the reader through the nuances of practical NC and its implementation in real‐world applications with curated, directly relevant mathematical explanations. Excellent resources for theoretical explanation of the concepts are listed, but mainly as additional readings, as the book itself is self‐contained in the material it presents. It concentrates on how these concepts can be used to formulate engineering solutions in the complex communication scenarios that are expected as part of current and future networks. This book begins with the basics of NC and explores more advanced concepts step‐by‐step with implementation details and possible use cases. Further, it provides a look ahead on how NC can be used in varied scenarios such as post‐quantum cryptography and heterogeneous wireless networks. This textbook is written in a way that it can be a stand‐alone read for engineers or go along with a lab‐based semester or quarter course on NC. It expects minimal prior knowledge of communication and information theory and presents the concepts from the introductory level.
As a structured and gradual learning experience, the book lays out the concepts of NC from basics to its more complex adaptations in a simple but rigorous manner. This textbook is designed to suit the requirements of the course material for a lab‐based semester‐long course or a one‐quarter course, while it also allows communication engineers to use it for self‐study and explore RLNC‐based implementations. For a one‐quarter (9‐week) course, Chapters 1, 2, 4, and 5 will form the basis of a course with sufficient substance and detail to serve as a stand‐alone introduction. For such a course, it would be recommended to skip some of the optional material (marked with **) in Chapters 2 and 4. Portions marked with ** indicate that the material in them provides interesting theoretical background, but they can be omitted. The sections with ** will be of interest to students who are curious about some of the mathematical underpinnings of NC, but they are not required for implementing RLNC algorithms or for developing an understanding of how they can benefit the operation.
For a full one‐term (12‐week) course, a more software engineering slanted curriculum will incorporate the quarter course material discussed above with all of Chapter 2, and, additionally, all of Chapter 3, most of Chapter 5, and all of Chapter 6. A one‐term course oriented more towards network optimization and architecture will benefit from covering all of Chapter 2, as well as all of Chapter 4 and additionally Chapters 5 and 6. A one‐term course oriented towards a more theoretical audience will benefit from covering all of Chapter 2, as well as all of Chapters 4, 7, and 8.
The clear mapping between the book and class organization allows instructors or engineers following a self‐paced program, a clear and ready way to use the book. While the primary focus is on the application of NC, different network models such as multipath and mesh networks as well as their design principlesare covered.
The book can be used in modular way to meet the needs of different engineering goals. Engineers who intend to understand how to construct a detailed, low‐level coding language version of NC modules may benefit from reading portions marked with a *. These provide extensive algorithmic development of implementing finite field operations in a context that is useful to NC. Those sections can be skipped by readers whose goal is to understand NC and incorporate it into systems, but who intend to use commercially available packages, say KODO library, to manage the mechanics of NC.
The organization of the book is as follows. This first chapter focuses on introducing NC as the use equations that result from combining data rather than the original data in networks. The data allows flexibility which is not only convenient, it also is the root of the robustness, design flexibility, and theoretical optimality of NC in many settings. The chapter also introduces the reader to a Python‐based package that will readily manage erasures. This package will provide readers with a tool that will suffice to verify the majority of the engineering uses ofNC.
Chapter 2 introduces the reader to finite representations. The approach is rigorous, but entirely practical in its philosophy. The finite field results focus on explaining the arithmetic that is critical to NC implementations. This discussion will make sure the engineers get a clear picture of NC implementations and should be able to choose different designs according to their application scenario.
Chapter 3 provides the reader with a detailed guide to implementing NC. Together, Chapters 2 and 3 provide a detailed description of the finite field representations of the data required for the inner mechanics of NC. The chapter also includes detailed pseudo‐codes and delves into computational efficiency aspects.
Chapter 4 considers the use of NC for managing losses in networks. We shall see that, whether there is a single receiver or several, the use of NC allows us to move away from considering uncoded packets of data, and to consider instead the transmission of equations, or degrees of freedom. Matters such as acknowledging received information, and adapting the transmission of data according to such acknowledgement, are covered in detail. A primer on queuing in this chapter suffices to exhibit the main performance advantages of NC in networks with losses, and the attendant benefits in terms of delay and throughput.
Chapter 5 allows the reader to compare practical NC to other state‐of‐the‐art communication protocols. Different NC protocol constructions are introduced. Building on Chapter 4, we show how protocols can be designed to realize the principles of NC. We provide means of analyzing the benefits of NC in protocols and schema for reasoning about and for modeling the operation ofNC‐based protocols.
In Chapter 6, we delve in detail in to how to incorporate NC into current transport protocols, and realize the principles and gains discussed in Chapters 4 and 5. We consider two of the main transport protocols, Transmission Control Protocol (TCP) and QUIC, and provide a full guide on how to integrate NC into these widely deployed protocols.
Chapter 7 moves towards treating more complex networks. First, the chapter extends the concept of representing data as equations to the network setting to show that successive linear transformations of data in different nodes of a network can be viewed as a single linear transformation in an end‐to‐end fashion, regardless of the network's topology. Leveraging concepts from Chapters 2 and 4, this chapter sets a simple mathematical framework for NC in arbitrary topologies.
Chapter 8 focuses on the interplay between security and NC. This chapter considers how data integrity, secrecy, and reliability can be ensured with NC. Topicssuch quantum‐safe encryption, which is based on coding data together, detection and defeating pollution attacks, are covered after a rapid primer on the essentials of information‐theoretic secrecy.
Some of the material in Chapters 2, 4, 5, 7, and8 overlaps with MIT's 6.120A, 6.7410/1, 6.263, 6.441 and 6.989 as taught by Médard and with Northeastern University's EECE 7332 as taught by Duffy.
We should note that NC has significant associated intellectual property. While it is not our role to detail it in this book, we provide a representative list in the appendix, as it may be of interest to the engineer who seeks to incorporate NC into commercial systems.
1.2 Coding
In information theory, coding is a technique used to improve efficiency and decrease error rates in data communication over noisy channels in order to reach channel capacity. There are two main types of coding traditionally: source coding and channel coding. Source coding involves optimizing the representation of data in outgoing symbols to enable exact recovery of the original message (lossless source coding) or recovery with some distortion (lossy source coding). Channel coding involves adding redundancy to the outgoing symbols so that the receiver can decode the original message over a noisy channel. Both of these coding processes are typically applied to source‐generated messages before they are sent over the noisy channel in practical systems. However, traditional coding schemes only involve the source and sink nodes. Network coding, as shown in Fig. 1.1, emerged as an approach to improve both reliability and efficiency together, but from a network perspective.
In multi‐hop communication systems, there are often intermediate nodes, also known as routers, between the source and sink. These intermediate nodes typically only forward the information they receive to the next node, a method known as the store‐and‐forward approach. However, the concept of network coding, introduced by Ahlswede et al. [6], allows intermediate nodes to also code the inputs they receive before sending them out, rather than just replicating the inputs to the outgoing links. This expands the possibilities for coding and can significantly improve the design of switching systems and network architecture. Throughout this book, unless specified, the term “coding” refers to NC and can happen at any node, not just the source. “Decoding” refers to the process of re‐extracting the original data from network‐coded packets. Additionally, the concept of “recoding” will be discussed as intermediate nodes in the network can also code their inputs to create new combinations to send on their outgoing links.
Figure 1.1 The introduction of network coding has created a new area within coding theory that focuses on enhancing the reliability and efficiency of the network.
Why Coding?
There are multiple reasons for using coding in a network. In particular, coding can be used to compensate for lost portions ofdata.
Packets can be lost in transit due to congestion.
Links can have outages, dropping packets.
Networks can be lossless but have bottlenecks.
