Multimedia Systems Manuscript#Nr.

(will be inserted by hand later)
2PSM: An Ef\Thetacient Framework for Searching Video Information in a
Limited#Bandwidth Environment

Kien A. Hua, Wallapak Tavanapong, and James Z. Wang

School of Computer Science, University of Central Florida, Orlando, FL 32816#2362, USA
Received: date / Accepted: date
Abstract. We present a novel technique, called 2#Phase Ser#
vice Model, for streaming videos to home users in a limited#
bandwidth environment.This scheme \Thetarst delivers some num#
ber of non#adjacent data fragments to the client in Phase 1.
The missing fragments are then transmitted in Phase 2 as the
client is playing back the video. This approach offers many
bene\Thetats. The isochronous bandwidth required for Phase 2 can
be controlled within the capability of the transport medium.
The data fragments received during Phase 1 can be used to
provide an excellent preview of the video. They can also be
used to facilitate VCR#style operations such as fast#forward
and fast#reverse. Systems designed based on this method are
less expensive because the fast#forward and fast#reverse ver#
sions of the video \Thetales are no longer needed. Eliminating these
\Thetales also improves system performance because mapping be#
tween the regular \Thetales and their fast#forward and fast#reverse
versions is no longer part of the VCR operations. Further#
more, since each client machine handles its own VCR#style
interaction, this technique is very scalable. We provide sim#
ulation results to show that 2#Phase Service Model is able to
handle VCR functions ef\Thetaciently. We also implement a video
player called FRVplayer. With this prototype, we are able to
judge that the visual quality of the previews and VCR#style
operations is excellent. These features are essential to many
important applications. We discuss the application of FRV#
player in the design of a video management system, called

VideoCenter. This system is intended for Internet applications
such as digital video libraries.

Key words: Data organization # video library # previewing #
VCR#style interaction # video on demand # World Wide Web
1 Introduction

World#Wide#Web has become very popular in recent years. It
enables a wide variety of information to be disseminated to a
wide range of users including home users who typically access
the Web from home via a modem. Thoughmodem technology

Correspondence to: kienhua@cs.ucf.edu

has advanced to operate at a higher speed (e.g, 57,600 bps), its
bandwidth is still signi\Thetacantly low compared to that of Local
Area Networks (LANs) or Wide Area Networks (WANs).
The modem bandwidth is barely enough to support the
retrieval of texts and graphics which are the primitive media
types offered on the Web today. As the Web progresses to
provide continuous media (e.g., audios and videos), the narrow
bandwidth of the modem implicitly limits the access to these
media to those home users who can tolerate either long wait
time or highly jittering pictures.
Video
archive
Internet

Video Server
video
stream
Web Server
video
stream video
script

1
2
Modem Home user
station
Modem Home user
station

. . .
Fig. 1. An environment for video service in WWW.
Fig. 1 depicts a simpli\Thetaed on#demand video streaming
over the Web. A home user visits the Web site which pro#
vides meta information about its video clips (i.e., video titles,
descriptions, and playback rates, etc.). Once the user selects
a video, the Web server returns to the user's Web browser a
video script corresponding to the video selection (Label 1 in
Fig. 1). The Web browser then invokes a local video player
which interprets the script andmakes a connection to the video
server speci\Thetaed in the script (Label 2 in Fig. 1). After some
negotiation between the video server and the player, the video
object is streamed to the player.

2 Kien A. Hua, Wallapak Tavanapong, and James Z. Wang
Two approaches are available for streaming a video object
to a remote player:

Approach 1 : This approach encodes the video object such
that the playback bit rate requirement is less than the data
rate of the modem. This is achieved today by reducing
the video quality. A signi\Thetacant advantage of this approach
is that the users will experience a small delay once the
video selection has been made. They can start watching
the video as soon as the \Thetarst frame arrives. To avoid jitters
due to network congestion, the player may buffer some
small number of frames before the normal playback is
allowed.

Approach 2 : This approach aims at providing a better video
quality (e.g., MPEG encoding). To handle the higher
bit rate with limited bandwidth, each video \Thetale in the
server is partitioned into a sequence of data segments
(S 0 ; S 1 ; : : : ; Sn\Gamma1 ; Sn ). After S 0 has been downloaded,
the client can play back S 0 as it continues to download S 1 .
The client then proceeds to play back S 1 as it downloads

S 2 , and so forth. To ensure the continuity in the video
playback, the data fragmentation scheme must guarantee
that the playback duration of S i\Gamma1 is suf\Thetaciently long to
allow the client enough leeway to download the entire S i ,
where 1  i  n. We note that the playback can begin
as soon as the \Thetarst segment of the video, S 0 , has been
downloaded.
In this paper, we focus on the second approach, and pro#
pose techniques to address several critical problems associated
with this environment. Conventional pipelining, as described
in Approach 2, has the following drawbacks making it un#
suitable for some important Web applications such as digital
libraries and distance learning:
1. Let us consider a library of digital videos. If we know
the exact video \Thetale to retrieve, we can always make the
selection and continue to do other work while waiting
for the playback to begin in a short while. Unfortunately,
video indexing relies on similarity matching. The result of
a query usually consists of a large number of video titles
and descriptions. The users must rely on these information
to identify the desired video manually. The title and de#
scription de\Thetanitely give the user a general idea about the
video. However, a preview is usually required to give a
better picture of the entire video. Conventional pipelining
is unable to support this feature. Many digital video li#
braries, such as CAETI Internet Multimedia Library [27],
have to use an extra preview \Thetale for each video. This ap#
proach has two drawbacks. First, it requires more storage
space. Second, downloading the preview \Thetale adds delay
to the service.
2. Being able to search within a video using VCR#style oper#
ations is essential to applications such as digital libraries
and distance learning. Again, conventional pipelining fails
to support this feature rendering today's systems using ex#
tra, so called, VCR \Thetales for each video. This brute#force
approach incurs a higher storage cost, and makes the im#
plementation of VCR#style operations more complicated.
For instance, if a user suddenly requests a fast#forward dur#
ing a normal playback, some mapping mechanism must
be available to quickly identify the corresponding video
frame in the fast#forward \Thetale. The mapping can also add
delay to the VCR operations. We note that although band#
width renegotiation is another way to provide the VCR
functionality [4, 5, 18], this approach is not suitable for a
limited#bandwidth environment. We recall that the band#
width is not even enough to support the normal playback.
To address the \Thetarst problem, one must be able to download the
preview frames for free (i.e., incurring no additional delay).
To resolve the second problem, one needs to be able to support
the VCR#style operations without the fast#forward and fast#
reverse \Thetales. In this paper, we present one such technique,
called 2#Phase Service Model (2PSM). This technique is able
to support preview and VCR#style operations in a very natural
manner. It requires no additional \Thetales, and therefore eliminates
the need for mapping. The result is a very ef\Thetacient technique
which is simpler to implement.
A preliminary version of this work was published in [23].
We rewrite the current version to include the following ad#
vances in this study. We have completed our prototype which
enables us to subjectively assess the visual quality of the pre#
view and VCR#style operations. We also redid the simulations
using MPEG#4 which is more suitable for a low#bandwidth
environment.
The remaining of this paper is organized as follows. In Sec#
tion 2, we review the conventional pipelining scheme to make
the paper self#contained. The proposed technique is described
in detail in Section 3. We present our simulation model and
compare the performance of 2PSM with that of conventional
pipelining technique in Section 4. In Section 5, we analyze
the service delay in each approach. The implementation of a
video player based on 2PSM, called FRVplayer, and its appli#
cation in a video management system are discussed in Section
6. Finally, we give our concluding remarks in Section 7.
2 Conventional Pipelining

