M/D/1 queue: Difference between revisions

Revision as of 21:36, 23 May 2016

Revision as of 21:41, 23 May 2016

Line 32:

So the utilization of the server is: ρ=20/30=2/3. Using the metrics shown above, the results are as following: 1) Average number in line L_Q= 0.6667; 2) Average number in system L =1.333; 3) Average time in line ω_Q = 0.033 hour; 4) Average time in system ω = 0.067 hour.

=== RelationRelations for Mean Waiting Time in M/M/1 and M/D/1 queues ===

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<ref name=":0">{{Cite book|title=Introduction to Queuing Theory|last=Cooper|first=Robert B.|publisher=Elsevier Science Publishing Co.|year=1981|isbn=0-444-00379-7|___location=|pages=189}}</ref>:

<math>E(W)=\frac{\rho\tau}{2(1-\rho)}(1+\frac{\sigma^2}{\tau^2})</math>

where τ is the mean service time; σ<math display="inline"sup>\sigma^2</mathsup> 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 σ<math display="inline"sup>\sigma^2</mathsup> = τ<math display="inline"sup>\tau^2</mathsup> and the mean waiting time in the queue denoted by W_M is given by the following equation<ref name=":0" />:

<math>{W_M}=\frac{\rho\tau}{1-\rho}</math>

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. σ<math display="inline"sup>\sigma^2</mathsup> = 0. The mean waiting time in the M/D/1 queue denoted as W_D is given by the following equation<ref name=":0" />:

<math>{W_D}=\frac{\rho\tau}{2(1-\rho)}</math>

Line 51:

==Stationary distribution==

The number of jobs in the queue can be written as an [[M/G/1 queue|M/G/1 type Markov chain]] and the stationary distribution found for state ''i'' (written π_''i'') in the case ''D''&nbsp;=&nbsp;1 to be<ref>{{cite journal| url = http://www.orsj.or.jp/~archive/pdf/e_mag/Vol.48_2_111.pdf | journal = Journal of the Operations Research Society of Japan | volume = 48 | year = 2005 | issue = 2 | pages = 111–122 | title = On the Series Expansion for the Stationary Probabilities of an M/D/1 queue | first = Kenji | last = Nakagawa}}</ref>

:<math>\begin{align}\pi_0 &= 1-\lambda \\

\pi_1 &= (1-\lambda)(e^\lambda - 1)\\

Line 58:

==Delay==

Define ''ρ''&nbsp;=&nbsp;''λ''/''μ'' as the utilization; then the mean delay in the system in an M/D/1 queue is<ref>{{cite book|title=Wide Area Network Design:Concepts and Tools for Optimization|page=319|first=Robert S.|last=Cahn|year=1998|publisher=Morgan Kaufmann|isbn=1558604588}}</ref>

::<math>\frac{1}{2\mu}\cdot\frac{2-\rho}{1-\rho}.</math>

and in the queue:

Line 88:

</math>

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

<math>W_N=(N-1-\frac{\sum_{k=0}^{N-1}b_k-N}{\rho b_{N-1}})T</math>