Super-Streaming: A New Object Delivery Paradigm for Continuous Media Servers

A number of studies have focused on the design of continuous media, CM, (e.g., video and audio) servers to support the real-time delivery of CM objects. These systems have been deployed in local environments such as hotels, hospitals and cruise ships to support media-on-demand applications. They typically stream CM objects to the clients with the objective of minimizing the buffer space required at the client site. This objective can now be relaxed due to the availability of inexpensive storage devices at the client side. Therefore, we propose a Super-streaming paradigm that can utilize the client side resources in order to improve the utilization of the CM server. To support super-streaming, we propose a technique to enable the CM servers to deliver CM objects at a rate higher than their display bandwidth requirement. We also propose alternative admission control policies to downgrade super-streams in favor of regular streams when the resources are scarce. We demonstrate the superiority of our paradigm over streaming with both analytical and simulation models.Moreover, new distributed applications such as distant-learning, digital libraries, and home entertainment require the delivery of CM objects to geographically disbursed clients. For quality purposes, recently many studies proposed dedicated distributed architectures to support these types of applications. We extend our super-streaming paradigm to be applicable in such distributed architectures. We propose a sophisticated resource management policy to support super-streaming in the presence of multiple servers, network links and clients. Due to the complexity involved in modeling these architectures, we only evaluate the performance of super-streaming by a simulation study.     

Range Multicast for Video on Demand

We explore a communication paradigm for video on demand, called Range Multicast. This schemeis a shift from the conventional thinking about multicast where every receiver must obtain the same data packet at any time. A range multicast allows new members to join at their specified time and still receive the entire video stream without consuming additional server bandwidth. Clients enjoy better service latency since they can join an existing multicast instead of waiting for the next available server stream. We also present techniques to support video-cassette-recorder-like interactivity in this environment. Unlike existing methods which require clients to cache data in a private buffer, the Range Multicast solution utilizes the shared network storage to make more efficient and cost-effective use of the caching space. Furthermore, since a range multicast can accommodate clients with different play points in the video, a client has a better chance to join an on-going multicast for normal playback after finishing a VCR operation. This strategy avoids the need for a new server stream, and thus further alleviates the server load. Our simulation results confirm the aforementioned benefits.     

Proxy-assisted scalable periodic broadcasting of videos for heterogeneous clients

Periodic broadcasting (PB) is a scalable technique for providing video-on-demand services. It significantly reduces server input and output (I/O) and backbone network bandwidth requirements, but increases the clients’ need for storage space and network bandwidth. Traditional protocols assume homogeneous clients with identical resources. In practice, however, clients have very different bandwidths, which are usually not sufficient for video-on-demand service from a PB server. Existing work on heterogeneous clients has focused on devising broadcast schedules that cater to low-bandwidth clients; these schedules inevitably require additional backbone network bandwidth between the server and the clients. In this paper, we propose a scheme to significantly reduce the waiting time of all heterogeneous clients, without the need for any additional backbone bandwidth. This scheme uses a proxy buffer within video-on-demand systems using PB. In the proposed system, the server broadcasts a video using one of the traditional PB protocols. Simultaneously, the proxy receives the stream from the server and stores it in its local buffer, then broadcasts the stored data to the clients in its local network. Because the proxy provides extra, transparent channels to the server, clients are likely to reduce their reception bandwidth requirements through the use of efficient reception schedules using the extra channels.     

Efficient schemes for broadcasting popular videos