We \Thetarst review the concept of pipelining, and summarize some
analyses relevant to this paper. Interested readers are referred
to [8, 26] for more detail.
A video \Thetale is logically divided into a sequence of data seg#
ments (S 0 ; S 1 ; : : : ; Sn\Gamma1 ; Sn ), where the playback duration of

S i\Gamma1 must eclipse the time required to materialize (download)

S i , 8i; 1  i  n. After the \Thetarst data segment, S 0 , has been
downloaded, the playback can begin. Fig. 2 illustrates the
pipelining mechanism.
Overlap

. . .
. . .
S 0 S 1 S n-1 S n

S 1 S n S n-1 S 0
time
Download
Display
0
delay
Fig. 2. Pipelining mechanism.

Let S represent a video \Thetale and jSj be its size (in bits). We
de\Thetane Production#Consumption Ratio (pcr) as the ratio of the

2PSM: An Ef\Thetacient Framework for Searching Video Information in a Limited#Bandwidth Environment 3
download rate (m) (i.e., the speed of the modem in bps) to the
average playback rate (p) in bps. Thus, we have

pcr =

m
p

; where 0 ! pcr ! 1.
Let jS i j denote the size (in bits) of data segment S i . Since the
time to play back S i\Gamma1 must eclipse the time to download S i ,
the following holds:

jS i j

m

=

jS i\Gamma1 j

p

jS i j =

m
p

\Delta jS i\Gamma1 j

= pcr \Delta jS i\Gamma1 j

where 1  i  n. Since the time to download the sequence of

S 1 ; S 2 ; : : : ; Sn is equal to the time to play back the sequence
of S 0 ; S 1 ; S 2 ; : : : ; Sn\Gamma1 (Fig. 2), jS 0 j can be computed as
follows.

jSj \Gamma jS 0 j

m

=

jSj \Gamma jS n j

p

jSj \Gamma jS 0 j = pcr \Delta (jSj \Gamma jS n j)
jS 0 j = jSj \Gamma pcr \Delta (jSj \Gamma jS n j) (1)
Since the service delay of this approach is determined by jS 0 j,

Equation (1) suggests that the size of the last segment, jS n j,

should be chosen to be as small as possible. Typically, it has
the size of a minimum retrieval unit, e.g., GOP (group of
pictures) in MPEG [11]. Under this condition, since jS n j is
very small compared to jSj, Equation (1) can be simpli\Thetaed as
follows.

jS 0 j  jSj \Gamma pcr \Delta jSj
 (1 \Gamma pcr) \Delta jSj (2)
3 2#Phase Service Model

The proposed technique is presented in this section. We \Thetarst
describe the data fragmentation technique and the playback
strategy. We then explain the preview mechanism, and discuss
the methods to provide the VCR#style operations.
3.1 Normal Playback

Although pipelining can reduce the service latency to the
time required to download the \Thetarst data segment, it cannot
support previewing, nor VCR#style operations as we have
discussed in Section 1. To address these de\Thetaciencies, 2PSM
fragments a video \Thetale into a sequence of playback units,

(PU 0 ; PU 1 ; \Delta \Delta \Delta PUn ), as illustrated in Fig. 3. Each playback
unit consists of a pair of L#fragment and R#fragment, where
the pre\Thetaxes #L" and #R" stand for #local" and #remote", re#
spectively. The reason for their name will become clear later
when we discuss the download strategy. We note that the two
types of fragments interleave each other throughout the video
\Thetale. Without loss of generality, we assume that the video
\Thetales are compressed using MPEG. The L#fragment and the
R#fragment contain l and r GOFs (group of frames), respec#
tively. We note that a GOF is similar to a GOP in MPEG
except for the following situation. If a video \Thetale consists of
only I#frames, the whole video is considered as a single very
large GOP in MPEG. In our technique, we will treat each of
these I#frames as a GOF. The rational for making the sizes of
the L#fragments and R#fragments a multiple of GOFs is due
to the fact that GOF is the basic unit for data retrieval, and is
an independently decodable unit of video frames.
R-fragment L-fragment

. . L 0 R 0 R 1 R n R n-1 R 2
R
L 1 L 2 L n-1 L n

PU 2 PU 1 PU 0 PU n-1 PU n
L
Fig. 3. Logical video \Thetale organization for 2PSM.
As the name implies, the playback of a video is carried
out in two phases in 2PSM as follows:

# Initialization Phase: The player downloads the L#fragments
of all playback units. Then, it downloads the R#fragment
of the \Thetarst playback unit. (Various orders can be used to
transmit these fragments. We will discuss them in detail
later.) When arriving, these fragments are stored in a local
L#\Thetale on the client disk. After the \Thetarst R#fragment has
arrived, the player proceeds to the Playback Phase.

# Playback Phase:

Server side : The server continues to transmit the remain#
ing R#fragments to the client. The GOFs belonging to
these R#fragments are transmitted in the order they
appear in the video \Thetale.

Client side : The client displays PU 0 while receiving the
R#fragment for PU 1 . Once the client \Thetanishes the play#
back of PU 0 , it proceeds to play back PU 1 while
receiving the R#fragment for PU 2 , and so forth. This
pattern is repeated until the playback of the whole
video is done.
The two phases of 2PSM are illustrated in Fig. 4. Once
the playback is initiated, a playback buffer is used to assemble
each playback unit using an R#fragment coming from the
server and the respective L#fragment from the local L#\Thetale.
We note that the R#fragments and L#fragments get their name
from the fact that they are obtained from the remote server,
and from the local buffer, respectively.
As illustrated in Fig. 4, to ensure the continuous playback,
the time required to download the i

th

R#fragment, R i , must
be less than or equal to the playback duration of the playback
unit PU i\Gamma1 , for 1  i  n. Let jR i j and jP U i\Gamma1 j be the sizes
(in bits) of the R#fragment R i and the playback unit PU i\Gamma1 ,
respectively. The continuity principle can be expressed math#
ematically as follows:

jR i j

m

=

jP U i\Gamma1 j

p

(3)
Unlike the conventional pipelining technique, in which
the sizes of the data segments vary signi\Thetacantly (i.e., jS i j =

pcr

i

\Delta jS 0 j), the sizes of different R#fragments and different
L#fragments are reasonably uniform in 2PSM. Let j # Lj, j # Rj,

and jP U j be the average sizes (in bits) of an L#fragment, an
R#fragment, and a playback unit, respectively. Equation (3)
can be estimated in terms of the average values as follows:

4 Kien A. Hua, Wallapak Tavanapong, and James Z. Wang
Fig. 4. The two phases of 2PSM.
j # Rj
m

=

