Transcript A Proactive Approach to Reconstructing Overlay Multicast Trees

Overlay Multicast Trees
Background




Multicast
IP multicast vs. Application layer multicast
Overlay network
Issues in application layer multicast
Construct and maintain efficient distribution trees
between the multicast session participants
Topics today




Algorithmic solutions for constructing multicast
tree
with explicit maximum degree constraints
(Fengming Wang)
without explicit maximum degree constraints
(Jing Liu)
Multicast Tree Maintenance
(Jianming Zhou)
Overlay Multicast Trees of
Minimal Delay
Antonio Riabov
Columbia University
Zhen Liu and Li Zhang
IBM T.J. Waston Research Center
Introduction


Motivation
For all of the previous proposed heuristics,
the scalability issue remains open with
respect to the optimal solution.
Our job
Present an algorithm for constructing a
degree-constraint spanning tree and show
that it arrives at asymptotically optimal
solution.
Assumptions


Each node can be mapped to a point in the
Euclidean space, and node-to-node delays
can be approximated by Euclidean distances
between these points.
Points are uniformly distributed inside a
convex region in Euclidean space and at
least 2 outgoing links are allowed at each
node.
Constant Factor Approximation



Divide the segment into four sub-segments, by splitting it
with an arc of radius (R+r)/2 and a ray dividing angle a into
two halves.
Pick a representative point in each non-empty subsegment, such that its radius in polar coordinates is
closest to the radius of the source node. Connect the
source to all the representatives.
Repeat the procedure within each non-empty subsegment, to connect the points inside the sub-segment,
using the representative point as a local source.
Argument
Length ≤ max (R-q, q-r) + Ra + Ra/2 + …
≤ max (R-q, q-r) + 2Ra


OPT ≥ max (R-q, q-r)
4 * OPT ≥ 4 * r sin (a) ≥ 2Ra
Thus Length ≤ 5 * OPT
Main Algorithm



Create a grid of cells with equal area by
partitioning the disk.
Connect the cells, using cell representatives,
and form a core network
Connect points within the cells, using the
constant factor approximation algorithm
Analysis


Any path in the constructed spanning tree
consists of two parts: the sub-path p
connecting cell representatives, and the subpath q between the points in the last cell.
Length (p) + Length (q) ≤ 1 + 2Ra + S
S ≈ 2π / (2^{(k+1)/2})
S is the sum of arc lengths for inner (k-1)
circles of k-ring grid
Final Statement



For any small ε, δ, which are larger than 0, there
exists an N such that with probability greater than 1δ, when the number of points n is larger than N, the
length of the longest path in the tree produced by
the algorithm is within ε plus the optimal solution.
This ε denotes the ratio between the length of the
longest path in the tree and the optimal solution
N → ∞ implies ε → 0
Extensions

Out-degree 2

Higher Dimensions

Lifting the assumptions
Some questions




The algorithm does not consider the robustness of the
multicast tree, what will happen if some point leaves the
tree?
The algorithm specifies a minimum degree constraint 2,
what if some point does not have this kind of capability
or some powerful point wants more degree constraint?
The mapping from real world to Euclidean space is very
crucial, how?
Is this solution suitable for existing recovery techniques?
Approximation and Heuristic
Algorithms for Minimum Delay
Application-Layer Multicast Trees
IEEE INFOCOM 2004
Author: Eli Brosh, Yuval Shavitt
Presenter: Jing(Janet) Liu
Agenda





Research motivation
Goal statement
An approximation algorithm
A heuristic algorithm
Evaluation & conclusion
Issues in creating multicast trees
By intuition:
•short latency
•small degree
Application layer issue:
•sequential message
distribution
•Application-centric cost
•processing capacity of end
hosts
Existing solutions


Naive solution: shortest path tree
Other solutions:



Build a minimum height (diameter) tree with fixed
degree constraint [Y.-H.Chu et. al. 2000]
Consider processing and communication delays,
but assume that each of them are the same for all
the nodes [Cidon et. al., 1995]
Considers link delay and switching(sending) time,
but assume switching time is always smaller than
link delay [Bar-Noy et. al., 2001]
Goal statement & Strategy outline

The optimal multicast tree problem (MDM)
Given a directed complete graph G = (V,E), a multicast group M V,
a source host s M, a non-negative real processing delay p(v) for
each vertex v V, and a non-negative real communication cost c(u,v)
for each edge (u,v) E, find a multicast scheme which minimizes the
delay by which all the hosts in M receive a message from s.

