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

Macro-Round

Micro-Round (N S per m a cro-round)

∆ = 1

Not full

Max delay = N S + + 1 micro-rounds

∆

Full

Figure 12.6 Worst-case delay in the admission process

Proof. Please refers to Appendix A.

For example, let t A be the local time the new request arrives at the admission scheduler. Then
the admission scheduler will attempt to admit the request to micro-round

t A
T F

n A = + 1 + (12.3)

Note that we need to add one to n A because a new request cannot join the current micro-
round (it has started already). If the assigned micro-round is full, the admission scheduler will
sequentially check the subsequent micro-rounds until an available micro-round is found. In
the worst case shown in Figure 12.6, the transmission of the first video block will be delayed
for ( N S + +

1) micro-rounds:

T F N S +

T F

1 D S = + (12.4)

To better evaluate the delay incurred, we can derive the average scheduling delay under a
given server load. Assume that there are n (0 N S ) active video sessions, then it can

be shown that (see Appendix A.2) the average scheduling delay is given by

≤ n ≤

N S

1 N full ( n

T F

N S − 1

Q
R V

k ( N S − j ) j !( N S − k − 1)! , j )

D S = + + (12.5)

N S !( j − k )! N ( n , N S , )

j = 1 k = 1

where

1) j N S
j

N S +

N S

n − j ( + 1) − 1

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

N S − 1

j = 0