Throughput optimization for video streaming proxy servers based on video staging

A video streaming proxy server needs to handle hundreds of simultaneous connections between media servers and clients. Inside, every video arrived at the server and delivered from it follows a specific arrival and delivery schedule. While arrival schedules compete for incoming network bandwidth, delivery schedules compete for outgoing network bandwidth. As a result, a proxy server has to provide sufficient buffer and disk cache for storage, together with memory space, disk space and disk bandwidth. In order to optimize the throughput, a proxy server has to govern the usage of these resources. In this paper, we first analyze the property of a traditional smoothing algorithm and a video staging algorithm. Then we develop, based on the smoothing algorithm, a video staging algorithm for video streaming proxy servers. This algorithm allows us to devise an arrival schedule based on the delivery schedule. Under this arrival and delivery schedule pair, we can achieve a better resource utilization rate gracefully between different parameter sets. It is also interesting to note that the usage of the resources such as network bandwidth, disk bandwidth and memory space becomes interchangeable. It provides the basis for inter-resource scheduling to further improve the throughput of a video streaming proxy server system.

An analytical model for interval caching in interactive video servers

Design of servers to meet the quality of service (QoS) requirements of interactive video-on-demand (VOD) systems is challenging. Recognizing the increasing use of these systems in a wide range of applications, as well as the stringent service demands expected from them, several design alternatives have been proposed to improve server throughput. A buffer management technique, called interval caching, is one such solution which exploits the temporal locality of requests to the same movie and tries to serve requests from the cache, thereby enhancing system throughput.In this paper, we present a comprehensive mathematical model for analyzing the performance of interactive video servers that use interval caching. The model takes into account the representative workload parameters of interactive servers employing interval caching and calculates the expected number of cached streams as an indication of the improvement in server capacity due to interval caching. Especially, user interactions, which sensitively affect the performance of interval caching, are realistically reflected in our model for an accurate analysis. A statistical admission control technique has also been developed based on this model. Using this model as a design tool, we apply the model to measure the impact of different VCR operations on client requests and rejection probability, as well as the effect of cache size.     

Predictive buffer control in delivering remotely stored video using proxy servers

We study the problem of using proxy servers to stream video stored at a geographically separate location. The separation of the server and the storage introduces a non-negligible delay in retrieving video frames in real time. We assume an additive-increase/multiplicative-decrease transport protocol to support the streaming process and develop an effective scheme to achieve consistent, high streaming quality. The heart of the scheme is the control of buffer occupancy at the proxy server. We model the buffer as a bilinear dynamical system disturbed by a point process with stochastic state-dependent intensity. We first develop a buffer controller that does not exploit this model. Then, using the buffer model, we construct a second controller based on an optimal-control analysis for the case without retrieval delay. Extending these two controllers, we subsequently synthesize two controllers based on prediction of future system states using the model, taking into account both the delay and the state-dependent disturbance intensity. Our empirical study illustrates the effectiveness of the streaming scheme. We further find that the controllers exploiting the buffer model demonstrate performance significantly superior to that of the model-free controller in overcoming the adverse impact of the retrieval delay. We also conduct limited experiments to study the impact of variable retrieval delays.     

Segmentation of multimedia streams for proxy caching

Proxy caching of large multimedia objects on the edge of the Internet has become increasingly important for reducing network latency. For a large media object, such as a two-hour video, treating the whole media as a single object for caching is not appropriate. In this paper, we study three media segmentation approaches to proxy caching: fixed, pyramid, and skyscraper. Blocks of a media stream are grouped into various segments for cache management. The cache admission and replacement policies attach different caching priorities to individual segments, taking into account the access frequency of the media object and the segment distance from the start of the media. These caching policies give preferential treatment to the beginning segments. As such, most user requests can be quickly played back from the proxy servers without delay. Event-driven simulations are conducted to evaluate the segmentation approaches and compare them with whole media caching. The results show that: 1) compared with whole media caching, segmentation-based caching is more effective not only in increased byte-hit ratio but also in lowered fraction of requests that requires delayed start; 2) pyramid segmentation, where segment size increases exponentially, is the best segmentation approach; and 3) segmentation-based caching is especially advantageous when the cache size is limited, when the set of hot media objects changes over time, when the media file size is large, and when there are a large number of distinct media objects.     

Grid VFS中代理管理客户端磁盘缓存的设计与实现

设计并实现了在网格虚拟文件系统Grid VFS客户端采用代理管理磁盘缓存来隐藏网络延迟，提高网格数据利用率。此方法扩展了虚拟化分布式文件系统，提高了对网格资源有效完整的数据访问。在Grid VFS中，客户端代理动态地产生和管理磁盘缓存，每一个未修改的应用程序和OS都能应用，支持write-back策略、文件系统之间缓存的共享以及磁盘缓存的多级化，通过用户级VFS可以完整的集成到网格应用程序和资源中，从而提高了网格数据的访问性能。     