Strategy:
find a multicast tree T which minimizes the quantity △T+LT
△T – the maximum generalized degree of T
generalized degree of a node = actual degree*switching time
LT– the maximum latency λrv in T from source r to any nodes v in U
λuv = c(u,v) + (p(u) + p(v))/2
The approximation solution(I)
Multicast
scheme
Uk
Uk = {r}
Multicast
scheme
Ui+1
Ui+1 = core(Ui)
Multicast
scheme
Ui
Multicast
scheme
U1
U1 = core(U0)
U0
U0 = the original
multicast group
1) size | Ui+1 | <= ¾ * | Ui |, r Uk
2) a multicast scheme to disseminate the message from Ui to Ui-1 in time
proportional to the minimum multicast time from r to Ui-1
The approximation solution(II)

1)
Core computation core(Ui)
Find a set of edge-disjoint paths, each path connects a pair
of nodes in Ui; the length of each path is bounded by 2LT*, the
generalized degree is bounded by 3 △T*
2) Transform the set of paths into a set of spider graphs
(graphs in which at most one node has degree more than two)
such that each connected component in this subgraph is a
spider
3) Arbitrarily select a terminal from each spider to the core
and select the nodes not in any spiders to the core
Note: the above steps insures that the chosen core members from
the spider is able to distribute a message to all the nodes in
that spider in the required linear time
The heuristic solution(I)
Note:
1. path <v1, …, vk> has
cost
2. Shortest path = minimum
cost
3. t[v] - the minimal time at
which the host is free to
initiate a non notified host
T - the constructed tree T
4. V[T] - set of notified hosts
5.
denotes the
predecessor of m[v] in
between m[v] and w
The heuristic solution(II)
V(T) = {s, v1, v2}
s
m(v5)
m(v3)
d2,5
d3,4 + d1,3 > d2,5
v5
v2
m(v4) v1
v4
d1,3
v3
d3,4
The heuristic solution(II)
V(T) = {s, v1, v2 , v3, v4, }
s
v5
v2
v1
v4
v3
Simulation
Comparison
Approx-MDM
Heuristic
performance
(OPT + (pmax – pmin)) . O(log n)
OPT
group size
small
large & small
different
network
topology
undirected, fully connected
directed,
partial or fully
connected
multiple
sources
support
support
Conclusion

The proposed solutions address the problem of
finding minimum multicast tree in a heterogeneous
postal model in the application layer


Value: there are some existing solutions, but the proposed
one is more realistic
Both the approximation and heuristic solutions are
centralized algorithms that could handle the new
sender join and multiple senders issue

Critics: fails to consider member join and leave issue, nor
other network dynamics such as bandwidth change
A Proactive Approach to
Reconstructing Overlay
Multicast Trees
INFOCOM 2004
Mengkun Yang, Zongming Fei
University of Kentucky
Introduction


Overlay Multicast vs. IP Multicast
Issues of Overlay Multicast


Approaches of maintenance


Reactive vs. Proactive
Challenges of proactive approach


Construction vs. Maintenance
degree constraint, multiple leaves, worst case
Design Principles of proactive approach

responsive, distributed, scalable
The Problem

Formalization



Overlay multicast tree => degree constrained
spanning tree
Degree-constrained minimum spanning tree
problem is NP-hard
The Problem of Recovery


The paper focus
Faster recovery
Existing Schemes

Reactive Schemes:





Grandfather
Root
Grandfather-All
Root-All
Same drawback


Concentration of traffic
Long time recovery
The Proactive Approach


Parent-to-be only for child
Solution formalization


Problem



Forest => spanning tree
Tree may not exist
The large distance between
root and grandfather
Solution


Pre-computation algorithm
Include grandfather
Pre-computation Algorithm
2
4
RD(N8)=1
RD(N9)=1
RD(N10)=1
Impossible!!
6
5
RD(N16)=1
RD(N17)=1
Possible!
8
15
16
9
17
18
10
19
20
21
22
The Proactive Approach

Recovery Protocol

Required Information of each node





List of ancestor, from grandfather to root
The parent-to-be, if any
The residual degree of each child
Total residual degree of subtree rooted at each child
Heartbeat and JOIN message


Heartbeat for detection
JOIN for recovery
Recovery Protocol

Upon receiving JOIN (parent-to-be)




Upon detecting children change (parent)


Accept if residual degree > 1
Redirect if node who subtree’s residual degree
biggest
Reject if no such child
Re-compute the rescue plan
Upon detecting parent leaving (child)

Join parent-to-be or ancestor
Recovery Protocol
Performance Study
Performance Study
Questions

Shortest Path Approach is not optimal!


Bandwidth, Processing Power
The quality of tree is not optimal
Conclusion



Faster Recovery
Comparable Quality of tree
Comparable Amortized cost