IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

ERGODICITY CONDITIONS
AND
CONGESTION CONTROL
IN
COMPUTER NETWORKS

G. PUJOLLE

Rapport de Recherche N° 190
Octobre 1976
ERGODICITY CONDITIONS AND CONGESTION CONTROL IN
COMPUTER NETWORKS

G. Pujolle

IRIA/LABORIA

Résumé

Les conditions d'ergodicité sont obtenues dans deux cas :

- lorsque la prévention est utilisée pour éviter la congestion, de telle sorte que la demande puisse être satisfaite par les ressources disponibles,

- lorsqu'un temps de séjour maximum ou «time-out» est introduit comme méthode pour guérir la congestion quand elle apparaît.

Nous modélisons un réseau de communications par commutation de paquets, par une suite de stations en série. Nos principaux résultats sont les suivants :

- nous donnons une méthode numérique pour obtenir la condition d'ergodicité d'une suite de files d'attente à capacité limitée et dont la durée de service a une distribution quelconque,

- nous étendons la condition classique d'ergodicité d'une file ($\rho < 1$) au cas où un temps de séjour maximum est utilisé pour détruire les paquets,

- nous donnons les conditions d'ergodicité de quelques modèles qui peuvent être utilisés pour étudier les performances d'un réseau à commutation de paquets.

Abstract :

Ergodicity conditions are obtained in two cases :

- firstly when prevention is used to avoid congestion (so that the request may be satisfied by the available resources),

- secondly when we introduce the time-out or maximum sojourn time, as a method to cure the congestion when it appears.

We consider a packet-switching network as a tandem store and forward links. Our main results are the following :

- we give a numerical method to obtain the ergodicity condition of a tandem queueing system with general service times and limited capacity stations,

- we extend the classical ($\rho < 1$) ergodicity condition when time-outs are used to destroy packets,

- we give ergodicity conditions of some systems with a «time-out policy», which are used as models to study the behaviour of a packet-switching network.
ERGODICITY CONDITIONS AND CONGESTION CONTROL IN

COMPUTER NETWORKS

Guy Pujolle

IRIA/LABORIA
78150 LE CHESNAY
FRANCE

Ergodicity conditions are obtained in two cases:

- firstly when prevention is used to avoid congestion (so that the request may be satisfied by the available resources),

- secondly when we introduce the time-out or maximum sojourn time, as a method to cure the congestion when it appears.

We consider a packet-switching network as a tandem store and forward links. Our main results are the following :

- we give a numerical method to obtain the ergodicity condition of a tandem queueing system with general service times and limited capacity stations,

- we extend the classical ($\rho < 1$) ergodicity condition when time-outs are used to destroy packets,

- we give ergodicity conditions of some systems with a "time-out policy", which are used as models to study the behaviour of a packet-switching network.

For some time, congestion control in computer networks and more precisely in the communication sub-network, has been designated as an important problem. Congestion is a phenomenon inherent to networks which leads to a degradation of system performance. Congestion occurs from a situation in which resources, insufficient in relation to the request, are less and less effectively used.

In this paper, saturation conditions are obtained in two cases :

- firstly when prevention is used to avoid congestion (so that the request may be satisfied by the available resources),

- secondly when we introduce the time-out or maximum sojourn time, as a method to cure the congestion when it appears.

We have divided our study into two main parts. In the first part, we give a method to find the maximal traffic rate of store-and-forward tandem links, with general retransmission times, and with finite capacity nodes. In the second, we study ergodicity condition of an identical system, when we introduce a time-out assigned to each customer.

<footnote>* This paper is presented at the 2nd International Workshop on Modelling and Performance evaluation of Computer Systems, Stresa, Italy, october 4, 1976.</footnote>
PUJOLLE GUY

Diverse tools are used for these studies : queueing theory, Markov chains and approximations by diffusion processes.

The results we obtain are the following : in the first part, by a numerical method, we compute the ergodicity condition of a tandem system of general queues. In the second part, we extend the classical ergodicity condition of a queue ($\rho < 1$) when customers are provided with a time-out. Then we study equilibrium conditions of some systems with time-out policy, which are used as models to study the behavior of packet-switching networks.

# FIRST PART

## ERGODICITY CONDITIONS OF A TANDEM QUEUEING SYSTEM

### I. INTRODUCTION

The purpose of this part is to evaluate with mathematical methods, the performances of a computer network. The study is made on a particular path inside network. This path can be represented by a tandem queueing system with finite capacity stations (figure 1). In preceding papers [1, 2] we studied the response time and maximal traffic rate of such a tandem queueing system, when service times are exponentially distributed. In this paper, we study the maximal traffic rate, the response time and the utilization rate of stations, in the case when service times have arbitrary distributions. For this study, we shall use especially approximations, obtained by diffusion processes [3, 4, 5, 6]. $G/G/1/N$ station (limited capacity queues with service and interarrival times which follow a general law) is studied by an equivalence with a closed two-station system [7 and 8]. The accuracy of the values obtained for the response time and the utilization rate is demonstrated in [6, 9, 13].

We shall determine three possible kinds of packet retransmission, when a packet cannot enter the next station. For each possibility, we develop a method based on equivalences to obtain the maximal traffic rate, the response time and the utilization rate for intermediate stations. We tabulate, for a number of stations between 2 and 10, the maximal traffic rate as a function of the capacity and the service law (services have a mean duration equal to one unit of time).

<figure><img src="image_2.png" /><figcaption>Figure 1</figcaption></figure>
## II. DESCRIPTION OF THE MODEL

A particular connection inside a packet switched network [10, 11] can be represented by a tandem queueing system (figure 1). We shall assume that there are no interferences with the other links of the network.

We shall assume that the packet lengths are distributed according to a general law. Considering a constant duration of time to transmit one byte, it is identical to take a retransmission time at station i, distributed by a law with $\mu_i^{-1}$ mean, $V_i$ variance, $Ks_i$ squared coefficient of variation.

We shall also assume that the queues have limited capacities, except for the first one. Node i cannot contain more than $M_i$ packets. The behaviour of the network will be studied under three assumptions of retransmissions of the packets when a transmission fails for lack of place.

1. The packet is retransmitted from the preceding station, and that till success.

2. The packet is retransmitted from the first station.

3. The packet is lost (no retransmission in the network).

Other cases can be included in those mentioned above; for example the packet is retransmitted to the preceding station after an overhead.

Blocking of a node, with retransmission as soon as a place becomes free in the next station, will not be studied. However the performances of this type of networks will be close to behaviour of type 1 networks; moreover it is exactly the same with exponential service times. Case 2 and 3 will be analyzed together.

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

## III. MAXIMAL TRAFFIC RATE, RESPONSE TIME AND UTILIZATION RATE WITH RETRANSMISSION OF TYPE 1

We give on figure 2, the model that we want to study (we have only depicted station n and n+1). To analyse the behaviour of station n, we are going to replace it by an equivalent queue in which there is no feedback. We shall note the mean of a distribution $f(x)$ by $E[f(x)]$, the variance by $Var[f(x)]$ and the squared
coefficient of variation of interarrival (service) times Ka, (Ks). Let $\lambda_n, \mu_n, p_n$ be interarrivalrate, service rate, rejection probability at station n.

Let $g(x)$ be the distribution of service time in station n. We shall
take $E[g(x)] = \frac{1}{\mu_n}$ and $Var[g(x)] = Var_n$. The service time distribution of the equi-
valent station is :

$$
h(x) = (1 - p_{n+1}) \sum_{k=1}^{\infty} p_{n+1}^{k-1} g^{*k}(x), \quad (1)
$$

where * is convolution product.

By Laplace-Stieltjes transform we obtain :

$$
E\{h(x)\} = E\{g(x)\}/(1 - p_{n+1}) = \frac{1}{\mu_n (1 - p_{n+1})} \quad (2)
$$

$$
K_s\{h(x)\} = p_{n+1} + K_s\{g(x)\} \cdot (1 - p_{n+1}) = p_{n+1} + \mu_n^2 \cdot \text{Var}_n \cdot (1 - p_{n+1}) \quad (3)
$$

We shall set $v_n = \mu_n \cdot (1 - p_{n+1})$ and $Ks'_n = p_{n+1} + Ka_n \cdot (1 - p_{n+1})$. To study the behavior of station n, it is necessary to know the interarrival rate $\lambda_n$ and the squared coefficient of variation of interarrival times in this station.

The packets arrival rate $\lambda_n$ at the station n is equal to $\lambda / (1 - p_n)$.
The number of packets flowing from station n-1 to n is the sum of external arri-
vals and of the number of packets retransmitted from station n-1.

