Optimal Coding of Multilayer and Multiversion Video Streams

Traditional video servers partially cope with heterogeneous client populations by maintaining a few versions of the same stream with different bit rates. More recent video servers leverage multilayer scalable coding techniques to customize the quality for individual clients. In both cases, heuristic, error-prone, techniques are currently used by administrators to determine either the rate of each stream version, or the granularity and rate of each layer in a multilayer scalable stream. In this paper, we propose an algorithm to determine the optimal rate and encoding granularity of each layer in a scalable video stream that maximizes a system-defined utility function for a given client distribution. The proposed algorithm can be used to compute the optimal rates of multiversion streams as well. Our algorithm is general in the sense that it can employ arbitrary utility functions for clients. We implement our algorithm and verify its optimality, and we show how various structuring of scalable video streams affect the client utilities. To demonstrate the generality of our algorithm, we consider three utility functions in our experiments. These utility functions model various aspects of streaming systems, including the effective rate received by clients, the mismatch between client bandwidth and received stream rate, and the client-perceived quality in terms of PSNR. We compare our algorithm against a heuristic algorithm that has been used before in the literature, and we show that our algorithm outperforms it in all cases.     

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.     

一个自组织可扩展PC集群存储系统

随着大型的分布式系统及商用机器集群的流行，许多重要的研究都致力于设计可扩展的集群存储系统。文中介绍了一个自组织可扩展PC集群存储系统的设计方案，并提出了一种对各个存储结点所挂磁盘的分组方案，对于大小数据对象采用不同的放置定位技术，重点讨论了小数据对象的伪随机放置算法，该算法在系统扩展时也能够有效地定位数据对象。该方案在同构系统中，达到了较好的磁盘负载平衡，从而各个节点的负载也达到了相对平衡的状态。另外通过对数据对象的有效的复制，使系统具有很好的容错性。     

Optimized scalable cache management for video streaming system

An important research issue in video streaming is how to efficiently utilize the network resources to provide clients instant access to multiple video objects. Caching strategy and transmission scheme are the two essential points inside the video streaming framework. Recent research efforts on them are not sufficient due to their inflexible support for scalable encoded video streams and heterogeneous requests from clients. In this paper, we propose an optimized caching strategy (OCS) and a scalable transmission scheme (STS) for scalable coded video streaming. By exploring the characteristics of video streaming workload and system design objectives, OCS and STS work efficiently to minimize both network bandwidth cost and user access latency. Firstly, we analyze the caching problem for the proxy-assisted video streaming system and derive a maneuverable caching scenario. Secondly, we develop an efficient transmission scheme for scalable coded videos. Thirdly, we formulate a multi-objective optimization model with closed-form expressions to obtain the optimized caching strategy. Finally, with designed algorithms, an excellent compromise between two competing objectives (minimizing the bandwidth cost and the access latency) is achieved. We start our evaluation by studying the optimized caching strategy for a single video object. Then we apply the strategy to multiple video objects and illustrate the tradeoff between the optimization objectives. Our evaluation results show that compared with other caching strategies, the proposed optimized scalable caching strategy can achieve a significant reduction in bandwidth cost with even a small proxy cache size. Meanwhile, the best performance (in terms of bandwidth cost) is obtained together with the proposed scalable batch-patching transmission scheme.

Harmonic proportional bandwidth allocation and scheduling for service differentiation on streaming servers

To provide ubiquitous access to the proliferating rich media on the Internet, scalable streaming servers must be able to provide differentiated services to various client requests. Recent advances of transcoding technology make network-I/O bandwidth usages at the server communication ports controllable by request schedulers on the fly. In this article, we propose a transcoding-enabled bandwidth allocation scheme for service differentiation on streaming servers. It aims to deliver high bit rate streams to high priority request classes without overcompromising low priority request classes. We investigate the problem of providing differentiated streaming services at application level in two aspects: stream bandwidth allocation and request scheduling. We formulate the bandwidth allocation problem as an optimization of a harmonic utility function of the stream quality factors and derive the optimal streaming bit rates for requests of different classes under various server load conditions. We prove that the optimal allocation, referred to as harmonic proportional allocation, not only maximizes the system utility function, but also guarantees proportional fair sharing between classes with different prespecified differentiation weights. We evaluate the allocation scheme, in combination with two popular request scheduling approaches, via extensive simulations and compare it with an absolute differentiation strategy and a proportional-share strategy tailored from relative differentiation in networking. Simulation results show that the harmonic proportional allocation scheme can meet the objective of relative differentiation in both short and long timescales and greatly enhance the service availability and maintain low queueing delay when the streaming system is highly loaded.     

