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., video-on-demand (VOD) systems may store tens of thousands of videos). We study in detail the design issues of the tape subsystem 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.     

Design and evaluation of a multimedia storage server for mixed traffic

The relative simplicity of access to digital communications nowadays and the simultaneous increase in the available bandwidth are leading to the definition of new telematic services, mainly oriented towards multimedia applications and interactivity with the user. In the near future, a decisive role will be played in this scenario by the providers of interactive multimedia services of the on-demand type, which will guarantee the end user a high degree of flexibility, speed and efficiency. In this paper, some of the technical aspects regarding these service providers are dealt with, paying particular attention to the problems of storing information and managing service requests. More specifically, the paper presents and evaluates a new storage technique based on the use of disk array technology, which can manage both typical multimedia connections and traditional requests. The proposed architecture is based on the joint use of the partial dynamic declustering and the information dispersal algorithm, which are employed for the allocation and retrieval of the data stored on the disk array. We also define efficient strategies for request management in such a way as to meet the time constraints imposed by multimedia sessions and guarantee good response times for the rest of the traffic. The system proposed is then analyzed using a simulation approach.     

An effective admission control mechanism for variable-bit-rate video streams

For admission control in real-time multimedia systems, buffer space, disk bandwidth and network bandwidth must be considered. The CBR-based mechanisms do not use system resources effectively, since media data is usually encoded with VBR compression techniques. We propose an admission control mechanism based on a VBR data model that has a dynamic period length. In our mechanism, the period can be adaptively changed to maximize the performance, considering both disk bandwidth and buffer space. To compare the performance, extensive simulations are conducted on RR, SCAN, and GSS schemes which have the dynamic period length and the static period length.     

Tertiary storage in multimedia systems: staging or direct access?

Multimedia applications that are required to manipulate large collections of objects are becoming increasingly common. Moreover, the size of multimedia objects, which are already huge, are getting even bigger as the resolution of output devices improve. As a result, many multimedia storage systems are not likely to be able to keep all of their objects disk-resident. Instead, a majority of the less popular objects have to be off-loaded to tertiary storage to keep costs down. The speed at which objects can be accessed from tertiary storage is thus an important consideration. In this paper, we propose an adaptive data retrieval algorithm that employs a combination of staging and direct access in servicing tertiary storage retrieval requests. At retrieval time, an object that resides in tertiary storage can either be staged to and then played back from disks, or the object can be accessed directly from the tertiary drives. We show that a simplistic policy that adheres strictly to staging or direct access does not exploit the full retrieval capacity of both the tertiary library and the secondary storage. To overcome the problem, we propose a data retrieval algorithm that dynamically chooses between staging and direct access, based on the relative load on the tertiary versus secondary devices. A series of simulation experiments confirms that the algorithm achieves good access times over a wide range of workloads and resource configurations. Moreover, the algorithm is very responsive to changing load conditions.     

Failure recovery algorithms for multimedia servers

In this paper, we present two novel disk failure recovery methods that utilize the inherent characteristics of video streams for efficient recovery. Whereas the first method exploits the inherent redundancy in video streams (rather than error-correcting codes) to approximately reconstruct data stored on failed disks, the second method exploits the sequentiality of video playback to reduce the overhead of online failure recovery in conventional RAID arrays. For the former approach, we present loss-resilient versions of JPEG and MPEG compression algorithms. We present an inherently redundant array of disks (IRAD) architecture that combines these loss-resilient compression algorithms with techniques for efficient placement of video streams on disk arrays to ensure that on-the-fly recovery does not impose any additional load on the array. Together, they enhance the scalability of multimedia servers by (1) integrating the recovery process with the decompression of video streams, and thereby distributing the reconstruction process across the clients; and (2) supporting graceful degradation in the quality of recovered images with increase in the number of disk failures. We present analytical and experimental results to show that both schemes significantly reduce the failure recovery overhead in a multimedia server.     

Issues in the design of a storage server for video-on-demand

