Storage Allocation Policies for Time-Dependent Multimedia Data.
AbstractMultimedia computing requires support for heterogeneous data types with differing storage, communication, and delivery requirements. Continuous media data types such as audio and video impose delivery requirements that are not satisfied by conventional physical storage organizations. In this paper, we describe a physical organization for multimedia data based on the need to support the delivery of multiple playout sessions from a single rotating-disk storage device. Our model relates disk characteristics to the different media recording and playback rates and derives their storage pattern. This storage organization guarantees that as long as a multimedia delivery process is running, starvation will never occur. Furthermore, we derive bandwidth and buffer constraints for disk access and present an approach to minimize latencies for non-continuous media stored on the same device. The analysis and numerical results indicate the feasibility of using conventional rotating magnetic disk storage devices to support multiple sessions for on-demand video applications.
Introduction
Files comprised of multimedia data are different from conventional data files in many re-
spects. As shown in Table 1, multimedia data, and hence files, consume enormous space
and bandwidth relative to program files or "text" documents. For example, a single feature-length
JPEG-compressed movie can require over 2 Gbytes of memory for digital storage.
Multimedia data can also be sensitive to timing during delivery. When a user plays-out or
records a time-dependent multimedia data object, the system must consume or produce data
at a constant, gap-free rate. This means that the file system must ensure the availability of
sufficient data buffer space for the playback or recording process. For example, to maintain
a continuous NTSC-quality video playback, a file system must deliver data at a rate of
frames/s. Moreover, the delivery mechanism must also satisfy the intermedia synchronization
requirement among related media (e.g., the lip synchronization between audio, video,
and subtitles).

Table

1: Properties of Multimedia Data
Data Type Buffer/Bandwidth
Single text document (HTML) - 80 Kb/document
Voice-quality audio (8 bits @ 8 KHz) 64 Kb/s
CD quality audio (stereo @ 44.1 KHz) 1.4 Mb/s
NTSC-quality video (uncompressed @ 5.9 Mb/frame
512 \Theta 480 pixels, 24 bits/pixel) (177 Mb/s)
JPEG-compressed NTSC video - 7 Mb/s - 3.5 Mb/s
MPEG-I-compressed NTSC video - 1.5 Mb/s
MPEG-II-compressed NTSC
HDTV-quality video (uncompressed @ 28.7 Mb/frame
1248 \Theta 960 pixels, 24 bits/pixel) (863 Mb/s)
A multimedia file system must reconcile the deficiencies of conventional storage subsys-
tems. A typical storage subsystem accesses data by positioning its read heads at the desired
location for a data block. A random allocation approach, regardless of the time-dependency
for multimedia data, increases the head and seek switching frequencies and resultant access
latency. In addition, the electro-mechanical nature of secondary-storage devices requires the
use of scheduling disciplines modified to meet the throughput and real-time requirements
of multimedia data delivery. When a multimedia file system transfers data from a disk,
it must guarantee that multimedia data arrive at the consuming device on time. It must
also meet the timing requirements of the multimedia object; however, this task is difficult
due to the unpredictability of disk seek latencies. Furthermore, in a multitasking system,
more than one user can request multimedia or non-real-time services, thereby requiring the
management of multiple sessions. In contrast, the data allocation and scheduling strategies
for conventional file systems are only concerned with the throughput, latency, and storage
utilization for random access to files. Therefore, we seek to provide real-time behavior for a
set of multimedia sessions originating from a single storage system; typically a conventional
rotating-disk magnetic storage device. Note that we constrain ourselves to cases in which
the aggregate bandwidth of sessions is less than or equal to the capacity provided by a single
device; we do not consider RAID or other data distribution approaches in this context.
A number of related works exist in this area. The problem of satisfying timing requirements
for multimedia data has been studied as a conceptual database problem [11], as an
operating system delivery problem [1, 12, 13, 22], as a physical disk modeling problem [6, 9,
10, 18], and as a physical data organization and performance problem [5, 7, 8, 14, 21, 23, 24].
Rangan et al. [16] propose a model for storing real-time multimedia data in file systems.
The model defines an interleaved storage organization for multimedia data that permits the
merging of time-dependent multimedia objects for efficient disk space utilization. In a related
work, Rangan et al. [15] develop an admission control algorithm for determining when
a new concurrent access request can be accepted without violating the real-time constraints
of existing sessions. Polimenis [14] shows that the hard requirement for the acceptance of
a set of real-time sessions is the availability of disk bandwidth and buffer space. Gemmell
and Christodoulakis [8] establish some fundamental principles for retrieval and storage of
time-dependent data. A theoretical framework is developed for the real-time requirements
of multimedia object playback. Storage placement strategies for multichannel synchronized
data are also examined. P. Yu, Chen, and Kandlur [24] present an access scheme called the
grouped sweeping scheme (GSS) for disk scheduling to support multimedia applications by
reducing buffer space requirements. C. Yu et al. [21, 23] describe approaches to interleaving
time-dependent data to support constant playout rates. Tobagi et al. [20] develop a Streaming
RAID approach to handle video traffic on a disk array. Chiueh and Katz [4] propose
a multi-resolution video representation scheme based on Gaussian and Laplacian Pyramids,
which allows the parallel disk array to deliver only the absolute minimum amount of data
necessary.
In this paper, we propose a physical data organization and file system for multimedia
data. We interleave different media objects within a block so as to maintain temporal
relationships among those objects during retrieval (Fig. 1). We also define an allocation
policy based on the contiguous approach to prevent frequent head movement that can cause
significant seek latencies and to support editing on multimedia files. The behavior of a
conventional magnetic rotating-disk storage device is analyzed with respect to the mean and
variance of the seek latency.
disk track
video
audio
text
reserved

