Im. 06009 RR348

IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

NOTE
ON THE M/M/1
FEEDBACK PROCESS

Jacques LABETOULLE
Guy PUJOLLE
Christine SOULA

Rapport de Recherche N° 348

Mars 1979

9p.
NOTE ON THE M/M/1 FEEDBACK PROCESS

Jacques Labetoulle, Guy Pujolle, Christine Soula

IRIA/LABORIA

Résumé :

Nous prouvons que le flux de rebouclage d'une file M/M/1 avec probabilité de retour en fin de la file d'attente n'est pas un processus de renouvellement.

Abstract :

We prove that the M/M/1 feedback stream is not even a renewal process.
Introduction

The M/M/1 queueing system is shown in figure 1. The arrival process is a poisson process with parameter $\lambda$. The queueing discipline is "first come, first served", and the service is exponential with parameter $\mu$. Upon completion of a service, the customer engages a Bernoulli switch : with fixed probability q, he leaves definitively the system and with probability p=1-q, he rejoins the queue. The feedback is assumed to be instantaneous. The times of service completions will be called "outputs". Exists from the system will be called "departures". Similarly, "inputs" and "arrivals" will be the moments when customers join the queue from outside or due to feedback), and enter the system respectively.

<figure><img src="image_2.png" /><figcaption>Figure 1</figcaption></figure>
Problems of the type we describe seem to have first been studied by Takacs [1].

Burke [2] shows that the interinput distribution fails to be poisson and Disney and McNickle [3] show this process is not even a renewal process.

Takacs [1] shows the departure process is a poisson process.
The output process is studied by Foley [4] and is proved to be neither
poisson nor renewal. Extensions to general Jackson network [5] are in-
troduced by Kelly [6], Melamed [7], Beutler and Melamed [8], Pujolle
and Soula [9], Labetoulle, Pujolle and Soula [10]. Mainly it is shown
that only flows without fedback customers are poisson and the input
distribution is equal to the output distribution.

Practically nothing is known about the feedback process. We
show here, this process fail to be a renewal process in the simple
M/M/1 case with feedback. For a general Jackson network it seems that
the flows with fedback customers are no longer renewal but this asser-
tion is not proved.

Let $\pi(i)$ be the stationary probability of state $i$. We have

$$
(1) \quad \pi(i) = \rho^i (1-\rho) = \left(\frac{\lambda}{\mu q}\right)^i (1-\frac{\lambda}{\mu q}) \quad i=0,1,\dots
$$

let us introduce the following function α(i).

$\alpha(i)$ is the L.S.T (Laplace Stieltjes Transformed) of the inter-
feedback times knowing that the queue is in state $i$.

Just after a feedback time, the queue is in state i with the
stationnary probability $\pi(i-1)$. Then the L.S.T of the time between two
feedbacks $\hat{r}(s)$ is given by

$$
\hat{r}(s) = \sum_{i=1}^{\infty} \pi(i-1)\alpha(i).
$$
To compute the function $\alpha(i)$, we use the following equations
(see [10])

$$
(2) \quad \alpha(i) = \frac{\lambda+\mu}{\lambda+\mu+s} \left[ \frac{\lambda}{\lambda+\mu} \alpha(i+1) + \frac{\mu q}{\lambda+\mu} \alpha(i-1) + \frac{\mu p}{\lambda+\mu} \right] \quad i > 0
$$

$$
(3) \quad \alpha(0) = \frac{\lambda}{\lambda+s} \alpha(1)
$$

Using (1) and (3), the summation of (2) for i=1 to ∞ after
multiplication by π(i-1) yields

$$
(4) \quad \hat{r}(s) = \frac{1}{\mu p + s} \left[ \mu p - \frac{\mu q}{\lambda} s \pi(0) \alpha(0) \right]
$$

And the function $\alpha(o)$ is determined as follows :

Setting $\alpha(i) = \Gamma(i) + \frac{\mu p}{\mu p + s}$ in (2) we get the equation

$$
(\lambda+\mu+s)\Gamma(i) = \lambda\Gamma(i+1) + uq \Gamma(i-1) \quad i \geq 1
$$

and a general solution of this last equation is

$$
(5) \quad \Gamma(i) = ax_1^i + b \cdot x_2^i,
$$

where $x_1, x_2$ are the solutions of :

$$
\lambda x^2 - (\lambda + \mu + s)x + \mu q = 0
$$

We have $x_1+x_2=1 + \frac{\mu+s}{\lambda}$; $x_1x_2 = \frac{\lambda}{\mu q}$. So, one root, say $x_2$, is such that
$|x_2| > 1$. As $i$ tends to infinity, $\alpha(i)$ obviously tends to $\frac{\mu p}{\mu p+s}$, so $b=0$.

In that case, we have

$$
x_1 = \frac{(\lambda + \mu + s) - \sqrt{(\lambda + \mu + s)^2 - 4\lambda\mu q}}{2\lambda}
$$

