Transcript ShapeShifter - Computer Science

Computer Science
ShapeShifter:
Scalable, Adaptive End-System Multicast
John Byers, Jeffrey Considine, Nicholas Eskelinen,
Stanislav Rost, Dmitriy Zavin
Listed alphabetically
1
Problem
Computer Science
Problem: efficient delivery of popular bulk content
 Existing Approaches:

Single-source unicast
Forward caching/Content Delivery Networks
Reliable IP Multicast
End-system multicast

Our approach:
Improving end-system multicast through the use of
forward error correction and better topologies
2
Network-supported (IP)
Multicast
Computer Science
Optimal solution: duplicates and disseminates
data only when necessary
 Relies on network support: in the real world, IP
Multicast lacks deployment
 Scalability concerns: per-group accounting and
topology management do not scale due to limited
router resources
 Reliability: many proposals, few solutions

3
End-System Multicast
Computer Science




Does not rely on network support: builds and manages
a virtual, overlay topology of unicast links on top of the
network’s physical topology
Flexibility: optimization of the tree according to a richer set
of metrics (perhaps specified by the application), ability to
change topology on-demand
Improved scalability: end-systems are richer than routers
in terms of dedicated resources
Problems: increased network resource requirements
compared to IP Multicast, non-optimal mapping of the
virtual topology onto physical topology
4
Related Work
Computer Science
Narada/End-System Multicast: Build and
maintain a mesh of low-latency unicast links and
use its minimal spanning tree for distribution. Also
showed costs relative to IP Multicast are not
excessive.
 Overcast: A core group of well-placed nodes uses
end-system multicast to distribute bulk content
internally, in order to eventually provide it to clients.
A node chooses a parent based on bandwidth
through the candidate nodes using the number of
network hops as a tie breaker.

5
Improvements in
ShapeShifter
Computer Science
Erasure codes: improved overlay management,
more connected graph structure, increased
adaptivity
 Scalable group management: a node need only
be aware of a small portion of the graph but
achieves coverage through continuous discovery
 Measurements: metrics crucial to optimization of
the overlay graph, such as shared-link congestion
(refer to Khaled’s presentation)

6
Forward Error Correcting
Codes
Computer Science



FEC codes: a well-known solution to dealing with packet
loss without using feedback – instead of retransmitting
packets, redundant packets are sent combining the original
packets to recover from losses. e.g. x, y, x+y, a, b, a+b+x
Efficient codes: instead of the traditional slow ReedSolomon codes, we use a variant of Tornado codes. This
allows fast decoding while only requiring a small number of
extra packets.
Strategy: the original server sends out FEC packets along
the end-system multicast graph (à la Digital Fountain).
7
Recoding
Computer Science

Problem
Correlation: client nodes may have a high degree of
correlation in information received due to common sources
Duplication: given correlation, duplicate packets received
from client nodes can be ineffectual

Solution
Recoding: nodes blend received packets to generate new,
high utility symbols for other nodes
Beyond trees: recoding allows non-tree topologies since
duplication is avoided
8
Uncorrelated Loss
Compensation
Computer Science
Loss
Rate
5%

Loss
Rate
30%
A neighbor node with greater throughput may supplement
the flow of content to another node, circumventing the
problematic physical link.
9
Download from Multiple
Nodes in Parallel
Computer Science
1 MB/s
1 MB/s
Well-connected
newcomer scenario
1 MB/s
1 MB/s
Non-uniform
dissemination of
content
10
Resilience To Partitioning
Computer Science
Collaborative
Reconstruction
Partition avoidance through
discovery and awareness
of multiple candidates
11
Future Work
Computer Science
Implementation underway
 More analysis of

Codes and correlation
Graph management
Security issues

Testing
WAN, simulated and real
Mobile environments

Extensions to streaming media
12