Scheduling and Optimization of the Delivery of Multimedia Streams Using Query Scripts.
New techniques are necessary to satisfy the high bandwidth requirement and temporal relationships of multimedia data streams in a network environment. Clients can experience gaps between the multimedia data streams during presentations as the multimedia server services multiple clients. This variable delay occurs between the end of one multimedia stream and the beginning of the next multimedia stream because client requests are queued awaiting service. This leads to interruptions and discontinuities of the client's presentation. Special techniques are necessary to manage the temporal relationships between multimedia streams in distributed environments. In this paper we propose two scheduling algorithms for delivering multimedia streams by using the query script, which is a multimedia database interface for clients. A client can specify all the multimedia objects that make up the presentation and their temporal relationships in a query script. Once submitted, the information in the query script is used by the multimedia database system to schedule and optimize the delivery. Using simulations we analyzed the performance of the proposed delivery scheduling algorithms and the predelivery optimization method. The simulation results show that delivery scheduling algorithms satisfy the specified temporal relationships between multimedia streams while maintaining better use of system resources.
Introduction
Multimedia information systems require new data modeling and delivery
capabilities to specify and guarantee temporal relationships between
streams [7]. These capabilities are more critical in distributed
computing systems due to multimedia data's high resource require-
ments. In this paper we propose the use of query scripts as the interface
between clients and multimedia database systems for specifying the delivery
of multimedia data. Query scripts allow clients to make a retrieval
This research was supported in part by NCR, Lexis-Nexis, and NSF under
Grant No. CDA-9601670.
c
2001 Kluwer Academic Publishers. Printed in the Netherlands.
S. T. Campbell and S. M. Chung
request consisting of a set of multimedia objects and their temporal
ordering to the multimedia database system. The information given in
the query script enables the database system to reserve su-cient disk
bandwidth, memory, and other system resources in order to meet the
client's request.
In our approach, a database management system (DBMS) is combined
with a multimedia server. The DBMS provides the data modeling
and manages key information about the multimedia data, while the
media server stores and delivers multimedia data as atomic objects. For
example, relational database systems can support multimedia through
the use of binary large objects (BLOBs). A BLOB is an unstructured
storage string that the database system treats as an atomic object.
The database schema manages access to the data in the BLOB by
storing a pointer to the BLOB. Object-oriented database systems can
support more accurate modeling and better integration of multimedia
data, but again they eventually store each multimedia data object as a
sequence of data. In both cases, in order to satisfy the delivery timing
requirements of multimedia streams, usually specialized media servers
handle the actual storage and delivery of multimedia objects.
A media server is a shared storage facility that is capable of
isochronous delivery of multimedia data. Isochronous delivery guarantees
that a new packet of data is available at the client in time to
present the next video frame or audio data. Additionally the media
server incorporates the server-push methodology as opposed to the
more traditional client-pull methodology to minimize network tra-c
and extraneous client read requests [23]. In the client-pull case, the
client makes separate requests for each block of data. On the other
hand, in the case of server-push, a single request is made by the client
for a stream delivery, then the server continually transmits data blocks
of the stream. Media servers extend existing le system capabilities
by providing multimedia data placement strategies, bounded delivery
timing, guaranteed buer and media management, and special disk
retrieval techniques. Through these techniques the media server is able
to handle concurrent retrieval and transmission of multimedia streams
and supports multiple clients.
We claim that the relationship between a media server and a multimedia
database system develops just as the relationship between le
systems and traditional database systems has developed. Originally
the le system was the central data management component and applications
managed their own logical view of data. Gradually database
systems emerged to provide common data models, catalogs, dictionar-
ies, indices and other tools [8]. Thus the database system extended the
le system's management capability. We feel that a similar architec-
Delivery Scheduling of Multimedia Streams 3
tural hierarchy exists between multimedia database systems and media
servers, as shown in Figure 1. The media server provides basic storage
and delivery functions for multimedia data while the database system
adds necessary modeling and management functions. Additionally the
media server can deliver information directly to the client application
bypassing the database system.
File System
DBMS
Media
Server
Application
DBMS
File System
Application
Traditional Multimedia

Figure

1. Hierarchy of database systems
Specialized media servers are necessary to handle the delivery of multimedia
data since audio and video data are continuous. Video consists
of a continuous sequence of frames, and each frame needs retrieval,
processing and delivery within a strict xed time interval. Audio is
a continuous sequence of samples that needs conversion in a sample
interval. Delivery of multimedia data is dierent from the delivery of
traditional data since multimedia data is inherently presentational. In
other words, usually the purpose of multimedia data is for presentation
to users rather than for additional computational processing. Since
multimedia data is large, for example 10 seconds of VCR quality video
is about 1.5 MB, the client can not wait for the complete retrieval of the
object before beginning the presentation. Instead, the client processes
multimedia data in blocks as they arrive. This sequence of data blocks
delivered in regular time intervals constitutes a multimedia stream.
Delivery problems are related to many subsystems, but a major bottleneck
is the disk [17]. Disk subsystems do not guarantee data delivery
within the bounds necessary for the presentation of video and audio.
This is because the disk orders the requests to minimize seek times.
Hence the exact data delivery timing is dependent upon the current
set of requests and the locations of corresponding disk blocks. This
leads to random delivery timing, which is unacceptable for multimedia
data. Proper decoding of multimedia data requires that data always
be present for decoding when needed. The most common solution is
to retrieve one unit of data from the disk for each multimedia stream
during each xed disk service round, as in [9]. This scheme guarantees
4 S. T. Campbell and S. M. Chung
timely delivery as long as the total number of requested streams is
below a certain limit.
The problem with the delivery scheme using a xed disk service
round is that it is characterized as best-eort delivery and can lead to
a loss of the temporal ordering of the streams. With best-eort delivery
the media server attempts to satisfy all accepted requests but oers no
guarantees due to the stochastic nature of the retrieval process. For
example, if a client wants to display two streams simultaneously and
makes two separate requests, the rst can be accepted and the second
rejected. This loses the desired temporal ordering between the two
multimedia streams. The other major problem is large gaps between
streams which are supposed to be sequential. A best-eort delivery
system may accept the request for the rst stream from the client and
then immediately receive several requests from other clients which ll
the media server's capacity. Then, when the second multimedia stream
is needed by the client, the media server is busy and can not deliver it
immediately. This results in an undesired gap between the two streams
(called interstream latency), as shown in Figure 2.

