Transcript P2VoD: Providing Fault Tolerant Video-on

P2VoD: Providing Fault Tolerant
Video-on-Demand Streaming in
Peer-to-Peer Environment
Tai T.Do, Kien A. Hua, Mounir A. Tantaoui
Proc. of the IEEE Int. Conf. on Communications (ICC 2004)
Outline
 Introduction
 Related Work
 Architecture of P2VoD
 Performance Evaluation
 Conclusion
2
Introduction
 P2P approach can potentially solve many
serious problems posed in existing streaming
systems


Infeasibility of IP Multicast
Network bottleneck at the video server
 Several projects on “live streaming”
 Not trivial to apply these techniques into VoD
systems
3
Introduction (cont.)
 Live streaming
 Shorter end-to-end delay, more lively the stream
 Short tree rooted at the video server
 User simply joins an on-going live streaming
session
 User may not quit if QoS degrades
 VoD streaming
 Liveness is irrelevant, video is pre-recorded
 Whole video must be delivered
 User will stop watching if QoS degrades
4
Introduction (cont.)
 Proposed techniques not based on any
existing live streaming systems
 Problems to be solved for a P2P VoD
streaming system




Fast and localized failure recovery without jitter
Quick join
Effective handling of clients’ asynchronous
requests
Small control overhead
 P2VoD (Peer-to-Peer approach for VoD
streaming)
5
Related Work: P2Cast
 Architecture uses a P2P approach to stream video
using patching
 Build application level multicast tree

Server streams the entire video over base tree
 P2Cast clients provide two functions


Base stream forwarding
Patch serving
 Base tree construction & patch server selection
algorithm



Best Fit (BF): find the “fattest pipes” to requesting clients
BF-delay: also use network delay information
BF-delay-approx: not using actual available bandwidth, (1 or
0 represents enough bandwidth or not)
6
Architecture of P2VoD
 A streaming connection is assumed to
constant bit-rate

equals to the playback rate of the video
 Retrieval block (R-block) as a data unit of the
video

equivalent to one unit of playback time
 Each client has a buffer, whose maximum
size is worth of MB units of playback time (i.e.
MB R-block)
7
Architecture of P2VoD (cont.)
 abX : actual amount of buffer storage used by
a client X

1 ≤ abX ≤ MB
 By using the cache, early arriving client can
serve late coming clients by forwarding the
stream


tjX : the joining time of a client X
X can serve clients whose joining time

[tjX , tjX + abX ]
8
P2VoD system
 abC1 = MB = 5, abC4 = 3 < MB
 When C6 arrives to the system at time 3, the first
R-block of the video is still in the buffer of C1
 C1 can serve the video stream to C6
9
Architecture of P2VoD (cont.)
 “Generation”
 Group of clients having the same smallest
numbered R-block in their caches
 Generations are also numbered
 G1 as the oldest generation to Gn as the youngest
generation
 Clients in these generations, excluding the
server, form a video session

A video session is closed

none of the clients has the first R-block of the video
10
P2VoD system
 C1, C2 , C3 , C4 , and C5 all have the same smallest
number R-block
11
Data Caching and Generation (cont.)
 Rules to build generations



Generations are indexed by numbers starting from 1
Members of a lower indexed generation arrive to the system
no latter than any member of other higher indexed
generations
A peer in generation i-th (i > 1) receives the video stream
from a peer in generation (i – 1)-th


Peers at the first generation receive the video stream directly
from the server
When joining a video session of the system, a new peer


belongs to the current highest numbered generation, OR
be the first member of a newly created generation of that video
session
12
Data Caching and Generation (cont.)
 Caching scheme with the generation concept
 X and Y join the same generation at time tjX and tjY


Caching Rule: The difference of actual cache sizes used by
two peers in the same generation must offset the difference
in their arrival times
abX – abY = tjY – tjX
E.g. abC2 = abC1 – (tjC2 – tjC1)
= 5 – (1 - 0) = 4
13
Data Caching and Generation (cont.)
 Assume that at time
36, peer C3 fails.
 C1, C2, C4, C5 available
to C8
 allow a quick and
localized recovery for
C8
14
Control Protocol
 Control Protocol is required to maintain the system
connectivity
 Neighbors of peer X



Siblings (peer in same G): need to keep a list of their IP
addresses
 Periodically update the list
 Update the list on-demand (joining/leaving)
Child: agree to forward the video stream, X needs to send
the IP addresses of X and its siblings to its child
Parent: first join the system, X sends the IP address to its
parent
X
t
 X sends control information < addX, G(X), exp > to
server when joining the system
X
 t exp : expiration time when the first R-block of the
video is no longer in the cache of X
15
Join Algorithm
 Server S has the list of peers at the youngest
generation for each video session, denoted
as Gy
Gy
 Expiration time t exp is the same for every
