Dynamic batching policies for an on-demand video server

In a video-on-demand environment, continuous delivery of video streams to the clients is guaranteed by sufficient reserved network and server resources. This leads to a hard limit on the number of streams that a video server can deliver. Multiple client requests for the same video can be served with a single disk I/O stream by sending (multicasting) the same data blocks to multiple clients (with the multicast facility, if present in the system). This is achieved by batching (grouping) requests for the same video that arrive within a short time. We explore the role of customer-waiting time and reneging behavior in selecting the video to be multicast. We show that a first come, first served (FCFS) policy that schedules the video with the longest outstanding request can perform better than the maximum queue length (MQL) policy that chooses the video with the maximum number of outstanding requests. Additionally, multicasting is better exploited by scheduling playback of the most popular videos at predetermined, regular intervals (hence, termed FCFS-). If user reneging can be reduced by guaranteeing that a maximum waiting time will not be exceeded, then performance of FCFS- is further improved by selecting the regular playback intervals as this maximum waiting time. For an empirical workload, we demonstrate a substantial reduction (of the order of 60%) in the required server capacity by batching.     

一种光盘库的短节目调度算法

海量的视频资料可以直接存储在光盘库(或磁带库)等大容量存储设备中，为了提高系统的性能，必须研究有效的调度策略，提出了一种基于光盘库的短节目视频点播系统调度算法——CMF（combined MQL／FCFS)算法。该算法依据等待请求队列的权重来选择所需服务的盘片，并根据节目请求到达率的不同来调整等待队列中请求的等待时间权重，使系统获得效率和公平之间的平衡，仿真结果表明，与MQL和FCFS算法相比，该算法有效减少了用户请求的撤消率，提高了系统的吞吐量。     

VOD系统批处理调度策略优化研究

大规模视频点播（VOD）业务需要消耗大量的网络带宽和服务器资源，基于多点组播的批处理技术允许服务器的不增加额外系统资源的情况下发送相同数据到多个客户端，从而达到系统资源利用率的最大化，通常使用的批处理调度策略有FCFS、MQL和MFQL三种，但是这些方案没有得到令人满意的结果，本文提出一种新策略，称之为MDP，即最大撤销概念，其基本思想是在组空间搜索用户请救撤概率和最大值，MDP以等待服务的所有组中撤销概率的和最大为调度决策依据。保障到达系统的用户因不能忍受等待时间太长而退出的概念最小，通过分析与仿真实验，MDP方案在系统蚕吐量，平均等待时间，用户请求撤销概率和不公平性等系统性能参量方面获得优良结果。     

可提供预约视频点播服务的一种加权入口控制算法

一个视频点播系统需要有大容量的存储空间和高速的输入／输出带宽,在视频点播的高峰时期,经常会出现系统资源供不应求的情况,这就需要有一种策略来决定如何管理用户请求,以及以什么样的顺序为用户提供服务,文中提出了一个新的入口控制算法：WMQL（Weighted Maximal Queue Length)调度,在选择要发送的视频段时,不仅考虑了视频的请求队列长度,还考虑了用户的请求等待时间。接着又提出了一个改进的调度方案：AWMQL（Advanced WMQL)调度,这种调度策略允许用户进行预约,而且尽量在用户的等待容忍度范围内满足用户请求,最后,进行了模拟试验,结果表明,AWMQL调度算法可以有效地增加系统的吞量,同时实现了较好的公平性。     

Design and analysis of a look-ahead scheduling scheme to support pause-resume for video-on-demand applications

In a video-on-demand (VOD) system, subscribers can choose both the movie they wish to view and the time they wish to view it. In such an environment there are invariably hot videos which are requested by many viewers. The requirement that each viewer be able to independently pause the video at any instant and later resume the viewing with little delay can cause difficulties in batching viewers for each showing. Under batching, a single video stream is shared by multiple concurrent viewers and a resume request has to wait for additional stream capacity to become available before actual resumption can occur. The conventional approach to the support of on-demand pause-resume provides one video access stream to disks for each video request. This can greatly increase the disk arm requirements of a VOD system. In this paper, we propose a more efficient mechanism to support the pause-resume feature usinglook-ahead scheduling withlook-aside buffering. The idea is to use buffering to increase the number of concurrent viewers supportable. The concept of look-ahead scheduling is not to back up each viewer with a real stream capacity so he can pause and resume at any time, but rather with a (look-ahead) stream that is currently being used for another showing which is close to completion. Before the look-ahead stream becomes available, the pause and resume features have to be supported by the original stream through (look-aside) buffering of the missed content. It is shown via simulations that the proposed scheme can provide a substantially greater throughput than the approach without batching. Furthermore, for a given amount of buffer, the improvement in throughput grows more than linearly with the stream capacity of the server. In other words, the look-ahead stream scheduling scheme operates with good economy of scale because it is easier to form look-ahead streams for video servers with larger stream capacity.     

