Collaborative multi-step mono-level multi-strategy classification

In this paper, we address the problem of retrieving a movie from a set of multimedia(MM) servers by the clients on a network. We consider a strategy in which multiple MM servers are deployed by the service provider (SP) to retrieve a requested MM movie to the clients, for minimizing the access time (the waiting time of the client before initiating the playback) and maximizes the system reliability. We design a movie retrieval strategy that explicitly considers issues such as reliability and/or availability factors of the multimedia servers and the communication channels in the problem formulation. We develop a mathematical model for this retrieval strategy and derive an optimal size of each movie portion that is expected to be rendered by each server. We then derive a closed-form expression for the access time of the MM document and the system reliability which gives a trade-off relationship between access time and reliability (availability) of the service by our strategy. We extend our study to investigate on the effect of sequencing of the servers, the order in which movie portions are to be retrieved, to minimize the access time and to maximize the system reliability. With system reliability factors, we identify an optimal sequence, which maximizes system reliability out of all possible retrieval sequences. We then propose two methods to retrieve any missing movie portions upon a server failure during the retrieval process. In order to measure the quality of service provided by the service provider to its customers, we introduce a QoS parameter that can tune the playback rate to avoid any data underflow or overflow situations. Then, from probabilistic perspective, we obtain an estimate of the failure time of a single server and its resulting missing movie portion caused by this server failure. We conduct rigorous simulation experiments to testify all the theoretical findings reported. Illustrative examples are provided for the ease of understanding.     

Multiple-server movie-retrieval strategies for distributed multimedia applications: a play-while-retrieve approach

In this paper, we present a generalized approach to retrieve a long-duration movie requested using a network-based video-on-demand service infrastructure employing multiple servers. We design and analyze a play-while-retrieve (PWR) playback strategy for this multiserver environment such that the access time (waiting time for the clients) is minimized. For this strategy, we use both the single-installment and multi-installment retrieval strategies to analyze the performance of the service system. For the above-mentioned retrieval strategies, we explicitly derive closed-form expressions for a minimum access time. For the case of multi-installment retrieval strategy, we conduct asymptotic performance analysis that quantifies the ultimate performance bounds of our strategy. We demonstrate analytically the impact of a large-scale network, as well as the impact of indefinitely increasing the number of installments, on the performance of such a multiserver service system. We then address the problem of buffer management at the client site, which is a closely related issue that has a significant influence on the performance of the strategy, and also serves as a key issue in making the service system attractive for clients. We derive relationships that quantify the minimum amount of buffer expected at the client site to have a smooth presentation with this multiserver service structure. Finally, we perform simulation experiments to verify all our theoretical findings. In the experiments, we compare the performance of PWR strategy with that of play-after-retrieve strategy, and discuss certain important points that are crucial for implementing a real-life working multiserver service system.     

Efficient Movie Retrieval Strategies for Movie-on-Demand Multimedia Services on Distributed Networks

In this paper, for a network-based multimedia Video/Movie-on-demand(VoD/MoD) service, we design and analyze efficient retrieval strategies to minimize both the access times of the movies and the block rates. We consider a heterogeneous set of servers and a generic network topology in which clients can request for movies from any site. We design and analyze a multiple servers retrieval strategy (MSRS) to retrieve the movies requested by the clients and present a rigorous analysis on its performance with respect to access times of the requested movies and the block rates. A generalized approach of MSRS is designed in a judicious manner using a two-step approach. In the first step, we partition the available bandwidth among the requested movies and in the second step, we derive optimal portions of the movies to be retrieved from each of the servers for each movie, based on allocated bandwidths in the first step. Thus, with the optimal playback portions of the movies using aggregate retrieval bandwidth from several servers, the access times of the movies are minimized. In the first step, in addition to the access times, we minimize the block rates by balancing the total accesses/requests among the servers. In generating the retrieval schedule, our scheme utilizes the available bandwidth (resource) among the servers and guarantees to use less buffer space than a single server retrieval strategy (SSRS). With this two-step approach, a complete flexibility is provided in tuning the access times of the movies and also shown to be robust to any variations in the user access rates of the movies, in reality. Rigorous simulation experiments are presented to observe the performance of MSRS with respect to some important system dependent parameters. Comparing with SSRS, MSRS shows better performance in the simulation.     

Optimized distributed delivery of continuous-media documents over unreliable communication links

