Network Coding for Engineers - Ken R Duffy

. .

Résumé :

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