Methodologies for designing video servers

This paper proposes an approach for integrating CPU/disk/network scheduling and memory management for supporting a variety of VCR operations and dynamic service changes efficiently. Under this approach we can optimize individual resources, and support a maximal number of clients on a given system. We present a framework of service modeling to characterize the requested video services and identify the scheduling parameters for supporting these services. A number of techniques and methodologies are developed for analyzing the behaviors of disk accesses, network operations, and CPU activities under the loads of both single and multiple clients. We also describe an admission control strategy that utilizes information about all the system resources to determine if a set of video services is acceptable     

自适应的分段代理缓存传输策略

结合现有的代理缓存策略和传输方案,针对现有的网络条件,提出了一种自适应的分段方法,解决了已有方法对于流媒体对象流行性的变化和用户访问模式的不确定缺乏自身调整能力的缺欠,和一种优化的传输方案,采用了单播和多播相结合, 主动预取和补丁传输相结合的方法,对于缩短启动延时、提高字节命中率以及节省骨干网带宽等方面取得了较明显的效果.     

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     

Proxy servers for scalable interactive video support

Targeting scalability, load balance and resource efficiency in streaming multimedia applications, proxy servers facilitate faster real-time access to cached objects and reduce response time to document requests     

A novel server-side proxy caching strategy for large-scale multimedia applications

Nowadays, server-side Web caching becomes an important technique used to reduce the User Perceived Latency (UPL). In large-scale multimedia systems, there are many Web proxies, connected with a multimedia server, that can cache some most popular multimedia objects and respond to the requests for them. Multimedia objects have some particular characteristic, e.g., strict QoS requirements. Hence, even some efficient conventional caching strategies based on cache hit ratio, meant for non-multimedia objects, will confront some problems in dealing with the multimedia objects. If we consider additional resources of proxy besides cache space, say bandwidth, we can readily observe that high hit ratios may deteriorate the entire system performance. In this paper, we propose a novel placement model for networked multimedia systems, referred to as the H^k/T model, which considers the combined influence of arrival rate, size, and playback time to select the objects to be cached. Based on this model, we propose an innovative Web caching algorithm, named as the ART-Greedy algorithm, which can balance the load among the proxies and achieve a minimum Average Response Time (ART) of the requests. Our experimental results conclusively demonstrate that the ART-Greedy algorithm outperforms the most popular and commonly used LFU (Least Frequently Used) algorithm significantly, and can achieve a better performance than the byte-hit algorithm when the system utilization is medium and high.     

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.     

集群缓存系统中代理缓存技术的研究

针对集群缓存系统的特点,对其内部各代理缓存进行了详细的研究.在缓存副本的存储方面,采用了面向网站的存储方案,更好的实现个性化服务的功能;在缓存副本的管理方面,采用了将替换和一致性结合在一起的RCA算法,使得整个系统有较高的命中陈旧率;在代理协作方面,通过重定向的方法将请求从未命中的代理转发给缓存了请求的代理,避免了代理之间复制对象,有效地减少了缓存对象的冗余度.通过理论分析推导,证明了它能大大减少访问延迟、有效地减轻了Web服务器的负担.实验证明,本协作方案有较高的命中率.     

Form-based proxy caching for database-backed web sites: keywords and functions

Web caching proxy servers are essential for improving web performance and scalability, and recent research has focused on making proxy caching work for database-backed web sites. In this paper, we explore a new proxy caching framework that exploits the query semantics of HTML forms. We identify two common classes of form-based queries from real-world database-backed web sites, namely, keyword-based queries and function-embedded queries. Using typical examples of these queries, we study two representative caching schemes within our framework: (i) traditional passive query caching, and (ii) active query caching, in which the proxy cache can service a request by evaluating a query over the contents of the cache. Results from our experimental implementation show that our form-based proxy is a general and flexible approach that efficiently enables active caching schemes for database-backed web sites. Furthermore, handling query containment at the proxy yields significant performance advantages over passive query caching, but extending the power of the active cache to do full semantic caching appears to be less generally effective.     

PopCap: popularity oriented proxy caching for peer-assisted Internet video-on-demand streaming services

With the success of Internet video-on-demand (VoD) streaming services, the bandwidth required and the financial cost incurred by the host of the video server becoming extremely large. Peer-to-peer (P2P) networks and proxies are two common ways for reducing the server workload. In this paper, we consider a peer-assisted Internet VoD system with proxies deployed at domain gateways. We formally present the video caching problem with the objectives of reducing the video server workload and avoiding inter-domain traffic, and we obtain its optimal solution. Inspired by theoretical analysis, we develop a practical protocol named PopCap for Internet VoD services. Compared with previous work, PopCap does not require additional infrastructure support, is inexpensive, and able to cope well with the characteristic workloads of Internet VoD services. From simulation-based experiments driven by real-world data sets from YouTube, we find that PopCap can effectively reduce the video server workload, therefore provides a superior performance regarding the video server’s traffic reduction.     