Figure

2. Loss of temporal order
Some multimedia presentation systems address these temporal synchronization
problems [4, 25], but they do not deal with network based
delivery systems. They assume local storage systems in which they can
exert strict control over disk accesses. This assumption is not feasible
in a network environment where multiple requests arrive at a media
server from several clients. In the network environment, best-eort de-
Delivery Scheduling of Multimedia Streams 5
livery systems can not provide the necessary synchronization between
multimedia streams.
Our approach enables the client to request a set of multimedia
objects and specify their temporal order by using query scripts. Query
scripts contain enough information for the multimedia database system
to maintain the requested temporal delivery order. A query script spec-
ies the entire set of multimedia objects and their temporal ordering in
one request so that the system can create a delivery schedule and ensure
proper delivery. This delivery scheduling minimizes the unacceptable
latencies experienced with best-eort delivery systems.
In the remainder of this paper, we introduce the query script and
then propose two delivery scheduling algorithms, which are named scan
scheduling and group scheduling. The simulation results demonstrate
that the proposed delivery scheduling algorithms satisfy the specied
temporal ordering between streams while maintaining high system resource
utilization. We also analyze the eect of predelivery optimization
on the performance of the proposed scheduling algorithms.
2. Scheduling of Delivery Using Query Scripts
A query script has two parts, declaration and temporal ordering. The
declaration part uses object identiers to specify the multimedia data
objects to be delivered to the client. The temporal ordering part species
the timing relationships between the multimedia objects. There are
three basic temporal ordering actions: initiate streams, wait for streams
to complete, and terminate streams. Figure 3 shows an example of a
query script that declares four multimedia data objects for delivery.
Here video A plays to completion, then videos B and C play simulta-
neously. When video B completes, video C terminates even though it
is not nished yet, and then video D plays. More details about query
scripts are given in [5].
The query script can be used for the specication of synchronized
presentation of multimedia objects. The temporal relationships between
continuous media objects can be easily specied by using the
query script because it covers all the event-based synchronization requirements
[3]. Compared to other synchronization specication schemes,
the query script is quite easy to use, and it can be easily extended
by adding other synchronization constructs. For example, some timing
operations can be added to cover interval-based synchronizations. An
extensive survey and comparisons of dierent synchronization speci-
cation methods are given in [3].
6 S. T. Campbell and S. M. Chung

Figure

3. Query script example
A query script does not support detailed temporal synchronization
semantics because it is not a presentation language such as Fire
y [4],
MHEG [12, 19, 20], or HyTime [11]. We expect the client applications
to use these schemes to provide richer temporal and physical modeling
semantics and to use query scripts to make delivery requests that include
temporal relationships. The client application manages the nal
presentation timing using the presentation language while the multi-media
delivery system uses the query script to schedule and manage
the delivery timing.
The information in the query script provides the database system
with enough information to properly schedule the delivery. Scheduling
ensures that the query script's temporal ordering is met, no overcommitment
of system resources occurs, and optimized usage of system
resources. Best-eort delivery systems can not perform scheduling since
only the current set of requests is known and, once the system accepts
the requests, there is a contract to maintain their delivery. This leads
to random rejection of streams or lengthy gaps between multimedia
streams. With query scripts, the delivery manager can create a delivery
schedule since the entire delivery request of each client is specied.
Then the delivery manager is able to schedule the delivery of multimedia
objects and guarantee the desired performance by creating a
feasible schedule and using the predelivery optimization technique. The
predelivery optimization consists of prefetching disk blocks during the
periods of disk underutilization, so that we can start some query scripts
Delivery Scheduling of Multimedia Streams 7
2.1. Scan Scheduling
Delivery scheduling is the main reason for using query scripts. A delivery
schedule is a consolidated list of service intervals for the streams of
accepted query scripts. The delivery manager uses the information in
the query script to schedule the delivery of its streams by integrating
their service intervals into the current delivery schedule. A feasible
schedule is one that does not have any overcommitment of system
resources during the delivery of all the scheduled multimedia streams,
while satisfying the temporal orderings specied in the query scripts.
The media server uses this delivery schedule to control the delivery of
multimedia streams to the client workstations.
There are three major parts in the delivery manager of the media
server: the parser, the scheduler and the retrieval manager, as shown
in

