Efficient support for interactive scanning operations in MPEG-based video-on-demand systems.
In this paper, we present an efficient approachfor supporting fast-scanning (FS) operations in MPEG-based video-on-demand (VOD) systems. This approach is based onstoring multiple, differently encoded versions of the samemovie at the server. A <i>normal version</i> is used for normalplayback, while several <i>scan versions</i> are used for FS. Eachscan version supports forward and backward FS at a givenspeedup. The server responds to an FS request by switching from the normal version to an appropriate scan version.Scanning versions are produced by encoding a sample of theraw frames using the same GOP pattern of the normal version. When a scanning version is decoded and played back atthe normal frame rate, it gives a perceptual motion speedup.By being able to control the traffic envelopes of the scanversions, our approach can be integrated into a previouslyproposed framework for distributing archived, MPEG-coded video streams. FS operations are supported using no or littleextra network bandwidth beyond what is already allocatedfor normal playback. Mechanisms for controlling the trafficenvelopes of the scan versions are presented. The actionstaken by the server and the client's decoder in response tovarious types of interactive requests are described in detail.The latency incurred in implementing various interactive requests is shown to be within an acceptable range. Stripingand disk-scheduling strategies for storing various versions atthe server are presented. Issues related to the implementationof our approach are discussed.
Introduction
The maturing of video compression technologies, magnetic storage subsystems, and broadband networking
has made video-on-demand (VOD) over computer networks more viable than ever. Major
carriers have tested small-scale VOD systems, and companies that provide related services and products
are emerging (cf. [18, 6]). To improve the marketability of VOD services and accelerate their
wide-scale deployment, these services must support user interactivity at affordable cost. At mini-
mum, an interactive VOD service must allow users to dynamically request basic VCR operations,
Part of this paper was presented at the ACM/SPIE Multimedia Computing and Networking Conference, 1998.
y Department of Electrical and Computer Engineering, University of Arizona, Tucson, AZ 85718. Tel. (520) 621-
8731. krunz@ece.arizona.edu. This work was partially supported by an NSF CAREER Award ANI-9733143 and
partially by a University of Arizona Faculty-Grant Award.
z Department of Computer Science, University of Maryland, College Park, MD 20742.
such as stop-resume, pause-resume, slow motion, jump (forward or backward), and fast scanning
(i.e., viewing the movie forward or backward at multiple times the normal playback rate).
The difficulty of supporting interactivity in a VOD system varies from one interactive function
to another. A stop, jump, or pause followed by resume are relatively easy to support, as they do not
require more bandwidth than what is required for normal playback. On the other hand, fast-scanning
involves displaying frames at several times the normal rate. Transporting and decoding frames
at multiple times the normal frame rate is prohibitively expensive and is infeasible with today's
hardware decoders. Backward FS is even more difficult to support in compression schemes that
involve motion interpolated frames, such as B frames in the MPEG scheme [17]. In the case of
MPEG, all the reference frames in a Group of Pictures (GOP) must be decoded before B frames of
that GOP can be played back in the reverse order.
Several approaches have been proposed to support interactivity in a VOD system. In [26] interactive
operations, including scanning, are implemented at the client side using prefetched frames.
The attractiveness of this approach lies in its transparency to both the network and the server. How-
ever, if a scanning operation lasts for an extended period of time, a significant portion of the movie
must be prefetched. In addition to the large buffer requirement, excessive prefetching necessitates
requesting the movie long before its commencement. Scanning operations can also be supported by
transmitting frames at multiple times the normal frame rate over a communications channel that is
different from the one used for normal playback [12, 28]. Since at a given point in time only a small
percentage of users are in the interactive mode, the "interactive channel" can be shared by several
users. However, in this case there is a small probability that a request for a FS operation will be
rejected (i.e., FS operations are guaranteed on a statistical basis). During the scanning operation,
video frames must be decoded at multiple times the normal decoding rate.
Interactivity has also been addressed in the context of batching [2, 1, 3, 11, 15, 24, 25, 34]. As an
example, in [2] the authors assume that the VOD server operates in a multicast environment, whereby
multiple instances of each movie are being simultaneously distributed. However, these instants have
different logical times. VCR operations are implemented by moving the user to a multicast group
with an appropriate logical time. Since the number of the different instances of the same movie is
limited, this scheme can only support "discontinuous" VCR functions. The set-top buffer needed to
support FS operations can be excessive if the number of multiple instances is small. Furthermore,
the decoder is still required to process frames at multiple times the normal frame rate to achieve a
FS effect.
FS functions can also be supported by dropping parts of the original compressed video stream
[9, 31, 7, 27]. Dropping aims at reducing both the transport and the decoding requirements of
FS without causing significant degradation in video quality. In MPEG-2, dropping is facilitated
by various modes of scalability (spatial, temporal, and SNR) [17]. Spatial scalability, for example,
provides the means to drop the less important data (the enhancement layer) and maintain the
essential data (the base layer). Typically, dropping is performed after compression, so it must be
done selectively to ensure that the dropped data will not result in significant degradation in video
quality. For example, if whole MPEG frames are to be dropped, then dropping must take into
account the dependency structure of the MPEG sequence. One possibility is to drop all B frames
of an MPEG stream and transmit anchor frames (I and P) [7]. When the transmitted frames are
played back at the normal playback rate, they give the visual perception of a FS. Another alternative
is to drop MPEG frames on a per-GOP basis [9]. Since a GOP interval corresponds to about half
of a second, this approach introduces discontinuities in the movie. A third approach is to skip a
trailing part of each GOP and transmit the first few frames of the GOP [27] (the transmitted frames
must be chosen in such a manner that they can be decoded independently of the skipped frames).
The transmitted frames are then played back at the normal frame rate. A good discussion of these
and other MPEG-related techniques is given in [31]. Instead of dropping frames after compression,
some researchers suggested supporting FS operations using separate copies of the movie that are
encoded at lower quality than the quality of the normal playback copy [30]. These "scan" copies
include only I and P frames (i.e., B frames are not used). This makes it easier to provide backward
fast-scan. The motion vectors of the predicted frames are encoded in such a manner so as to reduce
the artifacts when playing frames in the reverse order.
In this work, we introduce an efficient approach for supporting forward fast-scanning (FFS) and
backward fast-scanning (BFS) in a VOD system. Similar to [30], our approach is based on encoding
separate copies of the movie to be used for FS operations, with each copy being generated by skipping
raw video frames before compression. We refer to these versions as the scan versions, and to the
one used for normal playback as the normal version. Each scan version is used to provide both
BFS and FFS at a given speedup. Scan versions are encoded in a way such that when played back
at the normal frame rate, they give the perception of a faster video in the forward or backward
direction. In contrast to the approach in [30], the scan versions are encoded using the same GOP
of the normal version (B frames are included). The encoding of a scan version is performed in
a manner that enforces a particular time-varying traffic envelope for that version. This form of
rate-controlled compression results in variable picture quality during FS. By making the envelopes
of the scan versions identical or sufficiently close to the envelope of the normal version, FS can be
integrated into a previously proposed framework for the distribution of archived, MPEG-coded video
streams [21, 22]. By generating scan versions that exhibit similar envelopes to the normal version,
FS operations can be made transparent to the underlying network, and they can be supported with
little or no extra bandwidth and at the same decoding rate of normal playback.
The paper is organized as follows. In Section 2 we briefly describe our previously proposed frame-work
for video distribution based on time-varying traffic envelopes. In Section 3 the preprocessing
steps required to support FS operations are presented. Section 4 provides detailed description of
how FS-related interactivity is supported. Signalling between the client and the server is discussed
in Section 5. In Section 6 we discuss disk scheduling that is needed for our proposed FS approach.
Implementation issues are briefly discussed in Section 7. In Section 8 we compare our scheme against
other FS schemes. Finally, Section 9 summarizes the paper and points to open research issues.
Envelope-Based Video Scheduling and Multiplexing
In this section, we give an overview of our previously proposed framework for the distribution of
MPEG-coded video streams. Details can be found in [21, 22, 33]. In this framework, a video
distribution network consists of several fixed-capacity dedicated "bandwidth pipes" that extend from
the server to remote head-end (HE) switches over a public network (Figure 1). These bandwidth pipes
can be, for example, ATM virtual paths (VPs) onto which several video connections are multiplexed.
Clients request videos on demand by sending their requests to the server via one of the HE switches.
Video streams are transported at a constant frame rate, but with per-stream bandwidth that is
video streams
video streams Switch
Video Server
Clients
Clients
Head-End Switch
Public Network

