Network Coding Theory: Tutorial

Presented by
Avishek Nag
Networks Research Lab
UC Davis

Page 1
 Outline
• Introduction
• Classifications
• Single-Source Network Coding
– Global and Local Descriptions of a Network
Code
– Linear Multicast, Broadcast, and Dispersion
– Static codes
– Network Coding for Cyclic Networks

11/26/2008 Page 2
 Introduction

• DEFINITION: Network coding is a particular

in-network data processing technique that
exploits the characteristics of the broadcast
communication channel in order to increase
the capacity or the throughput of the network

11/26/2008 Page 3
 Communication networks

TERMINOLOGY
• Communication network = finite
directed graph
• Acyclic communication network
= network without any directed
cycle
• Source node = node without any
incoming edges (square)
• Channel = noiseless
communication link for the
transmission of a data unit per
unit time (edge)
– WX has capacity equal to 2

11/26/2008 Page 4
 The canonical example (I)
• Without network coding
– Simple store and forward
– Multicast rate of 1.5 bits per time unit

11/26/2008 Page 5
 The canonical example (II)

• With network coding

– X-OR  is one of the
simplest form of data
coding
– Multicast rate of 2 bits per
time unit

11/26/2008 Page 6
 NC and wireless communications

• Problem: send b1 from A to B and b2

from B to A using node C as a relay
(a)
• A and B are not in communication range
b1
(r)
• Without network coding, 4
transmissions are required.
• With network coding, only 3
transmissions are needed C
A r B

(b) (c)
b2 b1 b2

C C
A B A B

11/26/2008 Page 7
 Network Coding Classifications

• Based on Topology
– Acyclic Network Coding
– Cyclic Network Coding
• Based on number of nodes sourcing information
– Single Source Network Coding: Simple Algebraic
Notion
– Multi Source Network Coding: Probabilistic
Notion; the current understanding of multi-source
network coding is quite far from being complete

11/26/2008 Page 8
 Single-Source Network Coding

• Network is acyclic.
• The message x, a -dimensional row vector in a
finite field F, is generated at the source node.
• A symbol in F can be sent on each channel.

11/26/2008 Page 9
 Definition of a Field
• A field is a set together with two operations, usually
called addition (+) and multiplication (·), such that the
following axioms hold:
• Closure of F under addition and multiplication
– For all a, b in F, both a + b and a · b are in F (or
more formally, + and · are binary operations on F).
• Associativity of addition and multiplication
– For all a, b, and c in F, the following equalities hold:
a + (b + c) = (a + b) + c and a · (b · c) = (a · b) · c.
• Commutativity of addition and multiplication
– For all a and b in F, the following equalities hold: a +
b = b + a and a · b = b · a.

11/26/2008 Page 10
 Definition of a Field
• Additive and multiplicative identity
– There exists an element of F, called the additive identity
element and denoted by 0, such that for all a in F, a + 0 = a.
– Similarly, the multiplicative identity element denoted by 1,
such that for all a in F, a · 1 = a.
• Additive and multiplicative inverses
– For every a in F, there exists an element −a in F, such that a
+ (−a) = 0.
– Similarly, for any a in F other than 0, there exists an element
a−1 in F, such that a · a−1 = 1.
• Distributivity of multiplication over addition
– For all a, b and c in F, the following equality holds: a · (b +
c) = (a · b) + (a · c).

11/26/2008 Page 11
 Example: Binary Field

• A field with finite number of elements: finite

field or Galois Field
• A binary field with elements 0 and 1 and
operations XOR and AND is a GF(2)
• A message consisting of 1’s and 0’s and
containing say, 3 bits is a 3-dimensional row
vector in GF(2)

11/26/2008 Page 12
 Local Description of Network Code
• Let a pair of channels (d, e) be called an adjacent pair
when there exists a node T with d  In(T ) and e  Out (T )
• Let F be a finite field and a positive integer. An 
-dimensional F-valued linear network code on an acyclic
communication network consists of a scalar kd ,e , called
the local encoding kernel, for every adjacent pair (d, e)
• The local encoding kernel at the node T means the |In(T)|
× |Out(T)| matrix
KT   kd ,e  dIn (T ),eOut (T )

11/26/2008 Page 13
 Global Description of Network Code
• Let F be a finite field and  a positive integer. An 
-dimensional F-valued linear network code on an acyclic
communication network consists of a scalar kd ,e for
every adjacent pair (d, e) in the network as well as an 
-dimensional column vector f e for every channel e such
that
(1) f e  
d In (T )
kd ,e f d , where e  Out (T )

(2)The vectors f e for the  imaginary channels e  In( S ) form the

natural basis of the vector space F 

• The vector f e is called the global encoding kernel for

the channel e

11/26/2008 Page 14
 Local Description vs. Global Description

• Given the local encoding kernels for all channels

in an acyclic network, the global encoding
kernels can be calculated recursively in any
upstream-to-downstream order by (1), while (2)
provides the boundary conditions
• The global description and the local description
are the two sides of a coin:
– They are equivalent.
– Both can describe the most general form of a
(block) linear network code

11/26/2008 Page 15
 An Example

11/26/2008 Page 16
 d e