Figure

4. The scheduling process starts when a client sends a query
script to the media server. The query script is parsed into a graph
called the Script Realization Graph (SRG) [5]. The scheduler takes
the request from the queue and nds a starting time that will allow
all streams to be delivered according to the client's temporal ordering
requirements. It does this by creating a series of test schedules in which
it integrates the new request with the current delivery schedule. The
scheduler selects a feasible test schedule to be the new delivery schedule.
The retrieval manager reads the delivery schedule at every xed disk
service round to determine which streams to service. It then identies
a set of disk blocks to retrieve from the disk. Once these disk blocks
are retrieved, the delivery manager then sends them to the clients.
Isochronous delivery is guaranteed for each client request because all
the scheduled query scripts are served at every xed disk service round.
The main part of a schedule is the list of service intervals and the
resource needs for each service interval. A service interval represents a
period of time where the same set of streams is delivered. Therefore, the
same level of resource utilization is required during the service interval.

Figure

5(a) shows ve service intervals for a delivery schedule. A new
service interval begins with any change in the set of active multimedia
streams. Figure 5(b) shows the service intervals of a new query script.
Adding the new query script to the existing delivery schedule results
in the set of service intervals in Figure 5(c). The list of service intervals
in the delivery schedule maintains information about future resource
needs in a fashion that can be examined quickly.
We developed two scheduling algorithms, which are named scan
scheduling and group scheduling. We present the scan scheduling algorithm
and its simulation results before introducing the group scheduling

8 S. T. Campbell and S. M. Chung

Figure

4. Delivery manager

Figure

5. Service intervals
The scan scheduling algorithm schedules one query script at a time
by progressively slipping the new query script's start time until nding
the rst feasible schedule, so it is named scan scheduling. The algorithm
creates a test schedule by integrating the service intervals of the new
query script with the current schedule, as shown in Figure 6. This test
schedule becomes the new delivery schedule if it is feasible. A feasible
schedule is one in which all service intervals can receive adequate
disk bandwidth, buer memory, network bandwidth and other system
resources required. If the test schedule is not feasible, the algorithm
repeatedly nds the next possible start time for the new query script
until obtaining a feasible schedule. The algorithm can always nd a
start time that results in a feasible schedule since the media server
Delivery Scheduling of Multimedia Streams 9
admits only the query script that is feasible by itself. This ensures that
a feasible schedule exists, even though it may start the new query script
at the end of all currently accepted query scripts.
Apply the admission test
Integrate into a test schedule
Is the test schedule feasible?
Reject the query script
Accept the test schedule
Start
Fail
Pass
Locate the next possible start time
and update the test schedule
Try the predelivery optimization
Unsuccessful
Successful
Update the test schedule

Figure

6. Scan scheduling algorithm
A key to the e-cient execution of this scan scheduling algorithm is
how to limit the number of possible test schedules. This requires nding
a minimum set of possible start times for each new query script. Instead
of sequentially incrementing the possible start time, the scan algorithm
examines only the time instances where the current schedule's resource
utilization level changes, i.e. the start and end points of the service
intervals in the schedule. This signicantly reduces the number of test
schedules.
However, since only one service interval requiring an excessive amount
of resources can make a test schedule infeasible, we may have an unduly
long delay in starting the new query script. Thus, we need to optimize
the schedule to reduce the total service time for the query scripts.
S. T. Campbell and S. M. Chung
2.2. Predelivery Optimization
Optimization of delivery scheduling is required to reduce the total
delivery time for the query script while making better use of system
resources. The delivery manager uses prefetching and buering techniques
to overcome the overcommitment of system resources and to
provide earlier delivery of requests. Idle disk bandwidth and buer
memory are used to prefetch and buer some of the multimedia streams
so that there will be no overcommitted service intervals during the
delivery of query scripts. The rst step is to check the resource requirements
of each service interval of the test schedule. If there is a problem,
the algorithm calculates the total amount of memory space needed to
correct the overcommitment. This amount is proportional to the length
of the overcommitted service interval and the amount of overcommitted
disk bandwidth. The algorithm then scans back through the test sched-
ule's service intervals looking for available disk bandwidth and memory
space. When it nds available resources, the test schedule is updated to
include the prefetch operations. If all overcommitted service intervals
are corrected, the updated test schedule is accepted. Otherwise a new
test schedule is generated by selecting the next possible start time for
the new query script.
Is this media server based optimization necessary since the client
workstation can perform local optimization for the delivery of its own
requests? While the client workstation can perform local optimization,
it can not perform global optimization because it is unaware of other
client requests. Also the client may not be fully aware of the length,
bandwidth requirement, or composition of the requested multimedia
objects. For complete scheduling and optimization, the scheduling algorithm
needs to know the properties of all multimedia objects. While
the client can get this information, the delivery manager, as part of
the multimedia database system, can better perform the optimization
since it has detailed knowledge of the actual multimedia content.
3. Simulation
To evaluate the performance of the scheduling and optimization algorithms
based on the query script, we created a simulation environment.
The simulation is implemented using CSIM [18], a discrete event simulator
supporting concurrent processes written in C++. CSIM primitives
provide multitasking capabilities, handle interprocess communications,
and manage data collection. The resulting simulation is very close to
the actual implementation in C++.
Delivery Scheduling of Multimedia Streams 11
For comparison, we also evaluate the cases where clients release an
individual request for each multimedia stream, which is called baseline
approach in this article.
3.1. Simulation Model
The simulation model includes three major components: clients, delivery
manager, and disk manager. The client processes have three stages:
request generation, request submission, and data reception. For our
simulations, a client's request consists of four playback intervals where
the length of each interval is determined by the longest multimedia
stream in that interval. All the streams in a playback interval start
together at the beginning of the interval. Each playback interval has
up to three multimedia streams that are selected from a pool of 180
multimedia streams, which consists of 120 small streams and 60 large
streams. The length of each stream is randomly selected from a uniformly
distributed set of values where the distribution for small streams
ranges from 5 to 15 seconds and the distribution for large streams
ranges from 45 to 75 seconds.
For the baseline cases, the client makes a request for each multimedia
stream at the start of each playback interval. For the query script
cases, each client submits a single query script for all the multimedia
streams involved. In all the experiments, the clients wait and receive
the multimedia data from the delivery manager, record the delivery
times, and then initiate another cycle of requests.
Both the delivery manager and the disk manager are parts of the
media server. When the media server receives a query script, the delivery
manager rst parses the query script and then executes the delivery
scheduling routine. The scheduling routine merges the query script into
the current delivery schedule by using the proposed scan scheduling
algorithm. The delivery manager generates a list of disk blocks to be
retrieved according to the schedule, and sends it to the disk manager.
The disk manager retrieves the data blocks into memory buers, then
transfers them to the client through the network. This simulation does
not use network delay or network congestion models since appropriate
multimedia networks should be able to handle the maximum number
of 150 KB/sec streams that the current disk model supports.
The disk manager simulates a HP 97560 disk following the model
and methodology used in [24]. The disk model calculates seek time,
rotational delay, head switch time and data transfer time for each disk
request. A disk request consists of an entire track of data which is 36
Kbytes. The model uses a piecewise linear approximation of the disk's
S. T. Campbell and S. M. Chung

