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.     

一种新颖的带模糊截止时限的磁盘调度算法

设计了一种新的基于截止时限的磁盘调度算法,该算法支持带多优先级的请求。对于某些实时要求,其截止时限是不确定的或者不精确的,该算法采用模糊集来描述这类不确定性,模糊截止时限的隶属度函数表示对请求完成时间的满意程度。调度的目的是最优的指定优先级,使得截止时限的满意程度最大化。根据请求截止时限的不同,把满意程度划分为若干连续的区间。在每个不同的区间内,每个请求都对应有修正的截止时限,把请求按照其修正的截止时限非减的顺序分配优先级,才能实现请求优先级的最优配置。仿真结果表明该算法能有效的分配请求的优先级,降低请求的丢失率,保证了更多的请求得到满足。     

本地无数据的iSCSI磁盘数据保护机制

在信息窃取者合法登录系统的情况下,现有的Internet小型计算机系统接口（iSCSI）磁盘数据保护措施并不能保证数据不被窃取。通过结合磁盘读写重定向算法、磁盘透明加解密机制,提出一种本地无数据的iSCSI磁盘数据保护机制iSCSI_SEC。本地无数据指的是iSCSI磁盘中的重要数据只会存在于iSCSI磁盘服务器中而不会因为用户操作或者程序拷贝等原因在本地存储介质上存在,从而能够保证磁盘中重要数据的机密性。通过在系统内核层加载磁盘过滤驱动程序的方式来实现数据保护机制,并与TrueCrypt进行磁盘读写性能对比,实验结果显示iSCSI_SEC使磁盘读、写性能下降幅度小于TrueCrypt。结果表明,iSCSI_SEC不仅能够保证iSCSI磁盘数据的机密性,并且在iSCSI磁盘环境下比TrueCrypt有更好的性能表现。     

Fault detection for Byzantine quorum systems

In this paper, we explore techniques to detect Byzantine server failures in asynchronous replicated data services. Our goal is to detect arbitrary failures of data servers in a system where each client accesses the replicated data at only a subset (quorum) of servers in each operation. In such a system, some correct servers can be out-of-date after a write and can therefore, return values other than the most up-to-date value in response to a client's read request, thus complicating the task of determining the number of faulty servers in the system at any point in time. We initiate the study of detecting server failures in this context, and propose two statistical approaches for estimating the risk posed by faulty servers based on responses to read requests     

Evaluating video layout strategies for a high-performance storage server

We propose a systems approach to providing video service that integrates the multiresolution data generated by scalable compression algorithms with the high-bandwidth, high-capacity storage provided by disk arrays. We introduce two layout strategies for storing multiresolution video data on magnetic disk arrays, which vary in the degrees of parallelism and concurrency they use to satisfy requests. Our simulation results show that the storage of multiple video resolutions allows a video file server to satisfy considerably more user requests than a server that stores a single resolution of video data.     

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.     

影响多媒体服务器性能的关键因素研究

在构建大规模视频服务系统时 ,基于层次型多服务器群的体系结构在吞吐率、可扩展性、经济性等方面都有其突出的优势 ,尤其适合于在因特网上的应用 .但是 ,要充分发挥和提高视频服务系统的性能 ,还要针对一些主要的瓶颈(如服务器磁盘 I/ O带宽与网络带宽 ) ,解决好一系列的问题 .本文分析了影响多媒体视频服务器性能的一些主要因素 ,如视频服务器的体系结构、服务器与客户端之间的数据传送方式、媒体数据在视频服务器存储子系统中的分布与放置方式、对磁盘访问请求的调度、单服务器中的缓存及多服务器间协同缓存的管理、接入控制策略、流调度策略等 ,这些因素对视频服务器的性能与吞吐率有着极大的影响 .本文还介绍了一些适用于大规模视频服务系统的性能优化技术 ,如广播、批处理等流调度策略 .在构建视频服务器系统时 ,只有综合考虑这些因素 ,才能真正提高服务器乃至整个视频服务系统的吞吐率 ,并较好地满足客户的 Qo S要求     

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.     

基于Nginx负载均衡的动态改进算法

随着过去几十年互联网服务的指数增长,各大网站的访问量急剧上升。海量的用户请求使得热门网站的网络请求率可能在几秒钟内大规模增加。一旦服务器承受不住这样的高并发请求,由此带来的网络拥塞和延迟会极大地影响用户体验。负载均衡是高可用网络基础架构的关键组件,通过在后端引入一个负载均衡器,将工作负载分布到多个服务器来缓解海量并发请求对服务器造成的巨大压力,提高后端服务器和数据库的性能以及可靠性。而Nginx作为一款高性能的HTTP和反向代理服务器,正越来越多地应用到实践中。文中将分析Nginx服务器负载均衡的体系架构,研究默认的加权轮询算法,并提出一种改进后的动态负载均衡算法,实时收集负载信息,重新计算并分配权值。通过实验测试,对比不同算法下的负载均衡性能,改进后的算法能有效提高服务器集群的性能。     