Figure

1: Physical Storage Organization for a Rotating Disk Device
A round-robin scheduling discipline is chosen for the service of multimedia sessions as in
other work [12, 14, 17], permitting the disk to switch alternately between multimedia tasks
and other non-real-time tasks. The file system achieves a high disk bandwidth utilization
by assigning long disk reads or writes and thus sharing the seek and latency delays among a
large number of bits read or written, resulting in a small overhead per transferred unit. We
introduce a disk access schedule which is a refined model based on the work of Polimenis
[14]. We show the constraints which must be satisfied to permit the acceptance of a set of
multimedia sessions including bandwidth and buffer considerations. This work differs from
other approaches in that we establish a probabilistic model for our disk access schedule to
accept a set of sessions rather than using a guarantee of a worst case for the frequency of
starvation.
The remainder of this paper is organized as follows. In Section 2 we describe the storage
organization and allocation policy for multimedia objects to facilitate disk bandwidth uti-
lization. In Section 3 we analyze the probabilistic behavior of disk seek latency. In Section
4 we show an access schedule for the disk and present a periodic service discipline for multi-media
objects based on the probabilistic model. In Section 5 we describe how this schedule
reduces the required buffering and increases the number of supported multimedia sessions.
Section 6 concludes the paper.
Storage Organization for Multimedia Objects
Most existing storage server architectures employ random allocation of blocks on a disk.
This type of organization is not sufficient to meet the real time requirements of multimedia
applications because the disk latency between blocks of a media object is unpredictable [17].
The file system cannot guarantee satisfaction of the deadline for the retrieval of multimedia
data.
We view a multimedia object as an entity comprised of mixed-type data components.
Without loss of generality, we model a typical multimedia object as being comprised of
audio, video and text. These three components can be viewed as distinct even though they
might be recorded at the same time [17]. During retrieval, these three streams are sent to
three output queues for playout and ultimately are experienced by the user. From a timing
perspective, the data streams can arrive at the file system with specific implied timing (e.g.,
live audio) or can arrive at the file system arbitrarily. For example, live video and audio can
be recorded at the same time while subtitles are recorded later.
This leads us to the issue of data interleaving for maintaining intermedia synchronization.
The advantage of interleaving multiple data streams into a single layout is the preservation
of timing between related steams. The penalty with this scheme is the overhead associated
with data combination and redistribution. These layouts are also called homogeneous (non-
interleaved) and heterogeneous (interleaved) layouts [17]. The homogeneous layout stipulates
storage of single medium data in blocks without interleaving. However, timing relationships
among media are stored as part of the interrelated media.
In the homogeneous approach, each medium requests a session in a round-robin schedule.
When retrieving a multimedia object, the file system must switch between sessions which
can consume additional disk bandwidth and degrade throughput. There is no such problem
in the heterogeneous approach. We merge different media data within a block based on their
temporal relationships and can treat the aggregation of data as a single media object. There-
fore, there is only one session for each multimedia object for the heterogeneous approach.
For this reason we use the heterogeneous layout approach in this work. In our approach,
multiple media streams being recorded are stored within the same block and the length of
each object is proportional to its consumption rate.
In terms of intra-media timing, interleaving of data becomes important to maintain
smooth, gap-free playout. In the extreme case, contiguous space allocation yields the highest
effective bandwidth from a disk, but with a penalty for costly reorganization during data
insertions and updates:
1. With the interleaved policy, multimedia data are stored on disk in a interleaved fashion
[16, 17, 21, 23]. This approach can guarantee continuous retrieval and smooth the
speed gap between disk and multimedia devices. Therefore, it can reduce the buffer
requirement significantly. Usually, it can be applied on optical disks or in a single user
environment.
2. With the contiguous policy, multimedia data are stored on a disk contiguously. This
policy can also provide continuous retrieval, but entails enormous copying overhead
during insertions and deletions [16]. However, it is the most efficient way for bandwidth
utilization [14]. This approach can be used for data that is seldom modified such as
read-only digital entertainment video.
In our approach, we refine the contiguous scheme using a two-tiered structure. On the
first level, we propose a doubly-linked list which is created based on the temporal relations
for a multimedia object [11]. Each item in the list contains a pointer which points to the
disk address of a media block. The reason for the doubly-linked list structure is to support
reverse playback of multimedia objects. On the second level, we store the multimedia data
that are indicated in the first level, permitting the reversal of a multimedia presentation
at any moment. Multimedia objects are stored sequentially on the disk. Subsequent media
blocks are put on adjacent, unoccupied blocks. If a disk track or cylinder becomes full (or the
next block is occupied) this policy places the multimedia data in the next nearest available
block.
3 Disk Latency and Bandwidth
To support multimedia data requires the manipulation of large files and the support for
large data consumption rates. It is the responsibility of the file system to organize the
data for efficient storage and delivery within space and I/O bandwidth limitations. In most
disk drive subsystems, the dominant inhibitor to achieving maximum disk I/O bandwidth
is seek latency. However, seek latency can be reduced through contiguous writes or reads of
time-dependent multimedia data. When these data become fragmented and discontinuous,
effective disk bandwidth diminishes due to additional seek and rotational latencies involved
in each discontinuity.

