QoS Management in Educational Digital Library Environments.
Advances in multimedia computing technologies offer new approaches to the support of computer-assisted education and training within many application domains. Novel interactive presentation tools can be built to enhance traditional teaching methods with more active learning. Since a variety of user expectations are possible in such an environment, research must address the incorporation of these factors into presentation tools. During an interactive learning/training process, presentation tools must be able to handle various types of delays. A flexibly adjustable quality of service (QoS) should thus be supported. In this paper, we investigate a framework and systematic strategies for supporting the continuous and synchronized retrieval and presentation of multimedia data streams in a client/server distributed multimedia environment for educational digital libraries. Specifically, we establish a practical framework for specifying multimedia objects, tasks, schedules, and synchronization constraints between media streams. We identify the QoS parameters critical to the support of multimedia presentations for learning and training activities. Based on the proposed framework and QoS specifications, we develop presentation scheduling and buffer management strategies which can enforce the specified QoS requirements in an educational digital library environment.
Introduction
Currently available computer hardware and devices can support the processing of data in various
media, including video, audio, animation, and still images. Many multimedia standards for
software and hardware are already in place for uniform handling of multimedia data. These technologies
have made it possible to deliver graphs, voice, images, and diagrams through computers.
Substantial research has been directed toward the support of multimedia data processing within
operating systems and network architectures [RV93, Ste90, AH91, RRK93, GR93, ZF93]. Recently,
research involving multimedia data management in database systems has also been highly active
[TK95, MKK95, CGS95, GZ96, ZM96]. Through these research activities, new behavioral concepts
required for multimedia data have been identified and mechanisms have been proposed to
enhance conventional data processing, storage, synchronization, and communication mechanisms.
Using these mechanisms, audio, video, and image objects are supported through which multimedia
streams can be segmented into pieces and then stored in the multimedia database. In this way,
audio, video, and image data stored in the database can be flexibly retrieved and presented to
users.
These advances in multimedia data technologies have led to the possibility of developing multi-media
presentation tools in many application domains. For educational digital library applications,
books can be electronically captured for user to have on-line access to the full collection. Image,
audio, and video materials can be electronically stored, and their content can be extracted and
indexed. Users can navigate and browse through a large collection of multimedia education materials
and identify the relevant materials. In addition, to enhance traditional learning methods,
interactive learning tools can be built to support on-line access to education/training materials.
The interactive learning tools can include a materials-review and problem-exercise tool and a set
of question-answering tools. Through the proposed learning tools, users can conveniently review
both lecture (or tutorial) and supplementary materials. A user can also practice skills through
interactive problem-solving and question-answering.
In order to support these novel features in an educational digital library environment, special
requirements on synchronization, buffer management, and human interaction must be addressed.
To re-present the original data streams to users from media object bases, synchronization constraints
among media objects must be specified and maintained. Such synchronization is usually
termed intra-stream synchronization. An additional complication arises with the timing relationships
that may exist among the different types of media data streams. In educational digital library
applications, such as recording and playback of lecturing video and audio, slide presentations, and
distance learning, require the synchronized display of multiple media data streams. As such media
data streams may not be merged prior to storage in databases, the synchronization of multiple
media data streams, termed inter-stream synchronization, becomes an essential prerequisite to
successful multimedia presentation applications [LG90b, LG90a].
Buffer management within the multimedia presentation system is essential to ensure the maintenance
of the intra- and inter-stream synchronization requirements of multimedia data presentations.
To facilitate a hiccup-free presentation, we must ensure that an object is present in memory before
it is displayed. If the loading rate of a media stream from disk to memory is less than the
delivery rate of the media stream, preloading of the stream prior to delivery would be necessary to
ensure continuous presentation. If multiple media streams are synchronously presented, the buffer
space must be sufficient to simultaneously hold all these streams. Furthermore, an appropriate
allocation and replacement strategy must be provided to anticipate the demands of delays and user
interactions. Such a strategy must minimize the response time of multimedia presentations while
guaranteeing that all continuity and synchronization requirements are satisfied. Thus, the central
issues in this context involve the provision of efficient preloading and replacement mechanisms for
caching media objects. These mechanisms are intended to ensure that the defined continuity and
synchrony of media streams will be preserved to the greatest extent possible, even if there are user
interactions and loading delays.
Along with synchronization and buffer management, there are also important human interaction
factors which are particular to education/training applications. These factors define specific
requirements that must be considered in building the learning tools. In particular, the learning
tools must be able to handle various types of delays and to support user interactions such as skip,
pause, and fast forward/backward in a manner that is acceptable to on-line users. To effectively and
efficiently support these functions, a flexibly adjustable quality of service (QoS) [LG90a] must be
supported. Since these specific needs may be different from those of other multimedia applications,
tools that integrate these particular QoS parameters must be developed.
In this paper, we present an innovative on-line learning environment for education and training
applications. We investigate a framework and systematic strategies for supporting the continuous
and synchronized retrieval and presentation of multimedia data streams in a client/server
distributed multimedia environment for educational digital libraries. Specifically, we establish a
practical framework for specifying multimedia objects, tasks, schedules, and synchronization constraints
between different media streams. We identify the QoS parameters critical to the support
of multimedia presentations for learning and training activities. Based on the proposed framework
and QoS specifications, we develop presentation scheduling and buffer management strategies which
can enforce the specified QoS requirements in an educational digital library environment.
The remainder of this paper is organized as follows. Section 2 introduces the client-server
distributed multimedia architecture for educational digital library environments. In Section 3,
we introduce a framework to specify multimedia data, task, and synchronization constraints. In
Section 4, we discuss QoS parameters and introduce the correctness criteria to preserve the quality
of media presentations. Section 5 presents the scheduling principles and algorithms to ensure
the synchronous presentation of media streams in the event of delays. Section 6 discuss buffer
management strategies. Section 7 sets forth our experimental results. Concluding remarks are
offered in Section 8.
System Architecture
The system architecture under consideration is illustrated in Figure 1. This architecture includes
a distributed multimedia database management system (multimedia server), a set of multimedia
databases, and a set of clients which access the server. The multimedia database management
system is distributedly superimposed on top of a set of database management systems (DBMSs)
and file systems. As certain media streams may be represented and stored in different formats,
the underlying DBMSs or file systems can be heterogeneous. The main function of each client at a
workstation is to display multiple media data to the user in the specified format. Such an architecture
can provide adequate database support for multimedia applications demanding script-based
interactive multimedia presentations [TK95]. A client-server model wherein the client performs
the playout management locally is an ideal candidate for implementing the playout management
service. The integration of the multimedia playout management and database systems make it
possible to efficient interplay between playout management components and database management
system components.
Media DB
DBMS
Media DB
DBMS
Client 1 Client 2 Client n
Network
Server Server Server
Media DB
DBMS