Performance Comparison of Mirrored Disk Scheduling Methods with a Shared Non-Volatile Cache

Mirrored disks or RAID1 is a popular disk array paradigm, which in addition to fault-tolerance, doubles the data access bandwidth. This is important in view of rapidly increasing disk capacities and the slow improvement in disk access time. Caching of dirty data blocks in a non-volatile storage (NVS) cache allows the destaging of dirty blocks to be deferrable, so as to improve the response time of read requests by giving them a higher priority than write requests. Destaging of dirty blocks in batches to take advantage of disk geometry entails in lowered disk utilization due to writes and improved performance for reads. Polyzois et al. [12] propose a scheduling policy for mirrored disks equipped with an NVS cache, so that one disk processes read requests, while the other disk is processing a write batch according to the CSCAN policy. We propose an improved scheduling policy as follows: (i) eliminating the forced idleness caused by the batch processing paradigm for write requests, i.e., allowing write requests to be processed individually; (ii) using SATF or even an exhaustive search, to reduce destaging time compared to CSCAN; (iii) introducing a threshold for the number of read requests, which when exceeded defers the destaging of dirty blocks. We compare these two scheduling policies with each other and also against prioritizing the processing of reads versus writes: (i) the head-of-the-line (HOL) priority queueing discipline, (ii) SATF with conditional priorities. It follows from simulation results that the new method outperforms Polyzois' method, which is even outperformed by the HOL priority policy. SATF with conditional priorities slightly outperforms the proposed method from the viewpoint of its throughput and response time, but is susceptible to more variability in response time. Recommended by: Ahmed Elmagarmid     

Dynamic Buffer Management for Near Video-On-Demand Systems

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. A variety of studies have been focused on designing a video server suitable for VOD applications. However, the number of concurrent on-demand services supported by the server is often limited by the I/O bandwidth of the storage systems. This paper describes a discrete buffer sharing model which uses batching and buffer sharing techniques in video servers to support a large number of VOD services. Two operations, splitting and merging, enable the model to fully utilize system resources such as buffers and disk bandwidths. Moreover, this paper also introduces the concept of imprecise video viewing which assumes that a limited amount of quality loss is acceptable during video playback. Based upon this assumption, three shrinking strategies are explored to reduce buffer requirements. Finally, the results of experiments show that our methods perform better than traditional buffer management techniques for VOD systems.     

视频服务器中多网络I/O的调度与接纳控制

在视频服务器中,由于网络I/O带宽比磁盘I/O带宽相对丰富而未得到研究者的重视,但当服务达到一定的规模、网络输出成为瓶颈时,在多网络I/O情况下,网络输出的量化计算则不可避免.着重探讨了视频服务器在多网络I/O并行输出的情况下,如何进行最大输出调度的问题,给出了3个调度算法及相应的接纳计算公式,特别是一个带缓冲的优化调度模型.实验结果显示,调度模型及规划性能是优越而有效的.该项工作对视频服务器的调度设计、资源的有效配置具有指导作用.     

Handling Updates and Crashes in VoD Systems

Though there have been several recent efforts to develop disk based video servers, these approaches have all ignored the topic of updates and disk server crashes. In this paper, we present a priority based model for building video servers that handle two classes of events: user events that could include enter, play, pause, rewind, fast-forward, exit, as well assystem events such as insert, delete, server-down, server-up that correspond to uploading new movie blocks onto the disk(s), eliminating existing blocks from the disk(s), and/or experiencing a disk server crash. We will present algorithms to handle such events. Our algorithms are provably correct, and computable in polynomial time. Furthermore, we guarantee that under certain reasonable conditions, continuing clients experience jitter free presentations. We further justify the efficiency of our techniques with a prototype implementation and experimental results.     

A new real time disk-scheduling method based on GSR algorithm

Disk scheduling has an important role in QOS guarantee of soft real-time environments such as video-on-demand and multimedia servers. Since now, some disk-scheduling algorithms have been proposed to schedule real-time disk requests. One of the most recent algorithms is global seek-optimizing real-time (GSR) that schedules the disk requests with different ready times by a global regrouping scheme. In the present paper, we propose a real-time disk-scheduling algorithm based on GSR that is called IGSR (improved GSR). IGSR creates the scan-groups of the requests and tries to find a good feasible schedule by optimized grouping with considering another chance for tasks that miss their deadlines at initial grouping. With regard to the admission policy of tasks, two different version of proposed method are presented: the first one has been designed for the case that all the disk requests available simultaneously and second one has been designed for the case that requests are admitted dynamically (GSR does not support the second one). It means that in the second case, the request queue may change when a task is running but in the first one it does not change. Simulation results showed IGSR outperformed GSR and some other related works in terms of maximum supportable streams, number of missed deadlines, and disk throughput.     

Tulip: A New Hash Based Cooperative Web Caching Architecture

