Soft Scheduling - Scalable Continuous Media Streaming Systems - page 64

Table 4.1 ( Continued )

Description Symbol Notes

Residual service time of a round nps for non-preemptive scheduling

ps for preemptive scheduling

Arrival time for a new request t new Variable, in seconds

End time for the current service
round

t due Variable, in seconds

Seek function, including both seek
time and fixed overhead

f seek ( k ) k is seek distance in number of tracks

Probability of round overflow under
First-Block Replication

δ Computed

Expected scheduling delay D Computed, in seconds

Scheduling delay constraint D max Parameter in seconds

Retrieval deadline for request i d i Computed, in seconds

Size of partial block retrieval during
round overflow

Q d Computed, in bytes

randomization is necessary to prevent correlated overflows from one service round to the next.
To see why this randomization process is needed, let us assume that media blocks from a
media stream are stored sequentially in the disk. Now suppose a new stream joins the system
at round i and causes the service round to overflow (i.e., length of service round exceeding
T r ). Then due to the sequential data placement, the next round will have requests in similar
locations, and hence will likely experience overflow as well. Randomized placement can
break up spatial correlation between requests from consecutive service rounds and thus avoid
correlated overflows.
In practice, the entire placement information for a media stream can be stored in an index
file. Assume 16 bits are used to store the beginning sector number for a media block. Then a
2GB media stream stored in 128KB blocks will consume 32KB to store the index file, which
is negligible compared to the size of the media stream. Hence, the server can simply load the
entire index file into the memory at the time of stream admission.

4.3 Dual-Round Scheduling
The previous soft-scheduling approach in general can achieve better usable disk capacity
than hard scheduling at the expense of a small probability of service round overflow. In this
section, we present a Dual-Round Scheduling (DRS) technique to further reduce this overflow
probability so that even more streams can be admitted.

4.3.1 Read-Ahead Algorithm
We observe that in practice the majority of the service rounds are shorter than the maximum
limit T r . This is necessary to keep the overflow probability within the given threshold .Now

during this slack time the disk is in fact idle. Thus, instead of wasting the otherwise unused
disk time, we can start the retrievals for the next service round earlier. In this way the next

ε