Network Coding

Fundamentals and Applications

Muriel Medard, Alex Sprintson

• Publisher: Academic Press
• Year: 2011
• eBook ISBN: 9780123809193
• Topic: Computer Science
• Subtopic: Data Processing
• Index: Computer Science

Network coding is a field of information and coding theory and is a method of attaining maximum information flow in a network. This book is an ideal introduction for the communications and network engineer, working in research and development, who needs an intuitive introduction to network coding and to the increased performance and reliability it offers in many applications.This book is an ideal introduction for the research and development communications and network engineer who needs an intuitive introduction to the theory and wishes to understand the increased performance and reliability it offers over a number of applications.- A clear and intuitive introduction to network coding, avoiding difficult mathematics, which does not require a background in information theory.- Emphasis on how network coding techniques can be implemented, using a wide range of applications in communications and network engineering- Detailed coverage on content distribution networks, peer-to-peer networks, overlay networks, streaming and multimedia applications, storage networks, network security and military networks, reliable communication, wireless networks, delay-tolerant and disruption-tolerant networks, cellular and ad hoc networks (including LTE and WiMAX), and connections with data compression and compressed sensing- Edited and contributed by the world's leading experts

Chapter 1. An Introduction to Network Coding

Frank R. Kschischang

Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada

Contents

1. The Butterfly Networks 2

2. Graphs and Networks 6

2.1. Combinational Packet Networks 6

2.2. Network Information Flow Problems 8

3. The Single-Source Multicast Problem 9

3.1. Multicast Capacity 9

3.2. Linear Network Coding 10

3.3. Linear Network Coding Achieves Multicast Capacity 13

4. Construction of Network Codes for Multicasting 16

4.1. The Linear Information Flow Algorithm 16

4.2. Random Construction 20

5. Coding versus Routing 21

6. Noncoherent Network Coding 24

6.1. Transmission with Packet Headers 24

6.2. Subspace Transmission 25

7. On Alphabets and Nonlinearity 26

8. Conclusions 29

Acknowledgments 29

Appendix 29

A. Finite Fields 29

B. Zeros and Nonzeros of Polynomials 32

C. The Degree of det(G_t) 35

References 36

A tutorial introduction is given to network coding, with particular emphasis on the single-source multicasting problem. Many now-standard results are reviewed; in particular: (a) the multicast capacity of a network is given by the least-capacity cut separating the source from any of its destinations; (b) the multicast capacity is achievable with linear network coding over a finite field of sufficiently large size, and there exists a computationally efficient algorithm to find a set of capacity-achieving linear network coding coefficients; (c) the multicast capacity is achieved with high probability over a sufficiently large field when the linear network coding coefficients are chosen at random. Also discussed is the practically important case of noncoherent random network coding, where neither the source nor any of the destinations has a priori knowledge of the specific linear network coding operations performed by the network. Finally, several “diabolical” counterexamples are discussed that demonstrate that linear network coding is not sufficient to achieve maximum throughput for general network flow problems.

Keywords: Graphs and networks, multicast capacity, linear network coding, linear information flow algorithm, random linear network coding, noncoherent network coding, nonlinear network coding.

1. The Butterfly Networks

Network coding is based on a simple, yet far-reaching, idea: in a packet network, rather than simply routing packets, intermediate nodes may comp...

Table of contents

• Cover image
• Table of Contents
• Front Matter
• Copyright
• Preface
• Acknowledgments
• About the Editors
• List of Contributors
• List of Figures
• List of Tables
• Chapter 1. An Introduction to Network Coding
• Chapter 2. Harnessing Network Coding in Wireless Systems
• Chapter 3. Network Coding for Content Distribution and Multimedia Streaming in Peer-to-Peer Networks
• Chapter 4. Network Coding in the Real World
• Chapter 5. Network Coding and User Cooperation for Streaming and Download Services in LTE Networks
• Chapter 6. CONCERTO
• Chapter 7. Secure Network Coding
• Chapter 8. Network Coding and Data Compression
• Chapter 9. Scaling Laws with Network Coding
• Chapter 10. Network Coding in Disruption Tolerant Networks
• Index