With the exponential growth of WWW traffic, web proxy caching becomes a critical technique for Internet web services. Well-organized proxy caching systems with multiple servers can greatly reduce the user perceived latency and decrease the network bandwidth consumption. Thus, many research papers focused on improving web caching performance with the efficient coordination algorithms among multiple servers. Hash based algorithm is the most widely used server coordination mechanism, however, there's still a lot of technical issues need to be addressed. In this paper, we propose a new hash based web caching architecture, Tulip. Tulip aggregates web objects that are likely to be accessed together into object clusters and uses object clusters as the primary access units. Tulip extends the locality-based algorithm in UCFS to hash based web proxy systems and proposes a simple algorithm to reduce the data grouping overhead. It takes into consideration the access speed dispatch between memory and disk and replaces expensive small disk I/O with less large ones. In case a client request cannot be fulfilled by the server in the memory, the system fetches the whole cluster which contains the required object into memory, the future requests for other objects in the same cluster can be satisfied directly from memory and slow disk I/Os are avoided. It also introduces a simple and efficient data dupllication algorithm, few maintenance work need to be done in case of server join/leave or server failure. Along with the local caching strategy, Tulip achieves better fault tolerance and load balance capability with the minimal cost. Our simulation results show Tulip has better performance than previous approaches.     

Arrangement of multi-dimensional scalable video data for heterogeneous clients

A scalable video server extracts data corresponding to the resolution requested by its client from the total data containing the information encoding a full resolution video. Depending on the requested resolution, the extracted data may not be contiguously placed on a disk or a disk array. For this reason, the traverse distance, which indicates the difference between the first read position and the last read position, can be much larger than the amount of the requested data. This causes additional rotational latency in a disk and thus degrades disk performance. Furthermore, scalable video data more seriously deteriorates the independency of disks in a disk array. That is, even a small read request can be split into multiple disk requests across disks of a disk array, because the requested data are scattered across multiple disks. To address these problems, we propose new data arrangement schemes for scalable video data. In these new schemes, we first deal with the arrangement of multi-dimensional scalable video data, which can be employed regardless of the number of scalability dimensions. Second, we improve disk performance by reducing average disk cost, which is based on both the traverse distance of each disk and the independency of disks. Third, we improve overall performance of disk devices through considering the entire request pattern, when large numbers of clients concurrently demand heterogeneous resolutions of videos from a server. We also propose fast arrangement algorithms to reduce the computation time required for searching an effective arrangement so that they can be easily applied to practical server system.     

ZipfAllocation: an algorithm for static allocation of movies in a cluster of video servers

When a single video server provides a streaming service, there are many limitations. Thus, clusters of multiple video servers are widely used today to provide better service. How movies are allocated to each server in a cluster is an important and ongoing research topic because the movies are large, and there are so many of them. We have developed a movie allocation algorithm based on the observation that client accesses follow a Zipf distribution. We have developed an algorithm in which servers use their storage to their full capacities, movies are assigned to servers as evenly as possible, servers receive requests as evenly as possible, and all movies are allocated to at least one server. Copyright © 2010 John Wiley & Sons, Ltd.     

I/O issues in a multimedia system

In future computer system design, I/O systems will have to support continuous media such as video and audio, whose system demands are different from those of data such as text. Multimedia computing requires us to focus on designing I/O systems that can handle real-time demands. Video- and audio-stream playback and teleconferencing are real-time applications with different I/O demands. We primarily consider playback applications which require guaranteed real-time I/O throughput. In a multimedia server, different service phases of a real-time request are disk, small computer systems interface (SCSI) bus, and processor scheduling. Additional service might be needed if the request must be satisfied across a local area network. We restrict ourselves to the support provided at the server, with special emphasis on two service phases: disk scheduling and SCSI bus contention. When requests have to be satisfied within deadlines, traditional real-time systems use scheduling algorithms such as earliest deadline first (EDF) and least slack time first. However, EDF makes the assumption that disks are preemptable, and the seek-time overheads of its strict real-time scheduling result in poor disk utilization. We can provide the constant data rate necessary for real-time requests in various ways that require trade-offs. We analyze how trade-offs that involve buffer space affect the performance of scheduling policies. We also show that deferred deadlines, which increase buffer requirements, improve system performance significantly     

RAID控制器中I/O调度算法研究

介绍应用于RAID控制器的I/O调度算法的设计与实现.主要目标是把来自RAID模块针对每个磁盘的具体读写请求按照响应的策略放入对应磁盘的读写I/O队列.然后根据具体请求的优先级和读写特性,对响应请求在队列中的次序进行调整或者对前后项进行合并,实现I/O请求的调度策略.     

视频服务器存储子系统的I/O优化

视频服务器存储子系统的I／O性能决定了视频服务器的总体性能。本文提出的一种新的实时磁盘调度算法（LLF－Window)能有效地服务各种编码格式的视频流，并对传统的SCSI总线不均衡调度机制进行了改造，实验结果表明，新的磁盘调度算法和改造后的SCSI总线调度机制有效地改进了视频服务器存储子系统的I／O性能，保证了视频流的连续播放。