Transcript 슬라이드 1

A Survey of Application-Layer
Multicast Protocols
MOJTABA HOSSEINI, DEWAN TANVIR AHMED, SHERVIN SHIRMOHAMMADI, AND
NICOLAS D. GEORGANAS, UNIVERSITY OF OTTAWA
IEEE COMMUNICATIONS SURVEYS, 2007
Hongbeom Ahn
Page 1/18
Contents
Abstract
Multicasting
IP Multicast vs. Application Layer Multicast
ALM Protocol Design
• Application domain
• Deployment level
• Group management
• Routing mechanism
Popular ALM Protocols
• ZIGZAG
• NICE
• OMNI
Open Issues
Page 2/18
Abstract

Internet
– Born for one-to-one applications
• Nowadays : requires one-to-many, many-to-many applications
• IP multicast for a solution

Trade-off
– Group management
• Mesh-first vs. tree-first approach
– Routing
• Minimum spanning tree vs. cluster structure
– Application domain
• Multi-source vs. single-source
Page 3/18
Multicast Background


Unicast
–
–
Source sends N unicast datagrams,
one addressed to each of N
receivers
Not scalable
•
IP Multicast
–
•
•
Network is going to collapse
–
Page 4/18
Router actively participate in
multicast
Making copies of packet
Forwarding toward multicast
receivers
Multicast is more efficient than
multiple unicast connections
IP Multicast is a Solution?

Practical problems
– Needs to be installed at all levels of the network
• From backbone to edge routers
• Does ISP want to do this? -> Cost
– Requires routers to maintain per-group state
• Violates the stateless principle of the router construction
– Vulnerable to flooding attacks without complex network management
– Hard to provide reliability, congestion control

Reality
– Slow to be widely adopted
– A case for application-layer (or end-system) multicast
Page 5/18
Application-layer Multicast

Application Layer Multicast
– An alternative ways of multicasting at the application layer
– End systems communicate through an overlay structure
– Assuming only unicast paths provided by underlying network

Advantages
– No need to change routers
– Allow features to be easily incorporated

Main problems
– How do end systems with limited topological information cooperate to
construct good overlay structures!
– Performance implications of using an overlay structure
Page 6/18
IP Multicast vs. Application Layer Multicast (ALM)

IP Multicast optimal regarding tree structures
– Routers in tree

ALM has overhead due to tree built among application node
– Constructing non-optimal trees
Page 7/18
IP Multicast vs. Application Layer Multicast (ALM)
: Conceptual comparison
Page 8/18
IP Mutlicast vs. ALM
: Efficiency of IP Multicast vs. ALM



IP Multicast is efficient but needs deployment of routers
ALM hosts have little information about underlying network
ALM tree building can be optimized (link/tree stretch) to incur only
low penalties compared to IP Multicast
Topology
IP Multicast
ALM
Total cost = 37
Total cost = 39
Page 9/18
Deployment Issues with Multicasting

No widespread deployment of IP Multicast in the Internet

Technical, administrative and business related issues
–
–
–
–

IP Multicast capable routers all levels of network required
Tendency to install simple, unintelligent (= very fast) routers
Managing and security issues (flooding attacks)
Billing and charging
MBONE [5] project (mid 90ʼs)
–
–
–
–
–
Unicast connections between (IP Multicast) subnetworks
IP tunneling between these “IP Multicast islands”
Problems: receiver authentication, group management, flooding
Static setup of unicast tunnels = growth problem
Not available for home Internet users through their ISPs
Page 10/18
Application Layer Multicast Protocol Design

Design?
– ALM protocols have a wide variety of approaches and characteristics

Customization for improving overall performance of ALM protocols by
– Its requirements
– Its constraints
– Its assumed resources

Features
–
–
–
–
Application Domain
Deployment Level
Group Management
Routing Mechanism
Page 11/18
ALM Protocol Design
: Application Domain

ALM protocol design depends on the application domain
– Audio/Video streaming
• Single source
• Large number of receivers
– Audio/video conferencing
• Small to medium group size
• Interactive multipart conferencing session
• Multiple sources
– Generic multicast service
• Based on specific metric (delay, BW, fan-out,…)
– Reliable data broadcast and file transfer
• Large data sets (distributed DB, file sharing)
• Bandwidth as only metric

Typically focus on optimizing for a single application domain
Page 12/18
ALM Protocol Design
: Deployment Level

Proxy-based (infrastructure-level) ALM
– Requires dedicated server/proxies
in the Internet
– Creates overlay only among proxies
– Provides a transparent multicast
service to end-users (IP multicast)
– Typically generic multicast service
– Expect a service charge

End-system ALM
– Assumes only unicast infrastructure
– Expects users to take part in the forwarding
– Free as of peer-to-peer nature
• Independent and cost-free
– Enjoys more flexibility, optimized for specific
application domains
Page 13/18
ALM Protocol Design
: Group Management

Key decisions regarding group / node management
–
–
–
–
–
–

How to find out about / join / leave groups?
Sending allowed when not joined?
Centralized or decentralized management?
Support existing IP Multicast Islands?
Support refinement during group life-time?
Use mesh-first or tree-first approach?
Typically ALM uses
– Rendez-vous points for discovery
– Source-specific trees for video streaming (1:n]
– Mesh-first constructed shared trees for conferencing
Page 14/18
ALM Protocol Design
: Group Management