In the following analysis we shall use diffusion approximations:
[3 to 6].

We have two possibilities to approximate the squared coefficient of va-
riation of interarrival times : methods of Reiser and Kobayashi [12] and Gelenbe
and Pujolle [13]. We take the first one because in tandem queues the formulation
is very easy : Ka_n = Ks_{n-1}. The approximation will be better as we approach the
saturation condition.

The probability $p_n$ that a packet is refused at the entrance of station
n is equal to probability that there are $M_n$ packets in the station. This value
comes from Gelenbe [5] ; thus we have the system :

$$
\lambda_n = \lambda / (1 - p_n) \tag{4}
$$

$$
p_n = P(M_n) = \frac{\rho_n (1 - \rho_n)}{e^{-\gamma_n(M_n-1)} - \rho_n^2} \quad (4')
$$
where $\rho_n = \frac{\lambda_n}{v_n}$, $\gamma_n = \frac{2b_n}{\alpha_n}$ with $b_n = \lambda_n K_n + v_n K_s$.

It is a linear system of equations with two unknowns in which the probability $p_{n+1}$ interferes ($K_s = \text{Var}_n \mu_n^2 (1 - p_{n+1}) + p_{n+1}$). We must study the system beginning with the last station, because $p_{K+1} = 0$, thus we obtain step by step, $\lambda_n$ and $p_n$, from $n = K$ to $n = 2$. Utilization rates are given by $1 - P_n(0)$ where $P_n(0)$ is determined in [5] :

$$P_n(0) = \frac{1 - \rho_n}{1 - \rho_n^2 e^{\gamma_n(M_n - 1)}} \quad (5)$$

The mean number of customers in station n is computed by the technique described by Badel [6, 9], that we recall briefly. If f is the probability distribution of the number of customers in station n, given by [5] :

$$f(x) = \begin{cases} \frac{\lambda(1-\rho)}{b} [e^{\gamma x} - 1] & 0 \le x \le 1 \\ \frac{\lambda(1-\rho)}{b} [1 - e^{-\gamma}] e^{\gamma x} & x > 1 \end{cases} \quad (6)$$

we take

$$P_n(j) = \int_{b}^{b_j} f(x) dx \quad \text{for } j = 1, \dots, M_n \quad (7)$$

with $b_j$ determined by the following equation :

$$\int_{0}^{b_1} xf(x) dx = \int_{0}^{b_1} f(x) dx, \quad b_0=0, \quad b_{M_n} = M_n \quad (8)$$

and the $b_i$, $2 \le i \le M_n - 1$, are determined by dividing the interval $]b_1, M_n[$ in $M_n - 2$ identical intervals :

$$b_i - b_{i-1} = \frac{M_n - b_1}{M_n - 2} \quad (9)$$

The mean number of customers in station n is now :

$$E_n = \sum_{i=1}^{M_n} i P_n(i), \quad n = 2, \dots, K. \quad (10)$$

Station 1 is a particular case, since it is of infinite capacity. A good approximation of the mean number of customers in this station is given by Gelenbe [14] :
$$E_1 = \rho_1 \left[ 1 + \frac{\rho_1 K a_1 + K s_1}{2(1 - \rho_1)} \right] \quad (11)$$

$$\text{The total mean number is } E = \sum_{k=1}^{K} E_{k}.$$

Up to now, we assumed that $\lambda < \nu_i$ for all $i$. The maximum traffic rate will obtained as soon as there exists a $j$ such that $\lambda = \nu_j$ and if $i \neq j$ $\lambda \le \nu_i$, or when $E$ tends towards infinity, or when there exists a station in which the utilization rate is 1. We used the first method to determine the maximal traffic rate. An equivalent formulation is : $\lambda=\mu_j(1 - p_{j+1})$ or $\lambda_{j+1} = \mu_j$. We find the maximal traffic rate by the following algorithm. As the $\lambda_j$, $j = 2, \dots, K$, are increasing with $\lambda$, compute $\lambda_j$ from $\lambda$, and by increasing $\lambda$ obtain one $j$ such that $\lambda_{j+1} = \mu_j$ and if $i \neq j$, $\lambda_{i+1} \le \mu_i$.

<figure><img src="image_4.png" /><figcaption>Figure 3</figcaption></figure>

## EXAMPLE

We are going to compute maximal traffic rate in the particular case of two stations ; the first one has an infinite capacity, the second one has a limited capacity M. We shall assume that the two stations have the same general distribution, with mean $1/\mu$ and squared coefficient of variation Ks. We have represented this model on figure 3.

Maximal traffic rate is obtained for $\lambda_2 = \mu$. Thus we have the following system :

$$\left\{ \begin{array}{l} \lambda_2 = \lambda_{\max} / (1 - p_2) \\[1em] p_2 = \lim_{\lambda_2 \to \mu} \frac{\rho_2 (1 - \rho_2)}{e^{-\gamma_2 (M-1)} - \rho_2^2} \quad \text{with } \rho_2 = \frac{\lambda_2}{\mu} \to 1 \end{array} \right. \quad (12)$$

we find :

$$p_2 = \frac{1}{2 \left[ 1 + \frac{M-1}{K a_2 + K s_2} \right]} \quad (13)$$
As we have chosen $Ka_2 = Ks_1$, we have the system :

$$ egin{cases} 
\lambda_{\max} = (1 - p_2)\mu \\ 
p_2 = \frac{1}{2\left[1 + \frac{M-1}{Ks_1 + Ks_2}\right]} 
\end{cases} 
\quad (14) $$

Assume that interarrival times have an Erlang n distribution, with rate 1, thus $Ks = \frac{1}{n}$, we have $(\rho_{\max} = \lambda_{\max}/\mu)$

$$ egin{cases} 
p_2 = \frac{1}{nM - n + 2}, \\ 
\rho_{\max} = \frac{n(M-1) + 1}{n(M-1) + 2}. 
\end{cases} 
\quad (15) $$

■ If $n = 1$, namely if service times are exponentially distributed we have :

$$ egin{cases} 
p_2 = \frac{1}{M+1} \\ 
\rho_{\max} = \frac{M}{M+1} 
\end{cases} 
\quad (16) $$

this is a known result (Saaty [15]).

■ If $n = +\infty$, it is a constant service. $p_2 = 0$ since we have supposed $M > 1$. Thus $\rho_{\max} = 1$; it is an obvious result.

Now let us assume that service times are hyperexponential with squared coefficient of variation $n$ : $Ks = n$. Thus

$$ egin{cases} 
p_2 = \frac{n + M - 1}{2n + M - 1}, \\ 
\rho_{\max} = \frac{n + M - 1}{2n + M - 1}. 
\end{cases} 
\quad (17) $$

For $n=1$ we have the exponential case and for $n = +\infty$, we obtain the most unfavourable case :

$$ p_2 = \frac{1}{2} \quad \text{and} \quad \rho_{\max} = \frac{1}{2}. 
\quad (18) $$

## RESULTS

Let the system be composed of identical stations, with the same capacity
M and with the same service distribution ($\mu = 1$ and $Ks$), except for the first queue which has an infinite capacity. We begin to compute the maximal traffic rate for 2, 3, 4, 5, 10 queues in series, with different distributions of service times and different capacities M, (tables 1, 2, 3, 4, 5). Next, we compute response time and utilization rate of the first server of the system, for 3 queues in tandem, with the following service times : Erlang 2, 10 and hyperexponential with $Ks = 2, 10$, (tables 6, 7).

<figure><img src="image_5.png" /><figcaption>Figure 4</figcaption></figure>

## IV. MAXIMAL TRAFFIC RATE, RESPONSE TIME AND UTILIZATION RATE WITH RETRANSMISSION OF TYPE 2 AND 3

We want to study maximal traffic rate of a type 2 retransmission policy : when a packet is rejected out of the network for lack of place, it is retransmitted from the first station, (figure 4). Let us make the following assumption : interarrival times in the system are exponentially distributed. Moreover, we shall assume that in adding rejected customers to these external arrivals, the interarrival time distribution is still exponential.

When a packet is rejected, it is retransmitted from the first station, with three possible policies :

a - The return to the first station is instantaneous,

b - The return requires a time $D_i$ from the i-th station,

c - Let $a_j$ be the entrance time of packet j in the network. If packet j is rejected, it is retransmitted at the date $a_j + D$. This policy corresponds with the fact that if the first station has not received an acknowledgement for a packet, this packet is automatically retransmitted after a time D. We must take D large, to be sure that the date of rejection $a_j + T_j$ is inferior to $a_j + D$.

These three policies have exactly the same maximal traffic rate with our Poisson arrival assumption. Thus, firstly we are going to compute this rate. It is obtained if $\lambda_1 = \mu_1$ : the queues 2, 3, ..., K are stable since there is loss of packets. The ergodicity condition is obtained by the equality $\lambda_1 = \lambda + \sum_{j=2}^{K} \lambda_j p_j = \mu_1$. This
remark allows us to study only the system surrounded by the dotted line on Figure 4, and depicted again on figure 5. It is a tandem system with loss : when a packet cannot find a place in the following node it is rejected, never to return. We find a network with a type 3 behavior.

We may not define a maximal traffic rate for a type 3 network because there is loss of packets. In the type 2 case, maximal traffic rate will be given by the output rate when $\lambda_t = \mu_t$. As performances of type 2 are inferred from those of type 3, we shall begin to study this last sort of system.

<figure><img src="image_6.png" /><figcaption>Figure 5</figcaption></figure>

## STUDY OF TYPE 3 NETWORK (FIGURE 5)

We assume, as before, that the output process of a queue has the same squared coefficient of variation as its service time : $Ka_n = Ks_{n-1}$. The behavior of station i, is described by the following equations : $p_i = 0$,

$$ egin{cases} 
\lambda_i = \lambda_{i-1} (1 - p_{i-1}) \\ 
p_i = \frac{\rho_i (1 - \rho_i)}{e^{-\gamma_i (M_i - 1)} - \rho_i^2} \quad i = 2, \dots, K 
\end{cases} 
\quad (19) $$

From the first station, we may compute step by step $\lambda_i$ and $p_i$, for $i = 1, \dots, K$. We have $P_n(0)$, $P(M)$ and $E_n$, $n = 2, \dots, K$ given by the formula (4, 5, 7, 10). If the first queue has an infinite capacity, there exists an equilibrium state if $\lambda_1 < \mu_1$. We take ([14]):

$$ E_1 = \rho_1 \left[ 1 + \frac{\rho_1 K a_1 + K s_1}{2(1-\rho_1)} \right] \quad (20) $$

where $Ka_1$ ($Ks_1$) is the squared coefficient of variation of interarrival times (service times) at station 1.

The mean number and response time in the whole system is :

$$ E = \sum_{i=1}^{K} E_i \quad \text{and} \quad W = \sum_{i=1}^{K} \left( \frac{E_i}{\lambda_i (1-p_i)} \right). $$
# STUDY OF TYPE 2 NETWORK (FIGURE 4)

## * Response time

Response time of station n is the same as the preceding one.

Let $T_n$ be the response time of the n first stations. $W_n = E_n / \lambda_n (1-p_n)$.

### - Case a :

$$ T_n = \frac{T_{n-1} + W_n}{1 - p_{n-1}} \quad \text{for } 2 \le n \le K-1 \quad (21) $$

$$ \text{with} \quad T_1 = W_1 / (1 - p_2). $$

$$ \text{The total response time is : } T = T_{K-1} + W_K. $$

### - Case b

$$ T_n = (1 - p_{n+1}) \sum_{j=1}^{\infty} \left[ j(T_{n-1} + W_n) + (j-1) D_n \right] p_{n+1}^{j-1} \quad (22) $$

If $D_n = D$ for all n, we have :

$$ T_n = (T_{n-1} + W_n) \frac{1 + Dp_{n+1}}{1 - p_{n+1}} \quad \text{for } 2 \le n \le K-1 \quad (23) $$

$$ \text{and} \quad T_1 = W_1 \frac{1 + Dp_2}{1 - p_2}. $$

$$ \text{Total response time is : } T = T_{K-1} + W_K. $$

### - Case c

$$ T_n = (1 - p_{n+1}) \sum_{j=1}^{\infty} \left[ (j-1) D + T_{n-1} + W_n \right] p_{n+1}^{j-1} \quad (24) $$

$$ \text{thus} \quad T_n = \frac{Dp_{n+1}}{1-p_{n+1}} + T_{n-1} + W_n \quad \text{for } 1 \le n \le K-1 \quad \text{and} \quad T_0 = 0. $$

$$ \text{Thus, } T = T_{K-1} + W_K. $$

## * Ergodicity condition

Maximal traffic rate with a type 2 policy, is identical in the three preceding cases. It is obtained when $\lambda_1 = \mu_1$. Thus, from station 1, we may compute step by step $\lambda_i$ and $p_i$ for $i=2,...,K$, like for the type 3 resolution. Maximal rate
ERGODICITY CONDITIONS AND CONGESTION CONTROL IN COMPUTER NETWORKS

is given by $\lambda_{max} = \lambda_K(1-p_K)$.

## NUMERICAL RESULTS

We give in the tables 8 to 12 the maximal traffic rate for 2 to 100 queues in series, all identical, except the first which has an infinite capacity. Capacities change from $M=1$ to $M=6$. Mean service time is 1. and squared coefficient of variation changes following the service laws : Erlang 10, 2 and hyperexponential 2, 10, 1000.

Till now, we have used an approximate mathematical method, to compute the ergodicity condition of a tandem queues system. The validity of the approximation may be verified only by theoretical results or by simulations.

## COMPARISON WITH THEORETICAL RESULTS

We have only a few number of theoretical results on our kind of models. The some results known come from tandem queues with exponentially distributed service times. Since the exponential negative law has no memory, the model with retransmission at the preceding station is equivalent to the following model : when a unit cannot enter the next queue, the service is stoped till a place becomes free in the following station. The first results on the ergodicity condition of these models have been given by Hunt [16]. The comparison with the values obtained by Pujolle-Potier [17] shows a maximum difference of 3 %. (See results of table 13).

## COMPARISON WITH SIMULATION RESULTS

It is always difficult to obtain ergodicity conditions by simulation. However, with the recent paper of Lavenberg [18], this problem becomes easy : consider a network in which there is one input queue of infinite capacity and all the other stations have limited capacities ; under the assumption that all service times are mutually independent and distribution functions have rational Laplace-Stieltjes transforms, the maximal traffic rate is identical to the rate of departure from the network when the input queue is never empty. In our network of tandem queues, the preceding assumptions are verified so we have an easy method to obtain the maximal traffic rate by simulation [19].

We give in the tables 14 and 15 comparisons between simulated (S) and approximated (A) results, on the maximal traffic rate of a tandem network of queues. We give only the center of the confidence interval for simplicity (all results are in the confidence intervals). In table 16 we give some comparisons of response times between approximated and simulated results.
## CONCLUSION

The performances of the type 1 policy is better than that of type 2 but the difference is not large on an important set. Moreover type 1 overhead is certainly more important than in type 2 case. On counterpart, when the number of stations becomes very large, the maximal traffic rate of type 2 policy becomes null whereas it remains strictly positive with type 1 policy.

## SECOND PART

### ON ERGODICITY CONDITIONS IN A NETWORK WITH TIME-OUT POLICIES

#### INTRODUCTION

We study in this part, ergodicity conditions of a station, then after, of a tandem queueing system with general service distributions. The analyses proceed from transportation conditions in packet-switching communication networks, but may be applied in other real systems, as well in computer science as in other areas.

When the n-th customer arrives in the system we associate a time $T_n$ with it. We have three main possibilities to control the network, with time-out :

1. rejection of the customer in the service if an arriving unit (for example the packet n) has a response time (waiting time plus service time) superior to $T_n$: "uniformly bounded actual waiting time".

2. rejection of the arriving customer n, if its response time is superior to $T_n$: "uniformly bounded virtual waiting time".

3. the customer n is rejected at the end of the time $T_n$, elapsed in the queue if it did not come out.

Cases 1 and 2 have been very deeply studied, and a good summary is given in Cohen [20]. Loris-Teghem [21] and Schweitzer and Gavish [22] have analysed case 2 in more detail. Here we are interested more specially by case 3.

Let $a_n$ be the arrival time in the system for the n-th customer and $T_n$ be its time-out. If the customer n has not left the network at time $a_n + T_n$, it is rejected. In packet switching communication network, this is one of the mechanisms used to avoid congestion of nodes. Packets which stay for too long time in the network are rejected and this allows the other packets to proceed more rapidly. However, we shall show that this management policy must be accompanied with some conditions for the throughput not to become zero.
Initially we are going to study the ergodicity condition of only one station with the infinite storage assumption, in which a time-out $T_n$ is assigned to each customer. After we shall examine a tandem queueing system. Then we shall study the ergodicity conditions of some systems with time-out policies.

## DEFINITION

- A queue is stable if the mean number of customers in the station is finite, when there is an infinite number of customers which are entered the system.

- A queue is unstable if the mean number of customers in the station is infinite.

- A queue is pseudo-stable if it is stable or unstable depending on the initial conditions.

To state precisely these definitions, we give the classical example where all the time-outs are infinite : $\forall n \in N, T_n = +\infty$. If $\lambda^{-1}$ and $\mu^{-1}$ are means of interarrival and service times, we have :

* If $\lambda < \mu$ the system is stable

* If $\lambda > \mu$ the system is unstable

* If $\lambda = \mu$ the system is pseudo-stable, because we know that it is stable if service times are deterministic and unstable in the other cases. (If at the initial time the number of customers is finite).

We shall take the usual assumption, that two customers cannot arrive at the same instant in the system and we shall suppose, to avoid some complications, that the initial state is the empty state.

## I. THE ERGODICITY CONDITION OF A QUEUE

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

Let the station be depicted in Figure 6.

Let P be the following probability :

$P = \text{probability } (T_n < +\infty, n \in N)$ and $Q = \text{probability } (T_n = +\infty, n \in N)$.
Thus $P + Q = 1$.

**THEOREM** : If $\lambda > 0$, $\mu$, the system is unstable.

**PROOF** : Let $i_n = a_{n+1} - a_n$, $s_n$ the service time of the n-th customer and $w_n$ the waiting time in the queue of the n-th customer. Response time of the n-th customer is $w_n + s_n$ and let $T_n$ be its time-out. We assume that $w_n$ and $s_n$ are virtual waiting time, namely if the customer n is not rejected by its time-out, then its service time and waiting time are $w_n$ and $s_n$. Thus we have :

$$ w_{n+1} = \begin{cases} \sup(w_n + s_n - i_n, 0) & \text{if } w_n + s_n \le T_n \\ \sup(T_n - i_n, 0) & \text{if } w_n \le T_n < w_n + s_n \\ \sup(w_n - i_n, 0) & \text{if } w_n > T_n \end{cases} \quad (25) $$

From the preceding relation we have :

$$ w_{n+1} \ge \sup(w_n + s_n - i_n, 0) \quad (26) $$

$$ \text{and thus } w_{n+1} \ge \sup(w_{n-1} + s_{n-1} + s_n - i_{n-1} - i_n, s_n - i_n, 0) \quad (27) $$

And step by step, with $w_1 = 0$, we obtain :

$$ \begin{aligned} w_{n+1} &\ge \sup(s_1 + s_2 + \dots + s_n - i_1 - i_2 - \dots - i_n, s_2 + s_3 + \dots + s_n - i_2 - i_3 - \dots - i_n, 0) \\ &\ge s_n - i_2 - \dots - i_n, s_3 + s_4 + \dots + s_n - i_3 - i_4 - \dots - i_n, 0 \end{aligned} \quad (28) $$

$$ \text{Thus } w_{n+1} \ge s_1 + s_2 + \dots + s_n - i_1 - i_2 - \dots - i_n. \quad (29) $$

When n is infinite, by the law of large numbers, there is a proportion of Q services which are accomplished (with probability Q the time-out is infinite) thus :

$$ \lim_{n \to +\infty} w_{n+1} \ge \lim_{n \to +\infty} n \left( \frac{Q}{\Phi \mu} - \frac{1}{\lambda} \right) \quad (30) $$

So $w_{n+1}$ becomes infinite if $\lambda > 0$, $\mu$.

**THEOREM** : If $\lambda < 0$, $\mu$, the system is stable.
We are going to take the following set of time-outs :

$$ T_n^k = \begin{cases} T_n & \text{if } T_n < k \\ +\infty & \text{if } T_n \ge k \end{cases} \qquad (31) $$

We index by $k$ the variables describing the new set of time-outs.

Evidently we have : $w_n^k \ge w_n$

We can write again the relations (25) in the new case :

$$ w_{n+1}^k = \begin{cases} \sup(w_n^k + s_n^k - i_n, 0) & \text{if } w_n^k + s_n^k \le T_n^k \\ \sup(w_n^k - i_n, 0) & \text{if } w_n^k \le T_n^k < w_n^k + s_n^k \\ \sup(w_n^k - i_n, 0) & \text{if } w_n^k > T_n^k \end{cases} \qquad (32) $$

For a $k$ sufficiently large but infinite, from the second equation of (32) we have : [because $T_n^k$ is limited by $w_n^k + s_n^k$]

$$ \sup(T_n^k - i_n, 0) \le \sup(k - i_n, 0) \quad \text{and} \qquad (33) $$

$$ w_{n+1}^k \le \sup(w_n^k + s_n^k - i_n, k - i_n, 0) \quad \text{from which obtain :} \qquad (34) $$

$$ w_{n+1}^k \le \sup(w_{n-1}^k + s_{n-1}^k + s_n^k - i_{n-1}^k - i_n^k, k + s_n^k - i_n - i_{n-1}^k, 0) \qquad (35) $$

$$ s_n^k - i_n, k - i_n, 0) $$

$$ w_{n+1}^k \le \sup(s_1^k + \dots + s_n^k - i_n^k - \dots - i_n^k, k + s_2^k + s_3^k + \dots + s_{n-1}^k - i_{n-1}^k, 0) \qquad (36) $$

$$ + s_n^k - i_1^k - i_2^k - \dots - i_n^k, k - i_n, 0) $$