Table

I. Disk drive simulation parameters
Number of Cylinders 1962
Number of Tracks per Cylinder 19
Number of Data Sectors per Track 72
Sector Size (bytes) 512
Data Transfer Rate 2.3 MB/sec
Rotation Speed 4002 RPM
d, d < 383 cylinders
Head Switch Time 1.6 ms
Controller Overhead 2.2 ms
actual seek time with seek distances determined by the placement of
multimedia streams on the disk.
In our simulation, to determine whether a schedule is feasible or
not, the delivery manager uses the xed maximum number of continuous
multimedia streams that the disk model can deliver concurrently.
The theoretical maximum number of streams that the disk can deliver
is limited by the disk bandwidth. In practice, the actual number of
concurrent streams that can be delivered is signicantly lower than
this due to the random distribution of seek delay. We experimentally
determined the maximum number of streams that the disk can continuously
support by increasing the number of streams being delivered while
monitoring disk bandwidth utilization and the number of data under-
runs. In our simulation, each stream is stored as a sequence of randomly
selected tracks. We select the maximum number of serviceable streams
to be one less than the point where disk bandwidth utilization reaches
100% or a data underrun error occurs. Figure 7 shows the maximum
and average disk bandwidth utilization recorded during a simulation
run of 10,000 seconds.
During the simulation, one track for each stream is delivered during
each xed disk service round. One disk service round is the period of
time to playback the data in one buer. In our simulation a buer stores
a whole disk track, and the playback rate is assumed to be 150 KB/sec.
Disk head movement is based on the Grouped Sweeping Scheduling
Delivery Scheduling of Multimedia Streams 13
(GSS) algorithm [27], where the number of groups is one. The amount
of extra time in each disk service round after delivering one track for
each stream gives us the disk bandwidth utilization percentage. The
average disk bandwidth utilization is the statistical average from all
the disk service rounds, and the maximum disk bandwidth utilization
is the largest of all the disk bandwidth utilizations of disk service rounds
during the simulation. From Figure 7 we selected eight as the maximum
number of simultaneous streams that can be serviced continuously.

Figure

7. Determining the maximum number of serviceable streams
The disk model uses multiple buers for retrieving each multimedia
stream. One buer is loaded with the data from the disk while the
data in another buer is delivered to the client workstation. Multiple
buering results in e-cient continuous data retrievals from the disk
but forces a startup delay of at least one disk service round as the rst
buer is lled for each stream. Startup delay is the amount of time
between the client request and the delivery of the rst data block to
the client. Usually two buers are allocated for each stream for double
buering, except for the case of prefetching multiple tracks of a stream
for scheduling optimization.
During the simulation we capture disk bandwidth utilization, startup
delay and interstream latency, which is the gap between two consecutive
streams. For the experiments using the proposed predelivery optimiza-
tion, we also capture memory usage. The resulting output data are
collected after a xed length warm-up period to remove startup tran-
sients. We also perform 10 simulation runs of 10,000 seconds to obtain
the average values considering the stochastic nature of the simulation.
14 S. T. Campbell and S. M. Chung
Each run consists of a xed number of clients and each client makes a
new request when its current request is completely served.
3.2. Performance of Scan Scheduling
The goal of using query scripts is to eliminate the gap between two
consecutive streams that we may have with the baseline approach. This
gap is a result of the client individually requesting each stream. The
delivery manager queues the requests if the required disk bandwidth is
not available, and streams are then serviced on a rst-come-rst-served
basis. The length of this gap increases as the number of streams increases
because system work load increases. Figure 8 shows the average
and maximum latency between streams for the baseline experiments.
The baseline approach has an average of 0.75 second latency for three to
ve clients. However, the average interstream latency increases rapidly
as disk contention becomes higher, which is after six clients. At this
higher load there are more requests than available resources and the
system queues the requests for streams. The interstream latency has
the eect of creating gaps and problems in the delivery ordering.

