Token-tray/weighted queuing-time (TT/WQT): an adaptive batching policy for near video-on-demand system

In near video-on-demand (near-VoD), requests for a video title are grouped together (i.e. batched) and are served with a single multicast stream, thereby increasing the number of concurrent users which can be supported by the system. Since users may not be able to tolerate the delay incurred by batching and hence cancel their requests, a batching policy should be designed so as to achieve low user loss and high revenue (given by the total pay-per-view collected over a long period of time across all movies). We propose an adaptive batching policy which offers users low delay at low arrival rate, and gates the allocation of the channels at high rate. Such adaptivity is achieved by the use of a simple “token-tray” (TT) scheme which governs when a stream may be allocated to a movie. In assigning a movie to a stream, we propose a weight function which depends on the user queuing-time and its pay-per-view (hence the term “weighted queuing-time”) (WQT). By comparing our batching policy (TT/WQT) with a number of traditional ones (FCFS, forced-wait, batch-size-based scheme, etc.), our scheme is shown to achieve the highest revenue and lowest loss rate even when the arrival rate changes, with the user loss rate across the movies being fairly uniform, and the user delay being fairly low even at high arrival rate