We provide a formal framework for studying broadcasting schemes and design a family of schemes for broadcasting popular videos, the greedy disk-conserving broadcasting (GDB) family. We analyze the resource requirements for GDB, i.e., the number of server broadcast channels, the client storage space, and the client I/O bandwidth required by GDB. Our analysis shows that all of our proposed broadcasting schemes are within a small factor of the optimal scheme in terms of the server bandwidth requirement. Furthermore, GDB exhibits a tradeoff between any two of the three resources. We compare our scheme with a recently proposed broadcasting scheme, skyscraper broadcasting (SB). With GDB, we can reduce the client storage space by as much as 50% or the number of server channels by as much as 30% at the cost of a small additional increase in the amount of client I/O bandwidth. If we require the client I/O bandwidth of GDB to be identical to that of SB, GDB needs only 70% of the client storage space required by SB or one less server channel than SB does. In addition, we show that with small client I/O bandwidth, the resource requirements of GDB are close to the minimum achievable by any disk-conserving broadcasting scheme.     

Dynamic proxy-assisted scalable broadcasting of videos for heterogeneous environments

Periodic broadcasting (PB) is a scalable technique for providing video-on-demand services. It significantly reduces server I/O and backbone network bandwidth requirements at the expense of high storage space and high network bandwidth requirements for clients. Traditional protocols assume homogeneous clients with identical resources. Unfortunately, in practice clients have very different bandwidths, and these are usually insufficient to provide video-on-demand (VoD) service from a PB server. Existing work on heterogeneous clients has focused on devising broadcast schedules to cater to low-bandwidth clients, which inevitably requires an extra backbone network bandwidth between the server and the clients. In our previous work, we proposed to use proxies residing at the edge of backbone network to accommodate low bandwidth clients for PB-based VoD services. The server broadcasts a video using a PB protocol while the proxy receives and stores the data in its local buffer and broadcasts the stored data to the clients in its local network. It significantly reduces the waiting time of low-bandwidth clients without requiring any extra backbone bandwidth by using a proxy buffer and channels. However, although lots of PB protocols have been proposed, the scheme can be applied only to some old PB protocols based on a pyramid protocol. In this paper, we propose a proxy-assisted PB system that can be generally applied to almost all the existing PB protocols, by dynamically managing buffer space and channels in proxy servers. Thus, with our proposed system, PB VoD system can be optimized in terms of the resource usages in backbone networks, proxy servers, and clients, by adopting more suitable PB protocols.     

Video personalization in heterogeneous and resource-constrained environments

Access to multimedia data and multimedia services is becoming increasingly common in networked mobile environments. In such environments, both the mobile client devices and multimedia servers are typically resource constrained. Moreover, the mobile client population is often heterogeneous in terms of the clients’ preferences with regard to multimedia content, the clients’ quality of service requirements and system-level resource constraints. In order to provide a resource-constrained mobile client with its desired video content, it is often necessary to personalize the requested multimedia content in a manner that satisfies simultaneously the various client-specified content preferences and the system-level resource constraints. Also, in order to simultaneously reduce the client-experienced latency, provide optimal quality of service to the clients and ensure efficient utilization of server and network resources, it is necessary to perform client request aggregation on the server end. To this end, a video personalization strategy is proposed to provide mobile, resource-constrained clients with personalized video content that is most relevant to the clients’ requests while satisfying simultaneously multiple client-side system-level resource constraints. A client request aggregation strategy is also proposed to cluster client requests with similar video content preferences and similar client-side resource constraints such that the number of requests the server needs to process and service, and the client-experienced latency are both reduced simultaneously. The primary contributions of the paper are: (1) the formulation and implementation of a Multiple-choice Multi-dimensional Knapsack Problem (MMKP)-based video personalization strategy; and (2) the design and implementation of a client request aggregation strategy based on a multi-stage clustering algorithm. Experimental results comparing the proposed MMKP-based video personalization strategy to existing 0/1 Knapsack Problem (0/1KP)-based and the Fractional Knapsack Problem (FKP)-based video personalization strategies are presented. It is observed that: (1) the proposed MMKP-based personalization strategy includes more relevant video content in response to the client’s request compared to the existing 0/1KP-based and FKP-based personalization strategies; and (2) in contrast to the 0/1KP-based and FKP-based personalization strategies which can satisfy only a single client-side resource constraint at a time, the proposed MMKP-based personalization strategy is capable of satisfying multiple client-side resource constraints simultaneously. Experimental results comparing the client-experienced latency with and without the proposed server-side client request aggregation strategy are also presented. It is shown that the proposed client request aggregation strategy reduces the mean client-experienced latency without significant reduction in the average relevance of the delivered video content and without significant deviation in the client-side resources actually consumed by the delivered video content from the client-specified resource constraints.     

