Transcript Powerpoint slides - Stanford University Networking Seminar

Scattercast: Taming Internet Multicast
Yatin Chawathe
[email protected]
Research
Menlo Park
http://www.research.att.com/labs/mp/irg/
02/08/2001
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
2
Our Solution: 10,000 Foot View
• Explicit infrastructure support

Push complexity up the protocol stack
• Application-layer broadcasting

Keep network layer simple and robust
• Broadcast customization on per-application basis

Allow applications to optimize the broadcasting framework
Scattercast: Infrastructure-service-based
broadcasting—as opposed to global IP multicast
3
Outline
• Motivation
• Introduction: The Scattercast Architecture
• Gossamer: Application-level Multicast
• Semantic Transport: Application-aware
customization
• Summing up
4
The Problem
• Traditional unicast model does not scale
 Millions
of clients  server and network meltdown
5
Traditional solution: IP Multicast
• IP Multicast to the rescue

Global broadcast distribution primitive

Source sends single stream

Routers split stream towards all clients
6
Problems with IP Multicast
• Complex network protocol

Scaling issues: state explosion and inter-domain routing

No access control

Difficult to manage and debug
• Heterogeneity

Single stream cannot satisfy all clients/networks

Different applications have different requirements
• Reliable multicast

Much harder than TCP

No scalable loss recovery, congestion control
• End-to-end argument fails for multicast

network layer is no longer simple and robust
7
Scattercast: Broadcasting as an
Infrastructure Service
ScatterCast
proXies (SCXs)
Application-aware
computation
Locally scoped
multicast groups
Application-specific
Infrastructure
Application-level
proxies
broadcasting
customization
(SCXs) provide
the broadcast service
8
Benefits of this 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 SCXs

Leverage well-understood wide-area unicast protocols
• Incorporate app-specific semantics within SCXs to
address heterogeneity

App-specific reliability and data scheduling

On-the-fly content and bandwidth adaptation
9
New challenges
• How do you distribute data efficiently across the
infrastructure?

Gossamer: Application Level Multicast
• How do you incorporate application-specific
intelligence into the distribution infrastructure?

Application-customizable scattercast transport
• How do you manage the service and ensure fault
tolerance, availability, and scalability of SCXs?

Cluster-based SCX implementation
10
Outline
• Motivation
• Introduction: The Scattercast Architecture
• Gossamer: Application-level Multicast
• Semantic Transport: Application-aware
customization
• Summing up
11
Overview
ScatterCast
proXies (SCXs)
• Source injects data into a session via its local SCX
• SCXs dynamically construct overlay network of
unicast connections: the mesh
• Run DVMRP-style routing on top of this network to
construct distribution trees
12
Goals
• Minimize latency from source to all receivers
 SCXs
are not routers  Overlay tree not as
optimal as IP multicast
 Optimize
topology
overlay to “reflect” underlying Internet
• Limit number of duplicate packets traversing
any physical Internet link
 Each
SCX transmits to handful of nearby SCXs 
Restrict degree of each SCX based on its
bandwidth capabilities
13
SCX Discovery
• Bootstrap using list of well-known
rendezvous SCXs
• Gossip-style discovery
 Pick
random SCX Xj; send it our membership list
 Xj merges this into its own list
 Xj responds with part of its own list
 Gradually
all SCXs discover each other
Summary: well-known rendezvous + gossip to
disseminate session membership
14
Mesh Construction
• Set up connections with up to k other SCXs
k
= degree restriction
• Periodically probe a random SCX, 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
15
Application-level Routing
• Variant of distance vector routing
 shortest
 routing
 to
