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.     

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 operations in multi-resolution video servers

In this paper, we present a placement algorithm that interleaves multi-resolution video streams on a disk array and enables a video server to efficiently support playback of these streams at different resolution levels. We then combine this placement algorithm with a scalable compression technique to efficiently support interactive scan operations (i.e., fast-forward and rewind). We present an analytical model for evaluating the impact of the scan operations on the performance of disk-arr ay-based servers. Our experiments demonstrate that: (1) employing our placement algorithm substantially reduces seek and rotational latency overhead during playback, and (2) exploiting the characteristics of video streams and human perceptual tolerances enables a server to support interactive scan operations without any additional overhead.     

A Design Framework for Multi-Resolution Video Servers

Video can be encoded into multiple-resolution format in nature. A multi-resolution or scalable video stream is a video sequence encoded such that subsets of the full resolution video bit stream can be decoded to recreate lower resolution video streams. Employing scalable video enables a video server to provide multiple resolution services for a variety of clients with different decoding capabilities and network bandwidths connected to the server. The inherent advantages of the multi-resolution video server include: heterogeneous client support, storage efficiency, adaptable service, and interactive operations support.For designing a video server, several issues should be dealt with under a unified framework including data placement/retrieval, buffer management, and admission control schemes for deterministic service guarantee. In this paper, we present a general framework for designing a large-scale multi-resolution video server. First, we propose a general multi-resolution video stream model which can be implemented by various scalable compression techniques. Second, given the proposed stream model, we devise a hybrid data placement scheme to store scalable video data across disks in the server. The scheme exploits both concurrency and parallelism offered by striping data across the disks and achieves the disk load balancing during any resolution video service. Next, the retrieval of multi-resolution video is described. The deterministic access property of the placement scheme permits the retrieval scheduling to be performed on each disk independently and to support interactive operations (e.g. pause, resume, slow playback, fastforward and rewind) simply by reconstructing the input parameters to the scheduler. We also present an efficient admission control algorithm which precisely estimates the actual disk workload for the given resolution services and hence permits the buffer requirement to be much smaller. The proposed schemes are verified through detailed simulation and implementation.     

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.     

Storage System for Supporting More Video Streams in Video Server

Video server needs a storage system with large bandwidth in order to provide concurrently more users with the real time retrieval requests for video streams. So, the storage system generally has the structure of disk array, which consists of multiple disks. When the storage system serves multiple video stream requests, it's bottlenecks come from the seeking delay caused by the random movement of disk head and from unbalanced disk access due to disk load unbalance among multiple disks.This paper presents a novel placement and retrieval policy. The new policy retrieves the requested data through sequential movement of disk heads and maintaining disk load balance so that it can diminish the bottlenecks on retrieving and can provide the concurrent real time retrieval services for more users simultaneously. In addition, the novel policy reduces the startup latency for the requests. The correctness of the novel placement and retrieval policy is analyzed with theoretical views. Performance analysis of the novel placement and retrieval policy is provided with simulations.     

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.     

Improving multimedia systems performance using constant-density recording disks

Multimedia systems store and retrieve large amounts of data which require extremely high disk bandwidth and their performance critically depends on the efficiency of disk storage. However, existing magnetic disks are designed for small amounts of data retrievals geared to traditional operations; with speed improvements mainly focused on how to reduce seek time and rotational latency. When the same mechanism is applied to multimedia systems, overheads in disk I/O can result in dramatic deterioration in system performance. In this paper, we present a mathematical model to evaluate the performance of constant-density recording disks, and use this model to analyze quantitatively the performance of multimedia data request streams. We show that high disk throughput may be achieved by suitably adjusting the relevant parameters. In addition to demonstrating quantitatively that constant-density recording disks perform significantly better than traditional disks for multimedia data storage, a novel disk-partitioning scheme which places data according to their bandwidths is presented.     

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.     

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     

Data Management for Multiuser Access to Digital Video Libraries

