User:Tqzhang1010/sandbox

We added the following sections to the existing page. The detailed citations are in the existing page.

The state space diagram for M/D/1 queue is as below:

Stage Space Diagram of M/D/1 Queue

Transition Matrix:

$P={\begin{pmatrix}a_{0}&a_{1}&a_{2}&a_{3}&...\\a_{0}&a_{1}&a_{2}&a_{3}&...\\0&a_{0}&a_{1}&a_{2}&...\\0&0&a_{0}&a_{1}&...\\...&...&...&...&...\\\end{pmatrix}}$ ， $a_{n}={\frac {\lambda ^{n}}{n!}}e^{-\lambda }$, n = 0,1,....

Classic performance metrics:

$L=\rho +{\frac {1}{2}}\left({\frac {\rho ^{2}}{1-\rho }}\right);$

$L_{Q}={\frac {1}{2}}\left({\frac {\rho ^{2}}{1-\rho }}\right);$

$\omega ={\frac {1}{\mu }}+{\frac {\rho }{2\mu (1-\rho )}};$

$\omega _{Q}={\frac {\rho }{2\mu (1-\rho )}}$

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:

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

$E(W)={\frac {\rho \tau }{2(1-\rho )}}(1+{\frac {\sigma ^{2}}{\tau ^{2}}})$

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

${\overline {W_{M}}}={\frac {\rho \tau }{1-\rho }}$

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

${\overline {W_{D}}}={\frac {\rho \tau }{2(1-\rho )}}$

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.

Finite capacity

Stationary distribution

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

$P_{0}(N)={\frac {1}{1+\rho b_{N-1}}};$

$P_{N}(N)=1-{\frac {b_{N-1}}{1+\rho b_{N-1}}};$

$P_{j}(N)={\frac {b_{j}-b_{j-1}}{1+\rho b_{N-1}}}$， j = 1,..., N-1.

Transient solution

• 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]

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

$X_{N}=N-{\frac {\sum _{k=0}^{N-1}b_{k}}{1+\rho b_{N-1}}};$

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

$W_{N}=(N-1-{\frac {\sum _{k=0}^{N-1}b_{k}-N}{\rho b_{N-1}}})T$

Application

Includes applications in wide area network design, where a single central processor to read the headers of the packets arriving in exponential fashion, then computes the next adapter to which each packet should go and dispatch the packets accordingly. Here the service time is the processing of the packet header and cyclic redundancy check, which are independent of the length of each arriving packets. Hence, it can be modeled as a M/D/1 queue.