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

problem by an over-rate transmission scheme. Our results showed that the over-rate trans-
mission scheme can effectively prevent traffic overlapping with a small bandwidth overhead
under clock jitter bounds achievable by existing software-based synchronization algorithms.
Moreover, we showed that the server buffer requirement, the client buffer requirement, and
the server bandwidth requirement are all independent of the number of servers in the system.
The average system response time, though it increases slightly with more servers, remains
acceptable if we limit the system to less than full utilization. These results demonstrate that
the proposed architecture can be scaled up to large number of users without costly upgrade to
the existing servers and clients.

Appendices
A.1 Proof of Theorem 12.1
Let t i be the local time a new request arrives at server i (0

≤ i < N S ), t A be the local time

the new request arrives at the admission scheduler, and be the extra scheduling delay (in

number of micro-rounds). Then the admission scheduler will attempt to admit the request
to micro-round n A as given in equation (12.3). For server i , the new request arrives during
micro-round n i = N S ,

i.e., the assigned micro-round has not been started in any of the servers. Using this condition,
we can then obtain the following inequality:

t i / T F . Hence, the problem is to find so that n A > n i for 0 ≤ i <

n A > n i (12.34)

Expanding gives

t A
T F

t i
T F

+ 1 + > (12.35)

Rearranging gives

t i
T F

t A
T F

> − − 1 (12.36)

− ≤ − ≥

Applying the inequality x y x y : x , y 0, to R.H.S. of equation (12.36) we

can then obtain

t i
T F

t A
T F

t i
T F −

t A
T F

− − 1 ≤ − 1 (12.37)

Since clock jitter is bounded: | t i − t A | ≤ τ , for 0 ≤ i < N S , we can rewrite equation (12.37)

in terms of τ :

t i
T F −

T F

t A
T F

− 1 ≤ − 1 (12.38)