Scheduling and data layout policies for a near-line multimedia storage architecture.
Recent advances in computer technologies have made it feasible to provide multimedia services, such as news distribution and entertainment, via high-bandwidth networks. The storage and retrieval of large multimedia objects (e.g., video) becomes a major design issue of the multimedia information system. While most other works on multimedia storage servers assume an on-line disk storage system, we consider a two-tier storage architecture with a robotic tape library as the vast near-line storage and an on-line disk system as the front-line storage. Magnetic tapes are cheaper, more robust, and have a larger capacity; hence, they are more cost effective for large scale storage systems (e.g., videoon-demand (VOD) systems may store tens of thousands of videos). We study in detail the design issues of the tape sub-system and propose some novel tape-scheduling algorithms which give faster response and require less disk buffer space. We also study the disk-striping policy and the data layout on the tape cartridge in order to fully utilize the throughput of the robotic tape system and to minimize the on-line disk storage space.
Introduction
In the past few years, we have witnessed tremendous advances in computer technologies,
such as storage architectures (e.g. fault tolerant disk arrays and parallel I/O architec-
tures), high speed networking systems (e.g., ATM switching technology), compression and
coding algorithms. These advances have made it feasible to provide multimedia services,
such as multimedia mail, news distribution, advertisement, and entertainment, via high
bandwidth networks. Consequently, research in multimedia storage system has received
a lot of attention in recent years. Most of the recent research works have emphasized
upon the investigation of the design of multimedia storage server systems with magnetic
disks as the primary storage. In [2, 7], issues such as real-time playback of multiple audio
channels have been studied. In [17], the author presented a technique for storing video
and audio streams individually on magnetic disk. The same author proposed in [16]
techniques for merging storage patterns of multiple video or audio streams to optimize
the disk space utilization and to maximize the number of simultaneous streams. In [9],
performance study was carried out on a robotic storage system. In [4, 5], a novel storage
structure known as the staggered striping technique was proposed as an efficient way
for the delivery of multiple video or audio objects with different bandwidth demands to
multiple display stations. In [8], a hierarchical storage server was proposed to support a
continuous display of audio and video objects for a personal computer. In [11], the authors
proposed a cost model for data placement on storage devices. Finally, a prototype
of a continuous media disk storage server was described in [12].
It is a challenging task to implement a cost-effective continuous multimedia storage
system that can store many large multimedia objects (e.g., video), and at the same time,
can allow the retrieval of these objects at their playback bandwidths. For example, a
100 minutes HDTV video requires at least 2 Mbytes/second display bandwidth and 12
Gbytes of storage[3]. A moderate size video library with 1000 videos would then require
TBytes storage. It would not be cost effective to implement and manage such a huge
amount of data all on the magnetic disk subsystem. A cost-effective alternative is to
store these multimedia objects permanently in a robotic tape library and use a pool of
magnetic disks, such as disk arrays [15], for buffering and distribution. In other words,
the multimedia objects reside permanently on tapes, and are loaded onto the disks for
delivery when requested by the disk server. To reduce the tape access delays, the most
actively accessed videos would also be stored in the disks on a long term basis. The disk
array functions as a cache for the objects residing in the tape library, as well as a buffer
for handling the bandwidth mismatch of the tape drive and the multimedia objects.
Given the above architecture, this paper aims at the design of a high performance
storage server with the following requirements:
ffl Minimal disk buffer space between the robotic tape library and the parallel disk
array. Disk space is required for handling the bandwidth mismatch of large multi-media
objects, such as video or HDTV, and the tape subsystem.
ffl Minimal response time for the request to the multimedia storage system. The
response time of a request to a large multimedia object can be greatly reduced by
organizing the display unit, the network device, the parallel disk and the robotic
tape library as a pipeline such that data flows at the continuous rate of the display
bandwidth of the multimedia object along the pipeline. Since multimedia objects
reside in the tape subsystem, to minimize the system response time, we have to
minimize the tape subsystem response time. Throughout this paper, the tape
subsystem response time is defined as the arrival time of the first byte of data of a
request to the disk array minus the arrival time of the request to the multimedia
storage system.
ffl Maximal bandwidth utilization of the tape drives. The current tape library architectures
usually have few tape drives. Hence, the bandwidth utilization of tape
drives is a major factor of the average response time and throughput of the storage
server. A better utilization of the bandwidth of tape drives means a higher
throughput of the tape subsystem.
The contribution of this paper is twofold. First, we propose a novel scheduling approach
for the tape subsystem, and we show that the approach can reduce the system
response time, increase the system throughput and lower the disk buffer requirement.
Secondly, we study the disk block organization of the disk subsystem and show how it
can be incorporated with the tape subsystem to support concurrent upload and playback
of large multimedia objects.
The organization of the paper is as follows. We describe the architecture of our
multimedia storage system and present the tape subsystem scheduling algorithms in
Sections 2 and 3 respectively. Then, we discuss the disk buffer requirement for supporting
various tape subsystem scheduling algorithms in Section 4. In Section 5, we describe
the disk block organization and the data layout on the tape cartridge for supporting
concurrent upload and playback of large multimedia objects. In Section 6, we discuss
the performance study, and lastly the conclusion is given in Section 7.
Our multimedia storage system consists of a robotic tape library and a parallel disk array.
The robotic tape library has a robotic arm, multiple tape drives, tape cartridges which
multimedia objects reside, and tape cartridge storage cells for placing tape cartridges.

Figure

1 illustrates the architectural view of the multimedia storage server. The robotic
arm, under computer control, can load and unload tape cartridges. To load a tape
cartridge into a tape drive, the system performs the following steps:
1. Wait for a tape drive to become available.
2. If a tape drive is available but occupied by another tape (ex: this is the tape that
was uploaded for a previous request), eject the tape in the drive and unload this
tape to its storage cell in the library. We call these operations as the drive eject
operation and the robot unload operation respectively.
3. Fetch the newly requested tape from its storage cell and load it into the ready
tape drive. We call these operations as the robot load operation and the drive load
operation respectively.
When a multimedia object is requested, the multimedia object is first read from
the tape and stored in the disk drives via the memory buffer and the CPU. Then the
multimedia object is played back by retrieving the data blocks of the multimedia object
from the disk drives, at a continuous rate of the object bandwidth, into the main memory
while the storage server sends the data blocks in the main memory to the playback unit
via the network interface. Frequently accessed multimedia objects can be cached in the
disk drives to reduce tape access and improve system response time as well as throughput.
We define the notations for the robotic tape library in Table 1. These notations are
useful for the performance study in later sections.
display
display
display
or
Parallel Disk
Array
Disk Controller
memory buffer
Robotic Tape
Library
Tape Controller
cartridge
cell robot
arm
tape
cartridge

