Transcript Tsunami: Maintaining High Bandwidth Under Dynamic Network

Tsunami: Maintaining High
Bandwidth Under Dynamic
Network Conditions
Dejan Kostić, Ryan Braud, Charles
Killian, Eric Vandekieft, James W.
Anderson, Alex Snoeren, and Amin
Vahdat
Overview
•
•
•
•
•
•
Introduction / Background
Motivation
Related Systems
Design of Tsunami
Results
Conclusion
Introduction
Problem: Distribute a (possibly
large) file to a large set of end
hosts
Source
A
Design goals:
F
B
C
D
• Cannot reply on IP multicast
•No node may maintain global
state
E •Must be as efficient as
possible
•Must be extremely resilient to
failures, bandwidth changes,
etc
Motivation
• What is Tsunami good for?
– Software updates
– File distribution to a large set of Internet users,
CDN servers, or grid machines
– Not suitable for multimedia streaming
• BitTorrent is the current deployed solution
to this problem
Related Systems
• Hasn’t this problem been solved before?
–
–
–
–
–
BitTorrent
SplitStream
Slurpie
Bullet
Numerous others
• Not exactly
Design Questions
• What is the “correct” way to build a file
distribution protocol?
• How do we react to changes in bandwidth
as quickly as possible?
• How do we deal with unresponsive nodes or
those that leave the network?
• How do we make the protocol as robust as
possible?
More Design Questions
• Do we use push or pull?
• Should we encode the data?
• Use a tree or a mesh to distribute content?
Tsunami’s Design
• Uses a hybrid push/pull approach
• No encoding is used
• File is broken into fixed size pieces called
“blocks” for transmission
• Both an overlay mesh (data) and tree
(control) are used
Tsunami’s Design
• Tsunami can be viewed as a collection of
related “strategies”
–
–
–
–
–
Bootstrapping strategy
Update propagation strategy
Request strategy
Sender strategy
Peering strategy
Bootstrapping Strategy
• Every new node joins at the “root” and
obtains place in control tree
• Root node gives a short list of current mesh
members to joining node to use as initial
peers
How Do You Find Peers?
• Each node initially connects to nodes
provided by the source
• RanSub is used to distribute random subsets
of nodes periodically over the tree
• Nodes can peer with others discovered
through RanSub
• Peering relationships are not mutual
• A hard max of 20 peers is enforced per node
Update Propagation Strategy
• Peers send “diffs” to each other containing
updates about what new parts of the file
they have received
• Diff sending is both reactive and proactive
to minimize control overhead
Request Strategy
• Nodes make requests for blocks from their
peers based on parts of the file they need
• Disjoint requests are made to eliminate
duplicates
• Complex policy for maintaining “the right
amount” of data in flight from each peer at
all times
Sender Strategy
• Request strategy aims to have only one or
two blocks queued per peer at all times
• Since the request strategy does most of the
work, the sending strategy simply serves
requests in FIFO (per peer) order
Peering Strategy
• Every node initially desires 10 peers
• Through measurements, a node decides
whether it wants to add or remove a peer
based on its current performance
• No fixed set of peers is maintained
• Peering relationships change as bandwidth
changes
Results
Results
1
Percentage of nodes
0.8
0.6
0.4
0.2
0
250
Tsunami
Bullet
MACEDON SplitStream MS
BitTorrent
300
350
400
450
500
download time(s)
550
600
650
700
Conclusions
• Tsunami is efficient even under changing
bandwidth conditions
• Doesn’t use IP multicast
• No global state required at any node
Questions?