A unified benchmarking and model-based framework for building QoS-aware streaming media services

A number of technology and workload trends motivate us to consider the appropriate resource allocation mechanisms and policies for streaming media services in shared cluster environments. We present MediaGuard – a model-based infrastructure for building streaming media services – that can efficiently determine the fraction of server resources required to support a particular client request over its expected lifetime. The proposed solution is based on a unified cost function that uses a single value to reflect overall resource requirements such as the CPU, disk, memory, and bandwidth necessary to support a particular media stream based on its bit rate and whether it is likely to be served from memory or disk. We design a novel, time-segment-based memory model of a media server to efficiently determine in linear time whether a request will incur memory or disk access when given the history of previous accesses and the behavior of the server's main memory file buffer cache. Using the MediaGuard framework, we design two media services: (1) an efficient and accurate admission control service for streaming media servers that accounts for the impact of the server's main memory file buffer cache, and (2) a shared streaming media hosting service that can efficiently allocate the predefined shares of server resources to the hosted media services, while providing performance isolation and QoS guarantees among the hosted services. Our evaluation shows that, relative to a pessimistic admission control policy that assumes that all content must be served from disk, MediaGuard (as well as services that are built using it) deliver a factor of two improvement in server throughput.     

视频点播服务器的动态缓存管理

视频服务器的缓存管理对视频点播系统的性能有重要的影响。为了提高视频服务器的资源利用率、提高客户端节目的播放质量和流畅性，我们提出一种动态的缓存管理算法。该算法节省资源，有效地防止缓存上溢或下溢，为客户端的高质量播放提供可能。本文通过建立一个排队论模型对该算法进行分析，然后给出了详尽的算法描述，最后模拟仿真以证实其可行性和有效性。     

Retrieval schedules based on resource availability and flexible presentation specifications

A distributed multimedia document presentation involves retrieval of objects from one or more document servers and their presentation at the client system. The presentation of the multimedia objects has to be carried out in accordance with the specification of temporal relationships between the objects. The retrieval of multimedia objects from the document server(s) is influenced by factors such as temporal specification of objects presentations, throughput offered by the network service provider, and the buffer resources on the client system. Flexibility in the temporal specification of the multimedia document may help in deriving an object retrieval schedule that can handle variations in network throughput and buffer resource availability. In this paper, we develop techniques for deriving a flexible object retrieval schedule for a distributed multimedia document presentation. The schedule is based on flexible temporal specification of the multimedia document using the difference constrai nts approach. We show how the derived retrieval schedule can be validated and modified to ensure that it can work with the offered network throughput and the available buffer resources.     

Optimal chaining scheme for video-on-demand applications on collaborative networks

By forwarding the server stream client by client, a chaining-based scheme is a good way to reduce the server streams for streaming applications in well-connected networks. In this paper, we prove that the minimum number of required server streams in such schemes is n-k+1, where n is the number of client requests and k is a value determined by client buffer sizes and the distribution of requests. In addition, we present an optimal chaining algorithm using a dynamic buffer allocation strategy. Compared to existing chaining schemes, our scheme not only utilizes the backward (basic chaining) and/or forward (adaptive chaining) buffer, but also exploits the buffers of other clients in order to extend the chain as much as possible. In this way, more clients can be chained together and served by the same server stream. Our simulation results show that the requirements of the server streams in the presented scheme are much lower those of existing chaining schemes. We also introduce mechanisms for handling VCR functions and fault exceptions in practical applications.     

