1
$\begingroup$

So I am right off the boat with queuing theory and have been simulating M/M/1/N queues but I am faced with this phenomenon where the distribution across the wait time ranges approaches a uniform distribution when the traffic intensity is: $$\varrho=\frac{\lambda}{\mu}=\frac{3}{2} > 1$$ $$\varrho: \text{Traffic intensity}$$ $$\lambda: \text{Arrival rate}$$ $$\mu: \text{Processing rate}$$ when the number of customers is small, 1000 as in the first simulation, I get a noisy distribution but as I increase the number of customers, as to 10 million in the second simulation, it seems to be suggesting a uniform distribution across wait time ranges.

Here are screenshots of both simulations with 1000 and 10 million customers, respectively:

This is a screenshot illustrating the simulation with 1000 customers.

This is a screenshot illustrating the simulation with 10 million customers.

So far I thought of the following: that for higher values of N as N denotes the Number of customers, the inter-arrival and inter-departure periods will approach a certain value X so that they increase with a certain rate that guarantees that the waiting time ranges are uniform. Since the inter-arrival times are exponential random variables being a Poisson Process having independent increments, then I can think of the of the 10 million queue as 10000 of smaller 1000-queues, and using the Central Limit Theorem, it follows that the mean of means will be the value X and thus explain such a uniform distribution.

I don't really know if I am right or if I have mixed things up, I hope to find someone to clarify this with its mathematical/statistical backgrounds.

Note: I have edited the question to illustrate that it's an M/M/1/N queue in which the number of customers in a queue is determined and thus is stable. Simulations illustrated in the question use N = 1000 and N = 10 million.

Any help would be apprecited and thanks in advance ^^

$\endgroup$
  • $\begingroup$ For me it is unclear what you're specifically looking at. Are you looking at waiting time distribution? And what do you mean simulation 10 million customers, are you simulation 10 million arrivals and looking at their waiting times and log those? Furthermore, how do you initialize the system as you simulate it? Normally, you would expect that in an overloaded M/M/1 the waiting time goes to infinity as the system is not positive recurrent if you view it as a Markov chain. $\endgroup$ – Tim Huijgens Apr 28 '17 at 17:20
  • $\begingroup$ Yes it's as you mentioned, I simulate the 10 million arrivals, log their waiting times, form a histogram, and look at their distribution. An example of the running logic is that I call mm1_que_sim(10_000_000, 3, 2) ~ to start the simulation and plot_hist(queue) ~ to get the distribution of the waiting times returned, as illustrated in the provided screenshots. $\endgroup$ – Mourad Sheriey Apr 28 '17 at 17:39
  • $\begingroup$ Note: I have edited the question to illustrate that it's an M/M/1/N queue in which the number of customers in a queue is limited and thus is stable. Simulations illustrated in the question use N = 1000 and N = 10 million. $\endgroup$ – Mourad Sheriey Apr 28 '17 at 20:14
  • $\begingroup$ Ah, the bounded buffer is indeed a more natural setup. The initialization can however still be important since if it has to converge to a stationary regime then it will mess up your distribution. Furthermore, it may be insightful to look at the problem from the perspective of a customer. Since each customer finds a certain number of customers in the system and thus has to wait for as many exponential phases. Therefore the waiting time distribution is some sort of phase type distribution, which may wel reduce to an uniform one, but I can't really see how this would work. $\endgroup$ – Tim Huijgens Apr 28 '17 at 20:53
  • $\begingroup$ Also, I guess you're using discrete event simulation for this. You also may want to check some performance measures in the means to see whether these fit on your data. You could for instance look at the stationary distribution and mean waiting time and mean queue length (which are known). $\endgroup$ – Tim Huijgens Apr 28 '17 at 20:55
1
$\begingroup$

This queue is overloaded, so for large $n$

  • the $n$th customer arrives roughly (LLN) at time $\frac{1}{\lambda} n$

  • by which time roughly $\frac{\mu}{\lambda} n$ customers have been served

  • so there are roughly $\frac{\lambda-\mu}{\lambda} n$ customers still in the queue

  • so has to queue roughly time $\frac{\lambda-\mu}{\lambda \mu} n$ to get service and then takes about time $\frac{1}{\mu} $ to be served.

For example, if $\lambda =3$ and $\mu=2$, you have $\frac{\lambda-\mu}{\lambda}=\frac16$ so the $n$th customer might expect to wait for a time about $\frac16n$.

This means that roughly the first $333,333$ customers might expect to wait up to about $55,555$; roughly the second $333,333$ customers might expect to wait between about $55,555$ and $111,111$; and so on, with roughly the thirtieth and final $333,333$ customers of the $10,000,000$ expecting to wait between about $1,611,111$ and $1,666,666$. And this is what your second graph shows, with the fluctuations due to random times in simulations becoming relatively small.

$\endgroup$
  • $\begingroup$ So this is why when I increase the number of bins in the histogram, it shows a more noisy distribution as it puts more emphasis on these relatively small fluctuations, right? Is there a name for such a phenomenon? $\endgroup$ – Mourad Sheriey Apr 29 '17 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.