path routing protocol
table entries only for source SCXs
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
16
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
17
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
Cost ratio remains low (< 1.9) even as
session size increases
400
18
18
2.6
16
2.4
14
2.2
Total # of edge changes per SCX
12
Variation of cost ratio over time
10
2
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
19
Packet Duplication Overhead
180
Number of physical links
160
Unicast
140
Gossamer
120
100
80
60
Most heavily loaded link
for Gossamer: 14 copies
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
20
Gossamer Summary
• Application-level multicast is feasible
• Mesh + routing approach results in stable
overlay distribution structure
• Gossamer is but one approach for
application-level multicast
21
Outline
• Motivation
• Introduction: The Scattercast Architecture
• Gossamer: Application-level Multicast
• Semantic Transport: Application-aware
customization
• Summing up
22
Overview
• Different
Our solution:
applications
Application-awareTransport
have different transport
Framework
requirements
 Expose underlying overlay topology to applications

Allow
applications
to define
their own
forwarding
policies
Reliability,
bandwidth
management,
congestion
control,
etc.

Delivery
of “information”
One-size-fits-all
solution rather
will notthan
workthe “representation”
of
the data
information
Single
stream cannot satisfy all heterogeneous clients

Application-aware
computation
23
An Example Application
• Online Presentation

Distribute web pages for
on-line presentations

Requires eventual reliability

High-bandwidth image data
• Four levels of customization

Customizable data forwarding

Customizable data reliability

Transmission scheduling

Data transformation
24
Customizable Data Forwarding
• Expose underlying overlay topology to transport
layer

Local view of the distribution tree: upstream link towards
source + list of downstream links
• Allows applications to build custom transport
protocols for reliability, congestion control, etc.

Transmit nacks/acks upstream towards source

Transmit data/retransmissions towards receivers
25
Customizable Data Reliability
• Reliability constraints vary

Ordered/unordered delivery, best effort, periodically
updating data

Different types of reliability within the same app
• Apps define their own reliability policies

Application Data Units (ADUs)

Group related ADUs into containers
• e.g. html in one container, images in another

Assign reliability policies to containers
reliable
ignore losses
unordered
HTML
Image
container container
• e.g. ignore losses in image container
allow out-of-order delivery of ADUs
26
Customizable Transmission Scheduling
• Customized bandwidth management
 Buffer
data to avoid congestion
 Notify
upstream SCX to slow down
 Prioritize
“important” ADUs over others
HTML
high priority
images
low priority
27
Customizable Data Transformation
• Transform ADUs on the fly
 Bandwidth
adaptation:
discard redundant information
 Format
conversion:
adapt content to suit client devices
• Feedback from scheduler drives
transformation decisions
 e.g.
convert images to P-JPEG;
prioritize base scan
 limit
P-JPEG size based on available bandwidth
28
Real Applications
• Electronic whiteboard
 Shared
drawing space
 Adaptive reliability
• Whiteboard for PalmPilot
 Extreme
client heterogeneity
 Split application: PalmPilot
app is simple; smarts in SCX
Scattercast
overlay
network
Broadcast
server
• Streaming MP3 broadcast server
 Radio
over the Internet
 Interface to standard clients e.g. WinAmp
29
Outline
• Motivation
• Introduction: The Scattercast Architecture
• Gossamer: Application-level Multicast
• Semantic Transport: Application-aware
customization
• Summing up
30
Scattercast: Broadcasting as an
Infrastructure Service
• End-to-end is not the right answer
 Use
intelligent infrastructure to simplify the
network layer
• Divide-and-conquer localizes hard problems
 Use
multicast only in local area where it is
tractable; robust unicast across wide-area
• Application-level intelligence is crucial
 Adapt
to heterogeneity by leveraging
application hints in transport protocol
31
The Longer Term:
Evolving Scattercast
• Flat scattercast overlay cannot scale
• We may have many independent broadcast networks
• Solution: build a broadcast inter-network across
collections of broadcast networks
Scattercast
network
Yet-anotherbroadcast-network
IP-multicast
network
Broadcast
Inter-network
32
Come work with us!
• AT&T Research: Menlo Park
 http://www.research.att.com/labs/mp/irg/
• We are looking for summer interns as well
as full time hires
33