Figure

1: System architecture
As shown in Figure 1, the distributed multimedia database management system server contains
two main modules: a multimedia task language (MTL) interpreter and a media manager (MM).
The multimedia task language MTL interpreter allows users to specify a set of tasks associated with
a multimedia task, including intra- and inter-synchronization requirements on component tasks. A
multimedia task specified in MTL is then processed by the interpreter, and data accesses are sent
to both the MM and the underlying DBMS or file system for processing.
The MM component at each server site supports the multi-user aspect of media data caching
and scheduling. It maintains real-time retrieval of media data from the multimedia database and
transfer the data to the client sites through network. The MM at a client site ensures that media
data stored in the multimedia database will be available on demand in the local buffer and the
synchronous presentation of multiple media streams.
3 Data and Synchronization Models
In this section, we introduce the data and synchronization specification models that will be used
in the rest of the paper.
3.1 Objects
A media stream can be viewed abstractly at several levels. At the lowest level, a media stream
is viewed as an unstructured BLOB (binary large objects) into several higher-level object classes.
Objects from different media streams may also be spatio-temporally combined into multimedia
objects. Several conceptual data models which follow this general scheme have been proposed.
However, few efforts have been made to formalize a multimedia data model at the task management
level for the purpose of scheduling media data operations.
In the proposed data model, we assume that each media stream is broken into a set of atomic
objects. Higher levels of object classification need not to be considered in this context. Each atomic
object represents a minimum chunk of the media stream that bears some semantic meaning. Atomic
objects in different media streams may have different internal structures. For example, a continuous
video stream can be segmented into a set of atomic objects, each of which contains a set of video
frames with specific semantic meaning. Similarly, a continuous audio stream can be segmented
into a set of atomic objects, each of which contains a set of audio samples with specific semantic
meaning.
The atomic objects within a media stream are linked together through intra-synchronization
time constraints. These constraints may specify discrete, continuous, overlapping, or step-wise
constant time flow relationships among the atomic objects. For example, some multimedia streams,
such as audio and video, are continuous in nature, in that they flow across time; other data streams,
such as slide presentations and animation, have discrete, overlapping, or step-wise time constraints.
It may, for example, be necessary to display two distinct slide objects jointly within a single slide
presentation stream. In general, the temporal relationship between two atomic objects in a single
stream may conform to any of the thirteen temporal relationships described in [All83]. In our
representation, each atomic object is associated with a relative start time and a time interval which
specifies the duration of its retrieval, with the initial atomic objects in the media stream assumed
to start at time zero. The actual start time of a media object is usually dynamically determined.
Once a media stream is invoked, it is associated with an actual start time; each media object within
that stream will similarly be associated with an actual start time. We use ! o; t; 4t ? to denote
that object o is to be delivered at time t and will last time period 4t.
3.2 Multimedia Tasks
Media objects from different data streams may need to be linked through time constraints to specify
their synchronization; such time constraints are termed inter-synchronization requirements. For
example, in slide presentation applications, an audio object must be played along with a slide object.
The temporal relationship between two atomic objects from different media streams may also
conform to any of the thirteen temporal relationships described in [All83]. Inter-synchronization
requirements may be specified as meta-data or specified in task programs. In some cases, the relative
time and time interval associated with an atomic object may need to be adjusted to conform with
these inter-synchronization requirements.
We will now discuss the proposed multimedia task model. Since our primary concern with multimedia
data involves retrieval rather than update, our model will consider only delivery operations
of atomic objects. We shall now introduce the concept of a task. For the elements of a task, we
assume the availability of three basic operations: start(t), end(t), and deliver(o; t), where start(t)
and end(t) are beginning and termination operations at a relative time t, and deliver(o; t) is a
delivery operation of object o at relative time t. A task is then defined as a partial order of start,
end, and delivery operations which contain exactly one start operation that is the minimum (first)
element in the partial order, one end operation that is the maximum (last) element in the partial
order, and all delivery operations executed on a given data stream. A multimedia task consists of
a set of tasks upon which synchronization constraints are specified on the delivery operations to
enforce both intra- and inter-synchronization requirements.
We define a schedule to be the execution of multimedia tasks. We define a synchronization
point to be a point held in common by delivery operations from all participating tasks within a
single multimedia task needing to be synchronized. A scheduler must ensure the correct execution
of multimedia tasks. A schedule of a multimedia task may differ from the multimedia task because
the dynamic time constraints of the former differ from the static relative time assignments of the
latter. Additionally, the tolerance parameters given for a schedule will permit further deviations
from the multimedia task.
3.3 Synchronization Specification
we propose an approach to the specification of synchronization constraints among the component
tasks of a multimedia task. As indicated above, both data and task operations are associated with
time constraints. Synchronization constraints may also exist among the component tasks of a multimedia
task. Since synchronization constraints are implicitly imposed by the specification of time
constraints, the maintenance of the latter would ideally guarantee the maintenance of the former.
1.
2.
3.
4.
5.
6.
7.
A
A
A
A
A
A
A

