M/G/k queue

Last updated

In queueing theory, a discipline within the mathematical theory of probability, an M/G/k queue is a queue model where arrivals are Markovian (modulated by a Poisson process), service times have a General distribution and there are k servers. The model name is written in Kendall's notation, and is an extension of the M/M/c queue, where service times must be exponentially distributed and of the M/G/1 queue with a single server. Most performance metrics for this queueing system are not known and remain an open problem. [1]

Contents

Model definition

A queue represented by a M/G/k queue is a stochastic process whose state space is the set {0,1,2,3...}, where the value corresponds to the number of customers in the queue, including any being served. Transitions from state i to i + 1 represent the arrival of a new customer: the times between such arrivals have an exponential distribution with parameter λ. Transitions from state i to i − 1 represent the departure of a customer who has just finished being served: the length of time required for serving an individual customer has a general distribution function. The lengths of times between arrivals and of service periods are random variables which are assumed to be statistically independent.

Steady state distribution

Tijms et al. believe it is "not likely that computationally tractable methods can be developed to compute the exact numerical values of the steady-state probability in the M/G/k queue." [2]

Various approximations for the average queue size, [3] stationary distribution [4] [5] and approximation by a reflected Brownian motion [6] [7] have been offered by different authors. Recently a new approximate approach based on Laplace transform for steady state probabilities has been proposed by Hamzeh Khazaei et al.. [8] [9] This new approach is yet accurate enough in cases of large number of servers and when the distribution of service time has a Coefficient of variation more than one.

Average delay/waiting time

There are numerous approximations for the average delay a job experiences. [5] [7] [10] [11] [12] [13] The first such was given in 1959 using a factor to adjust the mean waiting time in an M/M/c queue [14] [15] This result is sometimes known as Kingman's law of congestion. [16]

where C is the coefficient of variation of the service time distribution. Ward Whitt described this approximation as “usually an excellent approximation, even given extra information about the service-time distribution." [17]

However, it is known that no approximation using only the first two moments can be accurate in all cases. [14]

A Markov–Krein characterization has been shown to produce tight bounds on the mean waiting time. [18]

Inter-departure times

It is conjectured that the times between departures, given a departure leaves n customers in a queue, has a mean which as n tends to infinity is different from the intuitive 1/μ result. [19]

Two servers

For an M/G/2 queue (the model with two servers) the problem of determining marginal probabilities can be reduced to solving a pair of integral equations [20] or the Laplace transform of the distribution when the service time distribution is a mixture of exponential distributions. [21] The Laplace transform of queue length [22] and waiting time distributions [23] can be computed when the waiting time distribution has a rational Laplace transform.

Related Research Articles

<span class="mw-page-title-main">Queueing theory</span> Mathematical study of waiting lines, or queues

Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide a service.

In mathematical queueing theory, Little's law is a theorem by John Little which states that the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system. Expressed algebraically the law is

In queueing theory, a discipline within the mathematical theory of probability, a Jackson network is a class of queueing network where the equilibrium distribution is particularly simple to compute as the network has a product-form solution. It was the first significant development in the theory of networks of queues, and generalising and applying the ideas of the theorem to search for similar product-form solutions in other networks has been the subject of much research, including ideas used in the development of the Internet. The networks were first identified by James R. Jackson and his paper was re-printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’

In queueing theory, a discipline within the mathematical theory of probability, the Pollaczek–Khinchine formula states a relationship between the queue length and service time distribution Laplace transforms for an M/G/1 queue. The term is also used to refer to the relationships between the mean queue length and mean waiting/service time in such a model.

<span class="mw-page-title-main">M/M/1 queue</span> Queue with Markov (Poisson) arrival process, exponential service time distribution and one server

In queueing theory, a discipline within the mathematical theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an exponential distribution. The model name is written in Kendall's notation. The model is the most elementary of queueing models and an attractive object of study as closed-form expressions can be obtained for many metrics of interest in this model. An extension of this model with more than one server is the M/M/c queue.

In queueing theory, a discipline within the mathematical theory of probability, Burke's theorem is a theorem asserting that, for the M/M/1 queue, M/M/c queue or M/M/∞ queue in the steady state with arrivals is a Poisson process with rate parameter λ:

  1. The departure process is a Poisson process with rate parameter λ.
  2. At time t the number of customers in the queue is independent of the departure process prior to time t.

In queueing theory, a discipline within the mathematical theory of probability, the Gordon–Newell theorem is an extension of Jackson's theorem from open queueing networks to closed queueing networks of exponential servers where customers cannot leave the network. Jackson's theorem cannot be applied to closed networks because the queue length at a node in the closed network is limited by the population of the network. The Gordon–Newell theorem calculates the open network solution and then eliminates the infeasible states by renormalizing the probabilities. Calculation of the normalizing constant makes the treatment more awkward as the whole state space must be enumerated. Buzen's algorithm or mean value analysis can be used to calculate the normalizing constant more efficiently.

