Chapter 37: Server-Based Service Aggregation Schemes for Interactive Video-on-Demand

Prithwish Basu, Thomas D. C. Little, Wang Ke, and Rajesh Krishnan
Department of Electrical and Computer Engineering
Boston University
8 Saint Mary's St., Boston, MA 02215, USA
{pbasu,tdcl,ke,krash}@bu.edu

1. Introduction

Interactive video-on-demand (i-VoD or VoD) describes one of the most attractive applications that has been proposed since the rapid advances in high-speed networking and digital video technology. Principal deterrents to the widespread deployment of i-VoD services are the cost of data storage, server and network capacity to the end user. In the worst case, support of independent VCR-like interactions requires a separate channel for each user. Because of the data-intensive and streaming nature of video data, fully provisioned interactive channels are prohibitively expensive to deploy. Service aggregation schemes attempt to alleviate these problems by sharing both server and network resources at the expense of small overheads in terms of delay and/or buffer space. These techniques propose to reduce resource requirements by aggregating users into groups. Many such techniques exist in the VoD literature (some of them only support non-interactive VoD) - batching [6], server caching [22,7], client caching or bridging [1] and chaining [20] (a limited form of distributed caching), adaptive piggybacking or rate adaptive merging [12], content insertion [17,23], content excision [23], periodic broadcasting [14], patching [13,8], and catching [10] to name a few. Table 37.1 illustrates the relative merits of these schemes.

Table 37.1: Taxonomy of Service Aggregation Schemes in VoD

Service Aggregation Scheme	Entity that performs aggregation	Initial Start-up Latency	Interactions Allowed?	Client Buffering Required?	Network Bandwidth Gains
Batching	Server	Significant	No (possible w/contingency channels)	Minimal	High
Interval Caching	Server	No	Possible	Minimal	Saves disk b/w only
Chaining	Client	Yes	Yes	Yes (distributed)	Moderate to High
Adaptive Piggyback (RateAdaptive Merging)	Server (client only switches multicast gr.)	No	Yes (unrestricted)	Minimal	Moderate
Periodic Broadcast	Server/Client (only for very popular movies)	Yes broadcast series dependent	No	Significant	Moderate to High broadcast series dependent
Patching	Server/Client	Yes	Yes	Significant	Moderate
Selective Catching	Server/Client	No	Yes	Significant	Moderate to High

A major bottleneck in the delivery of video is on the disk-to-server path. Interval-Caching solutions [7] attempt to minimize the bandwidth required on this path by caching intervals of video between successive disk accesses and then by serving subsequent requests from the cache. These schemes do not, however, attempt to minimize the network bandwidth on the subsequent server-to-client path.

Clustering schemes, in contrast, seek to minimize this network bandwidth by aggregating channels that are identical except for their potentially disparate start times. That is, they are "aggregatable" if their skew is within some bound, or their skew can be eliminated. ^[1] Batching is a clustering technique in the near-VoD scenario, in which users must wait until the next launch of a stream occurs. A more attractive technique for the end user is a technique called rate adaptive merging [12,16] in which a user acquires a stream without any waiting time; however, the system attempts to aggregate streams within a skew bound by minimally altering the "content progression rates" of a subset of these streams. Experiments have shown that speeding up a video stream by approximately 7% does not result in a perceivable difference in visual quality [17,4], giving credibility to this approach. A trailing stream, or streams, can be accelerated towards a "leading" stream, or streams, until both of them are at the same position in the program (or equivalently, their skews are zero) [16]. At this instant of zero skew, all users attached to the stream (e.g., via multicasting to multiple destinations and users) are served by a single stream from the video source.

Both batching and rate adaptive merging have the advantage of having the burden of implementation fall mainly on the server and partly on the network (through the ability to support multicast), with no extra requirement on the client except that it be able to display the data received and send back control signals (to make requests and perform VCR-like operations). This means that potentially "true-VoD" service can be extended even to wireless handheld devices that do not have a large storage capacity but which are connected to the network. Client based aggregation schemes that require clients to buffer video from multiple staggered broadcast channels [14,13,8] are thus unsuitable for heterogeneous pervasive computing environments.

It is also desirable to reduce the buffering requirement for interval caching schemes. This requirement is dependent on the skews between streams carrying the same content. Therefore, bridging the skew and/or reducing the number of streams by clustering can also reduce the memory requirement of a caching scheme. A continuum of aggregation schemes that lie between pure caching and pure clustering exists. Tsai and Lee [23] explore this relationship in the near-VoD scenario. Therefore, one can extend solutions for clustering to buffer management and vice versa. In this chapter, we focus on clustering schemes.

In hybrid CATV architectures that consist of the standard broadcast delivery mechanism augmented with on-demand channels, stream merging is used in schemes like Catching [10] in order to reclaim the on-demand channels. The described clustering algorithms are applicable in such scenarios as well.

