article

A survey on discriminatory processor sharing

Authors:

Konstantin Avrachenkov,

Urtzi AyestaAuthors Info & Claims

Queueing Systems: Theory and Applications, Volume 53, Issue 1-2

Pages 53 - 63

https://doi.org/10.1007/s11134-006-7586-8

Published: 01 June 2006 Publication History

Abstract

The Discriminatory Processor Sharing (DPS) model is a multi-class generalization of the egalitarian Processor Sharing model. In the DPS model all jobs present in the system are served simultaneously at rates controlled by a vector of weights { g _k > 0; k = 1,..., K }. If there are N _k jobs of class k present in the system, k = 1,..., K , each class- k job is served at rate $$g_k/\sum_{j=1}^K{g_j}{N_j}$$ . The present article provides an overview of the analytical results for the DPS model. In particular, we focus on response times and numbers of jobs in the system.

References

[1]

1. 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 (2004).

[2]

2. K. E. Avrachenkov, U. Ayesta, P. Brown, and R. Núñez-Queija, Discriminatory processor sharing revisited, in: Proceedings of IEEE INFOCOM (2005).

[3]

3. K. E. Avrachenkov, U. Ayesta, P. Brown, and R. Núñez-Queija, Discriminatory processor sharing revisited (2006), Extended version submitted for publication.

[4]

4. F. Baccelli and P. Brémaud, Elements of Queuing Theory: Palm Martingale Calculus and Stochastic Recurrences (Springer, 2003).

[5]

5. M. J. Bach, The Design of the UNIX Operating System (Prentice-Hall, 1986).

[6]

6. T. Bonald and L. Massoulié, Impact of fairness on Internet performance, in: Proceedings of ACM SIGMETRICS/Performance (2001) pp. 82-91.

[7]

7. T. Bonald and A. Proutière, Insensitive bandwidth sharing in data networks, Queueing Systems 44 (2003) 69-100.

[8]

8. T. Bonald and A. Proutière, On stochastic bounds for monotonic processor sharing networks, Queueing Systems 47 (2004) 81-106.

[9]

9. S. C. Borst, R. Núñez-Queija, and A. P. Zwart, Sojourn time asymptotics in processor sharing queues, (2006), in this special issue.

[10]

10. S. C. Borst, D. T. M. B. van Ooteghem, and A. P. Zwart, Tail asymptotics for discriminatory processor sharing queues with heavy-tailed service requirements, Performance Evaluation 61(2-3) (2005) 281- 298.

[11]

11. O. J. Boxma, N. Hegde, and R. Núñez-Queija, Exact and approximate analysis of sojourn times in finite discriminatory processor sharing queues, AEU International Journal on Electronic Communication (2006) (to appear).

[12]

12. T. Bu and D. Towsley, Fixed point approximation for TCP behaviour in an AQM network, in: Proceedings of ACM SIGMETRICS/Performance (2001) pp. 216-225.

[13]

13. S. K. Cheung, J. L. van den Berg, and R. J. Boucherie, Decomposing the queue length distribution of processor sharing models into queue lengths of permanent customer queues, Performance Evaluation 62(1-4) (2005) 100-116.

[14]

14. S. K. Cheung, J. L. van den Berg, R. J. Boucherie, R. Litjens, and F. Roijers, An analytical packet/flow-level modelling approach for wireless LANs with quality-of-service support, in: Proceedings of ITC-19 (2005).

[15]

15. E. G. Coffman and I. Mitrani, Acharacterization of waiting time performance realizable by single-server queues, Operations Research 28(3) (1980) 810-821.

[16]

16. G. Fayolle, I. Mitrani, and R. Iasnogorodski, Sharing a processor among many job classes, Journal of the ACM 27(3) (1980) 519- 532.

[17]

17. H. Feng and V. Misra, Mixed scheduling disciplines for network flows, Performance Evaluation Review 31(2) (2003) 36-39.

[18]

18. T. C. Green and S. Stidham, Sample-path conservation laws, with application to scheduling queues and fluid systems, Queueing Systems 36 (2000) 175-199.

[19]

19. S. Grishechkin, On a relationship between processor sharing queues and Crump-Mode-Jagers branching processes Adv. Appl. Prob. 24(3) (1992) 653-698.

[20]

20. L. Guo and I. Matta, Scheduling flows with unknown sizes: Approximate analysis, in: Proceedings of ACM SIGMETRICS (Extended Abstract) (2002) 276-277. Extended version available as a Boston University Technical Report BU-CS-2002-009.

[21]

