Transcript ZIGZAG: An Efficient Peer-to-Peer Scheme for Media Streaming

ZIGZAG: An Efficient Peer-to-Peer Sch
eme for Media Streaming
Duc A. Tran Kien A. Hua Tai Do
University of Central Florida
Published in IEEE INFOCOM 2003
Network Computing Laboratory
Outline
One line comment
Motivation
Proposed Solution
Performance Evaluation
Conclusions
Critiques
Network Computing Laboratory | 2
Korea Advanced Institute of Science and Technology
One line comment
ZIGZAG is multicast scheme for streaming
applications
Scalable
Robust
Network Computing Laboratory | 3
Korea Advanced Institute of Science and Technology
Motivation
Stream live bandwidth-intensive media from a single source to
many receivers
An individual connection to stream the content to each receiver
IP Multicast
Network Computing Laboratory | 4
Korea Advanced Institute of Science and Technology
Major design goal
Three important issues in designing an efficient P2P
technique
The end-to-end delay from the source to a receiver may be excess
ive
Hierarchical, Degree-bounded multicast tree
The behavior of receivers is unpredictable
A robust techniques to provide a quick and graceful recovery
Hierarchical Topology
ZIGZAG property of multicast tree
The resource limitation at each receiver
Minimize the control overhead (increasing the scalability)
Network Computing Laboratory | 5
Korea Advanced Institute of Science and Technology
Administrative organization
H is the number of layers
K>3 is a constant
(1) Layer 0 contains all peers
(2) Peers in layer j<H-1 are partitioned into clusters of sizes in [ k ,
3k ].Layer H-1 has only cluster which has a size in [ 2 , 3k ]
(3) A peer in a cluster at layer j<H is selected to be the head of that cluster.
This head becomes a member of layer j+1 if j<H-1. The server S is the
head of any cluster it belongs to.
Network Computing Laboratory | 6
Korea Advanced Institute of Science and Technology
Administrative organization (cont.)
H = Ө(logkN) where N = # of peers
Any peer at a layer j>0 must be the head of the cluster it
belongs to at every lower layer
Network Computing Laboratory | 7
Korea Advanced Institute of Science and Technology
Terms
Subordinate:
Non-head peers of a cluster headed by a peer X are called “subordinat
e” of X
Foreign head:
A non-head (or server) clustermate of a peer X at layer j>0 is called a
“foreign head” of layer-(j-1) subordinates of X
Foreign subordinate:
Layer-(j-1) subordinates of X are called “foreign subordinates” of any l
ayer-j clustermate of X
Foreign cluster:
The layer-(j-1) cluster of X is called a “foreign cluster” any layer-j clus
termate of X
Network Computing Laboratory | 8
Korea Advanced Institute of Science and Technology
Multicast Tree
(1) A peer, when not at its highest layer, cannot have any link to or from any
other peer. (peer 4 at layer 1)
(2) A peer, when at its highest layer, can only link to its foreign subordinates.
The only exception is the server; at the highest layer, the server links to
each of its subordinates (peer 4 in layer 2 )
(3) At layer j<H-1:non-head members of a cluster get the content directly from
a foreign head (peer 1 2 3 )
Network Computing Laboratory | 9
Korea Advanced Institute of Science and Technology
Multicast Tree (cont.)
The worst-case node degree of the multicast tree is O(k2)
The height of the multicast tree is O(logkN) where N = # of peers
Network Computing Laboratory | 10
Korea Advanced Institute of Science and Technology
Control protocol
Each node X in a layer-j cluster periodically communicates with its layer-j cl
ustermates, its children and parent on the multicast tree
For peers within a cluster, the exchanged information is the peer degree
If the recipient is the cluster head, X also sends a list L = {[X1,d1],[X2,d
2],..}, where [Xi,di] represents that X is currently forwarding the content to
di peers in the foreign cluster whose head is Xi (peer 5 at layer 1 {[S,3],[6,
3]})
Network Computing Laboratory | 11
Korea Advanced Institute of Science and Technology
Control protocol (cont.)
If the recipient is the parent, X instead sends the following information:
A Boolean flag Reachable(X): true iff there exists a path from X to a layer0 peer (Reachable(7)=false Reachable(4)=true )
A Boolean flag Addable(X): true iff there exists a path from X to a layer-0 p
eer whose cluster’s size is in [k,3k-1]
Although the worst-case control overhead of a node is O(k*logkN), the
amortized worst-case overhead is O(k)
Network Computing Laboratory | 12
Korea Advanced Institute of Science and Technology
Client Join
If the administrative has one layer, new Client P connects to S
D(Y) denotes the currently end-to-end delay from the server observed by a
peer Y
d(Y,P) is the delay from Y to P measured during the contact between Y to
P measured
1. If X is a leaf
2.
Add P to the only cluster of X
3.
Make P a new child of the parent of X
4. Else
5.
If Addable(X)
6.
Select a child Y :
Addable(Y ) and D(Y )+d(Y , P) is min
7.
Forward the join request to Y
8.
Else
9.
Select a child Y :
Reachable(Y ) and D(Y )+d(Y , P) is min
10.
Forward the join request to Y
The join overhead : O(logkN) in terms of number of nodes to con
tact
Network Computing Laboratory | 13
Korea Advanced Institute of Science and Technology
Client Join - Split
Suppose we decide to split a layer-j( j  [1,H-2]) cluster with a head X a
nd non-head peers X1,…Xn
xil = the number of peers that are both children of Xi and layer-(j-1) sub
ordinates of Xl

