Transcript Symmetrical Pair Scheme: a Load Balancing Strategy to

Symmetrical Pair Scheme: a Load
Balancing Strategy to Solve Intramovie Skewness for Parallel Video
Servers
Song Wu and Hai Jin
Huazhong University of Science &
Technology, Wuhan, China
1
Agenda
 Introduction
 Observations
 Symmetrical
Pair Scheme (SPS)
 Performance Evaluation
 Conclusion
2
Introduction
 Avoids
the load imbalance problem
caused by video popularity
 Use Coarse Grained Striping
 Parallel video servers divide video
objects into small segments
 Each server node store one of the
segment.
3
Introduction
Server Nodes
S[0]
S[1]
S[2]
Segment1
of Movie 1
Segment2
of Movie 1
Segment3
of Movie 1
Segment1
of Movie 2
Segment2
of Movie 2
Segment3
of Movie 2
4
Introduction
 The
viewing time of users are
different
 The access numbers of movie
segments are different
 Some segments are more popular
than others
 Intra-movie skewness
5
Introduction
 Solution
1: Fine Grained Striping
Server Nodes
S[0]
0
S[1]
1
S[2]
2
…
…
998
999
0
1
2
…
997
…
…
…
997
998
999
6
Introduction

Problem of Fine Grained Striping :
– Stripe unit size is very small
– Reduce the system throughput
– Reduce the amount of concurrent session

Goal of the paper:
– Study the characteristic of intra-movie
skewness
– Propose a data placement strategy with loadbalancing performance based on the analysis
results
J. Gafsi, E. Biersack, “Data Striping and reliability aspects in distributed video servers,” Cluster
Computing 2(1), pp. 75-91, 1999
7
Observations
 Data
Analysis:
– Source: log files from the video server
located in the CCRNC (Center China
Regional Network Center)
– Information in the log files: the viewing
time of all viewer
– Number of movie analyzed: 48
– Length of log files analyzed: 3 months
8
Viewing Time (minutes)
Observations
Different User
9
Segment Access Number
Observations
Movie Segment
10
Observations

Classification of segments
– Buffering segments
 Segment
within the buffering time, Tb
 User seldom stop watching during that period
 Period: 0 to Tb
– Leaking segments
 After
buffering time, segment access number
decreases sharply and almost linearly until a
particular time, leaking time Tl
 Period: Tb to Tl
11
Observations
– Normal segments
 Users
seldom stop watching during that
period
 Period: Tl to Tp (Duration of the movie)
12
Symmetrical Pair Scheme
 Notations:
– N: the number of server node in the
parallel video server
– S[i]: the i-th server node in the parallel
video server
– M: the number of movie in the parallel
video server
– mi[j]: j-th movie segment in i-th movie
13
Symmetrical Pair Scheme
 Buffering
segments:
– Distributes the buffering segments
uniformly
– Segment length is Tb/N
– The buffering segment mi[j] located on
S[j], j=0,1,…,N-1
14
Symmetrical Pair Scheme
 Leaking
Segments
– Segment Length: (Tl-Tb)/N
– If i mod 2 == 0
 Mi[N+j]
mod N]
located on S[((i div 2)mod N +j)
– Else
 Mi[N+j]
located on S[((i div 2)mod N + N -1
–j) mod N]
15
Symmetrical Pair Scheme
 Normal
Segments
– Segment Length: (Tp-Tl)/(x*N) where x
is the granularity factor and its value
depends on the system configuration
– Distributed uniformly on each server
16
Symmetrical Pair Scheme
17
Performance Evaluation

Compare SPS with the traditional round robin method
Layout of leaking
segments using
traditional round
robin manner
Layout of leaking
segments using SPS
18
Performance Evaluation
Let L[i] be the load of the i-th server node
 L[i] = sum of access numbers of segments
located on the node
 Let Lb[i], Ll[i], and Ln[i] respectively
represents the sum of access numbers of
buffering , leaking and normal segments
located on the i-th node
 L[i] = Lb[i] + Ll[i] + Ln[i]

19
Performance Evaluation
 Lb[0]
≈ Lb[1] ≈ … ≈ Lb[N-1]
 Ln[0] ≈ Ln[1] ≈ … ≈ Ln[N-1]
 Focus on Ll[i] only
 Metric:
– UD (Unbalance Degree)
– UD = max{| Ll[i] - Ll[j]|} (i, j =
0,1,…,N-1)
20
Performance Evaluation
 Assumption:
– The decrease of access number in the
leaking segments is linearly and the
slope is k
– All movie has the same slope k
 Let
A be the access number of the
most popular leaking segment.
 UD change periodically
21
Performance Evaluation
For round robin:
– UDRB = (N*M-M2)*A*k, M=0,1,…,N-1
– UDRB reach its maximum value of N2Ak/2 when
M=N/2 or (N2-1)AK/4 when M=(N+1)/2 or M=(N1)/2
Unbalance Degree

Number of Movie
22
Performance Evaluation
For SPS:
Unbalance Degree

Number of Movie
23
Maximal Unbalance Degree
Performance Evaluation
Number of Server Node
24
Performance Evaluation
 Mirror
SPS
25
Conclusion



Analyze the characteristic of intra-movie
skewness
Symmetrical Pair Scheme has better balancing
performance compared to traditional round
robin placement
Future work:
– The impact of intra-movie skewness on the
caching policy
– The relationship between intra- and intermovie skewness
26