Figure

2: Typical temporal relationships.
However, while the scheduler should make every effort to enforce the time constraints defined on
task operations, even minor delays may create great difficulties in scheduling. Experimental experience
demonstrates that such delays are frequent. Thus, the explicit specification and enforcement
of synchronization constraints is necessary.
Synchronization dependencies among the delivery operations in a multimedia task are dynamically
generated on the basis of the intra- and inter-synchronization constraints placed on the media
streams. Such dependencies are intended to facilitate scheduling by efficiently describing the synchronization
constraints existing among the tasks of each multimedia task.
Let a multimedia task be defined as a set of tasks which represent the synchronized
presentation of media streams Each media stream consists of a set of
objects and each object is specified as loss of generality,
we assume that the synchronization constraints are implied in the definition of time constraints on
objects. The synchronization relationship between any two objects in either a single media stream
or two media streams follows the thirteen temporal relationships outlined in [All83]; these are given
in

Figure

2. Inverse relationships are not listed in the figure. In general, these synchronization
relationships can be easily generalized to the synchronization relationships among n media objects
Three relationships, namely before, after, and equal, are used to define the temporal ordering of
one object with respect to another. The temporal relationships between two objects are
categorized as: (1) is said to start before is said to start after
is said to start equal to is said to end before
said to end after is said to end equal to
We say that two objects starts before
a single media stream are neighboring each other if there is no object
We introduce three types of synchronization points within media
streams, as follows:
has an intra-synchronization
point there exist two neighboring objects !
that s
+4t, where
has an inter-synchronization
point there exists an object o 1i in m 1 and another media object ! (may or
may not be in m 1 ) such that starts equal to o jk or ends equal to o jk .
has a middle-synchronization point p 1 if there exists another media object !
or may not be in
The synchronization relationships given in Figure 2 can be categorized into three classes, according
to their synchronization points: cases 1 and 2 have intra-synchronization points; cases 5,
6, and 7 have inter-synchronization points; and cases 3, 4, 5, and 6 have middle-synchronization
points.
We define the granularity of a media object to be the size of the object and the granularity of
the synchronization between a set of media streams to be the number of synchronization points that
must be identified. Clearly, the finer the object granularity, the more synchronization points will
need to be identified. Thus, the design of a higher-level data model for the decomposition of media
objects determines the minimum granularity of the synchronization between the media streams.
However, at the level of multimedia task management, the granularity of the synchronization can
be defined more finely. At this level, additional synchronization points can be defined in the midst
of objects to permit finer synchronization control among media streams. As the decomposition of
media objects is not the main concern of this paper, this subject will not be discussed further at
this point.
Quality-of-service Requirements and Correctness Criteria
In this section, we will first discuss QoS parameters and the effect of these parameters in the
scheduling of multimedia presentations. We will then define correctness criteria for the executions
of multimedia tasks. As illustrated below, QoS parameters must be considered in the definitions of
these correctness criteria.
The scheduling of multimedia tasks includes the scheduling of time-dependent delivery oper-
ations, synchronized delivery enforcement among multiple media streams in a multimedia task,
concurrent execution of multimedia tasks, and delivery delay recovery. A correctness criterion in
this context must verify that delivery operations are performed according to a predefined synchronization
pace and within the time constraints imposed on tasks. Since the correctness of time-based
presentations depends on the accuracy of timing that must be maintained on media streams, the
execution result of a multimedia task is a question of quality rather than consistency. We must thus
formulate new correctness criteria for the executions of multimedia tasks which define acceptable
quality in real-time. Several important QoS parameters must be considered in these correctness
criteria.
Little and Ghafoor [LG90a] have proposed several parameters to measure the QoS for multimedia
data presentation. The following parameters have been listed: (1) average delay, (2) speed ratio,
(3) utilization, (4) jitter, and (5) skew. The average delay is the average presentation delay of each
object in a time interval. The speed ratio is the actual presentation rate to the nominal presentation
rate. The utilization equals the actual presentation rate to the available delivery rate of a set of
objects. Ideally, both the speed and utilization ratios should equal 1. During the presentation of
a video stream, frame duplication leads to utilization values greater than 1, while dropping frames
would lead to values less than 1. The jitter is the instantaneous difference between two synchronized
streams. The skew is the average difference in presentation times between two synchronized
objects over n synchronization points. Clearly, average delay, speed ratio, and utilization are used
to measure the quality of individual media stream presentations, whereas jitter and skew are used
to measure the quality of presentation among multiple media streams.
While the delivery of each media stream would ideally minimize the average delay and maintain
the parameters of speed ratio and utilization to be close to 1, the achievement of these three goals
is actually in conflict. There must therefore be trade-offs between these goals during scheduling.
Consider a synchronous presentation of audio and video streams. If the scheduler attempts to
minimize the average delay of audio objects, it must then, in case that an audio object is delayed,
drop some video frames in the corresponding video object to maintain synchronization between
the two objects. If the scheduler tries to maintain the utilization of video objects close to 1 when
delays occur, it must decrease the speed ratio of these objects and, consequently, increase the
average delay. Thus, it is generally impossible for all parameters to achieve an ideal state for all
applications. There must be trade-offs among different QoS parameters.
Multimedia presentations in the domain of education or training are normally instruction-
oriented. Such presentations should usually last two to three hours. The media streams involved in
a single presentation may include a combination of audio and slides, or a combination of audio and
video as well as text. Preserving synchronization requirements on such presentations must be the
top priority in defining QoS services. Distortion between synchronized media objects may result
in misunderstanding of the teaching materials. Figure 3 demonstrates an experimental example of
the presentation of audio and video streams. Table 1 provides the measurement of average delay,
jitter, and skew. In this experiment, synchronization constraints are implicitly imposed by the
specification of time constraints on media objects. As the synchronization points are not explicitly
enforced in the presentation, delays occurred in the individual objects resulted in mismatches among
the displayed media objects from different streams. High values in jitter and skew are reported in
the table. Such mismatches may cause confusion in understanding the materials.1
(a)
(b)
Time
Audio

