Soft Scheduling - Scalable Continuous Media Streaming Systems - page 65

service round length will be extended beyond T r seconds and consequently will reduce the
overflow probability.
Let the length for round x be t x and further assume that the next round x + 1 is overflowed,

i.e., t x + 1 > T r . If the length of round x is less than or equal to (2 T r − t x + 1 ), then we can

+

1 simply by starting it ( t x + 1 − compensate for the longer service round x T r ) seconds earlier

than normal.
Let B early be the number of extra buffers (each Q bytes) available for storing these early-
retrieved media blocks. Then the disk scheduler can be modified as follows. If the current
round finishes early (i.e., round length shorter than T r ), then the disk will immediately proceed
to retrieve data blocks of the next round. This process continues until either the extra buffers
are exhausted, or all data blocks in the next round are completely retrieved. On the other hand,
no special operation is needed if the current round does not finish early (either round length
equals T r or round overflows). We analyze the capacity gain in Section 4.3.2 next, and derive
an upper bound for B early in Section 4.3.3.

4.3.2 Performance Modeling
To quantify the improvement, reconsider the round lengths for any two consecutive disk service
rounds. As data placement is random, the service round lengths for any two disk service rounds
are independent and identically distributed according to F round ( t , k ). Let

f round ( t , k )bethe

density function of F round ( t , k ) and let F (2) k ) be the distribution of the sum of two service

round lengths, which is the auto-convolution of F round ( t , k ):

round ( t

,

∞

F (2)

round ( t

, k ) = F round ( t − x , k ) f round ( x , k ) dx (4.4)

−∞

Now consider an arbitrary service round i . With DRS, round i can overflow under two
conditions. First, if round ( i 1) does not overflow, then round i will overflow only if the

combined round lengths are longer than 2 T r :

−

Pr { ( t i + t i − 1 ) > 2 T r | t i − 1 ≤ T r } ≤ Pr { ( t i + t i − 1 ) > 2 T r }

(4.5)

F (2) = 1 −

round (2 T r ,

k )

Second, if round ( i 1) does overflow, then it will be truncated to at most T r (see Section 4.5.2).

In this case, round i overflows if it is longer than T r :

−

Pr { t i > T r | t i − 1 > T r } = 1 − F round ( T r , k ) (4.6)

Hence the overflow probability of round i , denoted by ( k ), can be computed from

( k ) = Pr { t i > T r }

= Pr { ( t i + t i − 1 ) > 2 T r | t i − 1 ≤ T r } Pr { t i − 1 ≤ T r }

+ Pr { t i > T r | t i − 1 > T r } Pr { t i − 1 > T r } (4.7)

1

k ) F round ( T r , k ) + (1 k )) 2 F (2)

≤ −

round (2 T r ,

− F round ( T r ,