Figure

1: Cost-effective multimedia storage server
It is important to point out that the parameter values of a robotic tape library can
vary greatly from system to system. For instance, Table 2 shows the typical numbers for
two commercial storage libraries.
3 Tape Subsystem and Scheduling Algorithms
In this section, we describe several tape drive scheduling algorithms for our multimedia
storage system. A typical robotic tape library has one robot arm and a small number of
tape drives. A request to the tape library demands reading (uploading) a multimedia object
from a tape cartridge. The straight-forward algorithm or the conventional algorithm
to schedule a tape drive is to serve request one by one, i.e. the tape drive reads the whole
multimedia object of the current request to the disk array before reading the multimedia
object of the next request in the queue. Since the number of tape drives is small and the
r number of robotic arms.
number of tape drives.
l tape drive load time.
drive eject time.
drive rewind time.
drive search time.
T u robot load or unload time.
drive transfer rate.
display bandwidth of object O.
S(O) size of object O.

Table

1: Notations used for the robotic tape library.
reading time of a multimedia object is quite long 1 , a new request will often have to wait
for an available tape drive. The conventional algorithm performs reasonably well when
the tape drive has a bandwidth lower than the display bandwidth of the multimedia objects
being requested. However, the conventional algorithm would not result in the good
request response time when the tape drive bandwidth is the total display bandwidth of
two or more objects. To illustrate this, suppose the tape library is an Ampex DST800 2
with one tape drive. Consider the situation in which two requests of 100 minutes different
objects, each with a display bandwidth of 2 Mbytes/second. These
two requests arrive at the same time when the tape drive is idle. The video object size is
equal to the display duration times the display bandwidth, which is equal to 100 \Theta 60 \Theta 2
Mbytes. With the conventional algorithm, the transfer of the first request
starts after a robot load operation and a drive load operation. The response time
It takes 1200 seconds to upload a 1 hour HDTV video object by a tape drive with 6 Mbytes/second
bandwidth.
2 the parameter values are in Table 2.
Parameter Exabyte120 Ampex DST800
average T l 35.4 5
average T e 16.5 seconds 4 seconds
seconds 12-13 seconds
average T s 45 seconds 15 seconds
Number of tapes 116 256
Tape Capacity 5 Gbytes 25 Gbytes

Table

2: Typical parameter values of two commercial storage libraries.
of the first request is:
However, the second request will have to wait for the complete transfer of the first
multimedia object request, rewinding that tape (T r ), ejecting that tape from the drive
unloading that tape from the tape drive to its cell by the robot (T u ). Then the
robot can load the newly requested tape (T u ) and load it into the tape drive (T l ). The
response time of the second request is:
Hence, the average response time of the two requests is 450 seconds. This scenario is
illustrated in Figure 2
TransferR
Request 1 Request 2
drive load, drive eject,

Figure