Figure

3: Presentation of audio and video streams : (a) nominal, (b) actual presentation
Parameter
Average Delay 1.0 - 0.75 - 1.75 - 2.50 - 2.50 -
Skew 2.0 - 1.5 - 2.5 - 4.5 - 5.0 -
Jitter - 2.0 - 2.0 - 4.0 - 5.0 - 5.0

Table

1: Parameter values for presentation without synchronization
Thus, our primary goal on formulating acceptable QoS parameters should be to avoid any
deviations from the synchronization constraints associated with the media streams. We assume that
maximum allowable delays for individual media streams are pre-specified. These measures provide
the permissible ranges for average delay and speed ratio. In addition, we assume that maximum
allowable skips for individual media streams are also pre-specified. These measures provide the
permissible ranges for utilization. Upon these measures, we require that the presentation tools will
minimize the possibility of jitter and skew.
We will now define a correctness criterion for the execution of a multimedia task and then
identify those schedules to be considered to be correct. As with conventional database query
executions, the semantics of a multimedia task determine the correctness of its execution. Unlike
conventional database query executions, however, the time constraints defined within multimedia
tasks assume a position of prime importance. We thus introduce the following semantic correctness
criterion:
Definition 4 (Correct execution) The execution of a multimedia task T is correct if the time
constraints specified within T are preserved.
This semantic correctness criterion is theoretically applicable to the executions of multimedia
tasks. However, in a practical, delay-prone system, this criterion cannot be applied directly by the
scheduler to enforce the execution of multimedia tasks. Given the pervasive nature of delays, a
strict application of this rule would result in the aborting of the vast majority of multimedia tasks.
A more realistic scheduling criterion is therefore needed. We introduce the concept of acceptable
schedules by incorporating the effect of delays into the definition of schedules.
Definition 5 (Acceptable execution) The execution of a multimedia task is acceptable if and
only if all delays occurring at the defined synchronization points are within the permissible QoS
ranges.
Note that the scheduler at a client site need not consider the concurrent execution of multiple
multimedia tasks. It must control the presentation of multiple media streams to a single user.
There is need to have a central scheduler to manage the real-time executions of all multimedia
tasks at the server site. This paper will primarily focus on the schedulers at client sites.
5 QoS Guaranteed Presentation Scheduling
In this section, we will investigate the principles guiding the scheduling of the delivery of multiple
media data streams at each client site. We shall assume that the given transmission and the
server provide sufficient support for delivering media objects. A framework will be developed to
permit efficient synchronization of multimedia presentations which incorporates the effects of QoS
requirements.
5.1 Basic Scheduling Strategy
We assume that there is a permissible delay constraint that defines the maximum tolerable delay for
each media stream participating the execution of multimedia task T . Thus, as long as the delay of
the presentation of each stream is within the permissible delay range, we consider the presentation
is acceptable. We now present a basic scheduling strategy that minimizes the possibility of jitter
and skew.
In this context, the threefold categorization of synchronization points summarizes the most
critical scheduling information. Additional synchronization points could be specified between these
synchronization points within the shared intervals. While a finer granularity of stream synchronization
improves the synchronization of media stream presentation, it also increases the control-related
scheduling overhead. Thus, there is a trade-off between the quality of the presentation and the system
overhead.
We associate each media object with two events: a START event, denoted
by
, and an END event, denoted by e
. All START and END events are then classified into
layered GROUPs based on the time constraints pertaining to the events. The lowest-layer GROUP 1
contains all START events which are the events at the starting time of the entire presentation, and
the highest-layer GROUP n contains all END events which are the events at the ending time of the
presentation. All events occurring at a given time belong to the same GROUP. Thus, each
GROUP contains all START and END events that must be simultaneously executed. Within each
GROUP, all the END events and the START events are related by the before relationship. Events
between two consecutive groups are related by the after relationship.
At each middle-synchronization point, the object ij to which there are other objects that
start or end in the middle will be split by assigning a START and an END event at the middle-
synchronization point.
The following example demonstrates an application which uses the specification described above.
Example 1 Consider an application involving on-line computer-assisted learning in undergraduate
education. Without loss of generality, we assume that there are two media streams, audio and slides
(or video), in each multimedia task. Intra-synchronization within the slide stream may require
that two objects either overlap or be sequentialized. Intra-synchronization within the audio stream
requires only that objects be sequentialized. Additional inter-synchronization requirements between
the two media streams are specified among slides and audio objects. These requirements between
the slides and audio objects follow the thirteen temporal relationships outlined in [All83]. Let a
multimedia task contain two tasks, one of which accesses the slide stream and the other the audio
stream. In order to successfully deliver both streams to a student, the system must ensure that
all time constraints placed on the individual delivery operations and the synchronization between
slides and audio objects are preserved. Let a particular application is given in Figure 4. In this
application, a set of layered GROUPs, denoted GROUP 1 ,., GROUP 7 , are identified.
We will now discuss the generation of acceptable schedules. Following Definitions 1, 2, and 3,
at each intra-synchronization point, there exist an END event and a START event; at each inter-
synchronization point, there is one START event; at each middle-synchronization point, there may
exist either one START event or an END event and a START event. Synchronization points of
all three types can coexist at a given synchronization point; in such a case, the synchronization
point must be ensured to be both continuous and synchronous with other specified synchronization
points in different media streams.
The scheduler ensures that only synchronous schedules will be generated by controlling the
invocation order of events in the formulated layered GROUPs of each multimedia task. Let a
Time
GROUP2 GROUP3 GROUP4 GROUP5
slides
audio
o22 o23
GROUP6 GROUP7

Figure