21. R. Hassin and M. Haviv, Who should be given priority in a queue, Operations Research Letters, 34 (2006)(2):191-198.

[22]

22. R. Hassin and M. Haviv, To Queue or not to Queue: Equilibrium Behavior in Queueing Systems (Kluwer Academic Publishers, Boston etc., 2003).

[23]

23. M. Haviv and J. van der Wal, Equilibrium strategies for processor sharing and random queues with relative priorities, Probability in the Engineering and Informational Sciences 11 (1997) 403- 412.

[24]

24. M. Haviv and J. van der Wal, Waiting times in discriminatory processor sharing (2005), Submitted for publication.

[25]

25. Y. Hayel and B. Tuffin, Pricing for heterogeneous services at a discriminatory processor sharing queue, in: Proceedings of Networking (2005).

[26]

26. A. Jean-Marie and P. Robert, On the transient behavior of the processor sharing queue, Queueing Systems 17 (1994) 129-136.

[27]

27. F. Kelly, Stochastic Networks and Reversibility , (Wiley, Chichester, 1979).

[28]

28. J. Kim and B. Kim, Sojourn time distribution in the M/M/1 queue with discriminatory processor sharing, Performance Evaluation 58(4) (2004) 341-365.

[29]

29. J. F. C. Kingman, On queues in heavy traffic, Journal of the Royal Statistical Society. Series B, Methodological 24 (1962) 383- 392.

[30]

30. L. Kleinrock, A conservation law for a wide class of queueing disciplines, Naval Research Logistics Quarterly 12(2) (1965) 181- 192.

[31]

31. L. Kleinrock, Time-shared systems: Atheoretical treatment, Journal of the ACM 14(2) (1967) 242-261.

Digital Library

[32]

32. L. Kleinrock, Queueing Systems , vol. 2 (John Wiley and Sons, 1976).

[33]

33. L. Kleinrock, R. R. Muntz, and E. Rodemich, The processor sharing queueing model for time-shared systems with bulk arrivals, Networks Journal 1(1) (1971) 1-13.

[34]

34. L. Massoulié and J. Roberts, Bandwidth sharing and admission control for elastic traffic, Telecommunication Systems 15(1) (2000) 185-201.

[35]

35. D. Mitra and A. Weiss, A closed network with a discriminatory processor sharing server, Performance Evaluation Review 17(1) (1989) 200-208.

[36]

36. I. Mitrani and J. H. Hine, Complete parameterized families of job scheduling strategies, Acta Informatica (8) (1977) 61-73.

[37]

37. I. Mitrani and T. M. O'Donovan, Private communications.

[38]

38. J. A. Morrison, Asymptotic analysis of a large closed queueing network with discriminatory processor sharing, Queueing Systems 9 (1991) 191-214.

Digital Library

[39]

39. T. M. O'Donovan, Direct solutions of M/G/1 processor sharing models, Operations Research 22 (1974) 1232-1235.

[40]

40. A. K. Parekh and R. G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: The single-node case, IEEE/ACM Transactions on Networking 1(3) (1993) 344-357.

[41]

41. K. M. Rege and B. Sengupta, A decomposition theorem and related results for the discriminatory processor sharing queue, Queueing Systems 18 (1994) 333-351.

[42]

42. K. M. Rege and B. Sengupta, Queue length distribution for the discriminatory processor sharing queue, Operations Research 44(4) (1996) 653-657.

[43]

43. 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 (1989) 323-334.

[44]

44. L. E. Schrage, The queue M/G/ 1 with feedback to lower priority queues, Management Science 13 (1967) 466-471.

Digital Library

[45]

45. J. Shanthikumar and D. Yao, Multiclass queueing systems: Polymatroidal structure and optimal scheduling control, Operations Research 40(2) (1992) 293-299.

[46]

46. M. Shreedhar and G. Varghese, Efficient fair queuing using Deficit Round-Robin, IEEE/ACMTransactions on Networking 4(3) (1996) 375-385.

[47]

47. A. Silberschatz, P. Galvin, and G. Gagne, Applied Operating System Concepts (John Wiley and Sons, 2000).

[48]

48. G. van Kessel, R. Núñez-Queija, and S. C. Borst, Asymptotic regimes and approximations for discriminatory processor sharing, Performance Evaluation Review 32(6) (2004) 44-46.

[49]

49. G. van Kessel, R. Núñez-Queija, and S. C. Borst, Differentiated bandwidth sharing with disparate flow sizes, in: Proceedings of IEEE INFOCOM (2005).

[50]

50. M. J. G. van Uitert, Generalized processor sharing queues , PhD thesis, Eindhoven University of Technology (2003).