Video placement and configuration of distributed video servers on cable TV networks

A large-scale, distributed video-on-demand (VOD) system allows geographically dispersed residential and business users to access video services, such as movies and other multimedia programs or documents on demand from video servers on a high-speed network. In this paper, we first demonstrate through analysis and simulation the need for a hierarchical architecture for the VOD distribution network.We then assume a hierarchical architecture, which fits the existing tree topology used in today's cable TV (CATV) hybrid fiber/coaxial (HFC) distribution networks. We develop a model for the video program placement, configuration, and performance evaluation of such systems. Our approach takes into account the user behavior, the fact that the user requests are transmitted over a shared channel before reaching the video server containing the requested program, the fact that the input/output (I/O) capacity of the video servers is the costlier resource, and finally the communication cost. In addition, our model employs batching of user requests at the video servers. We study the effect of batching on the performance of the video servers and on the quality of service (QoS) delivered to the user, and we contribute dynamic batching policies which improve server utilization, user QoS, and lower the servers' cost. The evaluation is based on an extensive analytical and simulation study.     

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.     

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

Impact of video scheduling on bandwidth allocation for multiplexed MPEG streams

We present efficient schemes for scheduling the delivery of variable-bit-rate MPEG-compressed video with stringent quality-of-service (QoS) requirements. Video scheduling is being used to improve bandwidth allocation at a video server that uses statistical multiplexing to aggregate video streams prior to transporting them over a network. A video stream is modeled using a traffic envelope that provides a deterministic time-varying bound on the bit rate. Because of the periodicity in which frame types in an MPEG stream are typically generated, a simple traffic envelope can be constructed using only five parameters. Using the traffic-envelope model, we show that video sources can be statistically multiplexed with an effective bandwidth that is often less than the source peak rate. Bandwidth gain is achieved without sacrificing the stringency of the requested QoS. The effective bandwidth depends on the arrangement of the multiplexed streams, which is a measure of the lag between the GOP periods of various streams. For homogeneous streams, we give an optimal scheduling scheme for video sources at a video-on-demand server that results in the minimum effective bandwidth. For heterogeneous sources, a sub-optimal scheduling scheme is given, which achieves acceptable bandwidth gain. Numerical examples based on traces of MPEG-coded movies are used to demonstrate the effectiveness of our schemes.     

Providing QOS guarantees for disk I/O

In this paper, we address the problem of providing different levels of performance guarantees or quality of service for disk I/O. We classify disk requests into three categories based on the provided level of service. We propose an integrated scheme that provides different levels of performance guarantees in a single system. We propose and evaluate a mechanism for providing deterministic service for variable-bit-rate streams at the disk. We will show that, through proper admission control and bandwidth allocation, requests in different categories can be ensured of performance guarantees without getting impacted by requests in other categories. We evaluate the impact of scheduling policy decisions on the provided service. We also quantify the improvements in stream throughput possible by using statistical guarantees instead of deterministic guarantees in the context of the proposed approach.     

A buffer-inventory-based dynamic scheduling algorithm for multimedia-on-demand servers

We present a producer-consumer model of multimedia-on-demand (MOD) servers. The producer retrieves media data from a disk and places it into a set of buffers, while the consumer sends out the data in the buffers to the users. We develop for the producer a buffer-inventory-based dynamic scheduling (BIDS) algorithm that guarantees non-zero inventory and non-overflow of data in the buffers to meet the continuity requirement and no-loss of data for each media stream. The algorithm can deal with heterogeneous me dia streams as well as the transient circumstances upon service completions and arrivals of new requests. To smooth out the impact of bursty data of variable-bit-rate media streams and therefore increase the maximum admissible load of requests, we also introduce into the scheduling scheme a time-scale-dependent peak consumption rate and a virtual cycle time. Based on BIDS, an effective admission control mechanism can be easily established by checking two simple conditions respectively on the overall system load and buffer size. Our algorithm is very easy to implement. Experiments carried out with an actual disk system and real video stream data verify that it is more robust compared to static scheduling algorithms previously proposed in the literature, especially when handling variable-bit-rate media streams.     

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.     

一种新的基于补丁优先的流调度算法

通过对现有流调度算法的深入研究,提出了一种新的流媒体调度算法——补丁优先的最大等待队列算法。该算法依据请求等待队列的权重来选择服务队列,使系统获得效率和公平性之间的平衡。理论分析和仿真实验表明:与FCFS、MQL和MPQL算法相比,该算法有效减少了用户请求的撤消率、平均等待时间、不公平性,提高了系统的吞吐量,是一种有效的调度策略。     