$$ s_j^k + \dots + s_n^k - i_j^k - \dots - i_n^k < 0 \quad \text{when :} $$

- $n$ tends towards an infinite value

$$ - \lambda Q < Q \mu $$

- $k$ is finite

Thus, with our assumptions there exists a positive constant $C$ such that

$$ \lim_{n \to \infty} w_{n+1}^k < C. $$
As $w_{n+1}^k > w_{n+1}^l$, $w_{n+1}$ tends toward a finite limit. ■

When $\lambda = \lambda^* = \lambda^e$, we have a pseudo-stable equilibrium. As it is a particular case, we do not study it in detail.

## CONCLUSION

When all the time-outs are finite we obtain $Q = 0$. From preceding theorems, the queue is always stable in this case.

If all the time-outs have infinite values, we obtain $Q = \infty$, and we find again the classical ergodicity condition for a queue.

It is interesting to remark that the ergodicity condition depends only on $\lambda$, $\mu$ and $Q$. The value of the maximum finite sojourn time has no importance on the ergodicity condition as well as the distribution of interarrival and service times, Thus, for a same condition, it is possible to have different rejection rates.

We shall study this rejection rate in the following paragraph. Now we are going to study the ergodicity condition of a tandem queueing system.

## II. ERGODICITY CONDITION OF A TANDEM QUEUEING SYSTEM

