Transcript Network Coding with Unreliable, Unknown Bandwidths.

Network Coding and Reliable
Communications Group
Network coding with unreliable,
unknown bandwidths
Muriel Medard
EECS
RLE
MIT
Joint work with Szymon Jakubczak, Daniel Lucani, Jay-Kumar Sundararajan,
Joao Baros (University of Porto), Frank Fitzek (University of Aalborg), Michael
Mitzenmacher (Harvard University) , Milica Stojanovic (Northeastern),
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Overview
• Network coding changes the way that we can
consider data manipulation and dissemination in
networks
• One important aspect of this is how to
characterize the usefulness of nodes’ received
information consisting of coded packets
• We examine two main areas:
– File dissemination among nodes in wireless multihop
systems
– Using network coding with TCP to enhance
throughput and reliability
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
• Application: Network coding for file dissemination
– Data dissemination
• All nodes require all information
• Nodes start with some data: no constraint
– Wireless nodes
• Half-duplex: Node can transmit and receive, but
not at the same time
• Broadcast advantage: one tx can benefit several
nodes
• Previous work:
– Gossip algorithms, flooding, broadcasting
• # data packets ≤ # nodes
• Data is not concentrated at one node
• No losses
– Practical schemes for network coding , e.g. priority to
node with more information (progressive base station)
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Dissemination of a file
100%
75%
50%
25%
• Mobile devices are lined up with different
distances (link quality to the base station)
• Packet erasures
• All devices want to receive all information
• What is the right strategy?
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Greedy algorithm
coding horizon for device i
coding horizon for device 1
100%
75%
50%
backward healing
25%
device i forward dissemination
DAWN PI meeting – October 2009
device j
Network Coding and Reliable
Communications Group
Progressive Base Station:
Toy example
Slots
5M/2
2M
M
0
3M/2
M Data Packets
Greater Impact (Vanilla):
2M
3M/2
M/2
0M
M Data Packets
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Dissemination time gains: no losses
7
22
20
•Overhearing
of N = 2
6
18
16
5
14
12
4
10
•20 nodes
packets
•20
Gain = ( 3(M-1) +  (K - 1)/N  ) / ( M  (K-1)/N  )
Max Gain = (1/3)  (K-1)/N 
38
6
24
2
1
00
Gain = ( 3(M-1) +  (K - 1)/N  ) / ( M  (K-1)/N  )
Max Gain = M
200
400
600
800
1000
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
Number of Packets (M)
Number of Nodes (K)
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Dissemination time gains: losses
Pe2
1
Pe1
M
Pe2
2
0
Pe1
3
0
Pe1
4
0
3
Pe1 = 0.2, Pe2 = 0.6 (Simulation)
2.8
Pe1 = 0.5, Pe2 = 0.6 (Simulation)
Gain
2.6
Pe1 = 0.2, Pe2 = 0.4 (Simulation)
2.4
Pe1 = 0, Pe2 = 1
2.2
Pe1 = 0, Pe2 = 0
2
1.8
1.6
1.4
1.2
1
2
4
6
8
10
12
Number of PacketsDAWN
(M) PI meeting – October 2009
…
…
K
0
Initial
Number
of
packets
•Fixed number of nodes
•Overhearing reduces gain,
but reduces completion time
Network Coding and Reliable
Communications Group
TCP using network coding
Network coding
layer
between
TCP and IP
• Random linear network coding masks link losses from TCP in order to
prevent unnecessary back-off
• Novel ACK design that accounts for mixing (coding) of packets with each other
– Allows ACK of every innovative linear combination, even if it does not reveal a packet
immediately
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
The specifics
Redundanc
y factor
• Coding layer buffers packets given by TCP
• For every packet coming from TCP, coding layer transmits r
(>1) random linear combinations of buffered packets to IP
• Acknowledgment: ACK a packet upon seeing it (even before it
is decoded)
• Can do this at intermediate nodes as well in a daisy chain
(tandem) network
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
The specifics
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Experimental results (Reno)
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Experimental results (Reno)
Goodput versus redundancy factor for a 10% loss rate
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Window size issues
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Window size
• Note that a coding window size of W = 1 corresponds to
a repetition code that simply transmits every packet 1.06
times on average. In comparison,
• A simple sliding window code with W = 2 brings a big
gain in throughput by making the added redundancy
more useful
• Going beyond 2 reduces the goodput because a large
value of W can mislead TCP into believing that the
capacity is larger than it really is, which leads to timeouts
• We find that the best value of W for our setup is usually 2
for a loss rate up to around 5 %, and is 3 for higher loss
rates up to 25%
• Besides the loss rate, the value of W could also depend
on other factors such as the round-trip time of the path.
DAWN PI meeting – October 2009
Network Coding and Reliable
Communications Group
Conclusions
• We have shown that network coding can be
used to manage content in networks for file
distribution and for flow transmission
• The main thrust is to maintain a representation
of degrees of freedom, without necessarily a
detailed description of the space available at a
node
• The use of coding allows us to reduce delay and
increase throughput if we design the system
carefully
DAWN PI meeting – October 2009