A new window-based job scheduling scheme for 2D mesh multicomputers

Allocating submeshes to jobs in mesh-connected multicomputers in a FCFS fashion can lead to poor system performance (e.g., long job waiting delays) because the job at the head of the waiting queue can prevent the allocation of free submeshes to other waiting jobs with smaller submesh requirements. However, serving jobs aggressively out-of-order can lead to excessive waiting delays for jobs with large allocation requests. In this paper, we propose a scheduling scheme that uses a window of consecutive jobs from which it selects jobs for allocation and execution. This window starts with the current oldest waiting job and corresponds to the lookahead of the scheduler. The performance of the proposed window-based scheme has been compared to that of FCFS and other previous job scheduling schemes. Extensive simulation results based on synthetic workloads and real workload traces indicate that the new scheduling strategy exhibits good performance when the scheduling window size is large. In particular, it is substantially superior to FCFS in terms of system utilization, average job turnaround times, and maximum waiting delays under medium to heavy system loads. Also, it is superior to aggressive out-of-order scheduling in terms of maximum job waiting delays. Window-based job scheduling can improve both overall system performance and fairness (i.e., maximum job waiting delays) by adopting large lookahead job scheduling windows.     

A pricing mechanism for scalable video delivery

Many video applications tolerate continuous media (CM) scaling. Scaling is acceptable due to human tolerance to degradation in picture quality, frame loss, and end-to-end delay. CM scaling enables the network to utilize its resources efficiently for supporting additional customers and to increase its revenue. However, due to quality degradation, users will not be willing to tolerate scaling unless it is coupled with monetary or availability incentives. We propose a pricing policy and a corresponding admission control scheme for scalable video applications. The pricing policy is two-tiered, based on a connection set-up component and a scalable component. Connections that are more scalable are charged less, but are more liable to be degraded. The proposed policy trades off performance degradation with monetary incentives to improve user benefit and network revenue and to decrease the blocking probability of connection requests. We demonstrate by means of simulation that this policy encourages users to specify the scalability of an application to the network.     

Buffer-Sharing Techniques in Service-Guaranteed Video Servers

Advances in networking and storage technology have made it possible to deliver on-demand services over networks such as the emerging video-on- demand (VOD) applications. Although a variety of studies have been focused on designing video servers suitable for VOD applications, the number of concurrent on-demand services supported by such servers is often limited by the I/O bandwidth of the storage systems. Recently, several researchers have focused on providing guaranteed services instead of on-demand services in a VOD system. A service is said to be guaranteed if every viewer can be served within a specified waiting time after the video has been subscribed. This paper describes a model called a buffer-sharing autonomy, which combines batching and bridging techniques to provide guaranteed services to VOD systems. We also describe how buffer-sharing techniques can be used in this model to provide the same services with fewer buffer resource through the use of playback-rate alteration. Additionally, in order to make buffer sharing efficient, it is important to group appropriate video streams together to share buffer resource. Four grouping policies are proposed for this purpose and the benefits yielded are also analyzed and compared. Finally, the results of our experiments show that the proposed buffer-sharing techniques promise the provision of guaranteed video services at low cost.     

云环境下蚁群优化算法的视频点播视频流任务调度策略

针对云环境下大规模并发视频流调度过程中资源利用率低和负载不均的问题,提出一种基于蚁群优化(ACO)算法的视频点播(VOD)集群视频流任务调度策略VodAco。在分析视频流期望性能与服务器空闲性能的相关性、定义综合性能匹配度的基础上,建立数学模型,并采用蚁群优化思路进行最佳调度方案搜索。通过云仿真软件CloudSim实验表明,与轮询(RR)、贪婪(Greedy)算法相比,所提算法在任务完成时间、平台资源占有率、各节点性能负载均衡指标上具有较为明显的优势。     

Wavelet-based video indexing and querying

We present several algorithms suitable for analysis of broadcast video. First, we show how wavelet analysis of frames of video can be used to detect transitions between shots in a video stream, thereby dividing the stream into segments. Next we describe how each segment can be inserted into a video database using an indexing scheme that involves a wavelet-based “signature.” Finally, we show that during a subsequent broadcast of a similar or identical video clip, the segment can be found in the database by quickly searching for the relevant signature. The method is robust against noise and typical variations in the video stream, even global changes in brightness that can fool histogram-based techniques. In the paper, we compare experimentally our shot transition mechanism to a color histogram implementation, and also evaluate the effectiveness of our database-searching scheme. Our algorithms are very efficient and run in realtime on a desktop computer. We describe how this technology could be employed to construct a “smart VCR” that was capable of alerting the viewer to the beginning of a specific program or identifying