message x T

11/26/2008 Page 17
 Desirable Properties of a Linear Network
Code
• Law of information conservation: the content of
information sent out from any group of non-source
nodes must be derived from the accumulated
information received by the group from outside
• maxflow(T): the maximum flow from S to a non-
source node T
• maxflow(P): the maximum flow from S to a
collection P of non-source nodes
• Max-flow Min-cut Theorem: the information rate
received by the node T cannot exceed maxflow(T)

11/26/2008 Page 18
 Desirable Properties of a Linear Network
Code
• The network topology, the dimension  , and the
coding scheme determines achievability of the
upper bound
• Three special classes of linear network codes are
defined below by the achievement of this bound
to three different extents
– Linear Dispersion
– Linear Broadcast
– Linear Multicast
• Each notion is strictly weaker than the previous
notion!

11/26/2008 Page 19
 Linear Multicast

• For each node v, if maxflow(v)  , then the

message x can be recovered.

11/26/2008 Page 20
 Linear Broadcast

• For every node v,

– If maxflow(v)  , the message x can be received.
– If maxflow(v) < , maxflow(v) dimensions of the
message x can be recovered.
• Linear Broadcast  Linear Multicast

11/26/2008 Page 21
 Linear Dispersion
• For every collection of nodes P,
– If maxflow(P)  , the message x can be received.
– If maxflow(P) < , maxflow(P) dimensions of the
message x can be recovered.
• Linear Dispersion  Linear Broadcast
 Linear Mulicast
• For a linear dispersion, a new comer who wants to
receive the message x can do so by accessing a
collection of nodes P such that maxflow(P)  , where
each individual node u in P may have maxflow(u) < .

11/26/2008 Page 22
 Code Constructions

• Construction of multicast/broadcast/dispersion: consider

a linear network code in which every collection of
global encoding kernels that can possibly be linearly
independent is linearly independent
• This motivates the following concept of a generic linear
network code:
A linear network code is said to be generic if:
For every set of channels {e1, e2, … , en}, where n  
and ej  Out(vj), the vectors fe1, fe2, … , fen are linearly
independent provided that
{fd: d  In(vj)}  {fek: k  j} for 1  j  n
11/26/2008 Page 23
 Code Constructions
• A generic network code exists for all sufficiently
large F and can be constructed by the Li-Yeung-
Cai (LYC) algorithm.
• A linear dispersion, a linear broadcast, and a
linear multicast can potentially be constructed
with decreasing complexity since they satisfy a
set of properties of decreasing strength.
• In particular, a polynomial time algorithm for
constructing a linear multicast has been reported
independently by Sanders et al. and Jaggi et al.

11/26/2008 Page 24
 Static Network Codes
• Convention: A configuration  of a network is a mapping
from the set of channels in the network to the set {0,1}
•  (e) =0 for any link e signifies that the link e is absent
due to link failure

11/26/2008 Page 27
 Static Network Codes
• Let F be a finite field and  a positive integer. An 
-dimensional F-valued linear network code on an acyclic
communication network consists of a scalar kd ,e for
every adjacent pair (d, e) in the network. The  -global
encoding kernel for the channel e, denoted by f e , is 
-dimensional column vector calculated recursively in an
upstream-to-downstream order by

(1) f e,   (e) 

d In (T )
kd ,e f d , where e  Out (T )

(2)The  -global encoding kernals for the  imaginary channels are

independent of  and form the natural basis of the space F 

11/26/2008 Page 28
 Static Codes
• The adjective “static” in the terms above stresses the
fact that, while the configuration  varies, the local
encoding kernels remain unchanged
• The advantage of using a static network code in case of
link failure is that the local operation at any node in the
network is affected only at the minimum level

11/26/2008 Page 29
 Example

11/26/2008 Page 30
 Cyclic Networks

• Networks with at least one directed cycle

• Acyclic: the network coding problem independent
of the propagation delay, operation at all nodes
synchronized
• Cyclic: the global encoding kernels simultaneously
implemented under the ideal assumption of delay-
free communications (unrealistic)
• The time dimension is an essential part of the
consideration in network coding
• Non-equivalence between local and global
descriptions
11/26/2008 Page 31
 Non-Equivalence Example

• The local encoding kernels doesn’t give an unique solution for the global
encoding kernels
11/26/2008 Page 32
 Convolutional Codes for Cyclic Networks
• Corresponding to a physical node X, there is a sequence of
nodes X(0), X(1), X(2), . . . in the trellis network
• A channel in the trellis network represents a physical channel
e only for a particular time slot t > 0, and is thereby identified
by the pair (e, t)
• When e is from the node X to the node Y , the channel (e, t) is
then from the node X(t) to the node Y(t+1)

11/26/2008 Page 33
 Convolutional Codes for Cyclic Networks

11/26/2008 Page 34
 References

• R. W. Yeung, S. Y. R. Li, N. Cai and Z. Zhang,

“Network Coding Theory,” Now Publishers Inc.,
2006.
• Elena Fasolo, “Wireless Systems Lecture:
Network Coding Techniques,” March 2004

11/26/2008 Page 35
 Thank You!

11/26/2008 Page 36