An Analytical Study of Multimedia Batching Schemes

We consider the problem of minimizing the average wait times in a queueing system where a single server gives simultaneous service to a batch of customers. The length of this service is fixed and independent of the size of the batch. Our study is motivated by the application of this problem to Multimedia-On-Demand systems, in which user requests for multimedia objects can be serviced in batches. This can be done using the multicast facility available in the high-speed network connecting the multimedia server with the users. Indeed, users may withdraw access request, when wait-times become too long, leading to a loss in potential revenue for the system. Thus, a most important aspect of this type of service is providing access instantaneously or within a small latency upon request. In this work we develop an approximate model for evaluating the performance of multimedia batching schemes, with respect to system latency. Our mathematical model provides a method for analyzing the performance of two schemes that are natural for this problem - the First Come First Served (FCFS) and the Round Robin (RR). Within this framework we also study the Maximal Queue Length (MQL) scheme and show that in some typical scenarios it achieves a ratio that is a small constant to the minimal latency: Finally, using the relative frequencies of requests for the various multimedia objects, we give a simple algorithm that is a 2-approximation to the optimum.