In queueing theory, a discipline within the mathematical theory of probability, quasireversibility is a property of some queues. The concept was first identified by Richard R. Muntz and further developed by Frank Kelly. Quasireversibility differs from reversibility in that a stronger condition is imposed on arrival rates and a weaker condition is applied on probability fluxes. For example, an M/M/1 queue with state-dependent arrival rates and state-dependent service times is reversible, but not quasireversible.

<span class="mw-page-title-main">Fork–join queue</span> Type of queue

In queueing theory, a discipline within the mathematical theory of probability, a fork–join queue is a queue where incoming jobs are split on arrival for service by numerous servers and joined before departure. The model is often used for parallel computations or systems where products need to be obtained simultaneously from different suppliers. The key quantity of interest in this model is usually the time taken to service a complete job. The model has been described as a "key model for the performance analysis of parallel and distributed systems." Few analytical results exist for fork–join queues, but various approximations are known.

In queueing theory, a discipline within the mathematical theory of probability, the M/M/c queue is a multi-server queueing model. In Kendall's notation it describes a system where arrivals form a single queue and are governed by a Poisson process, there are c servers, and job service times are exponentially distributed. It is a generalisation of the M/M/1 queue which considers only a single server. The model with infinitely many servers is the M/M/∞ queue.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/1 queue is a queue model where arrivals are Markovian, service times have a General distribution and there is a single server. The model name is written in Kendall's notation, and is an extension of the M/M/1 queue, where service times must be exponentially distributed. The classic application of the M/G/1 queue is to model performance of a fixed head hard disk.

In queueing theory, a discipline within the mathematical theory of probability, a fluid queue is a mathematical model used to describe the fluid level in a reservoir subject to randomly determined periods of filling and emptying. The term dam theory was used in earlier literature for these models. The model has been used to approximate discrete models, model the spread of wildfires, in ruin theory and to model high speed data networks. The model applies the leaky bucket algorithm to a stochastic source.

In queueing theory, a discipline within the mathematical theory of probability, a bulk queue is a general queueing model where jobs arrive in and/or are served in groups of random size. Batch arrivals have been used to describe large deliveries and batch services to model a hospital out-patient department holding a clinic once a week, a transport link with fixed capacity and an elevator.

In queueing theory, a discipline within the mathematical theory of probability, the M/M/∞ queue is a multi-server queueing model where every arrival experiences immediate service and does not wait. In Kendall's notation it describes a system where arrivals are governed by a Poisson process, there are infinitely many servers, so jobs do not need to wait for a server. Each job has an exponentially distributed service time. It is a limit of the M/M/c queue model where the number of servers c becomes very large.

In queueing theory, a discipline within the mathematical theory of probability, a heavy traffic approximation is the matching of a queueing model with a diffusion process under some limiting conditions on the model's parameters. The first such result was published by John Kingman who showed that when the utilisation parameter of an M/M/1 queue is near 1 a scaled version of the queue length process can be accurately approximated by a reflected Brownian motion.

In queueing theory, a discipline within the mathematical theory of probability, an M/D/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times are fixed (deterministic). The model name is written in Kendall's notation. Agner Krarup Erlang first published on this model in 1909, starting the subject of queueing theory. An extension of this model with more than one server is the M/D/c queue.

In queueing theory, a discipline within the mathematical theory of probability, a D/M/1 queue represents the queue length in a system having a single server, where arrivals occur at fixed regular intervals and job service requirements are random with an exponential distribution. The model name is written in Kendall's notation. Agner Krarup Erlang first published a solution to the stationary distribution of a D/M/1 and D/M/k queue, the model with k servers, in 1917 and 1920.

In queueing theory, a discipline within the mathematical theory of probability, the G/G/1 queue represents the queue length in a system with a single server where interarrival times have a general distribution and service times have a (different) general distribution. The evolution of the queue can be described by the Lindley equation.

<span class="mw-page-title-main">Polling system</span>

In queueing theory, a discipline within the mathematical theory of probability, a polling system or polling model is a system where a single server visits a set of queues in some order. The model has applications in computer networks and telecommunications, manufacturing and road traffic management. The term polling system was coined at least as early as 1968 and the earliest study of such a system in 1957 where a single repairman servicing machines in the British cotton industry was modelled.

Amber Lynn Puha is an American mathematician and educator at California State University San Marcos. Her research concerns probability theory and stochastic processes.

