How Do You Calculate Idle and Blocking Probabilities in M/D/1/n Queues?

[Turboshortbus]

Hello PF,

I have an assignment on M/D/1/n queues and between all the formulas and theory, I am completely lost. I need to be able to calculate the idle probability, blocking probability, and average waiting time for different buffer sizes n (0,1,4, etc.). I can find the answers for the boundary cases 0 and infiniti, but its the others I am clueless. Can anyone give me some tips to point me in the right direction?

 

[SW VandeCarr]

Hello PF,

I have an assignment on M/D/1/n queues and between all the formulas and theory. I am completely lost. I need to be able to calculate the idle probability, blocking probability, and average waiting time for different buffer sizes n (0,1,4, etc.). I can find the answers for the boundary cases 0 and infiniti, but its the others I am clueless. Can anyone give me some tips to point me in the right direction?

With the M/D/n type queue you usually have a Poisson arrival process and a deterministic service process. For any given $\lambda$ (mean arrival rate) you can calculate the probability that the actual rate of arrivals exceeds the service capacity using the Poisson distribution. Calculators are available online or in statistical software. This would be the blocking probability. The idle probability is when the arrival rate falls below the service capacity leaving at least one server idle. The stationary state is when the system is in equilibrium. Average waiting time is just $1/\lambda$ and $k/\lambda$ is the average waiting time for the kth entity in the buffer. The buffer is simply the "waiting room" or allowable queue. The blocking probability is usually adjusted so that blocking only occurs when the buffer is full.

There's quite a few papers and articles available if you google queuing therory or Erlang's formulas.

 

[SW VandeCarr]

There's quite a few papers and articles available if you google queuing therory or Erlang's formulas.

Spelling and typo corrections: Apparently the word is "queueing" but my spellcheck accepts "queuing" and not "queueing". "Theory" is just a typo.

 

[Turboshortbus]

I have determined my utilizations and chance of blocking for various n size buffers but I am unsure how to calculate the estimated waiting times. I can use the pollaczek kinchen formula for n = 0 and infiniti but am unsure how to find the W(n) for finite buffers...any pointers anyone?

I think I should use Little's Theorem, but I don't have a formula for the queue length in a M/D/1/n system.

 

[SW VandeCarr]

I have determined my utilizations and chance of blocking for various n size buffers but I am unsure how to calculate the estimated waiting times. I can use the pollaczek kinchen formula for n = 0 and infiniti but am unsure how to find the W(n) for finite buffers...any pointers anyone?

I think I should use Little's Theorem, but I don't have a formula for the queue length in a M/D/1/n system.

It doesn't look like anyone else is going to respond to your question so you'll have to put up with (or ignore) me just one more time. First this reference:

http://spiderman-2.laas.fr/esquimaux/Documents/md1n-transitoire.pdf

Note some of the formulas refer to the probability mass function of the Poisson distribution. The calculations are tedious and most people use tables or calculators.

I outlined a direction for a steady state solution in my last post which either you did not understand or found too superficial. I suspect the former because you keep asking for a solution for W(n) without specifying whether it's the mean waiting time or the distribution of waiting times. Waiting time is a random variable in this kind of queue.

In the steady state, the mean waiting time for the first arrival will be zero if the service process is efficient. However, because the arrival process is a random variable with a mean $\lambda$ there will be queues as well as idle time for a fixed service capacity at various points. To make such a system more efficient a buffer is created that holds arrivals when queues develop which are then served during what would otherwise be idle time for the service process. I explained how to calculate the expected waiting time for the kth customer in the buffer in my last post.

It's clear that an inefficient service process will lead to an ever growing queue or to a long term excess service capacity. In a customer oriented situation, the former leads to customer losses because real queues are finite and the latter leads to financial losses.

You may know all of this, in which case others might be interested.