(1) Partition {X, X1,…,Xn} into two sets U and V,|U|,|V| [k,3k], and
X i U , X l V
( xil  xli )
is minimized. Suppose X  U
(2) For each node Xi  U and each node Xl  V such that xil > 0,remove a
ll the links from Xi to layer-(j-1) subordinates of Xl and select a random p
eer in V other than Xl to be the new parent for these members
Network Computing Laboratory | 14
Korea Advanced Institute of Science and Technology
Client Join – Split (cont.)
(3) Elect a new head Y for cluster V. Y is chosen to be a peer in V with the min
imum degree. Y becomes a new member of the cluster at layer-(j+1).
For
each child cluster (whose non-head members used to be children of Y), we sel
ect a peer Z != Y in V having the minimum degree to be the new parent.
Remove the current link from X’ to Y and add a link from X’’ to Y
Network Computing Laboratory | 15
Korea Advanced Institute of Science and Technology
Client Join – Split (cont.)
The worst-case split overhead is O(k2)
Network Computing Laboratory | 16
Korea Advanced Institute of Science and Technology
Client Departure
A peer X who departs
If X’s highest layer is layer 0, no further overhead emerges.
Suppose that X’s highest layer is j>0
For each layer-(j-1) cluster whose non-head members are children of X, th
e head Y of the cluster is responsible for finding a new parent for them.
Y selects Z, a layer-j non-head clustermate, that has the minimum degree
Network Computing Laboratory | 17
Korea Advanced Institute of Science and Technology
Client Departure (cont.)
Furthermore, since X used to be the head of j clusters at layers 0, 1,…,j1
Let X’ be a random subordinate of X at layer 0
X’ will replace X as the new head for each of those clusters
Network Computing Laboratory | 18
Korea Advanced Institute of Science and Technology
Performance Evaluation
Peer Stretch: (the length of the data path from the server to a peer in
our multicast tree) / (the length of the shortest path between them i
n the underlying network)
Link Stress: the number of times the same packet goes through the li
nk
Use the GT-ITM Generator to create a 3240-node transit-stub graph a
s our underlying network topology
2000 clients located randomly
K=5
Network Computing Laboratory | 19
Korea Advanced Institute of Science and Technology
Scenario 1: No Failure
Network Computing Laboratory | 20
Korea Advanced Institute of Science and Technology
Scenario 1: No Failure (cont.)
Network Computing Laboratory | 21
Korea Advanced Institute of Science and Technology
Scenario 2: Failure Possible
Network Computing Laboratory | 22
Korea Advanced Institute of Science and Technology
Scenario 3: ZIGZAG vs. NICE
Network Computing Laboratory | 23
Korea Advanced Institute of Science and Technology
Scenario 3: ZIGZAG vs. NICE (cont.)
Network Computing Laboratory | 24
Korea Advanced Institute of Science and Technology
Conclusions
ZIGZAG
Node degree
O(k2)
Height of multicast tree
O(logkN)
Control overhead of a node
O(k*logkN)
Join overhead
O(logkN)
Split overhead
O(k2)
Number of peers that need to reconnect
O(k2)
due to a failure
Merge overhead
Network Computing Laboratory | 25
O(k2)
Korea Advanced Institute of Science and Technology
Conclusions
Short end-to-end delay
Low control overhead
Efficient join and failure recovery
Low maintenance overhead
Network Computing Laboratory | 26
Korea Advanced Institute of Science and Technology
Critique
Strong Points
Exemplary Paper Organization
Clarify main contribution in introduction
Verbally describe protocol operation first
Analyze the operation overhead
Very thorough analysis
Weak Points
Stretch concerns
ZIGZAG scheme could incur longer stretches (max. 22)
Two main contribution ( fast recovery and control overhead) is marginal
performance improvement
Mostly benefited from their hierarchical architecture( same as NICE)
Is ZIGZAG really scalable?
O(k2) in node degree could easily overload upper layer nodes
Especially, when there are a large number of data sources (might be not considered)
Network Computing Laboratory | 27
Korea Advanced Institute of Science and Technology