47152006
Optimal proxy cache allocation for efficient streaming media distribution
We address the problem of efficiently streaming a set of heterogeneous videos from a remote server through a proxy to multiple asynchronous clients so that they can experience playback with low startup delays. We determine the optimal proxy prefix cache allocation to the videos that minimizes the aggregate network bandwidth cost. We integrate proxy caching with traditional server-based reactive transmission schemes such as hatching, patching and stream merging to develop a set of proxy-assisted delivery schemes. We quantitatively explore the impact of the choice of transmission scheme, cache allocation policy, proxy cache size, and availability of unicast versus multicast capability, on the resulting transmission cost. Our evaluations show that even a relatively small prefix cache (10%-20% of the video repository) is sufficient to realize substantial savings in transmission cost. We find that carefully designed proxy-assisted reactive transmission schemes can produce significant cost savings even in a predominantly unicast environment such as the Internet.
17022940
Using Windows NT for Real-Time Applications: Experimental Observations and Recommendations
Windows NT was not designed as a real time operating system, but market forces and the acceptance of NT in industrial applications have generated a need for achieving real time functionality with NT. As its use for real time applications proliferates, based on an experimental evaluation of NT, we quantitatively characterize the obstacles placed by NT. As a result of these observations, we provide a set of recommendations for users to consider while building real time applications on NT. These are validated by the use of NT for a prototype application involving real time control that includes multimedia information processing. The results of the above study should provide system designers with guidelines, as well as insight, into the design of an architecture based on NT for supporting applications with components having real time constraints.
2225573
Integrated scheduling of multimedia and hard real-time tasks
An integrated platform which is capable of meeting the requirements of both traditional real-time control processing and multimedia processing has enormous potential for accommodating various kinds of new applications. However, except for the simplest of situations, few, if any, research or commercial systems successfully provide architectural and OS mechanisms which can efficiently support both hard real-time computation and multimedia soft real-time computation. The authors propose a multimedia server execution on multiprocessor real-time operating systems to provide different classes of guarantee to support both types of processing. The multimedia server supports multiple periodic multimedia streams with a capability for graceful QoS degradation during system overload. They (i) develop several multimedia server scheduling algorithms, (ii) evaluate the performance of these algorithms, and (iii) discuss realistic system implementation issues on the SGI IRIX/REACT/PRO operating system.
2290480
Optimal multicast smoothing of streaming video over an internetwork
A number of applications such as internet video broadcasts, corporate telecasts, distance learning etc. require transmission of streaming video to multiple simultaneous users across an internetwork. The high bandwidth requirements coupled with the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for transmitting streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques which can efficiently deliver streaming video to multiple heterogeneous clients across a heterogeneous internetwork. We propose using multicasting of smoothed video and differential caching of the video at intermediate nodes in the distribution tree, as techniques for reducing the network bandwidth requirements of such dissemination. We formulate the multicast smoothing problem, and develop an algorithm for computing the set of optimally smoothed transmission schedules for the tree (such that the transmission schedule along each link in the tree has the lowest peak rate and rate variability for any feasible transmission schedule for that link) given a buffer allocation to the different nodes in the tree. We also develop an algorithm to compute the minimum total buffer allocation to the entire tree and the corresponding allocation to each node, such that feasible transmission is possible to all the clients, when the tree has heterogeneous rate constraints. MPEG-2 trace-driven performance evaluations indicate that there are substantial benefits from multicast smoothing and differential caching. For example, the optimal multicast smoothing can reduce the total transmission bandwidth requirements in the distribution tree by more than a factor of 3 as compared to multicasting the unsmoothed stream.
1578205
Broadcast on demand: efficient and timely dissemination of data in mobile environments
The demand for efficient scalable and cost effective mobile information access systems is rapidly growing. Radiofrequency broadcast plays a major role in mobile computing, and there is a need to provide service models for broadcasting information according to mobile users' needs. The authors present a model called broadcast on demand (BoD), which provides timely broadcasts according to requests from users. Compared to static broadcast, this approach has a different emphasis: it is based on a demand driven framework, aimed at satisfying the temporal constraints of the requests, and uses scheduling techniques at the server side to utilize the limited bandwidth dynamically and efficiently. Several broadcast transmission scheduling policies for BoD are examined. The study indicates that EDF-based policies combined with batching of requests achieve good performance. The results show that BoD is successful in satisfying the temporal constraints of the requests and is a viable service model for wireless broadcast stations.
6084623
Proxy prefix caching for multimedia streams
High latency and loss rates in the Internet make it difficult to stream audio and video without introducing a large playback delay. To address these problems, we propose a prefix caching technique whereby a proxy stores the initial frames of popular clips. Upon receiving a request for the stream, the proxy initiates transmission to the client and simultaneously requests the remaining frames from the server. In addition to hiding the delay, throughput, and loss effects of a weaker service model between the server and the proxy, this novel yet simple prefix caching technique aids the proxy in performing workahead smoothing into the client playback buffer. By transmitting large frames in advance of each burst, workahead smoothing substantially reduces the peak and variability of the network resource requirements along the path from the proxy to the client. We describe how to construct a smooth transmission schedule, based on the size of the prefix, smoothing, and playback buffers, without increasing client playback delay. Experiments with MPEG traces show how a few megabytes of buffer space at the proxy can substantially reduce the bandwidth requirements of variable-bit-rate video. Drawing on these results, we present guidelines for allocating buffer space for each stream, and how to effectively share buffer and bandwidth resources among multiple clients and streams.
35225520
Some Observations on Skip-Lists
The Skip-list data-structure was proposed by Pugh as an alternate to balanced binary search trees. This remarkably simple data-structure uses randomization and Pugh proved that the expected performance is comparable to the balanced trees. In this note we prove that the performance can be further guaranteed in the following sense: the probability of the search time or space complexity exceeding their expected values, approaches 0 rapidly as the number of keys increases.
790181
Predicting agent strategy mix of evolving populations
We study agent societies where self-interested agents interact repeatedly over extended time periods. In particular, we are interested in environments where agents can form mutually beneficial relationships by exchanging help but an agent would rather receive help than give it. Evolutionary tournaments with competing help-giving strategies can model scenarios where agents periodically adopt strategies that are outperforming others in the population. Such experiments, however, can be computationally costly and hence it is difficult to prescribe a rational strategy choice given environmental conditions like task mix, strategy distribution in the population, etc. A preferred approach, pursued in this paper, is to analytically capture the dynamics of the strategy mix in the population under an evolutionary tournament. Such an analytical model can be used to predict the evolutionarily dominant strategy, the rational strategy choice.
8938271
Kernel-Based Reinforcement Learning
We present a kernel-based approach to reinforcement learning that overcomes the stability problems of temporal-difference learning in continuous state-spaces. First, our algorithm converges to a unique solution of an approximate Bellman's equation regardless of its initialization values. Second, the method is consistent in the sense that the resulting policy converges asymptotically to the optimal policy. Parametric value function estimates such as neural networks do not possess this property. Our kernel-based approach also allows us to show that the limiting distribution of the value function estimate is a Gaussian process. This information is useful in studying the bias-variance tradeoff in reinforcement learning. We find that all reinforcement learning approaches to estimating the value function, parametric or non-parametric, are subject to a bias. This bias is typically larger in reinforcement learning than in a comparable regression problem.
6305829
Online Smoothing of Variable-Bit-Rate Streaming Video
Bandwidth smoothing techniques for stored video perform end to end workahead transmission of frames into the client playback buffer, in advance of their display times. Such techniques are very effective in reducing the burstiness of the bandwidth requirements for transmitting compressed, stored video. This paper addresses online bandwidth smoothing for a growing number of streaming video applications such as newscasts, sportscasts, and distance learning, where many clients may be willing to tolerate a playback delay of a few seconds in exchange for a smaller bandwidth requirement. The smoothing can be performed at either the source of the videocast or at special smoothing server(s) (e.g., proxies or gateways) within the network. In contrast to previous work on stored video, the online smoothing server has limited knowledge of frame sizes and access to only a segment of the video at a time. This is either because the feed is live or because it is streaming past the server. We formulate an online smoothing model which incorporates playback delay, client and server buffer sizes, server processing capacity, and frame size prediction techniques. Our model can accommodate an arbitrary arrival process. Using techniques for smoothing stored video at the source as a starting point, we develop an online, window-based smoothing algorithm for delay tolerant applications. Extensive experiments with MPEG-1 and M-JPEG video traces demonstrate that online smoothing significantly reduces the peak rate, coefficient of variation, and effective bandwidth of variable-bit-rate video streams. These reductions can be achieved with modest playback delays of a few seconds to a few tens of seconds and moderate client buffer sizes, and closely approximate the performance of optimal offline smoothing of stored video. In addition, we show that frame size prediction can offer further reduction in resource requirements, though prediction becomes relatively less important for longer playback delays. However, the ability to predict future frame sizes affects the appropriate division of buffer space between the server and client sites. Our experiments show that the optimal buffer allocation shifts to placing more memory at the server as the server has progressively less information about future frame sizes.
3054792
Towards a theory of cache-efficient algorithms
We present a model that enables us to analyze the running time of an algorithm on a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our cache model, an extension of Aggarwal and Vitter's I/O model, enables us to establish useful relationships between the cache complexity and the I/O complexity of computations. As a corollary, we obtain cache-efficient algorithms in the single-level cache model for fundamental problems like sorting, FFT, and an important subclass of permutations. We also analyze the average-case cache behavior of mergesort, show that ignoring associativity concerns could lead to inferior performance, and present supporting experimental evidence.We further extend our model to multiple levels of cache with limited associativity and present optimal algorithms for matrix transpose and sorting. Our techniques may be used for systematic exploitation of the memory hierarchy starting from the algorithm design stage, and for dealing with the hitherto unresolved problem of limited associativity.