Doubly-striped disk mirroring: Reliable storage for video servers

Disk striping is essential in Video-On-Demand servers to allow concurrent access for a large number of users to the same copy of a video object. On the other hand, disk striping makes the system more vulnerable to component failures. We propose a replication scheme for video content and an associated I/O scheduling algorithm that enables the system to tolerate a component failure. The scheme, called doubly-striped mirrors, compares favorably to other approaches for implementing redundancy such as RAID in terms of cost, bandwidth efficiency, buffer usage and system availability.     

Staggered push - a linearly scalable architecture for push-based parallel video servers

With the rapid performance improvements in low-cost PCs, it becomes increasingly practical and cost-effective to implement large-scale video-on-demand (VoD) systems around parallel PC servers. This paper proposes a novel parallel video server architecture where video data are striped across an array of autonomous servers connected by an interconnection network. To coordinate data transmissions from multiple autonomous servers to a client station, a staggered push scheduling algorithm is proposed. A system model is constructed to quantify the performance of the architecture. Unlike most studies, this work does not assume the existence of a global clock among the servers and tackles two problems arising from server asynchrony: inconsistent schedule assignment and traffic overlapping. The former problem is solved by using an admission scheduler and the latter problem is solved by an over-rate transmission scheme. Analytical results prove a remarkable property of the staggered push architecture: as long as the network has sufficient capacity, the system can be scaled up linearly to an arbitrary number of servers. Design examples and numerical results are used to evaluate the proposed architecture under realistic assumptions and to compare it against other architecture.     

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.     

Proxy-assisted periodic broadcast for video streaming with multiple servers

Large scale video streaming over the Internet requires a large amount of resources such as server I/O bandwidth and network bandwidth. A number of video delivery techniques can be used to lower these requirements. Periodic broadcast by a central server combined with proxy caching offers a significant reduction of the aggregate network and server I/O bandwidth usage. However, the resources available to a single server are still limited. In this paper we propose a system with multiple geographically distributed servers. The problem of multiple servers for periodic broadcast is quite different from the problem of object location for multiple web servers. Multiple servers offer increased amount of resources and service availability and may potentially allow a further reduction of network bandwidth usage. On the other hand, the benefit of periodic broadcast mostly comes from high demand videos. With multiple servers holding a video, the demand of the video at each server is reduced. Therefore, it is a challenge to use multiple servers efficiently. We first analyze the dependence of the resource requirements on the number and locations of the servers. Based on the character of the function describing such a dependence, we formulate and solve the problem of video location and delivery, in a way that minimizes resource usage. We explore a trade-off between network and I/O bandwidth requirements. We evaluate our proposed solutions through a number of tests.

Efficient support for interactive browsing operations in clusteredCBR video servers

Providing efficient support for interactive browsing operations such as fast-forward (ff) and fast-backward (fb) is essential in video-on-demand and other multimedia server systems. In this paper, we propose two basic approaches to scheduling interactive browsing operations: 1) the prefetching approach and 2) the grouping approach. Block-skipping and frame-skipping algorithms are presented for constant bit rate (CBR) data blocks. These algorithms can precisely schedule video streams for both normal play and interactive browsing operations     

A window-assisted video partitioning strategy for partitioning and caching video streams in distributed multimedia systems

In this paper, we address the issue of efficiently streaming a set of heterogenous videos under the constraint of service latency over a scalable multimedia systems. We propose a novel strategy, referred to as window-assisted video partitioning (WAVP), for rendering cost-effective multimedia services. The objective is to minimize the service cost and maximize the number of requests that can be successfully served under resources constraints (cache capacity and link bandwidth). We formulate the problem of video partitioning as an optimization of both bandwidth resources and cache space, and derive the optimal schedule window for different video portions under consideration of time constraints, the popularities and the sizes of the video portions. In WAVP, video are partitioned into multiple portions and delivered according to by adaptive schedule windows. We prove that WAVP strategy not only optimize the service cost but also be able to serve requests under the time constraints without causing too much delay. We conduct mathematical analysis and derive certain performance bounds that quantify the overall performance of the strategy. It shows that the service cost can be optimized by adjusting the schedule window and resources utilization can be improved as video streams are partitioned into multiple portions. We evaluate the performance under several influencing parameters such as available bandwidth, cache capacity, and partition gradients. Simulation results show that our proposed method can not only significantly reduce the service cost under tight time constraints and with low partition overhead, but also balance the utilization of network resources to achieve high acceptance ratio with low average service cost.