Soft Scheduling - Scalable Continuous Media Streaming Systems - page 80

4.7 Related Work
The principle of statistical multiplexing is not new and has been applied in many different
areas. In this section, we briefly review the related literature.
Vin et al . [7] proposed a statistical admission control algorithm for multimedia servers.
Their admission control algorithm used disk round-length distribution and request size
distribution to admit more streams than deterministic admission control algorithms. Their
simulation results showed that substantially more streams can be admitted compared to the
deterministic case. Instead of using empirical distributions, Chen and Little [8] took an ana-
lytical approach to derive the disk round length function and then use Chebychev's Inequality
to obtain statistical bounds. By allowing a small probability of overflow, their results also
showed performance gains over conventional hard-scheduling algorithms. Note that both stud-
ies assumed disks without zoning. A more recent work by Nerjes et al . [9] incorporated
zoning into their analytical disk model and used the method of Chernoff bounds to obtain
tighter statistical bounds for the SCAN scheduling algorithm. These pioneering works on
statistical admission control all focused on achieving better usable disk capacity by exploit-
ing the statistical behavior of the disk's service-round length. The key differences are in
the way the disk's service-round length is modeled and in the way statistical bounds are
obtained.
Other researchers have studied the disk zoning problem in isolation of the admission control
problem. For example, Birk [10] proposed a data layout technique called Track-Pairing for me-
dia servers with multi-zone disks. Under Track-Pairing, a media stream is placed alternatively
between tracks in the outer zones and matching tracks in the inner zones. During retrieval,
tracks from both zones will be retrieved in a cycle so that a more uniform disk throughput can
be obtained. Another study by Ghandeharizadeh et al . [11] proposed a placement algorithm
called FIXB where media blocks are striped across all disk zones in a round-robin manner.
Media blocks are then retrieved from every zone in a disk cycle so all zones will be utilized
to contribute to the average throughput. There are also other methods such as Logical Track
[12] and deadline-driven techniques [13] for tackling this disk zoning problem but these stud-
ies did not investigate statistical admission control issues in the context of continuous-media
servers.
4.8 Summary
In this chapter, we presented a soft-scheduling approach to increase disk efficiency in
continuous-media servers. Our results obtained from detailed simulations demonstrated that
existing hard-scheduling approaches sacrifice substantial disk efficiency for scheduling sim-
plicity. This is particularly significant for disk drives with zoning. Capacity gains in the
range of 20% to 40% are achievable by soft scheduling. With the additional dual-round
scheduling technique, usable disk capacity can be further increased by another 10-20% de-
pending on disk models and system parameters. In addition, the Early-Admission Schedul-
ing technique allows the use of much larger block size without adversely increasing the
scheduling delay, thus further increasing disk efficiency. Finally, we also presented proce-
dures for detecting and recovering from round overflow, which are necessary for practical
implementations.