we choose the average number of chunk delivery in one
slot as the performance metric to evaluate chunk selection
algorithms.
In basic model, every slot is divided into two phases,
and if a peer’s request queue is not empty after service re-
quest phase, this peer can schedule one request and upload
a chunk in the following service response phase. In this
case, this peer’s upload capacity is utilized, and we can ex-
press the average number of chunk delivery in one slot as:
C ¼
X
N
i¼1
PrðY
i
P 1Þð1Þ
Our objective is to maximize C to improve system perfor-
mance by designing efficient chunk selection algorithm.
In fact, Eq. (1) is equivalent to C ¼
P
N
i¼1
ð1 PrðY
i
¼ 0ÞÞ ¼
N
P
N
i¼1
PrðY
i
¼ 0Þ, so we can transform the maximization
problem of Eq. (1) to the minimization problem as follows:
min
X
N
i¼1
PrðY
i
¼ 0Þ
s:t :
X
M
j¼1
k
j
6 N
ð2Þ
Where the constraint of Eq. (2) indicates the sum of all
chunk requests does not exceed the number of peers.
However, it is difficult to solve Pr(Y
i
= 0) in many cir-
cumstances, and we have to modify the optimization
problem of Eq. (2). We know X
i
will influence the distri-
bution of Y
i
, because X
i
is the request number that peer i
receives in each service request phase, and as long as
X
i
– 0, Y
i
will be larger than 1. For peer i,ifE[X
i
] > 1, this
peer can receive enough requests in service request
phase and its upload bandwidth will be adequately uti-
lized, but some peers may be unable to serve all requests
they receive due to overload. On the other hand, E[X
i
]<1
makes peer i have light load, and peer i may not upload
chunk in some slots, and its bandwidth utilization will
decline with the decrease of E[X
i
]. Meanwhile, we know
P
N
i¼1
X
i
¼ N from the definition of X
i
, so the optimal solu-
tion for Eq. (2) exists only if the following condition is
satisfied:
E½X
i
¼1; for all 1 6 i 6 N ð3Þ
However, chunk selection algorithm will result in the dis-
crepancy of X
i
among peers, and greater discrepancy brings
more overload peers and light-load peers, which prevents
the utilization of peer resources. Therefore, we transform
the minimization problem of Eq. (2) to a new optimization
problem, and it can be expressed as:
min VarðE½X
i
Þ; 1 6 i 6 N
s:t :
X
M
j¼1
k
j
6 N
ð4Þ
As a result, our goal is to design an optimal chunk selection
algorithm to minimize the variance of chunk requests re-
ceived by different peers, and achieve the objective of per-
formance optimization.
4. Analysis on chunk selection algorithms
When a peer decides which chunk should be down-
loaded, it will choose one peer from the peer set in which
peers have derived this chunk, and send request to it. For
those peers in the set, the number of requests that they re-
ceive in one slot conforms to Binomial distribution. We as-
sume the probability that system generates n requests of
B(j)isPrðk
j
¼ nÞ. According to law of total probability, the
probability that every peer in the set receives m requests is
PrðR
j
¼ mÞ¼
X
N
n¼m
PrðR
j
¼ mjk
j
¼ nÞ Prðk
j
¼ nÞð5Þ
where PrðR
j
¼ mjk
j
¼ nÞ¼
n
m
1
jS
j
j
m
1
1
jS
j
j
nm
.
In addition, we assume the relation between peer i and
B(j) is as follows:
d
ij
¼
1; i 2 S
j
0; i R S
j
ð6Þ
So the expectation of requests that peer i receives in one
slot is:
E½X
i
¼
X
M
j¼1
d
ij
E½R
j
ð7Þ
In the following section, we analyze the impact of dif-
ferent chunk selection algorithms on Eq. (7).
4.1. Deterministic chunk selection algorithms
There are some existing chunk selection algorithms in
P2P applications, where rarest first algorithm and greedy
algorithm are the representatives. In rarest first algo-
rithm, peers prefer to choose the rarest chunk in the sys-
tem, while greedy algorithm selects chunk based on
playback deadline. In our basic model, all peers compose
a completely connected overlay, and earlier chunks have
been disseminated for several slots, so the number of
those chunks is absolutely not less than the newly gen-
erated chunks, which will cause all peers select B(1) in
rarest first algorithm. In contrast, the order that peers
choose chunks with greedy algorithm is from B(M)to
B(1). Rarest first algorithm has been employed in Cools-
treaming [1], while Greedy algorithm is proposed in
GPSA [22]. The two algorithms can decide the target
downloading chunk explicitly based on what the peer
has in its playback buffer, so we label them as determin-
istic chunk selection algorithms.
4.1.1. Rarest first algorithm
From the property of rarest first algorithm, we know all
peers except one peer that has already received B(1) from
streaming server will ask for B(1), and the exceptive peer
will request another chunk which is the nearest to B(1)
but still missing. Therefore, the request arrival rate of each
chunk is:
k
1
¼ N 1;
X
M
j¼2
k
j
¼ 1 ð8Þ
3012 C. Hu et al. / Computer Networks 57 (2013) 3009–3024