Efficient Selective Frame Discard Algorithms for Stored Video Delivery Across Resource Constrained Networks

Video delivery from a server to a client across a network is an important component of many multimedia applications. While delivering a video stream across a resource constrained network, loss of frames may be unavoidable. Under such circumstances, it is desirable to find a server transmission schedule that can efficiently utilize the network resources while maximizing the perceived quality-of-service (QoS) at the client. To address this issue, in this paper we introduce the notion ofselective frame discard at the server and formulate the optimal selective frame discard problem using a QoS-based cost function. Given network bandwidth and client buffer constraints, we develop an O (N log N) algorithm to find the minimum number of frames that must be discarded in order to meet these constraints. The correctness of the algorithm is also formally established. We present a dynamic programming based algorithm for solving the problem of optimal selective frame discard. Since the computational complexity of the optimal algorithm is prohibitively high in general, we also develop several efficient heuristic algorithms for selective frame discard. These algorithms are evaluated using JPEG and MPEG video traces.     

基于P2P的视频点播系统设计

随着计算机网络和多媒体技术的发展,人们对网络视频点播的需求越来越高,高清、流畅和互动已经成为人们对视频点播的要求,在传统的C/S模式的视频点播系统中,客户终端要观看视频都需要依赖中心化的视频服务器,而且对带宽的要求越来越大,视频服务器就容易成为网络的瓶颈,当网络规模越大时,服务器的负担就会越重,一旦服务器崩溃,整个网络就会瘫痪。另外由于服务器的能力有限,往往不能及时地对每一个客户端的请求作出响应,因此会造成资源利用率低下。P2P网络中没有中心化的服务器,不存在系统瓶颈,每个节点既充当客户端又充当服务器端,因而具有很高的资源利用率。     

Adaptive Broadcasting for Similarity Queries in Wireless Content Delivery Systems

We present a new adaptive and energy-efficient broadcast dissemination model that supports flexible responses to client requests. In current broadcast dissemination models, clients must specify precisely what documents they require, and servers disseminate exactly those documents. This approach can be impractical, since in practice, clients may know the characteristics of the documents, but not the document names or IDs. In our model, clients specify the required document using attributes, and servers broadcast documents that match client requests at a prespecified level of similarity. A single document may satisfy several clients, so the server broadcasts a minimal set of documents that achieves a desired level of satisfaction in the client population. We introduce a mechanism for the server to obtain randomized feedback from clients to adapt its broadcast program to client needs. Finally, the server integrates a selective tune-in scheme based on approximate index matching to allow clients to conserve energy. Our simulation results show that our model captures client interest patterns efficiently and accurately and scales very well with the number of clients, while reducing overall client average waiting times. The selective tune-in scheme can considerably reduce the consumption of client energy with moderate waiting time overhead.     

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     

A dynamic framework for integrated management of all types of resources in P2P systems

Traditional Peer-to-Peer (P2P) systems were restricted to sharing of files on the Internet. Although some of the more recent P2P distributed systems have tried to support transparent sharing of other types of resources, like computer processing power, but none allow and support sharing of all types of resources available on the Internet. This is mainly because the resource management part of P2P systems are custom designed in support of specific features of only one type of resource, making simultaneous access to all types of resources impractical. Another shortcoming of existing P2P systems is that they follow a client/server model of resource sharing that makes them structurally constrained and dependent on dedicated servers (resource managers). Clients must get permission from a limited number of servers to share or access resources, and resource management mechanisms run on these servers. Because resource management by servers is not dynamically reconfigurable, such P2P systems are not scalable to the ever growing extent of Internet. We present an integrated framework for sharing of all types of resources in P2P systems by using a dynamic structure for managing four basic types of resources, namely process, file, memory, and I/O, in the same way they are routinely managed by operating systems. The proposed framework allows P2P systems to use dynamically reconfigurable resource management mechanisms where each machine in the P2P system can at the same time serve both as a server and as a client. The pattern of requests for shared resources at a given time identifies which machines are currently servers and which ones are currently clients. The client server pattern changes with changes in the pattern of requests for distributed resources. Scalable P2P systems with dynamically reconfigurable structures can thus be built using our proposed resource management mechanisms. This dynamic structure also allows for the interoperability of different P2P systems.     

