Network coding : an introduction

Network coding promises to significantly impact the way communications networks are designed, operated, and understood. This book presents a unified and intuitive overview of the theory, applications, challenges, and future directions of this emerging field, and is a must-have resource for those working in wireline or wireless networking. * Uses an engineering approach - explains the ideas and practical techniques * Covers mathematical underpinnings, practical algorithms, code selection, security, and network management * Discusses key topics of inter-session (non-multicast) network coding, lossy networks, lossless networks, and subgraph-selection algorithms Starting with basic concepts, models, and theory, then covering a core subset of results with full proofs, Ho and Lun provide an authoritative introduction to network coding that supplies both the background to support research and the practical considerations for designing coded networks. This is an essential resource for graduate students and researchers in electronic and computer engineering and for practitioners in the communications industry.rs in electronic and computer engineering and for practitioners in the communications industry.rs in electronic and computer engineering and for practitioners in the communications industry.rs in electronic and computer engineering and for practitioners in the communications industry.

Preface	p. ix
1 Introduction	p. 1
1.1 What is network coding?	p. 1
1.2 What is network coding good for?	p. 2
1.2.1 Throughput	p. 2
1.2.2 Robustness	p. 5
1.2.3 Complexity	p. 7
1.2.4 Security	p. 8
1.3 Network model	p. 8
1.4 Outline of book	p. 11
1.5 Notes and further reading	p. 12
2 Lossless Multicast Network Coding	p. 13
2.0 Notational conventions	p. 13
2.1 Basic network model and multicast network coding problem formulation	p. 13
2.2 Delay-free scalar linear network coding	p. 14
2.3 Solvability and throughput	p. 17
2.3.1 The unicast case	p. 17
2.3.2 The multicast case	p. 18
2.3.3 Multicasting from multiple source nodes	p. 19
2.3.4 Maximum throughput advantage	p. 19
2.4 Multicast network code construction	p. 21
2.4.1 Centralized polynomial-time construction	p. 21
2.4.2 Random linear network coding	p. 23
2.5 Packet networks	p. 27
2.5.1 Distributed random linear coding for packet networks	p. 28
2.6 Networks with cycles and convolutional network coding	p. 30
2.6.1 Algebraic representation of convolutional network coding	p. 31
2.7 Correlated source processes	p. 34
2.7.1 Joint source-network coding	p. 35
2.7.2 Separation of source coding and network coding	p. 37
2.8 Notes and further reading	p. 37
2.A Appendix Random network coding	p. 39
3 Inter-Session Network Coding	p. 49
3.1 Scalar and vector linear network coding	p. 50
3.2 Fractional coding problem formulation	p. 51
3.3 Insufficiency of linear network coding	p. 52
3.4 Information theoretic approaches	p. 54
3.4.1 Multiple unicast networks	p. 58
3.5 Constructive approaches	p. 58
3.5.1 Pairwise XOR coding in wireline networks	p. 59
3.5.2 XOR coding in wireless networks	p. 60
3.6 Notes and further reading	p. 63
4 Network Coding in Lossy Networks	p. 65
4.1 Random linear network coding	p. 67
4.2 Coding theorems	p. 68
4.2.1 Unicast connections	p. 68
4.2.2 Multicast connections	p. 82
4.3 Error exponents for Poisson traffic with i.i.d. losses	p. 83
4.4 Notes and further reading	p. 85
5 Subgraph Selection	p. 86
5.1 Flow-based approaches	p. 87
5.1.1 Intra-session coding	p. 87
5.1.2 Computation-constrained coding	p. 110
5.1.3 Inter-session coding	p. 111
5.2 Queue-length-based approaches	p. 114
5.2.1 Intra-session network coding for multiple multicast sessions	p. 115
5.2.2 Inter-session coding	p. 128
5.3 Notes and further reading	p. 129
6 Security Against Adversarial Errors	p. 130
6.0 Notational conventions	p. 130
6.1 Error correction	p. 131
6.1.1 Error correction bounds for centralized network coding	p. 131
6.1.2 Distributed random network coding and polynomial-complexity error correction	p. 142
6.2 Detection of adversarial errors	p. 147
6.2.1 Model and problem formulation	p. 148
6.2.2 Detection probability	p. 150
6.3 Notes and further reading	p. 151
Appendix 6.A Proof of results for adversarial error detection	p. 152
Bibliography	p. 157
Index	p. 169

Available:*

On Order

Summary

Summary

Table of Contents