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

Hence, if

T F

> − 1 (12.39)

or at least

T F

= (12.40)

then the assigned micro-round is guaranteed not to have started in any of the servers.

A.2 Derivation of the Average Scheduling Delay
Assume that video sessions start independently and with equal likelihood at any time. Then
a video session can be assigned to any one of the N S micro-rounds with equal probability.
Assume that there are n active video sessions, then the number of ways to distribute these n
video sessions among N S groups is a variant of the urn-occupancy distribution problem [4]
and is given by

1) j N S
j

N S +

N S

n − j ( + 1) − 1

N ( n , N S , ) = ( − (12.41)

N S − 1

j = 0

To obtain the probability of having m fully-occupied micro-rounds, we first notice that

there are N m possible combinations of having m fully-occupied micro-rounds. Given that,
the number of ways to distribute ( n m ) micro-rounds

with none of those micro-rounds fully occupied can be obtained from equation (12.41) as
N ( n

− m ) video sessions among ( N S −

1). Hence, the total number of ways for exactly m of the micro-
rounds fully occupied is given by

− m , N S − m , −

N S
m

N ( n

N full ( n , m ) = − m , N S − m , − 1) (12.42)

Hence, the probability of having m fully-occupiedmicro-rounds given n active video sessions
can be obtained from

N full ( n , m )

P full ( n , m ) = (12.43)

N ( n , N S , )

Assume that m out of N S micro-rounds are fully occupied, then, the probability for the
assigned micro-round to be available (not fully occupied) is given by

N S − m

V 0 = (12.44)

N S

V 0 ) will be the probability of the assigned micro-round being fully occu-
pied. Now provided that the assigned micro-round is fully occupied, the probability that the

Hence, P 0 = (1 −