member of the youngest generation
 Initially, when the system is empty


Gy
t exp
is set to minus infinity
Set of youngest generation peers contains only S
16
Join Algorithm (cont.)
 Case 1
 If all of the existing video sessions are closed, X
will be admitted if server S still has enough
outbound-bandwidth
 Otherwise, X will be rejected
 Case 2
 For the case where there is at least one existing
video session still open, X will try to join that video
session
17
Join Algorithm (cont.)
 Case 2 proceeds as follows.
 Step1



Step2:



X contacts a random member of the Gy set
acquires the list of peers at the super generation of Gy.
If texp at the super generation > tjX, then go to Step3
Otherwise go to Step4
Step3: (generation not expired)


X selects a parent from the super generation
If such a candidate exists, X becomes a member of Gy
 X starts receiving the video stream from its selected parent
 X sets its actual cache size abX to conform to the caching rule

Otherwise go to Step4
18
Join Algorithm (cont.)
 Case 2 proceeds as follows.
 Step4: (generation expired)





A new generation is formed below Gy
X becomes the first member of that generation
Actual cache size abX is set to equal to MB
X selects a peer from Gy as its parent
If no such peer exists, X tries other open video sessions
or contacts the server
19
Parent Selection Criteria
 Round Robin Selection


promote the fairness among peers
the requesting peer should select a peer, who hasn’t served
any client for the longest period of time
 Smallest Delay Selection


minimize the joining time of the requesting peer
the requesting peer picks the first peer in the candidate
group, who has enough out-bound bandwidth
 Smallest Distance Selection


reduce the number of links involved in the underlying
network
the requesting peer chooses a peer, who has enough outbound bandwidth and closest to it
20
Failure Recovery
 P2VoD uses a two-phase failure recovery
protocol
 1) Detecting failure


Grateful failures: When a peer leaves the system,
it forwards the LEAVE_MESSAGE to its children
Unexpected failures: it happens unexpectedly
without any explicit warning, peers in P2VoD are
required to monitor their incoming traffic
21
Failure Recovery (cont.)
 2) Recovering from failures
 Failure at a peer X, the whole sub-tree under X is
affected
 The rest of the sub-tree are informed to wait
through the WAIT msg
 A disrupted peer X finds a new parent





X contacts the siblings of its parent
If no such parent exists, X contacts the server
Otherwise, X is rejected
X succeeds, the sub-tree is recovered
X fails, the immediate children of X will invoke the
recovery process
22
Performance Evaluation
 Examine the effects of two
parameters in P2VoD:


max number of clients allowed in
the first generation of each video
session, K
max buffer size each client can use,
MB
 Compare P2VoD with P2Cast
 Network topology using GT-ITM
 Clients arriving to system follow
the Poisson distribution
 one Transit network (with 4 nodes)
 12 stub domains (with 96 nodes)
 backbone link support 25 streams
 edge link support 7 concurrent streams
23
Performance Evaluation (cont.)
 Rejection probability
 probability that a client tries to join the system but
can not get the service
 Server stress
 amount of bandwidth used at the server, or the
number of streams established at the server
 Number of contacts during the recovery
 number of nodes a client has to contact during the
recovery process
24
Rejection probability for various
maximum buffer sizes (K = 3)
 MB is varied from 0.1 to 0.4 of the length of the video
 When doubling size of MB, the rejection probability is reduced by half
25
Server stress with various values of K
(MB = 0.1)
 In light workload, almost every clients get the video stream directly from
the server
 In heavy workload, most clients get the video stream from some other
client, not the server
 With small K, a failure at the
first generation will likely
cause disruption the whole
video session
 With large K, such failure
only cause a portion of the
video session to be in
recovery mode
26
P2VoD vs. P2Cast: Client rejection
probability
 P2VoD use K =6 & MB = 0.2
 The threshold for P2Cast is set at 0.2.
 P2VoD outperforms BF because P2Cast requires each client to obtain
two streams
27
P2VoD vs. P2Cast: Server stress
 In P2VoD, a video session is open as long as clients in the Gy still have
the first block of the video buffer
 In P2Cast, a video session is open for a short period of time starting
when the first client join the video session and last for the length of the
threshold
28
P2VoD vs. P2Cast: Failure overhead
 Clients arrive to the system at a rate of 0.4 per second during a period
of 2 hours (3516 clients)
 When the failure probability increases, the number of clients contacted
during a recovery decreases


more clients leave the system, network bandwidth is also released
easier for an affected client to find a new parent
29
Conclusion
 P2VoD, a new system for Video-On-Demand
streaming in a Peer-to-Peer environment
 the concept of generation and caching scheme
to deal effectively with failures
 An efficient control protocol help P2VoD to
allow clients join the system fast, as well as to
recover failures in a quick and localized
manner
 Simulation-based performance study shows
that P2VoD is superior than P2Cast
30