is a method of
attaining maximum information flow
in a network. The Traditional Approach
sender
receiver
receiver
receiver
receiver
Assumption:
Capacity = 1 The Traditional Approach
sender
receiver
receiver
receiver
receiver
Store, duplicate, forward
Assumption:
Capacity = 1 The Traditional Approach
sender
receiver
receiver
receiver
receiver
a
multicast
tree
Store, duplicate, forward
Assumption:
Capacity = 1 The Traditional Approach
sender
receiver
receiver
receiver
receiver
a
multicast
tree
To send one more bit
Assumption:
Capacity = 1 The Traditional Approach
sender
receiver
receiver
receiver
receiver
a
multicast
tree
two disjoint
multicast
trees
To send one more bit
Assumption:
Capacity = 1 The Traditional Approach
sender
receiver
receiver
receiver
receiver
Can we send one more bit?
stuck!
Assumption:
Capacity = 1 The Traditional Approach
sender
receiver
receiver
receiver
receiver
Assumption:
Capacity = 1 The Traditional Approach
sender
receiver
receiver
receiver
receiver
Assumption:
Capacity = 1 The Traditional Approach
sender
receiver
receiver
receiver
receiver
Assumption:
Capacity = 1 Assumption:
Capacity = 1
The Traditional Approach
sender
receiver
receiver
receiver
receiver
three disjoint
multicast
trees!
OPTIMAL!
Multicasting rate = 3 A Combinatorial Problem
sender
receiver
receiver
receiver
receiver
routers A Combinatorial Problem
receiver
receiver
receiver
receiver
routers
r
(the root) A Combinatorial Problem
routers
r
(the root)
r
(the root)
terminal
terminal
terminal
terminal A Combinatorial Problem
r
(the root)
r
(the root)
terminal
terminal
terminal
terminal
Steiner vertices A Combinatorial Problem
Steiner vertices
r
(the root)
r
(the root)
terminal
terminal
terminal
terminal
a
r
-
Steiner
tree
=
a
multicast
tree A Combinatorial Problem
Steiner vertices
r
(the root)
r
(the root)
terminal
terminal
terminal
terminal
a
r
-
Steiner
tree
=
a
multicast
tree
Maximum Multicasting = Maximum disjoint
r
-Steiner trees The Bottleneck Condition
Steiner vertices
r
(the root)
r
(the root)
terminal
terminal
terminal
terminal
Bottleneck = 3
Maximum multicasting rate Smallest bottleneck The Bottleneck Condition
[Menger 1927]
If only one receiver, then
maximum multicasting rate = smallest bottleneck.
r
Multicasting rate 3
Bottleneck
: a set of edges whose removal disconnect
the root (sender) from
some
terminal (receiver) The Bottleneck Condition
Bottleneck
: a set of edges whose removal disconnect
the root (sender) from
some
terminal (receiver)
r The Bottleneck Condition
Bottleneck
: a set of edges whose removal disconnect
the root (sender) from
some
terminal (receiver)
Smallest bottleneck = 2
r The Bottleneck Condition
Bottleneck
: a set of edges whose removal disconnect
the root (sender) from
some
terminal (receiver)
Smallest bottleneck = 2
But there are no 2 disjoint Steiner trees
r
Bottleneck conditions
are not tight! The Bottleneck Condition
Bottleneck
: a set of edges whose removal disconnect
the root (sender) from
some
terminal (receiver)
r
Let us insist to send
two units of data. The Bottleneck Condition
Bottleneck
: a set of edges whose removal disconnect
the root (sender) from
some
terminal (receiver)
r
a
b
Let us insist to send
two units of data. The Bottleneck Condition
Bottleneck
: a set of edges whose removal disconnect
the root (sender) from
some
terminal (receiver)
r
a
b
a
a
b
b
Let us insist to send
two units of data. The Bottleneck Condition
Bottleneck
: a set of edges whose removal disconnect
the root (sender) from
some
terminal (receiver)
r
a
b
a
a
b
b
Let us insist to send
two units of data. The Bottleneck Condition
Bottleneck
: a set of edges whose removal disconnect
the root (sender) from
some
terminal (receiver)
r
Let us insist to send
two units of data.
a
b
a
a
b
b
a
b
a
b
a
b
Encode
Decode
Multicasting rate = 2! The Network Coding Theorem
[Ahlswede, Cai, Li, Yeung, 2000]
In a
directed
network,
if network coding is supported, then
maximum multicasting rate =
capacity of smallest bottleneck Current activities
One of the most active topics in
information theory and network due
to its performance and robustness
Many interesting issues/projects
Microsofts Avalanche Project
Large Scale Software Update
P2P streaming Network Coding in Action:
Linear Coding
Assume each packet consists of
L
bits
Interpret
s
consecutive bits as symbols
over the field
F
2s
.
Each packet consisting of a vector of
L/s
bits
Outgoing packets are
``linear
combination
of the incoming packets Network coding in action:
Encoding
Assume original packets M
1
,, M
n
Each packet is associated with a sequence of
coefficients, g
1
,, g
n
X = n
i=1
g
i
M
i
In the example,F
2s
= {0,1}.
Each packet contains both the encoding vector
g=(g
1
,,g
n
) and information vector X
Encoding can be performed recursively.
A node stored (g
1
,X
1
),, (g
m
, X
m
), generates a
new encoded packet (g ,X ) by picking coefficients
h
1
,, h
m
such that X= j=1m
h
j
X
j Decoding
A node has received the set (g
1
,X
1
), , (g
m
, X
m
).
To retrieve the original packet, solve the system
{ X
j
= ni=1
g
ji
M
i
}
Obviously, we need m n to recover all data.
How to select linear combinations? Select
uniformly at random the coefficients over the
field F
2s
. Small field size (s=8) is sufficient. Security Issues
Passive attackers
Tap-the-line
Eavesdroppers
Honest-but-curious
Information-theoretic security against
passive attackers are first considered
by Cai and Yeung in ISIT, 2002.
In practice, end-to-end encryption is
always possible to achieve
computational security against passive
attackers. Security Issues
Active attack
Change the content (e.g., packet)
Inject arbitrary content
Remove content
.
Byzantine faults
Nodes can lie
Hinder reconstruction Exisiting Solutions
We can simply hash the content (or each
data blocks) and distribute the hash
values in a reliable way.
[Ho et al. 04] proposed a computationally
efficient method.
Draw backs:
Detection can only be performed when a data
block (or the entire content) can be
reconstructed.
Intermediate nodes may not have neough
information for detection. Open Issues
Effectiveness of network coding for
P2P
Security issues for software batches
Security issues for multimedia
streaming
Security in wireless network coding