User:Tqzhang1010/sandbox

brief: We will add something to the existing page.

topic: M/D/1 queue

What we modified

• 1Model definition:
• Add transition matrix; classic performance metrics ; proof of the equations; example; relations of the equations
• 2Stationary distribution
• 3Delay
• 4Busy period
• 5Finite capacity
  • 5.1Stationary distribution
  • 5.2Transient solution Add equations about this section according to the reference paper.
• Add 6. Application
• 7 References

Model definition[edit]

• An M/D/1 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 system, including any currently in service.
  • Arrivals occur at rate λ according to a Poisson process and move the process from state i to i + 1.
  • Service times are deterministic time D (serving at rate μ = 1/D).
  • A single server serves customers one at a time from the front of the queue, according to a first-come, first-served discipline. When the service is complete the customer leaves the queue and the number of customers in the system reduces by one.
  • The buffer is of infinite size, so there is no limit on the number of customers it can contain.

Classic performance metrics:

File:Basic matrix for md1.png

Example:

Customers arrive a Starbucks line at a rate of 20 per hour, and follows an exponential distribution. There is only one server, the service rate is at a constant of 30 per hour.

Arrival Rate: 20 per hour

Service Rate: 60 per hour

ρ=20/30=2/3

Using the queueing theory equations, the results are as following:

Average number in line= 0.6667

Average number in system: 1.333

Average time in line: 0.033

Average time in system: 0.067

Relation for Mean Waiting Time in M/M/1 and M/D/1 queues[10]:

For an equilibrium M/G/1 queue, the expected value of the time W spent by a customer in the queue are given by Pollaczek-Khintchine formula as below

where τ is the mean service time; ${\textstyle \sigma ^{2}}$ is the variance of service time; and ρ=λτ < 1, λ being the arrival rate of the customers.

For M/M/1 queue, the service times are exponentially distributed, then ${\textstyle \sigma ^{2}}$=${\textstyle \tau ^{2}}$ and the mean waiting time in the queue denoted by WM is given by the following equation

File:Equation222222.png

Using this, the corresponding equation for M/D/1 queue can be derived, assuming constant service times. Then the variance of service time becomes zero, i.e.  ${\textstyle \sigma ^{2}}$=0.  The mean waiting time in the M/D/1 queue denoted as WD is given by the following equation

File:Equation333333.png

From the two equations above, we can infer that Mean queue length in M/M/1 queue is twice that in M/D/1 queue.

Stationary distribution[edit]

• The number of jobs in the queue can be written as an M/G/1 type Markov chain and the stationary distribution found for state i (written π_i) in the case D = 1 to be^[4]

Delay[edit]

• Define ρ = λ/μ as the utilization; then the mean delay in the system in an M/D/1 queue is^[5]

  and in the queue:

Busy period[edit]

• The busy period is the time period measured from the instant a first customer arrives at an empty queue to the time when the queue is again empty. This time period is equal to D times the number of customers served. If ρ < 1, then the number of customers served during a busy period of the queue has a Borel distribution with parameter ρ.^[6][7]

Finite capacity[edit]

Stationary distribution[edit]

• A stationary distribution for the number of customers in the queue and mean queue length can be computed using probability generating functions.^[8]

Transient solution[edit]

• The transient solution of an M/D/1 queue of finite capacity N, often written M/D/1/N, was published by Garcia et al in 2002.^[9]

(Adding equations below according to the reference.)

The mean number of customers in M/D/1/N queue presented in Garcia et al. 2002 is as follows:

File:Mean number of customers.png

The mean waiting time W N in the M/D/1/N queuing system presented in Garcia et al. 2002 is as follows:

File:Mean waiting time.png

References[edit]

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

2.     Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems 63: 3–4. doi:10.1007/s11134-009-9147-4.

3.     Erlang, A. K. (1909). "The theory of probabilities and telephone conversations" (PDF). Nyt Tidsskrift for Matematik B 20: 33–39. Archived from the original (PDF) on October 1, 2011.

4.     Nakagawa, Kenji (2005). "On the Series Expansion for the Stationary Probabilities of an M/D/1 queue" (PDF). Journal of the Operations Research Society of Japan 48 (2): 111–122.

5.     Cahn, Robert S. (1998). Wide Area Network Design:Concepts and Tools for Optimization. Morgan Kaufmann. p. 319. ISBN 1558604588.

6.     Tanner, J. C. (1961). "A derivation of the Borel distribution". Biometrika 48: 222–224. doi:10.1093/biomet/48.1-2.222. JSTOR 2333154.

7.     Haight, F. A.; Breuer, M. A. (1960). "The Borel-Tanner distribution". Biometrika 47: 143. doi:10.1093/biomet/47.1-2.143. JSTOR 2332966.

8.     Brun, Olivier; Garcia, Jean-Marie (2000). "Analytical Solution of Finite Capacity M/D/1 Queues". Journal of Applied Probability (Applied Probability Trust) 37 (4): 1092–1098. doi:10.1239/jap/1014843086. JSTOR 3215497.

9.     Garcia, Jean-Marie; Brun, Olivier; Gauchard, David (2002). "Transient Analytical Solution of M/D/1/N Queues". Journal of Applied Probability (Applied Probability Trust) 39 (4): 853–864. JSTOR 3216008.

10. Cooper, Robert B. (1981). Introduction to Queuing Theory. Elsevier Science Publishing Co. p. 189 ISBN 0-444-00379-7