<figure><img src="image_8.png" /><figcaption>Figure 7</figcaption></figure>

We want to study the ergodicity condition of the queueing system of Figure 7. For the packet $n$, let $T_n$ be its time-out, and $a_n$ its arrival instant. The customer $n$ is rejected if it is not out at $a_n + T_n$.

If there exists a stable state let $r_i$ be the rejection probability of a packet by time-out through the station $i$. Let $\lambda_i$ be the arrival rate at station $i$, ($\lambda_i$ is the arrival rate in the system), and $\mu_i$ be the service rate.

As in preceding paragraph, let $P_i$ and $Q_i$, the proportion of finite and infinite time-outs.

For station $i$, we have :

$$P_i = \frac{P_{i-1} - r_{i-1}}{P_{i-1} + Q_{i-1} - r_{i-1}} = \frac{P_{i-1} - r_{i-1}}{1 - r_{i-1}} \quad (37)$$
$$Q_i = \frac{Q_{i-1}}{P_{i-1} + Q_{i-1} - r_{i-1}} = \frac{Q_{i-1}}{1 - r_{i-1}} \quad (37)$$

and $\lambda_i = \lambda_1(1 - r_i)(1 - r_2) \dots (1 - r_{i-1})$.

From the preceding theorem, the ergodicity condition at station i is
$Q_i \lambda_i < \mu_i$ or $\frac{Q_i}{\rho_i} < 1$ with $\rho_i = \lambda_i / \mu_i$. We deduce the following theorem :

**THEOREM** : The ergodicity condition of K queues in tandem is :

$$\sup_{i=1,...,K} \left( \frac{Q_i}{\rho_i} \right) < 1.$$

The real difficulty is to compute the rejection probability at station i, $r_i$, $i=1,...,K$. We deal with this problem in the following paragraph.

### III. COMPUTATION OF THE REJECTION RATE IN AN M/M/1 QUEUE

Let $\lambda$ and $\mu$ be the interarrival and service rate of a M/M/1 queue, and let us assume that all the customers have the same time-out T. We take again the same notations as in the preceding paragraph.