Figure

8. Interstream latencies
With larger loads the interstream latency can increase to 30 to
seconds between every two streams. In this simulation, where the client
request has four playback intervals, the total interstream latency can
easily be several minutes long.
With query scripts there are no gaps between streams as shown in

Figure

8. The scheduling algorithm ensures su-cient resources for the
delivery of all the streams in the query scripts.
Delivery Scheduling of Multimedia Streams 15
The benet of contiguous presentation of each query script comes
at the cost of increased startup delay. Figures 9 and 10 show the
average and maximum startup delay of the baseline and scan scheduling
experiments. The startup delay of the baseline experiments follows
the pattern of the interstream latency since there is no scheduling.
Delivery begins whenever system resources become available. The scan
scheduling experiments show an increase in startup delay since the
system starts the delivery of a query script when it maintains a feasible
schedule. The startup delay becomes high as the contention for system
resources grows, because the scheduler needs to delay the start times
of query scripts to manage contention.

Figure

9. Average startup delay

Figure

10. Maximum startup delay
S. T. Campbell and S. M. Chung

Figure

11 illustrates the delivery characteristics of the baseline approach
and the scan scheduling based on the query script. The baseline
approach experiences both interstream latency and loss of synchronization
due to the heavy system work load. The scan scheduling approach
may experience a larger startup delay since the system creates a delivery
schedule that ensures su-cient resources for the complete delivery
of the query script. The baseline approach can start the delivery earlier
since no such guarantee exists.

Figure

11. Delivery timing
Predelivery optimization lowers the startup delay as can be seen
from

Figure

9 and Figure 10. This benet comes from prefetching the
data and thus being able to nd a feasible schedule with earlier start
times of query scripts. The optimizer uses memory to hold prefetched
blocks of the multimedia streams. Figure 12 shows the memory utilization
for the predelivery optimization of the scan scheduling algorithm.
Memory usage quickly grows as the number of clients increases. Our
next simulation experiment limited the amount of memory to 20 MB
for the predelivery. Figure 13 shows little change in the average and
maximum startup delay with this memory limitation because most of
the infeasible schedules require only a small amount of predelivery to
become feasible.

Figure

14 shows the distribution of actual startup delays for a simulation
run of scan scheduling with optimization. This distribution shows
that a high percentage of requests start within a short period. With
ve clients, 65% of all requests are started within 9 seconds, and with
six clients, 65% of them are started within 28 seconds.
The next analysis examines the disk bandwidth utilization. We measure
the disk bandwidth utilization as a function of the disk's idle time
during each disk service round. In Figure 15 we can see that the average
disk utilization is highest for the baseline cases. Without scheduling,
Delivery Scheduling of Multimedia Streams 17

Figure

12. Memory usage for the predelivery optimization

Figure

13. Startup delay with/without memory limitation
the system service requests are made as quickly as possible, and results
in a higher disk utilization level. However, since these simulations
were performed for a xed continuous work load, lower disk bandwidth
utilization, while maintaining the same delivery throughput, indicates
a more e-cient scheduling methodology. It implies that more time
remains in each disk service round for additional requests including
non-stream requests. The approach of interleaving the access of continuous
streams with non-continuous data allows the same disk system to
service multimedia objects and traditional le accesses. Figure 15 also
shows that limiting the buer memory size to 20 MB for the predelivery
has no eect on the disk bandwidth utilization.
S. T. Campbell and S. M. Chung

Figure

14. Distribution of startup delay

Figure