and $b$ is a constant.
Now, using (3) and (5) we deduce the system

$$
\left\{
\begin{array}{l}
\alpha(o) = a + \frac{\mu p}{\mu p + s} \\[2ex]
\frac{\lambda + s}{\lambda} \alpha(o) = a x_1 + \frac{\mu p}{\mu p + s}
\end{array}
\right.
$$

and we obtain

$$
\alpha(o) = \frac{\mu p}{\mu p + s} \frac{1 - x_1}{1 - x_1 + \frac{s}{\lambda}}
$$

So, the L.S.T of the interfeedback times is entirely determined.
Let (tᵢ) i=0,1,... be the sequence of feedback times. It is interesting
to show that the intervals (tᵢ₊₁ - tᵢ) have the same distribution. We
know that at time t₀, the system is in steady state with the probability
π(i) i=0,1,...,n,...

We want to compute the probability state π*(i) of the system
at time t₁. For this aim we introduce the conditionnal probability
π[j/i] :

$$
\begin{align*}
\pi[j/i] &= \operatorname{proba} \{j+1 \text{ customers at } t_1/i \text{ customers at } t_0\} \\
\pi^*(j) &= \sum_{i=0}^{\infty} \pi(j/i+1) \pi(i)
\end{align*}
$$

because at t₀ we have i customers with the probability π(i-1) [3].

We have :

$$
\begin{align*}
\pi(j/i) &= \frac{\lambda}{\lambda+\mu} \pi(j/i+1) + \frac{\mu q}{\lambda+\mu} \pi(j/i-1) + \frac{\mu p}{\lambda+\mu} \delta_{i-1,j} \\
(\lambda+\mu)\pi(j/i) &= \lambda\pi(j/i+1) + \mu q \pi(j/i-1) + \mu p \delta_{i-1,j}
\end{align*}
$$

where $\delta_{i,j}$ is the Kronecker Symbol. Multiplying by $\pi(i-1)$ and by summing on $i=1,...,\infty$ we obtain :

$$
(\lambda + \mu) \pi^*(j) = \mu q [\pi^*(j) - \pi(0)\pi(j/1)] + \mu q [\pi(0)\pi(j/0) + \frac{\lambda}{\mu q} \pi^*(j)] + \mu p \pi(j)
$$
or
$$ \mu p \pi^*(j) = \mu q \pi(o) [\pi(j/o) - \pi(j/1)] + \mu p \pi(j). $$

As $\pi(j/o) = \pi(j/1)$; this implies $\pi^*(j) = \pi(j)$ for all j.
So the intervals $(t_{i+1} - t_i)$ have the same distribution.

Let $\hat{r}_*(s)$ be L.S.T of the time between three feedback time (see figure 2).

<figure><img src="image_3.png" /><figcaption>Figure 2</figcaption></figure>

$\hat{r}(s)$ and $\hat{r}_*(s)$ can be written :

$$ \begin{cases} \hat{r}(s) = \sum_{i=1}^{\infty} \pi(i-1)\alpha(i) \\ \\ \hat{r}_*(s) = \sum_{i=1}^{\infty} \pi(i-1)\beta(i) \end{cases} $$

and $\beta(i)$ verifies the equation :

$$ \beta(i) = \frac{\lambda+\mu}{\lambda+\mu+s} \left[ \frac{\lambda}{\lambda+\mu} \beta(i+1) + \frac{\mu q}{\lambda+\mu} \beta(i-1) + \frac{\mu p}{\lambda+\mu} \alpha(i) \right] $$

or

$$ (7) \quad \begin{cases} (\lambda+\mu+s)\beta(i) = \lambda\beta(i+1) + \mu q\beta(i-1) + \mu p\alpha(i) \\ \\ (\lambda+s)\beta(o) = \lambda\beta(1) \end{cases} $$

As we have seen $\alpha(i)$ writes as follows :

$$ \frac{\mu p}{\mu p+s} + ax_1^i $$
we have :

$$ (\lambda+\mu+s)\beta(i) = \lambda\beta(i+1) + \mu q\beta(i-1) + \mu p \alpha_1^i + \frac{(\mu p)^2}{\mu p + s} $$

setting $\gamma(i) = \beta(i) - \left(\frac{\mu p}{\mu p + s}\right)^2$ we obtain :

$$ (\lambda+\mu+s)\gamma(i) = \lambda\gamma(i+1) + \mu q\gamma(i-1) + \mu p \alpha_1^i $$

As a solution we have :

$$ \gamma(i) = b(i+k)x_1^i $$

where b is a constant and $k \in N$,

This gives :

$$ (\lambda+\mu+s)b(i+k)x_1^i = \lambda b(i+k+1)x_1^{i+1} + \mu q b(i+k-1)x_1^{i-1} + \mu p \alpha_1^i $$

dividing by $\rho_1^{i-1}$ and simplifying we obtain :

$$ \lambda b \rho_1^2 - \mu q b + \mu p \alpha_1 = 0 $$

then $b = \frac{p \alpha_1}{q(1-\rho x_1^2)}$.

Therefore $\beta(0)$ is determined by the following system :

$$ \begin{cases} \beta(o) = kb + \left(\frac{\mu p}{\mu p + s}\right)^2 \\ \frac{\lambda+s}{\lambda}\beta(o) = (k+1)bx_1 + \left(\frac{\mu p}{\mu p + s}\right)^2 = kbx_1 + bx_1 + \left(\frac{\mu p}{\mu p + s}\right)^2 \end{cases} $$

and we obtain after some algebra :

$$ \beta(o) = \left(\frac{\mu p}{\mu p + s}\right)^2 \frac{1-x_1}{1-x_1+\frac{s}{\lambda}} + \frac{p \alpha_1^2}{q(1-\rho x_1^2)} \frac{1}{1-x_1+\frac{1}{\lambda}} $$
From the system of equations (7), by summation on i and after multiplication by $\pi(i-1)$ we obtain :

$$ (\mu p + s) \hat{r}_*(s) = \mu p \hat{r}(s) + \mu q \pi(o) [\beta(o) - \beta(1)] $$

As $\beta(o)-\beta(1) = -\beta(o) \frac{s}{\lambda}$, we have :

$$ (8) \quad (\mu p + s) \hat{r}_*(s) = \mu p \hat{r}(s) - \frac{\mu q s}{\lambda} \pi(o) \beta(o) $$

For the feedback process be a renewal process the equation $\hat{r}_*(s) = \hat{r}^2(s)$ must be satisfied.

Using this last equality, equation (8) reduce to :

$$ \beta(o) = \alpha(o) \hat{r}(s) $$

We show that this last equality is false and so we prove the feedback process is not a renewal process.

Knowing the values of $\hat{r}(s)$, $\alpha(o)$ and $\beta(o)$ and using $a = \frac{\mu p}{\mu p+s} \left[ \frac{-s/\lambda}{1-x_1+s/\lambda} \right]$ the equality $\beta(o) = \alpha(o) \hat{r}(s)$ becomes [see [11] for more details]

$$ (9) \quad \left(\frac{\mu p}{\mu p+s}\right)^2 (1-x_1)^2 \frac{1-\rho}{\rho \mu p} = \frac{\rho x_1^2}{\lambda q(1-\rho x_1^2)} $$

As $x_1$ is the solution of the equation $\lambda x_1^2 - (\lambda+\mu+s)x_1 + \mu q = 0$, we have :

$$ (1-x_1)(1-\rho x_1) = \frac{\mu p + s}{\mu q} x_1 $$

Using this last equation (9) writes as follows :

$$ \rho(1-x_1)^2 = 0 $$

For the feedback process be renewal it is necessary that $x_1=1$, or $p=0$ or $\rho=0$. The condition $x_1=1$ is impossible; $\rho=0$ corresponds to a stream of value 0 and $p=0$ to a system without feedback. In the other cases the feedback process is not a renewal process.
REFERENCES

[ 1] Takacs, L. - "A single server queue with feedback", Bell Systems Tech. J. 42, 505-519, 1963.

[ 2] Burke, P.J. - "Proof of a conjecture on the interarrival time distribution in a M/M/1 queue with feedback" IEEE Trans. on Com. 24, 175-178, 1976.

[ 3] Disney, R., McNickle, D.C. - "The M/G/1 queue with instantaneous Bernoulli feedback", Technical Report 77-4, University of Michigan, Ann Arbor, 1977.

[ 4] Foley, R.D. - "On the output process of an M/M/1 queue with feedback", Research Report of the University of Michigan, 1977.

[ 5] Jackson, J.R. - "Jobshop-like queueing systems", Management Sciences, 10, 1, 131-142, 1963.

[ 6] Kelly, F.P. - "Networks of queues", Adv. Appl. Prob. 8, 416-432, 1976.

[ 7] Melamed, B. - "Characterization of Poisson Traffic Streams in Jackson Queueing network", Technical Report 77-2, University of Michigan, Ann Arbor, 1977.

[ 8] Beutler, and Melamed, B. - "Decomposition and customer streams of feedback queueing networks in equilibrium", Technical report 77-1, University of Michigan, 1977.

[ 9] Pujolle, G., Soula, C. - "A study of flows in queueing networks and an approximate method for solution", proc. 4th International Symposium on Modelling, Vienne, February 1979.

[10] Labetoulle, J., Pujolle, G., Soula, C. - "Distribution of the flows in a general Jackson Network", IRIA-Research Report n° 241, 1979.

[11] Soula, C. - "Les flots dans les réseaux de Jackson", Thesis, to appear.