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.     

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.     

Merging video streams in a multimedia storage server: complexity and heuristics

Due to recent advances in network, storage and data compression technologies, video-on-demand (VOD) service has become economically feasible. It is a challenging task to design a video storage server that can efficiently service a large number of concurrent requests on demand. One approach to accomplishing this task is to reduce the I/O demand to the VOD server through data- and resource-sharing techniques. One form of data sharing is the stream-merging approach proposed in [5]. In this paper, we formalize a static version of the stream-merging problem, derive an upper bound on the I/O demand of static stream merging, and propose efficient heuristic algorithms for both static and dynamic versions of the stream-merging problem.     

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.     

Dynamic real-time scheduling strategies for interactive continuous media servers

In this paper, we propose and study a dynamic approach to schedule real-time requests in a video-on-demand (VOD) server. Providing quality of service in such servers requires uninterrupted and on-time retrieval of motion video data. VOD services and multimedia applications further require access to the storage devices to be shared among multiple concurrent streams. Most of the previous VOD scheduling approaches use limited run-time,0 information and thus cannot exploit the potential capacity of the system fully. Our approach improves throughput by making use of run-time information to relax admission control. It maintains excellent quality of service under varying playout rates by observing deadlines and by reallocating resources to guarantee continuous service. It also reduces start-up latency by beginning service as soon as it is detected that deadlines of all real-time requests will be met. We establish safe conditions for greedy admission, dynamic control of disk read sizes, fast initial service, and sporadic services. We conduct thorough simulations over a wide range of buffer capacities, load settings, and over varying playout rates to demonstrate the significant improvements in quality of service, throughput and start-up latency of our approach relative to a static approach.     

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.     

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     

Performance of a Mass-Storage System for Video-on-Demand

Advancements in storage technology along with the fast deployment of high-speed networks has allowed the storage, transmission, and manipulation of multimedia information such as text, graphics, still images, video, and audio to be feasible. Our study focused on the performance of the mass storage system for a large-scale video-on-demand server. Different video file striping schemes, such as application level striping and device driver level striping, were examined in order to study scalability and performance issues. To study the impact of different concurrent access patterns on the performance of a server, experimental results were obtained on group access on a single video file and multiple group accesses on multiple video files. All of our experiments were conducted on a fully configured Silicon Graphics Inc. Onyx computer system. The Onyx machine was connected to 31 SCSI-2 channels which have 496 GBytes disk storage, 20 MIPS R4400 processors, and 768 MBytes main memory. From the experimental results, the storage system of Onyx machine can potentially provide about 360 concurrent video accesses with guaranteed quality of service.     

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.     

{\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.     

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     

Design and evaluation of a generic software architecture foron-demand video servers

Introduces the design, implementation and evaluation of a generic software architecture for on-demand video servers. We describe different key components for controlling the storage and network devices within the server. The interactive collaborations between these software components are also illustrated. The experimental results indicate a very promising direction in exploring the right combinations of these software components. The server is thus able to increase the number of concurrent video accesses with the same hardware configuration. For instance, with the right combinations, the system achieved about 80% of the storage system bandwidth of four disks, about 70% of the storage system bandwidth of six disks, and generally reached the maximal achieved SCSI bandwidth when eight disks are used over two SCSI buses. Our research and experimental results are based on video servers currently under construction across a variety of hardware platforms, including SMP, DMP and clusters of PCs or workstations. The most advanced prototype server is based on an SGI shared-memory multiprocessor with a mass storage system consisting of RAID-3 disk arrays. With all the enabling/management schemes, we were able to further investigate interesting research issues by considering the user's access profiles for taking advantage of popular video titles. The results were significant, with a range of 60% improvement given a 512 kByte block size. In addition to the experimental results, theoretical performance models were also developed that closely match to our collected experimental results     

连续媒体服务器存储系统中的容错算法

连续媒体服务器(如VOD服务器)要对大量连续媒体数据(如声频、视频)进行管理,按一定速率为用户提供连续的媒体服务。因此,在这样的系统中,作为存储设备的磁盘阵列要具有高可靠性和一定的容错能力。文章提出一种基于奇偶检验的数据重构恢复算法,以保证系统中只有一个盘出现故障时,能使服务器及时重构出故障盘上的数据,并且算法充分利用了媒体流内在特性———回放时数据的连续性,与目前使用的标准故障恢复算法相比,大大减少了磁盘在线故障后数据重构过程的系统开销。最后通过分析、比较证明了算法的有效性。     

大规模层次化视频点播存储系统的设计与管理

近来计算机和通信技术的发展使得视频点播（video-on-demand,简称VOD)在技术和经济上成为可能.连续媒体的特性使得VOD系统需要大规模的存储服务器.层次化存储体系是减少系统费用的合理方案.文章提出了一种层次化的存储模型和磁盘cache的概念.根据这个模型,提出了基于访问频率的替换算法,并对算法的有效性进行了模拟和分析.结果表明,这种算法解决了LFU(least frequently used)算法中的“cache污染”（cache pollution）问题,能较好地适用于连续媒体数据应用.     

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.     

