Interactive video streaming with proxy servers.
We study caching strategies for proxies that cache VBR-encoded continuous media objects for highly interactive streaming applications. First, we develop a model for streaming VBR-encoded continuous media objects. This model forms the basis for a stream admission control criterion and our study of caching strategies. We find that unlike conventional web caches, proxy caches for continuous media objects need to replicate or stripe objects to achieve high hit rates. We develop novel caching strategies that either implicitly or explicitly track the request pattern and cache (and replicate) objects accordingly. Our numerical results indicate that our caching strategies achieve significantly higher hit rates than caching without object replication.
Introduction
The dramatic growth of the World Wide Web has spurred
the deployment of proxy caches. These store frequently
requested objects close to the clients in the hope of satisfying
future client requests without contacting the origin
server. Highly localized request patterns, which exhibit
hot{spots, i.e., frequent requests for a small number of popular
objects, have made caching highly successful in reducing
server load, network congestion, and client perceived
latency. While most of the caching research to date has focused
on caching of textual and image objects, web{based
streaming of continuous media, such as video and audio,
becomes increasingly popular. In fact, it is expected that
by 2003, continuous media will account for more than 50
% of the data available on origin servers [13]. This trend is
Corresponding Author: Martin Reisslein, Dept. of Electrical
Eng., Arizona State University, P.O. Box 877206, Tempe
AZ 85287{7206, phone: (480)965{8593, fax: (480)965{8325,
reisslein@asu.edu, http://www.eas.asu.edu/~mre.
re
ected in a recent study [1], which found that the number
of continuous media objects stored on web servers has
tripled in the rst 9 months of 1998.
Caching and streaming of continuous media objects with
proxy servers poses many new challenges [29]. These are
due to the real{time constraints imposed by continuous media
tra-c and the high degree of interactivity expected by
users. In this paper we focus on caching strategies for proxies
that cache VBR{encoded continuous media for highly
interactive streaming applications in disk arrays. We consider
an architecture where the proxy servers cache frequently
requested continuous media objects in their local
storage, which is typically a disk array. The clients direct
their streaming requests to their assigned proxy server. If
the proxy can satisfy the streaming request | a cache hit
| the object is streamed from the proxy to the client. If
the proxy can not satisfy the request | a cache miss | the
object is obtained from the appropriate origin server and
the proxy decides according to a caching strategy whether
or not to cache the object.
The contribution of this paper is twofold. First, we develop
a stream model for streaming VBR{encoded continuous
media objects from the proxy's disk array over an access
network to the clients. Based on the stream model we
design a scheme for admission control and resource reservation
that provides stringent statistical Quality of Service
guarantees.
Our second contribution is to study caching strategies
for continuous media objects. Our study shows that unlike
conventional web caches, proxy caches for continuous
media should replicate or stripe objects to accommodate
the typically highly localized request patterns and to ensure
good stream quality. We develop natural extensions
of conventional caching strategies which implicitly track
the client request pattern by combining object replication
with a conventional replacement policy, such as LRU or
LFU. We then develop and evaluate a novel caching strategy
which explicitly tracks the client request pattern and
caches objects accordingly. Our numerical results indicate
that the hit rate achieved by our caching strategy with
explicit tracking is almost 20 % higher than the hit rate
of caching with implicit tracking. Caching with implicit
tracking in turn achieves typically 10 % higher hit rates
than conventional caching without object replication.
1.1 Related Work
There are only few studies of caching and streaming of
continuous media objects with proxy servers which are
complementary to the issues studied in this paper. Rejaie
et al. propose a proxy caching mechanism [26] in conjunction
with a congestion control mechanism [24, 25] for
layered{encoded video. With layered encoding the compressed
video stream is split into a base layer, which contains
low quality encoding information, and enhancement
layers, which improve the stream quality. The basic idea
of their caching mechanism is to cache layers according to
the objects' popularities: the more popular an object, the
more layers are cached. When streaming an object to a
client, the layers that are not cached at the proxy are obtained
from the origin server. A related idea is explored by
Wang et al. in their study on video staging [39]. With video
staging the part of the VBR video stream, that exceeds a
certain cut{o rate (i.e., the bursts of the VBR stream) is
cached at the proxy while the lower (now smoother) part
of the video stream is stored at the origin server. Our work
is complementary to these studies on caching of video lay-
ers. Our focus is on (1) developing a stream model and
admission control conditions that ensure statistical QoS
for continuous media streaming, and (2) object replication
and striping to accommodate the typically highly localized
client request pattern while providing good stream quality.
Sen et al. [33] propose to cache a prex (i.e., the initial
frames) of video streams at the proxy and to employ
work{ahead smoothing while streaming the object from the
proxy to the client. The cached prex hides the potentially
large initial start{up delay of the work{ahead transmission
schedule from the client. A major drawback of this approach
is that it is not suited for interactive video stream-
ing. The client experiences a potentially large delay after
invoking an interaction (such as a temporal jump) since the
work{ahead smoothing schedule has to build up a buered
reserve at the client before playback can resume.
Tewari et al. [38] propose a Resource Based Caching
(RBC) scheme for Constant Bit Rate (CBR) encoded video
objects. They model the cache as a two resource (storage
space and bandwidth) constrained knapsack and study replacement
policies that take the objects' sizes as well as
CBR bandwidth into account. Our work diers from RBC
in that we consider VBR encoded video objects. Also, object
replication and striping as well as interactive streaming
are not addressed by Tewari et al.
There is a large body of literature on striping of video
objects in the context of video servers. Most of these studies
assume that the videos are CBR encoded; see for instance
[12, 8, 19]. Striping for VBR encoded video objects
is studied by Shenoy and Vin [35]. They develop an analytical
model for the most heavily loaded disk and study the
optimal striping placement. Sahu et al. [30] study round
based retrieval strategies for VBR video from disk. These
studies on striping and retrieval of VBR video assume that
the user request pattern is uniform and do not consider
interactive delays.
Birk [2] proposed an approach where the video blocks are
placed randomly on the disk array to overcome the hot{
spot problem. In his scheme interactive requests, which result
from client interactions, are given priority over sequential
retrievals to ensure short interactive delays. This approach
appears promising in the context of proxy streaming
of interactive VBR video, although there are some issues
that require further research. Most importantly, a stream
admission control rule that ensures statistical QoS when
retrieving randomly placed blocks of VBR video from the
disk array requires more research. Also, the performance
of the scheme when the proportion of interactive requests
is high needs to be examined.
In this section we describe the end{to{end architecture
for the delivery of continuous media objects using proxy
servers. The architecture is illustrated in Figure 1. The
Wide Area Network
Origin Server Origin Server
Local Access Network
Proxy Server
Client
Client
Client

Figure

1: Architecture for continuous media streaming
with proxy server.
continuous media objects are stored on the origin servers.
The continuous media objects are prerecorded audio and
video objects, such as CD{quality music clips, short video
clips (e.g., trailers or music videos) or full{length movies
or on{line lectures. The proxy server is located close to the
clients. It is connected to the origin servers via a wide area
network (e.g., the Internet). The proxy server is connected
to the clients via a local access network. The local access
network could be a LAN running over Ethernet, or a residential
access network using xDSL or HFC technologies.
In the following we brie
y outline the delivery procedure
for continuous media objects. The client directs its request
for a particular continuous media object to its assigned
proxy server (for instance by using the Real Time Streaming
Protocol (RTSP) [32]). If the continuous media object
is not cached in the proxy, that is, in the case of a cache
miss, the proxy forwards the request to the appropriate origin
server. The origin server streams the continuous media
object to the proxy server. The proxy relays the stream
to the requesting client and at the same time caches the
continuous media stream in its local storage. If the local
storage (typically disk array) at the proxy is full the proxy
decides according to a replacement policy (see Section 5)
which continuous media object to remove from the cache
to make room for the new object. If the replacement algorithm
fails to free up enough disk space for the the new
objects (this is the case when not enough objects can be removed
without interrupting ongoing streams; see Section 5)
the object is streamed from the origin server directly to the
client. In the case of a cache miss the proxy server does
not reduce the bandwidth usage in the wide area network,
neither does it improve the stream quality and the level of
interactivity oered to the client.
In the case of a cache hit, that is, when the continuous
media object requested by the client is cached in the proxy's
disk array, the object is streamed from the proxy over the
local access network to the client.
Before the streaming commences the proxy conducts in
both cases admission control tests to verify whether the
available disk bandwidth and the bandwidth in the local
access network are su-cient to support the new stream.
Only if the admission tests are successful is the requested
object streamed from the origin server (in the case of a
cache miss) or from the proxy (in the case of a cache hit).
3 Model for Continuous Media
Streaming from Proxy
In this section we model the streaming of continuous media
from the proxy. Our analysis applies to any type of
continuous media tra-c, however, to x ideas we focus on
streaming of video objects. We naturally assume that the
video objects are Variable Bit Rate (VBR) encoded. For
VBR encoding the quantization scale is kept constant to
maintain high video quality even for high action scenes.
For the same quality level the le size and average bit rate
of a Constant Bit Rate (CBR) encoded movie or sports
clip are typically two times or more than the le size and
average bit rate of the VBR encoding [4, 37]. Our rst
contribution is to develop a unied scheme for admission
control and resource reservation in the proxy server as well
as the local access network. Toward this end we rst develop
a disk model and derive the eective disk bandwidth
for the retrieval of continuous media tra-c with tight interactive
delay constraints. We then develop a stream model
for the VBR{encoded continuous media tra-c and design a
scheme for admission control and resource reservation that
provides stringent statistical QoS.
3.1 Disk Model
We assume that each disk in the proxy's disk array consists
of single platter side and a single arm. We assume that the
proxy server retrieves data for the ongoing video streams
in constant{time rounds; we denote the round length by
T . We also assume that each disk in the disk array uses
the SCAN scheduling algorithm [20]. Specically, in each
round, each disk arm sweeps across its entire platter exactly
once with no back tracking. With the SCAN scheduling
algorithm, the overhead incurred within a round for a given
disk is
where I is the number of streams that the disk is servicing.
The constant l seek is the maximum seek time of the disk
(i.e., the time to move the arm from the center to the edge
of the platter, which is equal to the time to move the arm
from the edge to the center of the platter). The constant
l rot is the per{stream latency, which includes the maximum
rotation time of the disk and the track{to{track seek time.

Table

summarizes our disk notation and the nominal values
for the disk parameters. The nominal parameters reect
the current performance of high{speed disks [36].

Table

1: Nominal values of disk parameters
Parameters Notation Nominal value
disk size X 13 Gbytes
disk transfer rate r 8.5 Mbytes/sec
maximum seek time l seek
rotational latency l rot 5 msec
The initial start{up delay as well as the responsiveness to
an interactive request (pause/resume or a temporal jump)
is typically modeled to be twice the round length, 2T , when
the SCAN algorithm is used. This delay model is based
on the worst{case assumption that the request of the user
arrives just after the start of a round, say round k, and
arrives too late to be scheduled by the SCAN algorithm for
round k. The request has to wait for the start of the next
round. The request is included in the disk read schedule
of round and the requested video data is read into
the disk buer during round k + 1. The disk buer of
becomes the network buer of round k
and the transmission of the requested video data out of
the network buer starts at the beginning of round k 2.
Thus, the disk{subsystem introduces a maximum delay of
two rounds, i.e., 2T . We shall assume that the maximum
disk{subsystem delay is constrained to 0.5 sec. Therefore,
we use a round length of sec. Note that the
total interactive delay also includes transmission delays as
well as client de{smoothing and decoding delays. These
additional delays add another 0.25 sec to 0.5 sec to the
delay, giving a total delay on the
order of .75 sec to 1.0 sec. Thus, with a round length of
sec the system is able to give the user a pleasurable
interactive experience with less than 1 second delay for all
interactions.
For the development of the disk model we assume for now
that the video objects are placed in the proxy's disk array
using the localized placement strategy. With the localized
placement strategy each video le is placed contiguously
on a single disk. We shall later study a number of more
complex striping placement strategies, whereby each video
le is striped across a subset of the disks in the proxy's disk
array.
Now consider one of the disks in the proxy's disk array
and suppose that this disk is servicing I streams. Let
the number of bits retrieved for the I
streams in one round of length T . The disk transfers this
video data at the disk transfer rate r. Thus the total disk
transfer time within a round is retr(I ; T )=r. The total disk
overhead within a round is l seek . Thus the amount
of time the disk requires to service the I ongoing streams
in a round is retr(I ; T )=r . For lossless service
the time required to service the I streams in a round must
be no greater than the round length itself:
r
Rearranging the terms in the above inequality, we obtain
the maximum streaming rate for lossless service:
r
which we refer to as disk bandwidth. With the disk parameters
from Table 1 the disk bandwidth is (63:1 1:36  I)
Mbps. The disk bandwidth is obviously upper bounded
by the disk transfer rate. Note that the disk bandwidth
increases for increasing round length T . We therefore use
a round length of sec, the largest round length
that guarantees a maximum interactive delay of 1 second.
Note furthermore that the disk bandwidth decreases as the
number of ongoing streams I increases. This is because the
disk wastes a larger fraction of the round with seeks and
rotations when the number of ongoing streams increases.
3.2 Stream Model
We now develop a model for the VBR video streams that
are retrieved from the proxy's disk array and sent over the
local access network to the clients. We assume in the basic
stream model that the video objects are retrieved from a
single disk, that is, we assume localized placement in the
proxy's disk array. We shall consider streaming from a disk
array with striping placement later.
In our stream model we assume random stream phases,
which accurately model interactive streaming. We base the
stream model on the distribution of the frame sizes, as proposed
in [21]. We chose this approach because it provides
simple and accurate admission control decisions through
the Large Deviation Approximation [27]. The many models
that are based on Markov modulated processes (e.g.,
[18]) model tra-c quite accurately. However, for admission
control they are either more complex (requiring the
calculation of many state transition probabilities) or employ
the asymptotic theory of eective bandwidth which is
less accurate for small buers and bursty video tra-c [15].
Consider a single disk in the proxy's disk array and suppose
that this disk is streaming I video objects. For simplicity
we assume that each video object has N frames and
a frame rate of F frames per second. Let fn (i) denote the
number of bits in the nth encoded frame of video object
I . We assume that all video objects are cached
in the proxy; the frame size trace ffn (i); 1  n  Ng for
object i is therefore a sequence of known integers. As
pointed out above the video frames are retrieved from disk
in rounds of length T . For each ongoing video stream let K
denote the number of frames retrieved in one round; clearly
our numerical work we use a round length
of sec and a frame rate of
thus our numerical examples.) Following the terminology
of the le server literature [34] we refer to the K
frames retrieved in one round as block. Let xm (i) denote
the size of the block (in bits) retrieved for video stream i
in round m. Assuming that the frames of the video object
are retrieved strictly sequentially, that is, the rst K
frames are retrieved in round 1, the next K frames are retrieved
in round 2, and so on; in other words by excluding
client interactions, we have
n=(m 1)K+1
We refer to the sequence fxm (i); 1  m  N=Kg as block
size trace for stream i. Following [21] we model the random
start times of the video streams and the client interactions
by assigning to video object i the random phase  i .
(These client interactions such as pause/resume and for-
ward/backward temporal jumps can be communicated to
the proxy using the Real Time Streaming Protocol (RTSP)
[32]; we assume in our model that the temporal jumps have
the granularity of blocks, i.e., K frames.) It is natural to
assume that the random phases  I , are independent
and uniformly distributed over [0; N 1]. In
our model the amount of data retrieved from disk for video
stream i in round m is
where the index m wrapped around if it exceeds
the number of blocks N=K of the video object. The total
amount of data retrieved in round m for the I ongoing
video streams is
I
I
We now brie
y summarize the main implications of our
stream model:
1. For each xed round index m, Xm are
independent random variables.
2. The probability mass function of Xm (i) can be obtained
directly from the block size trace of the cached
video object:
Note that the distribution of Xm (i) does not depend
on the round index m. To simplify notation we write
henceforth X(i) for Xm (i) and X for Xm .
We now proceed to develop stream admission rules that
ensure a high user perceived quality of the streamed continuous
media while e-ciently utilizing the bandwidth resources
in the proxy's disk array and the local access net-
work. Toward this end we dene statistical QoS require-
ments. Specically, we dene the loss probability as the
long run average fraction of information (bits) lost due to
the limited bandwidth (in disk array and local access net-
work) and admit a new stream only if the loss is less than
some miniscule , such as Formally, the loss
probability due to the limited disk bandwidth is given by
where the expectation is over all possible phase proles.
Note that up to this point we have considered a single
disk in the proxy's disk array. To formally dene the loss
probability due to the limited bandwidth in the local access
network we consider the aggregate streaming rate from
the proxy's disk array (resulting from cache hits) as well
as the streaming from the origin servers (resulting from
cache misses). Let D denote the number of disks in the
proxy's disk array and let X d be the random variable denoting
the amount of data retrieved in one round from
disk d; D. The aggregate amount of data retrieved
from the proxy's D disks in one round is
Furthermore, let X o be the random variable denoting the
amount of data fed into the local access network in one
round from the origin servers. The total amount of data
fed into the local access network in one round is
The network loss probability is
net
where C net denotes the bandwidth available for streaming
continuous media objects into the local access network.
This bandwidth could, for instance, be the bandwidth of
the link connecting the proxy to an xDSL central o-ce, or
the bandwidth of the cable trunk that the proxy feeds into.
The overall streaming loss probability is bounded by the
sum of the disk and network loss probabilities. Our statistical
QoS requirement is that the streaming loss probability
be less than some miniscule :
loss
loss
Before granting a new streaming request we verify whether
continues to hold when including the new stream in (2)
(for the appropriate disk; recall we are assuming localized
placement) and (4).
Evaluating the probabilities in (6) involves the convolution
of independent random variables, which often leads to
numerical problems. We therefore apply the Large Deviation
approximation, which is known to be accurate and
computationally e-cient [27]. Let X (s) denote the logarithmic
moment generating function of X , the amount of
data retrieved from a given disk in one round,
Clearly,
I
by the independence of the X(i)'s. The individual
X(i) (s)'s are easily obtained from the respective round
size traces. The Large Deviation approximation for the
disk loss probability is [27]:
loss  1
Assuming that the streams retrieved from the D disks
in the proxy's disk array are mutually independent it is
straightforward to write out the corresponding Large Deviation
approximation for P net
loss
3.3 Striping Placement
In this section we study streaming from a proxy that
uses striping placement of video objects in its disk ar-
ray. Recall that D denotes the number of disks in the
proxy's disk array. We shall at rst focus on full striping,
whereby each video object is striped over all D disks in
the proxy. There are essentially two dierent striping tech-
niques: Fine Grained Striping (FGS) and Coarse Grained
Striping (CGS) [7, 17]. With Fine Grained Striping each
block (consisting of K frames) is segmented into D equal{
sized parts, called stripes, and each of the disks stores one
of the block's stripes. When retrieving a block from the
disk array, the server reads all D stripes in parallel. With
Coarse Grained Striping (also referred to as Data Interleaving
in [11]) each block is stored on a separate disk. The
blocks are typically assigned to the disks in a round robin
manner, When the proxy retrieves a block from its disk
array it reads the entire block from one disk. Therefore,
CGS has less overhead than FGS (since the proxy has to
access D disks to retrieve one block with FGS). The draw-back
of CGS, however, is its large interactive delay, which
is due to the large scheduling delay for disk accesses in
disk arrays with CGS [7, 17, 23]. The large scheduling delay
with CGS severely limits the number of streams that a
disk array with CGS can support when a tight interactive
delay constraint is imposed. In fact, it is shown in [23] that
given a tight interactive delay constraint of 1 second CGS
typically supports fewer streams than FGS. We are interested
in continuous media streaming with a high degree of
interactivity and focus therefore on FGS in this paper.
We now proceed to develop a model for streaming from a
disk array with FGS placement. For that purpose we adapt
the disk model (Section 3.1) and stream model (Section 3.2)
for localized placement. First, we consider the disk model.
Suppose that the proxy's disk array consists of D disks.
Suppose that the proxy is servicing J streams. Consider
one of the D disks. The disk will transfer J stripes in one
round. With J disk accesses the disk overhead incurred in
one round is
With a derivation that parallels the development of the disk
model for localized placement in Section 3.1 we obtain for
the disk bandwidth with FGS:
We now adapt the stream model of Section 3.2 to FGS.
Consider again one of the D disks. Let X FGS (j) be the
random variable denoting the amount of data (i.e., the size
of the stripe in bits) retrieved for stream
in a given round. Recall that the stripes are obtained by
dividing each block of a video object into D equal{sized
segments. With our stream model the probability mass
function of X FGS (j) can thus be directly obtained from
the block size trace of the cached video object:
The total amount of data retrieved from the disk in a given
round is
and the aggregate amount of data retrieved from the entire
disk array is Y . It is now straightforward
to compute the loss probabilities
loss and P net
loss using the
Large Deviation approximation.
We nally consider group striping. With group striping
the video objects are striped over W  D disks. We refer
to W as the striping width. Localized placement
and full striping are special cases of group strip-
ing. With group striping the proxy's disk array is typically
segmented into striping groups, which consist of W
disks each. Each cached video object is striped within a
striping group. With FGS each block of a video object is
segmented into W equal{sized stripes and each disk in the
striping group stores one of the block's stripes. The disk
model and stream model for streaming from a proxy with
group striping are straightforward extensions of the models
for full striping.
4 Replication and Striping of
Video Objects
In this section we study the impact of the placement of
video objects in the proxy's disk array on the proxy's per-
formance. We show that replication and striping of popular
objects in the proxy signicantly improve the hit rate and
throughput of the proxy as well as the user{perceived media
quality.
Throughout our performance study we assume that the
requests for continuous media objects follow the Zipf distribution
[40]. Specically, if there are M objects, with
object 1 being the most popular and object M being the
least popular, then the probability that the mth most popular
object is requested is
e
The Zipf distribution, which is characterized by the parameter
0, corresponds to a highly localized request
pattern. It has been observed that the requests for movies
in video rental stores and Video on Demand systems follow
a Zipf distribution with  around one [5]. Furthermore,
studies of web caches have shown that requests for images
and HTML documents are well described by a Zipf distribution
with a  of roughly one [3]. We expect therefore
that requests for on{line continuous media objects will also
follow a Zipf distribution.
For the numerical investigation in this paper we use
traces of MPEG encoded video objects. We obtained 7
MPEG{1 traces, which give the number of bits in each encoded
video frame, from the public domain [10, 16, 28].
The 7 video traces were used to create 10 pseudo traces
each 40,000 frames long. The statistics of the resulting
traces are summarized in Table 2. The bean, bond, lambs,

Table

2: Trace statistics
Frames
Trace Peak [Mbit/s] Peak/Mean Std. Dev.
bean 24.9 13.0 2.25
bond 19.3 10.1 2.03
lambs 35.2 18.3 2.94
oz 16.1 8.4 2.39
soccer 13.2 6.9 1.84
star wars 1 20.9 10.9 2.35
star wars 2 25.3 13.2 2.25
star wars 3 23.0 12.0 2.22
star wars 4 16.2 8.4 2.05
terminator 14.0 7.3 1.79
soccer, and terminator traces were created by multiplying
the frame sizes of the video traces from [28] by a constant
to bring their average bit rates to 2 Mbps. The oz trace
was created by taking the rst 40,000 frames of the MPEG
encoding from [16] and multiplying the frame sizes by a
constant to raise the average bit rate to 2 Mbps. Finally,
the four star wars traces were obtained by dividing the
MPEG encoding from [10] into four segments of 40,000
frames each and then raising the average bit rate of the
segments to 2 Mbps. Although the ten pseudo traces are
not traces of actual videos objects, we believe that they reect
the characteristics of MPEG{2 encoded video objects
(highly bursty, long{range scene dependence, average rate
about 2 Mbps). In summary, we have 10 VBR encoded
video objects with frames and a frame rate of
In our performance evaluation we focus on the impact of
the object placement and caching strategies in the proxy's
disk array on the proxy performance. Specically, we investigate
the object placement and caching strategies that utilize
the storage capacity and disk bandwidth of the proxy's
disk array most e-ciently. To highlight the impact of
the object placement and caching strategies we do not include
the streaming over the local access network in our
study, that is, we focus on the admission control condition
loss  . We refer the interested reader to [22, 31, 14, 6]
for studies of continuous media streaming over local access
networks.
To motivate the replication and striping of video objects
in the proxy's disk array, we rst consider a very
simple caching scenario. Suppose that the 10 video objects
from Table 2 are cached in the proxy's disk array.
Furthermore, suppose, that each video object is placed on
its own disk, that is, a localized placement strategy with
one video object per disk is employed. We use the disk
model and streaming model of Section 3 to evaluate this
simple caching scenario. We impose the statistical QoS
requirement that the long run average fraction of video information
(bits) lost due to the limited disk bandwidth be
loss
. For each video object
we use the large deviation approximation (7) to calculate
the maximum number of simultaneous streams that can
be supported by a single disk. The results are reported in

Table

3. The table also gives the maximum number of si-
Table

3: Number of streams that can be supported by a
single disk.
Trace Stat. Mux. Peak Allocation
bean
bond
lambs
soccer 15 4
star wars 1 14 2
star wars 2 14 2
star wars 3 14 2
star wars 4 14 3
multaneous streams that can be supported when peak rate
allocation is used. The video objects have an average rate
of 2 Mbps, thus the stability limit is 19 streams. We observe
from the table that the statistical admission control
criterion allows for signicantly more streams than peak
rate allocation. This substantial multiplexing gain comes
at the expense of small loss probabilities of the order of
6 . These miniscule losses, however, can be eectively
hidden by error concealment techniques and will therefore
not be noticed by the viewers. We also observe from Table
3 that the number of simultaneous streams supported
by a disk depends on the burstiness of the stored video ob-
ject. The disk with the lambs video object, which has the
largest peak{to{mean ratio, supports the smallest number
of simultaneous streams. On the other hand, the disks storing
the soccer and terminator video objects, which have the
smallest peak{to{mean ratio, support the most streams.
Next, we study the total number of streams that the
proxy can typically support, when the requests for the 10
video objects are distributed according to a Zipf distribution
with localized placement with
one video object per disk, that is, there is one disk with
bean, one disk with bond, and so on.) For this illustrative
example we assume that the popularity of the video
objects in Table 2 decreases in alphabetical order, that is,
bean is the most popular object (requested with probability
terminator is the least popular object
(requested with the probability
the typical number of streams, that the proxy can
simultaneously support with the following procedure. For
a given target number of streams S we generate S requests
from the Zipf distribution. We then determine the number
of requests that can be supported by the 10 disks using the
results from Table 3. We repeat the experiment 1000 times,
creating 1000  S requests. If 95 % of these requests can be
supported, then we increment S and repeat the entire pro-
cedure. The procedure continues until the 95 % criterion
is violated. We nd with this procedure that the proxy
can typically support 39 simultaneous streams. This, how-
ever, is only a small fraction of the disk array's capacity of
138 simultaneous streams (found by adding up the "Stat.
Mux" column of Table 3).
The reason for this is twofold. First, due to the limited
disk bandwidth the proxy cannot satisfy many of the
requests for the most popular objects. Secondly, much of
the disk bandwidth of the disks housing the less popular
objects is underutilized. This phenomenon is commonly
referred to as hot{spot problem. The hot{spot problem
severely aects the proxy's performance. The proxy either
has to reject many requests for the most popular objects
(and the clients have to obtain the objects directly
from the origin server) or it has to compromise the stream
quality by admitting more streams than the QoS criterion
loss allows. Both of these options, however, are
highly undesirable, as they increase the load on the wide
area network and reduce the media quality and level of interactivity
oered to the clients. We are thus motivated
to study strategies that overcome the hot{spot problem by
utilizing the proxy's storage capacity and disk bandwidth
more e-ciently. Specically, we study two strategies:
Object replication: The proxy stores more than one
copy of the popular video objects. The goal is to overcome
the hot{spot problem by roughly matching the
replication distribution (i.e., the distribution of the
number of copies of the objects) to the request distribution

Striping placement: The video objects are striped over
a subset of the disks in the proxy's disk array. This
allows the proxy to use the aggregate disk bandwidth
of the entire subset to stream the video objects. If the
video objects are striped over the entire disk array (full
striping) then the hot{spot problem vanishes and all
request distributions can be equally accommodated.
Recall that streaming from a proxy with striping placement
has been discussed in Section 3.3.
We now proceed to discuss object replication in detail.
To simplify the discussion we initially assume localized
placement. (We shall later study object replication in conjunction
with striping). To make the idea of object replication
a little more precise, let D denote the number of disks
in the proxy's disk array. Let M denote the number of distinct
objects in the proxy's cache. Let Cm
denote the number of copies of object m in the cache. For
simplicity, we initially assume that each disk stores exactly
one video object, thus
Now suppose that
the request pattern for the M object has a known distribution
(perhaps a Zipf distribution with known parameter ).
To make the replication distribution approximately equal
to the request distribution we replicate the objects according
to the following replication algorithm:
1.
2. If
3. Calculate
4. If C > D, decrement Cm for the least popular object
with Cm > 1, then for the next least popular object
with Cm > 1, and so on, until
5. If C < D , increment Cm for the most popular object,
then for the next most popular object, and so on,
Algorithm 1: Non-uniform replication algorithm.
This concludes our discussion of object replication for localized
placement. The concept extends to group striping
with striping width W > 1 in a straightforward manner.
With group striping the video objects are replicated on
distinct striping groups.
We have conducted a numerical study of object replication
and striping placement. In the numerical study we
consider a proxy with a disk array consisting of
disks. We use the objects from Table 2. In
the numerical study the requests for the video objects follow
a Zipf distribution with We use the replication
algorithm (see Algorithm 1) to match the number of copies
of the video objects to the request distribution. We then
use the 95 % criterion to determine the number of simultaneous
streams that the proxy can typically support. The
results are reported in Table 4 for dierent striping widths
W .

Table

4: Number of simultaneous streams that the proxy
can typically support for dierent replication strategies and
striping widths.
replication strategy
W uniform request request
The table also gives the number of simultaneous streams
that can typically be supported when the video objects are
uniformly replicated, that is, there are
of each video object in the disk array.
Two points are especially noteworthy. First, we observe
that replicating objects according to the clients' request
pattern signicantly increases the number of streams that
the proxy can typically support. For localized placement
streaming capacity of the proxy is increased
roughly threefold by taking the request pattern into ac-
count. The second noteworthy observation is that for uniform
replication the streaming capacity increases as the
striping width increases from one to two. This is because
striping over two disks alleviates the hot{spot problem and
thus allows the proxy to better accommodate the clients'
requests. As the striping width is increased further, how-
ever, the increased seek and rotational overhead of striping
becomes the dominant eect, reducing the streaming capacity
of the proxy. For the proxy with object replication
according to the request pattern localized placement (W
=1) gives the largest streaming capacity. This is because
localized placement minimizes the disk overhead while object
replication according to the request pattern overcomes
the hot{spot problem.

Table

4 also gives the number of simultaneous streams
that the proxy can typically support when the object replication
takes the video objects' popularity as well as band-width
demand into account. This approach is motivated by
the results from Table 3, which indicate that disks housing
relatively bursty video objects can support relatively fewer
simultaneous streams. To accommodate a given request
pattern the proxy should therefore house more copies of
objects that consume relatively more disk bandwidth. To
make this idea a little more precise let b
denote the maximum number of simultaneous streams of
object m that can be supported by a single disk. (For the
video objects used in the numerical study the b m 's are given
in

Table

3.) To take an object's bandwidth demand into
account we set
l c
in Step 1 of Algorithm 1. The factor 1
l is larger
(smaller) than one for video objects that require relatively
more (less) bandwidth. We see from Table 4 that taking
the objects' bandwidth demand into consideration increases
the proxy performance slightly for localized placement
1). For striping placement this replication
strategy does not improve the proxy performance.
We next study the robustness of the replication and
striping strategies of Table 4 with respect to changes in
the request pattern. For this purpose we vary the parameter
of the Zipf distribution from which the requests
are generated. Throughout this experiment the video objects
are replicated according to a Zipf distribution with
xed parameter (that is, throughout we use the object
replication used in the previous experiment). In other
words, the request distribution varies while the replication
distribution is held xed. Figure 2 shows the typical number
of simultaneous streams that the proxy can support
as a function of the Zipf parameter of the request distri-
bution. The gure gives plots for uniform replication and
replication according to Zipf distribution with
localized placement and striping over two disks. We see
Uniform (W=1)
Uniform (W=2)
Zipf, zeta=1 (W=1)
Zipf, zeta=1 (W=2)
Zipf parameter of request distribution
Number
of
streams

Figure

2: Robustness of replication strategies.
from the gure that uniform object replication gives good
performance only when the client request pattern is fairly
uniform, that is, when the Zipf coe-cient of the request
pattern is small. For the skewed request distributions that
are typical for client request patterns, uniform replication
even with striping gives poor proxy performance. Striping
over two disks with object replication according to the
Zipf distribution with which can be thought of
as an estimate of the client request pattern | is very robust
to changes in the client request pattern. This strategy
can support close to 1050 streams over a wide range of the
Zipf coe-cient of the actual request distribution. Striping
placement with object replication according to an estimate
of the client request pattern thus performs well even when
this estimate diers signicantly from the actual request
pattern. However, with a good estimate of the request pat-
localized placement object replication
according the estimate outperforms striping placement. In
the studied example, where the estimate of the request pattern
is the Zipf distribution with localized placement
with object replication according to this estimate outperforms
striping placement when the Zipf parameter of the
actual request pattern is between 0.6 and 1.4.
The localized placement strategy has the added advantage
that it is very simple and works well for heterogeneous
disk arrays consisting of disks with dierent performance
characteristics. Furthermore, localized placement avoids
the availability problem of striping placement | if one disk
fails then all video les that are striped over this disk become
unavailable to the clients. (With localized placement
a given disk stores parts of fewer video objects therefore
disk failure has less impact of availability.) The availability
problem of striping can be mitigated (at the expense
of added complexity) through mirroring of video blocks or
storing of parity information of the video blocks; see for instance
[9] and references therein. Because of its simplicity
and potential for improved performance we focus on localized
placement in the next section on caching
strategies, however, the studied caching strategies apply
equally well to striping placement.
5 Caching Strategies
In the previous section, which served to motivate object
replication and striping in the proxy, we assumed that (i)
the requests for video objects follow a known distribution,
and (ii) all available objects are cached in the proxy. In
this section we consider a more realistic scenario, where
(i) the client request pattern is unknown, and (ii) only a
subset of the available objects can be cached in the proxy.
We propose and evaluate caching and replacement policies
that either implicitly or explicitly track the client request
pattern. The caching policy determines which object (and
how many copies thereof) to cache while the replacement
policy determines which objects to evict from the cache to
space for new objects.
5.1 Implicit Tracking
With implicit tracking the caching policy is invoked whenever
the proxy can not satisfy a client's streaming request.
This is the case when either (1) the requested object is
not cached, or (2) the requested object is cached but the
additional stream can not be supported by the cached
copy without violating the QoS requirement P disk
loss  .
The basic caching policy is to always try to cache the requested
object in case (1). In case (2) we distinguish two
policies: caching with object replication and caching without
object replication. Caching with object replication attempts
to cache an additional copy of the requested object
(which is generated internally from the already cached
copy). Caching without object replication, on the other
hand, leaves the cache contents unchanged and the requested
object is streamed from the origin server directly
to the client.
If there is not enough free disk space to store the new
object (or additional copy when caching with replication
is employed) we invoke a replacement policy. We emphasize
at this juncture that our focus is on the impact of
the caching policy on the proxy performance. The studied
caching policies (i.e., caching with object replication and
caching without object replication) may be combined with
any replacement policy. For illustration we consider the
simple and well{known Least Recently Used (LRU) and
Least Frequently Used (LFU) replacement policies. (We
note that a wide variety of replacement policies has been
proposed, however, LRU continues to be the very popular
policy due to its simplicity.) With LRU replacement we
rst check whether we can remove one copy of the object
that was requested least recently without interrupting on-going
streams. We verify whether the ongoing streams (if
any) of the least recently requested object can be supported
by the remaining copies (if any). If so, we remove one copy
of that object. Otherwise, we move on to the next to least
recently requested object and start over. This replacement
algorithm terminates when we have freed up enough space
to cache the new object or we have considered all cached
objects. In the latter case the attempt to cache the new object
fails and the object is streamed from the origin server
directly to the client.
With LFU replacement a request counter is maintained
for every object in the cache. When the replacement policy
is invoked we consider rst the object with the smallest
request counter value, then the object with the next to
smallest counter value, and so on.
We have conducted a simulation study of these caching
strategies. For the simulation study we generate 1000 video
objects from the 10 pseudo traces from Table 2 in the following
manner. For each of the 1000 video objects we randomly
select one of the 10 pseudo traces and a random
average rate between 1.5 and 2.5 Mbps. For each video
object we furthermore draw a random starting phase into
the selected pseudo trace and a random lifetime from an
exponential distribution with mean L video frames. In the
simulation client requests arrive according to a Poisson pro-
cess. For each client request one of the 1000 video objects
is drawn according to the Zipf distribution with parameter
. (The request arrival rate is set to 0:95D   b m=L, where D
is the number of disks in the proxy and  b m is the average
number of streams that a single disk can support subject
to P disk
loss simplicity we assume that each disk
stores at most one video object.)

Figure

3 shows the hit rate as a function of the number
of disks in the proxy for caching without object replication
and caching with object replication both with LRU
replacement and LFU replacement (ignore the \Explicit
tracking" curves for now). The hit rate is dened as the
ratio of the number of requests served out of the cache
(without contacting the origin server) to the total number
of client requests. (The results for the byte hit rate are sim-
ilar.) The Zipf parameter of the client request distribution
is set to experiment. The average
length of the video objects is set to
(corresponding to 3.5 minutes) or
responding to 14 minutes). We observe from the plots that
caching with object replication outperforms caching without
replication by a signicant margin for
0.75 the margin is less pronounced. Interestingly, we see
from

Figure

3 that the replacement policy (LRU or LFU)
has no impact on the proxy performance.
In

Figure

4 we plot the hit rate as a function of the
average length of the video objects (which we assume is
identical to the stream lifetimes, i.e., clients receive the entire
object). We consider proxies with disks and
with disks and Zipf request patterns with
and 1.0 in this experiment. The gure reveals that for
short{lived streams (< 2000 video frames, corresponding to
roughly 1.3 minutes) LFU replacement outperforms LRU
replacement. We also see that the caching policy (caching
with or without object replication) has no impact on the
proxy performance. As the streams become longer lived,
however, the replacement policy looses its impact on the
proxy performance and the caching policy becomes dominant
(especially for the more localized access pattern,
1.0, and the large proxy, 100). The reason for
this is that, roughly speaking, it becomes harder to nd an
object copy that can be removed without interrupting on-going
streams when the streams become longer lived. As a
result both replacement policies tend to pick the same object
for removal. The main conclusion from this experiment
is that object replication is not needed for caching of text
and image objects (which can be thought of as having a
lifetime of zero). However, for caching of continuous media
objects, replication is crucial for good proxy performance,
especially when a large proxy serves a client community
with a highly localized access pattern.
We next investigate how well the caching policies adapt
to dierent client request patterns. In Figure 5 we plot the
hit rate as a function of the Zipf parameter of the request
distribution. In this experiment we consider proxies with
disks and disks and the average object
length is set to frames.
The plots clearly show that caching with object replication
outperforms caching without object replication for Zipf request
parameters larger than 0.65.
Note that the four discussed and evaluated caching
strategies (caching with and without object replication,
both with LRU and LFU replacement) implicitly track the
client request pattern. Popular objects | once cached |
tend to stay in the cache since it is very likely that their
removal would interrupt ongoing streams. In addition,
caching with object replication is able to adapt to highly
localized request patterns as it tends to cache more copies
of objects that are relatively more popular. A shortcoming
of the implicit tracking schemes is that they do not directly
take the objects' popularities into consideration. We observed
in our simulations that quite frequently, moderately
popular objects ll up the cache and prevent very popular
objects from being cached. We are therefore motivated to
explicitly take the objects' popularities into consideration.
5.2 Explicit Tracking
Our explicit tracking approach uses an exponential
weighted moving average to estimate the client request pat-
tern. Based on the estimated request pattern we determine
which objects (and how many copies thereof) to cache in
the proxy.
The estimation procedure works as follows. The proxy
maintains estimates of the request rate (requests per
time slot of length , we set our numerical
work) for all objects m; requested by its
client community. The estimates are updated at the
end of every time slot. Let req m denote the number of
requests for object m in the just expired time slot. The
estimates
r m are updated according to
where m is an object specic dampening factor. We set
m such that (1 m is the \aging
time" (in multiples of the slot length) of object m. We
propose to set  m to a small value for objects that \age"
relatively quickly, such as news clips. On the other hand,
should be set to a large value for objects that \age"
slowly, such as on{line lectures, operating instructions or
video clips showcasing products in on{line shopping sys-
tems. In our numerical work we set
objects.
Based on the estimated request rates ^
we calculate the popularity estimates ^
r l
Number of disks
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
Number of disks
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
a)
Number of disks
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
Number of disks
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
c)

Figure

3: Impact of proxy server resources.
We use the popularity estimates ^
q m to decide which objects
(and how many copies thereof) to cache. Our caching policy
strives to match the distribution of the number of copies
of the cached objects to the estimated popularities. For-
mally,
denote the number of copies
of object m required to match the estimated popularities
denote the number
of copies of object m that are currently in the cache.
For reasons that will become clear shortly, we distinguish
between the number of copies Cm in the cache and the number
of copies ^
Cm suggested by the popularity estimates.
The
Cm 's are matched to the ^
's with the following replication
algorithm:
2.
3. Calculate ^
CM .
4. If ^
Cm for the most popular object,
then for the next most popular object, and so on,
Algorithm 2: Replication algorithm.
The storage overhead of this popularity estimation procedure
is O(M ). This is because the estimate , the
counter req m , the popularity estimate ^ am , and the object
replication have to be maintained for every object
requested by the proxy's client com-
7Average Object Length
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
Average Object Length
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
a)
Average Object Length
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
Average Object Length
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
c)

Figure

4: Impact of average object length.
munity. The time complexity of the replication algorithm
is approximately O(M ). To see this, note that M iterations
are required to compute the popularity estimates ^ am and
matching replication ^
Cm . At most D iterations of Step 4
are required until ^
typically
D M . For simplicity we assume in the replication algorithm
that each disk stores exactly one video object. Note
that this replication algorithm diers from the replication
algorithm of Section 4 in that it caches only objects with
1=D. Based on the ^
Cm 's obtained with this replication
algorithm we propose a caching policy for explicit
tracking.
Similar to the implicit strategies discussed in the previous
section, the caching policy for explicit tracking is invoked
whenever the proxy can not satisfy a client's streaming
request. This is the case when either (1) the requested
object j  is not cached (i.e., C or (2) the requested
object j  is cached but the additional stream can not be
supported by the cached copies C j   1 without violating
the QoS requirement P disk
loss  . Our caching policy
with explicit tracking works as follows. First, we execute
the replication algorithm to determine the current popularity
estimates
q m and the matching object replication
we do not attempt to
cache object j  and it is streamed from the origin server
directly to the client. Otherwise, i.e., if ^
to store a copy of object j  in the disk array. In case
(1) this is the rst copy of object j  , which is obtained via
the wide area network from the appropriate origin server.
In case (2) this is an additional copy of object j  , which
is generated internally from the other already cached copy.
If there is enough empty disk space in the proxy we place
the new/additional copy of object j  there, otherwise we
invoke the replacement policy.
Roughly speaking, the replacement policy tries to remove
one copy of an object that has more copies in the
Zipf parameter of request distribution
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
Zipf parameter of request distribution
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
a)
Zipf parameter of request distribution
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
Zipf parameter of request distribution
Hit
Rate
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU
c)

Figure

5: Impact of object request distribution.
cache than are required to match its popularity. Formally,
g. If R is
non{empty we pick some j 2 R and check whether we can
remove one copy of object j without interrupting ongoing
streams. This amounts to verifying whether the ongoing
object{j streams (if any) can be supported by the remaining
copies. If so, we remove one copy of object j
and the replacement algorithm terminates if enough disk
space has been freed up. Otherwise, we remove object j
from consideration by setting R Rfjg and start over.
The replacement algorithm terminates when we have freed
up enough space or end up with an empty R. In the latter
case the attempt to cache object j  fails and object j  is
streamed from the origin server directly to the client.
The results of our simulation study of the explicit tracking
scheme are given in Figures 3, 4 and 5. The plots
show that the explicit tracking scheme consistently out-performs
the implicit tracking schemes with LRU or LFU
replacement. We observe from Figure 4 that the gap in
performance widens as the average object length increases;
explicit tracking achieves roughly higher hit rates
than the implicit tracking schemes when the average object
length exceeds 2000 video frames. Also, we observe
from

Figure

5 that explicit tracking outperforms the other
schemes for all requests patterns. In summary, we nd
that explicit tracking is a very attractive caching strategy
for continuous media objects.
Finally, we investigate the impact of the proposed
caching strategies on the utilization of the disk array. We
note, however, that the disk array utilization is only an auxiliary
performance metric of a caching strategy; the hit rate
is the decisive performance metric for a caching strategy.
In our utilization analysis we focus on the utilization of the
disk array bandwidth We dene the cache utilization as the
long run ratio of the sum of the average rates of the streams
supported by the proxy to the proxy's total disk bandwidth
Zipf parameter of request distribution
Cache
utilisation
Explicit Tracking
Obj. Rep., LRU
Obj. Rep., LFU

Figure

Cache utilization for varying Zipf parameter
(obtained by summing the disk bandwidths given by Eqn.
(1)).

Figure

6 gives the cache utilization as a function of
the Zipf parameter of the request pattern. We consider a
proxy with disks and movies with an average length
of frames in this experiment. The plots indicate
that caching with object replication achieves higher
cache utilizations than caching without object replication;
explicit tracking gives even higher utilizations. The cache
utilization results strengthen our conclusion of the importance
of object replication and explicit popularity tracking.
6 Conclusion
We have studied caching strategies for continuous media
objects in this paper. The basis for our study is our model
for VBR video streaming that provides statistical QoS. We
nd that for caching of continuous media objects, conventional
caching without object replication achieves only
small hit rates. We have proposed novel caching strategies
that either implicitly or explicitly track the client request
pattern. Our numerical evaluation indicates that
these novel caching strategies achieve signicantly higher
hit rates for continuous media objects. In our ongoing re-search
we study renements of the explicit tracking scheme,
such as a rened replacement algorithm, which tries to remove
one copy of objects with more than one cached copy
before considering objects with only one cached copy.



--R

Streaming media caching white paper.
Random RAIDs with selective exploitation of redundancy for high performance video servers.
Web caching and zipf-like distributions: Evidence and implications
Characterization of quality and tra-c for various video encoding schemes and various encoder control schemes
Dynamic batching policies for an on-demand video server
A comparison of bandwidth smoothing techiniques for the transmission of prerecorded compressed video.
Data striping and reliability aspects in distributed video servers.
Data striping and reliability aspects in distributed video servers.
Performance and reliability study for distributed video servers: Mirroring or parity.
Contributions toward Real-Time Services on Packet Networks
Multimedia storage servers: A tutorial.
Multimedia storage servers: A tutorial.
Storage and I/O Issues in Large-Scale Computing
RCBR: A simple and e-cient service for multiple time-scale tra-c

Statistical characteristics and multiplexing of MPEG streams.

queueing analysis and bandwidth allocation for VBR MPEG-2 video tra-c in ATM networks
On the design of a low-cost video-on-demand storage system
I/O issues in a multimedia system.
Call admission for prerecorded sources with packet loss.

Striping for interactive video: Is it worth it?
Architectural considerations for playback of quality adaptive video over the internet.

Proxy caching mechanism for multimedia playback streams in the internet.

Statistical properties of MPEG video tra-c and their impact on tra-c modelling in ATM systems
Design considerations for integrated proxy servers.
On the ecient retrieval of VBR video in a multimedia server.
Supporting stored video: Reducing rate variability and end-to-end resource requirements through optimal smoothing
Real time streaming protocol (RTSP).
Proxy pre


Seagate Disk Detailed Speci
A comparison study of variable bit rate versus

A network-conscious approach to end-to-end video delivery over wide area networks using proxy servers
Human Behavior and Principle of Least E
--TR
I/O issues in a multimedia system
Contributions toward real-time services on packet switched networks
RCBR
On the design of a low-cost video-on-demand storage system
Dynamic batching policies for an on-demand video server
Supporting stored video
Quality adaptation for congestion controlled video playback over the Internet
Data striping and reliability aspects in distributed video servers
Multimedia Storage Servers
Striping for Interactive Video
Performance and Reliability Study for Distributed Video Servers
A Comparison of Bandwidth Smoothing Techniques for the Transmission of Prerecorded Compressed Video
Statistical characteristics and multiplexing of MPEG streams
Characterization of Quality and Traffic for Various Video Encoding Schemes and Various Encoder Control Schemes

--CTR
Jussi Kangasharju , Felix Hartanto , Martin Reisslein , Keith W. Ross, Distributing Layered Encoded Video through Caches, IEEE Transactions on Computers, v.51 n.6, p.622-636, June 2002
K. Y. Leung , Eric W. Wong , K. H. Yeung, Designing Efficient and Robust Caching Algorithms for Streaming-on-Demand Services on the Internet, World Wide Web, v.7 n.3, p.297-314, September 2004
statistical QoS;streaming;VBR video;continuous media object;object replication;caching;replacement policy