Mesh-first vs. Tree-first
• Configure the data distribution pathways
– Mesh-first
•
•
•
•
•
Topology with many redundant interconnections
Source is chosen as a root and a routing algorithm
Builds P2P ‘mesh’ without the multicast
Limits multicast tree quality (depends on quality of the mesh)
More robust and better for multi-source applications
– Tree-first
• Builds the multicast tree directly without any mesh
• Members select their parent from the known members
– Require running an algorithm to detect and avoid loops
• Gives direct control over the tree
• Changes cause change for all descendants in tree
• Lower communication overhead (simpler)
Page 15/18
ALM Protocol Design
: Group Management

Source-specific tress vs. shared trees
– Conflicting design goals
• Minimize individual path length (hops/end-to-end delay) to specific destination
• Minimize sum of hops (cumulative end-to-end delay) to all destinations
– Source-specific trees
• Optimizes the tree for a single source
• Limited efficiency for multiple sources on the same tree
– Shared trees
• Supports efficiently multiparty-communications
• Better maintenance costs than source-specific trees
Page 16/18
ALM Protocol Design
: Group Management

Distributed vs. Centralized (balance simplicity vs. robustness)
– Distribute workload for tree maintenance among root nodes
(Robust, synchronization issues, large-scale applications)
• Synchronization -> real-time media hard to ensure
– Central group management for small-scale applications
(Single-point of failure, simple & easy deployment)

Refinement
– Optimize tree performance because of new joins and leaves
• Causes interruptions & stability issues
Page 17/18
ALM Protocol Design
: Routing Mechanism

Shortest path trees
– Uses RTT measurements to build the shortest path tree from source to
end hosts
– Constructs a minimum cost path from a source node to all its receivers
– Commonly used by ALM protocols

Minimum spanning trees
– Just tries to construct
a low cost tree
– Minimum total cost
spanning all members

Cluster structure
– Build hierarchical clusters

Peer-to-Peer structure
– Typically use reverse-path forwarding
Page 18/18
Survey and Classification of ALM Protocols
: Zigzag

Overview
– A single source
– Degree-bounded ALM for media streaming

Key in ZigZag
– Use of a foreign head to forward the content to the other members of
cluster

Purpose
–
–
–
–
Short end-to-end delay
Low control overhead
Efficient join and failure recovery
Low maintenance overhead
Page 19/18
Survey and Classification of ALM Protocols
: Zigzag

Operation
The Highest Layer
Only have links to its
foreign subordinates
(Only except for the server)
Non-head member
Cannot get the content
from their head
Page 20/18
Survey and Classification of ALM Protocols
: NICE

Overview
– Scalable application layer multicast – hierarchical clustering approach
– Support a larger number of receivers
– Low bandwidth soft real-time data stream (stock and internet radio)

Features
– Cluster size = k to 3k-1 (e.g. 3~8)
– Cluster leader
• Is the center of the cluster
• Minimum maximum distance to all other hosts in cluster
– All hosts are part of the layer L0
– Cluster leaders in
layer Li join layer Li+1
– Each host maintains state
about all clusters it belongs
to and about its super-cluster
(leader`s cluster)
Page 21/18
Survey and Classification of ALM Protocols
: NICE

Analysis
– Control overhead
•
•
•
•
Exchange message with clusters
A host belongs only to L0 = O(k)
A host belongs to Li(highest) = O(k*i)
Worst case = O(k*logN)
– Operations
•
•
•
•

Join
Maintenance
Refinement
Leave/Failure recovery
Assumption
– RP(Rendezvous Point)
• New host contacts the RP to initiate join process
Page 22/18
Survey and Classification of ALM Protocols
: NICE

Control and data paths
– Source-specific tree
Page 23/18
Survey and Classification of ALM Protocols
: NICE

Join process
– Find the closet to itself
– Using Rendezvous Point!
Page 24/18
Survey and Classification of ALM Protocols
: OMNI

Overlay Multicast Network Infrastructure
– Overlay architecture to efficiently implement media streaming
– Multicast Service Nodes(MSNs) deployed by service providers
• Act as a forwarding entities for a set of clients
– Distributed protocol to form a delivery backbone

Goal
– Construct a multicast data delivery
backbone such that the overlay
latency to the client set is minimized
– Minimum average-latency degreedegree bounded spanning tree
Page 25/18
Survey and Classification of ALM Protocols
: OMNI

A latency of client (consists of)
– The latency from the media source to the root MSN r
– The latency Lr,d on the path from root MSN r to destination MSN d
– The latency from the MSN d to the client I

Solve!
– The minimum average-latency degree-bounded by

Evaluation
– Aggregate subtree clients
• The entire set of clients
server by all MSNs at MSNi
– Aggregate subtree latency
• Summation of overlay latency
of each MSN in the subtree from MSNi
Page 26/18
M : is the set of all MSN
Ci : the number of clients served
by the MSN i
Children(i) : the set of children
of i in the overlay tree
Survey and Classification of ALM Protocols
: OMNI

Operations
– Initial join
• <LatencyToRoot, DegreeBound>
– Local transformation
•
•
•
•
Child-promote
Parent-Child Swap
Iso-level-2 transfer
Aniso+level-1-2 swap
Page 27/18
Open Issues

The Current Trend regarding ALM
–
–
–
–
–
Trust in overlay network
Heterogeneity of users
Providing resilience
High-bandwidth file transfer and downloading
Topologically-aware data path method
• Reduce unnecessary high latency and redundant network resource usage
– Confidentiality

Tree refinement
– Reorganization or shuffling of the nodes in the tree
– Enhance the system performance (zero-degree -> join? How to control)

Handle these points
– Minimizing the length of the paths (usually in terms hops) to the individual
destinations
– Minimizing the total number of hops to forward the packet to all the
destinations
Page 28/18