Figure

1: Video distribution network with two HE switches.
significantly less than the source peak rate. Since the frame transmission rate is the same as the
playback rate, prefetching is not needed at the client set-top box. Bandwidth gain is achieved through
statistical multiplexing of MPEG streams that are described by deterministic, time-dependent traffic
envelopes. An envelope here constitutes a time-varying upper bound on the bit rate. It is intended
to capture the periodic structure of an MPEG stream (in terms of the repetition of the GOPs). The
simplest form of our traffic envelope is called the global envelope, and is described as follows: For
the ith MPEG stream, s i , the global envelope is a periodic function (in time) that is parameterized
by the 5-tuple
I (i)
, where I (i)
max is the largest frame of s i (typically, an
I frame), P (i)
max is the largest P or B frame of s i (typically, a P frame), and B (i)
max is the largest B
frame of s i . By construction, I (i)
. The remaining two parameters characterize the
GOP pattern of the ith stream: N (i) is the length of a GOP (I-to-I frame distance) and M (i) is the
P-to-P frame distance. An example of the global envelope is shown in Figure 2.
Based on the global-envelope model, MPEG streams can be appropriately scheduled for multi-
Time (in frame periods)
Bit Rate
global traffic envelope
window-based envelope

Figure

2: Example of global and window-based traffic envelopes (N
plexing at the server. Consider n MPEG video streams, s are destined to the same HE
switch. Let b i (t) be the traffic envelope of s i , whose starting time is given by t i . Let e
N be the least
common multiple of fN (1) ; N g. We define the phase of s i by u
N , with u 1= 0.
In the special case when N describes the frame lag of a GOP of s i relative to the
closest GOP of s 1 . The temporal relationships between the GOPs of the n streams are completely
specified by which is referred to as the arrangement. Let b tot (t) be the traffic
envelope resulting from the superposition of the n streams; b tot
is periodic with period e
N . The peak rate of b tot (t) is given by
b tot
By allocating nC(u; n) of bandwidth to the aggregate traffic, each stream is guaranteed a constant-
frame-rate delivery on an end-to-end basis. For most values of u, C(u; n) (which is referred to as the
per-stream allocated bandwidth (PSAB)) is smaller than the source peak rate. The allocated band-width
nC(u; n) is updated dynamically upon the addition of a new video stream or the termination
of an ongoing one. Stream scheduling is performed only for new video requests, and is done at the
expense of delaying the service of a new request by no more than e
frame periods.
An optimal scheduling policy is one that produces the best arrangement, u   , where
u2U
n) (2)
and U is the set of all possible arrangements of n streams. In [21] optimal and suboptimal scheduling
policies were proposed for homogeneous and heterogeneous multiplexed streams that are characterized
by global envelopes. These policies resulted in PSAB of about 40-60% of the source peak
rate (the actual value depends on the envelope). Bandwidth gain can be further improved using
window-based traffic envelopes [33]. In this case, a pre-recorded MPEG sequence is divided into
several segments that have the same number of frames. The time it takes to transmit one segment
is called a window. As in the global-envelope model, five parameters are used to characterize the
window-based envelope. However, in this case the values of the first three parameters (i.e., the
maximum frame sizes) are computed for each segment of the movie (see Figure 2). Several efficient
scheduling schemes were devised under window-based envelopes. Clearly, the smaller the window
size the smaller the amount of allocated bandwidth, but the higher the computational complexity
of updating the allocated bandwidth. For reasonable window sizes, the PSAB is about 15-30% of
the source peak rate (depending on the envelope parameters and the window size). This bandwidth
gain is comparable to the one achieved through video smoothing (e.g., [29, 26, 23, 13, 16]), with the
advantages of (1) not requiring any buffer in the set-top box, (2) not depending on network delay
variation, and (3) having a very small startup delay.
The framework in [21, 22] was originally designed for playback-only VOD, so it did not support
client interactivity. Interactive operations other than FS can be easily integrated into that framework,
and therefore will not be addressed further. In this paper, we focus on FS interactive operations and
their integration into our VOD framework.
3 Preprocessing of Video Movies
3.1 Scan Versions
To support FS operations, the server maintains multiple, differently encoded versions of each movie.
One version, which is referred to as the normal version, is used for normal-speed playback. The other
versions, which are referred to as the scan versions, are used for fast-scanning. Each scan version
is used to support both FFS and BFS at a given speedup. The server switches between the various
versions depending on the requested interactive operation (only one version is transmitted at a given
instant of time). For a given speedup factor s (s - 2), the corresponding scan version is obtained by
encoding a subset of the raw (i.e., uncompressed) frames of the original movie at a sampling rate of
1-to-s. We refer to this sampling rate as the skip factor. Scan versions are encoded using the same
GOP pattern of the normal version, and are transported at the normal frame rate. As a result, it is
easy to show that every raw frame that is encoded as an I frame in a scan version is also encoded as
an I frame in the normal version (i.e., I frames of the scan versions constitute a subset of I frames
of the normal version).
Accordingly, I max in the global envelope of a scan version is less than or equal to I max in the
global envelope of the normal version. This is not the case for P max and B max . Both P and B
frame types involve motion compensation (prediction or interpolation), which exploits the similarities
between consecutive frames to reduce the frame size. Frame skipping increases the differences between
successive images, resulting in larger P and B frames. The impact of frame skipping on the maximum
and average frame sizes is illustrated in Figure 3 for the Race clip. Before skipping, this clip consists of
1000 frames with frame dimensions of 320\Theta240 pixels. For each skip factor, encoding was performed
using an MPEG-2 software encoder with 3. The quantization values were set to 8,
10, and 25, for I, P, and B frames, respectively. Part (b) of the figure shows that the average size of
I frames is almost unaffected by frame skipping. In contrast, the average sizes of P and B frames
tend to increase with the skip factor.
I frames
frames
Skip Factor
Normalized
Frame
Size
Race Trace
(a) Maximum frame sizes.
frames
frames
Normalized
Frame
Size
Race Trace
(b) Average frame sizes.

Figure