Efficient support for interactive scanning operations in MPEG-based video-on-demand systems

In this paper, we present an efficient approach for supporting fast-scanning (FS) operations in MPEG-based video-on-demand (VOD) systems. This approach is based on storing multiple, differently encoded versions of the same movie at the server. A normal version is used for normal playback, while several scan versions are used for FS. Each scan version supports forward and backward FS at a given speedup. The server responds to an FS request by switching from the normal version to an appropriate scan version. Scanning versions are produced by encoding a sample of the raw frames using the same GOP pattern of the normal version. When a scanning version is decoded and played back at the normal frame rate, it gives a perceptual motion speedup. By being able to control the traffic envelopes of the scan versions, our approach can be integrated into a previously proposed framework for distributing archived, MPEG-coded video streams. FS operations are supported using no or little extra network bandwidth beyond what is already allocated for normal playback. Mechanisms for controlling the traffic envelopes of the scan versions are presented. The actions taken by the server and the client's decoder in response to various types of interactive requests are described in detail. The latency incurred in implementing various interactive requests is shown to be within an acceptable range. Striping and disk-scheduling strategies for storing various versions at the server are presented. Issues related to the implementation of our approach are discussed.     

Delivery of compressed videos from video servers employing cycle-based data-block retrieval discipline

The significant frame size variability exhibited in the compressed videos imposes a great challenge on network delivery. In this paper we propose an efficient flow control scheme, employed in the peer stations (i.e., servers and clients), for delivery of prestored compressed videos in a video-on-demand (VOD) system. This scheme resorts to an off-line analysis on the video frame sizes and server properties for figuring out the necessary buffer space and network bandwidth. The server platform of particular interest obeys a cycle-based data-block retrieval discipline, which is an essential technique to reduce the disk seek time for leveraging the disk throughput for supporting a large number of concurrent video accesses. Such a discipline is taken into account here to guarantee smooth delivery of variable-bit-rate videos. In run-time a server-driven control model is in use, where a server performs the primary flow control task, without relying on any feedback from clients. The scheme has been implemented in our prototype VOD system to support both unicast- and multicast communication paradigms under an RSVP-enabled network.     

3TNet视频点播中内容分发策略设计与实现

在3TNet视频点播系统中,为了保障IP网中视频点播服务的QoS,在媒体服务器和内容服务器之间引入了内容分发平台,用来缓存内容服务器的一部分影片数据,因此内容分发平台中的调度策略直接关系到数据块的命中率和内容服务器的性能。论文提出了一种基于预测的新的调度策略,该策略能很好地提高热门影片的命中率。     

An experimental analysis of digital video library servers

Much work on video servers has concentrated on movies on demand, in which a relatively small number of titles are viewed and users are given basic VCR-style controls. This paper concentrates on analyzing video server performance for non-linear access applications. In particular, we study two non-linear video applications: video libraries, in which users select from a large collection of videos and may be interested in viewing only a small part of the title; and video walk-throughs, in which users can move through an image-mapped representation of a space. We present a characterization of the workloads of these applications. Our simulation studies show that video server architectures developed for movies on demand can be adapted to video library usage, though caching is less effective and the server can support a smaller user population for non-linear video applications. We also show that video walk-throughs require extremely large amounts of RAM buffering to provide adequate performance for even a small number of users.     

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