Transcript Presentation slides Powerpoint

Characterizing Overlay
Multicast Networks
Sonia Fahmy and Minseok Kwon
Department of Computer Sciences
Purdue University
For slides, technical reports, and implementations,
please see:
http://www.cs.purdue.edu/~fahmy/
1
Why Overlays?
• Overlay networks help overcome deployment
barriers to network-level solutions
• The advantages of overlays include flexibility,
adaptivity, and ease of deployment
• Applications
• Application-level multicast (e.g., End
System Multicast/Narada)
• Inter-domain routing pathology solutions
(e.g., Resilient Overlay Networks)
• Content distribution
• Peer-to-peer networks
2
Overlay Multicast
Overlay link
Receivers
Source
Routers and
underlying links
3
Why Characterize Overlays?
• Overlay multicast consumes additional network bandwidth
and increases latency over IP multicast  quantify the
overlay performance penalty
• Little work has been done on characterizing overlay
multicast tree structure, especially large trees
• Such characterization gives insight into overlay properties
and their causes, and a deeper understanding of different
overlay multicast approaches  better overlay design
Characterizing Overlay Networks
Real data from
ESM experiments
Simulations
Analytical
models
4
Our Hypothesis
• Observations
• Many high degree high bandwidth routers
heavily utilized in upper levels of ESM/TAG
trees, which tend to be longer. Many hosts are
connected to lower degree low bandwidth
routers, clustered close together at lower levels
of the trees. This lowers multicast cost
• Causes
• Topology (power-law/small-world)
• Overlay host distribution
• Overlay protocol (full/partial info/overhead,
delay/bandwidth/diameter/degree, sourcebased/shared tree)
5
Overlay Tree Metrics
• Overlay cost = number of underlying hops traversed by
every overlay link
• Link stress = total number of identical copies of a packet
over the same underlying link
• Overlay cost = ∑stress(i) for all router-to-router links i
• Number of hops and delays between parent and child hosts
in an overlay tree
• Degree of hosts = host contribution to the link stress of the
host-to-first-router link
• Degree of routers and hop-by-hop delays of underlying
links traversed by overlay links
• Mean bottleneck bandwidth between the source and
receivers
• Relative Delay Penalty (RDP), mean/longest latency
6
Metrics: Examples
Overlay link
Receivers
Source
C
20 ms
A
15 ms
B
10 ms
15 ms
• Overlay cost = 12
• Link stress on A = 2
• RDP of B = (15+15+10)/20 = 2
7
Overlay Tree Structure
• Questions
• What do overlay multicast trees look like? Why?
• How much additional cost do they incur over IP multicast?
• Methodology
• Use overlay trees (65 hosts) in ESM experiments (from
CMU) in November 2002. Use public traceroute servers
and synthesize approximate routes. (Most university hosts
are connected to the Internet 2 backbone network)
• PlanetLab experiments and tree/traceroute data
8
Results: End System
Multicast
• Number of hops between
two hosts versus level of
host in overlay trees
• Distributions of per-hop delay
for different overlay tree
levels
(a) Tree level 1
(b) Tree levels 4-6
9
Overlay Tree Structure:
Simulations
• Topologies
• Contains 4 thousand routers connected in ways consistent with
router-level power-law and small-world properties
• GT-ITM topology with 4 thousand routers
• Delays and bandwidths according to realistic distributions
• Overlay multicast algorithms
• ESM (End System Multicast) [SIGCOMM 2001]
• A host has the upper degree bound (we use 6) on the number of its
neighbors
• TAG (Topology-Aware Grouping) [extended NOSSDAV 2002]
• Uses ulimit=6 and bwthresh=100 kbps for partial path matching
• MDDBST (Minimum Diameter Degree-Bounded Spanning Tree)
[NOSSDAV 2001, INFOCOM 2003]
• Minimizes the number of hops in the longest path, and bounds the
degree of hosts in overlay trees (degree bound = edge bw/min bw)
10
Results: Number of Hops
• Uniform host distribution
• Non-uniform host
distribution
MDDBST less clear than ESM because it minimizes max. cost
11
Results: Isolation of Topology
Effects
• Router degrees
• Clustering (small world)
12
Results: Latency and Bandwidth
• Relative delay penalty
(RDP)
• Mean bottleneck
bandwidth
ESM achieves a good balance, but scalability is a concern
13
Overlay Multicast Tree Cost
Source
•
k
•
h
•
Host
Receiver
Network Model
• LO(h,k,n) denotes overlay cost for an
overlay O when n is the number of hosts
• We only count hops in router
subsequences
• We use n instead of m
Why an underlying tree model?
• Simple analysis
• Consistency with real topologies
[Radoslavov00]
• Transformation from a graph to a k-ary
tree with minimum cost tree
Why least cost tree?
•
Modeling and analysis are simplified
•
Many overlay multicast algorithms
optimize a delay-related metric, which is
typically also optimized by underlying
intra-domain routing protocols
•
A lower bound on the overlay tree cost can
be computed
14
Network Models with Unary
Nodes
Branching node
Unary node with
only one child
k ( h i )
Number of unary nodes
created between
 1 adjacent nodes at levels
