Soft Scheduling - Scalable Continuous Media Streaming Systems - page 70

4.4.2 First-Block Replication
To further improve the chance of successfully admitting a new stream into the current round
and to simplify the disk scheduler, we can use a technique called First-Block Replication
(FBR) which replicates the first data block of a media stream to both the innermost track and
the outermost track. With this technique, we can guarantee that request for a new stream will
always be located downstream in the disk head scanning direction.
Moreover, as the disk head has to be repositioned to the platter edge at the end of a service
round, seek time for the new request is eliminated as well. The residual service time with FBR
can be computed from

f seek (

u − 1

Q
r j + 1 +

t j + 1
latency

= v j + 1 − v j ) +

j = w

+ f seek ( N − v u ) + t residual (4.18)

Q
r u + 1 +

t u + 1
latency

+

and the scheduler can admit the new stream immediately if the round does not overflow.
The significance of FBR is that it guarantees that the data block of the new stream will be
located downstream in the scanning direction. Consequently, rather than using the worst-case
to estimate round overflow as in equation (4.14), we can approximate the probability of round
overflow by the round-length distribution

δ = Pr { overflow }

(4.19)

= 1 − F round ( T r , u + 1)

which is a conservative measure as the disk head has already scanned past some tracks.
Using equation (4.19) we can then compute the average scheduling delay under EAS + FBR

from

= .

5 T r δ +

. − δ

D 1 0 5 T r (1 )

(4.20)

≈ .

0 5 T r

for small .

Therefore, together Early-Admission Scheduling and First-Block Replication can reduce
the scheduling delay by two-thirds for small

δ

. The trade-off is the additional storage required
to replicate the first data block of each media stream, which is relatively insignificant, given
the size of typical media streams. For example, the overhead for a one-hour MPEG1 video of
bit-rate 150KB/s and block size 128KB is only 0.024%. Note that we can extend this FBR
technique to replicate additional blocks within a media stream, such as the first block in the
beginning of a seekable chapter to achieve similar admission-delay reduction when performing
interactive playback controls (e.g., chapter selection).
To quantify the gain of FBR, we assume that an admission delay constraint D max is given
as part of the service requirement. Then we must ensure that the expected admission delay is

δ