3: Frame sizes of a scan version versus the skip factor (values are normalized with respect to
their counterparts in the normal version).
3.2 Controlling the Envelopes of the Scan Versions
As indicated in Figure 3(a), encoding a sample of the raw frames may result in higher values of
To generate scan versions with comparable envelopes to that of the normal version,
the encoding of P and B frames of a scan version must be rate controlled. A common approach to
control the size of an MPEG frame is to vary the quantization factor on a per-frame basis. This
results in variable video quality during FS operations (however, the quality is still constant during
normal playback).
Without loss of generality, we consider the case when the envelopes are global. Extension to
window-based envelopes is straightforward. To bound the sizes of P and B frames of a scan version,
the encoder uses two predefined upper thresholds T (u)
are for the normal version, and S (u)
P and S (u)
are nonnegative constants. A P
frame in a scan version is encoded such that its size is no greater than T (u)
or S (u)
B is positive, the envelope of a scan version is allowed to exceed the envelope of the normal
version by no more than a fixed amount. In the case of window-based envelopes, T (u)
from one window to another, depending on the variations in P
After a raw frame of a scan version has been encoded as a P or a B frame, the encoding algorithm
checks whether the size of the compressed frame is below the associated upper threshold. If it is not,
then the quantization factor for the corresponding frame type is increased by one and the raw frame
is re-encoded. This procedure is repeated until the size of the compressed frame is smaller than the
corresponding upper threshold.
Two different approaches can be used to initialize the quantization value when a new P or B
frame is to be encoded. In the first approach (or algorithm), when a frame is to be encoded for the
first time, the encoder starts with the last quantization value that was used in the encoding of the
previous frame of the same type. The main problem with this approach is that the quantization
value might be kept unnecessarily high following the encoding of a very large frame, resulting in an
unnecessarily low quality during FS. While it is important to produce scan versions with comparable
envelopes to that of the normal version, there is little incentive in reducing these envelopes below
the envelope of the normal version.
In the second approach, the encoding algorithm tries to track the nominal quantization value,
which was used in encoding the same type of frame in the normal version. Consider the encoding
of a P frame (similar discussion applies to B frames). In the first encoding attempt, the encoder
checks the final quantization value that was used to encode the previous P frame. If that value is
equal to the nominal quantization value for P frames, then it is taken as the initial quantization
value for the current frame. If on the other hand, the last quantization value of the previous P frame
is larger than the nominal value, then the quantization value for the current frame is initialized to
the last quantization value minus one. After the first encoding attempt, if the resulting frame size is
within the upper bound, the encoder proceeds to the next frame. Otherwise, the quantization value
is incremented and the same raw frame is re-encoded, as in the first approach. The advantage of
the second approach is that it tries to produce a FS effect with the same constant quality of normal
playback, but when this is not possible it minimizes the fluctuation in video quality during FS.

Figure

4 depicts the variations in the quantization values for P and B frames when S (u)
0:05 and In these experiments, the nominal quantization values for P and B frames are 10
and 25, respectively. Note that the quantization factors for type-P and type-B frames are plotted
versus the index of every frame in the scan version (including the indices of I frames).
In the second encoding approach, video quality during FS varies smoothly around the nominal
quality at the expense of an increase in the number of encoding attempts. Since encoding in VOD
is done off-line, the encoding time may be less of an issue than video quality.
st Algorithm
2nd Algorithm
Quantization
Factor
Race Trace
nominal value
(a) P frames.
1st Algorithm
2nd Algorithm
2005152535Quantization
Factor
Race Trace
nominal value
frames.

Figure

4: Variations in the quantization values during the encoding of a scan version
The two approaches can be contrasted with respect to video quality using the peak signal-to-noise
ratio (PSNR). We use the PSNR of the Y-component of a decoded frame. The PSNR is obtained
by comparing the original raw frame with its decoded version with encoding being done using one
of the two algorithms. Figure 5 depicts the resulting PSNR values for Race movie with
0:05. Both approaches achieve acceptable quality (PSNR is sufficiently large). The
average PSNR value for the 200 frames is 36.9 dB for the first algorithm and 37.5 dB for the second,
i.e., the average quality is slightly better under the second algorithm. The absolute values of the
PSNR do not convey the advantage of the second encoding approach. For this purpose, we compute
the PSNR values for the 200 frames when encoding is done without any constraints (i.e., no upper
bounds are imposed), and use these values as a reference. For each frame, we compute the difference
between its reference PSNR value and the PSNR value resulting from each of the two rate-control
encoding algorithms. These differences are plotted in Figure 6 for a segment of the scan version. In
this figure, a large value indicates a large deviation from the reference PSNR, and thus lower quality.
Clearly, the second algorithm achieves better quality than the first approach, but at the expense of
more encoding attempts.
3.3 Storage Overhead
Generating separate copies for FS operations comes at the expense of extra storage at the server. To
evaluate the storage overhead, we take into account the following considerations: (1) BFS and FFS
with the same speedup can be supported using one scan version, (2) I frames of the scan versions need
not be stored, since they are part of I frames of the normal version, and (3) the number of encoded
frames in a scan version is inversely proportional to the skip factor. Given these considerations, the
storage overhead of the scan versions can be computed as follows. Without loss of generality, we
st Algorithm
2nd Algorithm
90 100 110 120 130 140 150 160 170 180 190515253545Race Trace

Figure

5: PSNR for encoded frames in a scan
version.
1st Algorithm
2nd Algorithm
90 100 110 120 130 140 150 160 170 180 1900.51.52.53.54.5Race Trace

Figure

Difference in PSNR between constrained
and unconstrained encoding.
consider the case of global traffic envelopes. Let f be the number of frames in the normal version.
Of these frames, f=N are I frames, f(1=M \Gamma 1=N) are P frames, and f(1 \Gamma 1=M) are B frames. The
storage requirement of the normal version is given by
where I avg ; P avg and B avg are the average frame sizes of I, P, and B frames in the normal version.
Let P avg be the average sizes of P and B frames in a scan version with skip factor s.
Then, the storage requirement of this scan version is given by
W scan
For n scan versions with skip factors s the relative increase in the storage requirement is
given by
Numerical examples that show the relative increase in the storage requirement are given in

Figures

7 and 8. for the Race clip. Figure 7 depicts the relative storage overhead of a scan version
as a function of s under different upper thresholds 3). The upper threshold has a
negligible impact on the storage overhead. For s - 4, the storage overhead of a scan version is no
more than 25% of the storage requirement of the normal version. Figure 8 shows the increase in
storage as a function of the GOP length (N) with
The storage overhead
increases slowly with N .
Skip Factor
Storage
Increase

Figure

7: Relative increase in storage as a function
of s.
0%
5%
10%
15%
20%
GOP Length
Storage
Increase

Figure

8: Relative increase in storage as a function
of N .
Switching Between Normal and Scan Versions
In this section, we describe how switching between versions is used to support various FS-related
operations. The notation that we use to specify a frame consists of a letter for the frame type and
a number that indicates the logical time of that frame (i.e., the time relative to the events in the
movie). This convention applies to all versions. Thus, B16 in a scan version is a B frame that is
obtained by encoding the 16th raw frame of the original movie. This B frame is not necessarily the
16th frame in the temporal order of that scan version (for example, if is the 8th
frame in the temporal order of the scan version).
4.1 Operation During Normal Playback
Because of the interpolative nature of B compression, the decoding of a B frame depends on two
reference frames (I or P ), both of which must be transmitted and decoded before the B frame is
decoded. One of these reference frames comes after the B frame in the temporal order. To enable
continuous playback at the receiver, MPEG frames are transmitted over the network according to
their decoding order. Thus, the transmission (and decoding) order of an MPEG sequence is different
from its temporal (playback) order. An example of the temporal and transmission orders of a normal
version is shown in Figure 9. In order to decode frames B2 and B3, both I1 and P4 must be first
transmitted and decoded. The process of transmitting, decoding, and displaying frames proceeds as
follows. Starting at time time unit is taken as one frame period), the server transmits
frames according to their transmission order. Ignoring network delays for the time being, the decoder
receives and decodes frame I1 during the time interval [0; 1). It maintains an uncompressed copy of
this frame to be used in decoding subsequent frames. During the interval [1; 2), frame P4 is received,
decoded, and stored in the frame buffer (note that P4 is decoded with reference to the uncompressed
version of I1). Playback starts with I1, which is displayed in the interval [2; 3), two time units after
it was received. During the same interval, B2 is received and decoded. During the interval [3; 4), B2
is displayed, and B3 is received and decoded. During the interval [4; 5), B3 is displayed, and I7 is
received, decoded, and stored in one of the two frame buffers (at this point the decoder discards I1).
In the subsequent interval, P4 (which has already been received and decoded) is displayed, and B5
is received and decoded using the uncompressed P4 and I7 frames that are in the frame buffer. And
so on. In the above discussion, we have assumed that a frame is received and decoded in one time
unit.
(a) Temporal order
(b) Transmission order