To support heterogeneous application types a video digital library will contain a large number of video objects with various lengths and display requirements. Multiuser access to the same video objects is required in order to increase the availability of video information and to make full use of the limited computing and storage resources. The access frequency and delay sensitivity of video objects require special methods to guarantee smooth playback of video objects and to minimize average waiting time. We propose an integrated approach to buffer and disk management for dynamic loading and simultaneous delivery of multiple video objects to multiple users. The allocation of buffer and disk resources in this study is based on quality of service variables such as average waiting time, display continuity, and viewer enrollment.     

I/O scheduling for digital continuous media

A growing set of applications require access to digital video and audio. In order to provide playback of such continuous media (CM), scheduling strategies for CM data servers (CMS) are necessary. In some domains, particularly defense and industrial process control, the timing requirements of these applications are strict and essential to their correct operation. In this paper we develop a scheduling strategy for multiple access to a CMS such that the timing guarantees are maintained at all times. First, we develop a scheduling strategy for the steady state, i.e., when there are no changes in playback rate or operation. We derive an optimal Batched SCAN (BSCAN) algorithm that requires minimum buffer space to schedule concurrent accesses. The scheduling strategy incorporates two key constraints: (1) data fetches from the storage system are assumed to be in integral multiples of the block size, and (2) playback guarantees are ensured for frame-oriented streams when each frame can span multiple blocks. We discuss modifications to the scheduling strategy to handle compressed data like motion-JPEG and MPEG. Second, we develop techniques to handle dynamic changes brought about by VCR-like operations executed by applications. We define a suite of primitive VCR-like operations that can be executed. We show that an unregulated change in the BSCAN schedule, in response to VCR-like operations, will affect playback guarantees. We develop two general techniques to ensure playback guarantees while responding to VCR-like operations: passive and active accumulation. Using user response time as a metric we show that active accumulation algorithms outperform passive accumulation algorithms. An optimal response-time algorithm in a class of active accumulation strategies is derived. The results presented here are validated by extensive simulation studies.     

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.     

A scalable storage supporting multistream real-time data retrieval

This paper presents a new data placement scheme for continuous-media playback via a scalable storage system. Multimedia contents are segmented into data blocks for the purpose of being stored, retrieved, and manipulated. If these data blocks belong to some continuous media, then they must be handled in a timely manner, for example, being retrieved before some deadline. One of the main challenges in implementing the above system is the simultaneous retrieval of a great number of different media streams from a very large storage system. The proposed scheme efficiently reduces the seeking delay by a very simple placement method and a retrieval scheduler. Thus, both the storage capacity and the number of concurrent accesses to the storage are scalable. The performance of the proposed scheme is evaluated through a simple analytical model and a practical prototype implementation.     

{\cal SMDP}: minimizing buffer requirements for continuous media servers

Excessive buffer requirement to handle continuous-media playbacks is an impediment to cost- effective provisioning for on-line video retrieval. Given the skewed distribution of video popularity, it is expected that often there are concurrent playbacks of the same video file within a short time interval. This creates an opportunity to batch multiple requests and to service them with a single stream from the disk without violating the on-demand constraint. However, there is a need to keep data in memory between successive uses to do this. This leads to a buffer space trade-off between servicing a request in memory mode vs. servicing it in disk-mode. In this work, we develop a novel algorithm to minimize the buffer requirement to support a set of concurrent playbacks. One of the beauties of the proposed scheme is that it enables the server to dynamically adapt to the changing workload while minimizing the total buffer space requirement. Our algorithm makes a significant contribution in decreasing the total buffer requirement, especially when the user access pattern is biased in favor of a small set of files. The idea of the proposed scheme is modeled in detail using an analytical formulation, and optimality of the algorithm is proved. An analytical framework is developed so that the proposed scheme can be used in combination with various existing disk-scheduling strategies. Our simulation results confirm that under certain circumstances, it is much more resource efficient to support some of the playbacks in memory mode and subsequently the proposed scheme enables the server to minimize the overall buffer space requirement.     

Efficient video file allocation schemes for video-on-demand services