i-1 and i
Self-similar Tree Model (k=2, θ=1, h=3)
• To incorporate the number-of-hops distribution,
use a self-similar tree model [SODA2002]
15
Receivers at Leaf Nodes
Source
h
k
( h i )
i 1
k
r
Overlay link
Level l
α
k
k (1  (1  k (l 1) ) n )  1
h
α
k r (1  (1  k  r ) n )
2k ( h l 1)
Receiver
(a)
(b)
16
Receivers at Leaf Nodes
The overlay cost in (a):
h
( h i ) r
r n
k
k
(
1

(
1

k
) )

i 1
The overlay cost in (b):
h 1
r k g (l )
l
where
l
where
2k ( hl 1) (k (1  (1  k (l 1) ) n )  1)
g (l )  
0

The sum of (a) and (b)
 1
k h  1
r  h  log k

2 
 
if k (1  (1  k  (l 1) ) n )  1
otherwise
h 1
k h  1 r
r n
L o (h, k , n)  
k (1  (1  k ) )   k l g (l )
k 1
l r

n1-θ is observed
17
Receivers at Leaf Nodes
Ro (h, k , n) 
Lo (h, k , n)
U o (h, k )
where
U o (h, k )  i 1 k ( hi )
h
θ=0.15
18
Receivers at Leaf or Non-leaf
Nodes
kp
p  1  (1  M1 ) n
k(1-p)
…
h
kp
α …
k(1-p)
…
β …
kp
k(1-p)
k h 1  k
M 
k 1
α
kp
k(1-p)
2k ( h l )  k ( h l 1) (A)
…
β
kp
…
…
Level l
2k ( hl 1) (kp  1) (B)
…
Lυ(h-1,k,n)
L υ(h-2,k,n)
B(h  l  1)  ( A)  ( B)
L υ(h-3,k,n)
(a)
T (l )  B(h  l  1)
 kpL (h  l  1, k , n)  k (1  p )T (l  1)
(b)
19
Receivers at Leaf or Non-leaf
Nodes
The overlay cost in (a): kp( k ( h 1)  L ( h  1, k , n))
The overlay cost in (b):
h 1
T (1)   k i (1  p ) i {B(h  i  1)  kpL (h  i  1, k , n)}
i 1
where
B(h  i  1)  k ( hi 1) (2k   2kp  1)(1  (1  k i ) n )
The sum of (a) and (b)
L (h, k , n)  kp(k ( h 1)  L (h  1, k , n))
h 1
  k i (1  p)i {B(h  i  1)  kpL (h  i  1, k , n)}
i 1
20
Receivers at Leaf or Non-leaf
Nodes
L (h, k , n)
R (h, k , n)   
U (h, k )
where
1
U (h, k ) 
M


h
l
k k
l
l 1
( h i )
i 1
θ=0.15
21
Cost Model Validation
• The analytical results are validated using traceroutebased simulation topologies and our earlier topologies
• Normalized overly cost via
simulations
• ESM and MDDBST have
n0.8-n0.9; TAG has a
slightly higher cost due to
partial path matching
• Cost with GT-ITM/uniform
hosts is slightly higher than
with power-law/small-world
• The normalized overlay tree
cost for the real ESM tree is
n0.945
22
Related Work
• Chuang and Sirbu (1998) found that the ratio between the total
number of multicast links and the average unicast path length exhibits
a power-law (m0.8)
• Chalmers and Almeroth (2001) found the ratio to be around m0.7 and
multicast trees have a high frequency of unary nodes
• Phillips et al.(1999), Adjih et al.(2002) and Mieghem et al.(2001)
mathematically model the efficiency of IP multicast
• Radoslavov (2000) characterized real and generated topologies with
respect to neighborhood size growth, robustness, and increase in path
lengths due to link failure. They analyzed the impact of topology on
heuristic overlay multicast strategies
• Jin and Bestavros (2002) have shown that both Internet AS-level and
router-level graphs exhibit small-world behavior. They also outlined
how small-world behavior affects the overlay multicast tree size
• Overlay multicast algorithms include End System Multicast
(2000,2001), CAN-based multicast (2002), MDDBST (2001,2003), TAG
(2001), etc.
23
Conclusions
• We have investigated the efficiency of overlay multicast
using theoretical models, experimental data, and
simulations. We find that:
 The number of routers/delay between parent and
child hosts tends to decrease as the level of the host
in the ESM/TAG overlay tree increaseslower cost
 Routing features in overlay multicast protocols, nonuniform host distribution, along with power-law and
small-world topology characteristics contribute to
these phenomena
 We can quantify potential bandwidth savings of
overlay multicast compared to unicast (n0.9 < n) and
the bandwidth penalty of overlay multicast compared
to IP multicast (n0.9 > n0.8)
24
Ongoing Work
• We are conducting larger scale simulations and
experimental data analysis using PlanetLab.
• We are examining other and more dynamic metrics
with other overlay protocols, e.g., NICE, Hypercast
• We will precisely formulate the relationship between
the overlay trees, overlay protocols and Internet
topology characteristics
• We are investigating the possibility of inter-overlay
cooperation to further reduce the overlay
performance penalty
25