3
$\begingroup$

This is a question about intuition in understanding the fluid limit queuing system.

Assume we have a sequence of queuing systems $\{S^N\}_{N=1}^{\infty}$ with N servers and each server has unit service rate. Assume the arrival rate of the system is $\lambda N$, where $\lambda<1$ is a constant. People come to the system and select one server to queue there. Let $k_i$ be the number of servers with $i$ people in line. So $\pi_i=\frac{k_i}{N}$ is the fraction of servers with $i$ people in line.

My first question is about understanding the situation when $N\rightarrow\infty$. I don't know if it is called the "fluid limit". Imagining the system as described above starts with empty, then every unit of time, roughly $\lambda N dt$ amount of people come in. We assume that each person chooses the shortest queue, i.e., the empty queue. To make life even simpler, for this moment, assume not service process, i.e., people coming in, and select a server who never start to work and just standing there. Then there are two ways of understanding the system:

A) the amount $\lambda N dt$ of people is uniformly assigned to each server, so that each server will have people, but not a whole people, it is only some fraction of people (e.g., $\lambda<1$ people)

B) only $\lambda$ fraction of the servers will have 1 people and the remaining $1-\lambda$ fraction of servers will have 0 people.

Which intuition is correct? There is a big difference between A and B. If A is correct, then this means, there is no queue of integer length. If we imagining people coming in like "fluid", then it makes sense. However, if A is correct, then it will implies that $\pi_1=\frac{k_1}{N}$ converges to 0, since there is no queue of integer length. If B is correct, then this means, there are only queues of integer length, which sounds more intuitive. And it will implies $\pi^1=\frac{k_1}{N}$ converges to $\lambda t$.

The things that are puzzling me the most is that, I think intuition B is very clearly in my setting, i.e., queue should increase or decrease with integer size, e.g., if there are empty queue, then people join that empty queue and hence we have queue of length one, if all queue are of length one, then people join queue of length one and hence create queue of length two, etc. If there is a service process, e.g., each server has identical service rate $\mu=1$, then as $N\rightarrow\infty$, then it should be clear that $\frac{d\pi_1(t)}{dt}=-\pi_1(t)+\lambda$. I am wondering where does intuition A come from? Is this because, in the "fluid model", people usually talking about the process $Q(t)$, which is the number of people in the queue, then they do scaling $\frac{1}{N}Q(t)$ and call this process $\bar{Q}(t)$, then because in the original $Q(t)$ process, every time when people come or leave, the process jump up or down by 1 unit, hence, after the scaling $\frac{1}{N}$, the scaled process $\bar{Q}(t)$ has a continuous state, so that's why they say queue (or people) become "fluid" such that "queues" are no longer has integer size?

So in my problem, should I call it "Fluid model"? Is there a clear definition of the terminology of "Fluid model"?

$\endgroup$
3
$\begingroup$

For fixed $t<1/\lambda$ it seems that intuition B is correct as $N \to \infty $. In this case, using the large deviations, one can see that it is highly unlikely that more than $(N+\varepsilon)\lambda t$ customers have arrived in time interval [0,t]. As there are $N$ servers and customers join the shortest queue it means that there will be empty servers and new customers will simply join them. Therefore, for $t<1/\lambda$ there will be a proportion of $\lambda t$ servers with 1 customer and $(1-\lambda t)$ servers with 0 customers.

It might be good to have a look at N. D. Vvedenskaya, R. L. Dobrushin, F. I. Karpelevich, “Queueing System with Selection of the Shortest of Two Queues: An Asymptotic Approach”, Probl. Peredachi Inf., 32:1 (1996), 20–34, who studied a related system.

$\endgroup$
  • $\begingroup$ Thanks! That one is helpful. I edited my question a little bit, could you please have a look at it? $\endgroup$ – FTXX May 30 '16 at 13:59
  • $\begingroup$ I think that intuition A shows what will happen in the long run. When $t$ is large and no service happens, then the customers will be distributed approximately uniformly among the servers. I am not sure that 'fluid model' is a good terminology. The fluid models which I saw had finite number of queues $(Q_1(t),Q_2(t), Q_K(t))$ which were rescaled. Here the number of queues increases as well and mean-field dynamics, or hydrodynamic (or thermodynamic) limit would probably be better terms. Here is another related work arxiv.org/abs/1512.05056 $\endgroup$ – Denis Denisov May 30 '16 at 22:20
1
$\begingroup$

in the fluid (or continuum) limit, you should allow $k$ to vary continuously and consider instead of $\pi_k$ (the probability of a queue of exactly length $k$) the probability $\pi(k)dk$ that a queue has length between $k$ and $k+dk$; the difference between A and B is then whether $\pi(k)$ varies continuously or as a step function, and in the large-$N$ limit these two descriptions become equivalent.

$\endgroup$
  • $\begingroup$ So your answer indicates that $\pi_1(t)$, i.e., the fraction of queue with EXACTLY one people, should be 0 as $N\rightarrow\infty$, right? But when I run a simulation, it seems that $\pi_1(t)\rightarrow \lambda t$. I think I want to make a clarification. If we let $Q_1(t)$ be the queue length process at server 1, then I agree, if you do the scaling $\frac{1}{N}Q(t)$, then as $N\rightarrow\infty$, then this stuff becomes continuous. But, $\pi_1(t)$ is not $\frac{1}{N}Q(t)$. So I guess, in my problem, there is no "scaling" as in the "fluid limit". I guess my case should not be called fluid limit $\endgroup$ – FTXX May 30 '16 at 5:23
1
$\begingroup$

To me, there are two types of continuous approximation in queuing theory: fluid approximation and mean-field approximation.

1/ Fluid approximation usually corresponds to scaling the initial number of packets per server to infinity. At the end, you obtain an ODE $dx_k/dt$, where $x_k$ is the "number" of packets waiting at server k.

This is often used to study the stability of queuing systems and a good reference is https://projecteuclid.org/euclid.ps/1220879338

2/ Mean-field approximation corresponds to scaling the number of servers to infinity. At the end, you obtain an ODE on $\pi_i$, where $\pi_i$ is the fraction of servers that have $i$ packets in your system. This corresponds to your case, for which the ODE is:
$$ \frac{d}{dt} \pi_i = \lambda(\pi_{i-1}-\pi_i) + (\pi_{i+1}-\pi) $$ There is a large literature on the subject but most papers are focused on specific examples. The paper from Vvedenskaya et al. mentioned by Denis is one of them. You can also look at http://members.unine.ch/michel.benaim/perso/pe-mf-tr.pdf

$\endgroup$

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.