Video-on-demand (VoD) applications place very high requirements on the delivery medium. High-quality services should provide for a timely delivery of the data-stream to the clients plus a minimum of playback disturbances. The major contributions of this paper are that it proposes a multiserver, multi-installment (MSMI) solution approach (sending the document in several installments from each server) to the delivery problem and achieves a minimization of the client waiting time, also referred to as the access time (AT) or start-up latency in the literature. By using multiple spatially distributed servers, we are able to exploit slow connections that would otherwise prevent the deployment of video-on-demand-like services, to offer such services in an optimal manner. Additionally, the delivery and playback schedule that is computed by our approach is loss-aware in the sense that it is flexible enough to accommodate packet losses without interrupts. The mathematical framework presented covers both computation and optimization problems associated with the delivery schedule, offering a complete set of guidelines for designing MSMI VoD services. The optimizations presented include the ordering of the servers and determining the number of installments based on the packet-loss probabilities of the communication links. Our analysis guarantees the validity of a delivery schedule recommended by the system by providing a percentage of confidence for an uninterrupted playback at the client site. This, in a way, quantifies the degree of quality of service rendered by the system and the MSMI strategy proposed. The paper is concluded by a rigorous simulation study that showcases the substantial advantages of the proposed approach and explores how optimization of the schedule parameters affects performance.     

A paracasting model for concurrent access to replicated Internet content

In this paper, we develop a model to study how to effectively download a document from a set of replicated servers. We propose a generalized application-layer anycasting protocol, known as paracasting, to advocate concurrent access of a subset of replicated servers to cooperatively satisfy a client's request. Each participating server satisfies the request in part by transmitting a subset of the requested file to the client. The client can recover the complete file when different parts of the file sent from the participating servers are received. This model allows us to estimate the average time to download a file from the set of homogeneous replicated servers, and the request blocking probability when each server can accept and serve a finite number of concurrent requests. Our results show that the file download time drops when a request is served concurrently by a larger number of homogeneous replicated servers, although the performance improvement quickly saturates when the number of servers increases. If the total number of requests that a server can handle simultaneously is finite, the request blocking probability increases with the number of replicated servers used to serve a request concurrently. Therefore, paracasting is effective when a small number of servers, say, up to four, are used to serve a request concurrently.     

Network caching strategies for a shared data distribution for a predefined service demand sequence

In this paper, we address the problem of minimizing the cost of transferring a document or a file requested by a set of users geographically separated on a network of nodes. We concentrate on theoretical aspects of data migration and caching on high-speed networks. Following the information caching paradigm introduced in the literature, we present polynomial time optimal caching strategies that minimize the total monetary cost of all the service requests by the users on a high-speed network. We consider a scenario in which a large pool of customers from one or more remote sites on a network demand a document, situated at some site, for their use. We also assume that the users can request the document at different time instants. This process of distributing the requested document incurs communication costs due to the use of communication resources and caching costs of the document at some server sites before it is delivered to the users at their desired time instances. We configure the network as a fully connected topology in which the service providers manage and control the distribution of the requested document among the users. For a high-speed network, we show that a single copy of the requested document is sufficient to serve all the user requests in an optimal manner. We extend the study to a homogeneous case in which the communication costs are identical and caching costs at all the sites are identical. In this case, we demonstrate the adaptability of the algorithm in generating more than one copy when needed by the minimization process. Using these strategies, the network service providers can decide when, where, and for how long the requested documents must be cached at vantage sites to obtain an optimal solution. Illustrative examples are provided to ease the understanding.     

Optimal state-free, size-aware dispatching for heterogeneous -type systems

We consider a cluster of heterogeneous servers, modeled as M/G/1 first-come first-serve queues with different processing speeds. A dispatcher that assigns jobs to the servers takes as input only the size of the arriving job and the overall job-size distribution. This general model captures the behavior of a variety of real systems, such as web server clusters. Our goal is to identify assignment strategies that the dispatcher can perform to minimize expected completion time and waiting time. We show that there exist optimal strategies that are deterministic, fixing the server to which jobs of particular sizes are always sent. We prove that the optimal strategy for systems with identical servers assigns a non-overlapping interval range of job sizes to each server. We then prove that when server processing speeds differ, it is necessary to assign each server a distinct set of intervals of job sizes in order to minimize expected waiting or response times.     

Application-Layer Protocol for Collaborative Multimedia Presentations