4: Layered GROUPs.
multimedia task T have n layered GROUPs. Assuming no distortion, the basic invocation policy
for the execution of T is as follows: assume that all START events in GROUP 1 have been invoked.
(1) The events in GROUP i\Gamma1 always have a higher invocation priority than those in GROUP i ,
for any i such that
(2) All START events in a GROUP i (1 - i - n) are invoked simultaneously.
(3) All END events in a GROUP i (1 - i - n) are terminated simultaneously.
events in a GROUP i (1 - i - n) can only be invoked after all END events in the
same GROUP have terminated.
Items (1) and (4) ensure the intra- and middle-synchronization points specified in T , while items
(2) and (3) ensure the inter- and middle-synchronization points specified in T .
The effects of a variety of delays, including network delays and storage delays, are not considered
in the above policy. As was noted earlier, such effects must be incorporated into the scheduling
policy to generate acceptable schedules. In the above basic scheduling strategy, we incorporate
the effect of delays into the scheduling policy by propagating delays into the invocation of successive
delivery operations. Thus, if a delivery operation is delayed, then the END event in the
corresponding GROUP will be delayed and, consequently, all END and START events in the same
GROUP will be delayed. By propagation, all the ensuing delivery operations and events in the
higher-layer GROUPs will be delayed. A full consideration of delay recovery will be presented in
the next section.
We assume that each media stream has a permissible delay constraint and the minimum value
of all permissible delay constraints given in the media streams defines the maximum tolerable delay
for the multimedia task. If a larger delay occurs, then timeout will be used by scheduler. If the
scheduler finds that it has been waiting too long for the completion of a delivery operation, then it
aborts the execution of the multimedia task.
Clearly, the basic scheduling strategy enforces all defined synchronization points by controlling
the invocation of START events. Both jitter and skew are thus minimized. As delays are propa-
gated, no data are lost in presentations, utilization is equal to one. In addition, timeout is used in
case a delivery operation is delayed beyond the permittable delay. Thus, this approach generates
only acceptable schedules.
5.2 Scheduling with Delay Recovery
In Section 5.1, a basic solution was presented in which delays are simply propagated to the ensuing
delivery operations. We will now systematically investigate a novel and more effective delay recovery
approach. Our discussion of delay recovery will consider not only the constraints of synchronization
but also the parameters of average delay, speed ratio, and utilization.
The proposed basic scheduling strategy guarantees that no temporal deviation will occur within
the simultaneous presentation at synchronization points. Since delays that may occur between
these synchronization points are not considered, such a synchronous execution may actually fail to
preserve the time constraints defined on the delivery operations within tasks. There may therefore
be a temporal deviation between the delivery operations of different tasks during these intervals.
However, any asynchronization caused by delays will be recovered at the next synchronization
point. Thus, a synchronous execution of a multimedia task may allow enormous delays between
the delivery operations of different tasks during some intervals. We shall now investigate the
principles involved in the scheduling of multimedia tasks with delay recovery. A framework will
be developed to permit efficient resynchronization of the presentation of multiple media streams in
the event of delays.
Let two parameters, maximum delay, denoted 4d max
i , and maximum skip, denoted 4s max
be specified for each media stream m i . These two parameters provide users with flexibility in
achieving the above goals. If maintenance of good utilization is of highest interest in a particular
instance, then the amount that can be skipped should be specified as a relatively small figure. If
it is more important to minimize the average delays, then the delay allowed for the media stream
should be set at a relatively low level. In our context, users may have different expectations for
various presentations of learning materials. Thus, the choices of QoS parameters may vary in
different stream presentations. Within the given QoS parameters, our approach will maximize
utilization and minimize the abortion rate of multimedia tasks in order to preserve the quality of
the presentations.
Consider a synchronous presentation of media streams and a set of media objects
from these streams are currently synchronously delivered. Let 4d i (1 - i - n) denote the delay
that is occurred in the object belonging to m i . We may have the following situations for these
media objects:
i for all integer i in the range 1
(2) For all
n g) and there exists some 4d i
n) such that 4s max
(3) There exists some 4d i (1 - i - n) such that 4d
In case (1), synchronous presentation can be restored by simply skipping by the interval by
which the delayed media streams lag behind. In case (2), since there exists some media object such
that its delay is larger than its permittable skip, simply skipping the delayed objects may not be
applicable. However, this difficulty can be circumvented by a compromise between skipping and
pausing. Similar to the situation discussed in Section 5.1, we assume that the timeout period is
the minimum value of all permittable delay constraints given in the media streams belonging to
the multimedia task. Within the permittable timeout period, we calculate the maximum difference
between the delay and the allowable skip for delayed objects:
If the amount of PAUSE is less than the permittable timeout period, then the period of PAUSE
will be paused in order for those delayed operations to catch up for the maximum possible period.
After this PAUSE period, if there exists some unfinished operation, then it must be within its
permittable skip period. Therefore, such an operation can be skipped.
Thus, in case of delays during the execution of GROUP i\Gamma1 , the following rule is added to the
basic invocation policy given in Section 5.1:
(4) Pause the START events in GROUP i for a period defined in (a) before invocation.
In case (3), the execution of the multimedia task must be aborted. The detailed algorithm
of this approach is offered in Algorithm 1. Note that the calculation of WAIT in Algorithm 1 is
slightly different from PAUSE, since the first completed END event might be delayed and this delay
effect must be added to WAIT while performing tolerance check.
Similar to the basic scheduling strategy, the scheduling with delay recovery enforces all defined
synchronization points by controlling the invocation of START events. Both jitter and skew are
minimized. However, delays are recovered instead of propagated. Thus, utilization may not be
equal to one, but within the permissible QoS range. Thus, this approach also generates only
acceptable schedules.
6 QoS Guaranteed Buffer Management
In this section, we will present a framework which generates the required start times for media
objects. This framework guarantees the continuity of media stream presentation while minimizing
buffer utilization at both client and server sites. Furthermore, an appropriate allocation and
replacement strategy must be provided to anticipate the demands of delays and user interactions.
6.1 Start Times of Media Streams
Buffer management is needed in both client and server sites to ensure that the loading of media
objects will not cause the delay of their presentation. At the client sites, to facilitate a hiccup-free
presentation, we must ensure that an object is present in local memory before it is delivered. At the
server sites, we must ensure that once a media stream is started to be retrieved and transmitted,
this retrieval and transmission will be performed in a desirable rate.
Normally, the loading of a media stream from disk to memory is much faster than the display
of the media stream. However, both network and storage delays must be considered in determining
the preloading time of a media stream. We first consider the situation of the entire stream. Let t m
l s
be the time at which the loading of media stream m begins and loading function Lm (t; t m
l s
) be the
total number of media objects of m read at time t. Let t m
cs be the time at which the consumption
Algorithm 1:
Input: multimedia task T with l number of layered GROUPs; allowable SKIP and DELAY
for media objects in T .
Coordinator for a multimedia task
invoke All START events in GROUP i
to l do
if there exist END events in GROUP i whose START events are in GROUP 1
to GROUP
then wait for e / the first END event to complete
on timeout begin abort T ; return end;
for the rest of END events do
WAIT / the maximum difference between the current delay and SKIP among
the delayed media objects
/* delay of e would be 0 if the first END event is not delayed */
the delay of e - min(fd max; d max; :::; d max
l g)
then wait for WAIT
send STOP signals to all delayed END events in GROUP
elseif WAIT+ the delay of e ? min(fd max; d max; :::; d max
l g)
if there exist START events in GROUP i
then invoke all START events in the GROUP i .
endfor
terminate all Participants
return
Participant for an individual task
do
if receive START signal from Coordinator
execute delivery operation
send END signal to Coordinator
elseif receive STOP signal from Coordinator
terminate delivery operation
elseif receive TERMINATE signal from Coordinator
return
forever
of data stream m begins and consuming function Cm (t; t m
cs ) be the total number of media objects
consumed at time t. The number of media objects that must be buffered at any given time is then
given by
cs
l s
l s
l s
cs ,
l s
cs
cs .
(1)
Given D max as the amount of buffer for delay recovery in the presentation of media stream m,
this amount must be added to consumption to determine the start time of displaying or delivering
the stream.
Suppose that a solution is to begin display or delivery at time x. That is, Bm (t; x) is at least
zero for any time x
l f
l f
is the time at which the loading of data stream m is
completed. If we compare Bm (t; x) with Bm (t; t m
l s
) in the range x
l f
, we see that
Bm (t;
l s
l s
l s
l s
l s
l s
If Bm (t; t m
l s
in the range t m
l s
l f
, then Bm (t;
l s
. Thus, the start time
of stream m can be t m
l s
. We now consider the situation that Bm (t; t m
l s
may be negative in
the range t m
l s
l f
. Let Bm (t; t m
l s
must be the
minimum start time such that
l s
Thus, x can be determined when both consuming function and the loading time are given. This
start time assumes that the entire stream will be continuously loaded. However, in our context,
we assume that the data unit to be accessed is media object rather than the entire stream. Thus,
after the display or deliver time of stream m is determined, the deliver time of each media object
within the stream must also be precisely determined.
6.2 Start Times of Media Objects
In order to ensure a hiccup-free presentation based on pre-determined time, the loading of each
media object must guarantee that there is enough object data to be consumed at its consuming
time. The presentation of each object can thus be divided into two phases: (a) a loading phase
and (b) a consumption phase. Let t im
l s
be the time at which the loading of object o im of stream
begins and loading function L im (t; t im
l s
) be the amount of object o im of stream m read at time
t. Let t im
cs be the time at which the consumption of object o im of stream m begins and consuming
function C im (t; t im
cs ) be the amount of object consumed at time t. The amount of buffer space
that must be allocated for object o im at any given time t is given by
cs
l s
l s
l s
cs ,
l s
cs
cs .
In similar manner to the derivation given above, we can derive the relationships between the
loading and consuming times for each media object
l s
cs
l s
l s
l s
l s
l s
cs
Let k im be determined by B im (t; t im
l s
max is the amount of
buffer for delay recovery in the presentation of the object We then have
l s
cs
Thus, for each object o im in stream m to be successfully presented at time
cs , it must be
loaded into memory at a time satisfying Formula (6).
In case that the consuming function is linear, that is,
Cm (t;
c is the consuming rate of stream m. We then have the start time of the first object of the
stream m based on Formula (3):
l s
c
and the preloading times for the rest of the media objects based on Formula (6):
l s
c
Depending on the loading delays and the amount of data that has to be loaded, t im
l s
can belong to
any of the time periods in which previous media objects are consumed.
6.3 A Prefetching Strategy
We now propose a prefetching technique which is based on the principles discussed above and
satisfies the requirement of continuity and synchrony in the presentation of multimedia objects
while minimizing the number of buffer faults.
To incorporate the buffer management into the proposed scheduling algorithms, prefetching of
the media objects must be performed before invoking their START events. The START event of
an object corresponds to t im
cs , and the END event to t im
Each object must be
prefetched before its START event is invoked. To minimize buffer requirements, all objects are
not prefetched at the same time. The start of prefetching of object o im can be calculated by using
Equation 9. These prefetching times are associated with a GROUP depending on the membership
of the GROUP.
A simple and effective prefetching strategy is to use a variation of the Least Recently Used (LRU)
strategy called the Least Recently Displayed (LRD) strategy that replaces the object with the
smallest t c f
in the buffer with the new object. In other words, the object that finished consumption
the earliest is removed first from the buffer. Using an LRD replacement strategy helps in dealing
with delays more gracefully. In the event of delays, the last presented object in the faster stream
is most likely to be presented over and over again (object duplication) to correct the skew in
presentation. An LRD strategy guarantees that the most recently displayed objects are always
in the buffer. The reader is referred to [GZ96] for a detailed discussion of the LRD strategy.
Algorithm 2 reflects the addition of buffer management to the scheduling strategies detailed in the
previous sections. Note that this algorithm provides only a rough sketch of the exact procedure. In
particular, the loading of objects in each interval [GROUP are performed
in a lump rather than at each individual loading time.
We have shown a prefetching algorithm that maintains synchronization constraints thereby
minimizing skew and jitter [LG90a] in a presentation. Furthermore, the algorithm handle delays
in the presentation more gracefully by using an LRD replacement strategy for buffer replacement.
This allows us to minimize the buffer faults and hence average delays in the presentation, thereby
decreasing the additional buffer size required to store the delayed objects and make the presentation
continuous.
7 Experimental Results
This section will present our experimental results based on the approaches proposed in the previous
sections.
In our experiments we have video-clips, audio-clips and images available as database objects.
The presentation script is stated in the application program that runs on top of the multimedia
server. At script realization time, methods of the media objects are invoked at the respective points
in time. The playout management is implemented in a multi-threaded environment in which the
Algorithm 2: (delay recovery with buffer management)
Input: multimedia task T with l number of layered GROUPs; allowable SKIP and DELAY
for media objects in T the maximum buffer
Coordinator for a multimedia task
l s
foreach obj 2 S do Prefetch(obj; i)
invoke All START events in GROUP i
to l do
if there exist START events in GROUP i
l s
foreach obj 2 S do Prefetch(obj; i)
invoke all START events in the GROUP i
endfor
terminate all Participants
return
if buffer size+jobjj - Bmax
then BUFFER / BUFFER [fobjg
buffer size / buffer size+jobjj
else replace a minimal set of objects with smallest t cf in BUFFER with obj
buffer size / buffer size +jobjj \Gamma jobjectsj
return
functions of the buffer manager, scheduler and the presentation of the media streams are managed
by threads.
We measured five QoS parameters including average delay, speed ratio, skew, jitter, and utilization
during the presentation of the three media streams; these streams consisted of audio, video,
and images, respectively. Two sets of experiments are illustrated in this section; one involves audio
and image streams and the other involves video and audio streams. In the examples presented
below, QoS parameters are measured at client sites.
In the first set of the experiments, as in a typical slide presentation, objects from the audio
and image streams were presented together. Each presentation of an audio or image object is for
a duration of five seconds followed by a time gap of two seconds. Figure 5(a) shows the defined
presentation of both the media streams. The presentation without delay recovery is illustrated in

Figure

5(b). Figure 5(c) shows the actual presentation using Algorithm 1. It was found that the
image stream consistently lagged in the presentation, possibly due to the additional overhead involved
in creating the image and writing it into a window. When delay recovery is not implemented,
the delay is allowed to propagate through the presentation. However, the synchronization between
the two streams is still maintained, since the synchronization constraints enforce the simultaneous
presentation of objects from both the media streams.
For the interval (t 0 , Figure 5, the average delay for the nominal case is 0. In the scenario
without delay recovery, the average delay is 1.0, 1.71, and 11 in the intervals (t 0 , t 1
These values are presented in the first row in Table 2. Similarly, the speed
ratio in the interval (t 0 , t 1 ) for the case without delay recovery is 0.89. This is because only two-thirds
of the audio object 2 is presented in (t 0 , t 1 ). In the interval (t 1 , t 2 ), the speed ratio is 0.78.
Since all the objects delivered are presented without object loss, the utilization ratio is 1 for all
time intervals. Note that the delayed stream, that is, the image stream, does not require any frame
duplication to pause its presentation. Hence the value of utilization is 1 and not greater than 1.
Furthermore, no difference in presentation times between an audio and image objects is observed.
Therefore, the skew is 0 for all the intervals.
The corresponding values when delay recovery is considered are shown in Table 3. The allowable
skip for the image stream is set to a high value of 2 seconds, allowing the object to skip the entire
delay. This is made possible by the non-temporal nature of images, so that information is not
lost by decreasing the display time of an image object. Such a scheme results in the presentation
schedule shown in Figure 5(c). Note that the utilization level does not decrease as a result of
omission of the display of a non-temporal object. In contrast, if the delivery of an audio object
were to be skipped or dropped, there would be a drop in the utilization level, as the actual data
presented is less than the data made available. This difference is highlighted in the second set of
experiments involving two temporal streams.
From

Figure

5(c), one can clearly see that the average delay has been reduced to 0 for all
intervals. The speed ratio for all intervals is equal to unity, as all necessary audio objects are
presented in all intervals. Since all the temporal (audio) objects delivered are presented without
Nominal Presentation
Actual presentation without
delay recovery
Actual presentation with
delay recovery
Time
Audio
Audio
Audio
Image
Image
Image
(a)
(b)
(c)

Figure

5: Presentation of audio and image streams : (a) nominal, (b) without delay recovery and
(c) with delay recovery
object loss, the utilization ratio is 1 for all time intervals. As in the scenario without delay recovery,
skew is observed to be 0 in all the intervals.
Parameter
Average Delay 1 1 1.71 11
Speed Ratio 0.89 0.78 0.9 -
Utilization
Skew 0/3 0/3 0/3 0/3

Table

2: Parameter values for presentation without delay recovery
In the second set of experiments, we presented a video stream along with an audio stream.
The video clips are MPEG encoded streams [SZ94, ZTSY95, ZLS95]. The nominal presentation
schedule is shown in Figure 6(a). Unlike the slide presentation, the presentation of both the streams
is continuous. The allowable skip for both the video and audio stream is set to 0.50 seconds. Similar
to the previous case, QoS parameters were measured with and without delay recovery.

Tables

4 and 5 respectively present the QoS parameters for the case with and without delay
recovery. Unlike in the previous case where the delays occurred in the image stream, presentation
delays occurred in the both the streams. These delays were either due to system load and other
extraneous conditions or the imposition of the presentation schedule on the delivery of a media
stream. Since both audio and video are temporal in nature, we do see a decrease in the utilization
as frames are dropped or skipped to maintain synchronization and decrease in average delay, skew
Parameter
Average Delay
Speed
Utilization
Skew 0/3 0/3 0/3 -

Table

3: Parameter values for presentation with delay recovery
(a)
(c)
(b)
Time
Audio
Audio
Audio

Figure

Presentation of audio and video streams : (a) nominal, (b) without delay recovery and
(c) with delay recovery
and jitter in the presentation. The delay in the presentation could also be corrected by decreasing
the speed ratio of the faster stream and thereby letting the slower stream catch up.
For the interval (t 0 , Figure 6, the presentation of the video object was delayed while the
presentation of that of the audio object was on time. In the absence of delay recovery, this delay
was allowed to propagate to the following presentation intervals. This made the average delay
substantial in each interval. For example, in intervals (t delay was
1.25 and 2.25 seconds respectively. In contrast, with delay recovery, audio and video objects can
be skipped as long as the skip is within the tolerable range for the presentation. This reduces
the average delay to 0.62 and 1.12 seconds in (t
this trend. Besides, speed ratio also increases when delay recovery is performed since the actual
presentation rate approaches the nominal presentation rate. Skew was observed in all intervals
there was no delay recovery in place. This skew was reduced or eliminated
when delay recovery was incorporated in the scheduling strategy. Without delay recovery, none of
the video frames or audio samples were dropped. Hence, the utilization was considered 1 across the
presentation with no delay recovery. However, with delay recovery some portions of the delayed
stream, either audio or video or both, are skipped. This leads to a decrease in the utilization in all
Parameter
Average Delay 1.25 - 2.25 - 2.25 - 3.5 - 3.0 -
Speed
Utilization
Skew
Jitter

Table

4: Parameter values for presentation without delay recovery
Parameter
Average Delay 0.62 - 1.12 - 0.75 - 0.25 -
Speed
Utilization 0.95 - 0.95 - 0.95 - 0.90 - 1.0 -
Skew
Jitter

Table

5: Parameter values for presentation with delay recovery
the intervals as shown in Table 5. In the case without delay recovery, jitter was observed at times
in the presentation. Using delay recovery jitter is reduced to 0.5 seconds at times t 1
and t 2 and is eliminated at t 3
From the experiments performed, we observed that although our scheduling algorithms minimize
jitter and skew by invoking the synchronization events simultaneously, the system-level differences
between two invoked participants may still result in the occurrence of jitter and skew. By using
delay recovery, such occurrence can be reduced, as the amount of objects to be dealt with is reduced.
We have shown that the implementation of the proposed synchronization algorithms minimizes
jitter, skew and delays in a presentation. Furthermore, a buffer management strategy is also
presented along with the synchronization algorithm. This allows us to minimize the average delays
in the presentation, thereby increasing speed ratio.
A playout management functionality allows the user to define an application specific presentation
script. Moreover, the service greatly enhances the user's ability to generate acceptable
schedules at various levels of granularity of synchronization and choose the right schedule.
Conclusions
In this paper, we have introduced a framework for QoS management in education digital library
environments. This framework includes a vehicle for the specification of multimedia data, tasks,
schedule, and synchronization constraints. A multimedia task consists of a set of tasks upon which
synchronization dependencies are specified on the delivery operations to enforce both intra- and
inter-synchronization constraints. A schedule of the multimedia task is acceptable only if it satisfies
the synchronization constraints defined on the multimedia task with the allowable QoS ranges.
Several parameters, including average delay, speed ratio, utilization, jitter and skew are used to
set up permittable QoS ranges. The framework also includes the principles and algorithms of
scheduling and buffer management to ensure synchronous presentations of multiple media streams.
Experimental results are also provided based on the implementation of the proposed approaches.
Through this research, we have observed that multimedia presentations in the educational
digital libraries require specific QoS management to ensure the quality of service in this domain.
In order to prevent the misunderstanding of the learning or training materials, distortion between
synchronized media objects must be minimized. Thus, preserving synchronization requirements on
such presentations is the top priority in defining QoS services. As a result, the presentation tools
proposed in this paper minimize the possibility of jitter and skew. Our experimental results have
demonstrated that the proposed approaches are effective and efficient in preserving these goals.
This paper has primarily focused on the specification, scheduling and buffer management at
client sites. We have assumed that the server provides sufficient support for delivering media
objects to client sites. In fact, the proposed principles of buffer management can also be applied
to the server with different values to be defined on delays. Further research needs to be done
to investigate the admission control at the server sites while distributed database systems or file
systems are accessed.



--R

A Communication Media I/O Server and Its Synchronization Mechanisms.
Maintaining Knowledge about Temporal Intervals.
Avoiding Retrival Contention for Composite Multimedia Objects.

Continuous Retrievals of Multimedia Data Using Parallelism.
Buffer Management in Multimedia Database Systems.
Network Considerations for Distributed Multi-media Object Composition and Communication
Synchronization and Storage Models for Multimedia Objects.
L/MRP: A Buffer Management Strategy for Interactive Continuous Data Flow in a Multimedia DBMS.
Performance of Inter-Media Synchronization in Distributed and Heterogeneous Multimedia Systems
Efficient Storage Techniques for Digital Continuous Multimedia.
Synchronization Properties in Multimedia Systems.

Playout Management - An Integrated Service of a Multimedia Database Management System
A Network Level Channel Abstraction for Multimedia Communication in Real-time Networks
Video Parsing and Browsing Using Compressed Data.
Implementation of Video Presentation in Database Systems.
Automatic Parsing and Indexing of News Video.
--TR

--CTR
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
digital libraries;quality of service QoS;synchronization;multimedia