OCFS：一种基于对象存储结构的可伸缩高性能集群文件系统

提出了一种基于确定性随机分布算法分布元数据和数据对象的可伸缩集群文件系统结构。其中目录路径属性与目录对象分离的元数据管理方法，在提高系统性能、均衡元数据分布和减少元数据迁移等方面具有明显优势。提出的基于动态区间映射的数据对象布局算法，支持权重分布和副本，在均衡数据分布和最少迁移数据方面都具有统计意义上的最优性，有效解决了动态存储系统的数据均衡分布与可伸缩性问题。     

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.     

Storage technique for real-time streaming of layered video

Scalable streaming technology has been proposed to effectively support heterogeneous devices with dynamically varying bandwidth. From the file system’s point of view, scalable streaming introduces another dimension of complexity in disk scheduling. Most of the existing efforts on multimedia file systems are dedicated to I/O scheduling algorithm and data placement scheme that efficiently guarantee I/O bandwidth. The important underlying assumption in these efforts is that most of the multimedia file accesses are simple playback operations and therefore are sequential. However, this workload characteristic is not valid in scalable streaming environment. In a scalable streaming environment, i.e., when only a subset of imagery is retrieved, the playback does not necessarily coincide with the sequential access on the file. The current file structure and the file system organization leaves much to be desired for supporting scalable streaming service. In this work, we propose a file system scheme, Harmonic Placement to efficiently support scalable streaming. The basic idea of Harmonic placement is to cluster the frequently accessed layers together to avoid unnecessary disk seeks. The data blocks are partitioned into two sets with respect to the layers: lower layers and upper layers. In Harmonic placement, the data blocks in the lower layers are placed with respect to their frame sequence and the data blocks in the upper layers are clustered according to the layers they belong to. We develop elaborate performance models for three different file system schemes: Progressive placement, Interleaved Placement and Harmonic Placement. We investigate the performance of the file server with different file system schemes. It was found that file system performance is very sensitive to the file organization scheme. When most of the service requests are for low-quality video (e.g., 128 Kbits/s ISDN), Progressive placement scheme supports twice as many sessions as the Interleaved placement scheme. When most of the service requests are for high-quality video (e.g., 1.5 Mbits/s MPEG-2 DVD quality), Interleaved placement can support twice as many requests as Progressive placement. In both cases, Harmonic placement scheme yields the most promising performance. Primitive version of this work has appeared on Proceedings of NOSSDAV ’06, Providence, Rhode Island, USA. This work is in part funded by KOSEF throught National Research Lab (ROA-2007-000-200114-0) and by HY-SDR center at Hanyang University.     

Modeling and generating realistic streaming media server workloads

Currently, Internet hosting centers and content distribution networks leverage statistical multiplexing to meet the performance requirements of a number of competing hosted network services. Developing efficient resource allocation mechanisms for such services requires an understanding of both the short-term and long-term behavior of client access patterns to these competing services. At the same time, streaming media services are becoming increasingly popular, presenting new challenges for designers of shared hosting services. These new challenges result from fundamentally new characteristics of streaming media relative to traditional web objects, principally different client access patterns and significantly larger computational and bandwidth overhead associated with a streaming request. To understand the characteristics of these new workloads we use two long-term traces of streaming media services to develop MediSyn, a publicly available streaming media workload generator. In summary, this paper makes the following contributions: (i) we propose a framework for modeling long-term behavior of network services by capturing the process of file introduction, non-stationary popularity of media accesses, file duration, encoding bit rate, and session duration. (ii) We propose a variety of practical models based on the study of the two workloads. (iii) We develop an open-source synthetic streaming service workload generator to demonstrate the capability of our framework to capture the models.     