References

  1. ↑ Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems . 63 (1–4): 3–4. doi:10.1007/s11134-009-9147-4. S2CID   38588726.
  2. ↑ Tijms, H. C.; Van Hoorn, M. H.; Federgruen, A. (1981). "Approximations for the Steady-State Probabilities in the M/G/c Queue". Advances in Applied Probability. 13 (1): 186–206. doi:10.2307/1426474. JSTOR   1426474. S2CID   222335724.
  3. ↑ Ma, B. N. W.; Mark, J. W. (1995). "Approximation of the Mean Queue Length of an M/G/c Queueing System". Operations Research . 43 (1): 158–165. doi:10.1287/opre.43.1.158. JSTOR   171768.
  4. ↑ Breuer, L. (2008). "Continuity of the M/G/c queue". Queueing Systems . 58 (4): 321–331. doi:10.1007/s11134-008-9073-x. S2CID   2345317.
  5. 1 2 Hokstad, Per (1978). "Approximations for the M/G/m Queue". Operations Research . INFORMS. 26 (3): 510–523. doi:10.1287/opre.26.3.510. JSTOR   169760.
  6. ↑ Kimura, T. (1983). "Diffusion Approximation for an M/G/m Queue". Operations Research . 31 (2): 304–321. doi:10.1287/opre.31.2.304. JSTOR   170802.
  7. 1 2 Yao, D. D. (1985). "Refining the Diffusion Approximation for the M/G/m Queue". Operations Research . 33 (6): 1266–1277. doi:10.1287/opre.33.6.1266. JSTOR   170637.
  8. ↑ Khazaei, H.; Misic, J.; Misic, V. B. (2012). "Performance Analysis of Cloud Computing Centers Using M/G/m/m+r Queuing Systems". IEEE Transactions on Parallel and Distributed Systems. 23 (5): 936. doi:10.1109/TPDS.2011.199. S2CID   16934438.
  9. ↑ Khazaei, H.; Misic, J.; Misic, V. B. (2011). "Modelling of Cloud Computing Centers Using M/G/m Queues". 2011 31st International Conference on Distributed Computing Systems Workshops. p. 87. doi:10.1109/ICDCSW.2011.13. ISBN   978-1-4577-0384-3. S2CID   16067523.
  10. ↑ Hokstad, Per (1980). "The Steady-State Solution of the M/K2/m Queue". Advances in Applied Probability. Applied Probability Trust. 12 (3): 799–823. doi:10.2307/1426432. JSTOR   1426432. S2CID   124883099.
  11. ↑ Köllerström, Julian (1974). "Heavy Traffic Theory for Queues with Several Servers. I". Journal of Applied Probability. Applied Probability Trust. 11 (3): 544–552. doi:10.1017/s0021900200096327. JSTOR   3212698.
  12. ↑ Nozaki, S. A.; Ross, S. M. (1978). "Approximations in Finite-Capacity Multi-Server Queues with Poisson Arrivals". Journal of Applied Probability. 15 (4): 826–834. doi:10.2307/3213437. JSTOR   3213437. S2CID   32476285.
  13. ↑ Boxma, O. J.; Cohen, J. W.; Huffels, N. (1979). "Approximations of the Mean Waiting Time in an M/G/s Queueing System". Operations Research . INFORMS. 27 (6): 1115–1127. doi:10.1287/opre.27.6.1115. JSTOR   172087.
  14. 1 2 Gupta, V.; Harchol-Balter, M.; Dai, J. G.; Zwart, B. (2009). "On the inapproximability of M/G/K: Why two moments of job size distribution are not enough". Queueing Systems . 64: 5–48. CiteSeerX   10.1.1.151.5844 . doi:10.1007/s11134-009-9133-x. S2CID   16755599.
  15. ↑ Lee, A. M.; Longton, P. A. (1959). "Queueing Processes Associated with Airline Passenger Check-in". Journal of the Operational Research Society . 10: 56–71. doi:10.1057/jors.1959.5.
  16. ↑ Gans, N.; Koole, G.; Mandelbaum, A. (2003). "Telephone Call Centers: Tutorial, Review, and Research Prospects" (PDF). Manufacturing & Service Operations Management . 5 (2): 79. doi: 10.1287/msom.5.2.79.16071 .
  17. ↑ Whitt, W. (2009). "Approximations for the GI/G/m Queue" (PDF). Production and Operations Management . 2 (2): 114–161. doi:10.1111/j.1937-5956.1993.tb00094.x.
  18. ↑ Gupta, V.; Osogami, T. (2011). "On Markov–Krein characterization of the mean waiting time in M/G/K and other queueing systems". Queueing Systems. 68 (3–4): 339. doi:10.1007/s11134-011-9248-8. S2CID   35061112.
  19. ↑ Veeger, C.; Kerner, Y.; Etman, P.; Adan, I. (2011). "Conditional inter-departure times from the M/G/s queue". Queueing Systems . 68 (3–4): 353. doi:10.1007/s11134-011-9240-3. S2CID   19382087.
  20. ↑ Knessl, C.; Matkowsky, B. J.; Schuss, Z.; Tier, C. (1990). "An Integral Equation Approach to the M/G/2 Queue". Operations Research . 38 (3): 506. doi:10.1287/opre.38.3.506. JSTOR   171363.
  21. ↑ Cohen, J. W. (1982). "On the M/G/2 queueing model". Stochastic Processes and Their Applications. 12 (3): 231–248. doi: 10.1016/0304-4149(82)90046-1 .
  22. ↑ Hokstad, Per (1979). "On the Steady-State Solution of the M/G/2 Queue". Advances in Applied Probability. Applied Probability Trust. 11 (1): 240–255. doi:10.2307/1426776. JSTOR   1426776. S2CID   125014523.
  23. ↑ Boxma, O. J.; Deng, Q.; Zwart, A. P. (2002). "Waiting-Time Asymptotics for the M/G/2 Queue with Heterogeneous Servers". Queueing Systems . 40: 5–31. doi:10.1023/A:1017913826973. S2CID   2513624.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.