A video-on-demand (VOD) server needs to store hundreds of movie titles and to support thousands of concurrent accesses. This, technically and economically, imposes a great challenge on the design of the disk storage subsystem of a VOD server. Due to different demands for different movie titles, the numbers of concurrent accesses to each movie can differ a lot. We define access profile as the number of concurrent accesses to each movie title that should be supported by a VOD server. The access profile is derived based on the popularity of each movie title and thus serves as a major design goal for the disk storage subsystem. Since some popular (hot) movie titles may be concurrently accessed by hundreds of users and a current high-end magnetic disk array (disk) can only support tens of concurrent accesses, it is necessary to replicate and/or stripe the hot movie files over multiple disk arrays. The consequence of replication and striping of hot movie titles is the potential increase on the required number of disk arrays. Therefore, how to replicate, stripe, and place the movie files over a minimum number of magnetic disk arrays such that a given access profile can be supported is an important problem. In this paper, we formulate the problem of the video file allocation over disk arrays, demonstrate that it is a NP-hard problem, and present some heuristic algorithms to find the near-optimal solutions. The result of this study can be applied to the design of the storage subsystem of a VOD server to economically minimize the cost or to maximize the utilization of disk arrays.     

Synchronized delivery and playout of distributed stored multimedia streams

Multimedia streams such as audio and video impose tight temporal constraints for their presentation. Often, related multimedia streams, such as audio and video, must be presented in a synchronized way. We introduce a novel scheme to ensure the continuous and synchronous delivery of distributed stored multimedia streams across a communications network. We propose a new protocol for synchronized playback and compute the buffer required to achieve both, the continuity within a single substream and the synchronization between related substreams. The scheme is very general and does not require synchronized clocks. Using a resynchronization protocol based on buffer level control, the scheme is able to cope with server drop-outs and clock drift. The synchronization scheme has been implemented and the paper concludes with our experimental results.     

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.     

Increasing multimedia system throughput with consumption-based buffer management

In a multimedia server, multiple media streams are generally serviced in a cyclic fashion. Due to non-uniform playback rates and asynchronous arrivals of queries, there tends to be spare disk bandwidth in each service cycle. In this paper, we study the issue of dynamically using spare disk bandwidth and buffer to maximize the system throughput of a multimedia server. We introduce the concept of minimizing buffer consumption as the criterion to select an appropriate media stream to utilize the spare system resources. Buffer consumption measures not only the amount of buffer but also the amount of time such buffer space is occupied (i.e., the space-time product). Different alternatives to utilizing spare disk bandwidth are examined, including different rate-adjustable retrievals of an already activated stream and prefetching the next waiting stream. For rate-adjustable retrievals, we study buffer consumption-based and remaining-time-based criteria for selecting an active stream to increase retrievals. Simulations are conducted to evaluate and compare different cases. The results show that (1) minimizing buffer consumption is the right criterion for maximizing the system throughput with spare disk bandwidth; (2) in general, prefetching a waiting stream incurs more buffer consumption, and thus is less effective than rate-adjustable retrieval of active streams in maximizing the system throughput; and (3) the advantage of rate-adjustable retrieval over prefetching is especially significant when service cycle time is small.     

Zodiac: A history-based interactive video authoring system

Easy-to-use audio/video authoring tools play a crucial role in moving multimedia software from research curiosity to mainstream applications. However, research in multimedia authoring systems has rarely been documented in the literature. This paper describes the design and implementation of an interactive video authoring system called Zodiac, which employs an innovative edit history abstraction to support several unique editing features not found in existing commercial and research video editing systems. Zodiac provides users a conceptually clean and semantically powerful branching history model of edit operations to organize the authoring process, and to navigate among versions of authored documents. In addition, by analyzing the edit history, Zodiac is able to reliably detect a composed video stream's shot and scene boundaries, which facilitates interactive video browsing. Zodiac also features a video object annotation capability that allows users to associate annotations to moving objects in a video sequence. The annotations themselves could be text, image, audio, or video. Zodiac is built on top of MMFS, a file system specifically designed for interactive multimedia development environments, and implements an internal buffer manager that supports transparent lossless compression/decompression. Shot/scene detection, video object annotation, and buffer management all exploit the edit history information for performance optimization.