Server based aggregation schemes are important for scalable delivery of interactive VoD content to heterogeneous end-clients with varying memory and storage capacities. In this chapter, we described the modeling of service aggregation by server-side stream clustering in i-VoD systems. We investigated various optimality criteria arising in stream clustering in video-on-demand, and then identified an optimal algorithm (RSMA-slide) with time complexity O(n3) for the "static stream clustering" problem. We also modeled a restricted version of the dynamic clustering problem (with user arrivals and interactions) by a general RSMA which has been recently proven to be NP-complete. Because the general RSMA formulation in the interactive case requires unreasonable assumptions and does not yield a polynomial time solution, we have modeled the dynamic problem using iterative invocation of the optimal algorithms applicable in the static case.
We demonstrated full-scale simulations of the dynamic scenario with users entering, interacting and leaving the system. In the simulations, we performed six different aggregation policies and compared their clustering gains in the steady-state. We investigated each policy for several re-computation intervals (W), arrival and interaction rates (λarr and λint respectively), and observed that a particular policy performs at its best at different values of W, λarr and λint. Although EMCL_RSMA and its heuristic counterpart perform equally well in most situations, RSMA-slide outperforms its heuristic counterpart by a large margin because of the larger number of streams in a snapshot.
Also shown was an attempt to use stochastic dynamic programming to model the dynamic, interactive scenario, but ran into difficulties due to computational complexity. Although we were able to craft a closed-form representation of the short-term cost due to merging between two successive events, we were unable to characterize the long-term cost in this study. Unfortunately, optimization with short-term cost as the objective does not yield satisfactory results. However, we remain hopeful that further investigation in this direction can result in the discovery of a good long-term cost formulation.
We observed that periodic invocation of the RSMA-slide clustering algorithm with a small recomputation interval produces best results under moderately high rates of arrival and interactions. Its O(n3) time-complexity is also justified because it is invoked only once in a recomputation period that is of the order of tens of seconds to a few minutes, and also because it yields much better gains than does its heuristic version. We analytically approximated channel usage due to RSMA-slide in non-interactive situations as a function of R, and then showed by simulation that its performance degrades linearly with increase in R; the analysis and simulation results were in reasonable agreement with each other.
Under high rates of arrival and interaction, we showed that RSMA with large re-computation periods yields highly suboptimal results, and heuristics that react to every event have superior performance. A greedy heuristic like GM may result in a much larger number of undesirable rate changes in the system. We also evaluated the performance of other variants of the RSMA-slide algorithm and found that the event-triggered RSMA and RSMA-Slide with R = 1/λa perform almost equally well. The event-triggered version performs well at the cost of a higher computational overhead. Hence we choose RSMA-slide with low to medium re-computation intervals to be the best overall clustering policy in moderately interactive situations. R can be tuned by the system designer to balance the trade-off between optimality and computational overhead.
There are a variety of unsolved problems related to the work described herein. Future work will consider the feasibility and complexity of distributed clustering schemes and the clustering of streams served from geographically displaced servers. If logical channels are not independent and share a common medium like IP multicast, new stream creation can impact existing streams. Specifically we have assumed QoS in-elasticity; interaction of these algorithms in the presence of heterogeneous and layered streams is interesting. Another important issue that remains to be resolved before clustering schemes can be deployed in practice is seamless splicing of video frames compounded by network delays and delays introduced by inter-frame coding as in MPEG. Moreover, blocking of users due to depletion of channels is not considered here; however, blocking and service denial is inevitable in a system with finite resources and its probability has to be minimized.