We examine issues related to the design of a storage server for video-on-demand (VOD) applications. The storage medium considered is magnetic disks or arrays of disks. We investigate disk scheduling policies, buffer management policies and I/O bus protocol issues. We derive the number of sessions that can be supported from a single disk or an array of disks and determine the amount of buffering required to support a given number of users. Furthermore, we propose a scheduling mechanism for disk accesses that significantly lowers the buffer-size requirements in the case of disk arrays. The buffer size required under the proposed scheme is independent of the number of disks in the array. This property allows for striping video content over a large number of disks to achieve higher concurrency in access to a particular video object. This enables the server to satisfy hundreds of independent requests to the same video object or to hundreds of different objects while storing only one copy of each video object. The reliability implications of striping content over a large number of disks are addressed and two solutions are proposed. Finally, we examine various policies for dealing with disk thermal calibration and the placement of videos on disks and disk arrays.     

Disk placement for arbitrary-rate playback in an interactive video server

Multimedia data, especially continuous media including video and audio objects, represent a rich and natural stimulus for humans, but require large amount of storage capacity and real-time processing. In this paper, we describe how to organize video data efficiently on multiple disks in order to support arbitrary-rate playback requested by different users independently. Our approach is to segment and decluster video objects and to place the segments in multiple disks using a restricted round-robin scheme, called prime round-robin (PRR). Its placement scheme provides uniform load balance of disks for arbitrary retrieval rate as well as normal playback, since it eliminates hot spots. Moreover, it does not require any additional disk bandwidth to support VCR-like operations such as fast-forward and rewind. We have studied the various effects of placement and retrieval schemes in a storage server by simulation. The results show that PRR offers even disk accesses, and the failure in reading segment by deadline occurs only at the beginning of new operations. In addition, the number of users admitted is not decreased, regardless of arbitrary-rate playback requests.     

Design and analysis of a video-on-demand server

