MPEG-L/MRP: Adaptive Streaming of MPEG Videos for Interactive
Internet Applications
Susanne Boll
, Christian Heinlein
, Wolfgang Klas
, Jo chen Wandel
Institute for Computer Science and Business Informatics,
University of Vienna, Vienna, Austria
f
Susanne.Boll,Wolfgang.Klas,Jochen.Wandel
g
@univie.ac.at
Dept. Databases and Information Systems (DBIS),
University of Ulm, Ulm, Germany
Abstract
Continuous delivery of media streams like video over IP
networks so far is mainly handled by commercial ap-
proaches delivering streams forward-oriented in their own
proprietary format. Though some existing streaming
technologies are able to adapt to varying bandwidths,
they do not provide smooth reactions to user interactions
with the continuous stream.
We have develop ed the
MPEG-L/MRP
strategy, an
adaptive prefetching algorithm for the MPEG-1 video
format in combination with an intelligent buering tech-
nique that allows for smooth and quick reactions to user
interactions with the stream. With L/MRP [12] an ap-
proach already has b een presented to deliver and buer
homogeneous continuous data streams like Motion-JPEG
with sp ecial fo cus on fast reaction to user interactions. In
contrast, the MPEG-1 enco ding with its dierent frame
typ es and inter-frame dependencies op ens the do or to
a more ne-grained adaptation of the continous stream.
However, the complexity of MPEG-1 calls for comprehen-
sive adaptation and sp ecial amendments of the L/MRP
algorithm to make it an eÆcient preloading and buering
technique for MPEG-1 videos.
With the realization of
MPEG-L/MRP
in the context
of a multimedia presentation engine on top of a multi-
media rep ository we have an eÆcient means to deliver
continuous streams of interactive multimedia presenta-
tions over existing IP infrastructure trying to minimize
interaction resp onse time and optimize loading/reloading
p ortions of a video stream.
1 Intro duction
In future, users of multimedia applications will no longer
b e satised with pre-packed presentations on stand-alone
systems or proprietary compositions embedded in Web
pages and rendered by browser plug-ins. Rather, p erson-
alized interactive multimedia presentations are needed,
delivered on-demand from a multimedia server over an IP
network to a user's exible presentation environment. In
this context, the delivery of continuous multimedia data
as well as its presentation must be tailored to the sp e-
cic requirements of this environment, i. e., the varying
bandwidth, resp onse time of the server, and the like.
The motivation of our work in the area of continu-
ous delivery of interactivemultimedia presentations over
a network stems from our research pro ject \Gallery of
Cardiac Surgery" (Cardio-OP
1
) [8] which aims at devel-
oping an Internet-based and database-driven multime-
dia information system in the domain of cardiac surgery.
The users of the system request multimedia content from
dierent platforms over dierent network connections.
Video streams are of high importance in this educational
environment. During the learning pro cess, it is indisp ens-
able for the user to interact on the stream so as to watch
a scene again or jump to another interesting part of the
video. Therefore the system must supp ort interactions
and, to be user-friendly, should react in a very resp on-
siveway. Hence, the presentation environment demands
for streaming support for continuous media with suitable
handling of user interactions.
In the pro ject context, we develop ed a multimedia pre-
sentation engine which includes supp ort for continuous
MPEG video streams. For this, we develop ed the
MPEG-
L/MRP
algorithm to continuously deliver MPEG-1 video
streams over an IP network whichwe present in this pa-
p er.
Compared with, e. g., Motion-JPEG, the enco ding of
continuous video streams with MPEG-1 oers a signi-
cantly higher compression rate which is very important
for a delivery over a network with p otentially low band-
width. We aim at continuously delivering the MPEG-1
stream in small units and at buering these units in an
intelligent way at the client such that the user is pro-
vided with a smo oth and continous presentation though
the user can p ossibly carry out VCR-likeinteractions on
the stream like fast forward, reverse, or jumping to a
b o okmark in the video. The buering technique should
hide the request and buering of units and rather deliver
a continuous MPEG-stream of the b est quality that can
b e currently provided to the application.
With
L/MRP
[12] we nd a preloading and buer-
ing strategy for continuous streams supp orting interac-
tions that has proven to perform b etter than \traditional"
strategies like, e. g., LRU, FIFO, LFU, etc. This ap-
proach, however, aims at delivering and buering
ho-
mogeneous
continuous data streams like Motion-JPEG
with sp ecial focus on fast reaction to user interactions.
The complexity of MPEG-1 with its heterogeneous frame
typ es of dierent imp ortance, varying frame sizes, and
1
Partially funded by the German Ministry of Research and
Education, grant number 08C58456. Our pro ject partners
are the University Hospital of Ulm, Dept. of Cardiac Surgery
and Dept. of Cardiology, the University Hospital of Heidel-
b erg, Dept. of Cardiac Surgery, an asso ciated Rehabilitation
Hospital, the publisher Huthig-Verlag, Heidelb erg, FAW Ulm,
and ENTEC GmbH, St. Augustin. For details see also URL
http://www.informatik.uni-ulm.de/dbis/Cardio-OP/
Proc. 6th Int'l Workshop on Multimedia Information Systems (MIS 2000), Chicago, October 2000
inter-frame dep endencies calls for comprehensive adap-
tation and special amendments of the original L/MRP
algorithm to make it an eÆcient preloading and buer-
ing technique for MPEG-1 videos. This pap er presents
our MPEG-1 sp ecic preloading and buer management
strategy
MPEG-L/MRP
for MPEG-1 videos that outper-
forms at least as go o d as L/MRP.
The remainder of this pap er is organized as follows:
Section 2 discusses related work. Section 3 revisits the
original L/MRP algorithm and gives a short overview of
the parts of MPEG-1 relevanttoour approach. In Sec-
tion 4, our new MPEG-L/MRP approach is presented
which consists of a formal mo del and a corresp onding al-
gorithm. Section 5 sketches the implementation of the
approach, and Section 6 concludes the pap er.
2 Related Work
Related work, concerned with the delivery of multime-
dia contentover the Internet, covers several research ap-
proaches dealing with the adaptive streaming of MPEG
videos. As a part of the QUASAR pro ject at the Oregon
Graduate Institute [19], an MPEG player for adaptive
MPEG streaming over the Internet has b een develop ed
which addresses resource scarceness in the end-to-end de-
livery. The fo cus lies on a quality of service (QoS) mo del
and an adaptation mechanism of the player. To facilitate
adaptive streaming, the MPEG video is provided by the
server in dierent qualities. The stream is adapted in the
temp oral dimension by dropping B frames rst, then P
frames, and nally I frames. In addition, dierent spa-
tial resolutions are provided as a second variable quality
dimension. Buering is applied to comp ensate network
jitter but do es not supp ort fast reactions to user interac-
tions. Another approach, the Media Streaming Protocol
[4] develop ed at the University of Illinois, provides adap-
tive streaming of MPEG movies, to o. On congestion,
the proto col considers the dierent frame typ es of MPEG
with their frame interdependencies and, similar to our
approach, drops less imp ortant MPEG frames rst. The
client side buer is employed only to smooth the jitter of
arriving data but do es not allow for minimizing interac-
tion resp onse time and reload of data after possible user
interactions.
In the commercial area, many approaches can be found
that deal very well with the streaming of videos, e. g.,
Quicktime [1] or Emblaze [2]. With VDOLive [17] and
Real [14] approaches exist, that are furthermore able to
adapt the video stream to uctuations of the available
bandwidth. For instance, with the introduction of the
SureStream technology [15], Real allows to encode a video
clip that serves for up to six dierent bandwidths. This
stream can automatically be adjusted to comp ensate for
network congestions. However, as this technique enco des
multiple disjoint streams into one le, it leads to an ina-
tion of the storage size and to redundancy. However, all
the commercial approaches mentioned have in common
that they op erate on proprietary video formats and are
neither designed to supp ort minimization of the interac-
tion resp onse time nor to optimize the eort for reloading
p ortions of a video stream.
With Q-L/MRP [3] an interesting application of
L/MRP has evolved. Q-L/MRP extends L/MRP with
additional interaction sets in order to support the spe-
cic QoS requirements of certain users. However, the ap-
proach do es not deal with MPEG sp ecic preloading and
replacement strategies.
3 L/MRP and MPEG-1 Revisited
3.1 L/MRP
L/MRP (
L
east/
M
ost
R
elevant for
P
resentation) [12] is
a buer management strategy for interactive continuous
data ows in a client/server environment. The client re-
quests and receives a continuous medium in small units
and buers that part of the stream that is relevant for
the current and future presentation. The main idea is to
request, preload, and buer those units that are
most rel-
evant
to b e presented in the near future. The sp eciality
of the L/MRP strategy here is that the preloading and
buering takes into account the interactions a user p ossi-
bly carries out on the stream, e. g., switch to fast forward
playback or jump to a b o okmark. By that means, the in-
teraction resp onse time compared to common buer man-
agement and replacement strategies is reduced (cf. [12]).
Preloading
and
replacement
are the two tasks the buer
management strategy has to master. During preloading
the next most relevant units of the continuous stream
are determined, whereas the replacement strategy must
decide which are the least relevant units as these are re-
moved from the buer to free space for more relevant
units.
The L/MRP buer management strategy treats the
stream as a sequence of so called
Continuous Object Pre-
sentation Units (COPUs)
with an ascending numb ering
of the units. Lo oking at a sequence of COPUs from a
sp ecic presentation p oint
p
in time, the single COPUs
are dierently relevant for the current presentation which
is expressed by assigning relevance values to each COPU.
Consider Figure 1 for an illustration: The current presen-
tation p ointis
p
= 43 and the user is watching the stream
at double sp eed in forward direction. Then, every other
COPU in forward direction close to the current presenta-
tion p oint is absolutely relevant for the up coming presen-
tation. These COPUs form the so called
referenced
set, as
they are likely to be referenced in the near future. How-
ever, there are COPUs that already have b een viewed.
These belong to the
history
set of COPUs of the stream.
As a user could change the direction of the playout at any
time, these COPUs are still relevant for the presentation.
Finally, the frames in forward direction which are
skipped
due to the double speed playout, are relevant, to o, as the
user could switch to normal sp eed playbackatany time.
These considerations can b e continued for further interac-
tion typ es such as fast backward, jumping to b o okmarks,
and the like.
The relevance of a COPU with resp ect to one of these
sets is determined by a so called
distancerelevance func-
tion
which expresses a COPU's relevance as a function
of the distance of the COPU to the current presenta-
tion p oint
p
. For the referenced set, the distance rele-
vance function is monotonously decreasing with value 1
for the next few COPUs to be presented. As the frames
of the history and skipp ed sets are less likely to b e pre-
sented, their distance relevance functions are decreasing
more rapidly. Given one or more relevance functions for
each COPU, an overall relevance function can b e calcu-
lated, e. g., by taking the maximum relevance value for
each COPU. This global relevance function is then used
by the preloading and replacement of the buer. The
relevance value expresses which COPUs are likely to be
presented when taking into account the dierentinterac-
tions a user could p erform on the stream. L/MRP tries
to keep those most relevant COPUs in the client buer
to achieve a quick and smo oth reaction to the user in-
teraction. Dep ending on the buer size those COPUs
ab ove a certain relevance value are kept in the buer and
those below the threshold value are not loaded/are re-
moved from the buer to make ro om for the more/most
relevant COPUs. Whenever the presentation p oint
p
pro-
ceeds, the relevance values are recalculated, the COPUs
to be preloaded are determined and the COPU(s) with
the least relevance value in the buer are replaced.
Referenced Skip
0.5
1
45 46 47444342414039383736 48 49 50 51 52 53 54 55 56 57 58 59
Relevance
COPU Indices
HistoryInteraction Sets:
60
pPresentation Point
Fig. 1: L/MRP: interaction sets and relevance values
Display order:
Bitstream order by frame number:
264 7850 9 ...
BB BB BBPPII
12345 78960
13
Fig. 2: MPEG frame typ es and their interdep endencies
3.2 MPEG-1
The MPEG-1 standard [6] is a co ding format for audio
and video streams. In this pap er, we are concerned with
video streams only [7]. The main feature of MPEG-1 that
is interesting in this pap er is that frames are no longer in-
dep endent of each other as is the case with, e. g., Motion-
JPEG which is a series of single JPEG [18] images. Figure
2 shows a sequence of MPEG frames and their interde-
p endencies which are relevant for deco ding the stream.
An MPEG-1 video sequence in general consists of three
dierent frame typ es,
I
,
B
, and
P
. Usually, the frames
from one I frame up to the frame b efore the next I frame
form a so called
Group of Pictures
(GoP). Since I frames
(intra-co ded pictures) are enco ded similarily to JPEG im-
ages, their deco ding is indep endent of other frames. The
deco ding of P frames (predictive coded pictures) dep ends
on the preceding I or P frame of the same GoP. For B
frames (bidirectionally co ded pictures) deco ding dep ends
on b oth the preceding and the succeeding I or P frame. P
and B frames allowamuch higher compression rate than
I frames by exploiting temp oral prediction using motion
vectors. It is important to note that the display order
in which the frames are presented is dierent from the
bitstream order in which the frames are deco ded due to
inter-frame dep endencies. Figure 2 illustrates b oth the
display order and the bitstream order of a stream. The
order for deco ding is very important as a preloading strat-
egy must of course consider the order of decoding and not
only of displaying the frames.
A preloading and buer management strategy for
MPEG-1 video must pay attention to the dierent frame
typ es and their inter-frame dependencies, the bitstream
order for decoding the stream, and the fact that the bit-
rate/data rate of the video and the size of the frames can
heavily vary.
4 MPEG-L/MRP Mo del
4.1 Overview of MPEG-L/MRP
Basic Idea
So far, the L/MRP approach has proven to be sup erior to
traditional preloading and buering strategies [12], esp e-
cially when it comes to fast reaction to user interactions.
The basic idea of
MPEG
-L/MRP is to provide the same
interaction resp onsiveness as achieved with L/MRP but
in particular to take into account the sp ecic features
of the MPEG video stream. The dierent frame typ es
with their inter-frame dependencies and their dierent
imp ortance for the presentation are the main issue when
adapting L/MRP to MPEG. The MPEG-L/MRP strat-
egy exploits the knowledge about the imp ortance and de-
p endencies of the frames such that the video can b e opti-
mally presented under the available network bandwidth.
Therefore, the interaction sets and the asso ciated rele-
vance functions of the L/MRP strategy are adapted such
that they reect this sp ecic imp ortance of frames for the
presentation. When frames do not arrive in time at the
client, temp oral adaptation is used in order to maintain
a continuous presentation.
Cho osing the Appropriate COPU Size
The rst issue of adapting L/MRP to MPEG streams is
the kind and size of the data that forms a COPU. The CO-
PUs are the basic units for transp ortation of the stream.
Lo oking at MPEG-1, there are dierent p ossibilities to
dene a COPU:
A COPU corresp onds to a GoP.
The rather big size
of the COPU might be a problem. If such a COPU can-
not b e delivered to the client, in average half a second of
the video is missing. This size is also unsuitable for, e. g.,
a fast forward presentation of the video, since all frames
had to be loaded to the client though only a subset of
them would b e needed.
A COPU corresp onds to a part of a GoP.
In [5], it is
prop osed to use IBB or PBB groups. However, the groups
and therefore the COPUs are then dep endent on each
other, and the supp orted co ding scheme of the MPEG
stream is restricted to IBBPBB...PBB patterns.
A COPU corresp onds to a frame.
Here, still the
COPUs are dependent on each other like the frames of the
MPEG stream are. However, this granularity allows for
fast and targeted reaction to varying network bandwidth
and user interactions.
We decided to use the third alternative as it oers the
most appropriate p ossibility to comp ensate uctuations
in the available network bandwidth and, at the same time,
oers support for fast and smo oth reactions to user inter-
actions on the stream. This decision serves as the basis
for the formal mo del to follow.
4.2 The MPEG-L/MRP Mo del
Overview
In this subsection, the MPEG-L/MRP model will b e de-
velop ed step by step. Following some preliminary def-
initions, we intro duce
presentation sets
as a means to
collect those frames whichhave to b e displayed for a par-
ticular kind of presentation of a video, such as normal
playback, double sp eed presentation, and so on. Since
P and B frames cannot b e deco ded indep endently, addi-
tional I or P frames might be necessary to actually de-
co de and display the frames of a sp ecic presentation set.
These inter-frame dep endencies are captured by
depen-
dency sets
, leading to the notion of
closed presentation
sets
.
Afterwards, static and dynamic
relevance functions
are
dened as a means to quantify the relevance of frames
contained in a particular presentation set. While static
relevance functions are used to assign relevance values to
frames surrounding a static
reference frame
(represent-
ing, e. g., a bo okmark), dynamic relevance functions are
needed to compute the relevance values of frames sur-
rounding the
current presentation point
which is con-
stantly moving in time during a normal presentation of
the video. Both static and dynamic relevance functions
are based on
generic relevance functions
which dene rel-
evance values indep endent of a particular reference frame
or the current presentation p oint.
Finally,a
global relevance function
is intro duced which
combines the relevance values of static and dynamic rel-
evance functions into a single overall relevance value for
each frame of the video which will be used by the MPEG-
L/MRP algorithm to determine preloading candidates
and replacement victims.
Remark:
For readers familiar with the details of the
original L/MRP model [12], it should be noted that the
formal mo del evolved in several asp ects in order to adapt
it to the sp ecial requirements of the MPEG video for-
mat. In particular, the notion of
interaction sets
con-
taining
pairs
of frames (or COPUs) and relevance val-
ues (determined by so called
distancerelevance functions
)
has b een split into two orthogonal concepts:
presentation
sets
containing frames only on the one hand, and
rele-
vance functions
assigning relevance values to frames on
the other hand. By that means, inter-frame dep enden-
cies can be captured quite easily by intro ducing dep en-
dency sets which are completely independent of the con-
cept of relevance values. Furthermore,
generic relevance
functions
, which are translated to a particular frame and
restricted to a particular presentation set in order to ob-
tain static and dynamic relevance functions, are some-
what easier to use than the corresp onding
distance rel-
evance functions
of the original mo del, especially when
frames are not equidistantly distributed within a presen-
tation set.
Preliminary Denitions
Let, as usual, IN=
f
1
;
2
;
3
;:::
g
b e the set of natural num-
b ers and
//
Z =
f
:::;
2
;
1
;
0
;
1
;
2
;:::
g
the set of integer
numbers. For
k
2
//
Z, let
//
Z
k
denote the set of integers
from 0 to
k
, i. e.,
//
Z
k
=
f
0
;
1
;:::;k
1
;k
g
for
k
0
;
f
k; k
+1
;:::;
1
;
0
g
for
k<
0
:
For a subset
M
//
Zofintegers, let
M
:
//
Z
!f
0
;
1
g
be
the
characteristic function
of
M
assigning a value of 1 to
all memb ers of
M
and 0 to all other numbers:
M
(
x
)=
1 for
x
2
M;
0 otherwise
:
Presentation Sets
For a particular video comprising
n
2
IN frames, let
F
=
f
0
;
1
;:::;n
1
g
be the set of its
frame numbers
in display order. Fur-
thermore, let
I
,
P
, and
B
b e pairwise disjoint subsets of
F
representing the set of all I, P, and B frames of the
video, resp ectively. Assuming that a video do es not con-
tain other frame typ es (in particular, D frames), it holds:
F
=
I
[
P
[
B:
A
presentation set
is a subset
S
F
of frames which
have to b e displayed for a particular kind of presentation
of the video. For instance, the presentation set
F
s
=
f
f
2
F
j
f
=
i
s; i
2
IN
0
g
=
f
0
;s;
2
s;:::
g
sp ecies the set of all frames
f
whichhave to be displayed
for a forward or backward presentation of the video with
a relative sp eed (or
skip factor
)of
s
2
IN.
Dep endency Sets
Due to inter-frame dependencies, in order to be able to
deco de and display the frames of a particular presentation
set
S
, it might be necessary,however, to deco de additional
frames. These inter-frame dep endencies are captured by
the
dependency set
D
(
f
)
F
containing all frames
g
2
F
which are directly or transitively needed to decode and
display frame
f
2
F
. Using the auxiliary denitions
I
(
f
) = max
f
g
2
I
j
g
f
g
and
P
(
f
) = min
f
g
2
I
[
P
j
g
f
g
sp ecifying the
closest preceding I frame
of frame
f
and the
closest succeeding I or P frame
of frame
f
, resp ectively,
D
(
f
) can be dened as follows:
D
(
f
)=
f
f
g[ f
g
2
I
[
P
j
I
(
f
)
g
P
(
f
)
g
:
Since
I
(
f
) =
f
=
P
(
f
) for an I frame
f
2
I
, it holds
D
(
f
)=
f
f
g
in that case, which means that no additional
frame is needed to deco de an I frame. For a P frame
f
2
P
it holds
I
(
f
)
<f
=
P
(
f
), and thus
D
(
f
) contains
f
and all preceding P frames up to and including the
closest preceding I frame. The same holds for a B frame
f
2
B
, but since
I
(
f
)
< f < P
(
f
) in that case,
D
(
f
)
contains the closest succeeding I or P frame of
f
,too.
Remark:
For
I
(
f
) and
P
(
f
)to be well-dened for all
frames
f
2
F
, the rst frame of a video must b e an I frame
and its last frame must b e an I or P frame. Without these
restrictions, the video would not b e standard-conforming,
however.
Closed Presentation Sets
The
closure
S
of a presentation set
S
F
can b e dened
as the set
S
=
[
f
2
S
D
(
f
)
containing all frames which are actually needed for a par-
ticular kind of presentation, either directly b ecause they
have to b e displayed or indirectly due to inter-frame de-
p endencies. A presentation set
S
is called
closed
,if
S
=
S
holds.
Given the denition of
F
s
ab ove, the closure
F
s
com-
prises, for example, all frames which are actually needed
for a presentation of the video with a relative sp eed of
s
.
Intersecting
F
s
with one of the sets
I
,
P
, or
B
, yields
the pairwise disjoint sets
I
s
=
F
s
\
I
,
P
s
=
F
s
\
P
, and
B
s
=
F
s
\
B
containing all I, P, or B frames, resp ectively,
necessary for such a presentation.
If the co ding scheme of a video is a constant rep etition
of the pattern illustrated in Figure 3 (i) (followed by a
nal I frame), the presentation set
F
2
contains all frames
depicted as shaded b oxes. Since this set comprises all I
and P frames of the video, it is already closed, i. e., it
holds
F
2
=
F
2
in that case. The presentation set
F
3
on
the other hand, illustrated in Figure 3 (ii) is not closed,
since additional P frames identied by black arrows are
needed to deco de the B frames that are to b e presented at
a skip factor of 3. That means, that the closure
F
3
con-
tains 6 instead of 4 frames out of each 12-frame pattern
IBBBPBBBPBBB resulting in an overhead of roughly
50%.
2
Relevance Functions
A
generic relevance function
is a function
:
//
Z
!
[0
;
1]
assigning a
relevance value
(
x
)
2
[0
;
1] to each integer
number
x
2
//
Z. Typically, a generic relevance function is
either
monotonously increasing
for
x
0 and zero-valued
2
Since the sizes of I, P, and B frames are usually quite dierent,
this is indeed only a rough estimation.
for
x >
0 or zero-valued for
x <
0 and
monotonously
decreasing
for
x
0. For instance, the linear functions
b
a
(
x
)=
max(
b
(1
x=a
)
;
0) for
x
2
//
Z
a
;
0 otherwise
;
with a p eak value of
b
2
[0
;
1] for
x
= 0 and p ositive
values for
x
2
//
Z
a
nf
a
g
(
a
2
//
Z) are typical examples of
generic relevance functions (cf. Figure 4 (i) for
a
0 and
(ii) for
a
0).
Bframes to be
presented
B
frames needed
for decoding
IBB
additional
BBBBBPP
IPPBBB BBB BBB
(i) 2
F :
(ii) F :
3
Fig. 3: Presentation sets at dierent skip rates
b
(i)
aa
(ii)
b
Fig. 4: Typical generic relevance functions
A
static relevance function
is a function
:
F
!
[0
;
1]
assigning a relevance value
(
f
)
2
[0
;
1] to each frame
f
2
F
. Typically, a static relevance function
is constructed
by
translating
the p eak of a generic relevance function
to a sp ecic
reference frame
r
2
F
and
restricting
its
domain to a particular presentation set
S
F
:
(
f
)=
(
f
r
)
S
(
f
)
:
A
dynamic relevance function
is a function
Æ
:
F
F
!
[0
;
1] assigning a relevance value
Æ
(
f; p
)
2
[0
;
1] to each
frame
f
2
F
taking into account the current presenta-
tion p oint
p
2
F
. Similar to a static relevance function,
a dynamic relevance function is usually constructed by
translating and restricting a generic relevance function
,
where the current presentation p oint
p
replaces the static
reference frame
r
:
Æ
(
f; p
)=
(
f
p
)
S
(
f
) for some
S
F:
As noted above, static relevance functions are typically
used to describ e b o okmarks where the reference frame
r
sp ecies the p osition of the b o okmark in the video, while
dynamic relevance functions are needed to model dynamic
presentations of the video like normal playback, reverse
playback, fast forward, etc., where the current presenta-
tion p oint
p
is constantly moving in time.
Global Relevance Function
Given a set of static relevance functions
1
;:::;
k
and a
set of dynamic relevance functions
Æ
1
;:::;Æ
m
, the
global
relevance function
:
F
F
!
[0
;
1] is dened as an
appropriate combination of these functions, e. g., by com-
puting a
weighted maximum value
for each frame
f
2
F
:
(
f; p
) = max
max
i
=1
;:::;k
!
i
i
(
f
)
;
max
j
=1
;:::;m
j
Æ
j
(
f; p
)
:
Here, the weighting factors
!
1
;:::;!
k
2
[0
;
1] and
1
;:::;
m
2
[0
;
1] can b e used as global regulators similar
to the slide controls of a sound mixer.
Examples
Example 1: Forward Presentations.
For a skip fac-
tor
s
2
IN, let
!
I
s
,
!
P
s
, and
!
B
s
b e generic relevance func-
tions
3
which are zero-valued for
x<
0 and monotonously
decreasing for
x
0. Since I frames are generally more
imp ortant than P frames which are in turn more impor-
tant than B frames, the relationship
!
I
s
(
x
)
!
P
s
(
x
)
!
B
s
(
x
) shall hold for all
x
2
//
Z (cf. Figure 5 for a typical
example using a skip factor
s
= 1).
Relevance
0.25
0.50
0.75
1.00
//
Z
3 6 9 12 15 18
!
I
1
!
P
1
!
B
1
Fig. 5: Generic relevance functions
!
I
1
,
!
P
1
,
!
B
1
Relevance
0.25
0.50
0.75
1.00
F
p p
+3
p
+6
p
+9
p
+12
p
+15
p
+18
!
Æ
I
1
!
Æ
P
1
!
Æ
B
1
Fig. 6: Dynamic relevance functions
!
Æ
I
1
,
!
Æ
P
1
,
!
Æ
B
1
Based on these generic relevance functions, dynamic
relevance functions
!
Æ
I
s
,
!
Æ
P
s
, and
!
Æ
B
s
can b e dened using
the presentation sets
I
s
,
P
s
, and
B
s
, resp ectively, dened
earlier (cf. Figure 6, again using
s
= 1):
!
Æ
I
s
(
f; p
) =
!
I
s
(
f
p
)
I
s
(
f
)
;
!
Æ
P
s
(
f; p
)=
!
P
s
(
f
p
)
P
s
(
f
)
;
!
Æ
B
s
(
f; p
)=
!
B
s
(
f
p
)
B
s
(
f
)
:
Dep ending on the current presentation p oint
p
, these
functions express the relevance values of those I, P, and
B frames, respectively, which will be needed in the near
3
the
!
denotes the direction of the playout
future for a forward presentation of the video with a skip
factor of
s
. Since the presentation sets
I
s
,
P
s
, and
B
s
are pairwise disjoint, at most one of the values
!
Æ
I
s
(
f; p
),
!
Æ
P
s
(
f; p
), and
!
Æ
B
s
(
f; p
) will b e p ositive for each frame
f
2
F
, while the others are zero.
Combining the functions
!
Æ
I
1
,
!
Æ
P
1
, and
!
Æ
B
1
into a global
relevance function using weight factors
!
I
1
=
!
P
1
=
!
B
1
=
1, yields the function
!
1
shown in Figure 7:
!
1
(
f; p
) = max
!
Æ
I
1
(
f; p
)
;
!
Æ
P
1
(
f; p
)
;
!
Æ
B
1
(
f; p
)
Relevance
0.25
0.50
0.75
1.00
F
p p
+3
p
+6
p
+9
p
+12
p
+15
p
+18
Fig. 7: Global relevance function
!
1
Relevance
0.25
0.50
0.75
1.00
F
pp
3
p
6
p
9
p
12
p
15
p
18
Æ
I
1
Æ
P
1
Æ
B
1
Fig. 8: Dynamic relevance functions
Æ
I
1
,
Æ
P
1
,
Æ
B
1
Example 2: Backward Presentations.
Replacing
the generic relevance functions
!
I
s
,
!
P
s
, and
!
B
s
with their
reected counterparts
I
s
,
P
s
, and
B
s
, resp ectively, which
are monotonously increasing for
x
0 and zero-valued for
x>
0, yields analogous dynamic relevance functions
Æ
T
s
(
f; p
)=
T
s
(
f
p
)
T
s
(
f
) for
T
=
I; P; B
expressing the relevance values of those
T
frames which
will be needed for a backward presentation of the video
in the near future (cf. Figure 8 for
s
= 1).
Remark:
Since the frames
g
2
D
(
f
)
nf
f
g
are nec-
essary to deco de frame
f
, their relevance values should
be greater than that of
f
. For the \forward functions"
!
Æ
T
s
describ ed ab ove, this requirement is normally fullled
due to the monotony of the generic functions
!
T
s
and the
global relationship
!
I
s
!
P
s
!
B
s
. The only critical case
here is a P frame
g
2
D
(
f
)
succeeding
a B frame
f
. By
cho osing functions
!
P
s
and
!
B
s
whose dierence is large
enough, it can b e guaranteed, however, that the desired
condition
!
Æ
P
s
(
g
)
>
!
Æ
B
s
(
f
) is always satised.
For the \backward function"
Æ
P
s
,however, the monotony
of the generic function
P
s
is partially counter-pro ductive,
since it yields the undesired relationship
Æ
P
s
(
g
)
Æ
P
s
(
f
)
for a P frame
f
2
P
and all frames
g
2
D
(
f
)
P
.
To remedy this aw, a correction term can be included
in the denition of
Æ
P
s
which reduces the relevance value
of a frame
f
2
P
by a small amount
"
for every frame
g
2
(
D
(
f
)
\
P
s
)
nf
f
g
that is necessary to decode
f
(cf.
Figure 9):
Æ
P
s
(
f; p
)=
P
s
(
f
p
)
k
"
P
s
(
f
)
where
k
=
j
D
(
f
)
\
P
s
j
1
:
Combining the forward functions
!
Æ
I
1
,
!
Æ
P
1
, and
!
Æ
B
1
and
the backward functions
Æ
I
1
,
Æ
P
1
, and
Æ
B
1
into a global rel-
evance function using weight factors
!
I
1
=
!
P
1
=
!
B
1
=1
and
I
1
=
P
1
=
B
1
= 0
:
75 expressing that the overall
relevance of backward playing should be weighted 0.75
compared with the overall relevance of forward playing,
yields the function
$
1
shown in Figure 10:
$
1
(
f; p
) = max(
!
1
(
f; p
)
;
0
:
75
Æ
I
1
(
f; p
)
;
0
:
75
Æ
P
1
(
f; p
)
;
0
:
75
Æ
B
1
(
f; p
))
Relevance
0.25
0.50
0.75
1.00
F
pp
3
p
6
p
9
p
12
p
15
p
18
Æ
I
1
Æ
P
1
"
"
Æ
B
1
Fig. 9: Dynamic relevance functions
Æ
I
1
,
Æ
P
1
,
Æ
B
1
with
Æ
P
1
mo died
Relevance
0.25
0.50
0.75
1.00
F
pp
3
p
6
p
9
p
+3
p
+6
p
+9
Fig. 10: Global relevance function
$
1
Example 3: Bo okmarks.
Setting a b o okmark at a
sp ecic frame
b
2
F
should allow a user to jump to
that frame at any time and continue the presentation
of the video at that p oint. Therefore, frames surround-
ing a b o okmark frame
b
should have the same rele-
vance values as those surrounding the current presenta-
tion p oint
p
. Thus, dep ending on the presentation di-
rections (forward/backward) and the skip factors
s
2
IN
which should be allowed after jumping to a b o okmark,
static relevance functions
!
T
s
and p ossibly
T
s
should b e
dened for each bo okmark frame
b
based on the generic
relevance functions
!
T
s
and
T
s
, resp ectively, intro duced
ab ove:
!
T
s
(
f
)=
!
T
s
(
f
b
)
T
s
(
f
) for
T
=
I; P; B;
T
s
(
f
)=
T
s
(
f
b
)
T
s
(
f
) for
T
=
I; P; B:
In order to include these functions into a global rele-
vance function like, e. g.,
$
1
, their weighting factors
!
!
T
s
and
!
T
s
should dep end on factors like the frequency b o ok-
marks are jump ed to, the number of b o okmarks which
have b een set, and the available buer size. If, for in-
stance, the numb er of b o okmarks is small with resp ect to
the buer size and b o okmarks are referenced frequently,
factors
!
!
T
s
=
!
T
s
= 1 mightbesensible in order to give
b o okmarks the same overall relevance as the current pre-
sentation p oint. If, on the other hand, the number of
b o okmarks is very large, smaller weighting factors have
to b e chosen in order to avoid that b o okmark frames com-
pletely push out frames which are relevant for the current
presentation.
4.3 MPEG-L/MRP Algorithm
Preloading and ReplacementofFrames
The MPEG-L/MRP algorithm, which is based on the
buer management algorithm presented in [12], integrates
preloading and replacement of frames. Using the global
relevance function
, those frames of an MPEG video are
determined that are to b e loaded next as they are most
relevant for the presentation. If the buer is full, the
global relevance function is also used to determine those
frames that are to be removed to make ro om for more
relevant ones. Listing 1 shows the essential parts of the
algorithm which are explained in the following.
The buer containing the currently loaded frames is
represented by an ob ject
b
of type
Buffer
supplying
metho ds
full()
,
load()
,
toss()
, and
undo()
explained
b elow. To simplify notations,
b
is also used as a set com-
prising all currently loaded frames.
The function
LoadMostRelevantFrames()
, which is
called whenever the current presentation p oint
p
changes,
maintains two frames,
l
and
t
, with corresponding rel-
evance values,
L
and
T
(cf. Figure 11). The
load
threshold
L
represents the maximum relevance value
max
f
2
F
n
b
(
f; p
) of all frames
f
2
F
n
b
of the movie which are
currently
not
loaded, while the
toss threshold
T
represents
the minimum relevance value min
f
2
b
(
f; p
) of all frames
f
2
b
which
are
currently loaded. Thus it is known, that
all frames with a global relevance value greater than
L
are already loaded, while those having a global relevance
value lower than
T
are not loaded. The
load candidate
l
2
F
n
b
and the
toss victim
t
2
b
are frames with global
relevance values
(
l; p
)=
L
and
(
t; p
)=
T
, resp ectively.
In the snapshot shown in Figure 11, it holds for example
l
=
p
+ 9 and
t
=
p
5.
The function rep eatedly selects a load candidate
l
(line 5) and loads it into the buer (line 11), causing the
load threshold
L
= max
f
2
F
n
b
(
f; p
) to gradually decrease.
As long as there is not enough buer space for the load
candidate
l
, however (line 6), a toss victim
t
is selected
(line 7) and tossed out of the buer (line 9), causing
the toss threshold
T
= min
f
2
b
(
f; p
) to gradually increase.
Since frame sizes mightvary heavily, it might indeed b e
necessary to toss several frames
t
out of the buer b efore
b eing able to load the load candidate
l
.
Relevance
0.25
0.50
0.75
1.00
F
pp
3
p
6
p
9
p
+3
p
+6
p
+9
"
T
#
L
Fig. 11: Load and toss thresholds
L
and
T
Listing 1
LoadMostRelevantFrames
1 Buffer
b
;
2
3 LoadMostRelevantFrames(i nt
p
)
f
4 while (true)
f
5 let
l
2
F
n
b
where
(
l; p
)= max
f
2
F
n
b
(
f; p
)
;
6 while (
b
.full(
l
))
f
7 let
t
2
b
where
(
t; p
) = min
f
2
b
(
f; p
)
;
8 if (
(
t; p
)
>
(
l; p
)
)
f
b
.undo(); return;
g
9
b
.toss(
t
);
10
g
11
b
.load(
l
);
12
g
13
g
If the toss threshold
T
=
(
t; p
) b ecomes greater than
the load threshold
L
=
(
l; p
) (line 8), i. e., load and
toss thresholds meet each other, a stable state is reached
causing the function to return without loading the cur-
rent load candidate
l
anymore. In that case, one or more
toss victims
t
might already have b een tossed out of the
buer in order to make ro om for
l
. Since the available
buer space is still not suÆcient for
l
,however, these vic-
tims might b e put backinto the buer in order to avoid
unused buer space. For that reason, the metho d call
b
.toss(
t
)
(line 9) only
tentatively
tosses the frame
t
, e. g.,
by
marking
it for deletion, while the actual tossing is p er-
formed implicitly by the next call to
b
.load(
l
)
(line 11).
Alternatively, the call to
b
.undo()
(line 8) undo es all ten-
tative tossing op erations, e. g., by unmarking all marked
frames, causing them to remain in the buer.
Remark:
Even though
b
.toss(
t
)
do es not actually
toss frame
t
out of the buer, it will be treated as re-
moved by subsequent calls to
b
.full()
, of course. Fur-
thermore,
t
is virtually removed from the set
b
to avoid
that it b ecomes the toss victim in line 7 again and again.
Optimizations
The algorithm presented so far, esp ecially the selection
of the load candiate
l
and the toss victim
t
(line 5
and 7, resp ectively), is describ ed in a rather abstract
way to make it more comprehensible. Hence, it is not
directly usable for a real-world implementation, since a
straight-forward implementation of the \where clauses"
(
l; p
) = max
f
2
F
n
b
(
f; p
) and
(
t; p
) = min
f
2
b
(
f; p
) would
require a lo op over all frames
f
2
F
n
b
and
f
2
b
,
resp ectively, and a computation of the global relevance
value
(
f; p
) for each such frame
f
. Givenatypical frame
rate of 20 to 30 frames per second, a 10 minute movie
comprises 12,000 to 18,000 frames for which
(
f; p
)would
have to b e computed. Fortunately, the typical prop erties
of generic relevance functions mentioned b efore, allowa
signicant reduction of the number of necessary compu-
tations, as will b e briey explained in the following.
Consider, for example, a generic relevance function
(
x
)
which is zero-valued for
x<
0 and monotonously decreas-
ing for
x
0, and an arbitrary set
M
//
Z of integers
which is partitioned into two subsets
M
=
f
x
2
M
j
x<
0
g
and
M
+
=
f
x
2
M
j
x
0
g
containing negative and
non-negative memb ers of
M
, resp ectively. If
l
= min
M
+
and
r
= max
M
+
denote the b orders of the subset
M
+
,
then the extreme values min
x
2
M
(
x
) and max
x
2
M
(
x
) of the
generic relevance function
can b e computed as follows:
min
x
2
M
(
x
)=
0
;
if
M
6
=
;
;
(
r
)
;
if
M
=
;
;
max
x
2
M
(
x
)=
(
l
)
;
if
M
+
6
=
;
;
0
;
if
M
+
=
;
:
That means, that at most one function value
(
x
) has
to be computed in order to determine the minimum or
maximum value of
over an arbitrarily large set
M
.
4
Applied to a dynamic relevance function
Æ
(
f; p
) which
is constructed by translating and restricting a generic rel-
evance function
to a presentation set
S
F
, this means,
that at most one function value
Æ
(
f; p
) has to be computed
in order to determine the minimum or maximum value
of
Æ
over an arbitrary subset of
S
. In particular, if
b
F
is any subset of frames, min
f
2
S
\
b
Æ
(
f; p
) and max
f
2
S
n
b
Æ
(
f; p
) can
b e determined by computing at most one function value
Æ
(
f; p
).
5
Finally, if a global relevance function
is dened as
the weighted maximum of a set of dynamic relevance
functions
Æ
1
;:::;Æ
m
with corresp onding presentation sets
S
1
;:::;S
m
and weighting factors
1
;:::;
m
, its maxi-
mum value max
f
2
F
n
b
(
f; p
) can be determined by simply
comparing the weighted maximum values
j
max
f
2
S
j
n
b
Æ
(
f; p
)
of the dynamic functions
Æ
j
(
j
= 1
;:::;m
). Since each
of these maximum values, as explained above, requires at
most one function evaluation, the global maximum value
needed in line 5 of the algorithm (Listing 1) can b e com-
puted very eÆciently,too.
4
Due to symmetry prop erties, the same holds for a generic rel-
evance function
which is monotonously increasing for
x
0 and
zero-valued for
x>
0.
5
If a dynamic relevance function
Æ
P
s
is modied as shown in
Figure 9, this statement do es no longer hold: Since the function's
monotony is partially violated, its extreme values over a set of
frames might not o ccur
exactly
at, but only
near
the b orders of
the set. Nevertheless, they can b e determined by computing
a few
function values near the b orders, where the exact numb er dep ends
on the maximum numb er of consecutive P frames in the video.
If the presentation sets
S
1
;:::;S
m
are pairwise dis-
joint, it can b e shown that the minimum value min
f
2
b
(
f; p
)
of the global relevance function
, needed in line 7 of
the algorithm, can also b e determined by comparing the
weighted minimum values
j
min
f
2
S
j
\
b
Æ
j
(
f; p
) of the dy-
namic functions
Æ
j
(
j
=1
;:::;m
) and thus can be com-
puted very eÆciently, to o. Otherwise, things b ecome a
bit more diÆcult, since a frame
f
2
b
might b elong to
more than one presentation set
S
j
causing it to p ossi-
bly p ossess multiple p ositive relevance values
Æ
j
(
f; p
). If
one of them represents the global minimum value over all
frames
f
2
b
and all relevance functions
Æ
j
, it would be
selected as the toss victim, despite the fact that it might
p ossess another, greater dynamic relevance, to o. In or-
der to avoid this problem,
virtual frames
are introduced
as pairs (
f; j
)
2
F
f
1
;:::;m
g
b elonging to at most one
\virtual presentation set"
S
j
f
j
g
(which is isomorphic to
the real presentation set
S
j
). Technically speaking that
means, that the buer
b
might contain multiple
references
(representing virtual frames) to the same physical frame
f
2
F
, and that a physical frame is only tossed out of
the buer if the last virtual frame which references it is
tossed.
In principle, static relevance functions needed to sup-
p ort b o okmarks can b e treated completely analogously to
dynamic functions. If their numb er b ecomes large, how-
ever, even more sophisticated optimizations can be em-
ployed. Since static relevance values do not change with
the current presentation p oint, it is possible to precom-
pute and store them in a global sorted list which can be
treated likea
single
monotonous function.
Video Stream Construction
In parallel with the preload and replacement func-
tion just describ ed, a video stream construction func-
tion
ConstructVideoStream()
is executed which re-
assembles the individual frames contained in the buer
into a coherent MPEG video stream which can be
handed to a player. Typically, this function is
called by the player (via an appropriate interface)
whenever it needs another group of pictures to dis-
play, i. e., when the current presentation p oint
p
has changed. Therefore,
ConstructVideoStream()
in turn calls
LoadMostRelevantFrames()
in a par-
allel thread in order to up date the buer contents.
If
LoadMostRelevantFrames()
has not nished when
ConstructVideoStream()
is called the next time, it is
interrupted and called again using the new current pre-
sentation p oint
p
.
4.4 Temp oral Adaptation
When applying the MPEG-L/MRP buering technique
for transmitting an MPEG video over a network connec-
tion, it might happ en that some frames cannot be used by
an MPEG-player, b e it b ecause they are not delivered in
time or because they are broken due to transmission fail-
ures. Many existing MPEG players are not able to cop e
with missing frames or at least cannot maintain a timely
or continuous presentation, resp ectively. Therefore, the
player must be provided with an MPEG stream in which
the missing frames are replaced by corresp onding surro-
gate frames. The structure of the MPEG format allows to
dene a frame that is able to reference the whole content
of a preceding I or P frame. By providing such a frame
as a surrogate for a missing one, a correct stream can b e
constructed that maintains the time synchronous play-
out. However, to maintain the inter-frame dependencies
of the original stream, it must b e assured that each of the
surrogate frames is inserted at the right p osition in the
stream. By constructing a syntactically correct MPEG
video stream with surrogate frames, anyavailable MPEG
player can present the mo died video.
In our implementation, this kind of temp oral adap-
tation is applied to complete the MPEG stream when
frames do not arrive in time and deliver the adapted
stream to the MPEG player.
4.5 Physical Storage Management
In order to eÆciently realize the buering of frames in the
MPEG-L/MRP algorithm, an adequate physical storage
management has to b e employed. Due to the high vari-
ability of frame sizes in MPEG videos, this is a non-trivial
task. We analyzed several memory management strate-
gies in search for an appropriate storage management
of MPEG frames in the client's memory. The require-
ments a good physical storage manager must meet are
eÆcient management and good utilization of the buer
and a high degree of reusage of freed memory. Therefore,
a dynamic management of the buer is indisp ensable. A
well-known technique for dynamic buer managementis
the binary buddy algorithm [9]. Peterson and Norman
[13] analyzed dierentvariants of buddy systems (binary,
Fib onacci, and weighted) and showed that they all suer
from a high fragmentation. Due to this reason, a more
suitable memory management algorithm had to b e found.
In a simulation, we compared a bunch of buddy systems,
namely DTSS buddy [10], Starburst buddy [11], exact
buddy, and as a reference system the binary buddy. The
simulation evaluated the internal and external fragmenta-
tion, reusability of the memory, and the numb er of used
buddy segments. We made diverse test runs with dif-
ferent MPEG videos and varying parameters. In anut-
shell one can say, that the Starburst buddy was the most
suitable algorithm for storing MPEG frames in a client
buer. Although it p erforms slightly worse than the gen-
uine buddy system, it is more eÆcient in the utilization
and the reusability of the memory. So we decided to im-
plement the physical storage management of the MPEG-
L/MRP algorithm based on the Starburst buddy strategy.
5 Implementation
Since L/MRP has b een developed as a typical
client/server architecture, we have implemented the
MPEG-L/MRP strategy employing a client/server archi-
tecture, to o. The client buer following the MPEG-
L/MRP buer management strategy has b een imple-
mented using Java and the Java Media Framework (JMF)
[16]. The JMF oers an easy to use and extendable API
for the presentation of continuous media. We realized the
client buer providing an interface that meets the require-
ments of the JMF players such that the standard MPEG
player of JMF can be connected. The client buer re-
quests the data from a server corresp onding to our strat-
egy and delivers a correct MPEG-1 data stream to the
player. On the server side we employ the Informix Dy-
namic Server / Universal Data Option (IDS/UD) to man-
age { among media of other typ es { the MPEG videos.
Due to its extensibility, manifesting in so called Data-
Blades, the IDS/UD can b e extended to support frame-
based access to MPEG videos. On top of the IDS/UD
we implemented a server in Java to p erform the task of
transfering the requested frames from the media server to
the client buer.
6 Conclusion
In this pap er, we presented the MPEG-L/MRP buer-
ing technique providing
interactive
and
adaptive
stream-
ing of MPEG-1 videos that exploits MPEG-sp ecic fea-
tures such as dierent frame typ es with dierent im-
p ortance and their inter-frame dep endencies. Compared
with the original L/MRP strategy, which assumes ho-
mogeneous streams like, e. g., Motion-JPEG, the dier-
ent frame typ es of MPEG op en additional possibilities to
adapt the stream to dierent and varying bandwidths.
In the same way as the original L/MRP, the ma jor
fo cus of the strategy is the suitable supp ort for
inter-
active
video streaming. Since the essential concepts of
L/MRP, which make it sup erior to traditional preloading
and buering strategies in this resp ect [12], have b een re-
tained in MPEG-L/MRP,it is \by construction" at least
as goo d. Therefore, applications like our multimedia in-
formation system in cardiac surgery, that delivers interac-
tivemultimedia learning material over the Internet, can
b e supp orted in sucha way that a user feels much more
comfortable with the system. With MPEG-L/MRP, a
much b etter
Quality of Presentation
can b e delivered due
to smo oth reactions to the exp ected frequent user inter-
actions. Consequently,amuch b etter
Quality of Informa-
tion
is delivered to the user who { not to b e forgotten {
mighthaveto pay for the multimedia material presented.
Even though the comparison with L/MRP and the
practical exp erience just mentioned provide strong evi-
dence that MPEG-L/MRP is sup erior to other streaming
techniques, weintend to prove this assumption either with
practical p erformance measurements or with appropriate
simulations.
An imp ortant advantage of the employment of a stan-
dard video format like MPEG-1 is, that one is no longer
b ound to the proprietary video formats of commercial ap-
plications. Since MPEG-2 oers further p ossibilities for
adaptation, we consider applying an adapted version of
MPEG-L/MRP to this format.
As we are concerned with the construction of multi-
media rep ositories, MPEG-L/MRP forms one building
blo ck of such a rep ository that provides comprehensive
supp ort for dierent kinds of multimedia information sys-
tems. On each architectural level and on each granularity
of the comp onents of the rep ository envisioned, we try
to build mo dules that follow the overall goal to support
multimedia applications that, with regard to the quality
of information and with regard to the quality of delivery
and presentation, is optimally adapted to the user con-
text and system environment. In this context, to please a
user with a continuous, smo oth, and b est quality presen-
tation, MPEG-L/MRP is an imp ortant mo dule to provide
smo oth interactive delivery of MPEG-1 videos.
References
[1] Apple. Quicktime streaming. http://develop er.apple.com/
techpubs/quicktime/qtdevdocs/RM/p drame.html.
[2] Emblaze. Streaming Audio and Video { Solutions over IP Net-
works. http://www.emblaze.com.
[3] P. Halvorsen, V. Go eb el, and T. Plagemann. Q-L/MRP: A
Buer Management Mechanism for QoS Supp ort in a Mul-
timedia DBMS. In
International Workshop on Multimedia
Database Management Systems
,Dayton, 1998.
[4] C. K. Hess and R. H. Campb ell. Media Streaming Proto col:
An Adaptive Proto col for the Delivery of Audio and Video
over the Internet. In
Proc. of IEEE Intl. Conf. on Multimedia
Computing and Systems (ICMCS'99)
, Florence, Italy, June
1999.
[5] S. Hollfelder and H.-J. Lee. Data Abstractions for Multimedia
Database Systems. Technical Rep ort 1075, GMD, Darmstadt,
Germany, 1997.
[6] ISO.
Information Technology { Coding of Moving Pictures and
AssociatedAudio for Digital Storage Media at up to about 1,5
Mbit/s { Part 1: Systems
. ISO/IEC 11172-1, 1993.
[7] ISO.
Information Technology { Coding of Moving Pictures and
AssociatedAudio for Digital Storage Media at up to about 1,5
Mbit/s { Part 2: Video
. ISO/IEC 11172-2, 1993.
[8] W. Klas, C. Greiner, and R. Friedl. Cardio-OP { Gallery of
Cardiac Surgery. In
Proc. of IEEE Int. Conf. on Multimedia
Computing and Systems (ICMCS'99)
, Florence, Italy, June
1999.
[9] D. E. Knuth.
The Art Of Computer Programming
, volume
1: Fundamental Algorithms. Addison-Wesley, Reading, Mas-
sachusetts, second edition, 1973.
[10] P.D.L.Koch. Disk File Allocation Based on the Buddy Sys-
tem.
ACM Transactions on Computer Systems
, 5(4), 1987.
[11] T. J. Lehman and B. G. Lindsay. The Starburst Long Field
Manager. In
Proc. of the 15th VLDB Conference
, Amsterdam,
1989.
[12] F. Moser, A. Krai, and W. Klas. L/MRP: A Buer Man-
agement Strategy for Interactive Continuous Data Flows in a
Multimedia DBMS. In
Proc. of the 21st VLDB Conference
,
Zurich, Switzerland, 1995.
[13] J. L. Peterson and T. A. Norman. Buddy Systems.
Commu-
nications of the ACM
, 20(6):421{431, 1977.
[14] Real Networks. Real Video Technical White Pap er, Feb. 1997.
http://www.real.com/devzone/library/whitepap ers/
overview.html.
[15] Real Networks. SureStream { Delivering Superior Quality Re-
liability,Feb. 2000. http://www.realnetworks.com/devzone/
library/whitepap ers/surestrm.html.
[16] SUN Microsystems. Java Media Framework 2.0, 1999.
http://java.sun.com/pro ducts/java-media/jmf/2.0.
[17] VDOnet. VDOLive. http://www.vdo.net.
[18] G. K. Wallace. The JPEG Still Picture Compression Standard.
Comm. of the ACM
, 34(4):30{44, 1991.
[19] J. Walp ole, R. Koster, S. Cen, C. Cowan, D. Maier, D. Mc-
Namee, C. Pu, and D. Steere. A Player for Adaptive MPEG
Video Streaming over the Internet. In
Proc. of the 26th
Applied Imagery Pattern Recognition Workshop (AIPR-97),
SPIE
,Washington DC, USA, Oct 1997.
