Transcript Multicast Overlays

Multicast Overlays
CSE 581: Internet Technology
(Winter 2002)
Instructor: Prof. Wu Chang Feng
Presenter: Charles ‘Buck’ Krasic
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
1
Papers Covered
•
•
•
•
•
An Architecture for Internet Content Distribution as an
Internet Infrastructure. Yatin Cahwathe, Steve McCanne, Eric
Brewer (UCB). Feb ‘2000, Unpublished.
The Inktomi Overlay Solution for Streaming Media Broadcasts.
Inktomi Corporation. (Brewer: Co-founder & Chief Scientist,
McCanne: CTO). WWW whitepaper.
Overcast: Reliable Multicasting with an Overlay Network. John
Jannotti, David K. Gifford, Kirk L. Johnson, M. Frans Kaashoek, James
W. O’Toole, Jr (Cisco). OSDI ‘2000
A Case for End System Multicast. Yang-hua Chu, Sanjay G. Rao,
and Hui Zhang (CMU). ACM SIGMETRICS 2000.
+ Enabling Conferencing Applications on the Internet using an
Overlay Multicast Architecture, Yang-hua Chu, Sanjay G. Rao,
Srinivasan Seshan and Hui Zhang (CMU). SIGCOMM 2001
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
2
The Problem
• Can the Internet today support large-scale
Internet broadcasting?  NO
“Madonna’s London gig broadcast live on the Internet… But as she burst
into her first song on Tuesday night, many fans were still queueing up
outside the virtual venue, struggling to connect to the live feed.”
—CNN News (Nov 29, 2000)
• Traditional unicast model does not scale
• IP Multicast is not the right solution
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
3
The Problem
• Traditional unicast model does not scale
– Millions of clients  server and network meltdown
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
4
Traditional solution: IP Multicast
• IP Multicast to the rescue
– Global broadcast distribution primitive
– Source sends single stream
– Routers split stream towards all clients
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
5
Concerns with IP Multicast
• Scalability with number of groups
– Routers maintain per-group state
– Analogous to per-flow state for QoS guarantees
– Aggregation of multicast addresses is complicated
• Supporting higher level functionality is difficult
– IP Multicast: best-effort multi-point delivery service
– End systems responsible for handling higher level functionality
– Reliability and congestion control for IP Multicast complicated
• Inter-domain routing is hard.
• No management of flat address space.
• Deployment is difficult and slow
– ISP’s reluctant to turn on IP Multicast
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
6
Alternative: Multicast Overlay
Multicast Proxies
Application-aware
computation
Locally scoped
multicast groups
Application-specific
Application-level
Overlay network
multicast
customization
provides multicast
1/23/2002
581 – Multicast Overlays
service CSE
above
substrate
(IP)
Charles ‘Buck’
Krasic
7
Overlay Architecture
Maintain a complete overlay graph (COG) of all group members
Step 0 • Links correspond to unicast paths
• Link costs maintained by polling
“Mesh”: Subset of complete graph may have cycles and includes all
Step 1 group members
• Members have low degrees (makes mesh a subset of COG)
• Shortest path delay between any pair of members along mesh is small
Stan1
Stan2
Berk2
CMU
Stan2
Gatech
Berk1
1/23/2002
Berk2
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
CMU
Stan1
Berk1
Gatech
8
Overlay Architecture (2)
•Source rooted shortest delay spanning trees of mesh
Step 2 •Constructed using well known routing algorithms
– Members have low degrees
– Small delay from source to receivers
Stan2
Berk2
1/23/2002
Stan1
Berk1
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
CMU
Gatech
9
Multicast Proxy Discovery
• Bootstrap using list of well-known rendezvous
proxies
• Gossip-style discovery
–
–
–
–
Pick random proxy Xj; send it our membership list
Xj merges this into its own list
Xj responds with part of its own list
Gradually all proxies discover each other
Summary: well-known rendezvous + gossip to
disseminate session membership
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
10
Mesh Construction and Optimization
• Set up connections with up to k other proxies
– k = degree restriction
• Periodically probe a random proxy, Xj
– Measure unicast distance to Xj
– Use local optimization algorithm to determine suitability
for picking as a neighbor
– If Xj has better route towards source than a current
neighbor, then replace that neighbor with Xj
Summary: Local optimization based on unicast
distances to choose mesh neighbors
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
11
Application-level Routing
• Variant of distance vector routing
– shortest path routing protocol
– routing table entries only for source proxies
– to detect loops, store entire path in routing table
• Build distribution trees from routing tables
– source-rooted trees
– reverse shortest path
– forward data using reverse path forwarding
Summary: Shortest path routing to build
source-rooted trees
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
12
Scattercast Evaluation
• Simulate the Gossamer control protocol
– 1000 node topology, approx. 4000 edges
– Constructed using gt-itm topology generator
• Measure:
– Average latency compared to multicast:
• Cost Ratio = (avg latency with Gossamer)
(avg latency with multicast)
– Time to construct stable overlay:
• Time for changes in overlay structure to stop
– Packet duplication overhead
• Number of physical Internet links with multiple copies
of same packet
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
13
Variation of Cost Ratio with
Session Size
2
1.9
1.8
Cost Ratio
1.7
1.6
1.5
1.4
1.3
1.2
Average with 95%
confidence intervals
1.1
1
0
50
100
150
200
250
Total number of SCXs
300
350
400
Cost ratio remains low (< 1.9)
even as session size increases
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
14
18
2.6
16
2.4
14
2.2
Total # of edge changes per SCX
12
2
Variation of cost ratio over time
10
1.8
8
1.6
6
Cost Ratio
Total number of edge changes per node
Time to Stability
1.4
4
2
1.2
0
1
0
200
400
600
800
1000
Time (seconds)
Most mesh changes occur
early on in the protocol
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
15
Packet Duplication Overhead
180
Number of physical links
160
Unicast
140
Gossamer
120
100
Most heavily
loaded link
for Gossamer:
14 copies
80
60
40
Most heavily
loaded link
for unicast: 99
copies
20
0
1
10
Total number of packets on any physical link
100
Load on physical links is lower for
Gossamer than for vanilla unicast
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
16
Contributions
• Overlay Architecture
– Lower-level constructs a routing mesh, shared across
multicast sessions
• Mesh is a subset of complete virtual graph
• Mesh is constructed through gossiping
– Nodes continuously arrive and leave the mesh
• Use dynamic optimization to improve mesh efficiency
• Must correct for path failures, esp. partitions
– Each multicast session tree constructed above mesh
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
17
Contributions (continued)
• Evaluations of Overlay Approach
– Mostly simulation based
• Metrics
– Efficiency of chosen paths
• Cost ratio, Relative Delay Penalty(RDP), Link stress,
Normalized Resource Usage
– Mesh convergence times
• Time for gossiping to stabilize
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
18
Advantages of Approach
• Localize hard multicast problems
– Bandwidth allocation, congestion control, loss recovery are
tractable
• Simplify network layer via intelligent infrastructure
– No inter-domain multicast routing required
– Impose access restrictions within overlay proxies
– Leverage well-understood wide-area unicast protocols and
naming schemes
• Incorporate app-specific semantics within proxies to
address heterogeneity
– App-specific reliability and data scheduling
– On-the-fly content and bandwidth adaptation
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
19
Disadvantages
• Topology of Overlay trees only approximate
– Link stress: number of times a packet crosses a
given physical link
• For IP Multicast: 1
• Overlay > 1
• Overlays represent are a trade-off relative to
pure unicast or native IP multicast
• Relative to IPM, overlays gain benefits in
exchange for:
– Lower overall bandwidth efficiency
– Higher end-to-end latency
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
20
Scattercast and Narada
• Topology discovery through learning/gossiping
– 2 levels: multicast tree over unicast mesh
• Scattercast mech uses directed edges:
– Simplifies mesh optimization (eliminates add/remove
race).
– More robust against unplanned partition
• Narada emphasizes low-latency more
– Narada target application is video conferencing
– Scattercast chose shared whiteboard and internet radio
broadcast
• Scattercast group seems to moving toward application
specific enhancements
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
21
Overcast
• Overcast: direct tree construction
– Doesn’t share information across sessions
– Prone to partitions?
– Less scaleable?
• Emphasizes deployment
– Protocols do everything in the upstream direction to
ensure compatibility with NAT and web proxies
– Everything done with http
• Overcast also emphasizes role of persistent storage
– Target application is efficient download of large production
quality MPEG video files
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
22
Inktomi
• Mostly static approach
– Overlay topology decided based on operator policy
– Limited automatic adaptation when substrate
topology changes
• Emphasizes explicit network management
tools more
– Tools for the broadcast war room
• Vaporware?
– Where are the broadcasts?
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
23
Further Work and
Improvements
• CMU SIGCOMM ’01
– Use better metrics during mesh construction/optimization
(bandwidth and latency)
– Evaluate on real internet
• Effects of Policy routing?
• Improve scalability?
– Would like all metrics to have sub-linear relationship to
group size
– Still linear:
– Time for mesh to converge
– Bandwidth and latency penalties
• Application specific processing
– Congestion control, content adaptation
1/23/2002
CSE 581 – Multicast Overlays
Charles ‘Buck’ Krasic
24