On the Design of Distributed Object Placement and Load Balancing Strategies in Large-Scale Networked Multimedia Storage Systems

In a large-scale multimedia storage system (LMSS) where client requests for different multimedia objects may have different demands, the placement and replication of the objects is an important factor, as it may result in an imbalance in server loading across the system. Since replication management and load balancing are all the more crucial issues in multimedia systems, in the literature, these problems are handled by centralized servers. Each object storage server (OSS) responds to the requests that come from the centralized servers independently and has no communication with other OSSs in the system. In this paper, we design a novel distributed load balancing strategy for LMSS, in which OSSs can cooperate to achieve higher performance. Such OSS modeled as an M/G/m system can replicate the objects to and balance the requests among other servers to achieve a near-optimal average waiting time (AWT) of the requests in the system. We validate the performance of the system via rigorous simulations with respect to several influencing factors and prove that our proposed strategy is scalable, flexible, and efficient for real-life applications.     

流媒体集群系统中多目标复制存储方法

分析流行度分布、会话长度、负载均衡度等因素对系统性能的影响,在流媒体集群系统中提出一种多目标复制存储方法。将副本生成问题归纳为席位分配问题,给出最优副本生成算法,根据文件流行度服从Zipf-like分布的特点,启发式地将磁盘空间分配给各流媒体副本,以平衡副本负载。在此基础上,设计基于进化的全局最优的副本放置算法。仿真结果证明,该方法可在存储空间受限的情况下实现较低的拒绝率和较高的负载均衡度。     

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.     

A novel distributed architecture of large-scale multimedia storage system using autonomous object-based storage devices

In a large-scale multimedia storage system (LMSS) where the user requests for different multimedia objects may have different demands, placement and replication of the objects is an important factor, as it may result in an imbalance in loading across the system. Since replica management and load balancing is a crucial issue in multimedia systems, normally this problem is handled by centralized servers, e.g., metadata servers (MDS) in distributed file systems. Each object-based storage device (OSD) responds to the requests coming from the centralized servers independently and has no communication with other OSDs among the system. In this paper, we design a novel distributed architecture of LMSS, in which the OSDs have some kind of intelligences and can cooperate to achieve a high performance. Such an OSD, named as autonomous object-based storage device (AOSD), can replicate the objects to and balance the requests among other AOSDs, and handle fail-over and recovery autonomously. In the proposed architecture, we move the request balancing from centralized MDS to AOSDs and make the system more scalable, flexible, and robust. Based on the proposed architecture, we propose two different object replication and load balancing algorithms, named as “Minimum Average Waiting Time” (MAWT) and “One of the Best Two Choices” (OBTC), respectively. We validate the performance of the algorithms via rigorous simulations with respect to several influencing factors. Our findings conclusively demonstrate that the proposed architecture minimizes the average waiting time and at the same time carries out load balancing across servers.     

A self‐organized load balancing mechanism for cloud computing

The growth in computer and networking technologies over the past decades established cloud computing as a new paradigm in information technology. The cloud computing promises to deliver cost‐effective services by running workloads in a large scale data center consisting of thousands of virtualized servers. The main challenge with a cloud platform is its unpredictable performance. A possible solution to this challenge could be load balancing mechanism that aims to distribute the workload across the servers of the data center effectively. In this paper, we present a distributed and scalable load balancing mechanism for cloud computing using game theory. The mechanism is self‐organized and depends only on the local information for the load balancing. We proved that our mechanism converges and its inefficiency is bounded. Simulation results show that the generated placement of workload on servers provides an efficient, scalable, and reliable load balancing scheme for the cloud data center. Copyright © 2016 John Wiley & Sons, Ltd.     

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.     

Optimizing server placement in hierarchical grid environments

In this paper, we address some problems related to server placement in Grid environments. Given a hierarchical network with requests from clients and constraints on server capability, the minimum server placement problem attempts to place the minimum number of servers that satisfy requests from clients. Instead of using a heuristic approach, we propose an optimal algorithm based on dynamic programming to solve the problem. We also consider the balanced server placement problem, which tries to place a given number of servers appropriately so that their workloads are as balanced as possible. We prove that an optimal server placement can be achieved by combining the above algorithm with a binary search on workloads. This approach can be further extended to deal with constrains on network capability. The simulation results clearly show the improvement in the number of servers and the maximum workload. Furthermore, as the maximum workload is reduced, the waiting time is reduced accordingly.

Inter-Object Layer Clustering for scalable video streaming

In this work, we develop an efficient storage technique to support real-time streaming of layer encoded video in a single hard disk. The size of a single hard disk drive will soon be able to hold multi-tera bytes and is going to handle relatively larger number of files. We expect that disk layout in a single disk will be rather critical issue in determining the efficiency of the storage system. We propose a novel storage technique, Inter-Object Layer Clustering for layer encoded video objects. In Inter-Object Layer Clustering, storage is partitioned into two regions: lower layer partition and upper layer partition. Lower and upper layer partition harbor the lower layer and upper layer data blocks across all video objects and cluster them together. We develop an elaborate performance model for this placement scheme. We examine the performance of the proposed technique using analytical formulation as well as a physical experiment. We found that clustering the layers across all objects brings 100% increase in the number of concurrent sessions compared to the case where file is stored in temporal order when the clients’ access bandwidth is narrow. Inter-Object Layer Clustering shows 15% performance improvement compared to the clustering of layers within the objects.     

Adaptive QoS Control Based on Benefit Optimization for Video Servers Providing Differentiated Services

We propose and analyze quality of service (QoS) control algorithms for video servers designed to provide differentiated video streaming services. The design concepts are based on resource reservation and benefit optimization so that resources are reserved dynamically and adaptively for different QoS levels in response to the changing workload of the system, with the objective of maximizing the benefit throughput obtainable by the system. We analyze the benefit throughput obtainable by the system for a baseline algorithm for which the QoS levels of admitted users are not changed during the service lifetime and a greedy algorithm that may raise QoS levels of admitted users due to resources being free from departure events. We validate the design of these two QoS control algorithms via a detailed simulation study.     

A dynamic caching algorithm based on internal popularity distribution of streaming media

Most proxy caches for streaming videos do not cache the entire video but only a portion of it. This is partly due to the large size of video objects. Another reason is that the popularity of different parts of a video can be different, e.g., the prefix is generally more popular. Therefore, the development of efficient cache mechanisms requires an understanding of the internal popularity characteristics of streaming videos. This paper has two major contributions. Firstly, we analyze two 6-month long traces of RTSP video requests recorded at different streaming video servers of an entertainment video-on-demand provider, and show that the traces provide evidence that the internal popularity of the majority of the most popular videos obeys a k-transformed Zipf-like distribution. Secondly, we propose a caching algorithm which exploits this empirical internal popularity distribution. We find that this algorithm has similar performance compared with fine-grained caching but requires significantly less state information.     

Cost-effective resource provisioning for multimedia cloud-based e-health systems

Recently, multimedia cloud is being considered as a new effective serving mode in e-Health area that meets the requirement of scalable and economic multimedia service for e-health. It can provide a flexible stack of powerful Virtual Machine (VM) resources of cloud like CPU, memory, storage, network bandwidth etc. on demand to manage e-health media services and applications (e.g. medical image/video retrieval, health video transcoding, streaming, video rendering, sharing and delivery) at lower cost. However, one major issue here is how to efficiently allocate VM resources dynamically based on e-health applications’ QoS demands and support energy and cost savings by optimizing the number of servers in use. In order to solve this problem, we propose a cost effective and dynamic VM allocation model based on Nash bargaining solution. With extensive simulations it is shown that the proposed mechanism can reduce the overall cost of running servers while at the same time guarantee QoS demand and maximize resource utilization in various dimensions of server resources.