As we suppose that two customers cannot arrive at the same instant, and the service discipline is first come, first served, each waiting time $w_n$, $n \in N$ is strictly inferior to T, (rejected customers are being served).

The customer n receive the service time $inf(s_n, T - w_n)$.

Let us call $W(x)$, the distribution function of $lim_{n \to \infty} w_n$. This function has been computed first by Barrer [23], then by Daley [24] in a more general case. Moreover Daley [24] remarks a duality between waiting time $w_n$ of customer n, and its life time in the system $v_n$ :

$$v_n = T - \inf(w_n + s_n, T) \quad (38)$$

If $V(x)$ is the repartition function of $lim_{n \to \infty} v_n$, then Daley gives the correspondance between $V(x)$ and $W(x)$ :

$$V(x) = 1 - \int_{0}^{T-x} W(T - x - y) \mu e^{-\mu y} dy. \quad (39)$$

What we search beeing exactly $V(0)$, we obtain after some computations :
$$V(0) = 1 - \frac{1 - e^{(\lambda - \mu)T}}{1 - \rho e^{(\lambda - \mu)T}} \quad \text{where } \rho = \lambda/\mu. \qquad (40)$$

We give in the table 17, some results for this rejection probability, for different values of interarrival rate and time-out.

## IV. ERGODICITY CONDITION OF A QUEUE WITH TIME-OUT POLICY AND WITH RETRANSMISSION OF REJECTED CUSTOMERS

<figure><img src="image_9.png" /><figcaption>Figure 8</figcaption></figure>

Let us take an M/M/1 queue with constant time-out T for all the customers, and assume that a rejected customer is reintroduced following the model of figure 8. We are going to assume that the distribution of the sum of external arrival and rejected customers is exponential. (As external arrival is exponential, we may assume that rejected customers wait for some time before they join again the queue, so that the interarrival times at the queue are exponentially distributed).

Ergodicity condition of the system is $\lambda/(1-r) \le \mu$.

$$\text{or : } \rho \frac{1 - \rho e^{(\lambda - \mu)T}}{1 - e^{(\lambda - \mu)T}} \le 1. \qquad (41)$$

## NUMERICAL RESULTS

Let $\mu^{-1} = 1$ be the mean service time. The maximal traffic rate must vary the relation (41) with the equality sign. We obtain the results of table 18 when the value of the time_out T takes different values.

## CONCLUSION

To have an idea of the behaviour of a computer network, we have studied the performances of a mathematical model: a tandem queueing system, with finite storage assumption in the nodes. Models with a "time-out policy" are very simple, but reveal some interesting phenomena: for example the loss probability by time-out in an M/M/1 queue is almost independent of the arrival rate.

What it may be interesting to do is to couple finite storage assumption and a "time-out policy", to have a more realistic model. When service times are deterministic a study of this sort is carried out in [25].
REFERENCES

1. PUJOLLE G., - "Files d'attente en série et application au taux de charge maximum d'un réseau d'ordinateurs" - *Revue d'Informatique de l'AFCET*, B-2, May 76

2. IRLAND M., PUJOLLE G. - "Models of tandem networks of queues motivated by packet switching" - to appear.

3. GAVER D.P. - "Diffusion approximations and models for certain congestion problems", J. Appl. Prob., 5, 607-623, 1968.

4. KOBAYASHI H. - Application of the diffusion approximation to queueing networks; part I", J.A.C.M., 21, 2, 316-328, 1974.

5. GELENBE E. - "On approximate computer system models", J.A.C.M., 22, 2, 261-269, 1975.

6. BADEL M., SHUM A.V.Y., - "Accuracy of an approximate computer system model".- IRIA Research Report 130, July 1975.

7. GORDON W.J., NEWELL G.F. - "Closed queueing systems with exponential servers" - Oper. Res., 15, 254-265, 1967.

8. KOBAYASHI H., SILVERMAN H.F. - "Some dispatching priority schemes and their effects on response time distribution" - IBM Research Report, RC-3584, Yorktown Heights, 1971.

9. BADEL M. - "Quelques problèmes liés à la simulation de modèles de systèmes informatiques" - Thèse de Docteur-Ingénieur, Université de Paris VI, May 1975.

10. KLEINROCK L. - "Communication Nets-stochastic message flow and delays" - McGraw-Hill, New York, 1964.

11. GRANCE J.L., POUZIN L. - "Cigale, la machine de commutation de paquets" - Congrès AFCET, Rennes, November 1973.

12. REISER M., KOBAYASHI H. - "Accuracy of the diffusion approximation for some queueing systems", IBM J. Res. Develop., 18, 2, 110-124, March 1974.

13. GELENBE E., PUJOLLE G. - "Probabilistic models of computer systems" - Proc. of ACM-SIGMETRICS/IFIP Symp. on Computer Performance, Cambridge, March 1976.

14. GELENBE E. - "A non-Markovian diffusion and its application to the approximation of queueing and computer system behavior" - Research Report 74-1, Université de Liège, 1974.

15. SAATY T.L. - Element of queueing theory, McGraw-Hill, 1961.

16. HUNT G.C. - "Sequential arrays of waiting lines" - Oper. Res. 4, 1956.

17. PUJOLLE G., POTIER D. - "Réseaux de files d'attente à capacité limitée avec des applications aux systèmes informatiques" - To appear.

18. LAVENBERG S.S. - "Stability and Maximum Departure Rate of Certain Open Queueing Networks having Finite Capacity Constraints" - IBM Research Report RJ 1625 San Jose, California, 1975.
19. CRANE M.A., IGLEHART D.I. - "Simulating Stable Stochastic System II ; Markov chains" - JACM 21, 114-123, 1974.

20. COHEN J.W. - "The single server queue, Norht-Holland Publishing Company, Amsterdam, 1969.

21. LORIS-TEGHEM J. - "On the waiting time distribution in a generalized queueing system with uniformly bounded sojourn times" - J. Appl. Prob., 9, 642-649, 1972.

22. SCHWEITZER P.J., GAVISH B. - "The M/M/1 queue with bounded virtual waiting time" - IBM Research Report RC-5561, Yorktown Heights, New York, 1975.

23. BARRER D.Y. - "Queueing with impatient customers and ordered service" - Oper. Res., 5, 650-656, 1957.

24. DALEY D.J. - "Single server queueing systems with uniformly limited queueing time" - Austral. Math. Soc., 4, 489-505, 1964.

25. LABETOULLE J. and PUJOLLE G. - "A study of queueing networks with deterministic services and applications to computer networks" - Proc. of ACM-SIGMETRICS/IFIP Symp. on computer Performance, Cambridge, March 1976.

M = capacity of the stations

<table><thead><tr><th>service</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=10</th><th>M=20</th><th>M=∞</th></tr></thead><tbody><tr><td>Constant</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>Erlang 10</td><td>0.916</td><td>0.955</td><td>0.969</td><td>0.976</td><td>0.990</td><td>0.995</td><td>1</td></tr><tr><td>Erlang 5</td><td>0.857</td><td>0.916</td><td>0.941</td><td>0.955</td><td>0.981</td><td>0.990</td><td>1</td></tr><tr><td>Erlang 2</td><td>0.75</td><td>0.833</td><td>0.875</td><td>0.9</td><td>0.955</td><td>0.976</td><td>1</td></tr><tr><td>Exponentiel</td><td>0.67</td><td>0.75</td><td>0.8</td><td>0.83</td><td>0.90</td><td>0.95</td><td>1</td></tr><tr><td>Hyperexp 2</td><td>0.6</td><td>0.667</td><td>0.714</td><td>0.75</td><td>0.846</td><td>0.913</td><td>1</td></tr><tr><td>Hyperexp 5</td><td>0.545</td><td>0.583</td><td>0.615</td><td>0.642</td><td>0.737</td><td>0.826</td><td>1</td></tr><tr><td>Hyperexp 10</td><td>0.523</td><td>0.545</td><td>0.565</td><td>0.583</td><td>0.655</td><td>0.743</td><td>1</td></tr><tr><td>Hyperexp ∞</td><td>0.5</td><td>0.5</td><td>0.5</td><td>0.5</td><td>0.5</td><td>0.5</td><td>1</td></tr></tbody></table>

Maximal traffic rate with 2 queues in series, with retransmission at the preceding station.