Table

2: Disk Parameters
Symbol Identification Value Units
dt Size of a single track 54,900 bytes
N head Number of tracks in a cylinder (number of disk heads) 15 tracks
T hh Time to change head to the another surface 2,000 -s
T tt Time to cross a track 21 -s
rot Rotation time for a disk 16,700 -s
R t Data transfer rate within a track 3.29 Mbyte/s
c Number of cylinders per disk 2,107 cylinders
In our modeling approach, we consider latencies attributed to data fragmentation as
well as session switching latencies. In the proposed scheduling approach, the disk is cycled
through a set of independent multimedia sessions. Because sessions exist for many cycles
and their access is unpredictable due to user interaction (e.g., start, stop, reverse), there are
significant session switching latencies. In this section, we determine these disk latencies and
their distributions through analysis for a typical hard disk storage unit suitable for a Unix
workstation [19]. Parameters characterizing such a device are summarized in Table 2 using
symbols adopted and extended from Kiessling [10].
3.1 Delay Latency
When a user edits the multimedia file or the file system schedules another process to access
the disk, the next block to be retrieved can be arbitrarily located anywhere on the device. The
disk head must start up, cross a number of tracks, switch to a recording (writing) surface and
rotate to the indicated block. Assuming that the location of the desired block is uniformly
distributed on the whole disk, then the total latency is T latency
where T cross is the arm positioning time for the disk head move to the correct track, T switch
is the delay to switch the head to the other surface, and T rotate is the delay for disk rotation.
We have derived various statistical disk performance behaviors from these base parameters,
and summarize them in Table 3.

Table

