A Staggered-Push Parallel Server Architecture - Scalable Continuous Media Streaming Systems - page 234

next micro-round is available is

N S − m

V 1 = Pr next round available | P 0 }= (12.45)

{

N S − 1

This is also the probability for a client to wait one additional micro-round provided the
assigned micro-round is already fully occupied. It can be shown that the probability for a client
to wait k additional micro-rounds provided that the first k assigned micro-rounds are all fully
occupied is

N S − m

V k = Pr { ( k + 1)th round available | P k }= 1 ≤ k ≤ m (12.46)

N S − k

We already know P 0 , and it can be shown that the probability for the first k micro-rounds
all being fully occupied is given by

m

k − 1

− i m !( N S − k )!

P k = =

k )! ,

1 ≤ k ≤ m (12.47)

N S − i N S !( m −

i = 0

Hence, we can solve for the probability of a client having to wait k additional micro-rounds
from

W k = Pr { ( k + 1)th round free | P k } P k (12.48)

( N S − m ) m !( N S − k − 1)!

= , 1 ≤ k ≤ m

N S !( m − k )!

Therefore, given m - the number of micro-rounds that are fully occupied - the average
number of micro-rounds a client has to wait can be obtained from

T F

1

N S

W avg ( m ) = kW k + + (12.49)

k = 1

where the second term accounts for the additional delay as described in Theorem 12.1. Sim-
ilarly, given n - the number of active video sessions - the average number of micro-rounds a
client has to wait can be obtained from

N S − 1

M avg ( n ) = W avg ( j ) P full ( n , j ) (12.50)

j = 1

And the corresponding average scheduling delay given a system utilization of n is

M avg ( n ) Q
R V

D S = (12.51)

Substituting equations (12.43), (12.48), (12.49), and (12.50) into equation (12.51) gives the
desired result.