Abstract
We study a multiclass time-sharing discipline with relative priorities known as discriminatory processor sharing (DPS), which provides a natural framework to model service differentiation in systems. The analysis of DPS is extremely challenging, and analytical results are scarce. We develop closed-form approximations for the mean conditional (on the service requirement) and unconditional sojourn times. The main benefits of the approximations lie in its simplicity, the fact that it applies for general service requirements with finite second moments, and that it provides insights into the dependency of the performance on the system parameters. We show that the approximation for the mean conditional and unconditional sojourn time of a customer is decreasing as its relative priority increases. We also show that the approximation is exact in various scenarios, and that it is uniformly bounded in the second moments of the service requirements. Finally, we numerically illustrate that the approximation for exponential, hyperexponential, and Pareto service requirements is accurate across a broad range of parameters.
- E. Altman, K. Avrachenkov, and U. Ayesta. 2006. A survey on discriminatory processor sharing. Queueing Systems 53, 1--2, 53--63. Google ScholarDigital Library
- E. Altman, T. Jimenez, and D. Kofman. 2004. DPS queues with stationary ergodic service times and the performance of TCP in overload. In Proceedings of the IEEE INFOCOM Conference.Google Scholar
- K. E. Avrachenkov, U. Ayesta, P. Brown, and R. Núñez-Queija. 2005. Discriminatory processor sharing revisited. In Proceedings of the IEEE INFOCOM Conference.Google Scholar
- S. C. Borst, R. Núñez-Queija, and A. P. Zwart. 2006. Sojourn time asymptotics in processor sharing queues. Queueing Systems 53, 1--2, 31--51. Google ScholarDigital Library
- S. C. Borst, D. T. M. B. van Ooteghem, and A. P. Zwart. 2005. Tail asymptotics for discriminatory processor sharing queues with heavy-tailed service requirements. Performance Evaluation 61, 2--3, 281--298. Google ScholarDigital Library
- O. J. Boxma, N. Hegde, and R. Núñez-Queija. 2006. Exact and approximate analysis of sojourn times in finite discriminatory processor sharing queues. AEU International Journal on Electronic Communications 60, 109--115.Google ScholarCross Ref
- T. Bu and D. Towsley. 2001. Fixed point approximation for TCP behaviour in an AQM network. In Proceedings of the ACM SIGMETRICS/Performance Conference. 216--225. Google ScholarDigital Library
- S. K. Cheung, J. L. van den Berg, R. J. Boucherie, R. Litjens, and F. Roijers. 2005. An analytical packet/flow-level modelling approach for wireless LANs with quality-of-service support. In Proceedings of the ITC-19 Conference.Google Scholar
- G. Fayolle, I. Mitrani, and R. Iasnogorodski. 1980. Sharing a processor among many job classes. Journal of the ACM 27, 3, 519--532. Google ScholarDigital Library
- S. Ben Fredj, T. Bonald, A. Proutiere, G. Regnie, and J. Roberts. 2001. Statistical bandwidth sharing: A study of congestion at flow level. In Proceedings of the SIGCOMM Conference. 111--122. Google ScholarDigital Library
- S. Grishechkin. 1992. On a relationship between processor sharing queues and Crump-Node-Jagers branching processes. Advances in Applied Probability 24, 3, 653--698.Google ScholarCross Ref
- R. Hassin and M. Haviv. 2003. To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems. Kluwer Academic, Boston, MA.Google ScholarCross Ref
- Y. Hayel and B. Tuffin. 2005. Pricing for heterogeneous services at a discriminatory processor sharing queue. In Proceedings of the Networking Conference. Google ScholarDigital Library
- A. Izagirre. 2015. Interpolation Approximations for Steady-State Performance Measures. Ph.D. Dissertation. INSA Toulouse and UPV-EHU.Google Scholar
- A. Izagirre, U. Ayesta, and I. M. Verloop. 2014. Sojourn time approximations in a multi-class time-sharing system. In Proceedings of the IEEE INFOCOM Conference.Google Scholar
- A. Izagirre, U. Ayesta, and I. M. Verloop. 2015. Interpolation approximations for the steady-state distribution in multi-class resource-sharing systems. Performance Evaluation 91, C, 56--79. http://dx.doi.org/ 10.1016/j.peva.2015.06.005, 91 (2015), 56--79. Google ScholarDigital Library
- F. P. Kelly. 1979. Stochastic Networks and Reversibility. Wiley, Chichester, UK.Google Scholar
- F. P. Kelly. 1997. Charging and rate control for elastic traffic. European Transactions on Telecommunications 8, 33--37.Google ScholarCross Ref
- A. A. Kherani and R. Núñez-Queija. 2006. TCP as an implementation of age-based scheduling: Fairness and performance. In Proceedings of the IEEE INFOCOM Conference.Google Scholar
- L. Kleinrock. 1967. Time-shared systems: A theoretical treatment. Journal of the ACM 14, 2, 242--261. Google ScholarDigital Library
- L. Kleinrock. 1976. Queueing Systems, Vol. 2. John Wiley & Sons.Google Scholar
- K. M. Rege and B. Sengupta. 1996. Queue length distribution for the discriminatory processor sharing queue. Operations Research 44, 4, 653--657. Google ScholarDigital Library
- M. I. Reiman and B. Simon. 1988a. An interpolation approximation for queueing systems with Poisson input. Operations Research 36, 454--469. Google ScholarDigital Library
- M. I. Reiman and B. Simon. 1988b. Light traffic limits of sojourn time distributions in Markovian queueing networks. Stochastic Models 4, 191--233.Google ScholarCross Ref
- M. I. Reiman and B. Simon. 1989. Open queueing systems in light traffic. Operations Research 14, 1, 26--59.Google ScholarDigital Library
- J. W. Roberts. 2004. A survey on statistical bandwidth sharing. Computer Networks 45, 319--332. Google ScholarDigital Library
- G. van Kessel, R. Núñez-Queija, and S. C. Borst. 2005. Differentiated bandwidth sharing with disparate flow sizes. In Proceedings of the IEEE INFOCOM Conference.Google Scholar
- I. M. Verloop, U. Ayesta, and R. Núñez-Queija. 2011. Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing. Operations Research 59, 3, 648--660. Google ScholarDigital Library
- J. Walrand. 1988. An Introduction to Queueing Networks. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
- Y. Wu, L. Bui, and R. Johari. 2012. Heavy traffic approximation of equilibria in resource sharing games. IEEE Journal on Selected Areas in Communications 30, 11, 2200--2209.Google ScholarCross Ref
- S. F. Yashkov. 1987. Processor sharing queues: Some progress in analysis. Queueing Systems 2, 1--17. Google ScholarDigital Library
Index Terms
- Sojourn Time Approximations for a Discriminatory Processor Sharing Queue
Recommendations
Sojourn times in a processor sharing queue with multiple vacations
We study an M/G/1 processor sharing queue with multiple vacations. The server only takes a vacation when the system has become empty. If he finds the system still empty upon return, he takes another vacation, and so on. Successive vacations are ...
Heavy-Traffic Analysis of a Multiple-Phase Network with Discriminatory Processor Sharing
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 that customers have phase-type ...
Sojourn time distribution in the M/M/1 queue with discriminatory processor-sharing
In this paper, we consider a queue with multiple K job classes, Poisson arrivals, exponentially distributed required service times in which a single processor serves according to the DPS discipline. More precisely, if there are ni class i jobs in the ...
Comments