jP U j

p

j #

Rj =

m
p

\Delta jP U j
j #

Lj, therefore, can be expressed as:

j # Lj = jP U j \Gamma j # Rj =

`

1 \Gamma

m
p

'

\Delta jP U j
Substitute the Production#Consumption Ratio pcr for

m
p

, the
following holds:

j # Lj = (1 \Gamma pcr) \Delta jP U j (4)
3.2 Preview Feature

We note that if the L#fragments are downloaded in r rounds
during the Initialization Phase, such that each round down#
loads non#adjacent L#fragments spread out in the video \Thetale,
then previewing of the video is possible using frame skipping
techniques [2] after only a few rounds of downloading. That
is, the preview can be done by displaying only the frames in
the L#fragments already downloaded. In this paper, we loosely
de\Thetane preview quality as how well a preview can cover the en#
tire video. Obviously, the whole video can be used to achieve
the best preview quality. However, this would entail the worst

preview delay which is de\Thetaned as the latency before the pre#
view is enabled. On the other hand, a single GOF can be used
to offer the best preview delay; but this would result in the
worst preview quality. Thus, a good tradeoff should retrieve
a minimum number of GOFs, yet they cover the entire video
well. With this as a guide line, we see that using the \Thetarst
data segment to provide the preview feature in conventional
pipelining is a bad idea because all the preview frames would
be clustered to the beginning of the \Thetale; and therefore the
preview would be too narrowly focused on the beginning of
the video.
Let v denote the number of GOFs required to be down#
loaded before the preview is enabled. The appropriate value
for v depends on the download strategy, and the type of the
video. For example, if the video is of head#talking type, which
has few changes in the scene, v can be small. On the other
hand, if the video is of action type, where one GOF is much
different from neighboring GOFs, then v should be larger. In
any case, since the preview quality will progressively improve
as more L#fragments are arriving at the client, it is a good idea
to choose v to be small and let the user decide if another
preview is desired after more GOFs have been downloaded.
We examine three different strategies to provide the preview
feature in 2PSM in the following. They show our effort to
improve the preview quality as de\Thetaned previously.

Linear strategy : This strategy further re\Thetanes the Initializa#
tion Phase into l steps, where l is the number of GOFs
in each L#fragment. For each step i, it downloads the i

th

GOF of each L#fragment. After Step l, R 0 is downloaded
to complete the Initialization Phase. This strategy is il#
lustrated in Fig. 5. It shows the video \Thetale as a sequence
of GOFs starting from GOF 0. The GOFs belonging to
the L#fragments are colored while those belonging to the
R#fragments are not. The L#fragments are downloaded in
three steps. In this example, v is assumed to be 2 \Delta (n + 1),
where (n+1) is the number of playback units in the video.
In other words, the user is allowed to preview the video as
soon as the start of Step 3. During the preview, the player
plays the \Thetarst two consecutive GOFs (i.e., GOFs 0 and 1).
It then skips 11 GOFs, and plays the next two consecutive

2PSM: An Ef\Thetacient Framework for Searching Video Information in a Limited#Bandwidth Environment 5
27 26
GOFs available after two steps
The preview quality improves gradually.
15 14 13 11 10 1
L 0

12 9 8 2 0 3 4 5 6 7 . . . 16 17 19 18
R 0

2021 22 2324 25
0 13 26
1 14 27
2 15 28

downloaded
during step 1
downloaded
during step 2
downloaded
during step 3

28
L 1 R 1 L 2

. . .
Fig. 5. 2PSM : Linear strategy.
34 30
GOFs available after two steps
The preview quality improves gradually.
4 27 26 15 14 13 11 10 1
L 0

12 9 8 2 0 3 5 6 7 . . . 1617 19 18
R 0
202122232425
0 13 26
4 17
8 21

downloaded
during step 1
downloaded
during step 2
downloaded
during step 3

28
L 1

29 313233
30
34
L 2

R 1 R 2

PU 0 PU 1 PU 2 . . .
Fig. 6. 2PSM : Spreading strategy.
GOFs (i.e., GOFs 13 and 14). This pattern is repeated until
the player reaches the end of the \Thetale. We note that the pre#
view covers the entire video very well. Furthermore, the
user can repeat the preview as many times as necessary.
For each repetition of the preview, the preview quality
improves since more data have been downloaded.

Spreading strategy : In this strategy, the GOFs of an L#
fragment are evenly spread out in its playback unit. This
is illustrated in Fig. 6. It shows that GOFs 0, 4 and 8 (col#
ored) are part of the \Thetarst L#fragment, L 0 . They are scat#
tered across the playback unit PU 0 . This strategy allows
each L#fragment to cover its playback unit better in terms
of preview quality. Obviously, this scheme is an improve#
ment over Linear strategy which has the video frames of
each L#fragment clustered to the beginning of its playback
unit. With this data fragmentation technique, the download
of the L#fragments is done as in Linear strategy. That is,
they are downloaded in l steps. During each step i, the

i

th

GOF of each L#fragment is downloaded. After all the
L#fragments have been downloaded, R 0 is downloaded to
complete the Initialization Phase. As an example, Fig. 6
shows that the L#fragments are downloaded in three steps
because there are three GOFs in each L#fragment. As in
Fig. 5, we also assume here that v = 2 \Delta (n + 1). Thus, the
preview can be activated after two steps of downloading.
The preview plays back the GOFs 0, 4, 13, 17, etc. We note
that these GOFs are more evenly spaced out than those in
Fig. 5. In general, Spreading should perform better than
Linear technique.

Binary#Tree strategy : To further improve the quality of the
preview, we can organize the \Thetale into smallest possible
playback units. That is, the number of GOFs in the L#
fragment and the number of GOFs in the R#fragment of
each playback unit must be relatively prime. An example
of this \Thetale organization is illustrated in Fig. 7. Each box
represents a GOF. The label signi\Thetaes the GOF number.
Each column of GOFs forms a playback unit. Let l be
the number of GOFs in each L#fragment, and L i;j denote
the i

th

GOF of L#fragment L j . The L#fragments can be
downloaded in two steps as follows.
Step 1: For all j, L 1;j are downloaded in r rounds in
the breadth#\Thetarst search order as illustrated in Fig. 7.
The GOFs downloaded in this step can be viewed as
forming a binary tree. During the \Thetarst round, the GOF
corresponding to the root of the tree (at level 0) is
downloaded; two GOFs corresponding to the nodes in
level 1 of the tree are downloaded in the second round;
and so forth. In general, 2

g\Gamma1

GOFs at level (g \Gamma 1) of
the tree are downloaded during round g.

Step 2: The remaining GOFs in the L#fragments are
downloaded in the order they appear in the video.
After all the L#fragments have been downloaded, the
client downloads the \Thetarst R#fragment to complete the
Initialization Phase.

6 Kien A. Hua, Wallapak Tavanapong, and James Z. Wang
0
1
2
3
4
6
7
8
9
10
12 18
13
14
15
16
5 11 17
19
20
21
22
23
25
26
27
28
29
24 30 36 42 48
31
32
33
34
35
37
38
39
40
41
43
44
45
46
47
54 60 66 72 78 84 90
49
50
51
52
53
55
56
57
58
59
61
62
63
64
65
67
68
69
70
71
73
74
75
76
77
79
80
81
82
83
85
86
87
88
89
91
92
93
94
95
96
97
98
99
100
102
103
104
105
106
108 114
109
110
111
112
101 107 113
115
116
117
118
119
121
122
123
124
125
120 126 132 138 144
127
128
129
130
131
133
134
135
136
137
139
140
141
142
143
150 156 186 162 168174 180
145
146
147
148
149
151
152
153
154
155
158
157
189 159
190 160
187
161
188
191
163
164
165
166
167
169
170
171
172
173
175
176
177
178
179
181
182
183
184
185
downloaded
during round 1
downloaded
during round 2
downloaded
during round 3
L
R
.
.
.
.
.
.
.
.
.

GOFs available for previewing after 3 rounds
The preview quality improves gradually.

.
.
.

90
114 66 18
42
162
138
174 150 126 102 78 54 30 6

downloaded
during round 4
Fig. 7. 2PSM : Binary#tree strategy.
Using the above initialization strategy, the preview feature
can be enabled after only a few rounds in Step 1. The
example in Fig. 7 shows that the preview is available after
three rounds of downloading. In general, it is advantageous
to enable the preview feature early. This strategy lets the
user be the judge of when the preview quality is acceptable.
If a user is not satis\Thetaed with a preview, this user can always
wait for a few more rounds and preview the video again.
We note that the binary tree is used in Fig. 7 to illustrate
the frame#stream order. No trees are actually maintained
in our technique. We will discuss the details of our \Thetale
organization in Section 6.
3.3 Supporting VCR#style Operations
Among the common VCR operations (e.g., pause, fast#
forward, and fast#reverse), pause is the easiest operation to
implement. During the pause period, the server can simply
pause the transmission of the video data. Alternatively, the
player can continue to download the data and cache them in
the local buffer. Since today's computers typically have very
large disk space, the latter is preferred, and is assumed in this
paper. In any case, these two options can also be negotiated
with the server during the admission process.
Fast#forward and fast#reverse are more complex. As we
have discussed in Section 1, bandwidth renegotiation [4] can#
not be used for a limited#bandwidth environment.On the other
hand, using fast#forward and fast reverse versions of the video
\Thetales [18, 2] is expensive and makes the system more complex.
The proposed 2PSM offers a more natural environment for
supporting such interaction. As soon as the L#fragments have
been downloaded, fast#forward and fast#reverse can be car#
ried out by simply playing only the frames in the L#fragments
already cached in the local buffer. As far as the server is
concerned, these two operations are the same as the pause
operation since the server need not involve in the interaction.
This approach off loads substantial work to the clients allow#
ing the server to be more scalable. We discuss these operations
in more detail in the following.

Fast#forward : If the user presses the fast#forward button
while the player is playing a frame belonging to some L#
fragment, the player plays the remaining frames in this L#
fragment. It then skips the next R#fragment, and continues
to play only the L#fragments in the subsequent playback
units until the end of the \Thetale or the normal#play button
is pressed. On the other hand, if the user presses fast#
forward while the player is playing a frame in some R#
fragment, the player skips the remaining frames of the
current R#fragment, and continues to display only the L#
fragments in the subsequent playback units until the end of
the video or the normal#play button is pressed. Obviously,
the resumption of normal play can be done with little delay
since it requires only downloading the R#fragment of the
playback unit which contains the resumption point. We
will examine this delay more carefully in our performance
study later.

Fast#reverse : Fast#reverse is similar to fast#forward. The
only difference is the direction or the order of the display.
If the user presses fast#reverse while the player is showing
a frame of some L#fragment, the player replays all the
previous frames of this L#fragment backward, and then
continues to play the frames in the preceding L#fragments
in the reverse direction. On the other hand, if the user
presses the fast#reverse button while the player is showing
the frame of some R#fragment, the player skips the current
R#fragment and plays the preceding L#fragments in the
reverse order until the beginning of the \Thetale or the normal#
play button is pressed. The resumption of normal play is
the same as in the case of fast#forward.
4 Performance Study

Due to the fact that 2PSM does not require additional \Thetales
to support the VCR and preview functions, it is obvious that

2PSM: An Ef\Thetacient Framework for Searching Video Information in a Limited#Bandwidth Environment 7
systems based on this technique are less expensive and simpler
to implement. It is also easy to see that since the server need
not involve in the control of the VCR functions, 2PSM is
much more scalable. Nevertheless, to determine that 2PSM is
indeed a good solution, we also need to assess the delays in
supporting these operations. In this section, we evaluate the
performance of 2PSM in terms of the following delays.

# Average Resumption Delay after Fast#Forward: This is
the average time required to resume the normal play after
a fast#forward.

# Average Resumption Delay after Fast#Reverse: This is
the average time required to resume the normal play after
a fast#reverse.

# Preview Delay: This is the time spent waiting for the
preview feature to become enabled.

# Initialization Delay: This is the time duration required
to download the initial portion of the video before the
playback can begin. This is also referred to as service
delay.

In this paper, we assume that the data downloaded are cached
in the local buffer until the user discards it. With this assump#
tion, it \Thetarst seems that a fast#reverse would not incur any delay.
However, a fast#forward can cause the player to skip forward
to a future point without downloading the intermediate play#
back units. If a fast#reverse is performedsome time later, it can
take the playback to a missing playback unit skipped earlier.
In order to resume the normal play starting from this point,
a brief delay is necessary to download the R#fragment of the
current playback unit.
We will show simulation results to demonstrate that 2PSM
incurs only very short delays. These performance data will
substantiate our claim that 2PSM is a good solution for many
Web applications. We will also include the simulation results
for the conventional pipelining technique. They are used as
a reference in our study. We assume that the conventional
pipelining technique uses VCR \Thetales to provide the VCR#style
operations.
4.1 Simulation Model

The simulator for the 2PSM maintains two pointers: display
pointer and download pointer. The display pointer points at
the GOF being displayed, while the download pointer keeps
track of the GOF being downloaded. The average time to
display one GOF is assumed to be one second. That is, the
display pointer is advanced every one second. The download
pointer is advanced only when the time to download the entire
GOF has passed. Obviously, this time duration is determined
by the data rate of the modem. Initially, the display pointer and
the download pointer are set to the \Thetarst GOF. The simulator
then proceeds as follows:

# Step 1: This step simulates the Initialization Phase. The
download pointer is incremented by one every

jGOF j

m

sec#
onds to simulate the downloading of the L#fragments,
where jGOF j and m denote the average size (in bits)
of a GOF, and the data rate of the modem, respectively.
When the download pointer is equal to v, the simulated
time so far is recorded as the preview delay. We recall that

v is the number of GOFs required before the preview fea#
ture can be enabled. During this step, the playback pointer
remains at the \Thetarst GOF since the playback is not ready
until the next step. When the download pointer reaches the
last GOF in the last L#fragment, it is positioned to point
to the beginning of the \Thetarst R#fragment. This pointer then
continues to advance until it reaches the end of this R#
fragment. At this time, the total elapsed time so far is
recorded as the initialization delay. The simulator now
proceeds to Step 2.

# Step 2: The parameter V CR PROB is used to model the
user behavior. At this step, a random number between 1
and 100 is generated. If the number is less than or equal
to V CR PROB, the user requests a VCR operation and
the simulator proceeds to Step 3; otherwise, it proceeds to
Step 4. Thus, the probability of issuing a VCR request is

V CR PROB

100 .

# Step 3: The simulator generates another random number
to determine the actual VCR function. The three functions,
pause, fast#forward and fast#reverse are assumed to occur
with the same probability. These operations are simulated
as follows.

# If the pause function is selected, a random pause time
is generated between 1 and the maximum pause pe#
riod of 5 seconds. During this period, the simulator
stops incrementing the display pointer, but continues
to increase the download pointer to simulate the down#
loading of the R#fragments. After the pause period has
passed, the simulator proceeds to Step 2. (We note that
a user is allowed to perform multiple VCR operations
consecutively.)

# If a fast#forward is selected, a random destination be#
tween the next GOF and the last GOF is generated.
The simulator then does the following:

ffl It advances the download pointer to simulate the
fact that the R#fragments continue to arrive.

ffl It moves the playback pointer to the resumption
point, and logs the resumption delay as the time
required to download the R#fragment of the play#
back unit which contains the resumption point.
The simulator proceeds to Step 2.

# If a fast#reverse is selected, a random destination be#
tween the preceding GOF and the \Thetarst GOF is gener#
ated. The simulator then does the following:

ffl It advances the download pointer to simulate the
fact that the R#fragments continue to arrive.

ffl It moves the playback pointer to the resumption
point, and logs the resumption delay as the time
required to download the R#fragment of the play#
back unit which contains the resumption point.
The simulator proceeds to Step 2.

# Step 4: The display pointer is incremented by one. The
download pointer is advanced accordingly to simulate the
arrival of the GOFs in the R#fragments. At this time, the
simulation terminates if the end of the video \Thetale is en#
countered; otherwise, it proceeds to Step 2.
The simulator for the conventional pipelining technique
is similar. It also maintains two pointers, one pointing to the
GOF being downloaded (download pointer), and another one

8 Kien A. Hua, Wallapak Tavanapong, and James Z. Wang
pointing to the GOF being played back (playback pointer).
The way the simulator manages these two pointers is as fol#
lows. The display pointer is not advanced until the download
pointer has reached the second data segment. Starting from
this moment, the display pointer is advanced at the playback
rate (i.e., one GOF per second) while the download pointer is
advanced at the rate of the modem. When a pause operation
is encountered, the playback pointer is stopped for the pause
period while the download pointer continues to advance. If a
fast#forward or a fast#reverse occurs, the simulator moves the
playback pointer to the resumption point, and logs the delay
required for the resumption of the normal playback. These
delays are used to compute the average delays at the end of
the simulation run.
4.2 Simulation Results

We discuss the simulation results in the following subsections.
4.2.1 Average Resumption Delay for VCR Functions
For this particular simulation, we \Thetaxed the data rate of the mo#
dem and the playback requirement at 28,800 bps and 64,000
bps, respectively. The latter is the maximum bit rate speci#
\Thetaed in VLBV (Very Low Bit#rate Video) core of the MPEG#4
standard [12]. The video length was varied between 1 (60
GOFs) and 10 minutes (600 GOFs). The probability that a
user performs a VCR function at the end of each one#second
interval was set to 5% (i.e., V CR PROB = 5). The results
are plotted in Fig. 8 and Fig. 9.
0
10
20
30
40
50
60
1 2 3 4 5 6 7 8 9 10

Video Length (min)

Delay
(sec)

2PSM Pipelining
Fig. 8. Average resumption delay after fast#forward.

Fig. 8 shows that the average delay after a fast#forward
in the conventional pipelining technique increases with the
increases in the video length. This is due to the fact that
the conventional pipelining partitions the video \Thetale into very
large data segments. The resumption of the normal play after
a fast#forward may require part of the data segment contain#
ing the resumption point and part of the next data segment

0
2
4
6
8
10
12
1 2 3 4 5 6 7 8 9 10

Video Length (min)

Delay
(sec)

2PSM Pipelining
Fig. 9. Average resumption delay after fast#reverse.
to be downloaded before the resumption can take place. As
a result, a larger video \Thetale which has larger data segments
will more likely incur longer resumption delay after a fast#
forward. On the contrary, we observe that the curve of 2PSM
in Fig. 8 is essentially at. This is due to the fact that the
delay is only dependent on the size of the R#fragment, not the
video length. This property is very desirable. Comparing the
two techniques, we see that 2PSM outperforms conventional
pipelining by a very wide margin. For instance, if the video
length is \Thetave minutes, 2PSM is more than four times better.
The performance difference increases with the increases in
the video length. The fact that 2PSM requires a delay of no
more than eight seconds using a 28,800#bps modem indicates
that this technique is good for many Web applications.
The plots for the average resumption delay after a fast#
reverse are given in Fig. 9. We also observe that the curve
of conventional pipelining increases with the increases in the
video length while the curve of 2PSM is rather level. These
phenomenons are due to the same reasons explained for Fig. 8.
Again, we see that 2PSM requires a very small delay to resume
the normal play after a fast#reverse. The latency of no more
than six seconds is well within the tolerable level for most
Web applications.
Comparing Fig. 8 and Fig. 9, we notice that the average
resumption delays in the two directions (i.e., forwarding or
reversing) are consistent under 2PSM, while they are very dif#
ferent for the pipelining scheme. The consistent performance
in either direction is an important characteristic to enhance
users' satisfaction.
4.2.2 Preview Delay
For this study, we used the same parameters as in Section
4.2.1, and measured the preview delay. The results are plotted
in Fig. 10. We allowed the user to preview after 5% of the
video has been downloaded. Our experiments with the video
player described in the next section suggest that 5% is plenty
to provide a general idea about the video.

2PSM: An Ef\Thetacient Framework for Searching Video Information in a Limited#Bandwidth Environment 9
0
100
200
300
400
500
600
700
800
1 2 3 4 5 6 7 8 9 10

Video Length (min)

Delay
(sec)

Initialization Delay Preview Delay
Fig. 10. Preview Delay vs Initialization Delay.
Fig. 10 demonstrates that the preview delay is much lower
than the initialization delay. For example, when the video
length is 5 minutes, users are able to watch the preview after
about 30 seconds of waiting, while the normal play can begin
only after about 6 minutes. Thus, the user can cancel the video
after only 30 seconds if it is not the desired one, instead of
having to waste the next 5.5 minutes waiting for the wrong
video. This important feature provides the video browsing
capability to a Web browser.
We note that we do not show the curves for the conven#
tional pipelining in Fig. 10 because it cannot effectively sup#
port preview. One can consider using the \Thetarst 5% of the video
as the preview frames. However, this approach will result in
very poor preview quality as we have discussed in Section 3.
4.2.3 Effect of Production#Consumption Ratio
In this experiment, the video length was \Thetaxed at 10 minutes.
We varied the production#consumption ratio (pcr) by varying
the playback rate between 32,000 and 28,8000 bps. We note
that varying the playback rate has the same effect to pcr as
varying the data rate of the modem. Thus, the simulation re#
sults presented in this subsection can be interpreted as either
the effect of the playback requirement or the effect of the
download bandwidth on the system performance. The simu#
lation results are plotted in Fig. 11. It shows the resumption
delay for fast#forward and fast#reverse for both 2PSM and
conventional pipelining.
We observe that the resumption delays for 2PSM are al#
ways under eight seconds. On the other hand, the resumption
delays after fast#forward are very large for a conventional
pipelining technique, unless pcr is very large, i.e., the down#
load bandwidth is almost the same as the playback rate. This
indicates that conventional pipelining is inadequate for provid#
ing VCR#style interaction in a low#bandwidth environment.

0
10
20
30
40
50
60
70
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

Production Consumption Ratio

Delay
(sec)

2PSM:FF
2PSM:FR
Pipelining:FF
Pipelining:FR
Fig. 11. Effect of production#consumption ratio.
5 Analysis of Initialization Delay
We recall that initialization delay is de\Thetaned as the time re#
quired to \Thetall the client buffer with the preloaded data before
the playback can begin. In this section, we provide mathemat#
ical proof to show that 2PSM and Pipelining require about the
same initialization delay. We recall the following notations:

# m: Modem transmission rate (in bps)

# p: Video playback rate (in bps)

# pcr: Production#consumption ratio

# jSj: Size (in bits) of the entire video \Thetale

# jS 0 j: Size (in bits) of the \Thetarst data segment in conventional
pipelining technique

# jR 0 j: Size (in bits) of the \Thetarst R#fragment in 2PSM

# jP U j: Average size (in bits) of a playback unit in 2PSM

# j #

Lj: Average size (in bits) of an L#fragment in 2PSM

# jLj: Accumulated size (in bits) of all L#fragments in 2PSM
We compute the initialization delays for Pipelining and
2PSM in the following.

# Pipelining: We recall from Equation (2) in Section 2 that

jS 0 j  (1 \Gamma pcr) \Delta jSj

Since the playback can begin as soon as S 0 has been
downloaded, the initialization delay for this scheme can
be derived as follows:

T init pipe =

jS 0 j

m



1 \Gamma pcr
m

\Delta jSj (5)

# 2PSM: The size of all (n+1) L#fragments can be computed
as follows:

jLj = (n + 1) \Delta j # Lj (6)
Using Equation (4) from Section 3.1, jLj can be rewritten
as follows:

10 Kien A. Hua, Wallapak Tavanapong, and James Z. Wang
jLj = (n + 1) \Delta (1 \Gamma pcr) \Delta jP U j

= (n + 1) \Delta (1 \Gamma pcr) \Delta
jSj

n + 1
= (1 \Gamma pcr) \Delta jSj

Since 2PSM can initiate the playback as soon as all the L#
fragments and the \Thetarst R#fragment (R 0 ) have been down#
loaded, the initialization delay can be derived as follows:

T init 2PSM =

jLj + jR 0 j

m

=
(1 \Gamma pcr) \Delta jSj

m

+

jR 0 j

m



1 \Gamma pcr
m

\Delta jSj (7)
Comparing Equations (5) and (7), we conclude that 2PSM and
Pipelining require about the same initialization delay. Hence,
the proposed technique is able to offer many desirable features
without compromising on the initialization delay.
6 Implementation

We have implemented a prototype for the 2PSM, called FRV#
player. FRVplayer is an acronym for Function#Rich Video
player. The player gets its name from the fact that it is able
to offer the preview feature, and support VCR#style opera#
tions effectively. FRVplayer is an important component of
our VideoCenter software which is being developed to sup#
port digital video libraries. We discuss these two software in
this section.
6.1 FRVplayer

We \Thetarst describe the run#time environment of FRVplayer. We
then discuss its system architecture, and \Thetanally examine the
\Thetale format.
6.1.1 Run#Time Environment
FRVplayer runs on Linux systems. It can be run as a stand
alone program or invoked as a helper program of a Web
browser (e.g., Netscape Navigator version 3.0.) Besides FRV#
player, the following components are required to deliver
videos to the user.

# Web Server: The Web server publishes the script \Thetales for
the videos it offers. The video server may not be needed
if the script \Thetale has been downloaded and stored on the
client's disk.

# Video Server: The server waits on a speci\Thetac port for a
service request from some player. For each request, the
server transmits the video data to the player after they
have negotiated and exchanged control information. The
video \Thetales must be organized using the 2PSM format.
Each GOF is encoded as an MPEG's GOP unless all the
frames in the video are of type I. In this case, each frame
is a GOF. We will discuss the \Thetale format in more detail
later.
We note that MPEG#4 [12] is more suitable for the Internet
as the standard is being designed for low bandwidth envi#
ronments. We plan to support this standard in the future. In
addition, since the focus of this study is on the \Thetale organization
and the data streaming technique, the current version of the
video server is quite simple. We will enhance the video server
in our VideoCenter project. Some of the sophisticated server
technology are presented in [3, 6, 7, 9, 10, 13, 16, 20, 25, 24].
6.2 System Architecture

We implemented our system using the following packages:

# Continuous Media Toolkit (CMT) [22] version 3.03b3: CMT
provides a exible and complete programming environ#
ment for developing continuous media applications on
several platforms. CMT extends Tcl/Tk [17] and Tcl#
DP [21] to support media in continuous domain. It sup#
ports several video \Thetale formats such as MPEG, Motion
JPEG, and H.261. Transport protocols such as RTP [1]
and UDP [14] can be used to deliver the media to the
client.

# Tk Interface Extension (Tix) [15] version 4.1.0: Tix extends
Tk to provide a richer set of attractive megawidgets which
consist of a number of Tk widgets. We use Tix to develop
the user interface for the player.
We describe our implementation in more detail in the follow#
ing.
FRVplayer is based on cmplayer [19]. Cmplayer inter#
prets CM script \Thetales for several types of information such as
hostnames of the media servers, locations of the media \Thetales,
etc. We modi\Thetaed it to accept two additional parameters in the
script \Thetale: preview and play. They are the default values for
preview delay and playback delay, respectively, speci\Thetaed by
the video provider. The client is allowed to override these de#
faults. FRVplayer supports two preview options: #according

to media provider# or #according to script#. When #accord#

ing to media providers# option is chosen, the player ignores
the values speci\Thetaed in the script. The preview and playback
delays are as speci\Thetaed by the media provider during the me#
dia preparation process. On the other hand, if #according to
script# is chosen, the delays are determined by the values
stated in the user's script. We make this option available be#
cause the visual quality is subjective and often depends on the
type of the video.
The CMT objects relevant to our prototype are shown
in Fig. 12. At the server, MPEGSegment object periodi#
cally prepares frames for PacketSource object. In each cycle,

MPEGSegment object determines the number of frames, the
frames to be transmitted, and their transmission order. It re#
lies on MPEGDataFile object to retrieve the needed MPEG
frames from the server disk. PacketSource object receives
the frames from MPEGSegment, organizes them into packets,
and transmits them to PacketDest object residing in the client.

PacketDest object assembles the packets and passes them to

MPEGPlay object. PacketSource and PacketDest objects em#
ploy UDP transport protocol and handle all low level com#
munication. After MPEGPlay object reassembles the frames,

MPEGSoftwareDevice renders them onto the screen. We mod#
i\Thetaed MPEGDataFile, MPEGSegment, and MPEGPlay as fol#
lows.

2PSM: An Ef\Thetacient Framework for Searching Video Information in a Limited#Bandwidth Environment 11
MPEGDataFile
MPEGSegment
PacketSource
MPEGPlay
MPEGSoftwareDevice
PacketDest
Server Side Client Side
Fig. 12. Flow of media data through CMT objects.
# MPEGDataFile was modi\Thetaed to recognize 2PSM \Thetale for#
mat. This format will be described in the next subsection.

# We modi\Thetaed MPEGSegment to \Thetarst transmit frames of
the L#fragments using Linear strategy followed by frames
of the R#fragments. We intend to use the Binary#Tree
scheme in a future version. We also modi\Thetaed this object
to supply additional information to MPEGPlay such as
the total number of GOFs in the \Thetale and the default values
for preview and play.

# We had to modify MPEGPlay extensively. It has to store
the downloaded L#fragments to a local \Thetale, to maintain
meta information about these fragments, and to support
the preview and VCR#style operations. During a video
session, each video frame is discarded from memory after
it is displayed. The entire video \Thetale, however, is saved to
a local disk to allow future references.
6.2.1 Chunk File Format
Before an MPEG#1 video can be used in our environment,
it needs to be organized into a chunk \Thetale. The format of the
chunk \Thetale is similar to that of CMT. That is, it also consists
of several header segments and one data segment. The header
segments contain information about the media data such as
the locations, sizes, and display times of the video frames.
However, our chunk \Thetale is different from that of CMT as
follows:

# Video frames are arranged in the chunk \Thetale in the trans#
mission order in order to facilitate sequential access of
the video \Thetale during the video delivery. That is, frames
transmitted in the \Thetarst round of Phase 1 (L#fragments) are
stored \Thetarst in the data segment, followed by frames trans#
mitted in the second round of Phase 1 (more L#fragments),
and so forth. Frames transmitted during the second phase
(R#fragments) are placed after all the L#fragments.

# We add one header segment to record the default values for
the preview delay (preview) and playback delay (play).
They are used to inform the player when to enable the
preview feature and the playback, respectively. As we have
discussed, these indicators are set by the media provider,
but can be overridden by the user at the receiving end.

6.3 VideoCenter

We are implementing a video management system for Web
applications called VideoCenter. This system is built on top
of FRVplayer. The user interface of VideoCenter consists of
\Thetave main panels as shown in Fig. 13. They are described in
the following.

# Query: This is the user interface for the Query Proces#
sor (Fig. 13(a)). It takes a set of keywords as the user's
impression of the desired videos. A text description is
used internally to describe each video object. Given a set
of keywords, the query processor employs text retrieval
techniques to determine the relevant videos.

# Results: The results of a query are displayed on this panel
(Fig. 13(b)). Each result consists of the title and the de#
scription of the video along with its degree of relevance
to the query. These video are listed in the order of their
relevancy.

# Playback: When a user clicks on a title on the Results
panel, The Playback panel pops up in the Initialization
mode (Fig. 13(c)). Initially, all the VCR functions are
disabled. When the preview is ready, the preview button
(i.e., the circle) lights up. If the user presses this button
at this time, the preview is shown on the screen. The user
can stop the preview at any time by pressing the stop
button, i.e., the square. When the playback is ready, all
the standard VCR buttons are enabled, and the preview
button is turned off. The user can now start the video by
pressing the play button (Fig. 13(d)). All the other VCR
buttons also become available to assist the user to search
within the video.

# File: This is the user interface for the File Manager
(Fig. 13(e)). It provides the facility for adding or removing
videos from the library. It also allows the user to bypass
the Query Manager, if the exact video is known.

# Options: This panel is used by the user to specify the
capability of the client machine (Fig. 13(f)). We note that
the user can override the default delay for preview by
selecting the #According to script# option.
7 Concluding Remarks

Playing videos from remote sites has not been popular in
the homes due to the following reasons. Today's video play#
ers either have to sacri\Thetace the playback quality (conventional
data streaming technique), or they require long delay to ini#
tialize the client's buffer with a signi\Thetacant portion of the
video (pipelining techniques). For important applications such
as digital libraries and distance learning, these standard ap#
proaches also fail to provide an effective environment for
searching video information. Typically, there are two levels
of searching:

# Level 1: Searching for the desired video.

# Level 2: Searching within the desired video for speci\Thetac
information.
Since bandwidth renegotiation is not an option for a low#
bandwidth environment, today's systems have to rely on pre#
view and VCR \Thetales to support level#1 and level#2 search op#
erations, respectively. This brute#force approach incurs addi#
tional delays and adds more cost to the system. In this paper,

12 Kien A. Hua, Wallapak Tavanapong, and James Z. Wang
(a) Query Panel (b) Results Panel
(c) Playback Panel: Previewing (d) Playback Panel: Normal Play
(e) File Panel (f) Options Panel

Fig. 13. Screen Shots of VideoCenter.
we introduced a 2#Phase Service Model (2PSM) which ad#
dresses the above problems in an elegant way. The advantages
of this technique are many:
1. It does not require additional \Thetales to provide the preview
feature.
2. Downloading the preview frames is free since this process
is blent with the normal playback operation.
3. It does not require additional \Thetales to support the VCR
functionality.
4. No mapping mechanism is necessary to associate video
frames with their image in the VCR \Thetales.
5. Each client manages its own VCR#style interaction. Server
is not involved.
Items 1, 3 and 4 imply that systems based on 2PSM are less
expensive; items 2 and 4 allow 2PSM to offer better perfor#
mance; and item 5 makes 2PSM more scalable.
We developed a simulation model to compare the perfor#
mance of 2#Phase Service Model and conventional pipelin#

2PSM: An Ef\Thetacient Framework for Searching Video Information in a Limited#Bandwidth Environment 13
ing. The results indicate that only 2#Phase Service Model
can effectively offer the preview and search operations in a
limited#bandwidth environment. To ensure that the proposed
technique does not impose any subtle dif\Thetaculty in practice, we
implemented a Function#Rich Video player (FRVplayer). Our
implementation experience con\Thetarms that the new approach
is simpler than having to deal with extra VCR and preview
\Thetales. It also demonstrates that the client can handle its own
VCR#style interaction without involving the server. With this
system, we were also able to judge that the visual quality
of the preview feature is excellent. We are currently using
FRVplayer to implement a video management system for the
Internet called VideoCenter. We presented the details of its
design and provided some screen shots of the user interface
in this paper.
In summary, 2#Phase Service Model offers a major step
forward in making video#based applications more appealing
to home users. It provides an ef\Thetacient framework for search#
ing video information in a limited#bandwidth environment.
Although we have discussed this technology in the context of
home users, the discussion can be generalized to include any
distributed multimedia applications which require a bit rate
higher than what the transport medium can sustain.
Acknowledgement. This research is partially supported by the National Sci#
ence Foundation grant ANI#9714591.
References

1. Audio#Video Transport Working Group, Schulzrinne H, Casner S, Fred#
erick R, and Jacobson V Rtp: A transport protocol for real#time appli#
cations. In RFC 1889, January 1996.
2. Chen M, Kandlur D, and Yu PS Support for fully interactive playout
in a disk#array#based video server. In Proc. of ACM Multimedia, pages
391#398, 1994.
3. Dan A and Sitaram A. An online video placement policy based on
bandwidth to space ratio (BSR). In Proc. of the 1995 SIGMOD Conf.,

pages 376#385, May 1995.
4. Dey#Sircar JK. et al. Providing VCR capabilities in large#scale video
servers. In Proc. of ACM Multimedia, pages 25#32, October 1994.
5. Feng W, Jahanian F, and Sechrest S Providing VCR functionality in
a constant quality video#on#demand transportation service. In Proc. of
IEEE Multimedia '96, pages 127#135, June 1996.
6. Federighi C and Rowe LA The design and implementation of the UCB
video on demand system. In Proc. of IS&TISPIE Int'l Symp. on Elec.
Imaging:Science and Technology, San Jose, CA, February 1994.
7. Freedman CS and DeWitt DJ The SPIFFI scalable video#on#demand
system. In Proc. of ACM SIGMOD Conference, pages 352#363, San
Jose, CA, May 1995.
8. Ghandeharizadeh S and Shahabi C On multimedia repositories, personal
computers, and hierarcical storage systems. In Proc. of ACM Multimedia,

pages 407#416, October 1994.
9. Hua KA and Sheu S Skyscraper broadcasting: A new broadcasting
scheme for metropolitan video#on#demand systems. In Proc. of ACM
SIGCOMM, Cannes, France, 1997.
10. Sheu S, Hua KA, and Tavanapong W Chaining: A generalized batching
technique for video#on#demand systems. In Proc. of the Int'l Conf. on
Multimedia Computing and Systems, pages 110#117, Ottawa, Ontario,
Canada, June 1997.
11. ISO Standard: IS 11172. Coding of moving pictures and associated
audio # for digital storage media at up to about 1.5 Mbits/s. November
1992.
12. ISO/IEC JTC1/SC29/WG 11 N1730. Overview of the MPEG#4 Stan#
dard. Stockholm, July 1997.
13. Jadav D and Choudhary A Designing and implementing high#
performance media#on#demand servers. IEEE Parallel and Distributed
Technology, pages 29#39, Summer 1995.
14. Kochan S. G. et. al. Unix Networking. Hayden Books, IN, 1989.
15. Lam IK. Tix Programming Guide. ftp://ftp.xpi.com/pub/tix#4.0.ps.gz.
16. Neufeld G, Makaroff D, and Hutchinson N The design of a variable bit
rate continuous media server. In Proc. of the 5th International Workshop
on Network and Operating Support for Digital Audio and Video, pages
354#357, Durham, New Hampshire, USA, April 1995.
17. Ousterhout JK Tcl and the Tk Toolkit. Addison#Wesley Publishing
Company, Inc, 1994.
18. Ozden et al. A low#cost storage server for movie on demand databases.
In Proc. of the 20th VLDB Conference, Santiago, Chile, 1994.
19. Patel KM, Simpson D, Wu D, and Rowe LA Synchronized contin#
uous media playback through the World Wide Web. In Proc. of the
4th ACM International Multimedia Conference, pages 435#436, Boston,
MA, USA, November 1996.
20. Rangan PV and Vin H Designing \Thetale systems for digital video and audio.
In Proc. ACM Symposium on Operating Systems Principles, pages 69#
79, 1991.
21. Smith BC, Rowe LA, and Yen SC Tcl distributed programming. In Proc.
of the 1993 Tcl/TK Workship, Berkeley, CA, USA, June 1993.
22. Smith BC, Rowe LA, Konstan J, and Patel KD The Berkeley contin#
uous media toolkit. In Proc. of the 4th ACM International Multimedia
Conference, pages 451#452, Boston, MA, USA, November 1996.
23. Tavanapong W, Hua KA, and Wang JZ A framework for supporting pre#
viewing and VCR operations in a low bandwidth environment. In Proc.
of the ACM Multimedia Systems, pages 303#312, Seattle, Washington,
U.S.A., November 1997.
24. Vernick M, Venkatramani C, and Chiueh TC Adventures in building
the Stoney Brook video server. In Proc. of ACM Multimedia, pages
287#295, November 1996.
25. Vin HM, Goyal P, Goyal Al, and Goyal An A statistical admission
control algorithm for multimedia servers. In Proc. of ACM Multimedia,

pages 33#40, October 1994.
26. Wang JZ, Hua KA, and Young HC SEP: a space ef\Thetacient pipelining
technique for managing disk buffers in multimedia servers. In Proc. of
the IEEE int'l Conf. on Multimedia Computing and Systems, Hiroshima,
Japan, June 1996.
27. Wolf W, Liang Y, Kozuch M, Yu H, Phillips M,Weekes M, and Debruyne
A A digital video library on the World Wide Web. In Proc. of ACM
Multimedia, pages 433#434, November 1996.
Kien A. Hua received the B.S. degree
in Computer Science, M.S. and Ph.D. de#
grees in Electrical Engineering, all from
the University of Illinois at Urbana Cham#
paign, in 1982, 1984 and 1987, respec#
tively. From 1987 to 1990, he worked
for IBM, where he led a project to im#
plement a highly parallel computer. This
was a precursor to the series of products
known as SPx (i.e., SP1, SP2, etc.) While
at IBM, Dr. Hua also led another project
to design a high#performance processor
for mainframe computers. This work led
to a Best Paper Award and a Best Presen#
ter Award from IEEE for his presentation
at the International Conference on Com#
puter Design in 1990. Dr. Hua joined the University of Central Florida in 1990.
He is currently an associate professor in the School of Computer Science,
and the Director of the Database Systems Laboratory. His current research
interests include database management systems, media servers, and multime#
dia communications. He is a member of IEEE and Association of Computing
Machinery. He has served on various program committees for the ACM and
IEEE.
 Kien A. Hua, Wallapak Tavanapong, and James Z. Wang
Wallapak Tavanapong received the
B.S. degree in Computer Science from
Thammasat University in Thailand in
1992 and an M.S. degree in Computer
Science from the University of Central
Florida in 1995. She is currently a Ph.D.
candidate in the School of Computer Sci#
ence at the University of Central Florida.
Her research interests include multime#
dia systems, networking, and database
systems. She is a student member of
the Association of Computing Machinery
(ACM) and IEEE.
James Zijun Wang received the B.S.
and M.S. degrees in Computer Science
from the University of Science and Tech#
nology of China, in 1990 and 1993, re#
spectively. He is currently a Ph.D. candi#
date in the School of Computer Science at
the University of Central Florida. His cur#
rent research interests include multimedia
systems, data compression and network#
ing.
This article was processed by the author using the L a T E X style \Thetale pljour2

from Springer#Verlag.