2: the conventional tape scheduling algorithm
The major problem about the conventional algorithm is that multiple requests can
arrive within a short period of time and the average request response time is significantly
increased due to the large service time of individual requests. Since the tape drive of the
Ampex system is several times the display bandwidth of the multimedia objects, the tape
drive can serve the two requests in a time-slice manner such that each request receives
about half the bandwidth of the tape drive.
Suppose the tape drive serves the two requests in a time-slice manner with a transfer
period of 300 seconds as illustrated in Figure 3. The two objects are being uploaded into
the disk array at an average rate of 6.5 Mbytes/second 3 . From Figure 3, the response time
of the first and second requests are T u seconds and T u +T l +300+T e +T u +T u +T l
seconds respectively. Hence, the average response time is (15
seconds or an improvement of 60%. We argue that the time-slice scheduling
Request 2
Request 1
drive load, drive eject,

Figure

3: the time-slice tape scheduling algorithm
algorithm can be implemented with small overheads. In some tape systems, for instance,
the D2 tapes used in the Ampex robot system, have the concept of zones[1]. Zones are
3 The overhead of tape switch is approximately10% of the transfer time. Hence the effective bandwidth
of the tape drive is 13.05 Mbytes/second or 6.5 Mbytes/second for each object.
the places on the tape where the tape can drift to when we stop reading from the tape.
The function of the zone is that the tape drive can start reading from the zone rather
than rewinding to the beginning of the tape when the tape drive reads the tape again.
The time-slice algorithm has the following advantages:
ffl The average response time is greatly improved in light load conditions.
ffl In the case that the request of a multimedia object can be canceled after uploading
some or all parts of the object into the disks (ex: customers may want to cancel
the movie due to emergency or the poor entertainment value of the movie), the
waste of tape drive bandwidth for uploading unused parts of multimedia objects is
reduced.
ffl The time-slice algorithm requires less disk buffer space than the conventional algo-
rithm. The discussion of disk buffer space requirement is given in Section 4.
However, the time-slice algorithm requires more tape switches and therefore has a
higher tape switch overheads and a higher chance of robot arm contention. Our goal
is to study several versions of the time-slice scheduling algorithm which can minimize
the average response time of requests to the multimedia storage system and also, find
the point of switch from the time-slice algorithm to the conventional tape scheduling
algorithm. In the rest of this section, we will describe each scheduling algorithm in
detail.
3.1 Conventional Algorithms
The conventional algorithm is any non-preemptive scheduling algorithm, such as the
First-Come-First-Served algorithm. As each request arrives, the request joins the
request queue. A request in the request queue is said to be ready if the tape cartridge of
the request is not being used to serve another request. The simplest scheduling algorithm
is the FCFS algorithm. The FCFS algorithm selects the oldest ready request in the queue
for reading when a tape drive is available. A disadvantage of the FCFS algorithm is that
the response time of a short request can be greatly increased by any preceding long
requests [18].
Another possible conventional algorithm is the Shortest-Job-First (SJF) algorithm.
The SJF algorithm improves the average response time by serving the ready request
with the shortest service time where the service time of a request is the time required
to complete the tape switch, the data transfer, and the tape rewind operation of the
request. However, a risk of using the SJF algorithm is the possibility of starvation for
longer requests as long as there is steady supply of shorter requests.
The implementations of the FCFS and SJF algorithms are similar. We have to separate
the implementation into two cases, (1) where there is only a single tape drive
available for the tape subsystem and, (2) where there are multiple tape drives in the tape
subsystem.
Single Tape Drive The implementation of the conventional algorithms is straight-forward
and is shown as follow:
procedure conventional();
begin
while true do
begin
if (there is no ready request) then
wait for a ready request;
get a ready request from the request queue;
serve the request;
Multiple Tape Drives The implementation of the conventional algorithms consists of
several procedures. The procedure robot is instantiated once and procedure tape is
instantiated N t times where each instance of procedure tape corresponds to a physical
tape drive and each instance has an unique ID.
procedure conventional()
begin
run robot() as a process;
for i := 0 to NUM TAPE -1 do
run tape(i) as a process;
procedure robot();
begin
while true do
begin
/* accept new request */
if (a request is ready and a tape drive is available) then
begin
get a request from the request queue;
send the request to an idle tape drive;
else
if (an available drive is occupied) then
perform the drive unload operation and the robot unload operation;
else
wait for a ready request or an occupied available drive;
procedure tape(integer id);
begin
while true do
begin
wait for a request from robot arm;
serve the request;
3.2 Time-slice Algorithms
The time-slice algorithms classify requests into two types: (1) non-active requests and (2)
active requests. Newly arrived requests are first classified as non-active requests and put
into the request queue. A non-active request is said to be ready when the tape cartridge
is not being used for serving another request. Active requests are those requests being
served by the tape drive in a time-slice manner.
Since the time-slice algorithms are viable only if the tape switch overhead is small,
we restrict that the tape rewind operation to be performed when a request has been
completely served and the tape search operation is performed only at the beginning of
the service of a request. This implies that two requests of the same tape cannot be served
concurrently. Note that the chance of having two requests of the same tape in the system
is very small because (1) the access distribution of objects is highly skewed since video
rental statistics suggest some highly skewed access distributions, such as the 80/20 rule,
in which 80 percent of accesses go to the most popular 20 percent of the data [6] and,
(2) frequently accessed objects are kept in the disk drives.
The tape switch time is equal to the total time to complete a tape drive eject opera-
tion, a robot unload operation, a robot load operation, a tape drive load operation and
a tape search operation. In the remaining of the paper, we let H to be the maximum
tape switch time. The time-slice algorithms break a request into many tasks, each with
a unique task number. Each task of the same request is served separately in the order
of increasing task number. Each request is assigned a time-slice period, s, which is the
maximum service time of a task of the request. The service time of a task includes the
time required for the tape switch and the data transfer of the task. For the last task of
a request, the service time also includes the time required for a tape rewind operation.
There are many possible ways to serve several requests in a time-slice manner. We concentrate
on two representative time-slice algorithms: the Round-robin (RR) algorithm
and the Least Slack (LS) algorithm.
3.2.1 Round-robin Algorithm
In this section, we formally describe the Round-robin algorithm.
be the active requests and R n+1 ; :::; Rm be the ready non-active requests
where m  n. Let O i be the video object requested by R i for m. Let
be the time-slice periods assigned to R
With the Round-robin algorithm, the active requests are served in a round-robin
manner. In each round of service, one task of each active request will be served. The
active requests are served in the same order in each round of service. In order to satisfy the
bandwidth requirement of active request R i , the average transfer bandwidth allocated
for R i must be geater than or equal to the bandwidth of R i . Formally speaking, the
bandwidth requirement of R i is satisfied if
The Round-robin algorithm maintains the following condition:
The condition guarantees that the bandwidth requirements of the active requests are
satisfied. The efficiency of the algorithm is defined as:
(1)
When the system is lightly loaded, the tape drive can serve at least one more request
in addition to the currently active requests, the average response time is reduced for
a smaller time-slice period because a newly arrival is less likely to have to wait for a
long period. However, a smaller time-slice period means that a smaller number of active
requests can be served simultaneously, thereby increasing the chance that a newly arrived
request has to wait for the completion of an active request. Therefore, different time-slice
periods or different efficiencies of the time-slice algorithm are required to optimize
the average response time at different load conditions. To simplify our discussion, we
assume each request has the same time-slice period in the rest of the paper unless we
state otherwise.
The specification of the Round-robin algorithm is:
Simple Round-robin Algorithm. The algorithm assigns each active request
a time-slice period of s ? H seconds which has to satisfy the following
conditions:
Condition 1. The tape drive serves requests R 1 ; :::; R n in a round-robin
manner with a time-slice period of s seconds.
Condition 2. In each time slice period, the available time for data transfer
is the task being served is not the last task of an
active request, otherwise, the available time for data transfer
is the rewind time of the tape.
Condition 3. Request R n+1 which is the oldest ready non-active request
becomes active if
The straight-forward implementation of the simple Round-robin algorithm is to consider
whether more active requests can be served concurrently at the end of a service
round, i.e., the algorithm evaluates Condition 3 at the end of each service round. We
call this implementation as the RR-1 algorithm. Again, we separate the implementation
into two cases, (1) where there is only a single tape drive in the tape subsystem and, (2)
where there are multiple tape drives in the tape subsystem.
Single Tape Drive
procedure RR-1();
begin
while true do
begin
if (there is no active request and ready non-active request) then
wait for a ready non-active request;
if (the last active request is served and Condition 3
of the Simple Round-robin Algorithm is satisfied) then
accept a ready non-active request;
get a task from the active task queue;
serve the task;
With the RR-1 algorithm, a newly arrived request has to wait for one half of the
duration of a service round when the tape subsystem can serve at least one more request
in addition to the currently active requests. Since the duration of a service round grows
linearly with the number of active requests, the average waiting time of a request is high
when there are several active requests. To improve the above situation, we can check
whether one more request can be served by the tape subsystem after every completion
of an active task. We call this improved implementation of the Round-robin algorithm
as the RR-2 algorithm.
Multiple Tape Drives For the case of multiple tape drives, we have to consider the
robot arm contention because the tape drives need to wait for the robot arm to load or
unload. In the worst case, each tape switch requires a robot load operation and a robot
unload operation. Therefore, the worst case robot waiting time is 2 \Theta T u \Theta (N t \Gamma 1).
Hence, Condition 3 can be revised to become:
3.2.2 The Least-slack (LS) Algorithm
Let us study another version of time-slice algorithm which can improve on the response
time of the multimedia request. In order to maintain the playback continuity of an object,
task i of the request of the object must start to transfer data before finishing the playback
of the data of the previous task i \Gamma 1. We define the latest start time of transfer (LSTT)
of a task of an active request as the latest time that the task has to start to transfer
data in order to maintain the playback continuity of the requested object. Formally, the
LSTT of task J i is defined as:
request arrival time request response time if J i is the
first task
time of the data of task J
The slack time of a task is defined as max(LSTT of task \Gamma current time; 0). Let
be the time required to complete the data transfer of J i and the tape
rewind operation of J i (if J i is the last task of a request). The deadline of a task J i is
defined as:
A ready non-active request R can become active when the tasks of R can be served
immediately such that each task of an active request can be served at or before its
LSTT.
LS Algorithm The algorithm serves requests with the following conditions:
Condition 1. Each active task can be served in one time-slice period of s
seconds.
Condition 2. Active tasks are served in ascending order of slack time.
Condition 3. In each time slice period, the available time for data transfer
is the task being served is not the last task of an
active request, otherwise, the available time for data transfer
is the rewind time of the tape.
Condition 4. The data transfer of each active task can start at or before
the LSTT of the active task.
Condition 5. A ready non-active request can become active if Condition 4
is not violated after the request has become active.
We choose the LS algorithm for tape scheduling because the LS algorithm is optimal
for a single tape system [14] 4 in the sense that if scheduling can be achieved by any
algorithm, it can be achieved by the optimal algorithm.
For the case that the tape subsystem has only one robot arm and one tape drive,
Condition 4 of the LS Algorithm can be rewritten as follows.
Given a robotic tape library with a single tape drive, let J be the
active tasks listed in ascending order of slack time. If no active task is in service, then
Condition 4 of the LS algorithm is equivalent to the condition that each active task can
be completed at or before its deadline. In other words, Condition 4 of the LS algorithm
is equivalent to the following condition:
is the tape switch time of J i .
4 The paper discussed scheduling in single and multiple processors. The case of a single tape drive
robot library is equivalent to the case of a single processor described in the paper.
Proof: Assume there is no active task in service. By Equation (2), an active task can
start data transfer at or before its LSTT if and only if it can be completed at or before
its deadline. A task J k can be completed at or before its deadline if and only if the
time between the current time and the deadline of J k is enough to complete J k and its
preceding tasks. Therefore, Condition 4 of the LS algorithm is equivalent to
Again, we separate the implementation into two cases, (1) where there is only a single
tape drive in the tape subsystem and, (2) where there are multiple tape drives in the
tape subsystem. The implementation of the LS algorithm for the single tape case is as
follows:
Single Tape Drive
procedure LS();
begin
while true do
begin
if (there is no request) then
wait for a new request;
if (there is a ready request is non-empty and acceptnew()) then
begin
get the oldest ready request;
put the tasks of the request into the active task queue;
get the active task with the least slack time;
serve the task;
begin
float work;
pointer x;
if (the active task queue is empty) then
work := 0.0;
save the active task queue;
put the tasks of the oldest ready request into the active task queue;
while task queue is not empty do
begin
x := next active task;
work
current time) then
begin
restore the active task queue;
return(false)
restore the active task queue;
Multiple Tape Drives This implementation consists of two procedures: robot and
tape drive. Procedure robot performs the following steps repeatedly: accept a ready
request if the request can be accepted to become active immediately; if there are active
tasks and an idle tape, then send the active task with the least slack time to an idle
tape, else wait for an idle tape or an active task. Procedure tape repeatedly waits for an
active task and performs the sequence of a drive eject operation, a drive load operation,
a data transfer, and a tape rewind operation (for the last task of a request). Procedure
robot is instantiated once and procedure tape is instantiated N t times. Each instance
of procedure tape has an unique ID.
4 Disk Buffer Space Requirement
In this section, we study the disk buffer requirement for the various scheduling algorithms
that we have described. First, we show that the conventional algorithm (the FCFS or the
SJF algorithm) requires a huge amount of buffer space to achieve the maximum through-
put. The following theorem states the buffer space requirement for the conventional
algorithm.
Theorem 1 If each object of a request is of the same size S and same display bandwidth
then the conventional algorithm requires O( B
buffer space in order to
achieve its maximum throughput where the sustained tape throughput is B
t and it is equal
to SB t
Proof: The tape subsystem achieves its maximum throughput when (1) there is infinite
number of ready requests and (2) each request does not have a search time, i.e., the
requested object resides at the beginning of the tape cartridge and the tape drive can
start to read the object right after the drive load operation has been done. The sustained
bandwidth of tape subsystem is:
the tape subsystem is idle and starts to serve requests one by one. In time
interval (0, S
data are consumed at the rate of B d (O) and uploaded at the rate of
t . Hence, at time
t \GammaB d (O))S
buffer space is required to hold the accumulated
data. In time interval [ S
data are consumed at the rate of 2B d (O) and uploaded
at the rate of B
t . Therefore, at time
t \GammaB d (O))S
t \Gamma2B d (O))S
buffer space is
required to hold the accumulated data. This argument continues until the total object
display throughput matches with the tape sustained throughput. To obtain the upper
bound buffer requirement, assume we have a tape system whose sustained throughput
satisfies the following criteria:
then the upper bound buffer requirement is:
obtain the lower bound buffer requirement, assume we have a tape system whose
sustained throughput B l
satisfies the following criteria:
then the lower bound buffer requirement is:
1)STherefore, the buffer space requirement is O( B
For example,
the disk buffer size = 38.22 Gbytes.
Corollary 1 If there are N t tape drives in the tape library system. The buffer disk buffer
requirement is O( N t B
In the following theorem, we state the disk buffer requirement for the Round-robin
time-slice algorithm.
Theorem 2 If R 1 , ., R n are the active requests that satisfy the following condition:
then the Round-robin algorithm achieves the bandwidth requirements of the requested
objects, O 1 ; :::; O n iff the disk buffer size is
Proof: For R i (1  i  n), at least two disk buffers of size (s i \Gamma H)B t required for
concurrent uploading and display of object O i . Hence the necessary condition is proved.
Suppose for each request O i , there are two disk buffers b i1 and b i2 , each with size of
While one buffer is used for uploading the multimedia object from the tape
library, the other buffer is used for displaying object O i . At steady state, the maximum
period between an available buffer till the time of uploading from tape is
b i1 has just been available, the system starts to output data from the other buffer b i2 for
display. By the condition of the theorem, b i2 will not be emptied before the tape drive
starts to upload data to b i1 . Hence, the bandwidth of O i is satisfied.
5 equivalent to 1.5 hours of display time
With the same arguments, we have the following corollary for the disk buffer requirement
for the LS algorithm.
Corollary 2 If R 1 , ., R n are the active requests that satisfy the following condition:
then the LS algorithm achieves the bandwidth requirements of the requested objects, O 1 ,
iff the disk buffer size is
By Theorem 2 and Corollary 2, the LS and Round-robin algorithms require less buffer
than the conventional algorithm for the same throughput because the transfer time of
each time slice period, s can be chosen to be much smaller than the total upload
period of the object, S
5 The Disk Subsystem
Since the tape drive bandwidth or the object bandwidth can be higher than the band-width
of a single disk drive, we have to use striping techniques to achieve the required
bandwidth of the tape drive or the object. In [4], a novel architecture known as the
Staggered Striping technique was proposed for high bandwidth objects, such as HTDV
video objects. It has been shown that Staggered Striping has a better throughput than
the simple striping and virtual data replication techniques for various system loads [4]. In
this section, we show how to organize the disk blocks in Staggered Striping together with
the robotic tape subsystem so that (1) the bandwidths of the disks and the tape drives
are matched, and (2) concurrent upload and display of multimedia objects is supported.
5.1 Staggered Striping
We first give a brief review of the staggered striping architecture. With this technique,
an object O is divided into subobjects, U i , which are further divided into MO fragments.
A fragment is the unit of data transferred to and from a single disk drive. The disk drives
are clustered into logical groups. The disk drives in the same logical group are accessed
concurrently to retrieve a subobject (U i ) at a rate equivalent to B d (O). The Stride, k,
is the distance 6 between the first fragment of U i and the first fragment of U i+1 . The
relationships of the above parameters are shown below:
e where B disk is the bandwidth of a single disk drive.
ffl The size of a subobject = MO \Theta the size of a fragment.
ffl A unit of time = the time required for reading a fragment from a single disk drive.
Note that a subobject can be loaded from the disk drives into the main memory in one
time unit. To reduce the seek and rotational overheads, the fragment size is chosen to be a
multiple of the size of a cylinder. A typical 1.2 Gbytes disk drive consists of 1635 cylinders
which are of size 756000 bytes each and has a peak transfer rate of 24 Mbit/second, a
minimum disk seek time of 4 milliseconds, a maximum disk seek time of 35 milliseconds,
and a maximum latency of 16.83 milliseconds. For a fragment size of 2 cylinders, the
maximum seek and latency delay times of the first cylinder and the second cylinder
are milliseconds and milliseconds respectively. The
transfer time of two cylinders is 481 milliseconds. The total service time (including disk
seek, latency delay, and disk transfer time) of a fragment is 553.66 milliseconds. Hence,
the seek and rotational overheads is about 13% of the disk bandwidth 7 . To simplify
6 which is measured in number of disks
7 A further increase in number of cylinders does not result in much reduction of the overhead. Hence,
a fragment of 2 cylinders is reasonable assumption.
our discussion, we assume the fragment size is two cylinders and one unit of time is 0.55
seconds. To illustrate the idea of Staggered Striping, we consider the following example:
Example 1 Figure 4 shows the retrieval pattern of a 5.0 Mbytes/second object in five
2.5 Mbytes/second disk drives. The stride is 1 and MO is 2. When the object is read for
display, subobject U 0 is read from disk drives 0 and 1 and so on.
disk
time 4 U4.1 U4.0
6 U6.0 U6.1
9 U9.1 U9.0

Figure

4: Retrieval pattern of an object.
5.2 Layout of Storage on the Tape
In the following discussion, we assume that (1) staggered striping is used for the storage
and retrieval of objects in the disk drives and, (2) the memory buffer between the tape
drives and the disk drives is much smaller in size than a fragment.
Let the effective bandwidth for the time slice algorithm be B
t which is equal to s\GammaH
We show that the storage layout of an object on the tape must match the storage layout
on the disk drives so as to achieve maximum throughput of the tape drive. When the
object is displayed, each fragment requires a bandwidth of B d (O)
MO . Therefore, the tape
drive produces NO fragments where
c in a unit of time. The blocks of NO
fragments are stored in a round-robin manner such that the NO fragments are produced
as NO continuous streams of data at the same time. Consider the case described in
Example 1. Suppose B
3. If the subobjects are
stored in the following In the first time
unit, U 0:0 , U 0:1 , U 1:0 are read from the tape drive. At the same time, U 0:0 and U 0:1 are
stored in disk drive 0 and disk drive 1. Fragment U 1:0 has to be discarded and re-read in
the next time unit because disk drive 1 can only store either U 0:1 or U 1:0 . Since the output
rate of tape drive must match the input rate of disk drives, the effective bandwidth of
the tape drive is 5 Mbytes/second and the tape drive bandwidth cannot be fully utilized.
On the other hand, if the storage layout of the object is as follows: fU 0:0 ; U 0:1 ; U 1:1 g,
In each time unit, the output fragments from the
tape drive can be stored in 3 consecutive disk drives. Hence, the bandwidth of the tape
drive is fully utilized. Figure 5 shows the timing diagram for the upload of the object
from the tape drive. From time 2, subobject U 0 can be read from disk drives 0 and 1.
Hence, the object can be displayed at time 2 while the remaining subobjects are being
uploaded into the disk drives from the tape drive. Both the bandwidth of the disk drives
and the tape drive are fully utilized.
Now we should derive the conditions of matching the way that the fragments are
retrieved from the disk and the way that the fragments are uploaded from the tape. Let
D and k be the number of disk drives of the disk array and the stride respectively. In the
Zg is a representation which shows that the blocks of X, Y, and Z are stored in a round-robin
manner.
disk
time 3 U4.1 U7.1 U4.0
6 U10.1 U11.1 U8.0
9 U14.1 U11.0 U14.0

Figure

5: Upload pattern of an object.
rest of the section, we assume that the bandwidth of tape drive is at least (MO+1) \Theta B d (O)
MO
Given an object O which has been uploaded from a tape drive into the disk
array, the retrieval pattern RO of O is an L \Theta D matrix where L is the number of time
units required for the retrieval of O from the disk drives and RO (i; j) is equal to "U a:b "
if fragment U a:b of O is read at time i from disk drive j. RO (i; contains a blank entry
if no fragment is read from disk drive j at time i.
Given an object O, the upload pattern PO of O is an L \Theta D matrix where
L is the number of time units required for uploading O and PO (i; j) from a tape drive
into the disk array is equal to "U a:b " if fragment U a:b is read at time i and stored in disk
drive j. RO (i; contains a blank entry if no fragment is stored in disk drive j at time
i.
Definition 3 The storage pattern LP of a retrieval or upload pattern P is an L \Theta D
matrix where L is an integer and LP (i; j) the i-th non-blank entry of column j of P, i.e.
LP is obtained by replacing all the blank entries of P by lower non-blanking entries of
the same column with the preservation of the row-order of the entries, i.e., 8LP (a; b) and
Examples of retrieval and upload patterns are shown in Figures 4 and 5 respectively.
The retrieval and upload patterns of Figure 4 and Figure 5 have the same storage pattern
which is shown in Figure 6.
disk

Figure

An example of storage pattern.
staggered striping, when an object O is uploaded from a tape drive into
the disk array, the tape drive bandwidth can be fully utilized if
ffl the tape drive reads NO fragments of O into NO different disk drives in each unit
of time; and
ffl the storage patterns of the retrieval pattern and upload pattern of O are the same,
Proof: Assume that the retrieval pattern and the upload pattern of O have the same
storage pattern and the tape drive reads NO fragments into NO different disk drives.
Since the retrieval pattern and the upload pattern has the same storage pattern, each
uploaded fragment (from the tape drive) can be retrieved from its storage disk for display.
Since the tape drive reads NO fragments in each unit of time and all uploaded fragments
(from the tape drive) can be retrieved from the storage disks, the bandwidth of the tape
drive is fully utilized.
Definition 4 An object is said to be uniformly distributed over a set of disk drives if
each disk drive contains the same number of fragments of the object.
Theorem 3 With staggered striping, when an object O is uploaded from a tape drive to
the disk array, the tape drive bandwidth can be fully utilized if
1. k and D do not have a common factor greater than 1, i.e. the greatest common
divisor (GCD) of k and D is 1, and
2. the data transfer period, s \Gamma H, is a multiple of LCM(D;MO ;N O )
is the least common multiple of integers x, y, z.
Proof: Suppose the GCD of k and D is 1 and s \Gamma H is a multiple of LCM(D;MO ;N O )
units.
Consider the case that the object starts to be uploaded at time 0. At time i, NO
fragments has been stored and uniformly distributed into disk drives (i \Theta
(i D. Since the GCD of k and D is 1,
mod D is a one-one mapping. If we extend the domain of
f to the set of natural numbers N , then This implies that
fragments can be uniformly distributed over the disk drives. Hence,
at time LCM(D;MO ;N O )
stored and uniformly distributed
over the disk drives of the disk buffer.
Consider the case that the object is playbacked at time 0. At time i, MO fragments are
retrieved from disk drives (i \Theta
At time LCM(D;MO ;N O )
retrieved and LCM(D;MO ;N O )
fragments have been retrieved from each disk drive. Let O 0 be the object consisting of
the fragments. The following procedure finds the upload pattern PO 0
which has the same storage pattern of the retrieval pattern RO
procedure upload(var upattern : upload pattern; rpattern : retrieval pattern);
var
begin
initialize all the entries in count to 0;
initialize all the entries in upattern to blank;
spattern := storage pattern of rpattern;
for
for
begin
c := (i*k+j) mod D;
With upload pattern PO 0 , the tape reads NO different fragments into NO different
disk drives in each time unit and the storage pattern of the retrieval pattern and the
upload pattern of O 0 are the same. By Lemma 2, O 0 can be retrieved with the maximum
throughput of the tape drive. Hence, an object of a multiple of the size of O 0 , i.e.
can be uploaded with the maximum throughput of the tape drive.
Thus, if the data transfer period is a multiple of LCM(D;MO ;N O )
NO
, the tape drive bandwidth
can be fully utilized.
For the case of Example 1, the data transfer period is a multiple of LCM(5;2;3)= 10
time units or 5:5 seconds. For the case that seconds, a reasonable time-slice
period is from 200 to 300 seconds 9 . A video on demand system with a capacity of 1000
100-minutes HDTV videos of 2 Mbytes/second bandwidth requires a storage space of
1000 \Theta 12 Mbytes = 12 TBytes. If 10% of the videos reside on disks, 1.2 TBytes disk
space is required. The number of 1.2 Gbytes disk drives of the disk array is 1200, and the
data transfer period is a multiple of LCM(1200;2;3)= 400 time units = 400 \Theta 0.55 seconds
seconds or the time-slice period is 250 seconds. Hence, the disk array of 1200 disk
drives can be used as a disk buffer as well as a disk cache.
To maximize the tape drive throughput, the maximum output rate of the disk buffer
9 For this range of time-slice period, the tape switch overhead is about 10-15% of the tape drive
bandwidth.
must be at least the maximum utilized bandwidth of the tape drive. The maximum
utilized bandwidth of the tape drive is given by NOB d (O)
MO
. To have an output rate of at
least the maximum utilized bandwidth of the tape drive, the disk buffer must support
concurrent retrieval of at least d NO
MO e subobjects. For each tape drive, the minimum
number of required disk drive for buffering is NO
MO e \Theta MO .
Video uploading from the tape drive is first stored in the disk array. The playback of
the video object can start when the cluster of disk drives for uploading does not overlap
with the cluster of disk drives of the first subobject. Hence, the minimum delay, d, of the
disk buffer is defined as the smallest integer n such that 80
MO . The stride k should be carefully chosen to minimize the disk buffer delay and
improve the overall response time of the storage server.
6 Performance Evaluation
We evaluate the the performance of the scheduling algorithms for two values of the tape
drive Mbytes/second and 15 Mbytes/second by computer simulation. We
assume that (1) each tape contains only one object, and hence the search time of each
request is 0 seconds and (2) a request never waits for a tape. Since frequently accessed
objects are kept in disk drives, the probability that a request has to wait for a tape which
is being used to serve another request is very low 10 . Hence, the second assumption causes
negligible errors in the simulation results. We assume that the disk contention between
disk reads (generated by playback of objects) and disk writes (generated by upload of
objects) is resolved by delaying disk writes [13] as follows. A fragment uploaded from the
tape is first stored in the memory buffer and written into its storage disk in an idle period
of the disk. This technique smoothes out the bursty data traffic from the disk subsystem
the probability is in the order of 0.001 for the parameters of the simulation
and hence improves request response time. In practice, the additional memory buffer
space required by this technique is small because the aggregate transfer rate of the tape
subsystem is much lower than that of the disk subsystem [13]. The storage size of each
object is uniformly distributed between (7200; 14400) Mbytes. Table 3 shows the major
simulation parameters. The results are presented with 95% confidence intervals where
the length of each confidence interval is bounded by 1%.
Parameter Case 1 Case 2
seconds 12 seconds

Table

3: simulation parameters
6.1 Single Tape Drive
We first study the performance of the algorithms in a system with one robot arm and
one tape drive. Here, the request arrival process is Poisson.
Case 1. Tape drive
The maximum throughput of the tape subsystem is 1.95 requests/hour. Table 4
presents the average response time of the FCFS, SJF, RR, and LS algorithms. Blank
entries in the table show that the tape subsystem has reached the maximum utilization
and the system cannot sustain the input requests. The efficiency of RR and LS algorithms
is defined as the percentage of time spent in data transfer. An efficiency of 90% means
that 10% of time is spent in tape switches. We define the relative response time to be the
ratio of the scheduling algorithm response time divided by the FCFS algorithm response
time. The relative response times of the SJF, RR, and LS algorithms are shown in Figure
7.
Req. Arr. FCFS SJF RR-1 RR-1 RR-1 LS LS LS
Rate
(req./hr.) (sec) (sec) (sec) (sec) (sec) (sec) (sec) (sec)
1.00 1022.84 936.15 867.36 1323.80 2426.81 652.23 1059.95 2069.68

Table

4: Response time vs request arrival rate.
Case 2. Tape drive bandwidth = 15 Mbytes/second.
The maximum throughput of the tape subsystem is 4.72 requests/hour. Here, we
consider a tape subsystem with a higher performance tape drive. The average response
time of the FCFS, SJF, RR, and LS algorithms are tabulated in Table 5. Again, those
Request Arrival Rate (req/hour)
Relative
Average
Response
Time

Figure

7: The relative response time of SJF, RR, and LS scheduling algorithms.
blank entries in the table represent a case whereby the tape subsystem has reached the
maximum utilization and the system cannot sustain the input requests. The relative
response time of RR and LS algorithms is shown in Figure 8.
Req. Arr. FCFS SJF RR-1 RR-1 RR-1 RR-2 RR-2 RR-2 LS LS LS
Rate
(req./hr.) (sec) (sec) (sec) (sec) (sec) (sec) (sec) (sec) (sec) (sec) (sec)
2.0 298.70 280.84 145.82 110.13 163.25 104.66 75.62 132.80 106.30 73.92 102.24
2.5 447.42 410.77 250.22 226.21 500.59 162.93 171.68 466.91 169.01 170.92 380.94

Table

5: Response time vs request arrival rate
In both cases, the LS algorithm has the best performance in a wide range of request
arrival rates. The simulation result shows that the time-slice algorithm (especially the
LS algorithm) performs better than the FCFS algorithm and the SJF algorithm under a
RR-2
RR-2
RR-2
Request Arrival Rate (req/hour)
Relative
Average
Response
Time

Figure

8: Relative response time of SJF, RR-1, RR-2, and LS algorithms.
wide range of request arrival rates. The SJF algorithm performs better than the FCFS
algorithm for all request arrival rates.
6.2 Multiple Tape Drives
Previous experiments have shown that LS and RR algorithms outperform the FCFS and
SJF algorithms in a wide range of load conditions. We study the effect of robot arm
contention of the LS algorithm in this experiment.
The system contains 4 tape drives which have a bandwidth of 15.0 Mbytes/second.
The maximum throughput of the tape subsystem is 18.90 requests/hour. The results are
shown in Table 6. A plot of the relative response time vs arrival rate is shown in Figure
9.
In this simulation experiment, we found out that for the large range of request arrival
rates, the utilization of robot arm is very small. For example, the robot arm utilization
is only 0:215 when the request arrival rate is 14:0 requests/hour. Hence, the effect of
Request Arrival Rate FCFS SJF LS (E=0.9)
2.0 19.19 19.18 15.13
4.0 25.11 25.02 16.22
6.0 36.05 35.60 20.60

Table

Multiple tape drives case: response time vs request arrival rate.
robot arm contention is not a major factor in determining the average response time.
6.3 Throughput Under Finite Disk Buffer
In this section, we study the maximum throughput of the FCFS, SJF, and LS algorithms
with finite disk buffer space. The maximum throughput of the scheduling algorithm is
found by a close queueing network in which there are 200 clients and each client initiates
a new request immediately after its previous request has been served. Hence, there are
always 200 requests in the system. The maximum throughput of the LS, FCFS, and SJF
algorithms are evaluated for Cases 1 and 2. In each case, the size of each disk buffer is
chosen to be large enough to store the data uploaded from a tape drive in one time-slice
period. The efficiency of the LS algorithm is chosen to be 0.9, and therefore, the time-slice
period is 300 seconds. The disk buffer sizes of Case 1 and 2 are 1.582 Gbytes and
3.955 Gbytes respectively. The results for Case 1 and Case 2 are shown in Figure 10 and
Request Arrival Rate (req/hour)
Relative
Average
Response
Time

Figure

9: Relative response time of the SJF and LS algorithms

Figure

respectively. From the figures, we observe that the LS algorithm has much
higher throughput (in some cases, we have 50 % improvement) than the FCFS and SJF
algorithms in a wide range of number of disk buffers. The throughput of each algorithm
grows with the number of disk buffers but the LS algorithm reaches its maximumpossible
throughput with about half of the buffer requirement that the FCFS algorithm needs to
achieve its maximum possible throughput. The SJF algorithm performs slightly better
than the FCFS algorithm. The FCFS (or SJF) algorithm performs better than the LS
algorithm for about 10% when the disk buffer space is large enough.
6.4 Discussion of Results
The results show that the LS and Round-robin algorithms outperform the conventional
algorithms (FCFS and SJF) in a wide range of request arrival rates. In all the cases, the
LS algorithm with 90% efficiency outperforms the FCFS algorithm and the SJF algorithm
when the request arrival rate is below 60% of the maximum throughput of the tape
subsystem. The conventional algorithms have a better response time when the request
FCFS
Number of Disk Buffers
Maximum
Throughput
(req./hr.)

Figure

10: Maximum throughput of the FCFS, SJF, and LS algorithms
arrival rate is quite high (above 70% of the maximum throughput of the conventional
algorithms). For the LS or Round-robin algorithm, the algorithm performs better with
a lower efficiency factor at low request arrival rate and better with a higher efficiency
factor at high request arrival rate. The results also show that the relative response time
of the LS and Round-robin algorithms reach a minimum at certain request arrival rate.
This is because the response time is the sum of the waiting time W and the tape switch
time H. At low request arrival rate, H is the major component of the response time.
As the request arrival rate increases from zero, the waiting time of the conventional
algorithms grows faster than that of the LS and Round-robin algorithms because the LS
and Round-robin algorithms can serve several requests at the same time and hence reduce
the chance of waiting for available tape drive. Therefore, the relative response time of
the LS and Round-robin algorithms decreases with the increase of request arrival rate
when the request arrival is low. When the request arrival rate is high enough, the waiting
time of LS and Round-robin algorithms becomes higher than that of the conventional
algorithms because the conventional algorithms have a better utilization of the tape drive
bandwidth which covers the high load conditions.
FCFS
Number of Disk Buffers
Maximum
Throughput
(req./hr.)

Figure

Maximum throughput of the FCFS, SJF, and LS algorithms
7 Concluding Remarks
In this paper, we have proposed a cost-effective near-line storage system for a large
scale multimedia storage server using a robotic tape library. We have studied a class of
novel time-slice scheduling algorithms for the tape subsystem and have shown that under
light to moderate workload, this class of tape scheduling algoritms has better response
time and requires less disk buffer space than the conventional algorithm. Also, we have
complemented our work to the proposed Staggered Striping architecture [4] and showed
that using our proposed scheduling algorithms, how we can organize the data layout on
disks and tape cartridges for concurrent upload and display of large multimedia objects.
From the performance results, the selection of time-slice value is often more important
than the choice of the time-slice algorithm used. If the request arrival process is known in
advance (i.e. the average request arrival rate and the inter-arrival time distribution are
known), the time-slice value can be adjusted by using pre-computed results (obtained by
either analytical methods or simulations). In practical environments, the request arrival
process is usually not known in advance. One simple method that can be used is to
adjust the time-slice value according to the length of the queue of waiting requests, i.e., a
larger time-slice value is required if the length of the queue is longer. The function from
the queue length to the time-slice value can be pre-determined by empirical studies. In
general, the optimal time-slice value depends on the request arrival process, the number
of requests waiting for service, and the states of the currently active requests. Further
work is required to find the best way to determine the optimal time-slice value.



--R

The Ampex DST800 Robotic Tape Library Technical Marketing Document.
"A File System for Continuous Media,"
"Channel Coding for Digital HDTV Terrestrial Broadcasting,"
"Staggered Striping in Multi-media Information Systems,"
"A Fault Tolerant Design of a Multimedia Server,"
An Evaluation of New Applications
"Principles of Delay-Sensitive Multimedia Data Storage and Retrieval,"
"On Multimedia Repositories, Personal Com- puters, and Hierarchical Storage Systems,"
"Analysis of Striping Techniques in Robotic Storage Libraries,"
"Video On Demand: Architecture, Systems, and Applications,"
"Using
"The Design of a Storage Server for Continuous Me- dia,"
"Scheduling and Replacement Policies for a Hierarchical Multimedia Storage Server,"
"Multiprocessor Scheduling in a Hard Real-Time Environment,"
"A case for Redundant Arrays of Inexpensive Disks (RAID),"
"Efficient Storage Techniques for Digital Continuous Multimedia,"
"Designing an On-Demand Multimedia Service,"
Operating Systems
"Designing a Multi-User HDTV Storage Server,"
--TR
A case for redundant arrays of inexpensive disks (RAID)
Principles of delay-sensitive multimedia data storage retrieval
A file system for continuous media
Staggered striping in multimedia information systems
On multimedia repositories, personal computers, and hierarchical storage systems
Tertiary storage
Fault tolerant design of multimedia servers
Efficient Storage Techniques for Digital Continuous Multimedia
Using tertiary storage in video-on-demand servers

--CTR
Kien A. Hua , Ying Cai , Simon Sheu,
Patching
M. Y. Y. Leung , J. C. S. Lui , L. Golubchik, Use of Analytical Performance Models for System Sizing and Resource Allocation in Interactive Video-on-Demand Systems Employing Data Sharing Techniques, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.615-637, May 2002
S.-H. Gary Chan , Fouad A. Tobagi, Modeling and Dimensioning Hierarchical Storage Systems for Low-Delay Video Services, IEEE Transactions on Computers, v.52 n.7, p.907-919, July
multimedia storage;scheduling;data layout