Figure

9: Temporal and transmission orders of a normal version
The decoder maintains a two-frame buffer, which contains the two most recently decoded reference
frames. An incoming P frame is decoded with reference to the most recent of these two, while an
incoming B frame is decoded with reference to both of them.
4.2 Switching From Normal Playback to FFS
Interactive FS operations are implemented at the server by switching between the normal version and
one or more scan versions. Switching from one version to another is performed on-line, in response
to a client request. In this section, we describe how switching is used to implement FFS.
Similar to the situation during normal playback, the frames of the scan version have a different
transmission order than their temporal order (in the case of FFS, the temporal order of a scan version
is the same as its playback order). Figure 10 depicts the temporal and transmission orders of a scan
version with 2. Two successive I frames in a scan version differ in their logical times by sN
frame periods (the logical time is the time relative to the events in the movie).
(a) Temporal order
(b) Transmission order

Figure

10: Temporal and transmission orders of a scan version
To maintain the GOP periodicity, switching from a normal to a scan version must take place
at an I frame. Furthermore, to enable correct decoding of all P and B frames of both normal and
scan versions, this I frame must be common to both versions. When the FFS request arrives at the
server, the server continues to send frames from the normal version up to (and excluding) the first
P frame that follows a common I frame. From that point and on, the server switches to the scan
version. The example in Figure 11 illustrates the idea. In this example, we use the normal and scan
versions of Figures 9 and 10, respectively. A FFS request arrives at the server after P16 of the normal
version has just been transmitted. In this case, the server continues to send frames from the normal
version up to (and including) B24. This essentially corresponds to continuing to play back frames
from the normal version until the next common I frame (I25). After that, the server switches to the
scan version, starting with P31, B27, B29, etc. Frame P31 is decoded using I25, which is common
to both versions. This example gives the worst-case latency, in which the receiver continues normal
playback sN frame periods from the time the FFS request is issued. Assuming that each GOP of the
normal version corresponds to half of a second, the worst-case latency is s=2 seconds (the average
latency is s=4 seconds). In requesting FFS, the client is trying to advance fast in the movie. Thus,
extending normal playback by few seconds prior to initiating FFS is acceptable. Note that there is
no disruption in the playback during the transition from normal to FFS. The switching operation is
transparent to the decoder.
normal version a ' scan version a
Received
Displayed B9 P10 B11 B12 I13 B14
" (normal playback) 7\Gamma!
FFS request start FFS

Figure

11: Switching from normal playback to FFS.
4.3 Switching From FFS to Normal Playback
We present two different approaches for switching from FFS to normal playback. The first approach
is very similar to the one used to switch from normal playback to FFS. Upon receiving a request for
normal playback, the server continues to send frames from the scan version until the next common
I frame (it also sends the B frames of the scan version that precedes this I frame in the temporal
order, but comes after it in the transmission order). After that, the server switches to the normal
version. This approach is illustrated in the example in Figure 12
the movie is in a FFS mode when the client requests normal playback during the display of frame
B23. At that point, the server has just transmitted P31. Ideally, the receiver should proceed by
playing back frames with indices 24, 25, 26, etc. To decode B24 the decoder needs P22 of the normal
version. However, if the server transmits P22, this frame will eventually be played back, causing
undesirable artifacts. Neither can the server start from P28 of the normal version, since the decoder
will incorrectly decode this frame with reference to P31 of the scan version. To ensure that switching
to normal playback is done with all received frames being decoded properly, with no artifacts, and
without any modifications to the normal operation of the decoder, the server must continue to send
frames from the scan version until the next common I frame (I37). After that, it switches to the
normal version, starting with P40, which can be decoded properly using I37. This means that FFS
will be extended beyond the point at which normal playback was requested. In the worst case, normal
playback is resumed at a logical time that is s=2 seconds from the logical time of the normal-to-FFS
request (since N frames of the scan version correspond to seconds worth of video).
However, it takes a maximum of only 1/2 second of real time to reach the appropriate switching
point.
scan version a ' normal version a
Received & Decoded I25 B21 B23 P31 B27 B29 I37 B33 B35 P40 B38 B39 I43
Displayed B17 P19 B21 B23 I25 B27 B29 P31 B33 B35 I37 B38 B39
normal playback request start normal playback

Figure

