Mean Delay Analysis of Multi Level Processor Sharing Disciplines
Samuli Aalto, Urtzi Ayesta · 2006
scheduling disciplines permit to model a wide variety of non-anticipating scheduling disciplines. Such disciplines have recently attracted attention in the context of the Internet as an appropriate flow-level model for the bandwidth sharing obtained when priority is given to short TCP connections. In this paper, we compare the mean delay in an M/G/1 queue among MLPS disciplines under the assumption that the service time distribution belongs to class Decreasing Hazard Rate (DHR). We are able to prove that, given an MLPS discipline, the mean delay is reduced whenever a level is added by splitting an existing one in several cases. The exceptions concern splitting the upper levels with PS internal discipline. Our numerical examples, however, indicate that the level splitting be advantageous even in these cases. Furthermore, we characterize the effect on the mean delay of changing internal disciplines within levels. By numerical means we demonstrate that the mean delay of an MLPS discipline can get close to the minimum optimal delay with just a few levels. As the number of levels increases in an MLPS discipline, the MLPS queue mimics closer and closer the behavior of a Foreground-Background queue, which is known to minimize the mean delay among all disciplines. Thus, our result provides a constructive way to demonstrate the optimality of FB. I.