The scope for aggregation of video streams is ameliorated by the long-lived nature of video traffic and the high density of accesses on popular titles (e.g., hit movies) during certain times of the day. By clustering streams during peak periods, a system can accommodate a much larger number of users than without aggregation, thus increasing potential revenue earned. Therefore, in any VoD system where peak demands are higher than the available bandwidth, aggregation schemes are attractive. This is particularly true of scenarios that commonly arise with Internet traffic and content. For example, when a popular news item is made available by a news provider, the peak demand can far outstrip the available network bandwidth, thus making aggregation increasingly attractive.

Because resource sharing by aggregating users is a promising paradigm for VoD systems supporting large user populations, it is useful to study its inherent complexity. Irrespective of whether we are trying to use rate adaptive merging or content insertion or using "shrinking" to reduce buffer usage for caching, the underlying clustering problem remains the same. In this chapter, we take a systematic approach to formulating these clustering problems and discuss the existence of optimal solutions. These algorithms are general across a large class of implementation architectures as well as aggregation techniques.

From a performance engineering standpoint, one must not lose sight of the fact that simpler solutions while provably sub-optimal can at times be preferable due to simplicity, elegance or speed. Often, they can be necessitated by the fact that optimal solutions are computationally expensive or intractable. In such cases, the engineering approach is to seek good approximate or heuristic alternatives that provide near-optimal solutions. With this in mind, we present optimal solution approaches and also investigate when such sophisticated algorithms are warranted by the application under consideration. In the "static" version of the problem, clusters of users receiving the same video content are formed but it is assumed that the users cannot break away after their streams have been merged with others in a cluster. If we allow the users to break away from their clusters by interacting, the gains due to aggregation will be lost. Hence, dynamic approaches are necessary for handling these interactive situations. We present some such approaches and also explore how far the gains from an optimal solution in the static case are retained in dynamic scenarios. Our performance results can be readily applied to the related capacity planning and design problem; that is, given the mean arrival (and interaction) rate and distribution, what should the design capacity be, in number of streams, of a video-server network which actively uses service aggregation?

We transform the static clustering problem (with the objective of minimizing average bandwidth) to the RSMA-slide problem (terminology used by Rao et al. [19]). An important observation here is that an RSMA-slide on n sinks is isomorphic to an optimal binary tree on n leaf nodes. Aggarwal et al. have described an optimal binary tree formulation in reference [2], but we describe a more general approach that can model additional interactive scenarios. By periodically recomputing the RSMA-slide with a small period, we can reclaim up to 33% of channel bandwidth when there are 1,250 interacting users in the system watching 100 programs, in steady state. We compare the RSMA-slide algorithm with other heuristic approaches and find it to be the best overall policy for varying arrival and interaction rates of users. We also find that under server overload situations, EMCL-RSMA (forming maximal clusters followed by merging by RSMA-slide in the clusters) is the best policy as it releases the maximum number of channels in a given time budget, consuming minimum bandwidth during the process. We also investigate some variants of the RSMA-slide algorithm such as event-triggered RSMA, Stochastic RSMA, etc. and compare their performance with the RSMA-slide.

Related work

The static stream clustering problem has been studied by Aggarwal et al. [2] and Lau et al. [18]. The latter provides a heuristic solution for the problem while the former discusses an optimal solution based on binary trees. Neither discuss how to accommodate user interactions although Aggarwal et al. consider implications of user arrivals. Basu et al. investigate the stream clustering problem from a user arrival/interaction standpoint with early performance results [3].

An important contribution of this work is the inclusion of user arrivals and interactions into the stream clustering model and showing that iterative application of optimal static algorithms in a controlled fashion can preserve most of the gains in dynamic interactive situations too. We use a different problem formulation that allows us to model most interactive situations although in the static case it reduces to the optimal binary tree formulation in [2]. We point out that the problem of freeing maximum number of channels under server-overload is different from the minimum bandwidth clustering problem and that our algorithm Earliest Maximal Clustering, also known as EMCL [17] is optimal in the static case. We show performance simulations over a wide range of parameters and a number of different clustering policies. We also demonstrate that the optimal re-computation period depends not only on the rates of arrival and interaction but also on the specific policy used.

Another contribution of this work is an attempt to formulate the dynamic stream clustering problem as a Stochastic Dynamic Programming problem, although that resulted in a few negative results. To the best of our knowledge, this is the first approach of its kind in this domain, and we believe that our preliminary findings will spur the VoD research community to find better solutions in this space. We also present an approximate analytical technique for predicting the average number of streams in such an aggregation system in steady state, and demonstrate that the analytical results are reasonably close to the simulation results.

The remainder of the chapter is organized as follows. In Section 2, we formulate the clustering problem mathematically, and consider optimal algorithmic solutions. Section 3 introduces a stochastic dynamic programming approach to tackle the dynamic stream clustering problem. In Section 4 we present the results of simulations of heuristic and approximate algorithms for clustering. In Section 5 we conclude with our recommendations of clustering algorithms that should be used for aggregation in interactive VoD systems.

^[1]Skew is defined as the difference in program positions at current instant of time of two video streams containing the same program.