<caption>Table 1</caption>
<table><thead><tr><th>service</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=10</th><th>M=20</th><th>M=∞</th></tr></thead><tbody><tr><td>Constant</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>Erlang 10</td><td>0.88</td><td>0.94</td><td>0.97</td><td>0.97</td><td>0.99</td><td>0.99</td><td>1</td></tr><tr><td>Erlang 5</td><td>0.80</td><td>0.88</td><td>0.92</td><td>0.94</td><td>0.97</td><td>0.98</td><td>1</td></tr><tr><td>Erlang 2</td><td>0.67</td><td>0.78</td><td>0.83</td><td>0.87</td><td>0.93</td><td>0.96</td><td>1</td></tr><tr><td>Exponentiel</td><td>0.57</td><td>0.67</td><td>0.73</td><td>0.78</td><td>0.87</td><td>0.92</td><td>1</td></tr><tr><td>Hyperexp 2</td><td>0.5</td><td>0.58</td><td>0.64</td><td>0.68</td><td>0.80</td><td>0.86</td><td>1</td></tr><tr><td>Hyperexp 5</td><td>0.44</td><td>0.48</td><td>0.52</td><td>0.55</td><td>0.66</td><td>0.77</td><td>1</td></tr><tr><td>Hyperexp 10</td><td>0.41</td><td>0.44</td><td>0.46</td><td>0.48</td><td>0.57</td><td>0.67</td><td>1</td></tr></tbody></table>

Maximal traffic rate with 3 queues in series, with retransmission at the preceding station.

<caption>Table 2</caption>

M = capacity of the stations

<table><thead><tr><th>service</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=10</th><th>M=20</th><th>M=∞</th></tr></thead><tbody><tr><td>Constant</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>Erlang 10</td><td>0.85</td><td>0.92</td><td>0.96</td><td>0.97</td><td>0.99</td><td>0.99</td><td>1</td></tr><tr><td>Erlang 5</td><td>0.77</td><td>0.87</td><td>0.91</td><td>0.93</td><td>0.97</td><td>0.98</td><td>1</td></tr><tr><td>Erlang 2</td><td>0.63</td><td>0.75</td><td>0.81</td><td>0.85</td><td>0.93</td><td>0.95</td><td>1</td></tr><tr><td>Exponentiel</td><td>0.53</td><td>0.64</td><td>0.71</td><td>0.75</td><td>0.85</td><td>0.91</td><td>1</td></tr><tr><td>Hyperexp 2</td><td>0.46</td><td>0.54</td><td>0.60</td><td>0.65</td><td>0.78</td><td>0.84</td><td>1</td></tr><tr><td>Hyperexp 5</td><td>0.39</td><td>0.44</td><td>0.48</td><td>0.51</td><td>0.63</td><td>0.74</td><td>1</td></tr><tr><td>Hyperexp 10</td><td>0.37</td><td>0.39</td><td>0.42</td><td>0.44</td><td>0.53</td><td>0.63</td><td>1</td></tr></tbody></table>

Maximal traffic rate with 4 queues in series with retransmission at the preceding station.

<caption>Table 3</caption>
<table><thead><tr><th>service</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=10</th><th>M=20</th><th>M=∞</th></tr></thead><tbody><tr><td>Constant</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>Erlang 10</td><td>0.84</td><td>0.92</td><td>0.95</td><td>0.96</td><td>0.99</td><td>0.99</td><td>1</td></tr><tr><td>Erlang 5</td><td>0.75</td><td>0.85</td><td>0.90</td><td>0.93</td><td>0.97</td><td>0.98</td><td>1</td></tr><tr><td>Erlang 2</td><td>0.60</td><td>0.73</td><td>0.80</td><td>0.84</td><td>0.92</td><td>0.95</td><td>1</td></tr><tr><td>Exponentiel</td><td>0.51</td><td>0.62</td><td>0.69</td><td>0.74</td><td>0.85</td><td>0.90</td><td>1</td></tr><tr><td>Hyperexp 2</td><td>0.44</td><td>0.52</td><td>0.59</td><td>0.63</td><td>0.77</td><td>0.83</td><td>1</td></tr><tr><td>Hyperexp 5</td><td>0.37</td><td>0.42</td><td>0.46</td><td>0.49</td><td>0.61</td><td>0.72</td><td>1</td></tr><tr><td>Hyperexp 10</td><td>0.34</td><td>0.37</td><td>0.39</td><td>0.41</td><td>0.51</td><td>0.51</td><td>1</td></tr></tbody></table>

Maximal traffic rate with 5 queues in series, with retransmission at the preceding station.

<caption>Table 4</caption>

M = capacity of the stations

<table><thead><tr><th>service</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=10</th><th>M=20</th><th>M=∞</th></tr></thead><tbody><tr><td>Constant</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>Erlang 10</td><td>0.81</td><td>0.90</td><td>0.93</td><td>0.95</td><td>0.98</td><td>0.99</td><td>1</td></tr><tr><td>Erlang 5</td><td>0.71</td><td>0.83</td><td>0.88</td><td>0.91</td><td>0.96</td><td>0.98</td><td>1</td></tr><tr><td>Erlang 2</td><td>0.57</td><td>0.70</td><td>0.77</td><td>0.81</td><td>0.91</td><td>0.94</td><td>1</td></tr><tr><td>Exponentiel</td><td>0.47</td><td>0.58</td><td>0.66</td><td>0.71</td><td>0.83</td><td>0.89</td><td>1</td></tr><tr><td>Hyperexp 2</td><td>0.41</td><td>0.49</td><td>0.55</td><td>0.61</td><td>0.74</td><td>0.81</td><td>1</td></tr><tr><td>Hyperexp 5</td><td>0.34</td><td>0.38</td><td>0.43</td><td>0.46</td><td>0.59</td><td>0.70</td><td>1</td></tr><tr><td>Hyperexp 10</td><td>0.31</td><td>0.33</td><td>0.36</td><td>0.38</td><td>0.47</td><td>0.58</td><td>1</td></tr></tbody></table>

Maximal traffic rate with 10 queues in series, with retransmission at the preceding station.

<caption>Table 5</caption>
Response time of 3 station in series

<table><thead><tr><th>Arrival rate</th><th colspan="4">Number of buffers</th></tr><tr><th></th><th>3</th><th>4</th><th>5</th><th>10</th></tr></thead><tbody><tr><td>0.20</td><td>3.31</td><td>3.31</td><td>3.31</td><td>3.31</td></tr><tr><td>0.40</td><td>3.57</td><td>3.57</td><td>3.57</td><td>3.57</td></tr><tr><td>0.60</td><td>4.13</td><td>4.13</td><td>4.13</td><td>4.13</td></tr><tr><td>0.80</td><td>5.79</td><td>5.79</td><td>5.79</td><td>5.79</td></tr></tbody></table>

Erlang 10

<table><tbody><tr><td>0.20</td><td>3.89</td><td>3.90</td><td>3.90</td><td>3.90</td></tr><tr><td>0.40</td><td>4.33</td><td>4.36</td><td>4.38</td><td>4.38</td></tr><tr><td>0.60</td><td>5.00</td><td>5.24</td><td>5.41</td><td>5.52</td></tr><tr><td>0.80</td><td></td><td>15.06</td><td>12.33</td><td>15.06</td></tr></tbody></table>

Erlang 2

<table><tbody><tr><td>0.20</td><td>4.72</td><td>5.19</td><td>5.84</td><td>7.19</td></tr><tr><td>0.40</td><td>5.21</td><td>5.77</td><td>6.85</td><td>10.79</td></tr><tr><td>0.60</td><td></td><td>17.38</td><td>12.22</td><td>21.53</td></tr><tr><td>0.80</td><td></td><td></td><td></td><td></td></tr></tbody></table>

Hyperexponential 2

<table><tbody><tr><td>0.20</td><td>10.84</td><td>11.81</td><td>13.50</td><td>32.65</td></tr><tr><td>0.40</td><td>31.54</td><td>23.48</td><td>21.90</td><td>39.72</td></tr><tr><td>0.60</td><td></td><td></td><td></td><td></td></tr><tr><td>0.80</td><td></td><td></td><td></td><td></td></tr></tbody></table>

Hyperexponential 10

Table 6
Utilization rate of the first station with 3 stations in series

Arrival rate

Number of buffers

<table><thead><tr><th></th><th>3</th><th>4</th><th>5</th><th>10</th></tr></thead><tbody><tr><th>0.20</th><td>0.20</td><td>0.20</td><td>0.20</td><td>0.20</td></tr><tr><th>0.40</th><td>0.39</td><td>0.40</td><td>0.40</td><td>0.40</td></tr><tr><th>0.60</th><td>0.54</td><td>0.56</td><td>0.58</td><td>0.59</td></tr><tr><th>0.80</th><td>0.66</td><td>0.70</td><td>0.72</td><td>0.78</td></tr></tbody></table>

Erlang 10

