Discriminatory processor sharing revisited
Authors:
- K. AvrachenkovKAK. Avrachenkov
- U. AyestaUAU. Ayesta
- P. BrownPBP. Brown
- R. Nunez-QueijaRNR. Nunez-Queija
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 784-795
Abstract
As a natural multi-class generalization of the well-known (egalitarian) Processor Sharing (PS) ser- vice discipline, Discriminatory Processor Sharing (DPS) is of great interest in many application areas, including telecommunications. Under DPS, the mean response time conditional on the service requirement is only known in closed form when all classes have exponential service re- quirement distributions. For generally distributed service requirements, Fayolle et al. (1) showed that the expected conditional response times satisfy a system of integro- differential equations. In this paper, we exploit that result to prove that, provided the system is stable, for each class the expected unconditional response time is finite and that the expected conditional response time has an asymptote. The asymptotic bias of each class is found in closed form, involving the mean service requirements of all classes and the second moments of all classes but the one under consideration. In the course of the development we prove two other results that are of independent interest: we establish a conservation law for the time average unfinished work of all classes and, using a stochastic coupling argument, we show that the response times of different classes are stochastically ordered according to the DPS weights. Finally, we study DPS as a tool to achieve size based scheduling and we provide guidelines as to how the weights of DPS must be chosen such that DPS outperforms PS.Keywords
This publication has 24 references indexed in Scilit:
- On Stochastic Bounds for Monotonic Processor Sharing NetworksQueueing Systems, 2004
- Scheduling flows with unknown sizesACM SIGMETRICS Performance Evaluation Review, 2002
- Sample-path conservation laws, with applications to scheduling queues and fluid systemsQueueing Systems, 2000
- On a relationship between processor-sharing queues and Crump–Mode–Jagers branching processesAdvances in Applied Probability, 1992
- Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling ControlOperations Research, 1992
- Workloads and waiting times in single-server systems with multiple customer classesQueueing Systems, 1989
- Scheduling Multiclass Single Server Queueing Systems to Stochastically Maximize the Number of Successful DeparturesProbability in the Engineering and Informational Sciences, 1989
- Poisson Arrivals See Time AveragesOperations Research, 1982
- On the relation between customer and time averages in queuesJournal of Applied Probability, 1971
- The Queue M/G/1 With Feedback to Lower Priority QueuesManagement Science, 1967