6
$\begingroup$

I'm studying an M/M/c queuing model with an unusual (?) dispatching discipline:

  1. Servers are numbered 1...c
  2. The servers have an identical mean service time, exponentially distributed (as usual), which does not vary with time or load
  3. If all servers are busy, the transaction is allocated to the first server that becomes free
  4. If any servers are free, the transaction is allocated to the free server with the lowest number.

I am especially interested in the mean server utilisation ($\rho_i$) for each server (which could be derived from the proportion $p_i$ of jobs served by server $i$), and also its distribution (though I guess that is more difficult).

What results are available which give the distribution of traffic going to each server?

$\endgroup$
7
  • 1
    $\begingroup$ Nice exercise. I guess $\lambda\leqslant c\mu$? Did you check the obvious, say Asmussen's book? $\endgroup$
    – Did
    Commented May 23, 2015 at 13:44
  • 1
    $\begingroup$ @Did : Oh, yes, otherwise I already know the distribution :-) I'm afraid I didn't check Asmussen; my (rural) local library doesn't have one; and the question is not sufficiently main-stream (for me) to justify spending over £70 on my own copy. $\endgroup$ Commented May 23, 2015 at 18:28
  • $\begingroup$ Are the servers identical? Does each server have its own queue? For the second bullet point: does this mean you know the service time of each customer and allocate him to a specific queue at the moment of arrival, or do you place the customer in a general queue and wait for a server to become idle and then sent the customer to the queue of the server that has become idle? $\endgroup$
    – Ritz
    Commented May 27, 2015 at 7:28
  • $\begingroup$ @Ritz : The servers are identical; there is a single customer queue from which all the servers are fed; the only difference between this and a "normal" queuing system lies in the way the transactions are dispatched, from the queue to whichever server the dispatching rules decide. Dispatching does not depend on the expected service time, which unknown other than its mean and the fact that it is exponentially distributed (I.e. the simplest case) $\endgroup$ Commented May 27, 2015 at 14:10
  • $\begingroup$ Bullet point 3 is just the normal first-come, first-served principle, where you assign the job at the head of the line at the instant a server becomes available. I guess then the only difference with a standard $M/M/c$ lies in bullet point 4. Instead of assigning jobs uniformly at random to one of the idle servers, you assign it to the server with the lowest index. Are you interested in the proportion $p_i$ of jobs that go to server $i$, or in other terms, the proportion $p_i$ of jobs that are served by server $i$? $\endgroup$
    – Ritz
    Commented May 28, 2015 at 7:22

1 Answer 1

1
$\begingroup$

This is (an attempt at) a partial answer.

I think that you should be able to decouple the server selection aspect from the composite load aspect, since the servers are identical with exponentially distributed service time $\mu$. That is, one can analyze the number in system (irrespective of distribution across the servers) as an ordinary M/M/$c$ system with the usual distribution:

$$ p_k = \begin{cases} \hfill p_0 \frac{\sigma^k}{k!} \hfill & k \leq c \\ \hfill p_0 \frac{\sigma^k}{c!c^{k-c}} \hfill & k \geq c \end{cases} $$

where $\sigma = \lambda/\mu$ and

$$ p_0 = \left(\sum_{k=0}^{c-1} \frac{\sigma^k}{k!} + \sum_{k=c}^\infty \frac{\sigma^k}{c!c^{k-c}}\right)^{-1} = \left(\frac{c\sigma^c}{c!(c-\sigma)} + \sum_{k=0}^{c-1} \frac{\sigma^k}{k!}\right)^{-1} $$

For the simplest case $c=2$, we can then disentangle the individual states $(1, 0)$ (server $1$ busy, server $2$ idle) and $(0, 1)$ (server $1$ idle, server $2$ busy) by writing

$$ \lambda p_0 = \mu p_{1, 0} + \mu p_{0, 1} = \mu p_1 $$ $$ (\lambda+\mu) p_{1, 0} = \lambda p_0 + \mu p_2 $$ $$ (\lambda+\mu) p_{0, 1} = \mu p_2 $$ $$ 2\mu p_2 = \lambda p_{1, 0} + \lambda p_{0, 1} = \lambda p_1 $$

Together, these equations yield

$$ p_{1, 0} = \frac{2+\sigma}{2+2\sigma} \, p_1 $$ $$ p_{0, 1} = \frac{\sigma}{2+2\sigma} \, p_1 $$

I'm still thinking about (a) whether this is all correct for $c = 2$, and (b) if it is, how one might generalize for all $c$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .