Heavy-traffic analysis of the M/PH/1 discriminatory processor sharing queue with phase-dependent weights

Abstract

We analyze a generalization of the Discriminatory Processor Sharing (DPS)queue in a heavy-traffic setting. Customers present in the system are served simultaneously at rates controlled by a vector of weights. We assume phase-type distributed service requirements and allow that customers have different weights in various phases of their service. We establish a state-space collapse for the queue length vector in heavy traffic. The result shows that in the limit, the queue length vector is the product of an exponentially distributed random variable and a deterministic vector. This generalizes a previous result by [2] who considered a DPS queue with exponentially distributed service requirements. We finally discuss some implications for residual service requirements and monotonicity properties in the ordinary DPS model.

References

1. E. Altman, K.E. Avrachenkov, and U. Ayesta. A survey on discriminatory processor sharing. Queueing Systems 53:53--63, 2006.
2. E. Altman, T. Jimenez, and D. Kofman. DPS queues with stationary ergodic service times and the performance of TCP in overload. In Proceedings of IEEE INFOCOM Hong Kong, 2004.
3. K.E. Avrachenkov, U. Ayesta, P. Brown, and R. Núñez-Queija. Discriminatory processor sharing revisited. In Proceedings of IEEE INFOCOM Miami, FL, USA, 2005.
4. A. Ben Tahar and A. Jean-Marie. The fluid limit of the multiclass processor sharing queue. INRIA Research Report RR-6867, 2009.
5. R. Egorova, S.C. Borst, and A.P. Zwart. Bandwidth-sharing networks in overload. Performance Evaluation 64:978--993, 2007.
6. G. Fayolle, I. Mitrani, and R. Iasnogorodski. Sharing a processor among many job classes. Journal of the ACM 27:519--532, 1980.
7. G. Grishechkin. On a relationship between processor-sharing queues and Crump-Mode-Jagers branching processes. Advances in Applied Probability 24:653--698, 1992.
8. M. Haviv and J. van der Wal. Mean sojourn times for phase-type discriminatory processor sharing systems. European Journal of Operational Research 189:375--386, 2008.
9. W.N. Kang, F.P. Kelly, N.H. Lee, and R.J. Williams. State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy. Annals of Applied Probability 2009. To appear.
10. G. van Kessel, R. Núñez-Queija, and S.C. Borst. Asymptotic regimes and approximations for discriminatory processor sharing. Performance Evaluation Review 32:44--46, 2004.
11. L. Kleinrock. Time-shared systems: A theoretical treatment. Journal of the ACM 14:242--261, 1967.
12. K.M. Rege and B. Sengupta. Queue length distribution for the discriminatory processor-sharing queue. Operations Research 44:653--657, 1996.
13. R. Righter and J.G. Shanthikumar. Scheduling multiclass single server queueing systems to stochastically maximize the number of successful departures. Probability in the Engineering and Informational Sciences 3:323--333, 1989.
14. A.L. Stolyar. Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Annals of Applied Probability 14:1--53, 2004.
15. I.M. Verloop.Scheduling in Stochastic Resource-Sharing Systems...PhD thesis, Eindhoven University of Technology, 2009.
16. I.M. Verloop, U. Ayesta, and R. Núñez-Queija. Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing. CWI research report PNA-E0905 2009.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Design

    • Performance

• Networks

  • Network services

    • Network management