15. Average disk bandwidth utilization
In this article, we considered constant-bit-rate (CBR) streams with
the constant playback rate of 150 KB/sec. However, modern digital
videos use variable-bit-rate (VBR) compression, such as MPEG [13,
15, 21, 22], where the data consumption rate during the playback is
dierent for dierent frames. For the retrieval of VBR streams, we can
use Constant Time Length (CTL) retrieval or Constant Data Length
(CDL) retrieval [6]. With CTL retrieval, variable amount of data is
retrieved for a stream during each disk service round, but the playback
time is the same during the next service round. On the other hand, with
CDL retrieval, xed amount of data is retrieved for a stream during
Delivery Scheduling of Multimedia Streams 19
each disk service round, but the playback time is dierent during the
next disk service round. If the buer has enough data for the playback
during the next disk service round, no data is retrieved during the
current disk service round [1].
If we use CDL retrieval, the scan scheduling algorithm can be applied
as described above because xed amount of data is retrived for a stream
during each disk service round. However, to use CTL retrieval, we
can adopt the Generalized CTL (GCTL) proposed in [2]. In GCTL,
the duration of the CTL retrieval round is an integer multiple of the
duration of the disk service round, so that xed amount of data is
retrieved for a stream during each disk service round. Thus, the Scan
scheduling algorithm can be used along with the GCTL retrieval.
Networking is a critical issue in the delivery of multimedia streams,
especially for VBR streams [10, 14, 26]. However, this article is focused
on the retrieval scheduling of multimedia streams from a disk subsystem
within a media server, and networking issues are beyond the scope of
this article.
As the main goal of scan scheduling algorithm is to satisfy the inter-stream
synchronization specications, supporting video-like operations,
such as rewind and fast-forward operations, on a specic stream is
not easy. If a user initiates a video-like operation on a stream being
presented, that stream is removed from the corresponding query script,
and the system should change the current delivery schedule. The video-
like operation should be regarded as a separate request, and its disk
bandwidth requirement should be considered to generate a new sched-
ule. If there are many query scripts being serviced, so that there is not
enough disk bandwidth available, the start of the requested video-like
operation may be delayed.
4. Group Scheduling
In this section we look at an additional optimization technique that
extends the scan scheduling algorithm in order to improve system resource
utilization. The scan scheduling algorithm does not perform any
optimization after it nds a feasible schedule with the earliest start time
for a new query script. However, if we nd other feasible schedules, we
can select a schedule that better uses resources and reduces the overall
query script startup delay. For example, if the rst feasible schedule for
a new query script happens to have a set of intervals with high disk
bandwidth utilization late in the schedule, then all following query
scripts must start after this point of high utilization. However, if the
new query script's start time is slightly delayed, then a new schedule is
S. T. Campbell and S. M. Chung
created that might avoid the intervals with high utilization levels, and
hence allow other query scripts to start earlier.
Pass
Integrate into a test schedule
Is the test schedule feasible?
Include the test schedule in the
Apply the metrics to the candidate
schedules and select the best one
Select another start time in the time window
to find a feasible schedule
Apply the Scan scheduiling algorithm
Fail
set of candidate schedules
Start

Figure

16. Group scheduling algorithm
4.1. Creation of Candidate Schedules
To nd multiple feasible candidate schedules for a new query script,
we check all possible start times within a xed time span from the
earliest start time of the query script that we obtained by applying the
scan scheduling algorithm. The xed time span is called time-window
and it prevents us from considering too many candidate schedules with
dierent start times for the new query script. Moreover, it is not desirable
to delay the start time too much in favor of other performance
metrics. Once we have a set of candidate schedules, we can select a
schedule based on some performance metrics. This scheduling algorithm
is named group scheduling and is shown Figure 16.
The scan scheduling algorithm always minimizes the startup latency
of a new query script since it selects the rst feasible start time. Group
scheduling may increase the startup delay of the new query script by
selecting a start time that better uses system resources. However, limiting
the additional latency is important so that the process of optimizing
Delivery Scheduling of Multimedia Streams 21
the delivery schedule of multiple query scripts does not inadvertently
make the new query script unduly suer with a long startup delay. Some
metrics could select a start time that maximizes the startup delay of
the new query script. For example, selecting a schedule with the lowest
maximum disk bandwidth utilization level may be desirable so that
we can accommodate more query scripts later. However, this strategy
leads to starting the new query script at the end of all current scheduled
query scripts. Figure 17 shows a sample case where this situation
occurs. Figure 17(a) depicts the existing schedule and the new query
script. Immediately starting the new query script results in a delivery
schedule with a maximum utilization of 8, as shown in Figure 17(b).
Starting the new query script at the end of the current schedule, as in

Figure

17(c), results in a maximum utilization of 5. The strategy will
thus select the schedule in Figure 17(c) which maximally delays the
start time of the new query script.(a) Existing Delivery Schedule and a New Query Script
(b) Test Schedule - New Query Script Starts Immediately(c) Test Schedule - New Query Script Starts at the End
New Query Script
Current Schedule33

Figure

17. Increased startup delay problem
The time-window limits the additional startup delay of the new
query script because only feasible schedules with a start time falling
within the time-window are allowed to be candidate schedules. Varying
the length of the time-window controls the maximum startup delay for
the new query script. The trade-o is that larger time-window size provides
more candidate schedules for selection at the cost of potentially
increasing the startup delay of the new query script. In our simulation
we used 10 seconds as the time-window size.
22 S. T. Campbell and S. M. Chung
4.2. Selection Criteria
Once a set of candidate schedules is created, the next task is to select
the best schedule. The selection algorithm ranks each candidate schedule
based on a metric and then selects the schedule with the highest
rank as the new delivery schedule. The metric identies schedules that
exhibit desirable properties based on the optimization goals. One optimization
goal is to reduce the sum of all query scripts' startup delay.
Another goal is to better use system resources such as disk bandwidth.
We use disk bandwidth utilization since it measures the e-ciency of
data transfer between the disk drive and memory. Basically we seek
schedules that minimize spikes and other big changes in disk band-width
utilization so that the startup delay of later query scripts will be
reduced.
The example in Figure depicts how poor selection of a schedule
impacts the query scripts submitted later. In Figure 18(b) the scheduler
integrates the new query script into the existing schedule such that one
service interval has a high utilization of 8. As a result, the start of the
next query script is delayed until after that interval. However, if the
schedule integrates the new query script as in Figure 18(c) by delaying
its start, then the maximum utilization level becomes 6 and the next
query script may start earlier.
(a) Existing Delivery Schedule and a New Query Script
(b) Test Schedule - New Query Script Starts Immediately
New Query Script
Current Schedule3 5 5 38
New Query Script
Starts Here
(c) Starting New QS Later Avoids a High Utilization Level

