Experiences in Modeling Dynamic Service Aggregation in Interactive Video-on-Demand Systems

AbstractSupporting independent VCR-like interactions in true video-on-demand systems is resource intensive and in theworst case requires a separate channel for each user. A variety of techniques have been proposed to reduce resourcerequirements by aggregating users into groups. Clustering of users by bridging the temporal skews between them isone such service aggregation technique. We present some recurrent problems in stream clustering and investigateoptimal solutions with the main goal of minimizing average bandwidth. We show that for dynamic interactivescenarios where streams can break away from clusters, given perfect prediction, the problem is isomorphic tothe Rectilinear Steiner Minimal Arborescence (RSMA) problem which has been recently proved to be NP-hard.Since the RSMA model relies on some unrealistic assumptions, we investigate some heuristic techniques, whichare essentially periodic invocations of the statically optimal algorithm, and show results of their performanceevaluation. We demonstrate that the heuristic algorithms perform reasonably well in dynamic situations. Thesealgorithms are general across a large class of implementation architectures and aggregation techniques.We also attempt to model the interactive VoD system using stochastic dynamic programming and develop anaverage cost formulation. However, hugeness of the state space makes the optimization problem impractical, andwe resort to other variants of RSMA such as predictive RSMA, and periodic RSMA with the same frequency asthat of the mean of aggregate event process. We show that the former does not improve performance by much,and the latter performs better than other variants of the algorithm.Keywords: Interactive video-on-demand, dynamic service aggregation, stream clustering, dynamic programming.