G/G/1 queue

Last updated

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 (meaning arbitrary) distribution and service times have a (different) general distribution. [1] The evolution of the queue can be described by the Lindley equation. [2]

Contents

The system is described in Kendall's notation where the G denotes a general distribution for both interarrival times and service times and the 1 that the model has a single server. [3] [4] Different interarrival and service times are considered to be independent, and sometimes the model is denoted GI/GI/1 to emphasise this. The numerical solution for the GI/G/1 can be obtained by discretizing the time. [5]

Waiting time

Kingman's formula gives an approximation for the mean waiting time in a G/G/1 queue. [6] Lindley's integral equation is a relationship satisfied by the stationary waiting time distribution which can be solved using the Wiener–Hopf method. [7]

Multiple servers

Few results are known for the general G/G/k model as it generalises the M/G/k queue for which few metrics are known. Bounds can be computed using mean value analysis techniques, adapting results from the M/M/c queue model, using heavy traffic approximations, empirical results [8] : 189  [9] or approximating distributions by phase type distributions and then using matrix analytic methods to solve the approximate systems. [8] : 201 

In a G/G/2 queue with heavy-tailed job sizes, the tail of the delay time distribution is known to behave like the tail of an exponential distribution squared under low loads and like the tail of an exponential distribution for high loads. [10] [11] [12]

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 probability theory, the Lindley equation, Lindley recursion or Lindley processes is a discrete-time stochastic process An where n takes integer values and:

In queueing theory, a discipline within the mathematical theory of probability, a Markovian arrival process is a mathematical model for the time between job arrivals to a system. The simplest such process is a Poisson process where the time between each arrival is exponentially distributed.

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.

U. Narayan Bhat is an Indian-born Mathematician, known for his contributions to queueing theory and reliability theory.

In queueing theory, a discipline within the mathematical theory of probability, Kingman's formula also known as the VUT equation, is an approximation for the mean waiting time in a G/G/1 queue. The formula is the product of three terms which depend on utilization (U), variability (V) and service time (T). It was first published by John Kingman in his 1961 paper The single server queue in heavy traffic. It is known to be generally very accurate, especially for a system operating close to saturation.

<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, an M/G/k queue is a queue model where arrivals are Markovian, 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.

In probability theory, reflected Brownian motion is a Wiener process in a space with reflecting boundaries. In the physical literature, this process describes diffusion in a confined space and it is often called confined Brownian motion. For example it can describe the motion of hard spheres in water confined between two walls.

In queueing theory, a discipline within the mathematical theory of probability, a layered queueing network is a queueing network model where the service time for each job at each service node is given by the response time of a queueing network. Resources can be nested and queues form along the nodes of the nesting structure. The nesting structure thus defines "layers" within the queueing model.

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, an M/D/c queue represents the queue length in a system having c servers, 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. The model is an extension of the M/D/1 queue which has only a single server.

In queueing theory, a discipline within the mathematical theory of probability, the G/M/1 queue represents the queue length in a system where interarrival times have a general distribution and service times for each job have an exponential distribution. The system is described in Kendall's notation where the G denotes a general distribution, M the exponential distribution for service times and the 1 that the model has a single server.

References

  1. ↑ Bhat, U. N. (2008). "The General Queue G/G/1 and Approximations". An Introduction to Queueing Theory . pp.  169–183. doi:10.1007/978-0-8176-4725-4_9. ISBN   978-0-8176-4724-7.
  2. ↑ Foss, S. (2011). "The G/G/1 Queue". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0878. ISBN   9780470400531.
  3. ↑ Kendall, D. G. (1953). "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain". The Annals of Mathematical Statistics. 24 (3): 338. doi: 10.1214/aoms/1177728975 . JSTOR   2236285.
  4. ↑ Smith, W. L. (1953). "On the distribution of queueing times". Mathematical Proceedings of the Cambridge Philosophical Society . 49 (3): 449. Bibcode:1953PCPS...49..449S. doi:10.1017/S0305004100028620.
  5. ↑ Grassmann, Winfried; Tavakoli, Javad (June 2019). "The Distribution of the Line Length in a Discrete Time GI/G/1 Queue". Performance Evaluation. 131: 43–53.
  6. ↑ Kingman, J. F. C.; Atiyah (October 1961). "The single server queue in heavy traffic". Mathematical Proceedings of the Cambridge Philosophical Society . 57 (4): 902. Bibcode:1961PCPS...57..902K. doi:10.1017/S0305004100036094. JSTOR   2984229.
  7. ↑ Prabhu, N. U. (1974). "Wiener-Hopf Techniques in Queueing Theory". Mathematical Methods in Queueing Theory. Lecture Notes in Economics and Mathematical Systems. Vol. 98. pp. 81–90. doi:10.1007/978-3-642-80838-8_5. ISBN   978-3-540-06763-4.
  8. 1 2 Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press. ISBN   9781439806586.
  9. ↑ 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.
  10. ↑ Harchol-Balter, M. (2012). "Task Assignment Policies for Server Farms". Performance Modeling and Design of Computer Systems. p. 408. doi:10.1017/CBO9781139226424.031. ISBN   9781139226424.
  11. ↑ Whitt, W. (2000). "The impact of a heavy-tailed service-time distribution upon the M/GI/s waiting-time distribution" (PDF). Queueing Systems. 36: 71–87. doi:10.1023/A:1019143505968.
  12. ↑ Foss, S.; Korshunov, D. (2006). "Heavy Tails in Multi-Server Queue". Queueing Systems . 52: 31. arXiv: 1303.4705 . doi:10.1007/s11134-006-3613-z.
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.