The availability of high-speed networks, fast computers and improved storage technology is stimulating interest in the development of video on-demand services that provide facilities similar to a video cassette player (VCP). In this paper, we present a design of a video-on-demand (VOD) server, capable of supporting a large number of video requests with complete functionality of a remote control (as used in VCPs), for each request. In the proposed design, we have used an interleaved storage method with constrained allocation of video and audio blocks on the disk to provide continuous retrieval. Our storage scheme interleaves a movie with itself (while satisfying the constraints on video and audio block allocation. This approach minimizes the starting delay and the buffer requirement at the user end, while ensuring a jitter-free display for every request. In order to minimize the starting delay and to support more non-concurrent requests, we have proposed the use of multiple disks for the same movie. Since a disk needs to hold only one movie, an array of inexpensive disks can be used, which reduces the overall cost of the proposed system. A scheme supported by our disk storage method to provide all the functions of a remote control such as “fast-forwarding”, “rewinding” (with play “on” or “off”), “pause” and “play” has also been discussed. This scheme handles a user request independent of others and satisfies it without degrading the quality of service to other users. The server design presented in this paper achieves the multiple goals of high disk utilization, global buffer optimization, cost-effectiveness and high-quality service to the users.     

Efficient support for interactive service in multi-resolution VOD systems

Advances in high-speed networks and multimedia technologies have made it feasible to provide video-on-demand (VOD) services to users. However, it is still a challenging task to design a cost-effective VOD system that can support a large number of clients (who may have different quality of service (QoS) requirements) and, at the same time, provide different types of VCR functionalities. Although it has been recognized that VCR operations are important functionalities in providing VOD service, techniques proposed in the past for providing VCR operations may require additional system resources, such as extra disk I/O, additional buffer space, as well as network bandwidth. In this paper, we consider the design of a VOD storage server that has the following features: (1) provision of different levels of display resolutions to users who have different QoS requirements, (2) provision of different types of VCR functionalities, such as fast forward and rewind, without imposing additional demand on the system buffer space, I/O bandwidth, and network bandwidth, and (3) guarantees of the load-balancing property across all disks during normal and VCR display periods. The above-mentioned features are especially important because they simplify the design of the buffer space, I/O, and network resource allocation policies of the VOD storage system. The load-balancing property also ensures that no single disk will be the bottleneck of the system. In this paper, we propose data block placement, admission control, and I/O-scheduling algorithms, as well as determine the corresponding buffer space requirements of the proposed VOD storage system. We show that the proposed VOD system can provide VCR and multi-resolution services to the viewing clients and at the same time maintain the load-balancing property. Received June 9, 1998 / Accepted April 26, 1999     

A comprehensive analytical performance model for disk devices underrandom workloads

Our goal is to contribute a common theoretical framework for studying the performance of disk-storage devices. Understanding the performance behavior of these devices will allow prediction of the I/O cost in modern applications. Current disk technologies differ in terms of the fundamental modeling characteristics, which include the magnetic/optical nature, angular and linear velocities, storage capacities, and transfer rates. Angular and linear velocities, storage capacities, and transfer rates are made constant or variable in different existing disk products. Related work in this area has studied Constant Angular Velocity (CAV) magnetic disks and Constant Linear Velocity (CLV) optical disks. We present a comprehensive analytical model, validated through simulations, for the random retrieval performance of disk devices which takes into account all the above-mentioned fundamental characteristics and includes, as special cases, all the known disk-storage devices. Such an analytical model can be used, for example, in the query optimizer of large traditional databases as well as in an admission controller of multimedia storage servers. Besides the known models for magnetic CAV and optical CLV disks, our unifying model is also reducible to a model for a more recent disk technology, called zoned disks, the retrieval performance of which has not been modeled in detail before. The model can also be used to study the performance retrieval of possible future technologies which combine a number of the above characteristics and in environments containing different types of disks (e.g., magnetic-disk-based secondary storage and optical-disk-based tertiary storage). Using our model, we contribute an analysis of the performance behavior of zoned disks and we compare it against that for the traditional CAV disks, as well as against that of some possible/future technologies. This allows us to gain insights into the fundamental performance trade-offs     

Design and analysis of permutation-based pyramid broadcasting

Periodic broadcasting can be used to support near-video-on-demand for popular videos. For a given bandwidth allocation, pyramid broadcasting schemes substantially reduce the viewer latency (waiting) time compared to conventional broadcasting schemes. Nevertheless, such pyramid schemes typically have substantial storage requirements at the client end, and this results in set-top boxes needing disks with high transfer rate capabilities. In this paper, we present a permutation-based pyramid scheme in which the storage requirements and disk transfer rates are greatly reduced, and yet the viewer latency is also smaller. Under the proposed approach, each video is partitioned into contiguous segments of geometrically increasing sizes, and each segment is further divided into blocks, where a block is the basic unit of transmission. As in the original pyramid scheme, frequencies of transmission for the different segments of a video vary in a manner inversely proportional to their size. Instead of transmitting the blocks in each segment in sequential order, the proposed scheme transmits these blocks in a prespecified cyclic permutation to save on storage requirements in the client end. Performance analyses are provided to quantify the benefits of the new scheme.     

Adaptive piggybacking: a novel technique for data sharing in video-on-demand storage servers

Recent technology advances have made multimedia on-demand services, such as home entertainment and home-shopping, important to the consumer market. One of the most challenging aspects of this type of service is providing access either instantaneously or within a small and reasonable latency upon request. We consider improvements in the performance of multimedia storage servers through data sharing between requests for popular objects, assuming that the I/O bandwidth is the critical resource in the system. We discuss a novel approach to data sharing, termed adaptive piggybacking, which can be used to reduce the aggregate I/O demand on the multimedia storage server and thus reduce latency for servicing new requests.     

Using rotational mirrored declustering for replica placement in a disk-array-based video server

In a video-on-demand (VOD) environment, disk arrays are often used to support the disk bandwidth requirement. This can pose serious problems on available disk bandwidth upon disk failure. In this paper, we explore the approach of replicating frequently accessed movies to provide high data bandwidth and fault tolerance required in a disk-array-based video server. An isochronous continuous video stream imposes different requirements from a random access pattern on databases or files. Explicitly, we propose a new replica placement method, called rotational mirrored declustering (RMD), to support high data availability for disk arrays in a VOD environment. In essence, RMD is similar to the conventional mirrored declustering in that replicas are stored in different disk arrays. However, it is different from the latter in that the replica placements in different disk arrays under RMD are properly rotated. Combining the merits of prior chained and mirrored declustering methods, RMD is particularly suitable for storing multiple movie copies to support VOD applications. To assess the performance of RMD, we conduct a series of experiments by emulating the storage and delivery of movies in a VOD system. Our results show that RMD consistently outperforms the conventional methods in terms of load-balancing and fault-tolerance capability after disk failure, and is deemed a viable approach to supporting replica placement in a disk-array-based video server.     

RAID0.5: design and implementation of a low cost disk array data protection method

RAID has long been established as an effective way to provide highly reliable as well as high-performance disk subsystems. However, reliability in RAID systems comes at the cost of extra disks. In this paper, we describe a mechanism that we have termed RAID0.5 that enables striped disks with very high data reliability but low disk cost. We take advantage of the fact that most disk systems use offline backup systems for disaster recovery. With the use of these offline backup systems, the disk system needs to only replicate data since the last backup, thus drastically reducing the storage space requirement. Though RAID0.5 has the same data loss characteristics of traditional mirroring, the lower storage space comes at the cost of lower availability. Thus, RAID0.5 is a tradeoff between lower disk cost and lower availability while still preserving very high data reliability. We present analytical reliability models and experimental results that demonstrate the enhanced reliability and performance of the proposed RAID0.5 system.     

Constructing a video server with tertiary storage: Practice and experience

Handling a tertiary storage device, such as an optical disk library, in the framework of a disk-based stream service model, requires a sophisticated streaming model for the server, and it should consider the device-specific performance characteristics of tertiary storage. This paper discusses the design and implementation of a video server which uses tertiary storage as a source of media archiving. We have carefully designed the streaming mechanism for a server whose key functionalities include stream scheduling, disk caching and admission control. The stream scheduling model incorporates the tertiary media staging into a disk-based scheduling process, and also enhances the utilization of tertiary device bandwidth. The disk caching mechanism manages the limited capacity of the hard disk efficiently to guarantee the availability of media segments on the hard disk. The admission controller provides an adequate mechanism which decides upon the admission of a new request based on the current resource availability of the server. The proposed system has been implemented on a general-purpose operating system and it is fully operational. The design principles of the server are validated with real experiments, and the performance characteristics are analyzed. The results guide us on how servers with tertiary storage should be deployed effectively in a real environment. RID="*" ID="*" e-mail: hjcha@cs.yonsei.ac.kr     

Performability of disk-array-based video servers

Video services are likely to dominate the traffic in future broadband networks. Most of these services will be provided by large- scale public-access video servers. Research to date has shown that disk arrays are a promising technology for providing the storage and throughput required to serve many independent video streams to a large customer population. Large disk arrays, however, are susceptible to disk failures which can greatly affect their reliability. In this paper, we discuss suitable redundancy mechanisms to increase the reliability of disk arrays and compare the performance of the RAID-3 and RAID-5 redundancy schemes. We use cost and performability analyses to rigorously compare the two schemes over a variety of conditions. Accurate cost models are developed and Markov reward models (with time-dependent reward structures) are developed and used to give insight into the tradeoffs between system cost and revenue earning potential. The paper concludes that for large-scale video servers, coarse-grained striping in a RAID-5 style of disk array is most cost effective.     

Integrated document caching and prefetching in storage hierarchies based on Markov-chain predictions

Large multimedia document archives may hold a major fraction of their data in tertiary storage libraries for cost reasons. This paper develops an integrated approach to the vertical data migration between the tertiary, secondary, and primary storage in that it reconciles speculative prefetching, to mask the high latency of the tertiary storage, with the replacement policy of the document caches at the secondary and primary storage level, and also considers the interaction of these policies with the tertiary and secondary storage request scheduling. The integrated migration policy is based on a continuous-time Markov chain model for predicting the expected number of accesses to a document within a specified time horizon. Prefetching is initiated only if that expectation is higher than those of the documents that need to be dropped from secondary storage to free up the necessary space. In addition, the possible resource contention at the tertiary and secondary storage is taken into account by dynamically assessing the response-time benefit of prefetching a document versus the penalty that it would incur on the response time of the pending document requests. The parameters of the continuous-time Markov chain model, the probabilities of co-accessing certain documents and the interaction times between successive accesses, are dynamically estimated and adjusted to evolving workload patterns by keeping online statistics. The integrated policy for vertical data migration has been implemented in a prototype system. The system makes profitable use of the Markov chain model also for the scheduling of volume exchanges in the tertiary storage library. Detailed simulation experiments with Web-server-like synthetic workloads indicate significant gains in terms of client response time. The experiments also show that the overhead of the statistical bookkeeping and the computations for the access predictions is affordable. Received January 1, 1998 / Accepted May 27, 1998     

Constant time permutation: an efficient block allocation strategy for variable-bit-rate continuous media data

To provide high accessibility of continuous-media (CM) data, CM servers generally stripe data across multiple disks. Currently, the most widely used striping scheme for CM data is round-robin permutation (RRP). Unfortunately, when RRP is applied to variable-bit-rate (VBR) CM data, load imbalance across multiple disks occurs, thereby reducing overall system performance. In this paper, the performance of a VBR CM server with RRP is analyzed. In addition, we propose an efficient striping scheme called constant time permutation (CTP), which takes the VBR characteristic into account and obtains a more balanced load than RRP. Analytic models of both RRP and CTP are presented, and the models are verified via trace-driven simulations. Analysis and simulation results show that CTP can substantially increase the number of clients supported, though it might introduce a few seconds/minutes of initial delay. Received June 9, 1998 / Accepted January 21, 1999     

The “Authoring on the Fly” system for automated recording and replay of (tele)presentations

We discuss the problem of capturing media streams which occur during a live lecture in class or during a telepresentation. Instead of presenting yet another method or system for capturing the classroom experience, we introduce some informal guidelines and show their importance for such a system. We derive from these guidelines a formal framework for sets of data streams and an application model to handle these sets so that a real-time replay becomes possible. The Authoring on the Fly system is a possible realization of a framework which follows these guidelines. It allows the capture and real-time replay of data streams captured during a (tele)presentation, including audio, video, and whiteboard action streams. This article gives an overview of the different AoF system components for the various phases of the teaching and learning cycle. It comprises an integrated text and graphics editor for the preparation of pages to be loaded by the whiteboard during the presentation phase. The recording component of the system captures various data streams of the live presentation. They are postprocessed by the system so that they become instances of the class of media for whose replay the general application model was developed. From a global point of view, the Authoring on the Fly system allows one to merge three apparently distinct tasks – teaching in class, telepresentation, and multimedia authoring – into one single activity. The system has been used routinely for recording telepresentations over the MBone net and has already led to a large number of multimedia documents which have been integrated automatically into Web-based teaching and learning environments.     

Data partitioning and load balancing in parallel disk systems

Parallel disk systems provide opportunities for exploiting I/O parallelism in two possible ways, namely via inter-request and intra-request parallelism. In this paper, we discuss the main issues in performance tuning of such systems, namely striping and load balancing, and show their relationship to response time and throughput. We outline the main components of an intelligent, self-reliant file system that aims to optimize striping by taking into account the requirements of the applications, and performs load balancing by judicious file allocation and dynamic redistributions of the data when access patterns change. Our system uses simple but effective heuristics that incur only little overhead. We present performance experiments based on synthetic workloads and real-life traces. Received May 17, 1994 / Accepted June 9, 1997