A set of applications such as Internet video broadcasts, corporate telecasts, and distance learning require the simultaneous streaming of video to a large population of viewers across the Internet. The high bandwidth requirements and the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques to efficiently stream video to a large number of disparate clients across a heterogeneous Internet. In this paper, we propose to multicast smoothed video over an application-level overlay network of proxies, and to differentially cache the video at the intermediate nodes (proxies) in the distribution tree, in order to reduce the network bandwidth requirements of video dissemination. We formulate the multicast smoothing problem as an optimization problem, and develop an algorithm for computing the set of transmission schedules for the tree that minimize the peak rate and rate variability, given buffer constraints at different nodes in the tree. We also develop an algorithm to compute the minimum buffer allocation in the entire tree, such that feasible transmission to all the clients is possible, when the tree has heterogeneous rate constraints. We show through trace-driven simulations that substantial benefits are possible from multicast smoothing and differential caching, and that these gains can be realized even with modest proxy caches.

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.

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.

We consider a real time task model where a task receives a "reward" that depends on the amount of service received prior to its deadline. The reward of the task is assumed to be an increasing function of the amount of service that it receives, i.e., the task has the property that it receives increasing reward with increasing service (IRIS). We focus on the problem of online scheduling of a random arrival sequence of IRIS tasks on a single processor with the goal of maximizing the average reward accrued per task and per unit time. We describe and evaluate several policies for this system through simulation and through a comparison with an unachievable upper bound. We observe that the best performance is exhibited by a two level policy where the top level algorithm is responsible for allocating the amount of service to tasks and the bottom level algorithm, using the earliest deadline first (EDF) rule, is responsible for determining the order in which tasks are executed. Furthermore, the performance of this policy approaches the theoretical upper bound in many cases. We also show that the average number of preemptions of a task under this two level policy is very small.

Providing smooth playback capabilities for video servers, which must support potentially thousands of on-demand users, has been an area of active research. From a user's perspective, VCR functions of fast-forward and rewind (FF/Rew), are desirable features in video-on-demand. But FF/Rew at n times the regular playback rate requires n times the regular playback bandwidth from architectural components of the video server. Thus, guaranteeing sufficient bandwidth to enable users to perform FF/Rew reduces the number of supportable users by a factor of n. In this paper we propose an alternative, effective FF/Rew service, which provides FF/Rew capabilities with an associated statistical quality-of-service (QoS) guarantee. This service provides immediate access to full-resolution FF/Rew bandwidth with high probability. When bandwidth is not available, service is either delayed or provided immediately but with a loss in resolution. In addition, we specify several QoS metrics to characterize the delay or loss experienced by a FF/Rew request. We show that using effective FF/Rew with statistical guarantees on these QoS metrics results in a significant increase in the number of supportable users, when compared to systems in which FF/Rew bandwidth is statistically reserved for each user. Moreover, a playback-only video server can be extended to provide FF/Rew service by reserving only a small portion of its total bandwidth, which is dynamically shared among FF/Rew requests.

In this paper we consider the problem of on-line scheduling of real-time tasks which receive a that depends on the amount of service received. In our model, tasks have associated deadlines at which they must depart the system. The task computations are such that the longer they are able to execute before their deadline, the greater the value of their computations, i.e., the tasks have the property that they receive increasing reward with increasing service (IRIS). We focus on the problem of scheduling IRIS tasks in a system in which tasks arrive randomly over time, with the goal of maximizing the average reward accrued per task and per unit time. We describe and evaluate a two-level policy for this system. A top-level algorithm executes each time a task arrives and determines the amount of service to allocate to each task in the absence of future arrivals. A lower-level algorithm, an earliest deadline first (EDF) policy in our case, is responsible for the actual selection of tasks to execute. This two-level policy is evaluated through a combination of analysis and simulation, We observe that it provides nearly optimal performance when the variance in the interarrival times and/or laxities is low and that the performance is more sensitive to changes in the arrival process than the deadline distribution.