<table><thead><tr><th></th><th>3</th><th>4</th><th>5</th><th>10</th></tr></thead><tbody><tr><th>0.20</th><td>0.20</td><td>0.20</td><td>0.20</td><td>0.20</td></tr><tr><th>0.40</th><td>0.39</td><td>0.40</td><td>0.40</td><td>0.40</td></tr><tr><th>0.60</th><td>0.56</td><td>0.56</td><td>0.58</td><td>0.60</td></tr><tr><th>0.80</th><td></td><td>0.76</td><td>0.76</td><td>0.78</td></tr></tbody></table>

Erlang 2

<table><thead><tr><th></th><th>3</th><th>4</th><th>5</th><th>10</th></tr></thead><tbody><tr><th>0.20</th><td>0.21</td><td>0.20</td><td>0.20</td><td>0.20</td></tr><tr><th>0.40</th><td>0.65</td><td>0.43</td><td>0.42</td><td>0.42</td></tr><tr><th>0.60</th><td></td><td>0.73</td><td>0.69</td><td>0.62</td></tr><tr><th>0.80</th><td></td><td></td><td></td><td></td></tr></tbody></table>

Hyperexponential 2

<table><thead><tr><th></th><th>3</th><th>4</th><th>5</th><th>10</th></tr></thead><tbody><tr><th>0.20</th><td>0.24</td><td>0.23</td><td>0.23</td><td>0.21</td></tr><tr><th>0.40</th><td>0.65</td><td>0.62</td><td>0.59</td><td>0.48</td></tr><tr><th>0.60</th><td></td><td></td><td></td><td></td></tr><tr><th>0.80</th><td></td><td></td><td></td><td></td></tr></tbody></table>

Hyperexponential 10

Table 7
<table><thead><tr><th></th><th>M=1</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=6</th></tr></thead><tbody><tr><td>2</td><td>.50</td><td>.74</td><td>.82</td><td>.87</td><td>.89</td><td>.91</td></tr><tr><td>3</td><td>.33</td><td>.73</td><td>.82</td><td>.86</td><td>.89</td><td>.91</td></tr><tr><td>4</td><td>.25</td><td>.72</td><td>.82</td><td>.86</td><td>.89</td><td>.91</td></tr><tr><td>5</td><td>.20</td><td>.72</td><td>.81</td><td>.86</td><td>.89</td><td>.91</td></tr><tr><td>10</td><td>.10</td><td>.69</td><td>.80</td><td>.86</td><td>.89</td><td>.90</td></tr><tr><td>20</td><td>.05</td><td>.66</td><td>.79</td><td>.85</td><td>.88</td><td>.90</td></tr><tr><td>50</td><td>.02</td><td>.61</td><td>.76</td><td>.83</td><td>.87</td><td>.89</td></tr><tr><td>100</td><td>.01</td><td>.57</td><td>.74</td><td>.81</td><td>.85</td><td>.88</td></tr></tbody></table>

Maximal traffic rate with an Erlang 10 service law, and with retransmission at the first station.

<table><caption>Table 8</caption><thead><tr><th></th><th>M=1</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=6</th></tr></thead><tbody><tr><td>2</td><td>.50</td><td>.70</td><td>.78</td><td>.83</td><td>.86</td><td>.88</td></tr><tr><td>3</td><td>.33</td><td>.60</td><td>.72</td><td>.78</td><td>.82</td><td>.85</td></tr><tr><td>4</td><td>.25</td><td>.54</td><td>.67</td><td>.75</td><td>.79</td><td>.82</td></tr><tr><td>5</td><td>.20</td><td>.50</td><td>.64</td><td>.72</td><td>.77</td><td>.80</td></tr><tr><td>10</td><td>.10</td><td>.37</td><td>.54</td><td>.63</td><td>.70</td><td>.74</td></tr><tr><td>20</td><td>.05</td><td>.28</td><td>.45</td><td>.56</td><td>.63</td><td>.69</td></tr><tr><td>50</td><td>.02</td><td>.18</td><td>.35</td><td>.47</td><td>.56</td><td>.62</td></tr><tr><td>100</td><td>.01</td><td>.13</td><td>.29</td><td>.42</td><td>.51</td><td>.57</td></tr></tbody></table>

Maximal traffic rate with an Erlang 2 station law, and with retransmission at the first station.

<caption>Table 9</caption>
<table><thead><tr><th></th><th>M=1</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=6</th></tr></thead><tbody><tr><th>2</th><td>.50</td><td>.62</td><td>.70</td><td>.75</td><td>.79</td><td>.81</td></tr><tr><th>3</th><td>.33</td><td>.45</td><td>.54</td><td>.60</td><td>.65</td><td>.69</td></tr><tr><th>4</th><td>.25</td><td>.36</td><td>.45</td><td>.52</td><td>.57</td><td>.61</td></tr><tr><th>5</th><td>.20</td><td>.30</td><td>.39</td><td>.46</td><td>.52</td><td>.56</td></tr><tr><th>10</th><td>.10</td><td>.18</td><td>.25</td><td>.32</td><td>.38</td><td>.43</td></tr><tr><th>20</th><td>.05</td><td>.10</td><td>.16</td><td>.22</td><td>.28</td><td>.33</td></tr><tr><th>50</th><td>.02</td><td>.04</td><td>.08</td><td>.13</td><td>.18</td><td>.23</td></tr><tr><th>100</th><td>.01</td><td>.02</td><td>.05</td><td>.08</td><td>.12</td><td>.17</td></tr></tbody></table>

Maximal traffic rate with an Erlang 2 service law, and with retransmission at the first station.

<table><caption>Table 10</caption><thead><tr><th></th><th>M=1</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=6</th></tr></thead><tbody><tr><th>2</th><td>.50</td><td>.54</td><td>.58</td><td>.64</td><td>.63</td><td>.66</td></tr><tr><th>3</th><td>.33</td><td>.37</td><td>.40</td><td>.42</td><td>.45</td><td>.47</td></tr><tr><th>4</th><td>.25</td><td>.27</td><td>.30</td><td>.33</td><td>.35</td><td>.37</td></tr><tr><th>5</th><td>.20</td><td>.22</td><td>.25</td><td>.27</td><td>.29</td><td>.31</td></tr><tr><th>10</th><td>.10</td><td>.11</td><td>.13</td><td>.14</td><td>.16</td><td>.17</td></tr><tr><th>20</th><td>.05</td><td>.05</td><td>.06</td><td>.07</td><td>.08</td><td>.10</td></tr><tr><th>50</th><td>.02</td><td>.02</td><td>.02</td><td>.03</td><td>.03</td><td>.04</td></tr><tr><th>100</th><td>.01</td><td>.01</td><td>.01</td><td>.01</td><td>.02</td><td>.02</td></tr></tbody></table>

Maximal traffic rate with an hyperexponential 10 service law

<caption>Table 11</caption>
<table><thead><tr><th></th><th>M=1</th><th>M=2</th><th>M=3</th><th>M=4</th><th>M=5</th><th>M=6</th></tr></thead><tbody><tr><td>2</td><td>.50</td><td>.50</td><td>.50</td><td>.50</td><td>.50</td><td>.50</td></tr><tr><td>3</td><td>.33</td><td>.33</td><td>.33</td><td>.33</td><td>.33</td><td>.33</td></tr><tr><td>4</td><td>.24</td><td>.25</td><td>.25</td><td>.25</td><td>.25</td><td>.25</td></tr><tr><td>5</td><td>.20</td><td>.20</td><td>.20</td><td>.20</td><td>.20</td><td>.20</td></tr><tr><td>10</td><td>.10</td><td>.10</td><td>.10</td><td>.10</td><td>.10</td><td>.10</td></tr><tr><td>20</td><td>.05</td><td>.05</td><td>.05</td><td>.05</td><td>.05</td><td>.05</td></tr><tr><td>50</td><td>.02</td><td>.02</td><td>.02</td><td>.02</td><td>.02</td><td>.02</td></tr><tr><td>100</td><td>.01</td><td>.01</td><td>.01</td><td>.01</td><td>.01</td><td>.01</td></tr></tbody></table>

Maximal traffic rate with an hyperexponential 1000 service law, and with retransmission at the first station.

Table 12

Comparison on the ergodicity condition obtained by :

a - the approximate method

b - the theoretical approach of [18]