Many multimedia presentation applications involve retrieval of objects from more than one collaborating server. Presentations of objects from different collaborating servers might be interdependent. For instance, we can consider distributed video servers where blocks of movies are distributed over a set of servers. Here, blocks of a movie from different video servers have to be retrieved and presented continuously without any gaps in the presentation. Such applications first need an estimate of the available network resources to each of the collaborating server in order to identify a schedule for retrieving the objects composing the presentation. A collaborating server can suggest modifications of the retrieval schedule depending on its load. These modifications can potentially affect the retrieval schedule for other collaborating applications. Hence, a sequence of negotiations have to be carried out with the collaborating servers in order to commit for a retrieval schedule of the objects composing the multimedia presentation. In this paper, we propose an application sub-layer protocol, Resource Lock Commit Protocol (RLCP), for handling the negotiation and commitment of the resources required for a collaborative multimedia presentation application.     

Techniques for Scheduling I/O in a High Performance Multimedia-on-Demand Server

One of the key components of a multiuser multimedia-on-demand system is the data server. Digitalization of traditionally analog data such as video and audio, and the feasibility of obtaining network bandwidths above the gigabit-per-second range, are two important advances that have made possible the realization, in the near future, of interactive distributed multimedia systems. Secondary-to-main memory I/O technology has not kept pace with advances in networking, main memory, and CPU processing power. Consequently, the performance of the server has a direct bearing on the overall performance of such a system. In this paper, we present a highperformance solution to the I/O retrieval problem in a distributed multimedia system. We develop a model for the architecture of a server for such a system. Parallelism of data retrieval is achieved by striping the data across multiple disks. We present the algorithms for server operation when servicing a constant number of streams, as well as the admission control policy for accepting requests for new streams. The performance of any server ultimately depends on the data access patterns. Two modifications of the basic retrieval algorithm are presented to exploit data access patterns in order to improve system throughput and response time. Finally, we present preliminary performance results of these algorithms on the IBM SP1 and Intel Paragon parallel computers.     

一种基于Sever和Proxy流媒体流行性的Caching策略

1 概述经过了2000、2001两年的社区宽带网建设的高速发展后,摆在中国ISP们面前的任务是如何在已建成的宽带网上开展增值服务,许多ISP尝试在宽带网上开展流媒体(Streaming Media)服务,如视频点播VOD(Video On-Demand)系统。然而,流媒体对网络带宽和实时性的要求使得流服务器必须能够进行端对端(End-to-End)的拥塞控制和质量调整,由于     

种基于Sever和Proxy流媒体流行性的Caching策略

It is expected that by 2003, continuous media will account for more than 50% of the data available on origin servers. This will provoke a significant change in Internet workload, due to the high bandwidth requirements and the long-lived nature of digital video, streaming server loads and network bandwidths are proving to be major limiting factors. Aiming at the characteristic of broadband network in a residential area, we propose a popularitybased on server-proxy caching strategy for streaming media. According to a streaming media popularity on streaming server and proxy, this strategy caches the content of this streaming media partially or completely, and plays an important role in decreasing server load, reducing the traffic from streaming server to proxy, and improving the startup latency of the client.     

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.     

Task Allocation in a Multi-Server System

We consider a slotted queueing system with C servers (processors) that can handle tasks (jobs). Tasks arrive in batches of random size at the start of every slot. Any task can be executed by any server in one slot with success probability . If a task execution fails, then the task must be handled in some later time slot until it has been completed successfully. Tasks may be processed by several servers simultaneously. In that case, the task is completed successfully if the task execution is successful on at least one of the servers.We examine the impact of various allocation strategies on the mean number of tasks in the system and the mean response time of tasks. It is proven that both these performance measures are minimized by the strategy which always distributes the tasks over the servers as evenly as possible. Subsequently, we determine the distribution of the number of tasks in the system for a broad class of task allocation strategies, which includes the above optimal strategy as a special case. Some numerical experiments are performed to illustrate the performance characteristics of the various strategies.     

WebCompanion: a friendly client-side Web prefetching agent

Accessing remote sites of the World Wide Web is often a frustrating experience for users because of long Web page retrieval times even over relatively fast Internet connections. Users are more likely to embrace the further expansion of the role of the Web into a major infrastructure for electronic commerce and for information, application, and multimedia delivery if Web accesses can be accelerated. One technique that attempts this is prefetching. We built a client-side Java-implemented prefetching agent, WebCompanion, which employs a novel adaptive, fast, and selective online prefetching strategy based on estimated round-trip times for Web resources. This strategy efficiently hides the access latencies for slow resources while at the same time limiting the network and server overhead and local resource consumption to moderate levels. Our extensive experiments show an average access speedup of greater than 50 percent and an average network byte overhead of less than 150 percent using WebCompanion over a fast Internet connection. We measured a slight acceleration in accessing the Web through WebCompanion even in a pessimistic scenario where the user never requests a prefetched document     

