Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates. (English) Zbl 1117.60083
For a processor sharing queueing system with time varying arrival and service rate the transient sojourn time distribution of a virtual customer is approximated by fluid limits and diffusion limits. A virtual customer observes the system over the time which can be termed a virtual processing time for him under the observed state of the other customers present (contrary to the concept of tagged customers who influences the other customers as well). The asymptotics are derived by accelerating the arrival and service rates in parallel. The asymptotic results for the sojourn times (their distributional approximations) are compared with simulations, especially concerning first and second moments.
Reviewer: Hans Daduna (Hamburg)
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90B22 | Queues and service in operations research |
Keywords:
processor sharing; fluid limit; diffusion limit; time-varying rates; sojourn times; virtual customer; transient behaviour; uniform accelerationReferences:
| [1] | N. Bansal and M. Harchol-Balter, Analysis of SRPT Scheduling: Investigating Unfairness, in: Proceedings of Association of Computing Machinery Sigmetrics 2001 Conference on Measurement and Modeling of Computer Systems, Cambridge, MA, (2001). · Zbl 1056.68610 |
| [2] | T. Bonald and A. Proutière, On Performance Bounds for the Integration of Elastic and Adaptive Streaming Flows, in: Proceedings of Association of Computing Machinery Sigmetrics/Performance Joint International Conference on Measurement and Modeling of Computer Systems, (2004) 235–245. |
| [3] | H. Chen, O. Kella, and G. Weiss, Fluid Approximations for a Processor Sharing Queue, Queueing Systems: Theory and Applications, 27 (1997) 99–125. · Zbl 0892.90073 · doi:10.1023/A:1019105929766 |
| [4] | E.G. Coffman, R.R. Muntz, and H. Trotter, Waiting Time Distribution for Processor-Sharing Systems, Journal of the Association of Computing Machinery 17 (1970) 123–130. · Zbl 0197.15304 |
| [5] | F. Delcoigne, A. Proutière, and G. Règniè, Modeling Integration of Streaming and Data Traffic, Performance Evaluation 55 (2004) 185–209. · doi:10.1016/S0166-5316(03)00115-9 |
| [6] | M. Harchol-Balter, B. Schroeder, N. Bansal, and M. Agrawal, Size-based Scheduling to Improve Web Performance, Association of Computing Machinery Transactions on Computer Systems 21(2) (2003) 207–233. |
| [7] | F. Guillemin and J. Boyer, Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory, Queueing Systems 39(4) (2001) 377–397. · Zbl 0995.60085 · doi:10.1023/A:1013913827667 |
| [8] | A. Jean-Marie and P. Robert, On the Transient Behavior of the Processor Sharing Queue, Queueing Systems 17 (1994) 129–136. · Zbl 0811.60083 · doi:10.1007/BF01158692 |
| [9] | M. Yu. Kitaev, The M/G/1 Processor-Sharing Model: Transient Behavior, Queueing Systems 14 (1993) 239–273. · Zbl 0802.68011 · doi:10.1007/BF01158868 |
| [10] | L. Kleinrock. Queueing Systems, Volume II: Computer Applications (John Wiley & Sons, 1976). · Zbl 0361.60082 |
| [11] | J.D.C. Little, A Proof of the Queueing Formula L={\(\lambda\)} W, Operations Research 9 (1961) 383–387. · Zbl 0108.14803 · doi:10.1287/opre.9.3.383 |
| [12] | A. Mandelbaum and W.A. Massey, Strong Approximations for Time Dependent Queues, Mathematics of Operations Research 20(1) (1995) 33–64. · Zbl 0834.60096 · doi:10.1287/moor.20.1.33 |
| [13] | W.A. Massey, Asymptotic Analysis of the Time Dependent M/M/1 Queue, Mathematics of Operations Research 10 (1985) 305–327. · Zbl 0567.60089 · doi:10.1287/moor.10.2.305 |
| [14] | H. Masuyama and T. Takine, Sojourn Time Distribution in a MAP/M/1 Processor-Sharing Queue, Operations Research Letters 31(5) (2003) 406–412. · Zbl 1025.60040 · doi:10.1016/S0167-6377(03)00028-2 |
| [15] | J. Morrison, Response Time for a Processor-Sharing system, SIAM J. Appl. Math. 45(1) (1985) 152–167. · Zbl 0558.68031 · doi:10.1137/0145007 |
| [16] | R. Nunez-Queija, Processor Sharing Models for Integrated Services Networks, Ph.D. Thesis Eindhoven University of Technology (2000). · Zbl 0953.68016 |
| [17] | T. Ott, The Sojourn Time Distribution in the M/G/1 Queue with Processor Sharing, J. Appl. Prob. 21 (1984) 360–378. · Zbl 0544.60087 · doi:10.2307/3213646 |
| [18] | J.W. Roberts, Engineering for Quality of Service, in: K. Park and W. Willinger (eds.), Self-Similar Network Traffic and Performance Evaluation (Wiley, New York, 2000) pp. 401–420. |
| [19] | R. Schassberger, A New Approach to the M/G/1 Processor Sharing Queue, Adv. Appl. Prob. 16 (1984) 202–213. · Zbl 0529.68015 · doi:10.2307/1427231 |
| [20] | B. Schroeder and M. Harchol-Balter, Web servers under overload: How scheduling can help, 18th International Teletraffic Congress (Berlin, Germany, 2003). |
| [21] | B. Sengupta and D.L. Jagerman, A Conditional Response Time of the M/M/1 Processor-Sharing Queue, AT& T Technical Journal 64 (1985) 409–421. · Zbl 0587.68036 |
| [22] | S.F. Yashkov, A Derivation of Response Time Distribution for a M/G/1 Processor-Sharing Queue, Problems of Control and Information Theory 12(2) (1983) 133–148. · Zbl 0519.68052 |
| [23] | S.F. Yashkov, Processor-Sharing Queues: Some Progress in Analysis, Queueing Systems 2 (1987) 1–17. · Zbl 0648.68050 · doi:10.1007/BF01182931 |
| [24] | S.F. Yashkov, Mathematical Problems in the Theory of Shared-Processor Systems, Journal of Soviet Mathematics 58 (1992) 101–147. · Zbl 0735.68010 · doi:10.1007/BF01097426 |
| [25] | B. Zwart and O.J. Boxma, Sojourn Time Asymptotics in the M/G/1 Processor Sharing queue, Queueing Systems 35 (2000) 141–166. · Zbl 0997.90024 · doi:10.1023/A:1019142010994 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