<table><thead><tr><th></th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>2<sup>-a</sup><sub>b</sub></td><td>0.67<br>0.67</td><td>0.75<br>0.75</td><td>0.80<br>0.80</td><td>0.83<br>0.83</td></tr><tr><td>3<sup>-a</sup><sub>b</sub></td><td>0.57<br>0.56</td><td>0.67<br>0.67</td><td>0.73<br>0.73</td><td>0.78<br>0.77</td></tr><tr><td>4<sup>-a</sup><sub>b</sub></td><td>0.53<br>0.51</td><td>0.64<br>0.63</td><td>0.71<br>0.70</td><td>0.75<br>0.74</td></tr><tr><td>5<sup>-a</sup><sub>b</sub></td><td>0.51<br>0.49</td><td>0.62<br>0.61</td><td></td><td></td></tr></tbody></table>

Table 13
Comparison between simulation (S) and approximation (A) on the maximal traffic rate of a tandem network of queues, with retransmission at the preceding station.

number of buffers

<table><thead><tr><th rowspan="2">number of stations</th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>2</td><td>0.92</td><td>0.91</td><td>0.96</td><td>0.95</td><td>0.97</td><td>0.96</td><td>0.98</td><td>0.98</td></tr><tr><td>3</td><td>0.88</td><td>0.88</td><td>0.94</td><td>0.93</td><td>0.97</td><td>0.96</td><td>0.97</td><td>0.96</td></tr><tr><td>5</td><td>0.84</td><td>0.84</td><td>0.92</td><td>0.92</td><td>0.95</td><td>0.94</td><td>0.96</td><td>0.95</td></tr></tbody></table>

Erlang 10

<table><thead><tr><th rowspan="2"></th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>2</td><td>0.75</td><td>0.76</td><td>0.83</td><td>0.85</td><td>0.87</td><td>0.86</td><td>0.9</td><td>0.9</td></tr><tr><td>3</td><td>0.67</td><td>0.69</td><td>0.78</td><td>0.77</td><td>0.83</td><td>0.82</td><td>0.87</td><td>0.88</td></tr><tr><td>5</td><td>0.60</td><td>0.63</td><td>0.73</td><td>0.73</td><td>0.80</td><td>0.81</td><td>0.84</td><td>0.83</td></tr></tbody></table>

Erlang 2

<table><thead><tr><th rowspan="2"></th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>2</td><td>0.6</td><td>0.59</td><td>0.67</td><td>0.65</td><td>0.71</td><td>0.70</td><td>0.75</td><td>0.73</td></tr><tr><td>3</td><td>0.5</td><td>0.5</td><td>0.58</td><td>0.56</td><td>0.64</td><td>0.63</td><td>0.68</td><td>0.65</td></tr><tr><td>5</td><td>0.44</td><td>0.40</td><td>0.52</td><td>0.49</td><td>0.59</td><td>0.57</td><td>0.63</td><td>0.61</td></tr></tbody></table>

Hyperexponential 2

<table><thead><tr><th rowspan="2"></th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>2</td><td>0.52</td><td>0.49</td><td>0.54</td><td>0.51</td><td>0.56</td><td>0.53</td><td>0.58</td><td>0.55</td></tr><tr><td>3</td><td>0.41</td><td>0.36</td><td>0.44</td><td>0.40</td><td>0.46</td><td>0.42</td><td>0.48</td><td>0.44</td></tr><tr><td>5</td><td>0.34</td><td>0.30</td><td>0.37</td><td>0.35</td><td>0.39</td><td>0.37</td><td>0.41</td><td>0.39</td></tr></tbody></table>

Hyperexponentiel 10

Table 14
Comparison between simulations (S) and approximations (A) on the maximal traffic rate of a tandem network of queues, with retransmission at the first station.

Number of buffers

<table><thead><tr><th rowspan="2">number of stations</th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>2</td><td>0.74</td><td>0.90</td><td>0.82</td><td>0.95</td><td>0.87</td><td>0.96</td><td>0.89</td><td>0.98</td></tr><tr><td>3</td><td>0.75</td><td>0.86</td><td>0.82</td><td>0.93</td><td>0.86</td><td>0.95</td><td>0.89</td><td>0.96</td></tr><tr><td>5</td><td>0.72</td><td>0.80</td><td>0.82</td><td>0.90</td><td>0.86</td><td>0.93</td><td>0.89</td><td>0.95</td></tr></tbody></table>

Erlang 10

<table><thead><tr><th rowspan="2"></th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>2</td><td>0.70</td><td>0.76</td><td>0.79</td><td>0.84</td><td>0.83</td><td>0.86</td><td>0.86</td><td>0.98</td></tr><tr><td>3</td><td>0.60</td><td>0.65</td><td>0.72</td><td>0.75</td><td>0.78</td><td>0.82</td><td>0.82</td><td>0.85</td></tr><tr><td>5</td><td>0.50</td><td>0.55</td><td>0.64</td><td>0.68</td><td>0.72</td><td>0.75</td><td>0.77</td><td>0.80</td></tr></tbody></table>

Erlang 2

<table><thead><tr><th rowspan="2"></th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>2</td><td>0.62</td><td>0.59</td><td>0.70</td><td>0.65</td><td>0.75</td><td>0.70</td><td>0.78</td><td>0.73</td></tr><tr><td>3</td><td>0.46</td><td>0.49</td><td>0.54</td><td>0.54</td><td>0.60</td><td>0.57</td><td>0.65</td><td>0.65</td></tr><tr><td>5</td><td>0.31</td><td>0.36</td><td>0.40</td><td>0.43</td><td>0.46</td><td>0.50</td><td>0.52</td><td>0.55</td></tr></tbody></table>

Hyperexponential 2

<table><thead><tr><th rowspan="2"></th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>2</td><td>0.54</td><td>0.42</td><td>0.57</td><td>0.51</td><td>0.63</td><td>0.53</td><td>0.63</td><td>0.56</td></tr><tr><td>3</td><td>0.37</td><td>0.30</td><td>0.40</td><td>0.34</td><td>0.42</td><td>0.36</td><td>0.45</td><td>0.44</td></tr><tr><td>5</td><td>0.23</td><td>0.20</td><td>0.25</td><td>0.23</td><td>0.27</td><td>0.27</td><td>0.29</td><td>0.30</td></tr></tbody></table>

Hyperexponential 10

Table 15
Comparison on response time, between simulations (S) and approximations (A)
of a tandem network of queues, with retransmission at the preceding station.
(simulations are with 90 % confidence intervals)

<table><caption>Maximum number in a station</caption><thead><tr><th rowspan="2">Arrival rate</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>0.2</td><td>3.89</td><td>3.35 - 3.75</td><td>3.90</td><td>3.34 - 3.70</td><td>3.90</td><td>3.35 - 3.80</td></tr><tr><td>0.4</td><td>4.33</td><td>4.20 - 4.49</td><td>4.36</td><td>4.27 - 4.56</td><td>4.38</td><td>4.08 - 4.48</td></tr><tr><td>0.6</td><td>5.00</td><td>5.53 - 6.76</td><td>5.24</td><td>5.80 - 7.01</td><td>5.41</td><td>5.35 - 6.13</td></tr><tr><td>0.8</td><td></td><td></td><td>15.06</td><td>14.14 - 17.53</td><td>12.33</td><td>11.02 - 15.56</td></tr></tbody></table>

<table><caption>Erlang 2</caption><caption>Maximum number in a station</caption><thead><tr><th rowspan="2">Arrival rate</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th></tr><tr><th>A</th><th>S</th><th>A</th><th>S</th><th>A</th><th>S</th></tr></thead><tbody><tr><td>0.2</td><td>4.72</td><td>4.12 - 4.63</td><td>5.19</td><td>4.25 - 4.70</td><td>5.84</td><td>4.11 - 4.61</td></tr><tr><td>0.4</td><td>5.21</td><td>6.10 - 8.15</td><td>5.77</td><td>5.75 - 7.15</td><td>6.85</td><td>6.85 - 7.16</td></tr><tr><td>0.6</td><td></td><td></td><td>17.38</td><td>22.82 - 28.33</td><td>12.22</td><td>12.25 - 15.31</td></tr></tbody></table>

<caption>Hyperexponential 2</caption>

<caption>Table 16</caption>

<table><caption>Time-out</caption><thead><tr><th></th><th>0.1</th><th>0.5</th><th>1</th><th>5</th></tr></thead><tbody><tr><td>0.05</td><td>0.905</td><td>0.609</td><td>0.375</td><td>0.008</td></tr><tr><td>0.5</td><td>0.907</td><td>0.639</td><td>0.435</td><td>0.043</td></tr><tr><td>0.9</td><td>0.909</td><td>0.661</td><td>0.487</td><td>0.134</td></tr></tbody></table>

Arrival rate Loss probability by time-out in an M/M/1 queue.
Mean service time equals 1

<caption>Table 17</caption>
<figure><img src="image_10.png" /><figcaption>Table 16</figcaption></figure>