工程数据库管理系统OSCAR的页面服务器

为了适应工程应用的特点，工程数据库管理系统OSCAR采用了页面服务器体系结构．OSCAR的页面服务器集中实现了数据库管理系统核心的事务管理，即并发控制和恢复功能．它向客户端提供支持多用户共享的、可靠的数据页面服务，客户端模块在此基础上构建一个功能完备的工程数据库管理系统．介绍了设计与实现OSCAR页面服务器过程中碰到的问题及其解决方法，包括OSCAR页面服务器的功能在物理层、缓冲层和事务层的分配，客户／服务器环境中ARIES恢复策略的改进以及先写日志文件原则的实现方案。     

An adaptive framework for 3D graphics over networks

Access to and transmission of 3D models over networks becomes increasingly popular. However, the performance and quality of access to remote 3D models strongly depends on system load conditions and the capabilities of the various system components, such as clients, servers, and interconnect. The network graphics framework (NGF) integrates various transmission methods for downloading 3D models in a client–server environment. The NGF automatically selects the optimal transmission method for a given pair of client and server, taking into account characteristics of the model to be transmitted, critical environment conditions, user preferences and the capabilities of the client and the server. The NGF aims to provide constant quality of service across different clients and under varying environment conditions.     

一种新的视频点播方案——扩展幂级方案

提出一种适合于热门节目的分块广播(partition broadcasting)方案——扩展幂级方案，分析了该方案的资源需求包括服务器信道、用户端缓存、用户端I／O带宽等，并根据方案的周期性分析了用户点播时间与缓存空间及用户端I／O带宽的关系．结论表明它比现有的许多其它同类方案有着更好的兼容性，能很好地权衡用户端的I／O带宽及缓存空间，而且更易于实现。     

A novel resource allocation mechanism for live cloud-based video streaming service

With the recent emergence of cloud computing, growing numbers of clients are using online cloud services through the Internet such as video streaming service. The rent costs of cloud service providers increase when the resource utilizations of the cloud-servers are not well. Therefore, resource allocation is a crucial problem for cloud data centers. The resource allocation problem is an NP-hard problem. This paper proposes a novel cloud resource allocation mechanism based on a winning strategy for a Nim game. This mechanism offers all clients an effective number of running cloud servers, and allocates cloud resources rapidly and effectively by using a pre-pairing approach. The proposed mechanism does not require searching for remaining resources of the running cloud server; hence, it can reduce the time taken to arrange resources. The experimental results show that the proposed mechanism can improve utilization of cloud servers and reduce the rent costs of the cloud service providers. The proposed mechanism can reach the utilization of cloud servers by as much as 99.96 %. The proposed mechanism is approximately 9 % more efficient than the market-based grid resource allocation algorithm, and 19 % more efficient than the modified best fit decreasing algorithm.

     

一种基于节的视频服务器允许接纳控制算法

提出了一种基于“服务器节”的支持压缩多媒体流的服务器中CPU、磁盘、网络和内存等资源管理的方法和允许接纳控制算法。“服务器节”概念定义了一组客户视频服务特性,如播放、快进、慢进和暂停等,并且确定了视频服务所需资源的分配参。一个“服务器节”包括视频服务器、磁盘设备、网络设备和允许接纳控制。它不但能优化使用单个资源,对于给定系统支持最大数量的客户端,保证其服务质量（QoS),而且其允许接纳控制算法能根据系统所有资源的状况,在不影响原有的视频服务基础上,确定对客户端新提出的视频服务是否接受。