[51]

51. S. F. Yashkov, Processor sharing queues: Some progress in analysis, Queueing Systems 2 (1987) 1-17.

Digital Library

[52]

52. S. F. Yashkov, Mathematical problems in the theory of processor sharing queueing systems, Journal of Soviet Mathematics 58 (1992) 101-147.

[53]

53. A. P. Zwart and O. J. Boxma, Sojourn time asymptotics in the M/G/ 1 processor sharing queue, Queueing Systems 35 (2000) 141-166.

Cited By

Fiems DPrabhu B(2024)Strategic Routing in Heterogeneous Discriminatory Processor Sharing QueuesNetwork Games, Artificial Intelligence, Control and Optimization10.1007/978-3-031-78600-6_2(14-23)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-78600-6_2
Fiems D(2023)Strategic Revenue Management for Discriminatory Processor Sharing QueuesComputer Performance Engineering and Stochastic Modelling10.1007/978-3-031-43185-2_1(3-17)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-43185-2_1
Walraevens JVan Giel TDe Vuyst SWittevrongel S(2022)Asymptotics of waiting time distributions in the accumulating priority queueQueueing Systems: Theory and Applications10.1007/s11134-022-09839-7101:3-4(221-244)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s11134-022-09839-7
Show More Cited By

Index Terms

A survey on discriminatory processor sharing

Recommendations

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 ...
Beyond processor sharing

While the (Egalitarian) Processor-Sharing (PS) discipline offers crucial insights in the performance of fair resource allocation mechanisms, it is inherently limited in analyzing and designing differentiated scheduling algorithms such as Weighted Fair ...
Sojourn Time Approximations for a Discriminatory Processor Sharing Queue
Inaugural Issue

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Queueing Systems: Theory and Applications

Queueing Systems: Theory and Applications Volume 53, Issue 1-2

June 2006

92 pages

ISSN:0257-0130

Issue’s Table of Contents

Copyright © Copyright © 2006 Springer Science + Business Media, LLC.

Publisher

J. C. Baltzer AG, Science Publishers

United States

Publication History

Published: 01 June 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fiems DPrabhu B(2024)Strategic Routing in Heterogeneous Discriminatory Processor Sharing QueuesNetwork Games, Artificial Intelligence, Control and Optimization10.1007/978-3-031-78600-6_2(14-23)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-78600-6_2
Fiems D(2023)Strategic Revenue Management for Discriminatory Processor Sharing QueuesComputer Performance Engineering and Stochastic Modelling10.1007/978-3-031-43185-2_1(3-17)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-43185-2_1
Walraevens JVan Giel TDe Vuyst SWittevrongel S(2022)Asymptotics of waiting time distributions in the accumulating priority queueQueueing Systems: Theory and Applications10.1007/s11134-022-09839-7101:3-4(221-244)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s11134-022-09839-7
Dudin ADudin SDudina OKim C(2022)Analysis of Retrial Queuing System with Limited Processor Sharing Discipline and Changing Effective BandwidthDistributed Computer and Communication Networks: Control, Computation, Communications10.1007/978-3-031-23207-7_19(243-256)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-23207-7_19
Scully Zvan Kreveld LBoxma ODorsman JWierman A(2020)Characterizing Policies with Optimal Response Time Tails under Heavy-Tailed Job SizesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33921484:2(1-33)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3392148
Marin ARossi SSottana M(2020)Dynamic Resource Allocation in Fork-Join QueuesACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33723765:1(1-28)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3372376
Sacoto-Cabrera ESanchis-Cano AGuijarro LVidal JPla VMarsa-Maestre I(2018)Strategic Interaction between Operators in the Context of Spectrum Sharing for 5G NetworksWireless Communications & Mobile Computing10.1155/2018/43089132018Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1155/2018/4308913
Avrachenkov KBodas T(2018)On the equivalence between multiclass processor sharing and random order scheduling policiesACM SIGMETRICS Performance Evaluation Review10.1145/3273996.327399845:4(2-6)Online publication date: 28-Aug-2018
https://dl.acm.org/doi/10.1145/3273996.3273998
Cui LTezcan T(2016)Approximations for Chat Service Systems Using Many-Server Diffusion LimitsMathematics of Operations Research10.1287/moor.2015.075441:3(775-807)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1287/moor.2015.0754
Izagirre AAyesta UVerloop I(2016)Sojourn Time Approximations for a Discriminatory Processor Sharing QueueACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/28128071:1(1-31)Online publication date: 22-Feb-2016
https://dl.acm.org/doi/10.1145/2812807
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents