Transcript spects2005_slides_mson

Multicast Service
Overlay Design
Li Lao (UCLA),
Jun-Hong Cui (UCONN),
Mario Gerla (UCLA)
Multicast Overview
IP Multicast
Application Layer Multicast
SPECTS 2005
Overlay Multicast
2
Multicast Overview

IP multicast (network level, routers)



Application layer multicast (end hosts)



Easy to deploy
Inefficient and difficult to scale to large groups
Multicast Service Overlay Network (MSON) (proxies)



Efficient
Faces deployment and marketing problems
Efficient and scale to large groups
Need careful overlay design
A Comparative Study of Multicast Protocols: Top, Bottom, or In the
Middle? (Lao, et al. GI 2005)
SPECTS 2005
3
An Example of MSON
TOMA
F
MSON
D
C
E
B
A
Application-Layer
Multicast
SPECTS 2005
4
Our Goal

Investigate MSON provisioning




Where to place proxies
How to connect these proxies (overlay links)
How much bandwidth to be reserved on each
overlay link
Examine effects of design algorithms

Performance of TOMA (as example)
SPECTS 2005
5
An Example of MSON Design
A
D
E
I
SPECTS 2005
6
Roadmap





Motivation
Problem Formulation
Our Approach
Simulation Study
Conclusion
SPECTS 2005
7
Problem Formulation

Input: a network N = (V, E), multicast groups G
with membership distribution and bandwidth
requirement

Output: a virtual network N’ = (V’, E’)



V’  V, and E’  path(E)
Each e’ is assigned bandwidth, e’E’
Objective: minimize multicast overlay cost and
average end-to-end delay
SPECTS 2005
8
Our Approach
Divide and Conquer



Overlay proxy placement: determine V’
Overlay link selection: determine E’
Bandwidth dimensioning: determine bandwidth
for e’  E’
SPECTS 2005
9
1. Overlay Proxy Placement



Given: the number of members wi for each router i
(1  i  n), and the shortest distance dij between
every two routers i and j
Find: no more than K (1  K  n) routers as proxies
Objective: the weighted sum of distances from each
router to its nearest proxy is minimized
SPECTS 2005
10
Solution


ILP Formulation

1,
xi  
 0,
if router i is selected as a proxy
otherwise

1,
yij  
 0,
if router j subscribes to proxy i
otherwise

A lot of approaches to solve, but expensive
Greedy


In each step, a router i is selected if this reduces the
weighted sum of distances by the largest amount
O(Kn2)
SPECTS 2005
11
2. Overlay Link Selection
E
C
A
A
D
D
B
B
E
C
A
Complete Graph
E
C
A
D
D
B
E
C
B
1-MST
SPECTS 2005
Adjacent Connection
12
Solutions

Complete Graph
 Shortest path length
 Highest tree cost
n( n  1)
 Largest number of overlay links:
2

Adjacent Connection
 Shortest path length
 Reduced tree cost
 Reduced number of overlay links

Minimum Spanning Tree
 Long path length
 Minimum tree cost
 Minimum number of overlay links: n  1
SPECTS 2005
13
3. Bandwidth Dimensioning

Given: an overlay network N’ = (V’, E’), a set
of groups G with member distribution and
bandwidth requirements, and a multicast
routing algorithm

Compute the amount of bandwidth reserved
on each overlay link e’  E’
SPECTS 2005
14
Solution

Simulation-based approach



Compute the multicast trees
Sum up the traffic volume of these trees for each
overlay link
Over-dimensioning
SPECTS 2005
15
Simulation Study

Abstracted AT&T backbone



Rocketfuel 1755



54 nodes, 9 proxies
Weight-based membership model
~300 nodes, 20 proxies
Uniform membership distribution
Metrics

Multicast tree cost, path length, request rejection ratio
SPECTS 2005
16
Overlay Proxy Placement
SPECTS 2005
17
Overlay Proxy Placement
SPECTS 2005
18
Overlay Link Selection
Number of
overlay links
Multicast
Tree Cost
Path Length
Complete Graph
190
81.9
4.24
Adjacent Connection
76
48.3
4.24
1-MST
19
31.2
6.05
2-MST
38
35.0
4.98
SPECTS 2005
19
Bandwidth Dimensioning
SPECTS 2005
20
Bandwidth Dimensioning
SPECTS 2005
21
Conclusions & On-going Work

Formulated the problem and divided it into three subproblems

Proposed solutions to each sub-problem




Greedy algorithm very effective for overlay proxy placement
MST and Adjacent Connection perform better than
Complete Graph
Over-dimensioning is needed for bandwidth dimensioning to
reduce join request rejection ratio
On-going work:


Overlay link selection: trade-off of overlay cost and delay
Probe a comprehensive optimal approach
SPECTS 2005
22
Questions ???
SPECTS 2005
23