Figure

18. Optimizing query script integration
With these basic optimization goals in mind, we identied the following
optimization strategies that are summarized in Table II and
fully described below.
Delivery Scheduling of Multimedia Streams 23

Table

II. Summary of selection metrics
Smallest Startup Delay Scan scheduling algorithm
Biggest Soonest Highest utilization level early in the schedule
Monotonic Decreasing Consistently decreasing utilization level
Highest Floor Schedule with the highest minimum utilization
level
Lowest Ceiling Schedule with the lowest maximum utilization
level
Minimum Dierential Schedule with the smallest dierence between
the maximum and minimum utilization levels
Time at Minimum Schedule with the largest total time period at
the minimum utilization level
Smallest Startup Delay
The rst strategy corresponds to the scan scheduling algorithm where
we select the rst feasible schedule. The advantages of this methodology
are that each query script starts as quickly as possible and the
optimization overhead is low because other candidate schedules are not
considered.
Biggest Soonest
In this strategy, we rank the schedules based on the end time of the last
interval with the highest disk bandwidth utilization. The scheduler then
selects the schedule with the smallest end time, which corresponds to
the schedule with its highest utilization level ending sooner than other
schedules. As a result, we can avoid cases where an interval late in the
schedule delays other query scripts because of its high utilization level.
Selecting schedules that have their high utilization levels early allows
other query scripts to start earlier.
Monotonic Decreasing
In this strategy, we record the earliest time within each schedule from
which the bandwidth utilization remains the same or decreases. The
earlier this time, the better the schedule. The biggest-soonest strategy
is based upon only the last time of the highest bandwidth utilization.
Thus it ignores the behavior of all other intervals in the schedule. On the
other hand, the monotonic decreasing strategy measures the tendency
S. T. Campbell and S. M. Chung
to have higher bandwidth utilization levels sooner and lower utilization
levels later in the schedule. Selecting a schedule that exhibits decreased
bandwidth utilization levels late in the schedule again makes it easier to
schedule other query scripts with smaller startup latencies and increases
the near-term disk bandwidth utilization.
Highest Floor
This strategy looks at the minimum disk bandwidth utilization as a
measure of the schedule's e-ciency. The \
oor" represents the lowest
bandwidth utilization level of the schedule. Since most schedules have
at least one interval with a low utilization level, the lowest
oor is not
considered. Instead, in this strategy we select a schedule with the high-
est
oor. The idea is that schedules with consistently high utilization
levels can retrieve more data in the same period of time, and hence
make better use of the resources.
Lowest Ceiling
The \ceiling" represents the highest bandwidth utilization level of the
schedule, and this strategy selects the schedule with the lowest ceiling.
This is an attempt to select a schedule with consistent disk bandwidth
utilization. Selecting a schedule with a high ceiling does not make sense
because a single short interval with maximum utilization occurs fre-
quently. Schedules with consistent utilization as characterized by low
ceilings can allow other query scripts to be scheduled at the earliest
possible time, which reduces their startup delay.
Minimum Dierential
A logical combination of the highest
oor and lowest ceiling strate-
gies, described above, is to select a schedule that has the smallest
dierence between its ceiling and
oor. These schedules have consistent
performance which makes it easier to integrate other query scripts into
them.
Time at Minimum
The nal metric that we considered is the amount of time a schedule
spends at the
oor. The longer the schedule uses the
oor utilization,
the more disk bandwidth is available to other query scripts.
4.3. Adding Predelivery Optimization to the Schedule
Selection
Let's consider the role of predelivery optimization in creating candidate
schedules. There are three basic approaches. The rst is to perform
Delivery Scheduling of Multimedia Streams 25
predelivery optimization only on the nally selected delivery sched-
ule. The second is to perform predelivery optimization on all potential
schedules | one for each possible start time of the new query script
| to identify the feasible candidate schedules. The nal approach is to
make the predelivery overhead a part of the metric.
The rst case, performing predelivery optimization only on the selected
schedule, reduces the optimization time, but it decreases the
possibility of nding the best. Predelivery optimization makes more
schedules feasible at the cost of adding more time to the group scheduling
process. The additional time necessary for predelivery optimization
is around 100 ms per schedule in our simulation. However, the simulation
results show that we can reduce the average startup delay of
query scripts by about 5 seconds if we apply the predelivery optimization
(with a time-window of 10 seconds) on all potential schedules.
Thus performing predelivery optimization on all potential schedules is
benecial.
The last option, including the predelivery overhead into the metric,
can be simply done by using the total amount of memory used by the
predelivery as a tie-breaker. When the selection metric values are equal,
the memory usage for predelivery determines which schedule to select.
4.4. Performance of Group Scheduling
We use the same simulation environment and disk model for the simulation
of group scheduling as were used in the simulation of scan
scheduling. For each query script requested from a client, the new
group scheduling algorithm rst creates a set of candidate schedules
by selecting feasible start times for the new query script. As with the
scan scheduling algorithm, only the start and end points of the service
intervals in the current schedule are the potential start times of the new
query script. This dramatically cuts down on the number of candidate
schedules to be evaluated. The scheduler then creates a test schedule for
each potential start time for the new query script. If this test schedule is
not feasible, predelivery optimization is applied as an attempt to make
it feasible. The collection of all feasible schedules found from this trial
integration process becomes the set of candidate schedules. Then one
of the candidate schedules is selected for the new query script based on
the selection metric. In our simulations, we limited the buer memory
size to 20 MB for the predelivery optimization.
First we compare various selection strategies (using dierent met-
rics) in terms of the average startup delay of the scheduled query
scripts. Figure 19 shows the results of experiments with four to ten
clients. The scan algorithm has slightly higher average startup delay for
26 S. T. Campbell and S. M. Chung
many cases. With six clients the resource contention begins, and it is at
this point that group scheduling begins to in
uence the results. How-
ever, since the average startup delays with dierent selection strategies
are quite similar, we can conclude that much of the improvement comes
from the small delay added to the start time of the new query script.
Selecting the best schedule from the candidate schedules with dierent
start times provides a 5{7% improvement in the average startup delay.

Figure

19. Average startup delay

Figure

20. Maximum startup delay
A larger improvement is seen in the maximum startup delay as
shown in Figure 20. Compared to the scan scheduling, the group schedul-
Delivery Scheduling of Multimedia Streams 27
ing algorithm reduces the maximum startup delay by around 10%, or
seconds for runs with high numbers of clients.

Figure

21 shows the amount of memory used for the predelivery
optimization with the group scheduling algorithm. The memory usage
does not play a role in the selection metrics but the maximum limit
can make some potential schedules infeasible. The group scheduling
algorithm better uses disk bandwidth (as will be explained below) and
hence does not require as much predelivery optimization as the scan
scheduling algorithm in many cases. Thus the memory usage for the
predelivery optimization with the group scheduling algorithm is usually
lower than that with the scan scheduling algorithm.

Figure

21. Memory usage for the predelivery optimization
The next analysis examines the disk bandwidth utilization. We measure
the disk bandwidth utilization as a function of the disk's idle time
during each disk service round. In Figure 22 we can see that the average
disk bandwidth utilization is higher for all the group scheduling cases
than for the scan scheduling. It is because more information can be
delivered in a shorter period of time with group scheduling, as evidenced
by the smaller startup delay of the query scripts.
5. Conclusion
In this paper we presented a new methodology for delivering multi-media
objects from a multimedia database system that maintains the
temporal ordering requirements specied by the client. We developed
delivery scheduling algorithms that ensure su-cient system resources
28 S. T. Campbell and S. M. Chung

Figure

22. Average disk bandwidth utilization
to meet the client's temporal ordering requirements. To obtain the
client's requirements, we introduced the query script which is a new
interface between clients and multimedia database systems that allows
the client to completely specify a set of multimedia objects and
their temporal relationships. With this information and the proposed
scheduling algorithms, the delivery manager creates a delivery sched-
ule. To minimize the resulting startup delay for each query script, we
use a predelivery optimization technique that prefetches disk blocks to
memory. A series of system simulations shows the eects and benets
provided by the proposed delivery scheduling algorithms. Without
query scripts, the clients experience large interstream latencies since no
global delivery scheduling is possible. For example, simulations showed
the maximum interstream latency of 40 seconds with six clients. With
query scripts there is no interstream latency. Once the presentation
of a query script begins, desired temporal order and synchronization
of multimedia streams are perfectly satised. With the scan scheduling
using query scripts, the average startup delay may increase as the delivery
manager delays the start of some query scripts to maintain feasible
schedules. However, the increase in the startup delay for a client with
scan scheduling is quite comparable to the total interstream latencies
with the baseline approach. That means the delivery throughput is
quite comparable in both cases. Moreover, the scan scheduling algorithm
requires less disk bandwidth for the same delivery throughput,
and the limited buer memory for predelivery optimization does not affect
the delivery performance. The group scheduling algorithm extends
the scan scheduling algorithm by examining multiple potential retrieval
Delivery Scheduling of Multimedia Streams 29
schedules and selecting the best schedule. This algorithm rst creates
a set of candidate schedules, uses a predened selection metric to rank
them, and then selects the best schedule. We proposed various selection
metrics and discussed their implementation and benets. Compared to
the scan scheduling, the group scheduling results in a 5% decrease in
the average startup delay and a 10% decrease in the maximum startup
delay while maintaining better memory and disk bandwidth utilization.
The computation overhead of the group scheduling is around 100 ms
for a potential schedule, so it is almost negligible compared to the
performance gain.



--R







Multimedia Information Storage and Management
An Introduction to Database Systems


ISO 10744
ISO Multimedia and Hypermedia Experts Group (MHEG)



Computer Science: A Mathematical Introduction

Getting Started with CSIM17: Users Manual
MHEG Center

MPEG Video Compression Standard






--TR

--CTR
Soon M. Chung , Anil L. Pereira, Timed Petri Net Representation of SMIL, IEEE MultiMedia, v.12 n.1, p.64-72, January 2005
Harald Kosch , Ahmed Mostefaoui , Lszl Bszrmnyi , Lionel Brunie, Heuristics for Optimizing Multi-Clip Queries in Video Databases, Multimedia Tools and Applications, v.22 n.3, p.235-262, March 2004
query script;optimization;simulation;delivery scheduling;multimedia streams