12: First approach for switching from FFS to normal playback.
The above approach has the advantage of being transparent to the decoder (i.e., the decoder need
not know that a switch from a scan version to the normal version has occurred). However, it has
the disadvantage that normal playback resumes at a later point than requested, with a worst-case
difference of s=2 seconds of movie time. To reduce this extra FFS, we introduce a second switching
approach, in which normal playback resumes from the subsequent I frame of the normal version.
This I frame is not necessarily common to both scan and normal versions. We will describe this
approach with reference to the example in Figure 13 (N As shown in the
figure, the client requests resume-playback while B27 of the scan version is being displayed. Normal
playback is resumed starting from the subsequent I frame of the normal version whose logical time is
closest to the logical time of the resume-playback request. In our example, this frame is I31. During
the switching process, the client continues to display frames from the scan version (i.e., extended
FFS) until the frame with the closest logical time to I31. In our example, this frame is P31. Frame
P31 is never displayed, but is only used to decode B27 and B29 of the scan version. After receiving
and displaying I31 of the normal version, the movie pauses at that frame until P34 of the normal
version has been received and decoded (since two reference frames are needed to stream the playback
process). During the pause period, the decoder ignores any frames sent by the server (in Figure 13
such frames are represented by 'X' for `don't care'). Of course, a mechanism is needed to inform the
decoder when to start accepting and decoding incoming frames. Such a mechanism will be described
in a later section. Note that this switching approach is not transparent to the decoder.
It can be shown that the logical time of the last displayed frame from the scan version is no farther
than s frame periods from the logical time of the subsequent I frame of the normal version. Thus,
in the transition from the scan version to the normal version, the speedup of the motion picture is
somewhere between normal playback and FFS (in our example, B29 of the scan version was followed
by I31 of the normal version, and the transition appears as a continuation of FFS).
In the second FFS-to-normal switching approach, normal playback resumes at a logical time that
is no farther than 1=2 second (N frame periods) from the logical time of the FFS-to-normal request.
This is compared to s=2 seconds in the first approach. The maximum time that a client has to wait
for before normal playback is resumed is N=s frame periods of extended
FFS and M frame periods of pause. This amounts to 1=2s +M=2N seconds, which is less than one
second.
scan version a ' normal version a
Received & Decoded P31 B27 B29 I31 X X P34 B32 B33 I37 B35
Displayed B23 I25 B27 B29 I31 I31 I31 I31 B32 B33 P34
normal playback start normal playback
request

Figure

13: Second approach for switching from FFS to normal playback.
4.4 Switching From Normal Playback to BFS
Instead of generating a distinct scan version for BFS, we use one scan version for both FFS and BFS
that have the same speedup. In this case, the dependency structure of an MPEG sequence must be
taken into account when transmitting frames during BFS and when decoding and displaying these
frames at the client side. We first consider switching from normal playback to backward playback,
which is a special case of BFS with
4.4.1 Normal Playback to Backward Playback
To implement backward playback (BPB), the server uses a different transmission order than the one
used during (forward) normal playback. After receiving a BPB request, the server initiates the BPB
operation starting from the subsequent reference frame (I or P) of the current GOP. Before initiating
BPB, the decoder must receive and decode the reference frames of the current and previous GOPs.
Consider the situation in Figure 14. The temporal order of the underlying MPEG sequence is shown
in Part (a) of the figure. Suppose that a BPB is issued during the playback of B36. The subsequent
reference frame that follows B36 in the temporal order is I37. Thus, the client continues normal
playback until the display of I37. Meanwhile, the server continues sending the frames of the normal
version that are needed to maintain normal playback until (and including) I37. After that, the server
starts sending the reference frames of the current and previous GOPs. A maximum of 2N=M reference
frames need to be decoded and stored in the frame buffer before BPB is initiated. In our example,
the client had already decoded and stored I37 when the BPB was issued. Hence, before initiating
BPB the decoder must receive and decode I28, P31, and P34 of the current GOP as well as I19 and
P22 of the previous GOP. While these frames are being transmitted and decoded, the movie pauses
for a maximum duration of two GOPs (one second). To minimize the pause duration, the following
guidelines are followed whenever possible: (1) reference frames of the present GOP are sent before
reference frames of the previous GOP, and (2) reference frames of a given GOP are sent according
to their decoding order. However, ensuring the GOP periodicity of the transmitted sequence is more
important that satisfying these two guidelines. Thus, these guidelines can be violated if necessary.
For example, in Figure 14(b) frames I28, P31, and P34 must be sent in this order according to the
first guideline. But the first available slot to send an I frame while maintaining the GOP periodicity
is time slot # 42, whereas the server can send a P frame during slot # 39. Thus, the server sends
during slot # 39 and I28 during slot # 42, violating the first guideline.
In the process of building up the reference frames at the decoder, the server need not send any
frames in between (otherwise, these B frames are ignored at the decoder). The resulting "empty"
slots in the transmission sequence are indicated by 'X's (for `don't care') in Figure 14(b). Once
the required reference frames are received and decoded, BPB can be initiated. Note that some P
frames are decoded M periods after they are received, so they must be temporarily stored in their
compressed format. After all the reference frames of the previous GOP have been received and
frames can be received, decoded, and displayed in the backward direction.
Clearly, the management of the frame buffer at the decoder must be modified to support BPB.
Instead of storing two reference frames, the decoder must store a maximum of 2N=M uncompressed
frames. A mechanism is needed to signal to the decoder that the transmitted reference frames are
for BPB. Such a mechanism will be described in Section 5. Once the decoder receives an indication
that BPB has been requested, it modifies its management of the frame buffer to accommodate up to
uncompressed frames. Figure 15 depicts the change in the content of the frame buffer in our
example. Note that the BPB request was issued during the decoding of P40, which under normal
playback replaces P34. Thus, by the time the decoder starts modifying its buffer management, the
uncompressed P34 (or parts of it) has already been discarded, and P34 must be retransmitted.
4.4.2 Normal Playback to BFS
In addition to reversing the playback direction, a BFS request also involves switching from the normal
to the scan version. In this section, we present two different approaches to supporting BFS.
First Approach
In this approach, BFS is initiated at a common I frame. Following a BFS request, normal playback
continues until the display of a common I frame. Thus, the server continues sending frames from
(a) Temporal order of normal version
Received I37 B35 B36
Decoded I37 B35 B36 P40 - I28 -
Displayed B33 P34 B35 B36 I37 I37 I37 I37 I37 I37 I37 I37
Time 43 44
(normal
request
Received
Decoded P31 - P34 - I19 B36 B35 P22 B33 B32
Displayed I37 I37 I37 I37 I37 I37 I37 I37 B36 B35 P34 B33
Time
(pause) 7\Gamma!
start BPB
Received P13
Decoded P25
Displayed B32 P31
Time 57 58 59
(continue BPB)
(b) Received, decoded, and displayed frames.

Figure

14: Switching from normal playback to backward playback.
Time Uncompressed frames in buffer
36 P40, I37
37 I37 (P40 is discarded)
42 I28, I37
48 P34, P31, I28, I37
54 P22, I19, P34, P31, I28, I37
57 P25, P22, I19, P34, P31, I28

Figure

15: Content of the frame buffer during the transition from normal playback to BPB.
the normal version for a short period following the receipt of a BFS request. After that, the server
switches to the scan version. As in the case of normal-to-BPB, the server must first send all or
most of the reference frames of the current and previous GOPs of the scan version (for a maximum
of 2N=M reference frames). Consider the example in Figure 16, in which the scan version has the
following parameters: 2. A BFS request is issued during the playback
of frame B72 of the normal version. Normal playback continues until the display of I73; the first
common I frame. The server receives the BFS request during the transmission of P76. Thus, all
the frames that precede I73 in the playback order have already been sent. The server switches to
the scan version and starts sending the reference frames of the current and previous GOPs. In this
example, frames I37, I55, P61, and P67 must be received and decoded before BFS is initiated (in
general, BFS cannot be initiated before all frames of the current GOP and one or more frames of
the previous GOP are decoded). These frames are transmitted following the same guidelines that
are used to support BPB. Thus, the transmission order is P61, I55, P67, and I37, while the decoding
order is I55, P61, P67, and I37. As in the case of BPB, no B frames need to be transmitted during
the buildup of the reference frames. Also, some P frames are decoded few frame periods after they
are received, so they must be temporarily stored in their compressed format. During the buildup
of the reference frames, the movie pauses at frame 73. Once frame I37 is received and decoded,
the transmission, decoding, and reverse playback of the scan version can be streamed, and BFS is
initiated. Part (c) of Figure 16 depicts the change in the content of the frame buffer.
In the previous example, the BFS request was issued just before the display of a common I
frame, which is a rather best-case scenario. The worst-case scenario occurs when BFS is requested
just after the display of a common I frame. In this case, normal playback continues for an additional
sN frame periods (s=2 seconds) until the next common I frame is encountered. This extra normal
playback is followed by a pause period that lasts for no more that two GOPs (one second), during
which reference frames are being accumulated in the decoder.
Second Approach
An alternative approach is to initiate BFS from the "closest" reference frame (I or P) of the scan
version. When a BFS request is issued, the movie pauses immediately at the currently displayed
frame (which could be of any type). The client identifies the reference frame of the scan version
that has the closest logical time to (but no larger than) the logical time of the currently displayed
frame. BFS is initiated from this reference frame. When the server receives the BFS request, it starts
sending the reference frames of the last two GOPs up to (and including) the designated reference
frame. Thereafter, the process is similar to the one used in the first BFS approach.
As an example, consider the situation in Figure 17. Since the BFS request is issued during the
playback of B80, the movie pauses at that frame. The reference frame of the scan version that is
(a) Temporal order of the scan version
Received
Decoded
Displayed
Time
(normal
BFS request
Received
Decoded P61 - P67 - I37 B71 B69 P43 B65 B63 P49
Displayed I73 I73 I73 I73 I73 I73 I73 I73 B71 B69 P67 B65 B63
Time 81
(pause) 7\Gamma!
start BFS
Received
Decoded
Displayed P61 B59 B57 I55 B53 B51
Time 94 95 96 97
(continue BFS)
(b) Received, decoded, and played frames.
Time Uncompressed frames in buffer
71 I73, P70
72 P76, I73
73 I73 (P76 is discarded)
78 I55, I73
84 P67, P61, I55, I73
87 I37, P67, P61, I55, I73
90 P43, I37, P67, P61, I55 (I73 is discarded)
93 P49, P43, I37, P61, I55 (P67 is discarded)
(c) Content of the frame buffer at the decoder.

Figure

First approach for switching from normal playback to BFS.
closest (in logical time) to the current logical time is P79. Thus, BFS will be initiated from P79. But
before that, the decoder must receive P79, P61, I73, P67, P43, I55, and P49 (in this order); and must
decode I73, P79, I55, P61 (in this order). Once this is done, the process of transmitting, decoding,
and displaying frames for the purpose of BFS can be streamed, similar to the first approach. The
maximum duration of the pause period is given by periods (one second and M=2N
of a second), which is independent of s. This is slightly higher than the worst-case pause period in
the first approach, but there is no extra normal playback as in the first approach.
Received
Decoded B78 I82 B80 B81 - I73 -
Displayed B77 B78 P79 B80 B80 B80 B80 B80 B80 B80 B80 B80 B80
(normal
BFS request
Received
Decoded P79 - I55 - P61 B77 B75 P67
Displayed B80 B80 B80 B80 B80 B80 B80 B80 B80 B80 P79 B77 B75
(pause) 7\Gamma!
start BFS
Received
Decoded
Displayed I73 B71 B69 P67 B65 B63 P61 B59 B57
(continue BFS)

Figure

17: Second approach for switching from normal playback to BFS.
4.5 Switching From BFS to Normal Playback
The easiest way to resume normal playback following BFS is to initiate the normal playback from
an I frame that is common to both the normal and the scan versions (this is analogous to the
first approach for switching from normal playback to BFS). Thus, when the client requests normal
playback, the movie remains in the BFS mode until a common I frame is encountered. At worst,
normal playback is resumed at a logical point that is s=2 seconds (in movie time) from the logical
time at which the resume was requested, but it takes only a maximum of 1=2 second to reach this
common I frame (each GOP of the scan version corresponds to a sampled video segment of duration
seconds. However, it takes only 1=2 second to play back this GOP). Upon receiving
the resume-playback request, the server switches to the normal version, starting from the common I
frame. Since two reference frames are needed in the frame buffer to stream the decoding process, the
movie pauses at the common I frame for no more that M periods (M=2N of a second). This pause
is needed to decode the P frame of the normal version that follows the common I frame. After that,
normal playback can be resumed. The switching process is illustrated in the example in Figure 18.
Other forms of interactivity include switching between FFS and BFS without going through
Received I37 B65 B63 P31 B59 B57 P7 B53 B51 I19 B47 B45 X
Decoded I37 B65 B63 P43 B59 B57 P49 B53 B51 I19 B47 B45 -
Displayed B69 P67 B65 B63 P61 B59 B57 I55 B53 B51 P49 B47 B45
normal playback request
Received
Decoded
Displayed P43 B41 B39 I37 I37 I37 I37 B38 B39 P40
(continue BFS) (pause) 7\Gamma!
start normal playback

Figure

18: Switching from BFS to normal playback.
Requested Operation Switching Delay
(in seconds)
(1st
FFS-to-normal (1st approach) 1=2
FFS-to-normal (2nd approach) 1=2s +M=2N
BPB-to-normal 1=2 +M=2N
BFS-to-normal 1=2 +M=2N

Table

1: Worst-case switching delay associated with various interactive operations.
normal playback. Also, if the VOD system supports multiple FS speedups, switching can take place
between two scan versions that have different speedups. These and other scenarios can be dealt with
using similar approaches to the ones we described (with slight modifications to fit the specifics of
each scenario). Due to space limitations, we do not elaborate further on these scenarios.
We define the latency of an interactive operation as the difference between its time of request
at the client side and its initiation time on the client's display device. This latency measures the
actual waiting time of the client. It consists of: (1) roundtrip propagation time (RTT) between
the client and the server, (2) processing delay at the server, and (3) "switching delay", which is
the delay caused by switching from one version to another (it includes the time needed to reach an
appropriate switching point and the time needed to build up the frame buffer in BFS operations).
The second component of the latency is relatively small, and can be ignored. The RTT depends
on the underlying network topology. In [28] the authors report one-way propagation delays from
to 50 milliseconds for a wide-area ATM network, and less than 10 milliseconds for ATM LAN
connections. Table 1 summarizes the worst-case switching delay for various types of requests. This
delay is measured in real time (not the logical time of the movie).
For typical values of N , M , and s (say, the worst-case switching
delay associated with common interactive operations ranges from a fraction of a second to three
seconds. This delay can be further reduced by using a smaller GOP length (N) or by reducing s.
However, reducing the skip factor will increase the storage requirement of the scan version (since
more frames are generated), while reducing the GOP length will increase the storage needed for the
normal and the scan versions and will potentially reduce the efficiency of the underlying envelope-
based scheduling mechanism. Tuning the above parameters requires careful consideration of the
involved tradeoffs.
5 Signalling
Signalling between the client and the server must be extended to allow the decoder to distinguish
between various versions. For this purpose, we use an in-band signalling mechanism based on the
user-data field in the header of an MPEG frame. Each frame carries in its header the value of the
skip factor and the playback direction (forward or backward). This information can be conveyed
using one byte in the user-data field. The most significant bit of this byte encodes the playback
direction while the other seven bits encode the skip factor (in fact, four bits are enough to represent
skip factors from the remaining three bits can be used to convey other types of
information). For P and B frames of a given version, the skip factor is inserted in the frame header
during the encoding of that version. In contrast, for I frames the skip factor is inserted during
transmission since some of these frames are common between two or more versions. For all frames,
the playback direction is added on the fly during the transmission of the MPEG stream. This can be
done efficiently since user data in the frame header are byte aligned and are located at a fixed offset
from the beginning of the MPEG frame. The server can insert user-data bytes with minimal parsing
of the MPEG stream. Information about the GOP structure of a version is included in the sequence
header and in the header of the first GOP. This information can be used to allocate memory for the
frame buffer during the initial signalling phase.
6 Disk Scheduling
Compressed videos are typically stored on disk in units of retrieval blocks, where each block consists
of one or more consecutive GOPs. Our stream switching scheme requires storing multiple versions
of the same MPEG movie. A straightforward approach is to store each version separately as a
self-contained MPEG stream. The main disadvantage of this approach is that it wastes some disk
space by separately maintaining the I frames of each scan version (although these frames are already
included in the normal version). If the cost of disk space is not a major issue, then this storage
approach is preferred for its simplicity. Otherwise, the duplicate I frames can be eliminated, and
a method for "intermixing" the versions of the same movie is needed. This can be accomplished if
the structure of the retrieval block is extended so that it can accommodate all the scan versions of a
movie. Let s be the k skip factors supported by the system, with
Let s lcm be the least common multiple of these skip factors. Each block consists of s lcm GOPs from
the normal version plus s lcm =s i GOPs from the ith scan version, for all This way, each
block contains portions of the normal and scan versions that correspond to the same segment of the
movie. The resulting block consists of (s lcm
frames. Excessively large block
sizes can be avoided by appropriate choice of the skip factors so that their least common multiple
is small. Frames within a block are organized as follows. First, the I frames of the s lcm GOPs of
the normal version are put at the beginning of the block (no separate I frames are generated for the
scan versions). They are followed by P and B frames of the same version, then P and B frames of
the first scan version (preferably the one with the smaller skip factor), then P and B frames of the
next scan version, and so on until the frames of all scan versions are included. This structure allows
for efficient disk access since related data are stored consecutively on disk and no extra disk-head
movements are needed to access "out-of-stream" I frames.
In the above scheme, the frames in a block are not ordered according to their transmission
order. So they have to be rearranged before being sent over the network. Such a rearrangement can
be efficiently achieved by allowing the envelope-scheduling module (which is responsible for sending
frames to the network) to have random access to buffered frames. In this way, any transmission order
can be achieved without data movement in memory. In order to be able to manipulate individual
frames, knowledge of the location of each frame within the retrieval block is necessary. This is
accomplished by associating a small directory of indices with each retrieval block. The directory can
be computed when the movie is initially stored on disk and can be maintained in a main memory
database since its size will be small.
During playback of the normal version, only the first part of the retrieval block (which includes
I , P and B frames of the normal version) is retrieved from disk, with no waste of I/O bandwidth.
When a scan version is to be retrieved, two alternatives exist. The first alternative is to read the
whole block and discard frames that do not belong to the target scan version. The other alternative is
to read only the frames of the target scan version in two reads: one for the I frames at the beginning
of the block and one for the P and B frames of the target scan version. The directory associated
with the block is used to locate the appropriate frames inside the retrieval block. The first approach
is simpler but wastes I/O bandwidth during FS periods. The second alternative requires two reads
per block but eliminates the waste in I/O bandwidth, especially when there are several scan versions
per movie.
Another issue is the placement of blocks within the disk subsystem. In a multi-disk system,
blocks are typically striped among different disks in order to maximize the disk throughput and
balance its I/O load. Examples of striping schemes can be found in [32, 5, 10]. A conventional block
placement approach such as the ones in [19] can be easily adapted to our framework. In particular, if
the retrieval block is composed of frames from all versions of the movie, then the resulting composite
stream is striped similar to a typical MPEG stream. On the other hand, if different versions of
the movie are stored independently, then each version can be placed on disk independently using,
for example, one of the algorithms in [19]. Finally, block retrieval during playback is performed
using algorithms that attempt to minimize disk head movements. We handle block retrieval with
the SCAN algorithm [14], which sorts the blocks to be retrieved by cylinder location. Blocks that
are at the outermost cylinders are serviced first as the head moves towards the innermost cylinders.
7 Implementation Issues
The feasibility of our stream scheduling and multiplexing approach was demonstrated in [20] using
a specific hardware setup. We now briefly discuss general implementation issues related to this
approach. Since our approach relies on time-varying envelopes, timing considerations are crucial to
its operation. For this purpose, two important modules must be implemented at the video server:
stream manager and envelope scheduler. Both modules coordinate their operation with the disk
scheduler that is used for prefetching video blocks.
7.1 Stream Manager
The main purpose of this module is to handle client requests for new movies as well as requests for
interactive operations. In its simplest form, the stream manager consists of a user-level process. This
process establishes a bandwidth pipe to the destination switch, and then waits indefinitely for client
requests. (e.g., 'listens' at a given port). When a request for a new video arrives at the server, the
stream manager inquires the envelope scheduling module about the admissibility of the new stream.
It then provides information to the disk I/O subsystem on how to retrieve the movie data and place
them in the buffers of the envelope scheduling module. In the case of a FS request, the stream
manager is responsible for adding the stream switching information that are needed by the client
decoder (e.g., speedup and direction of playback).
7.2 Envelope Scheduler
This module is responsible for envelope-based stream scheduling, multiplexing, and admission control.
Upon receiving a request for a new stream, the envelope scheduler computes the best phase for
scheduling this stream. For this purpose, it maintains a a "bandwidth table" of dimension n \Theta e
where n is the number of ongoing streams. Each row describes the traffic envelope of one active
stream, taking its relative phase into account. An additional row is needed to give the aggregate
bandwidth in each of the e
N successive time slots. From the bandwidth table and the envelope of the
prospective stream, the envelope scheduler can easily determine the best phase for the new stream
and the associated bandwidth. Similarly, it can check for the admissibility of the new stream. If the
stream if found admissible, the envelope scheduler updates the bandwidth table by incorporating
the envelope of the new stream. An analogous procedure is used when an ongoing stream is to be
terminated.
Once a request is accepted, data can be retrieved from the disk subsystem in units of blocks. The
block size depends on the underlying striping mechanism, but typically consists of several GOPs.
Ideally, we would like to retrieve data on a frame-by-frame basis, but this level of fine granularity is
not feasible in current disk systems. The envelope scheduler maintains a per-stream buffer space that
is used to temporarily store the retrieved data. Statistical multiplexing is implemented in software
using a high-priority process that executes periodically every 1=f seconds, where f is the frame rate
formatted video). At the start of each period, this process reads one frame
from every per-stream buffer, and sends these frames over the network. Clearly, the timeliness of
this process impacts the effectiveness of our multiplexing approach. This timeliness can be easily
ensured in a real-time operating system (OS). For other OS's that do not support near-deterministic
execution of processing tasks, various approaches can be used to increase the priority of the process
performing the multiplexing task. For example, in some flavors of Unix it is possible to assign
a negative priority to this process, giving it higher priority in execution over all other user-level
processes. Another possibility is to implement this process as part of the OS kernel, which gives
the process a high priority and ensures its timeliness. Such an approach was used in the design of
the Stony Brook server [31], which was based on the FreeBSD 2.4 Unix OS. Yet, another approach
to performing the multiplexing process is to implement this process in the network device driver
[20]. In [20] the multiplexing process was implemented in the device driver of the ATM network
adaptor card (NIC). Communications between the stream manager (a user-level process) and the
device driver were provided by an extended set of system calls that are derived from the UNIX
system call.
8 Comparison with Other Schemes
In this section, we compare our FS approach to the following approaches: (1) multicast-based stream
switching [2], (2) contingency-channel-based [12], (3) the Stony Brook server [31], (4) prefetching
[26], (5) GOP-skipping [8], (6) partial-GOP-skipping [27], and (7) skipping B/P frames [7]. A brief
discussion of these approaches was given in Section 1. The comparison is performed with respect
to the factors in the first column of Table 2. Because of the difficulty to quantify certain factors
and the lack of detailed information about certain FS approaches, we contend with a qualitative
comparison in which a scheme is given one of three grades for each examined factor: (G)ood, (F)air,
or (P)oor. The comparison is only meant to convey the tradeoffs provided by different schemes. We
now comment on the examined factors.
Video data are retrieved from disk in units of blocks, which are temporarily stored in the server's
main memory before being sent over the network. Therefore, the memory requirement at the server
depends on the block size. This, in turn, depends on the underlying disk scheduling approach. In our
scheme, there are different ways for storing scan versions on disk. When scan versions are intermixed
with the normal version so that each block is composed of GOPs from both, the block size will be
relatively large, resulting in large server-memory requirement. Other schemes will generally have
smaller block sizes than ours.
Client resources refer to the memory and CPU requirements that are needed to process and decode
a received frame. To provide backward FS operations, our scheme requires buffering a maximum of
reference frames. This is larger than post-encoding frame skipping schemes (which require
the buffering of two reference frames only), but lower than the prefetching approach in which a large
amount of video data must be prefetched into the client's set-top box. Also, the client processing
requirement in our scheme is lower than that of the contingency-channel scheme, in which the client
has to decode and display data at multiple times the normal playback rate.
Bit-rate control refers to the flexibility in trading off the visual quality during FS for a lower
bit rate. With regard to this factor, partial-dropping schemes perform poorly since only a limited
reduction in the bit-rate is achievable during FS. In contrast, stream-switching schemes (ours and
Stony Brook's) achieve good degree of bandwidth control since they both use pre-encoded scan
versions. Between the two, our scheme provides tighter control on the resulting bit rate. The bit
rate injected into the network can also be controlled, to some extent, in the prefetching approach.
Visual quality includes the quality of the displayed video during FS operations, the continuity
of this video (i.e., amount of disruption due to video gaps), and any artifacts caused by the delay
in the initiation of an interactive operation. These factors are hard to measure quantitatively. In
general, we expect stream-switching schemes to give better performance than single-stream schemes.
Compared to the Stony Brook's approach [31], our scheme is expected to result in better visual
quality during backward FS periods (the latter scheme requires modifying the motion vectors of
the backward scan versions). Other frame-skipping schemes result in progressively worse quality,
as larger parts of the MPEG stream are skipped. Prefetching and contingency-channel approaches
result in very good visual quality at the expense of extra client memory and network bandwidth.
Performance guarantees refer to mathematically proven bounds on the response time of an interactive
operation. The response time is the duration from the instant the client issues a FS request
until FS is initiated at the client display. It includes both transport and processing delays. Only our
scheme is capable of providing such bounds.
Functionality refers to the flexibility in supporting FS requests (e.g., number of speedups, duration
of a FS period, allowable sequence of interactive operations, etc. Our scheme and the Stony Brook
scheme achieve high functionality since they do not impose any limitation on the time and durations
of the FS operations. In the prefetching approach, the duration of a FS operation is limited by the
size of the memory of the set-top box (which typically holds a small portion of the video movie).
Post-encoding frame-skipping schemes provide a limited number of FS speedups. In the contingency-
channel approach, the interactive operation may be denied if many users are in the interactive mode
(i.e., interactivity is supported only on a statistical basis). In the multicast approach, short FS
periods are supported using the locally stored data. Extended FS requires switching to a different
multicast group (with a different logical playback time). In general, interactivity is more difficult to
support in the multicast approach.
In terms of the required network bandwidth for FS operations, our approach uses almost the same
amount of bandwidth that is needed for normal playback. The per-stream bandwidth during FS
operations is also small in the multicast and the contingency-channel approaches (its value depends
on the number of active sources). In the prefetching approach, if FS is supported locally, then no
extra network bandwidth is needed for FS operations. Similarly, no extra bandwidth is required in
the GOP-dropping approach. Partial dropping schemes are less efficient in terms of FS bandwidth
requirement (e.g., dropping B frames causes the average bit rate of an MPEG sequence to increase
drastically).
The storage requirement is relatively high for schemes that use multiple copies per movie (ours
and Stony Brook's). If no duplication of I frames is done, then the storage overhead in our scheme
is less than that of Stony Brook's. All single-copy schemes have lower storage requirements.
In terms of the complexity of disk scheduling, schemes that involve skipping parts of a GOP
require a relatively complicated disk scheduling subsystem that carefully places data on disk, so
that the disk load is balanced during both normal and scan periods. Stream switching schemes also
require slightly more sophisticated disk scheduling to support switching between different copies. In
the contingency-channel scheme, the need to retrieve frames at multiple times the normal playback
rate further complicates the disk scheduling subsystem. In general, disk scheduling for interactive
VOD is inherently sophisticated because of the unpredicted pattern of client's interactivity.
Factor Scheme
Ours
Server Memory F G G G G G G G
Client Resources F G P G P G G G
Bit-Rate
Visual Quality G P G G G P P P
Performance Guarantees G
Network Bandwidth G G G F G G F P
Storage Requirement P G G P G G G G
Scheduling Complexity F G P F G G G G

Table

2: Comparison of different approaches to support FS operations.
9 Summary and Future Work
In this paper, we presented an approach for supporting interactive fast-scanning (FS) operations in
a VOD system. This approach is integrated into a previously proposed framework for distributing
archived, MPEG-coded video streams over a wide-area network. Scanning operations are supported
by generating multiple, differently encoded versions of each movie. In addition to a normal version
that is used for normal playback, several scan versions are maintained at the server. Each scan
version is obtained by encoding a sample of the raw frames, and is used to support both forward
and backward fast scanning at a given speedup. The server responds to a FS-related request by
switching from the currently transmitted version to another version. By proper encoding of the
scan versions, interactive scan operations can be supported with little or no extra bandwidth and
with the same decoding requirement of normal playback. This gain comes at the expense of small
storage overhead at the server and some variability in the quality of the motion picture during
the fast-scanning periods. Our scheme does not impose any restriction on the number, spacing, or
sequencing of interactive operations.
VOD clients should be given the flexibility to choose from a set of available VOD services that
offer different levels of interactivity. Billing would then be done based on the quality and flexibility
associated with the selected service. Our future work includes developing a multi-level QoS framework
for interactive VOD. Each level corresponds to a certain degree of interactivity, which could include
some limitations on the interactive functions (e.g., number of supported speedups, visual quality
during scanning, maximum duration of a scanning operation, etc.



--R

On optimal batching policies for video-on-demand servers
The use of multicast delivery to provide a scalable and interactive video-on-demand service
Metascheduling for continuous media.
Audiovisual multimedia services: Video on demand specification 1.1

An open-systems approach to video on demand with VCR like functions
A scalable video-on-demand service for the provision of VCR-like functions
Support for fully interactive playout in a disk-array-based video server
Storage and retrieval methods to support fully interactive playout in a disk-array based video server

Scheduling policies for an on-demand video server with batching
Providing VCR capabilities in large-scale video servers
A comparison of bandwidth smoothing techniques for the transmission of prerecorded compressed video.
Multimedia storage servers: A tutorial.
Adaptive piggybacking: A novel technique for data sharing in video-on-demand storage servers
VBR video over ATM: Reducing network resource requirements through endsystem traffic shaping.
ISO/MPEG II.
Baseband and passband transport systems for interactive video services.
Evaluation of video layout strategies for a high-performance storage server
Bandwidth allocation and admission control schemes for the distribution of MPEG streams in VOD systems.
Exploiting the temporal structure of MPEG video for the reduction of bandwidth requirements.
Impact of video scheduling on bandwidth allocation for multiplexed MPEG streams.
An algorithm for lossless smoothing for MPEG video.
Performance model of interactive video-on-demand systems
The split and merge (SAM) protocol for interactive video-on-demand systems


Bandwidth renegotiation for VBR video over ATM networks.
Supporting stored video: Reducing rate variability and end-to-end resource requirements through optimal smoothing
Efficient support for scan operations in video servers.
Adventures in building the Stony Brook video server.

Efficient transport of stored video using stream scheduling and window-based traffic envelopes
Design and analysis of a look-ahead scheduling scheme to support pause-resume for video-on-demand application
--TR
Metascheduling for continuous media
An algorithm for lossless smoothing of MPEG video
Staggered striping in multimedia information systems
Scheduling policies for an on-demand video server with batching
Providing VCR capabilities in large-scale video servers
Support for fully interactive playout in disk-array-based video server
Evaluating video layout strategies for a high-performance storage server
Efficient support for scan operations in video servers
Design and analysis of a look-ahead scheduling scheme to support pause-resume for video-on-demand applications
Storage and retrieval methods to support fully interactive playout in a disk-array-based video server
Adaptive piggybacking
Supporting stored video
Adventures in building the Stony Brook video server
Impact of video scheduling on band width allocation for multiplexed MPEG streams
Multimedia Storage Servers
A Low-Cost Storage Server for Movie on Demand Databases
VBR Video over ATM
A Comparison of Bandwidth Smoothing Techniques for the Transmission of Prerecorded Compressed Video
Exploiting the Temporal Structure of MPEG Video for the Reduction of Bandwidth Requirements
The Split and Merge (SAM) Protocol for Interactive Video-on-Demand Systems
Pipelined Disk Arrays for Digital Movie Retrieval
A Scalable Video-on-Demand Service for the Provision of VCR-Like Functions
Optimizing the Placement of Multimedia Objects on Disk Array

--CTR
Kostas E. Psannis , Yutaka Ishibashi, MPEG-4 interactive video streaming over wireless networks, Proceedings of the 9th WSEAS International Conference on Computers, p.1-7, July 14-16, 2005, Athens, Greece
video scheduling;MPEG;scanning operations;interactive video-on-demand