Continuous Data Block Placement in and Elevation from Tertiary Storage in Hierarchical Storage Servers.
Given the cost of memories and the very large storage and bandwidth requirements of large-scale multimedia databases, hierarchical storage servers (which consist of disk-based secondary storage and tape-library-based tertiary storage) are becoming increasingly popular. Such server applications rely upon tape libraries to store all media, exploiting their excellent storage capacity and cost per MB characteristics. They also rely upon disk arrays, exploiting their high bandwidth, to satisfy a very large number of requests. Given typical access patterns and server configurations, the tape drives are fully utilized uploading data for requests that fall through to the tertiary level. Such upload operations consume significant secondary storage device and bus bandwidth. In addition, with present technology (and trends) the disk array can serve fewer requests to continuous objects than it can store, mainly due to IO and/or backplane bus bandwidth limitations. In this work we address comprehensively the performance of these hierarchical, continuous-media, storage servers by looking at all three main system resources: the tape drive bandwidth, the secondary-storage bandwidth, and the host's RAM. We provide techniques which, while fully utilizing the tape drive bandwidth (an expensive resource) they introduce bandwidth savings, which allow the secondary storage devices to serve more requests and do so without increasing demands for the host's RAM space. Specifically, we consider the issue of elevating continuous data from its permanent place in tertiary for display purposes. We develop algorithms for sharing the responsibility for the playback between the secondary and tertiary devices and for placing the blocks of continuous objects on tapes, and show how they achieve the above goals. We study these issues for different commercial tape library products with different bandwidth and tape capacity and in environments with and without the multiplexing of tape libraries.
Introduction
Future multimedia information systems are likely to contain large collections
of delay sensitive data objects (e.g. audio and video) with various lengths and
requirements. Some of the main data characteristics which
present serious challenges when building multimedia servers are: their large size,
the delay-sensitivity of their data, and their high display bandwidth requirements.
Multimedia objects can be very large in size: As one example, 100 minutes of
MPEG-2 video may require up to 6 GB of storage. Thus, the storage requirements
of future continuous media servers for many different applications will easily
exceed several terabytes.
The cost of memory strongly depends on the type of memory being em-
ployed. Currently, for RAM memory the cost is about $1.0 per MB; for individual
magnetic disk storage, the cost is about $0.1 per MB (see for ex-
ample, the cost of high performance disk drives, such as the Quantum Atlas
(http://www.quantum.com)and the Seagate Cheetah (http://www.seagate.com)).
When a large number of disk drives are grouped using disk array technology
to store large amounts of data, the cost for disk storage becomes greater than
$0.3 per MB (see for example Maximum Strategy's Gen-5 disk array product
(http://www.maxstrat.com)). For magnetic tape storage the cost is less $0.004
per MB. For higher-end tape libraries, the tape storage cost per MB ranges from
per MB (e.g., for the high-performance Ampex DST812 library with 50GB
tapes (http//www.ampex.com/html)) to significantly lower figures for 330GB
tapes.
These "capital" costs for different types of memories should also include
an organization's costs for managing their storage systems, which can be quite
significant: for disk storage it is reported to be $7 per MB; for tape library
storage, due to its automated functions, this cost is minimal [Sim97].
As an indication, in absolute dollar costs, a company's capital investment
for the storage required for a full-fledged video server (which for a few thousand
videos is currently around 12TB) would be around $400,000 if a high-performance
tape library is chosen (such as the 12.8TB Ampex DST812 library with four drives
and 256 50GB tapes) or more than $4,000,000 for eight Gen-5 disk arrays (each
storing about 1.7TB). Given that small and mid-sized companies are reported
to be willing to spend annually less than $50,000 and $120,000 for mass storage,
respectively the above cost difference ensures a dominant place in the market
for tape libraries. In fact, the annual tape library market has been reported as
growing at a pace of 34%, with some submarkets growing with a pace around
50% [Sim97].
Thus, tape library storage is very attractive when storage cost is of primary
concern. On the other hand, the access speeds of memory units point to a different
direction. Tertiary storage is characterized by very slow access times, in the order
of tens of seconds (or up to minutes in lower-end products) for magnetic tape
libraries. Magnetic disks have access times in the order of tens of milliseconds,
whereas RAM memories' access times are in the order of tens of nanoseconds.
The above are strong arguments for employing a hierarchy of memory tech-
nologies, forming a Hierarchical Storage Management System (HSMS), including
RAM-based Primary Storage (PS), magnetic disk-array-based Secondary Storage
(SS), and tape-based Tertiary Storage (TS). A key idea in a HSMS is to store
all objects in the inexpensive TS, from where they will be elevated to the SS
and PS levels before being accessed. This solves the problems owing to the large
storage space requirements of continuous media servers and the costs of memory
units. A complementary idea is to use the higher levels as a cache for the levels
below; all objects will reside permanently on TS, while popular objects, for ex-
ample, will reside for long periods of time in SS and portions of them will reside
for long periods of time in PS. This idea addresses the problems owing to the
memories' access times, and to the delay-sensitivity and high display bandwidth
requirements of many continuous objects.
Given the reported market growth, tape libraries are becoming increasingly
popular for the low level of such a HSMS. In fact, with respect to continuous
media applications, several companies have developed video storage solutions
based on tape libraries for applications such as broadcasting [Hen97]. In
most envisaged solutions, tape libraries are occupying the lowest level of the
hierarchy, are used mainly for storing the vast amounts of data, exploiting their
excellent cost per MB characteristics, while disk arrays are used for their high
bandwidth in order to serve as many requests as possible. At the same time,
colder (hoter) data objects migrate from disks (tapes) to tapes (disks). With this
in mind, this paper addresses how to cleverly exploit the bandwidth offered by
Table
Storage and display parameters
explanation typical values
bD display bandwidth (consumption rate)
of blocks in an object varies; user-defined
s block size varies; user-defined
d "time display time for 1 block varies; depends on s
bT tape drive bandwidth 0.5 - 20 MB/sec
- # of tape drives 1 - 64
e robot exchange time 6 - ?40 sec
c switch search
- # of tape cartridges
r bT =bD 0.5 - 50
of jobs multiplexed varies
t # of blocks in a "time slice" (in multiplexing) varies
modern tape drives employed in such HSMSs for continuous media applications,
so to help increase the overall system's performance.
1.1. Hierarchical Storage Management Systems
We will now discuss HSMSs in some detail, paying attention to their specifications
and functionality in order to gain the relevant insights and put the
contributions of this work in context. A summary of the HSMS's relevant parameters
and some typical values is given in Table 1.
An appropriate candidate for SS appears to be arrays of magnetic disks
[PGK88]. Given the high bandwidth requirements of many multimedia objects
and the typical, relatively low, effective bandwidth of magnetic disks
(nominal bandwidths are in the range of 4-15 MB/sec), striping techniques
[SGM86,BMGJ94,TF98] are likely to prove beneficial, since, when striping objects
across several disks, the effective SS bandwidth for these objects is several
tape- / CDROM- based
elevate
Primary Storage (PS)
Secondary Storage (SS)
disk-based
Tertiary Storage (TS)

Figure

1. Conceptual model of a Hierarchical Storage Management System (HSMS)
times that of a single disk. Currently, average seek and rotational delays are
approximately 8-10 and 3-5 msec, respectively.
With respect to TS, technological developments have led to the emergence of
robot-based magnetic-tape libraries, making them the best candidate for the TS
devices, given their desirable cost per megabyte figures. Tape libraries consist
of a series of shelves (storing a number of tape cartridges), a number of tape
drives onto which the tapes must be loaded before their objects can be accessed,
and a number of robot arms (usually 1) which are responsible for loading and
unloading the tapes to and from the drives. Despite TS's high data transfer rates
(see

Table

these devices remain comparatively slower than magnetic disks due
to the high exchange costs (unload a tape, put it on the shelf, get another tape,
load it) and to the cost of searching within a tape (proceeding at a maximum
pace of less than 1.6 GB/sec).
The conceptual model of a HSMS is illustrated in Figure 1. The conceptual
model shows the three levels of the HSMS. Data is elevated one level at a time.
In the rest of this paper, the term "elevate" has been reserved for "elevate from
TS to SS".

Figure

2 illustrates the physical architectural view of the HSMS. The key
feature that must be noted here is that PS serves as an intermediate staging
area between the TS and the SS device and that an object is not required to be
SS-resident in order to be displayed; it can also be displayed from TS.
Display
consume
upload
Tape Controller
disk array
Secondary Storage (SS)
robotic tape library
Tertiary Storage (TS)
Disk Controller
Primary Storage (PS)
retrieve
flush

Figure

2. Physical model of a Hierarchical Storage Management System (HSMS)
1.2. Related Work, Motivations, and the Problem
1.2.1. The Big Picture
There is great consensus that the I/O subsystem of a computer system
has become the performance bottleneck [PGK88,Pat93]. This observation is the
motivation for a large body of research in the area of storage servers, aiming to
increase the available SS bandwidth in the system. One thread of this research
led to the development of disk arrays [PGK88] and to the development of new
methods for placing data objects on disk arrays, which attempt to exploit their
inherent potential for high performance and reliability [SGM86,PGK88,CP90,
Gea94], mainly through data placement techniques, such as striping. Multimedia
data, such as video and audio, require very large storage capacities and very
large I/O bandwidths, making disk arrays the natural choice for the SS medium.
Researchers in multimedia and video storage servers then started paying attention
to the placement of multimedia data on SS devices in such a way so to increase
the system's performance by effectively utilizing the available SS bandwidth of
the system [RV93,LS93,GR,Tea93,BMGJ94,KK95,
ORS96,TF98].
Another thread concentrated on developing techniques to reduce the number
of required secondary storage I/O's by exploiting main-memory buffer caches and
the characteristics of several emerging applications (such as video on demand
servers). Through buffer and data sharing techniques, such as batching, bridging,
and adaptive piggybacking, and prefetching into smart-disk caches this research
attained a reduction in the required number of SS I/O streams required to support
video object requests [KRT94,RZ95,GLM96,DS94,Dan95,ASS96,TH99].
Thus, so far related research has concentrated on techniques for cleverly
exploiting the PS and SS resources of the system in order to increase its perfor-
mance. With respect to tertiary storage, there have been efforts at modelling
the performance characteristics of individual tape drives and robotic tape libraries
[HS96b,HS96a,JM98a,JM98b] and [Joh96,JM98a,JM98b] respectively, to
predict future references and prefetch documents in the SS [KW98] for digital
library applications, to derive intelligent placement strategies of data in the library
[CTZ97], as well as efforts to derive intelligent scheduling algorithms for
multiplexed video streams over tape drives [KMP90,LLW95]. As mentioned in
the introduction, disk-based storage is viewed as presently too costly to store the
thousands of video objects in a full-fledged video server, and thus TS is employed
for storage augmentation purposes.
A continuous object can be played either from TS or from SS [Che94,
KDST95,GR98,Che98]. One may Play from TS an object by issuing upload
requests to TS. The uploaded blocks of the object are placed into PS buffers,
from where they are subsequently consumed: 1 either they are transmitted over
a network to a remote client, or they are displayed to a local client. However,
note that the bandwidth of TS tape drives is typically significantly greater than
the display bandwidth of objects. Thus, playing objects directly from TS can
in general create serious PS buffer space problems. As a result, a much more
preferable choice is to first elevate the object from TS to SS (that is, physically
upload it from TS to PS, and then flush it from PS to SS), and subsequently
Play from SS the object, by issuing retrieval requests to SS for the blocks to
be displayed [GS94,KDST95]. Furthermore, given that very few users (if any)
would tolerate high response times, the playback process must be started immediately
after enough data has been elevated to SS; hence, typically, the retrieval
1 The terms "consume", "display", "playback" and "play" will be used interchangeably in this
paper.
operations executing on behalf of the playback process are executed in parallel
with the elevate operations which move the future blocks of the object to SS
[GDS95]. Let us refer to the above procedure (i.e., elevate from TS to SS, and
simultaneously play from SS), which represents the research state of the art, (for
displaying continuous objects residing in TS) as the Conventional Play method.
1.2.2. The Problem
This paper assumes the above framework of a continuous media server based
on a hierarchical storage manager. The research reported here first addresses the
important problem of continuous data elevation, from its permanent place in TS
to the higher levels [CT95]. In particular, we concentrate on on-demand elevation
(i.e., elevation occurs when a display request for the object arrives). On-demand
elevation is a non-trivial problem since it must deal with the bandwidth mismatch
problem: firstly, the display bandwidth requirements of objects are different from
the bandwidths of TS and SS devices; and secondly, the sustained (available,
effective) TS bandwidth vary with time, depending on the requirements of the
current workload (e.g., whenever multiplexing is employed).
An Example System Configuration and Problem Setup
Let us consider an example HSMS system configuration which can be employed
for a media server for movie-viewing, tele-teaching, digital libraries, and
other video-based multimedia applications. At the lower level there is a high
performance tape library (based on the Ampex DST812 tape library) with 12.8
of storage, with four drives and 256 50GB tapes, costing about $400,000.
The SS level, acts as a cache, and is a high performance disk array (based on
Maximum Strategy's Gen-5 array) consisting of 95 magnetic disks, each storing
totaling about 10% of the tertiary storage, and costing about $500,000 (or
125% of the tertiary cost).
Considering 90 minute MPEG-2 videos that require about 3GB of storage,
about 6 videos can fit in a disk. Thus, the SS level can store 570 videos in total.
Assuming for simplicity 500KB video disk blocks, each with a display time of
one second, with present technology each disk drive of the array, in isolation,
can support the uninterrupted display of about 16 videos (e.g., with 12MB/s
transfer rate, 8ms average seek cost, 4 ms average rotational delay, and 1 ms
track/cylinder switch cost). However, due to the bandwidth limitations in the
front-end and back-end I/O buses, the combined data transfer rate of the array
is about 250MB/sec, or about 20 times that of a single member drive. Thus,
although the whole SS can store 570 videos, it can support the playback of about
(20 \Theta 16 =) 320 video requests.
Assuming a real-world system, with several hundred video requests in the
system at any time, and a Zipf access-request distribution to videos, a few (e.g.,
the 10-15) most popular videos will be receiving more than 70% of all requests.
Thus it is important to create copies of the most popular videos and employ
a clever video placement of the copies to the SS disks, so their load can be
balanced and serve as many video requests as possible. Given that considerable
SS bandwidth is (in addition to sustaining the playback of the SS-resident videos)
required for elevating colder video blocks from TS to SS, it is easy to see that
all of the system's SS I/O bandwidth can be consumed. In fact, please note that
products for servers supporting large numbers of disks are currently constrained
by backplane bus limitations, which is many times smaller the combined raw
disk bandwidth [www98,www97]. This fact has been recognized by many storage
system researchers [RGF98,KP98] and is a key problem on which they focus.
In this framework, and using the Conventional Play method, the TS is used
for storage augmentation purposes, simply to store the large number of colder
videos and elevate them to SS when a request for them arrives. Since typically
the TS bandwidth is sufficient to support only few requests that fall through to
the TS level [Che98] the TS drives will be fully utilized elevating colder video
data to SS. The SS I/O bandwidth (including the backplane bus bandwidth)
is also fully utilized supporting retrieval requests for video blocks and elevation
requests for TS blocks. As mentioned, even without the bandwidth consumed by
the data elevation from TS, the SS stores many more videos than it can support.
When SS bandwidth is consumed by the need to elevate colder videos from the
TS, the available SS bandwidth decreases significantly.
The key goal of this work is to develop techniques which cleverly exploit the
bandwidth of the tape drives during elevation so to save IO bandwidth. This
saved bandwidth can allow the SS to serve additional requests for some of the
other videos it stores and thus improve the overall system performance. This is
not an easy task because, despite the high transfer rates of modern tape drives,
the average access cost in tape libraries remains very high (currently, about three
orders of magnitude higher) due to the high costs for robotic movements and
head positioning delays.
Thus, we focus on requests for delay-sensitive data elevation from TS to
higher levels, with the goals of achieving IO bandwidth savings and, in addition,
hiccup-free displays of video streams, and low start-up latencies. The saved IO
bandwidth can be used to accept and serve additional requests for SS-resident
data. At the same time, we handle the bandwidth mismatch problem during data
elevation, in a manner that allows the above savings in IO bandwidth while not
requiring any extra PS buffer space.
The remainder of the paper is structured as follows. In Section 2 we will
present "Alternate Play", a novel algorithm for on-demand data elevation through
the levels of the hierarchy and we will discuss its benefits with respect to IO
bandwidth savings and its compromises with respect to PS buffer space. In
Section 3, we contribute a set of novel techniques which place the blocks of
video objects on the tertiary storage media in a manner which alleviates the
need for extra PS buffer space and companion play algorithms which achieve the
same SS bandwidth savings as the Alternate Play algorithm. Subsequently, we
contribute the notion of strips of streams, the use of which makes our techniques
applicable even when the display bandwidth requirements are larger than the
available TS bandwidth (e.g., for low-end tape drives). In Section 4 we revisit
these issues, contributing algorithms and analyses for the case when the tape
library is multiplexed across streams (to avoid experiencing unacceptably-long
start-up latencies and to be able to offer the SS savings of the earlier sections to
many more video requests). In Section 5 we revisit the same issues, only now the
assumption of a fixed and known, a priori, multiprogramming degree is removed.
In Section 6 we discuss some real-world pitfalls and how our algorithms can be
used to avoid them. Finally, in Section 7 we will present the conclusions of this
work.
2. Data Elevation with Alternate Play
In this section we will present a novel elevation method, achieving IO band-width
savings (when compared with the Conventional Play). This new method
will be an integral part of many of our algorithms in the rest of this paper.
2.1. Alternate Play
The obvious advantage of the Conventional Play method is that it requires
no additional PS buffer space. 2 On the other hand, its obvious deficiency, is
that SS is additionally taxed as a result of the execution of flush and retrieval
operations, reducing thus the available IO bandwidth significantly. Since in our
target environment we expect IO bandwidth to be one of the (two) scarcest
resources, the above observation must be noted seriously. In the following, we
will present some approaches aiming to alleviate this problem.
An initial attempt to overcome the shortcomings of the Conventional Play
method centers on the following idea: uploaded blocks from TS can be maintained
in PS buffers and made available to the playback process from them. This can
save significant IO bandwidth.
Of course, blocks belonging to popular objects may still be flushed to SS, in
addition to maintaining them in PS buffers from where they will be consumed.
This alteration of the Play from TS method (i.e., Play from TS, and then flush to
SS), when compared with the Conventional Play, saves bandwidth for the current
request (since no retrievals from SS are needed). Also, future requests for the
same object will not additionally tax the TS or SS (since no uploads or flushes
for the SS-resident blocks are needed).
Despite these unquestionable benefits, there is an obvious concern regarding
the amount of PS buffer space which is needed to realize the aforementioned
bandwidth savings. For example, if 2, the PS space requirements are 50%
of the size of the entire object to be displayed (since when the last block is
uploaded, only half of the blocks will have been consumed). In general, the PS
space requirements are (r \Gamma 1)=r of the object's size. Given that PS buffer space
is another scarce system resource, care must be taken to use it wisely.
In an effort to reconcile this trade-off between the PS space requirements
and the IO bandwidth savings, we can use hybrid techniques, so that for some
blocks the Conventional Play method - essentially: Play from SS - is employed,
while for other blocks a Play from TS method is followed. We refer to the newly-
2 Throughout the paper, "PS buffer space requirements" will refer to the maximum number of
PS buffers (each holding 1 block) required at any instance during the display of an object.
The buffers holding blocks, which are currently being displayed, to be displayed during the
next time unit, or currently being elevated to SS are not counted, since in each of these cases,
using a buffer is unavoidable.
Table
Example of Alternate Play (r =2; B=13)
time (elevated) (uploaded) block
unit to SS to PS displayed
proposed method as the Alternate Play algorithm.
For the special case, an example of the Alternate Play algorithm on
a 13-block object, playing odd-numbered blocks from TS and even-numbered
blocks from SS, is shown in Table 2. Newly arriving blocks have been underlined.
The Alternate Play algorithm terminates when all blocks have been read off
the TS. The display of the requested object continues by consuming all remaining
blocks in strict alternation from PS and SS. At the end, half of the blocks will
have been played from TS and half from SS.
Two features of the above described (for the Alternate Play
algorithm must be noted. First, during its execution (i.e., during the first
l
time units of the object's display) the SS bandwidth requirements of even
time units are twice the SS bandwidth requirements of odd time units; for the
remaining
time units, the SS bandwidth requirements are equal to
those of the odd time units. Second, during the algorithm's execution, every two
time units the number of PS buffers (needed to hold the Play from TS blocks)
increases by 1; at the end of the algorithm's execution, half of the 'B=2 Play
from TS blocks will still be in PS. It thus follows that the PS space requirements
are 25% of the object's size.
2.2. Generalizing Alternate Play
2.2.1. Integer r
The r=2 Alternate Play algorithm of the last section, can be generalized to
handle arbitrary r ratios as follows: In every time unit, r blocks are read from TS.
From these r blocks, k blocks are uploaded to PS (and played from there) and
the remaining r\Gammak blocks are elevated to SS, for some (arbitrarily/appropriately
chosen) This gives us a family of Alternate Play algorithms, one
for each different value of k.
Pseudo-code for the above described Alternate Play is given as Algorithm 1.
The given algorithm uses routines to upload an indicated block to a PS buffer,
Algorithm 1 Alternate Play
INPUT: Object's blocks in TS
next upld blk
next displ blk
upload(next upld blk++)
for time unit i:= 1 to
l
r
do
parbegin
1. if 1
then Play-from-SS(next displ blk++)
else consume(next displ blk++)
2. for j:= 1 to r \Gamma k do elevate(next upld blk++)
for j:= 1 to k do upload(next upld blk++)
parend
or to elevate (i.e., upload and then flush) an indicated block to SS. The
parbegin/parend construct is intended to indicate that the display (consume
and Play-from-SS) of a block occurs in parallel with the readings (elevate and
upload) of the next two blocks from TS. The reader may verify that Table 2 is
a trace of Algorithm 1 for the r=2, k=1 case.
The obvious question now is "what is the best value of k?". To answer this
question, we will examine the impact of the choice of k on the SS bandwidth
savings and on the required PS buffer space.
For any value of k, the SS bandwidth savings are Bk=r blocks (since for k
out of every r blocks neither a flush to, nor a retrieve from, SS is required).
Also for any value of k, the PS buffer space requirements are Bk(r \Gamma 1)=r 2 .
This holds because the algorithm runs for B=r time units, during which Bk=r
Table
Example of brc Alternate Play (r =3:5; k=1; B=22)
time (elevated) (uploaded) block
unit to SS to PS displayed
blocks are uploaded to PS (k blocks per time unit) and Bk=r 2 blocks (= k=r
blocks for each of the B=r time units) have been played from TS. Therefore,
blocks are still in PS when the algorithm terminates.
We thus see that there is a trade-off between SS bandwidth savings and
required PS buffer space: the higher the # of blocks played from SS
# of blocks played from TS ratio is, the
lower the PS space requirements become, but the lower SS bandwidth savings are
achieved. The k parameter in the general algorithm acts as a "knob", fine-tuning
this trade-off.
2.2.2. Real r
The alert reader may have realized that, so far, we have made the implicit
assumption that r is an (arbitrary) integer. If r is a real number, as it will
most likely be the case in real-world situations, one may apply the above ideas,
uploading k out of every brc blocks to PS (and playing them from there). An
example is shown in Table 3. Again, newly arriving blocks have been underlined.
A block in brackets indicates that only part of the block is uploaded/elevated.
Clearly, the SS bandwidth savings of the above outlined algorithm (when
compared with the Conventional Play algorithm) are Bk= brc blocks.
The PS space requirements of the above algorithm are Bk(r \Gamma 1)=(r brc)
Bk=r. This holds because the algorithm runs for B=r time units, displaying B=r
blocks. During this time, Bk= brc blocks are uploaded to PS, and Bk=(r brc)
blocks (= k= brc blocks for eac h of the B=r time units) are played from TS.
Therefore, when the algorithm terminates, the number of blocks still in PS is
One might of course chose to upload k out of every dre blocks. Alternatively,
if PS space is very scarce, one might chose to upload sometimes k out of every
brc blocks and some other times k out of every dre blocks. This method will be
further discussed in Section 3.2.2.
3. Data Elevation without Multiplexing
The Alternate Play methods of the preceding section (some blocks are played
from TS, and some from SS) will be the starting point for the derivation of better
playing algorithms.
3.1. APWAT
As discussed earlier, the high PS buffer requirements of the Alternate Play
method are due to the long time that a PS buffer is dedicated to holding a
particular Play from TS block. Observe also that this long time is dependent on
r: if r is large, then the Play from TS blocks will occupy a PS buffer for a long
time (since they will come into a PS buffer too far ahead of their consumption
times). In trying to attain further reductions in the PS space requirements, our
key idea is that, by altering the order with which the blocks of an object are
recorded on the TS media, large values of r (i.e., bandwidth mismatches between
the TS and the display) can be accounted for in a way that reduces the occupancy
time of PS buffers by Play from TS blocks.
Algorithm 2 is a placement algorithm, which, when given as inputs B and r,
Algorithm 2 Twisted Placement (integer r)
INPUT: B, integer r
OUTPUT: r-twisted sequence of object's blocks (to be placed on TS)
for i:=0 to
l
r
randomly place blocks B d B
r
to blank tape positions
determines an r-twisted placement/sequence of an object's blocks
locations on a tape. Examples of twisted sequences are given
in

Figure

3 (the "randomly place blocks . " of Algorithm 2 is the "sequentially
(b)
(a)

Figure

3. (a) 2-twisted and (b) 4-twisted placements of a 13-block object
place blocks . " in the given examples).
One may now immediately see that a produced r-twisted sequence is such
that, for given r, when the object's blocks are read off the tape sequentially, every
r-th block (boldfaced in Figure 3) will be uploaded into PS precisely before the
time it has to be consumed. These ' B=r blocks can thus be played from TS
without any PS buffer space requirements; the remaining blocks will be elevated
to SS, and will be played from SS when needed. Algorithm 3 materializes the
above idea. The notational conventions of Algorithm 1 have been used here,
Algorithm 3 APWAT on r-twisted sequence, when system's bandwidth ratio is
r
INPUT: r-twisted placement of object's blocks in TS
next upld blk
next displ blk
upload(next upld blk++)
for time unit i:= 1 to
l
r
do
parbegin
1. consume(next displ blk++)
2. for j:=1 to r \Gamma 1 do
elevate(next upld blk++)
upload(next upld blk++)
parend
too. Note that the given Alternate Play With A Twist (APWAT) algorithm is
essentially an Alternate Play algorithm (that is, some blocks are played from TS
and some others from SS), but applied on a specific arrangement of the object's
blocks, so that boldfaced blocks are played from TS.
The APWAT algorithm terminates when all blocks have been read off the
TS. The display of the requested object continues by consuming one more block
from PS, and all remaining blocks exclusively from SS. The SS bandwidth requirements
remain constant (r \Gamma 1 blocks per time unit) throughout the algorithm's
execution; the display of the remaining blocks requires a constant bandwidth of
1 block per time unit. An example of APWAT's action on the 2-twisted sequence
of

Figure

shown in Table 4. Again, newly arriving blocks
have been underlined.
One can immediately see that the SS bandwidth savings of the APWAT
method are B=r blocks (since 1=r of the blocks are played from TS) for each
object. Clearly also, the PS buffer requirements are zero.
3.2. Generalizing APWAT
3.2.1. Disassociating integer r and twisting
Given the system parameter r, APWAT can be applied not only on the r-
twisted sequence, but also on any r
-twisted sequence, where k is a divisor of r.
In this case, APWAT will play all boldfaced blocks (of the r
-twisted sequence)
from TS. An example of APWAT's action on the 2-twisted sequence of a 13-block
object (see Figure 3(a)) when r=4 is given in Table 5. Once more, newly arrived
blocks have been underlined.
Clearly, when the system's bandwidth ratio is r, the SS bandwidth savings
of our newest APWAT algorithm applied on the r
-twisted sequence, are Bk=r
blocks, since k=r (boldfaced) of the B blocks are never flushed to or retrieved
from the SS.
The PS buffer space requirements of the new algorithm are B(k\Gamma1)=r. This
is true because the algorithm runs for B=r time units, during each of which the
number of blocks in PS is increased by k (uploaded from TS) and decreased by
Note that when space requirements are zero. Note
also that APWAT is always better than Alternate Play, in the sense that for any
attainable SS bandwidth savings, APWAT's PS requirements are less that Alternate
Play's PS requirements. This follows, since Bk(r\Gamma1)
r is equivalent to
r  k, which is always true.
3.2.2. Real r
As it were the case with our Alternate Play algorithm (in Section 2.2.2),
our APWAT algorithm and its companion Twisted Placement algorithm do not
require r to be an integer. One may generate the brc-twisted sequence, and apply
APWAT on it (playing all boldfaced blocks from TS). Let's call this algorithm
the brc APWAT algorithm.
The obvious drawback of the brc APWAT algorithm is that the PS buffer
space requirements are not zero any more. Indeed, one may routinely verify that,
in the worst case, the PS buffer requirement will increase to B=(r(r \Gamma 1)). This
is so, because the APWAT algorithm runs for B=r time units, displaying B=r
blocks. During this time, B= brc blocks are uploaded to PS. Since all blocks are
played from TS, when the algorithm terminates, the number of blocks still left
in PS is B
brc
.
If PS space is scarce, an alternative to the brc APWAT is possible. The
main idea is to generate a twisted sequence such that, when it is APWAT-played,

Figure

4. 2.3-twisted sequence of a 20-block object
no boldfaced block will be ever uploaded earlier than the time it will be consumed
(actually, since r may not be an integer, a block is allowed to be uploaded earlier
than the time it will be consumed but only by a fraction of a time unit). An
example of such a twisted sequence is given in Figure 4. Pseudo-code is given
Algorithm 4. Since the distances between the boldfaced blocks of our new
Algorithm 4 Twisted Placement (for real r)
INPUT: B, real r
OUTPUT: r-twisted sequence of object's blocks (to be placed on TS)
for i:=1 to
l
r
randomly place blocks B d B
r
to blank tape positions
method are sometimes 1
brc
and sometimes 1
dre
, we will refer to this new twist and
play method as the brc&dre APWAT algorithm.
Clearly, the SS bandwidth savings of our newest brc&dre APWAT algorithm
are B=r blocks, and the PS requirements is 1 block (needed to hold parts of the
partially uploaded blocks).
3.2.3. Disassociating real r and twisting
If the system parameter is a real number r, APWAT can be applied not
only on the r-twisted sequence, but also on a r 0 -twisted sequence, for any r 0 !r.
Again, APWAT will play all boldfaced blocks (of the r 0 -twisted sequence) from
TS.
Reasoning as in Section 3.2.1, one may easily verify that the SS bandwidth
savings in this case are B=r 0 blocks, and that the PS requirements are B( 1

Table

6 summarizes the performance of all examined play algorithms.
Table
Play algorithms' performance comparison
PS SS bandwidth
requirements savings Remarks
Conventional Play 0 -
Alternate Play
r
(integer r)
r
(integer
r
r
divisor of r
(integer
r
(real
\Gammar
(real
3.3. SS-resident Objects & Strips of Streams
Although not mentioned explicitly so far, all previously described algorithms
work only if r  1. One may notice that a r !1 situation may indeed arise (e.g.,
low-end products - see Table 1). One may also immediately see that the r  1
restriction is obviously not a deficiency of our algorithms: if r!1, and an object
resides exclusively on TS, no algorithm can display it without hiccups, or without
a long response time.
If r ! 1, and the object resides in SS as well, one may use the ideas presented
in the previous sections to display the object in a manner requiring less
SS bandwidth than the obvious Play from SS algorithm, while still requiring zero
PS buffer space. To this goal, we contribute the concept of a strip of a stream.
3.3.1. Integer r
A strip of a stream is a subset of the blocks of a (stream) object. We
define a 1
r -strip (of a stream) to be the strip consisting of every 1
r -th block of
an object, except for the 1st block of the object. For example, the 2-strip is
[B3, B5, B7, B9, . ], the 3-strip is [B4, B7, B10, B13, . ], etc. We store such
a 1
r -strip (as a partial replica of the object) permanently in TS.
One may now see that a continuous uploading of TS blocks results in each
such block being brought into PS precisely before it has to be consumed. Pseudo-code
displaying an object in such a manner is given as Algorithm 5. The nota-
Algorithm 5 Strips of Stream Playing (r !1; 1
r -strip (br(B\Gamma1)c blocks) in TS
ffl (rest of) object's blocks in SS
next upld blk := first block on strip
next displ blk
upload(next upld blk++)
for time unit i:= 1 to 1
r do
Play-from-SS(next displ blk++)
while time unit i  B do
parbegin
1. consume(next displ blk++)
for
Play-from-SS(next displ blk++)
2. upload(next upld blk++)
parend
tional conventions of Algorithms 1 and 3 have been used here, too. A trace of
the algorithm is given in Table 7.
Unlike all previous algorithms, the given Strips of Stream Play algorithm
terminates when all blocks have been displayed (not simply when they have been
read off the TS). Eventually, rB of the object's B blocks will have been played
from TS, and the remaining (1\Gammar)B from SS. When compared with the Conventional
Play algorith, the Strips of Stream Play algorithm achieves rB blocks SS
bandwidth savings. The PS buffer space requirement of the algorithm is zero.
Table
Example of Strips of Stream Play (B=12; r=0:5;
time uploaded block
unit from TS strip displayed
5-6 B7 B5 B6
7-8 B9 B7 B8

Table
Example of Strips of Stream Play
2:3
time uploaded block
unit from TS strip displayed
1.0-2.3 B4 B1 B2 [B3
2.3-4.6
6.9-9.2
14.8-16.1
17.1-18.4
3.3.2. Real r
Once more, the given definition of a 1
r -strip is meaningful if 1
r is an integer.
r is a arbitrary real, a 1
r -strip can be defined so that each block in the strip is
uploaded precisely before it is to be consumed.
As an example, the reader is invited to verify that if
2:3
, then the2:3 -strip of a 20-block object should be [B 4
The analogy between this 1
2:3
-strip and the boldfaced blocks of the 2.3-twisted
sequence of Figure 4 should be obvious. The Strips of Stream Play, when applied
on the above 1
2:3
-strip, will play the object as shown in Table 8. Here, notation
that 0.3 of block B 3 is displayed. Pseudo-code generating a
r -strip, for arbitrary r, is given in Algorithm 6.
Algorithm 6 1
r -strip generation (real r!1)
INPUT: B, real r!1
r -strip S[1], . , S[B]
s :=r
for i:= 1 to
l
r
4. Data Elevation With Known Multiplexing Degree
In many environments, consisting of high-end tape library products with
very large bandwidth, the tertiary storage level of a multimedia server will be
satisfying more than one requests simultaneously. In order to avoid unacceptably
high start-up latencies, it is desirable for the TS to be multiplexed. When the
bandwidth is multiplexed across several concurrent streams, the effective TS
bandwidth b T;eff and the effective ratio r eff are reduced. We will assume a Round
Robin scheduling discipline for the multiplexed requests.
A moment's thought reveals that using, say, the APWAT algorithm on the
twisted sequence for r, does not work. Consider, for example, the twisted sequence
for r =4, given in Figure 3(b). If the number of multiplexed jobs (multi-
plexing degree) is for each of the two multiplexed jobs, 3 the
APWAT algorithm, with Round Robin scheduling of a time slice equal to d, will
suffer from hiccups. For instance, while the B1's of the two objects are displayed,
APWAT will elevate/upload the next 4 blocks of the first object (which will take
time unit) and it will then switch to elevate/upload the next 4 blocks of the
second object (which will also take 1 time unit). Thus, it is apparent that the
displays will starve.
Another approach, is to use the APWAT algorithm on the twisted sequence
of

Figure

3(a), instead of Figure 3(b). For our example, the
APWAT algorithm, with Round Robin scheduling of a time slice equal to d=2,
3 For now, for readability purposes, we assume no exchange overhead.
will display both objects without hiccups. It will elevate/upload a pair of blocks
of the first object (which will take 1/2 time unit), and it will then switch to
elevate/upload a pair of blocks of the second object (which will take another 1/2
time unit). This method (playing boldfaced blocks from TS, and the rest from
SS) requires no extra PS buffers, and it achieves 50% SS bandwidth savings (since
half of the blocks are played from TS), when compared with the Conventional
Play algorithm.
A crucial factor to the last approach's success (besides the use of the twisted
sequence for r
was the fact that its time slice was the time needed to
blocks. To see why this is indeed crucial, consider, for example, the
extreme case of a time slice equal to the time needed to upload 12 blocks: the
last approach could not achieve 50% SS bandwidth savings with no extra PS
buffers (for the same sequence of r This suggests that small time slices
are better than big ones, and one should thus use time slices as small as possible.
Unfortunately, as we discussed earlier, the above approach is over-simplified,
since there is a switch cost c (which includes, possibly, a tape exchange cost, plus
a search within a tape) associated with each Round Robin's switch from one
object to another. Therefore, the just derived minimum time slice will not be
sufficient to display the objects without hiccups. Nevertheless, we are now in a
position to describe a general approach and to derive the minimum time slice.
4.1. APWAT with Round Robin
The basic idea is to split each object's blocks into groups of t blocks each
(called t-tuples, or, simply tuples), for some appropriate value of t, as follows:
the first t-tuple will contain the blocks the second t-tuple will contain
the blocks B t+1 , . , B 2t , etc. In order to process (upload, elevate, display) each
t-tuple in the most efficient way, we will use an r-twisted placement of the blocks
within each t-tuple. The desired twisting here is slightly different than the one
produced by Algorithm 2. The Twisted Placement, produced by Algorithm 2,
places the first blocks of an object in locations 1; r+1; 2r+1; 3r+1, etc. (for integer
r). The Twisted Placement that is useful in our case places the first blocks of
a tuple in locations r, 2r, 3r,. within the tuple. Such an arrangement of an
object's blocks will be called a (t; r)-organization, or simply a t-organization. An
example is shown in Figure 5.
The pseudo-code for deriving the (t; r)-organization is given in Algorithm 7.

Figure

5. (8,4)-organization of a 17-block object
The number of "full" t-tuples is
, with possibly one more t-tuple with
fewer than t blocks. Note that there are \Xi t
r
bold blocks in each t-tuple. In
general, the contents of the n-th
t-tuple is the set of blocks
which will occupy the tape positions
The first bold block in the n-th t-tuple will be B (n\Gamma1)t+2 . The i-th bold block
of a t-tuple is placed at position ir within the positions occupied by this t-tuple,
r
Algorithm 7 Twisted (t; r)-organization
INPUT: B, integer r, t
OUTPUT:(t; r)-organization
for n:=1 to
do
/* place the bold blocks in their proper position */
for i:=1 to \Xi t
r
do
randomly place un-assigned blocks of the set fB
on the blank tape positions in the set f(n \Gamma 1)t
As stated earlier, the j objects to be displayed will be multiplexed in a Round
Robin fashion: each time slice will process one t-tuple by employing the APWAT
algorithm. As an example, suppose that r=4, and consider the (8,4)-organization
of

Figure

5. While displaying B 1 of the first object, the Round Robin algorithm
will elevate [B 4 . While displaying B 2 , it will elevate
It will then start displaying B 3 , and it will
switch to a second object (processing its first 9 blocks), possibly then to a third
object (also processing its first 9 blocks), etc. During the uploads/elevations of
the blocks of the second, third, etc., objects, the display process of the first object
will finish off consuming B 3 , and it will subsequently start playing
9 from SS. To guarantee a play of all objects with no hiccups, Round
Robin should return to the first object before its display of B 9 has started.
The last remark can be used to derive a relationship between j and t. As
explained, the time required to read j t-tuples (one tuple from each object) should
be less than or equal to the time needed to display the t blocks of the tuple read
time slices earlier. Since the time needed to upload a t-tuple is ts=b T , or td=r,
and the switch cost is c, it follows that the time required to read j t-tuples is
(td=r+c)j, or (ts=b T also, the time needed to display t blocks (of
one object) is td. Thus
td
td
r
should hold. This allows us to derive the minimum allowable value of t, given the
system's characteristics c, r and d, - or equivalently (since d=r=s=b T
r, s and b T - and the number j of multiplexed jobs, as
cjr
The "j !r" condition is intuitively correct (if the number of jobs to be multiplexed
is greater than the number of blocks that can be uploaded in a time unit, then
no multiplexing is possible), and is mathematically a consequence of the "t ? 0"
condition that must hold together with (1). Note also that if (2) gives t min (j)B,
then no multiplexing is possible.
Example 1: Consider an object consisting of 12,000 blocks, each 0.5 MB,
residing on a TS having bandwidth 20 MB/sec and exchange cost 10 sec. Further-
more, assume that the time needed to display one block is 1 sec. These figures
imply that r=40.
Then, eqn. (2) says that the display of objects can be multiplexed
using APWAT with Round Robin if each object is split into at most 30 tuples of
at least 400 blocks each.
Inequality (1) may be seen under a different angle. If we assume that the
size t of each tuple has been (somehow) fixed, it gives us the maximum number
of jobs that can be multiplexed as
rtd
cr
tsr
ts
Example 2: Given the configuration described in Example 1, eqn. (3) says
that if each object is split into 30 tuples of 400 blocks each, then up to 20 such
objects can be multiplexed.
Given a system bandwidth ratio r, the APWAT algorithm using a (t; r)-
configuration, for any t, has zero PS buffer requirements, since each uploaded
(boldfaced in Figure 5) block of each of the j objects is uploaded precisely before
it is to be consumed. Clearly also, the SS bandwidth savings are B=r for each of
the j jobs yielding a total savings of jB=r blocks for all j jobs, when compared
with the Conventional Play algorithm (elevating all blocks to SS, and playing
them from there).
Note that as discussed in Section 3.2.1, given the system's ratio r, one need
not use a (t; r)-configuration; one may use instead a (t; r
k )-configuration, for any
dividing r. In such a case (see Table 6), the PS buffer requirements will be
and the SS bandwidth savings will be jBk=r blocks
for all j jobs.
Similarly, we can also handle the case where r is real. We omit the relevant
details, for space reasons, since they are very similar to the description presented
in Section 3.2.2.
4.2. Start-Up Latency Considerations
In the algorithms of Sections 2 and 3, the issue of the start-up latency was
not addressed in detail since it was not important (we were assuming only one
display request at a time: start-up latency was equal to the time needed to upload
the 1st block of the object). However, in a multiplexed environment, this issue
deserves more attention.
Assuming that all requests for the j objects arrive simultaneously, the display
of the 1st object will start with a delay of s=b T (i.e., after B 1 of the 1st
object has been uploaded), the display of the 2nd object will start with a delay
of s=b T +ts=b T +c (i.e., after the 1st t-tuple of the first object has been uploaded,
has switched to the beginning of the 2nd object, and B 1 of the 2nd object
has been uploaded), etc. Therefore, the display of the j-th object will start with
4 This is the worst case scenario, assuming that techniques such as bridging, batching, and
adaptive piggy backing are not employed.
a delay of
r
The precise effect of the choice of t now becomes more clear. Given a certain
multiplexing degree j, if one chooses t ? t min , the start-up latency will be higher
(as implied by (4)), but the TS will be idling (since when the time slice of the 1st
object arrives again, not all of its blocks, uploaded during its previous time slice,
will have been consumed), allowing it to be used for other purposes. Nonetheless,
the display of the object will be done correctly (i.e., without hiccups), the PS
space requirement will still be zero, and the total SS bandwidth savings will still
be jB=r for all j jobs. It is worth noting that, for the configuration in Example 1
20, the maximum start-up latency witnessed by a multiplexed stream
is smaller than 7 minutes. If multiplexing was not performed, to serve 20 streams
the maximum start-up latency witnessed would be over one hour and thirty eight
minutes, which is of course unacceptable for video-on-demand applications.
5. Data Elevation With Unknown Multiplexing Degree
The algorithms of the previous section (generating the (t; r)-organizations
and subsequently APWAT-playing them) work if the number j of multiplexed
jobs in known in advance. In this section, we will discuss methods of overcoming
this limitation. Assuming that r?1, if j ?r, then no multiplexing of all j display
requests is possible. We may thus assume that there is a known upper bound j M
on the maximum value of the multiplexing degree j for the system. Obviously,
In order to display j objects, for arbitrary 2  j  j M , it suffices to use
the t min (j M )-organization. This is so, because, according to (2), t min (j M )
(j). The discussion now of the last paragraph of Section 4.2 implies that using
the t min (j M )-organization will work correctly, without changing the attained SS
bandwidth savings of jB=r blocks, or the required zero PS buffer space.
One drawback of the last proposal is the fact that the TS may be idling
as discussed in Section 4.2. Additionally, this proposal suffers from increased
start-up latency, as shown by (4). If startup latency is of great importance, it
can be traded-off with additional TS media storage space, as follows: Create and
store a t min (j 1 )-organization, a t min (j 2 )-organization, etc., for various values of
Each used t min (j i )-organization is a full replica of an object in TS.
Frequently, the workload can be guessed, using past experience, and this can be
used as a guide to decide which replicas to create. At run time, given the current
multiplexing degree j curr , use the smallest such t min (j i ) value which is larger than
t min (j curr ). This will result in the smallest possible start-up latency.
On the other hand, as shown by (3), selecting the smallest such t min (j i )
value (which is larger than t min (j curr )) results in a smaller value for the maximum
allowable number of multiplexed jobs. Since the total SS bandwidth savings
offered by our methods are potentially greater when the allowable multiprogramming
degree is higher, it is most beneficial from this point of view to use the t min
value for the highest possible number of multiplexed jobs. To resolve this trade-off
between start-up latencies and achievable SS bandwidth savings, we suggest
the following algorithm:
use the smallest such t min (j i ) value which is larger than t min (j curr )
ffl as more requests arrive to the TS for multiplexing, (or depart from TS service)
dynamically switch to the smallest such t min (j i ) value which is larger than
t min (j curr ) for the new value of j curr .
With this algorithm we exploit the replicas (with the different t-tuple organi-
zations) in order to dynamically adapt to the new j curr value and allow the
maximum number of requests to be multiplexed by the TS, while at the same
time enforcing the smallest possible penalty for their start-up latencies.
6. Pragmatic Concerns
In this section we focus on pragmatic concerns arising from tape technology
and MPEG-based video-server application peculiarities and which present difficulties
for the implementation of the placement strategies developed in the earlier
sections.
6.1. Streaming Mode Recording
The first concern is with regard to the fact that tape drives are usually
recorded in a streaming mode. Because of their relatively high error rates, this
means that, when errors are detected during recording, the re-write of the affected
block occurs without stopping and rewinding the tape, creating essentially a
number of "bad spots" or "holes" amidst the useful data on the tape. This of
course complicates the requirements for our twisted placements.
The proposed solution is technical. Recall from Section 3 that given the
system parameter r, our play algorithms can operate on any r 0 -twisted sequence,
for any r 0 ! r. Note that essentially the aforementioned "holes" on a tape
have the effect of reducing the transfer rate of the real/useful data. In other
words, given r and an estimation of the write-error rate of a tape drive, we can
(perhaps pessimistically, to avoid hiccups) estimate the parameter r 0 and create
the twisting sequence for r 0 . As an example, if our estimations of the
tape write-error rate lead us to r instead of using the 4-twisting sequence
shown by Figure 3(b), we can use the 2-twisting sequence of Figure 3(a). When
recorded on tape, there will be "holes" in between the blocks of this sequence so
that on average, in each time unit the tape head will have scanned as much tape
is required to hold data blocks will have been
read off the tape, one of which will be played from TS directly.
6.2. Twisting Variable Sized Blocks
Our champion application is video servers. The predominant encoding technique
for videos is MPEG. Given the well-established practice of normalizing
video block lengths with respect to the playback duration time, the recorded
MPEG video blocks necessarily become of variable size. The variability in the
block sizes, of course, complicates our twisted placements. In fact, it complicates
all video-data placement problems. For this reason most related work (placement
algorithms (and their analyses) for video data on SS) [
assume
constant block sizes, as we have done up to now.
In this section we solve this problem. We adopt the following approach.
Let us assume that b denotes the size of block
with s now denoting the average block size. Recalling that each time unit lasts
d seconds, in each time unit T \Delta d MB are read off the tape. Assuming that none
of the B blocks has a size that is greater than T \Delta d, the pseudocode for the twist
algorithm is given as Algorithm 8.
Observations
1. During each time unit, by design, one partition is read.
2. Blocks will be the Play-from-TS blocks.
Algorithm 8 Twisted Placement with Variable Block Sizes
1. Store B 1 at the beginning of the tape
2. Split the remaining movie size into partitions
Each partition has size T \Delta d MB
There will be L such partitions, where
l
\Deltad
3. Store blocks BL+1 at the right end of
partition 1, 2, ., L, respectively
4. Distribute the remaining blocks into the empty spaces of
the partitions - these will be the Play-from-SS blocks.
3. As long as each Play-from-TS block is "flushed right" in each partition, there
will be no additional PS space requirements - these blocks will arrive just in
time before their display starts.
4. Step 4 with the above requirement is NP-Complete. It can be reduced to
the well-known bin packing problem, where each partition corresponds to a
bin and we want to employ as few (bins) partitions as possible during Step
4. That is, we wish to fit the remaining Play-from-SS blocks as tightly as
possible in the partitions, so to have the Play-from-TS blocks closer to the
right end of their partitions, so to minimize the additional requirements for
PS space.
Thus, finding the solution with the minimum PS space requirements is an
NP-Complete problem. We want an approximation algorithm for Step 4 that is
computationally inexpensive and performs close to the optimal solution. A simple
algorithm that meets these demands is the Decreasing First Fit (DFF) algorithm
[GJ79]. DFF, when "translated" into our problem setting, works as follows: First
it sorts the blocks in decreasing order of their sizes. Then the blocks are placed
in this order into the first partition they fit. It can be shown [GJ79] that the
performance of DFF is never worse than 22% of the optimal solution, which in
our problem setting means that:
1. On occasion DFF will result in requiring 22% more tape storage for a video,
because of "holes" in each partition between the Play-From-SS and the Play-
3from-TS blocks. This also implies that, in the worst case, 22% more time
will be required to read the blocks of a video from the tape.
2. However, each Play-from-TS block will require zero additional PS space.
The obvious solution to the above problem is to, first, shift left each Play-
block in its partition to fill the empty space and, second, shift left
the partitions to cover the now empty spaces between the partitions. This will
eliminate all "holes" but will also result, in the worst case, in 22% additional PS
space. Thus, we need an algorithm that will strike an effective balance between
read time and PS space overhead. Pseudocode for this algorithm is given as
Algorithm 9.
The essence of the algorithm's contribution is in Step 6, which guarantees
that there will never be a requirement for additional PS space that is greater than
MB. This is achieved at the expense of having fewer Play-from-TS blocks
(i.e., lower SS bandwidth savings, since some partitions "lose" their Play-from-TS
blocks). A following example, using typical parameter values, will illustrate the
usefulness of the above algorithm.
6.3. Average I/O Bandwidth Savings of Algorithm 9
We now provide an analysis showing the average I/O bandwidth savings of
the above algorithm, in the worst case performance of the DFF algorithm.
The total empty space, in the worst case, that would result from the running
of Algorithm 8 is 22% of the total space, that is:
total s: (5)
The number of partitions is
The average empty space per partition is:
Thus, on average, one in every k partitions "loses" its Play-from-TS block,
where
Algorithm 9 Polynomial-Time Twisted Placement under Variable Block Sizes
INPUT: All Play-from-SS and from-TS blocks, after B 1 is placed at the beginning.
next
remaining blocks = set of all Play-from-SS blocks
next
available tape into partitions of size T \Delta d MB.
1. Put at the right end of partition next part the block next TS block
2. Sort remaining blocks in decreasing order
3. Run DFF algorithm until partition next part can be filled no more
i.e., until its empty space is smaller than minimum block size in remaining blocks
4. inherit empty += amount of empty space in partition next part
5. shift left the Play-from-TS block in partition next part to cover
the partition's empty space
6. If (inherit empty  T \Delta d) then f
the last block in partition next part will now be marked
as a Play-from-SS block (i.e., partition next part lost its Play-from-TS block)
7. remove from remaining blocks the ones just placed
8. next part += 1
9. next TS block += 1
10. Repeat until all blocks are placed.
Therefore, the number of partitions without a Play-from-TS block is L
k and the
I/O bandwidth savings are
k .
Example 7: Consider an object consisting of 3,000 blocks, each 0.5 MB,
while MB/sec. For this example we have:
total
5. The number of partitions without a Play-from-TS block is about
60. So, in the worst case, we require at most 5MB PS space while about 80% of
all partitions retain their Play-from-TS block.
7. Conclusions
In this paper we have addressed the problem of continuous data elevation
in multimedia servers which are based on HSMSs; a problem which, in our view,
has not received adequate attention despite the facts that: (i) the current cost
per megabyte figures make tape libraries the most cost-efficient medium for such
applications, (ii) several real-world products are already employing tape libraries
for storing continuous media, and (iii) the significant continuous annual increase
in the tape library market promises near-future technological improvements that
will improve their performance.
We first contributed the notion of alternating the playback of delay-sensitive
data between the TS and the SS and discussed how this idea can save significant
SS bandwidth (but also pointed out that it requires non-zero buffer space). Sub-
sequently, we contributed the Twisted Placement algorithm with a companion
play algorithm, called Alternate Play With A Twist; the Placement algorithm
determines the proper placement/recording order for the blocks of objects on
the tapes so that the Play algorithm achieves the same SS bandwidth savings as
before but with zero PS buffer space requirements this time.
Subsequently, we contributed the notion of strips of streams, which are
special partial replicas of stream objects, residing permanently in TS, and which
consist of the blocks which are to be played from TS. Strips of streams allow
the previous contributions to be enjoyed even when (1) the bandwidth of TS is
smaller than the display bandwidth of objects; and (2) the objects also reside in
SS (which will be the case for the most popular objects).
Later we considered the subject of multiplexing TS-resident video streams
over tape drives. Multiplexing is desirable for two reasons. First, it can drastically
reduce the average start-up latency of videos residing in the TS. Second,
employing our placement and Play algorithms in such environments can offer
the associated SS bandwidth savings for all streams being multiplexed, increasing
the total benefits of our approach. We derived algorithms which employ the
previously-developed techniques to continue offering SS bandwidth savings, at no
additional PS buffer space. We presented an algorithm showing how to store the
stream on tapes so that a high multiplexing degree j is maintained. For each of
the j jobs the algorithm continues to achieve the aforementioned savings; thus,
the total savings are significantly greater.
For many applications we expect that the data objects will exhibit skewed
access distributions (e.g., popular movies in a movie-on-demand application). For
a large majority of cases the most popular objects will have been uploaded and
will be residing in SS. In such scenarios, the SS will be responsible for satisfying a
great percentage of requests, referring to the most popular streams. With present
technology, however, even the high-end SS server products do not have enough
bandwidth to satisfy all requests for all streams they store. (This is expected to
hold in the future as well, given the pace of improvement of storage capacities.)
When taking into account the IO bandwidth required for uploading colder streams
from TS to SS, the available IO bandwidth becomes even smaller. In this paper,
we have shown techniques which exploit the ever-increasing bandwidth of modern
tape drives, for increasing the available IO bandwidth for satisfying requests. We
made an effort to view the problem comprehensively in the sense that we focus
on all main resources (host RAM memory, SS and IO bus bandwidth, and TS
bandwidth). With our techniques the overall IO bandwidth is increased without
requiring extra host RAM, while still avoiding video hiccups. In a sense, the
aforementioned contributions suggest the collaboration of TS and SS in order to
improve the system's throughput. The essence of our proposed techniques is that
the TS of a HSMS, is not simply used to augment the storage capacity of SS
(as its traditional role would indicate) but to augment the SS bandwidth as well.
This is the high level contribution of this research.



--R

Dynamic batching policies for an on-demand video server
Staggered striping in multimedia information systems.
Tertiary Storage: An Evaluation of New Applications.
Challenges for tertiary storage in multimedia servers.
Maximizing performance in a striped disk array.
Research and development issues for large-scale multimedia information systems
Principles of optimallly placing data in tertiary storage libraries.
Buffering and caching in large-scale video servers
Buffer management policy for an on-demand video server
A pipelining mechanism to minimize the latency time in hierarchical multimedia storage managers.

Computers and Intractability: A Guide to the Theory of NP-completeness
Adaptive piggybacking: A novel technique for data sharing in video-on-demand storage servers
Continuous retrieval of multimedia data using parallelism.
A Study on the Use of Tertiary Storage in Multimedia Systems.
On multimedia repositories
The role of data storage in broadcasting future.
On the modeling and performance characteristics of a serpentine tape drive.
Random I/O scheduling in online tertiary storage systems.
Benchmarking tape system performance.
Performance measurements and models of tertiary storage devices.
An analytical performance model of robotic storage libraries.
Using tertiary storage in video-on-demand servers
Evaluating video layout strategies for a high performance storage server.
The optimum execution order of queries in linear storage.
A case for intelligent disks (idisks).
Buffer management for continuous media sharing in multimedia database systems.
Integrated document prefetching and caching in hierarchical storage based on markov-chain predictions

The design of a storage server for continuous media.

Keynote speech.
A case for redundant arrays of inexpensive disks (RAID).
Active storage for large-scale data mining and multimedia applications
Efficient storage techniques for digital continuous multime- dia
Buffer management for video database systems.
striping.
Untangle your tape storage costs.

Overlay striping and optimal parallel I/O in modern applications.
Prefetching into smart-disk caches for high-performance continuous media servers


Tpc executive summaries.
--TR

--CTR
simulated annealing approach for multimedia data placement, Journal of Systems and Software, v.73 n.3, p.467-480, November-December 2004
Athena Vakali , Evimaria Terzi , Elisa Bertino , Ahmed Elmagarmid, Hierarchical data placement for navigational multimedia applications, Data & Knowledge Engineering, v.44 n.1, p.49-80, January
tape libraries;video playback;hierarchical storage servers;placement algorithms