Transcript PowerPoint slides - Department of Computer Science and Engineering

Stealth Multicast - A New
Paradigm for Incremental
Multicast Deployment
Dr. Aaron Striegel
Dept. of Computer Science & Engineering
University of Notre Dame
NSF CAREER
Talk Overview
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Information Dissemination
• Motivation
• Stealth Multicast
– Basic Architecture
– Recent work: Wireless, ALM
– Preliminary Results
• Future Research
– Inter-domain Peering
– Network stack enhancement
2
Information Dissemination
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Distribute rich content in a timely fashion to
users
– Problem: Internet evolved as point-to-point
• Inefficient but currently manageable via unicasts
• Two main approaches
– Active involvement - Multicast
• Close temporal proximity
• Applications, network can participate
– Community participation -> network efficiency
– Passive involvement - Caching
• Multiply-accessed data over time
• No required participation of apps/network
– Exploit existing characteristics of network
» HTTP Caching, Packet-level caching
3
Multicast
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Operation
– Tree structure
• Network state - replication
• Benefits
– Reduced bandwidth
• N receivers << N bandwidth
– Bottleneck relief
• Relief close to source
– Simplifies sender
management
• Send to group vs. individuals
4
Caching vs. Multicast
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Caching
– Cannot handle rapidly changing data
• Data w/close temporal proximity
– Easy deployment
• No global participation
• Multicast
– Deployment problems
• Global participation
– Addressed by ALM
» Delay-sensitive traffic, rich user base
• Economic incentive
– Bandwidth glut, ISP benefit
– Can handle close temporal data
• Group-oriented activities - synchrony is an issue
5
Current State
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Caching: Yes
Multicast: ??
– Several recent studies [2000, 2003]
• Lackluster adoption 150 (99) -> 250 (2001)
• Most groups are single source (SSM)
– Why have *, G, CBTs, etc.?
» Harder form of multicast anyway
– Key lesson from caching
• Incremental deployment is key
– Big-bang theory is impossible
– Transition as easy as possible (FUD inertia)
• Immediate benefit
– Large benefit with minimal investment
• Directable economic benefit
– Avoid “If you build it, they will come…”
6
Motivation
• Research premise
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
– Transparent bandwidth conservation technique
– Best of caching and multicast
• Incremental deployment
– Zero dependence on external forces
• Immediate benefit
– Exploit the redundancy in the network, first/last mile & core
• Economics
– Offer a significant and quantifiable benefit
• Stealth Multicast
– Dynamically convert packets to/from multicast
– Target
• Small to medium group-oriented apps
• Delay-sensitive apps
5-500 users
– On-line gaming, video streaming
7
Stealth Multicast
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Two governing principles
– Externally transparent
• Zero modification - application (server/client)
• Zero modification - external Internet
• Seamless operation
– Negligible QoS impact?
• Should not noticeably impact QoS
• What are noticeable QoS changes?
– Depends upon application
» Large buffer - streaming video
» On-line game - zero buffer
– Informal definition
» Additional delay should not make the
application unusable versus separate unicasts
8
Stealth Multicast Model (Core)
Conversion
Other Domains
Servers
ISP Domain
Clients
Company LAN
(Content Provider)
Unicast
Multicast
Unicast
9
Multicast Detection
VGDM - Virtual Group Detection Manager
Virtual
Group
Mgr
Disp
Checksum
Tree
Calculation
Construction
H
Rules
State
Management
Filter
Edge Router
Incoming Traffic
Outgoing Traffic
(Unicast only)
(Unicast+Multicast)
10
Further Examination
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Benefits
– Dynamic conversion
– Zero modification
– Multicast transport
via virtual groups
– Exact billing
Too much delay
Benefit
Delay
• Drawbacks
–
–
–
–
Non-zero queuing delay
Aggregation effects
Imperfect virtual groups
Not a universal solution
Not enough gain
Virtual Group Delay
Minimum gain
Maximum delay
11
Multicast Transition Options
Approach
Pure
Multicast
Application
Assisted
Customer
Aware
Stealth
Mode
Separate
Unicast
Application
Multicast
Stealth
Unicast
Unicast
Unicast
Internet
Multicast
Unicast
Unicast
Unicast
Unicast
ISP
Multicast
Stealth
Stealth
Stealth
Unicast
None
ISP
Company
ISP Edge
None
Perfect
Perfect
Good
OK
None
Customer,
ISP
Customer,
ISP
Customer,
ISP
ISP
None
App change
Deployment
App change
Deployment
Deployment
Deployment
None
VGDM
Detection
Accuracy
Benefits
Costs
12
Dynamic Trees
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Implementation of stealth multicast
– Dynamically grow/shrink physical
multicast groups
• Virtual group - snapshot at current time
• Physical group - superset of potential
clients
– Defines key issues of stealth multicast
• Triggers - Virtual group release
• Transport - Dynamic groups
• State management - Where to place
state
13
Virtual Group Triggers
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Trigger
– Dilemma: Gain for waiting
– When to release the virtual group
• MHT - Maximum Hold Time
• TSW - Time Search Width
• PSW - Packet Search Width
Target packet
MHT
TSW
PSW
time
14
Triggers - Continued
• Triggers/thresholds
– MinGS - Minimum group size
– MaxGS - Maximum group size
– MVG - Maximum virtual groups
New group
Multicast
Unicast
VG 0
..
MaxGS
MVG
MinGS
VG N
15
Scalability & Storage
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Examine worst case constraints
– Worst case delay is MHT
• 10% of an RTT of 50 ms
• 5 ms MHT
• Average delay is MHT / 2
– Worst case storage
• PSW and TSW yield MHT, no matches
• 1 Gb/s link, 1000 byte group overhead
– 1 Gb/s @ 8 bit/byte * 5 ms = 625 kB
– 625 kB/sec / 64 bytes = 9765 packets
– 625 kB + 9765 * 1000 = ~ 11 MB
16
Multicast Transport
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Issue
– Members (clients) not known a priori
– Dynamically construct tree
• Approaches
– Exhaustive tree construction
• All variations, all egress points
– Broadcast/hold
• Costly - queuing at edge
– Encapsulation-based
• Embed tree inside the packet
– Dynamic tree construction
• Grow/shrink tree as necessary
• Multicast or ALM
– Broadcast (wireless)
17
Application State
18
Control Messages
19
State Management
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Issue
– Unique portions of packet
• Compress multiple packets for different
destinations into a single packet
– Dest port, dest IP
– Who is responsible for exporting?
• Egress A vs. Egress B vs. Egress C
• Approaches
– Include in packet
• Similar to encapsulation-based approach
– Distributed knowledge
• Egress points share knowledge
20
Application-Assisted Method
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Virtual group detection
– Imprecise nature - best guess
• Application-assist
– Application knows about VGDM
– Application sends 1 packet w/state to VGDM
– VGDM constructs tree
• Benefits
– No change to the client - deployment
– Precise group construction
• Issues
– Billing
– Requires change to server app
21
Other Issues - TCP, IPSec, IPv6
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• TCP
– Limited benefit
• Why?
– Extra state
– Retransmit of lost packets
– Potential benefit
• Web serving - initial request
– Assume no cookies
• CNN on 9/11
• IPSec / VPNs
– XBox Live (on-line gaming)
• IPv6
22
Wireless Stealth Multicast
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Apply stealth to the last mile
– Guarantee of B/W issues
– Exploit broadcast nature of wireless
• Design issues
– Discovery
– Partial group coverage
• Bitmask on UDP header
– Linkage on client
• Spoof packet back through stack
• Open issues
– Ad hoc networks
23
Passive ALM (PALM)
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Avoid reliance on IP multicast
– Leverage existing ALM work
– Dynamically convert to/from ALM
• AC, AHD, non-ALM clients
– New services to leverage
• Design issues
– Reliability constraints on ALM
• Tree consistency
– Partial tree subsets
– Discovery
• VGDM outwards, client to client
24
Simulation Studies
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Simulation setup
– Ns-2 simulator
• Freely available simulator
– GenMCast module for ns-2
– GIPSE for simulation management
• Network setup
– Medium-sized multicast groups
• On-line gaming apps - 8 to 64 clients
• UDP traffic - 40 server apps
– Compare various approaches
• Based on VGDM location + others
– Local, Stealth, None, App-Assist, ALM
• Evaluation metrics
– Bandwidth savings
– End-user QoS
25
Effect of Clients - Link BW
No savings, unicast
Higher up-link cost
26
Effect of clients - Domain BW
Increasing savings
vs. unicast
Trades B/W for
client B/W
27
Effect of Clients - QoS (Delay)
Only amenable
packets are queued
Limited impact
of queuing
28
Results – Wireless Stealth
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Interesting performance
– Remove entire queuing penalty
• 3+ clients, huge B/W savings
– Need larger search space
• Inter-packet spacing from network
• Prototype work
– Concurrent development
• Wireless Stealth, PALM
– Beta: Jan 2005
• COTS, COTS + HW
29
Future Research Areas
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Inter-domain peering / super-proxy
– Transparent bandwidth conservation
• Packet caching and stealth multicast
• Edge routers of domains exchange info
– Stealth multicast
• Avoid conversion to/from multicast/unicast
• Construct tree for new domain
– Packet caching
• Share cache in other domains
– Issues
• Billing, QoS
• Resource management
• Protocol / security
30
Future Research Areas
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
• Network stack modification
– Present: Minimize overhead
• Avoid extra IP/TCP or IP/UDP headers
– Premise
• Can we increase redundancy but increase overall
system performance?
– Enhance network stack
• Add End of Data marker - TCP
• Modify sendmail / Apache to use
– Issues
• Benefit to the network
• Downstream impact -> net system impact
31
Conclusions
Talk Overview
Introduction
Multicast
Motivation
Stealth Multicast
Virtual Groups
Triggers
Scalability
Transport
State Mgmnt
Other Issues
Wireless Stealth
PALM
Simulations
Dynamic Trees
Wireless
Future Research
I-D Peering
Network Stack
Conclusions
• Stealth multicast
– New paradigm for multicast
– Offers several key benefits
• Solves multicast deployment issue
– Zero modification outside of the domain
• Inherent resource management
• Offers directable economic benefit
– Interesting research problems
• Transport, state management
• Inter-domain peering, stack optimization
32
Questions?
[email protected]
http://www.cse.nd.edu/~striegel
GenMCast Package (ns-2)
http://www.cse.nd.edu/~striegel/GenMCast
33