视频服务器网络中影像对象映射问题的研究

视频服务器网络中的影像对象映射问题是一种新的组合优化问题.服务器网络可以建立在基于局域网的工作站网络之上,也可以建立在广域网之上.基于对用户的服务请求模式、服务器网络的存储容量和通信带宽等因素的综合考虑,研究了服务器网络中影像对象映射问题,利用局部搜索算法给出了一套对该映射问题的解决方案.然后用一套基准集实例对给出的算法集进行验证.结果表明,在较短的计算时间内,该算法可以得到近似最优解的方案.     

A simple distributed scheduling policy for parallel interactive continuous media servers

In this paper we discuss the design of parallel interactive continuous media servers suitable for the implementation of scalable server-based media delivery services like Video-on-Demand or Teleshopping. The main design problems for the development of such servers is to ensure the just-in-time delivery of media elements in order to maximize the Quality of Service and to minimize the buffer size at the user site. Just-in-time delivery means that the media elements should be sent as late as possible to the users but early enough to ensure a continuous replay of the media. This is important because clients have to provide buffer space for data arriving to early. The Quality of Service measures the number of data elements arrived in time at the user side. Thus, the real-time properties of the internal communication network as well as the congestion arising at the disks are of highest importance. We present models for parallel media servers and a very simple scheduler that is fully distributed and can therefore easily be implemented on a scalable parallel continuous media server. For each requested data element the scheduler sends a request to the storage subsystems at a point of time only depending on the deadline of that request, i.e. the time the data has to be delivered to the user, and the length of the path the data has to be routed through the internal network of the parallel server. In order to minimize the buffer space at the user site, and to maximize the Quality of Service, we develop timing strategies for the scheduler using simulation results as well as analytical observations.     

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.     

Optimal Content Distribution in Video-on-Demand Tree Networks

Video-on-demand (VOD) services are expected to grow significantly over time, providing diverse programs for home entertainment, distance instruction, news on demand, and other applications. These services require large bandwidth resources. We present a model for a tree network where each node may have demands for multiple different VOD program families, where each program family is an aggregation of similar programs. The decision variables include location of VOD servers and assignment of program families to servers. The model considers cost of servers, cost of assigning program families to servers, and cost of link bandwidths used to broadcast programs. The objective is to minimize the sum of all these costs. The model is formulated as an integer program. We develop a dynamic programming formulation with multiple state variables and an algorithm that solves this model. Starting from the end nodes of the tree network, the algorithm determines optimal solutions to subtrees, eventually reaching the root node with the central server, thus providing an optimal solution to the entire network.     

Design a progressive video caching policy for video proxy servers

Proxy servers have been used to cache web objects to alleviate the load of the web servers and to reduce network congestion on the Internet. In this paper, a central video server is connected to a proxy server via wide area networks (WANs) and the proxy server can reach many clients via local area networks (LANs). We assume a video can be either entirely or partially cached in the proxy to reduce WAN bandwidth consumption. Since the storage space and the sustained disk I/O bandwidth are limited resources in the proxy, how to efficiently utilize these resources to maximize the WAN bandwidth reduction is an important issue. We design a progressive video caching policy in which each video can be cached at several levels corresponding to cached data sizes and required WAN bandwidths. For a video, the proxy server determines to cache a smaller amount of data at a lower level or to gradually accumulate more data to reach a higher level. The proposed progressive caching policy allows the proxy to adjust caching amount for each video based on its resource condition and the user access pattern. We investigate the scenarios in which the access pattern is priorly known or unknown and the effectiveness of the caching policy is evaluated.     

Retrieval scheduling for collaborative multimedia presentations

The single-system approach is no longer sufficient to handle the load on popular Internet servers, especially for those offering extensive multimedia content. Such services have to be replicated to enhance their availability, performance, and reliability. In a highly replicated and available environment, server selection is an important issue. In this paper, we propose an application-layer broker (ALB) for this purpose. ALB employs a content-based, client-centric approach to negotiate with the servers and to identify the best server for the requested objects. ALB aims to maximize client buffer utilization in order to efficiently handle dynamic user interactions such as skip, reverse presentation, go back in time. We also present details of a collaborative multimedia presentation platform that we have developed based on ALB.