3: Derived Statistical Disk Behavior
Symbol Equation Value Units
ms
E(T cross ms
cross
ms 2
oe cross
pT tt 10.4 ms
E(T switch
ms
head
ms 2
oe switch
ms
E(T rotate ms
rotate
rot 92.96 ms 2
oe rotate
pT rot 9.64 ms
E(T latency
ms
latency
rot 201.6 ms 2
3.2 Disk Bandwidth Normalization
In an ideal disk storage organization, data can be accessed without latencies, and the data
transfer rate (or bandwidth) is dependent only on the disk rotational speed. In a real disk,
latencies are introduced due to track and platter switching, and disk rotation. These latencies
are determined by the layout of data on the disk and the scheduling policy for their access.
We can normalize the data transfer rate based on a complete disk scan policy as follows:
once the head reaches and retrieves the first block of an object, it retrieves the adjacent block
in the same track. If the whole track has been retrieved, it switches to the next surface but
remains on the same cylinder. If the whole cylinder has been retrieved, the disk arm crosses
to the next track. We normalize by considering each of these head motions in the complete
scan.
We define the size of a block as M . The frequency for switching the head to the other
disk P switch is
The size of a cylinder is S dt \Theta N head . Thus, the frequency P cross for the arm to cross to
the next track is P
. Let TM be the time to transfer a block from disk in the
optimal case. Then
period
latency 1 latency 2 latency 3 leftover
session 1 session 2 session 3
playback recording

Figure

2: Layout Model
dt \Theta N head
T represents the minimum transfer time to transfer a single byte from the disk:
dt \Theta N head
T be the maximum transfer rate onto the disk. We normalize the disk bandwidth
R as:
R =1
(1)
Therefore, we can use this derived value as the maximum effective bandwidth for data
transfer from the disk.
4 Disk Access Scheduling
In this section we show the constraints for the acceptance of a set of multimedia sessions
and the requirements for buffer size and disk bandwidth.
4.1 Scheduling Layout Model
In the layout model of Polimenis [14], a working period T period is defined for a set of multi-media
tasks and other non-real-time tasks as shown in Fig. 2.
During a working period, the schedule switches among all multimedia sessions. It carries
enough data into the buffer for the ith session to keep task i busy until its term is active
in the next working period. If R is the whole disk bandwidth that we derived in Equ. 1,
then each session i shares an interval T (i) proportional to its consumption rate R c (i). The
amount of data accessed during T (i) is equal to the amount consumed during the period
T period as follows:
R c (i)
R
period (2)
In this equation, R c (i) represents the consumption rate for session i. Let the ith session
contain k different media data (video, audio, text, etc. For viable multimedia data delivery,
the bandwidth lost due to task switching latencies plus the bandwidth consumed by each
multimedia session must be less than the normalized disk bandwidth (where the period is
fixed unless we change the number of sessions).
4.2 Bandwidth Requirements
In this section, we derive the bandwidth constraint based on the round-robin scheduling
model. Let n(i) be the number of bytes accessed for medium i during a working period
T period . The total number of bytes n to be read during a period T period is then
Because the time interval T (i) for each media is proportional to its bandwidth requirement
and R. Thus, we have period \Theta R c (i), then
R c
R c
R c (i) (3)
As shown in Fig. 2, the total interval used for multimedia sessions plus the disk seek
latency should be less than the working period T period in order to have sufficient bandwidth
for other non-real-time tasks. On the other hand, the period T period must be greater than the
time needed in the worst case to transfer data from (or to) the disk for all sessions. Suppose
we have m multimedia sessions. Let R be the total disk bandwidth and T latency (i) be the
task switching latency between sessions
R
latency
R c (i) (4)
where n(i)
R c (i)
should be equal to T period to maintain a steady-state. This means that the
amount of data read from the disk for each session i during a period is exactly equal to the
amount of data consumed by the ith consumer process. Thus, by Equ. 4,
latency (i)
latency (i)
, then
R ?R c (i)
latency (i)
R c (i)
latency (i)
The right-hand side of the above equation can be divided into two parts. The first part
is the bandwidth requirement of all multimedia sessions. The second part is the factor due
to the seek latency between any two sessions. Thus,
R c (i) +R seek (5)
and
latency (i)
latency (i) (6)
The R seek is the bandwidth wasted, or lost, when the disk head is switched between
sessions.
4.3 Buffer Requirements
In Section 4.1, we showed the bandwidth requirements for a set of multimedia sessions
without considering their acceptability in terms of buffer utilization. In the layout model,
a
time
buffer
use
latency i
period
a

Figure

3: Buffer Consumption
each session i shares only part of a period (Fig. 2). Each session must carry enough data
into the buffer to keep process i busy until it is reserviced, otherwise, the process starves.
Therefore, the second condition to accept a set of multimedia sessions is the availability of
sufficient buffer space. As illustrated in Fig. 3, session i shares a duration T (i) in a disk
access.
When session i is active, its buffer size increases at a rate R \Gamma R c (i). Outside this duration,
the buffer size shrinks at a rate R c (i). Let B(i) be the buffer requirement for session i. Then
(i), or B(i) ? R c (i) \Theta (T period \Gamma T (i)). If we let B be the total buffer
(i)]. Rewriting, we get:
Therefore, we have defined the buffer constraint that can be applied to determine the
feasibility of adopting additional multimedia sessions.
4.4 Length of Period T period
In Fig. 2 and Equ. 4, we show that the period T period must be greater than the sum of all
individual session periods in order to transfer data from (or to) disk for all sessions. Let D
be the leftover duration as shown in Fig. 2. For each period, the disk spends T transfer to
transfer data, where T
D. In a period, session i shares
duration based on its consuming rate R c (i). Therefore,
latency
R c (i)
To maintain a steady-state for the system, the data read from the disk during T (i) for
session i must be equal to the amount consumed during the period T period . Otherwise, the
buffer can starve or grow without bound. Thus,
latency (i) \Theta
R
If we let U be the utilization, where
let C be the total latencies,
then the minimum period for a set of multimedia sessions is [14]:
In Equ. 8, T latency (i) represents the seek latency corresponding to the switch from session
Because the next retrieval for session i can be allocated anywhere on
the disk, the latency T latency is a random variable. In Section 3, we derive the average seek
latency and the variance of the seek latency. Let E(T latency ) be the average seek latency and
latency be the variance of seek latency (Table 3). The expectation E(T ) and variance oe 2 (T )
of T in Equ. 8 are as follows:
latency ) \Theta
R
latency \Theta
R
By the above equations, we know T is also a random variable, so we cannot assign T to
be the lower bound of the period T min
period . Let p be the probability of starvation that can be
tolerated for the mth session. By Chebychev's Inequality we have P [jT min
period - E(T
frequency of
starvation
E(T)
Probability

Figure

4: Distribution of T
This means that if the lower bound T min
period is chosen, the probability for the mth session
to be accepted successfully is greater than
By Equ. 10, if we choose T period equal to the lower bound E(T )
, we can guarantee
that the starvation rate for session m will be less than p. Equation 10 is always true; however,
it does not mean that the starvation rate is equal to p. In the heavy load situation, when the
number of multimedia sessions m is very large, by the Law of Large Numbers, the starvation
rate will approach p. In the light load case, the starvation rate can be much lower than p.
Conversely, we can use a shorter period T period to keep the starvation rate under p.
A period T period for a set of multimedia sessions must meet two hard requirements. In
Section 4.2, we derived the bandwidth requirement, but it was not sufficient to determine
whether to accept a set of multimedia sessions. The system must also provide sufficient
buffering for each multimedia session. In the lightly loaded situation, there are always
enough buffering to support multimedia sessions. However, buffering becomes significant
when the number of multimedia sessions m is large. In this case, compared to the period
period , the duration T (i) assigned to each multimedia session is small. We simplify Equ. 7
by ignoring the T (i) and the result is still valid:
R c (i) (11)
From the equation above, we see that the buffer requirements are dependent on the length
of period T period . Let B max be the maximum buffer space that is available. There is an upper
bound T max
period for the period that can be accepted for a set of multimedia sessions; otherwise,
the total buffer requirements will exceed the available buffer space B max . From Equ. 11, we
Equs. derived above are for the general case where the consumption rates
for multimedia sessions have different values. In real applications, the disk bandwidth requirements
for multimedia sessions can have the same value. In the following example, we
assume, for simplicity, that the consumption rates for all multimedia sessions are the same
and evaluate the buffer consumption and number of sessions supported.
Example 1 In this example, we assume all multimedia sessions request the same disk
bandwidth R c . Each multimedia session includes video data at a rate of 1.92 Mb/frame
@ frames/s with a 20:1 compression ratio and audio data at a rate of 1.4 Mb/s with a
4:1 compression ratio. Each multimedia session consumes disk bandwidth at a rate of 0.4
Mbyte/s. Using the disk parameters from Tables 2 and 3 we pick the average disk latency
E(T latency ) equal to 35; 965-s and the standard deviation oe latency equal to 14; 212-s. For
Equ. 10 we let p be 0:05. We then derive the lower bound for different numbers of supported
sessions using Equ. 10 assuming the availability of 16 Mbytes of main memory that can be
assigned for buffering. The upper bound of a period is then determined by Equ. 12.

Table

4: File System Performance for Example 1
100 % Bandwidth Utilization 100 % Buffer Allocation
period (ms) Buffer Allocation (bytes) T max
period (ms) Bandwidth Utilization
6 14,013 * 28,163,000 6,667 * 100.80 %
* Insufficient memory.
Let N be the number of multimedia sessions and T min
period be the lower bound for the period.
If T min
period is chosen then there is no disk bandwidth left. By Equ. 7 we know that the buffer
requirement is minimized and we have
fR c (i) \Theta [T min
R c (i)
R
period
N \Theta R c \Theta T min
period \Theta (1 \Gamma
R c
R
)0.51.52.53.5x(Sec)
Number of Multimedia Sessions
Period
lower bound
upper bound

Figure

5: Number of Sessions vs. Period Length
The results of this analysis are summarized in Table 4. The third column presents the
buffer requirement for N multimedia sessions when we chose T min
period . The fourth column
indicates the upper bound for period. In this case, the entire 16 Mbytes of memory are
assigned to buffering, allowing us to minimize the use of disk bandwidth given the constraints.
In our layout model, a period T period is equal to the sum of all durations assigned to
multimedia sessions plus the session switching latency between sessions plus the leftover used
for other non-real-time process (Fig. 2). The percentage P of disk bandwidth consumed by
multimedia sessions can be considered as the interval assigned to the multimedia sessions,
plus disk latency lost in task switching between multimedia sessions, divided by the length
of the period:
latency (i)
period
R c
R +N \Theta T latency
period
In the fifth column of Table 4 we show the percentage of disk bandwidth consumed by
the multimedia sessions when the upper bound T max
period is chosen.
When we increase the number of supported sessions, both buffer and bandwidth requirements
will increase (Fig. 5). If there are five multimedia sessions accessing the file system,
the system can perform within these constraints, but it cannot accept additional multimedia
sessions. In this case an additional session causes the request for a 28,163,000 byte buffer
and 100:8% of disk bandwidth, both of which exceed the capacity of the system.
From the analysis presented in Sections 3 and 4, it is appropriate to describe considerations
for choosing the length of a round-robin scheduling period, and to describe the impact of
session consumption rates.
5.1 Consideration for Choosing a Period
Two hard requirements must be met when choosing the length of a period, otherwise the
system cannot function for a given workload. A period must be greater than T min
period to meet
the bandwidth requirement and less than T
period to meet the buffer requirement. These
constraints are summarized as:
period
A new multimedia session can be accepted only it satisfies this relationship. Fig. 5 illustrates
the ranges of sessions supported that satisfy these constraints. The region enveloped
by the lower bound and upper bound is safe. In Table 4, for the sixth session, the lower bound
of period T min
period is 14; 013 ms, the upper bound T max
period is 6; 667 ms. Since T min
period ,
we know the file system cannot accept six multimedia sessions at the same time.
We estimate the upper and lower bound very conservatively (due to the large m assumed).
The real upper bound can be larger and the lower bound can be lower than we have derived.
However, when the number of sessions increases, our estimates approach the real upper and
lower bounds. There are two justifications for our assumption. First, in the lightly loaded
case, there are always enough resources for use. We are more concerned about the heavily
loaded situation in which the number of multimedia sessions m is large. Second, it is not
necessary or wise to chose a period T period close to either the upper or lower bounds because
of the degradation of the throughput of other non-real-time data transfers. For a general-purpose
machine, a multimedia file system not only has to meet the hard requirements
above, but also must leave enough bandwidth for these other non-real-time transfers. Let
period be the the percentage of disk bandwidth used to read data from the disk
for non-multimedia jobs during every period T period . For a set of multimedia sessions, A is
maximized when T
period [14]. This means if we increase the period T period we can
have additional disk bandwidth leftover for non-multimedia tasks.
From a memory perspective, a multimedia file system must minimize its buffer utilization
to make memory available for other system tasks. From Equ. 11, we see that when period
period , the buffer requirement is minimized. From the above two results, we seek to
increase the period for more disk bandwidth for non-multimedia traffic but also to reduce the
period for more free memory for non-multimedia tasks. In the extreme case, if we minimize
the T period value, we minimize the buffer requirement and maximize free memory for other
non-multimedia tasks. At the same time, the leftover for disk bandwidth is zero. Similarly,
maximizing the T period can free the maximum disk bandwidth for other non-multimedia
processes to use but will also result in complete memory consumption. In this case, even if
the disk has ample bandwidth available, no non-multimedia process can use it. Thus, these
two soft requirements are in conflict.
To improve the response time for non-multimedia processes, we can change the period
period dynamically with feedback from the operating system to balance resource allocation.
For example, if there are tasks suspended due to disk bandwidth shortages and there is free
buffer space available, the file system can extend the period T period in order to have more
disk bandwidth to assign to non-multimedia processes. If there are non-multimedia processes
waiting for memory and the disk is idle during the leftover interval, the file system can shrink
the period T period in order to free memory for additional non-multimedia processes.

Table

5: Refined Model vs. Worst Case
Refined Model Worst Case
Period (ms) Buffer Allocation (bytes) Period (ms) Buffer Allocation (bytes)
For a multimedia on-demand server, the file system need only provide service to multimedia
processes. In this situation, we chose the lower bound to achieve the highest disk
utilization. Given the physical disk characteristics we can determine the buffer requirements.
By Fig. 3 and Equ. 7, we know that the amount of consumed buffer space is determined by
the period length T period . By Equ. 8, the period length depends on the sum of random variables
latency (i). We assume the worst case, take the maximum value for all task switching
latencies T latency (i), and decide the period length. This assumes that starvation can never
happen, when in practice it will only rarely happen. In a refined model, we define an acceptable
rate of non-starvation, and derive the period length which guarantees a
set of multimedia sessions can be accepted with at least a probability q of not starving. In

Table

5, we define 95%. In this case, if there are five multimedia sessions in the system
we can save 20:8% of available memory.
5.2 Consumption Rate for Multimedia Sessions
There are several factors that effect the consumption rate for a multimedia session. The most
important factor is the data compression ratio affecting the multimedia data. For example,
for video data, a compression ratio in the range of 1:10 to 1:100 is not uncommon.
In Fig. 6, we show a set of constrained bandwidth-buffering regions for sessions with
differing data rates due to a range of compression rates. Parameters are otherwise identical
to that of Example 1. This figure illustrates the safe region for various consumption rates
and allows the selection of period length T period and buffer use for a given number of sessions.
By varying the compression rate we can reduce the bandwidth required for any (video)
session and increase the number of multimedia sessions supported per device. Assuming
a uniform bandwidth requirement for each session, Fig. 7 shows the number of sessions
supported for a range of consumption ratios (bandwidth).
5.3 Variable Video Encoding Rates
In our analysis we have assumed constant-bit-rate (CBR) video encoding. This assumption
greatly simplifies analysis and is reasonable based on the MPEG-I ISO 11172 CBR option.
However, we recognize that CBR video is uncommon. Our model can be modified to accommodate
variable-bit-rate (VBR) compression schemes by aggregating several VBR streams
together [3]. For this situation, not only is the disk production rate unpredictable but the
(Sec)
Number of Multimedia Sessions
Period

Figure

Number of Sessions vs. Period Length481216200.1 0.2 0.3 0.4 0.5 0.6 0.7

Number
of
Multimedia
Sessions
Consumption Rate (MByte/s)

Figure

7: Consumption Rate vs. Number of Sessions
display consumption can be unpredictable as well, particularly if software-only decompression
of video is used. We view disk seek latencies and the transfer time of VBR streams
as random variables and use a similar probabilistic model to guarantee that the frame loss
ratio will be under a given threshold. Moreover, in [3], we describe an algorithm to reduce
the impact of frame losses due to disk starvation.
6 Conclusion
When a multimedia file system transfers data from a disk, it must guarantee that multimedia
data arrive at the playout device with a minimum latency. It must also satisfy the timing
requirements implied by the nature of the multimedia object (e.g., intermedia synchronization
among media). However, disk seek latency is very significant and can be unpredictable
in a general-purpose file system.
In this paper we presented a physical data organization for supporting the storage of
time-dependent multimedia data. We interleaved different media objects within a block
to maintain timing among the objects during data storage and retrieval. Furthermore, we
introduced a probabilistic model as a refinement of the round-round scheduling discipline
that supports concurrent multimedia sessions. It was found to reduce the amount of required
buffering during data transfer from storage. We showed the acceptance conditions
for additional multimedia sessions including bandwidth and buffer constraints, and a means
for balancing these two parameters to support the largest number of multimedia sessions
originating from a single device.



--R

"A Continuous Media I/O Server and Its Synchronization Mechanism,"
"Physical Storage Organizations for Time-Dependent Multimedia Data,"
"A Scalable Video-on- Demand Service for the Provision of VCR-Like Functions,"
"Multi-Resolution Video Representation for Parallel Disk Array,"
"Design and Performance Considerations for an Optical Disk-based, Multimedia Object Server,"
"Disk Shadowing,"
"Optimal Placement of High-Probability Randomly Retrieved Blocks on CLV Optical Disks,"
"Principles of Delay-Sensitive Multimedia Data Storage and Retrieval,"
"Parity Striping of Disk Arrays: Low Cost Reliable Storage with Acceptable Throughput,"
"Access Path Selection in Databases with Intelligent Disc Subsystems,"
"Interval-Based Conceptual Models for Time-Dependent Multimedia Data,"
"The Design and Implementation of a Continuous Media Storage Server,"
"Multimedia/Realtime Extensions for the Mach Operating System,"
"The Design of a File System that Supports Multimedia,"
"Designing an On-Demand Multimedia Service,"
"Efficient Storage Techniques for Digital Continuous Mul- timedia,"
"Designing File Systems for Digital Video and Audio,"
"An Introduction to Disk Drive Modeling,"
Seagate Wren 8 ST41650N Product Manual (Volume
"Streaming RAID - A Disk Array Management System for Video Files,"
"Placement of Audio Data on Optical Disk,"
"A Runtime Environment for Multimedia Communications,"
"Efficient Placement of Audio Data Optical Disks for Real-Time Applications,"
"Design and Analysis of a Grouped Sweeping Scheme for Multimedia Storage Management,"
--TR

--CTR
Gang Qu , Malena Mesarina , Miodrag Potkonjak, System Synthesis of Synchronous Multimedia Applications, Proceedings of the 12th international symposium on System synthesis, p.128, November 01-04, 1999
Kyungoh Lee , Heon Y. Yeom, An effective admission control mechanism for variable-bit-rate video streams, Multimedia Systems, v.7 n.4, p.305-311, July 1999
Keun Hyung Kim , Seog Park, Storage System for Supporting More Video Streams in Video Server, Multimedia Tools and Applications, v.13 n.2, p.177-196, February 2001
Guido Nerjes , Peter Muth , Gerhard Weikum, Stochastic service guarantees for continuous data on multi-zone disks, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-160, May 11-15, 1997, Tucson, Arizona, United States
Gang Qu , Miodrag Potkonjak, System synthesis of synchronous multimedia applications, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.1, p.74-97, February
Korst , Joep Aerts, On the Guaranteed Throughput of Multizone Disks, IEEE Transactions on Computers, v.52 n.11, p.1407-1420, November
Kyung-Oh Lee , Jun-Ho Park , Yoon-Young Park, Striping and scheduling for large scale multimedia servers, Journal of Computer Science and Technology, v.19 n.6, p.885-895, November 2004
Nevzat Hurkan Balkir , Gultekin Ozsoyoglu, Delivering presentations from multimedia servers, The VLDB Journal  The International Journal on Very Large Data Bases, v.7 n.4, p.294-307, December 1998
performance modeling;multimedia;time-dependent audio and video data;scheduling;physical data organization;file systems;secondary storage