# A study of queueing networks with deterministic service and applications to computer networks

Jacques Labetoulle, Guy Pujolle

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

## To cite this version:

Jacques Labetoulle, Guy Pujolle. A study of queueing networks with deterministic service and applications to computer networks. [Research Report] IRIA-RR-161, IRIA. 1976, pp.11. hal-04716350

HAL Id: hal-04716350

https://inria.hal.science/hal-04716350v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
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_3.png" /></figure>

A STUDY OF
QUEUEING NETWORKS
WITH DETERMINISTIC SERVICE
AND APPLICATIONS TO
COMPUTER NETWORKS

Jacques

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

J. Labetoulle, G. Pujolle

Rapport de Recherche N° 161

Mars 1976
# A STUDY OF QUEUEING NETWORKS WITH DETERMINISTIC SERVICE AND APPLICATIONS TO COMPUTER NETWORKS

J. Labetoulle, G. Pujolle

IRIA/LABORIA

## Résumé :

Nous examinons le comportement d'un réseau à commutation de paquets en le modélisant à l'aide d'un système de files d'attente à service constant ; ceci signifie encore que les longueurs des paquets sont supposées égales. Nous étudions un tel réseau en isolant un chemin particulier, que nous considérons comme une suite de files d'attente. Deux aspects particuliers seront examinés :

1. L'étude du temps de réponse.

2. L'étude du débit quand la notion de temps de séjour maximum (time-out) est introduite pour chaque paquet.

Les résultats que nous obtenons montrent que, en négligeant les interférences entre les chemins, le temps de réponse est indépendant de l'ordre des stations. La politique de contrôle, que nous examinons, prouve la nécessité d'avoir une capacité de mémorisation limitée à chaque nœud du réseau à commutation de paquets. Ces résultats confirment l'option prise intuitivement dans un réseau comme Cyclades.

## Abstract :

We consider packet-switching network as a queueing system with constant service times : that means that the lengths of the packets are equal. We study such a network by isolating a particular path, that we consider as a tandem system of queueing. Two aspects of the question will be examined :

1. The study of the response time of such a system.

2. The study of the throughput of such a system when introducing the notion of time-out for each packet.

The results we obtained show that when neglecting the interferences between paths the response time is independent of the order of the stations. The control policy we examined prove the necessity to have a limited memorisation capacity at each node of a packet-switching network. These results confirm the intuitive options taken in a network like Cyclades.
# A STUDY OF QUEUEING NETWORKS WITH DETERMINISTIC SERVICE AND APPLICATIONS TO COMPUTER NETWORKS

J. Labetoulle, G. Pujolle

IRIA/LABORIA

## INTRODUCTION

If we consider that in a packet-switching network, packets transit successively in a certain number of nodes in the network and that the transition time of one packet from one node to the next one is proportional to the size of the packet, this one being considered as fixed, we may understand the interest of studying tandem queues with constant service time. Two aspects of this question will be examined :

A - The study of the response time of such a system,

B - The study of the throughput of such a system when the notion of time-out for each packet is introduced.

For the first case two methods are possible : .
* the theoretical solution based on the analysis of Avi-Itzhak (1) and Friedman (3) and the results

of Izhak Rubin (16); ● the diffusion approximation.
In this case two approaches may be followed : the
one of Reiser-Kobayashi (15) and the one of Gelenbe
(7).

In the first part of this paper, we develop and
examine thoroughly the theoretical method in order
to obtain some useful results for the analysis of
packet-switching networks. Then we compare the
theoretical results with the solutions provided by
the diffusion approximations.

A - Tandem queues

I - Some theoretical properties of tandem queues

I.1 - Theoretical results

In this paragraph we consider the tandem queue sys-
tem of the figure two. The system consists of K queues; a customer (corresponding to a "packet" of data arriving to the first queue) goes through the system passing by the (i+1)-th queue after the i-th device for $1 \le i \le K-1$. All the stations, except the first one, have a limited capacity $M_i$ (corresponding to the finite storage), and the customers go through the stations in the order of their arrival (first come, first served). We assume that service time $\mu_i^{-1}$ of the i-th station ($1 \le i \le K$) has a constant value (deterministic service time). Because of limited queueing capacities, a packet which terminates its service at station i will remain in this queue if the (i+1)-station contains $M_{i+1}$ customers, and will proceed to queue i+1 when a packet will leave station i+1. We call this phenomenon the blocking situation.

**Remark 1** : These assumptions are in agreement with the behavior of a store-and-forward packet switching network in the case where all the packets have the same length. Constant service times, which may be different from a station to another, correspond to the time of retransmission of a packet on lines which have different characteristics (speed, etc.). The finite queueing capacity corresponds to the storage facilities at each node. The structure of tandem queues represents a peculiar lane in the network, reserved for the transmission between two points.

**Remark 2** : For the system under consideration it is equivalent to assume that service at station i is interrupted when a packet has completed its service at the i-th station and cannot enter the (i+1)-th station. In the remaining of the paper, this description of blocking case will be analyzed. In order to come back to the first definition of blocking it is sufficient to add one storage location to each station.

Let $t_i$ (resp $r_i$) be the arrival time at the first queue (resp. the departure time of the K-th station) of the i-th packet in the system described before and $r'_i$ the departure time of the i-th packet of a system with the same stations, but rearranged in arbitrary order, and with different amounts of capacity.

**Theorem 1** : (Avi-Itzhak (1)). The epochs of departure of the considered system are independent of the order and the capacity of stations. The same result is true when limiting the total capacity of a subset of stations.

**Proof** : Let be $\mu_{inf} = \inf_{i=1,...,K} (\mu_i)$ and $D = \sum_{i=1}^{K} \mu_i^{-1}$; D is

the total transmission time of a packet when the system is empty. We have $r_1 = r'_1 = D$. We assume now that $r_{n-1} = r'_{n-1}$ and we will prove that $r_n = r'_n$. The n-th customer has two possibilities : either it does not overtake any other packet so its time of departure is $t_n + D$, or it comes up with another packet, (namely, it is in the same queue or it is blocked by this other packet). This fact can occur only before or in the slower service queue, since after, the customers cannot meet because they are separated by an interval of time superior to service time of the slowest station. In this last case the packet goes out $\mu_{inf}^{-1}$ after the preceding one :

$$r_n = r_{n-1} + \mu_{inf}^{-1} \quad \text{so } r = \sup(t_n + D, r_{n-1} + \mu_{inf}^{-1}) \\ \text{and } r'_n = \sup(t_n + D, r'_{n-1} + \mu_{inf}^{-1})$$

and with our recurrent assumption $r_n = r'_n$. The theorem is proved since the above arguments do not take any account of the capacities of the stations.□

We may extend this last theorem, with less restrictive assumptions : assume that packets have different length, but that retransmission times follow the conditions : (if $i \ne j$)

$$\alpha_i \le \mu_i^{-1} \le \beta_i \quad \text{and} \quad \alpha_i, \beta_i \in [0, 1] \quad \text{with} \quad \alpha_i, \beta_i \in \mathbb{R}$$

**Theorem 2** : With the preceding assumptions, the mean response time does not depend on the order and the capacity of the stations.

**Proof** : (see in appendix)

**Theorem 3** : If packets have arbitrary length (denoted $l_i$, for packet i), and all retransmission stations have the same speed $\mu^{-1}$ then the date of departure of the system is independent of the order and the capacity of the stations.
**Proof** : Take again the definition of the theorem 1;
so $r_n=\sup(s_n+D, r_{n-1}+1/n\mu_i^{-1})$.

As $r_n$ does not depend neither on the order nor on
the capacity, the theorem 3 is demonstrated. [ ]

In the following, we shall use only theorem 1.

**Remark 1** : In this theorem we have assumed that the discipline of service was first come, first served. If we are interested only with mean response time, then the discipline may be arbitrary with the two following conditions :

1. The service must not be idle if the station is not empty and if there is no blocking situation.

2. The service discipline is not preemptive. Effec-
tively, since retransmission takes constant time,
the number of packets in the memory does not depend
on the discipline of service, and so does mean res-
ponse time. We may assume in the following, for
example, there are two kinds of packets : normal
packets and priority packets (in the Cigale net-
work, letters and telegrams). Priority packets
wait for the server to be free, to go on.

**Remark 2** : In a more general store-and-forward com-
munication networks, the fact that lines interfere
at nodes may bring some differences on response
times if capacities are limited or not. The princi-
pal disturbance comes from the fact that a node,
when there is blocking, can be fully occupied by
packets going all in the same direction and so
preventing the other lines to function at the speed
that they would if the capacity were infinite. If
we reserve some places in memory for every line
going out of a node, and choosing a policy which
preserves the order of passage in a congested node,
we come back for each itinerary on the tandem queue
case, with interruptions for packets being transfer-
red on the line but which do not go to the same
destination. So a finite capacity network (with
preceding conditions) has the same response time
as an infinite capacity network.

**Consequence** : In a store-and-forward communication network, it is not necessary to have an important capacity of memory. A few storage location and a rational policy are sufficient. This observation confirms that it is sufficient to have a mini-

computer to execute the switching of packets.

**Corollary 4** : Ergodicity condition (condition for the existence of stable state) of the system described in theorem 1 is :

$$
\lambda/\inf_{i=1,...,K} (\mu_i) < 1.
$$

**Proof** : Since the order of stations is of no impor-
tance, we can always assume that the longer service
time in first place. So the stable condition is the
same as G/D/I system. [ ]

I.2 - Total response time

We have shown, that in a packet-switching network
it is not necessary to consider that nodes have
limited capacity. So we may compute the distribu-
tion function of waiting time with or without the
finite storage assumption.

Let $\mu_{\inf}$ be $\inf_{i=1,...,K} (\mu_i)$.

**Corollary 5** : Let $W$ be the waiting time of a cus-
tomer arriving at a G/D/I queue with a service time
of $\mu_{\inf}^{-1}$. The distribution function of waiting time
in the considered system $v(\tau)$ is then :

$$
v(\tau) = \begin{cases} 0 & \text{if } \tau < \sum_{i=1}^{K} \mu_i^{-1} \\ \text{Prob } \{W < \tau - \sum_{i=1}^{K} \mu_i^{-1}\} & \text{i} \neq \inf \\ \end{cases}
$$

**Proof** : To obtain this result it is sufficient to
place first the slower service station. [ ]

I.3 - Mean response time of each station with the
infinite storage assumption

We are going to study the response time of each
station in the tandem queue system. Let us assume
infinite storage and denote $W_i$ the response time
at the i-th station (the mean time for a packet to
go through the i-th station). If the i-th station
has a service time inferior to one of the preceding
ones, we have immediately $W_i = 1/\mu_i$ since inter-
arrival times are larger than $1/\mu_i$. Thus, we have
to study a certain set of H stations with the as-
sumption $1/\mu_1 < 1/\mu_2 < 1/\mu_3 < ... < 1/\mu_H$.
If the distribution of interarrival times in the system has a probability function G(x), denote $V_i$ the response time of GI/D/1 queue with $1/\mu_i$ service time. The computation of $V_i$ is straightforward (Cohen (2), Prabhu (14)).

**Theorem 6** : The response time of station n, n > 1, is :

*Proof* : For two stations we have : (denoting W the total response time, and with theorem 1) :

$$ 
\left. 
\begin{aligned}
W &= V_2 + 1/\mu_1 \\
W &= V_1 + W_2
\end{aligned}
\right\} \Rightarrow W_2 = \frac{1}{\mu_1} + V_2 - V_1
$$

Assume that $W_i = 1/\mu_{i-1} + V_i - V_{i-1}$ for $i \le n-1$ we have for n stations :

$$W = V_n + \sum_{i=1}^{n-1} 1/\mu_i$$

$$W = \sum_{i=1}^{n-1} W_i + W_n = \sum_{j=1}^{n-2} \frac{1}{\mu_j} + V_{n-1} + W_n$$

with recurrent assumption and so

$$W_n = 1/\mu_{n-1} + V_n - V_{n-1} \quad \Box$$

In the particular case where the arrival process is Poisson, the solution is very simple. Let $\rho_i = \lambda/\mu_i$.

**Corollary 7** : The n-th station response time with Poisson arrival is :

*Proof* : A M/D/1 response time is $V = \frac{1}{\mu} (1 + \frac{1}{2} \frac{\rho}{1-\rho})$ which gives the result from theorem 6. $\square$

So we find again the results of Rubin (16) by an easier method.

We could give other results for different arrival processes (Erlang, hyperexponentiel, etc...) but GI/D/1 results being complicated, we prefer to give a general approximated result (but a good approximation). In effect diffusion processes give very

good results in the study of one queue and we have (see study of II-th part)

$$V = \frac{1}{\mu} \left[ 1 + \frac{\rho c_a + c_s}{2(1-\rho)} \right]$$

where $\rho = \lambda/\mu$, Ca is the squared coefficient of variation of interarrival times and Cs of departure times.

So a very good approximation of G/D/1 system is

$$V = \frac{1}{\mu} \left[ 1 + \frac{\rho c_a}{2(1-\rho)} \right]$$

**Corollary 8** : The response time of n-th station in the general tandem queue is :

## II - Approximate analysis

A second method to analyse a network of queues with constant service time is given by diffusion processes. Two approaches are possible. First the one of Gaver and Shedler (4) extended by Kobayashi (11) and which exploitable form is given by Reiser and Kobayashi (15), and Gelenbe's (6,7) one. Diffusion theory consists in replacing a discrete stochastic process corresponding to the number of customers in the queue by a continuous process. Denote $f$, the length distribution of queue, $\lambda$ and $\mu$ the arrival and service rate, Ca and Cs the squared coefficients of variation of interarrival and interdependency times, $\beta=\lambda-\mu$ and $\alpha=\lambda Ca + \mu Cs$.

**Proposition 9** : (Gaver and Shedler, Kobayashi). The continuous solution is $f(x) = \gamma e^{-\gamma x}$ with $\gamma = \frac{2\beta}{\alpha}$, the discrete probability of $f$ is $P(n) = (1-\hat{\rho})^{\hat{\beta}n-1}$ with $\hat{\rho} = e^{\gamma}$, $P(0) = 0$ and the corrected discrete probability $P(0) = 1-\rho$, $P(n) = \rho(1-\hat{\rho})^{\hat{\beta}n-1}$. (See for example Kobayashi (11)).

**Proposition 10** (Gelenbe) : The mass at the origin is $1-\rho$ and the continuous solution is
$$f(x) = \begin{cases} \frac{m\lambda}{\beta} [e^{\gamma x} - 1] & 0 \le x \le 1 \\ \frac{m\lambda}{\beta} [1 - e^{-\gamma}] e^{\gamma x} & \text{if } x \ge 1 \end{cases}$$
The results for the two methods can be extended to general networks of queues (8,11,15).

Each queue can be analysed separately; it is sufficient to know the arrival process:

$$ \lambda_m = \lambda e_m \quad e_m = p_{0m} + \sum_{m'=1}^{N} e_{m'} \quad p_{m'm} \quad (1) $$

$$ Ca_m = (1/\lambda_m) \sum_{j=0}^{N} [(Cs_j - 1)p_{jm} + 1] \mu_j p_{jm}^{\rho_j} \quad (2) $$

$Ca_m$ is an approximation (15); in this expression, $N$ is the total number of stations in the network, $\lambda$ is the rate or arrival, $\rho_m = \lambda_m / \mu_m$, $p_{ij}$ is the probability to go to station j from station i.

However the result is not acceptable for constant service times; for tandem queues, we obtain $Ca_m=0$ if $m>1$ since $Cs_j=0$ for all j, and the departure rate is approximated as constant, which is most often far from reality. We know the exact variance of interdeparture of the first station, it is $(1-\rho_1^2)/\lambda^2$. So for the station 2,3,...,K, the arrival process is no longer Poisson. We can give for the coefficient of variation of the interdeparture times at stations m, m=2,...,K a better approximation in using the method of Gelenbe-Pujolle (17): the values of the $Ca_m$, $1 \le m \le N$ are the solutions of the system of equations:

$$ Ca_m = \rho_m^2 (Ka_m + 1) + (1-\rho_m) \{ 2\rho_m + 1 + \lambda_m^{-1} \sum_{j=0}^{N} [(Ca_j - 1)p_{jm} + 1] \lambda_j p_{jm} \} - 1 $$

In these equations $Ka_m$, $1 \le m \le N$ are the squared coefficients of variation of service times. We find that a good approximation of $Ca_m$ is $1-\rho_m$ if $Ka_m=0$, $1 \le m \le N$.

Now we can apply this formula for our diffusion processes. The mean number of customers given by Gelenbe's method for the m-th station is:

$$ E_m = \rho_m \left[ 1 + \frac{\rho_m Ca_m + Cs_m}{2(1-\rho_m)} \right] $$

By Little formula (12) we obtain response time of each station $W_m = E_m / \lambda$.

### III - Example

We now present a simple example to compare the results obtained in the first two parts.

Consider the packet-switching store and forward communication network of figure 3. The arrival process is Poisson with rate 0.1. Since packets have fixed lengths, we assume that retransmission times for one packet are 4, 5, 2, 8 seconds and that buffers have an infinite capacity. We obtain the following table:

(comparison on mean response time)

<table><thead><tr><th></th><th>station 1</th><th>station 2</th><th>station 3</th><th>station 4</th><th>station 5</th></tr></thead><tbody><tr><td>Analytic compute</td><td>5.33</td><td>6.17</td><td>2</td><td>21.5</td><td>35</td></tr><tr><td>Gelenbe diffusion with Ca_m=1-ρ_m=1</td><td>5.33</td><td>6</td><td>2.125</td><td>20.0</td><td>33.255</td></tr></tbody></table>

We note that the error is very small. This method is really interesting in more complicated network because it is almost as easy to apply, even if there does not exist any theoretical results. We analyse this case in next part of this paper.

We now study the effect of the arrival Poisson in the results. We take Erlang 2, 5, 10, $\infty$ distribution and hyperexponential distribution with a squared coefficient of variation equal to 2, 5. In each case the mean arrival rate is 0.1. We obtain the following table:

(comparison on mean response time)

<table><thead><tr><th></th><th>station 1</th><th>station 2</th><th>station 3</th><th>station 4</th><th>total</th></tr></thead><tbody><tr><td>Erlang = -Ca = 0</td><td>4</td><td>5</td><td>2</td><td>8</td><td>19</td></tr><tr><td>Erlang = 10 Ca = 0.1</td><td>4.13</td><td>5.12</td><td>2</td><td>9.35</td><td>20.60</td></tr><tr><td>Erlang = 5 Ca = 0.2</td><td>4.25</td><td>5.23</td><td>2</td><td>10.7</td><td>22.19</td></tr><tr><td>Erlang = 2 Ca = 0.5</td><td>4.66</td><td>5.58</td><td>2</td><td>14.75</td><td>27</td></tr><tr><td>Exponential Ca = 1</td><td>5.33</td><td>6.17</td><td>2</td><td>21.5</td><td>35</td></tr><tr><td>Ca = 2</td><td>6.66</td><td>7.33</td><td>2</td><td>35</td><td>51</td></tr><tr><td>Ca = 5</td><td>10.66</td><td>10.85</td><td>2</td><td>75.5</td><td>99</td></tr></tbody></table>

The table shows that in such a system it is preferable that the interarrival times have small coefficient of variation.
IV - Extension at a general packet switching network and example.

In this part, we consider a general packet-switching network (figure 1). Until now, the study of such a network has been done by simulation, or by the Jackson (9) approximation, assuming Markov arrival and service processes. Diffusion processes form a new method and we shall now compare it with the known results in this area. If we are interested only by mean response time (MRT) (i.e. the mean time that a packet spends in the network), an important restriction may be suppressed: the finite storage of nodes. In effect, we have seen that in tandem queues the MRT is identical with or without finite storage. That property is still true for general network with the condition that a "good" policy is followed, which we shall assume now. We can then study the MRT with the infinite storage assumption.

If the network is important enough so that a customer arriving in a station may come from several other nodes, then it is possible to approximate the interarrival process to this station by a Poisson process. In this case the arrival rate is the sum of some arriving streams, (Kleinrock (9)).

With this assumption, we can study each station one after one, in considering them like M/D/1 queues. The results obtained by this method will be as better as the number of links and nodes is large. This method has the merit to be very simple, and it gives easily response time.

Diffusion processes may be applied to general networks. For a station it is sufficient to know the mean and the coefficient of variation of interarrival times. We can use again known expressions for tandem queue, in adapting them at a general network. If m is the examined station, denote $\lambda_m$ the mean interarrival time and $Ca_m$ its coefficient of variation.

$$ \lambda_m = \lambda_e m \quad e_m = p_{Om} + \sum_{m'=1}^{N} e_{m'} p_{m'm} $$

$$ Ca_m = \sum_{m'=0}^{N} (1 - p_{m'}) p_{m'm} $$

the response time of the m-th queue is then

$$ W_m = \frac{1}{\mu_m} \left[ 1 + \frac{\rho_m Ca_m + Cs_m}{2(1 - \rho_m)} \right] $$

We now compare the results of the two preceding methods with those of a simulation of the same network. As an example, we take the structure of the French network Cigale which is the packet-switching network of Cyclade (13), figure 4. This network has seven nodes and let $\lambda_i$, $i=1, \dots, 7$ be the arrival rates to those nodes, and we assume that the arrival processes are Poisson. We also assume that from any entry node, the probability of destination of the six other possible nodes are equal. All nodes are alike, and their structure is represented in figure 5. Each arriving packet is put in a queue to be treated by the commutator, which drives the packet in its come out line. We assume that switching times are negligible and that every queue has an infinite storage. All the lines have the same speed except $1 \to 2, 2 \to 1, 3 \to 2, 2 \to 3$. We also assume packets to be 1000 bits long. We take the following arrival rates :

$$ \lambda_1 = 1.3 \quad \lambda_2 = 1.87 \quad \lambda_3 = 1.17 \quad \lambda_4 = 2.26 \quad \lambda_5 = 2.83 \quad \lambda_6 = 1 $$

$$ \lambda_7 = 2.83 $$

We then obtain for the mean response times the following table (by analytic we refer Kleimock method)

<table><thead><tr><th></th><th>Analytic</th><th>Diffusion</th><th>Simulation</th></tr></thead><tbody><tr><td>1 → 2</td><td>0,514</td><td>0,514</td><td>0,506</td></tr><tr><td>2 → 1</td><td>1,155</td><td>0,796</td><td>0,835</td></tr><tr><td>2 → 3</td><td>1,948</td><td>1,722</td><td>1,738</td></tr><tr><td>2 → 7</td><td>0,576</td><td>0,536</td><td>0,552</td></tr><tr><td>3 → 2</td><td>1,173</td><td>1,217</td><td>1,123</td></tr><tr><td>3 → 4</td><td>1,741</td><td>1,568</td><td>1,549</td></tr><tr><td>3 → 5</td><td>0,612</td><td>0,554</td><td>0,533</td></tr><tr><td>3 → 6</td><td>0,973</td><td>0,613</td><td>0,527</td></tr><tr><td>4 → 3</td><td>5,310</td><td>5,310</td><td>5,221</td></tr><tr><td>5 → 3</td><td>1,923</td><td>1,798</td><td>1,728</td></tr><tr><td>5 → 6</td><td>0,492</td><td>0,511</td><td>0,508</td></tr><tr><td>6 → 3</td><td>0,225</td><td>0,269</td><td>0,271</td></tr><tr><td>6 → 5</td><td>0,219</td><td>0,279</td><td>0,285</td></tr><tr><td>6 → 7</td><td>0,889</td><td>0,847</td><td>0,858</td></tr><tr><td>7 → 2</td><td>1,983</td><td>2,654</td><td>2,845</td></tr><tr><td>7 → 6</td><td>1,010</td><td>0,961</td><td>0,951</td></tr></tbody></table>

We see on the preceding table that the approximation by a diffusion process gives very good results. Moreover it is an easy method to apply. Thus it seems that for the study of complicated network it is a very good tool.
B - Tandem queue with time-out.

I - Assumptions.

In a lot of computer networks, regulation techniques exist to prevent the congestion of nodes. One possible technique is the time out: we know that a packet has to go through the K+1 different stations in a well defined order. If the packet has not finished its service at the last station within a time T since it entered the network, it is rejected from the network and reinjected later in the network. In our model represented in figure 6, the network itself is represented by the station 1 to K, station 0 being the queue of packets waiting for entering the network. So, if a packet has not completed its service at station K after a time T, it is rejected and reinjected in station 0. In that model we also assume a limitation of memory capacity at nodes (i.e. for stations 1 to K), and for simplification of the model we assume that the number of packets in the whole network is limited to M. That means that the queue of station i, i=1,...,K is limited to M and that, if $n_i$ is the length of the queue at a given time :

$$ \sum_{i=1}^{K} n_i \le M. $$

The station 0 is supposed to have an infinite capacity.

**Definition** : We will say that the system is stable if the mean number in the station 0 is finite.

We certainly know that if $\lambda > \inf_{i=1,...,K} (\mu_i)$ there is no stable state. So we only consider the case where $\lambda < \inf_{i=1,...,K} (\mu_i)$.

We would like to know the relation which must be satisfied by M, $\mu$ and T so that there is no rejected packet, and, if packets are rejected the rejection rate.

II - Relation between M, $\mu$ and T.

We assume first that $K=1$. Let us take $\mu_1=\mu$ (figure 7).

**Theorem 11** : There is no rejected packet if $M/\mu \le T$.

**Proof** : Consider the worst case for a packet : the system is empty and M customers arrive at the same time (or in an infinite small time) ; the waiting time of M-th is $M/\mu$. This is not rejected if $M/\mu \le T$.

Now suppose $M/\mu > T$ and denote $u_1, u_2, ..., u_j, j \le M$ the packets in the system at time t, $u_j$ is in service, and $t_1, ..., t_j$ their entrance dates in the network (in station 1).

**Lemma 12** : If customer i is rejected and if $t_{i+1} - t_i < 1/\mu$, then the customer i+1 is also rejected.

**Proof** : Let $d_i$ be the critical date (date of reject of customer i if it is always in the network) and let $s_i$ be the virtual date of exit (date of exit of customer i if it is not rejected before). We want to show that $s_{i+1} > d_{i+1}$ if $s_i > d_i$ and $t_{i+1} - t_i < 1/\mu$. When the packet i is rejected, customer i+1 must stay almost $1/\mu$ in the network for its service so $s_{i+1} \ge d_i + 1/\mu$ and as $d_i = t_i + T$

$$ s_{i+1} \ge t_i + T + 1/\mu = t_{i+1} + T + t_i - t_{i+1} + 1/\mu $$

$$ s_{i+1} \ge d_{i+1} + t_i - t_{i+1} + 1/\mu > d_{i+1} $$

$s_{i+1} > d_{i+1}$. This completes the proof.□

**Lemma 13** : If the difference of entry times of two successive packets, is larger than $1/\mu$ then the second one will complete its service before its time out.

**Proof** : We show that if $t_{i+1} - t_i \ge 1/\mu$ then the i+1-th is not rejected by time out. We have :

$$ d_{i+1} \ge d_i + 1/\mu $$

→ if $t_{i+1} \ge d_i$ the property is obvious.

→ if $t_{i+1} < d_i$ then at the date $d_i$ the packet i+1 begins its service because all the customers j, with $j \le i$, are no longer in the system. The packet i+1 finishes at $d_i + 1/\mu \le d_{i+1}$ so customer i+1 is not rejected by its time out.

**Theorem 14** : If $M/\mu > T$ the output is zero, after a certain transitory period.
In reality the transition period can be very long, for a cyclic behavior can appear whose life time may be very large. By cyclic we mean that if the customer of rank i is rejected by its time out (resp. not rejected) the customer of rank i+M is also rejected (resp. no rejected). More than that, if $p=\lfloor T\mu \rfloor$, a maximum of P customers over M may not be rejected.

**Proof:** Suppose there are M packets inside the network with $t_{i+1} - t_i < 1/\mu$ for $i=1,...,M-1$ and that the first customer will be rejected. Then every packet will be rejected if $t_{M+1} - t_M < 1/\mu$. In effect the customers $u_1,u_2,...,u_M$ are rejected (lemma 12) and following customers also because :

$$t_{M+i+1} - t_{M+1} = (t_{i+1} + T) = t_{i+1} - t_i < 1/\mu; \text{ (a customer}$$

may enter only if another one goes out and there is at least customer i to go in, with position $M+i$).

So we must have the condition $t_{M+1} - t_M < 1/\mu$. Like $t_{M+1} = t_1 + T$ this condition can be written :

$$t_M - t_1 > T - 1/\mu \text{ or} \\ (t_M - t_{M-1}) + (t_{M-1} - t_{M-2}) + \dots + t_2 - t_1 > T - 1/\mu.$$

As $t_{i+1} - t_i < 1/\mu$, we must verify that we may have :

$$\frac{M-1}{\mu} > \sum_{i=1}^{M-1} (t_{i+1} - t_i) > T - \frac{1}{\mu}$$

Like we have the condition $\frac{M}{\mu} > T$ we have $\frac{M-1}{\mu} > T - \frac{1}{\mu}$; so it is always possible to find a set of $t_i$, $i=1,...,M$, which verifies the preceding equation, with a no null measure for the probability density of interarrival times. The transition period can be a cyclic behavior as defined before. The probability to go out of this cyclic period is never zero, but is smaller and smaller with the duration of that period. So physically if the queue 0 becomes very large, the cyclic regime is nearly endless.

Certain series of arrival can occur, with non-zero probability, that conducts to a cyclic period with non-zero throughput. We give an example to illustrate that phenomenon, in which n packets over M are not rejected. If $\lambda > n\mu/M$ it is statistically very improbable to go out of that state, because this periodic behavior can be broken only if the

length of the queue at station 0 becomes null. If for example $t_{j+1} - t_j > 1/\mu$ and $t_{i+1} - t_i < 1/\mu$ for $i \neq j$ and customer j+2 is rejected, only the customer j+1 and $kM+j+1$ are rejected (lemma 13), and a cyclic phenomenon is established. If $T=P/\mu + \varepsilon$, $\varepsilon < 1/\mu$ and $T < M/\mu$, at the most P/M customers can go out by cycle. Let $\lambda$ the arrival rate and n the number of customers which can go out by cycle, then if $\lambda < \frac{\mu n}{M}$ we are in transient period and if $\mu > \lambda > \frac{\mu n}{M}$, cyclic regime may become endless, in physical meaning but not mathematically.

## CONCLUSION

When $M/\mu > T$ there is no stable state and the first queue (the host) grows indefinitely.

Now if M becomes large, the relation $M/\mu > T$ is always true so there is not an equilibrium state; and to have a regulation with time out, it is then necessary to control the entry in the packet-switting network.

We now come back to the system represented in figure 6.

Let $\mu_{inf} = \inf_{i=1,...,K} (\mu_i)$ and $D = \sum_{\substack{i=1 \\ i \neq inf}}^{K} \mu_i$ so we have :

**Theorem 15 :** If $M/\mu_{inf} < T-D$ then no packet is rejected.

**Proof :** Suppose that nobody is rejected, so from the first part of this paper, we may change the order and the capacity of stations without changing the date of departures of packets. Thus we can put the station inf in first place. In the following stations there is at most one packet because they are separated by the time $1/\mu_{inf}$. The larger waiting time for a packet is when M packets arrive in the same time or almost. The response time of the last one is $M/\mu_{inf} + D$, it is not rejected if $M/\mu_{inf} + D < T$. $\square$

**Theorem 16 :** If $M/\mu_{inf} > T$ the output is zero after a certain transitory period.

But like in theorem 14, physically an endless cyclic regime can establish before.
**Proof** : Take the preceding notations and suppose that there are M customers inside the system, their arrival times verify $0 < t_{i+1} - t_i < 1/\mu_{inf}$ and the first one is rejected. Since a packet must pass by the service inf we must have

$$s_{i+1} \geq d_i + 1/\mu_{inf}$$

$$\text{as } d_i = t_i + T$$

$$s_{i+1} \geq t_i^{+1} + 1/\mu_{inf} = t_{i+1} + T + t_i - t_{i+1} + 1/\mu_{inf}$$

$$s_{i+1} \geq d_{i+1} + t_i - t_{i+1} + 1/\mu_{inf}$$

thus

$$s_{i+1} > d_{i+1} \text{ for all } i \in [1, M-1]$$

Like the first customer is rejected, following customers also are rejected till M-th. If $t_{M+1} - t_M < 1/\mu_{inf}$ the $(M+1)$-th is rejected and the following ones also, because $t_{KM+j} = t_j$.

We must have :

$$1/\mu_{inf} > t_{M+1} - t_M = t_1 + T - t_M \text{ or } t_M - t_1 > T - 1/\mu_{inf}$$

$$t_M - t_{M-1} + t_{M-2} + \dots + t_2 - t_1 > T - 1/\mu_{inf}$$

so we must have :

$$\frac{M-1}{\mu_{inf}} > \sum_{i=1}^{M-1} (t_{i+1} - t_i) > T - 1/\mu_{inf}$$

Since the assumption is $M/\mu_{inf} > T$, a set of $t_i$, with no null measure, exists. As in the case of two stations it is possible that a cyclic regime established before the "good" $t_i$ appear. []

Suppose now $T-D < M/\mu_{inf} < T$, we have :

**Theorem 17** : With the preceding assumption, a stable state exists (the queue 0 cannot become infinite).

We may not prove this theorem theoretically, but examples and simulations seem to prove it. It seems that when we are in saturation situation the throughput goes up to 1.

**Conclusion** : In a packet-switching network, with time-out regulation, if the computers which switch the packets, have a large memory, a regu-

lation on the total number of packets in the system must be done.

## REFERENCES

[1] AVI-ITZHAK B. - "A sequence of Service Station with Arbitrary Input and Regular Service times" Manag. Science - Vol. 11 - N° 5 - pp. 565-571-1965.

[2] COHEN J.W. - "The Single Server Queue" - Amsterdam - North-Holland Publishing Company - 1969.

[3] FRIEDMAN H.D. - "Reduction Methods for Tandem Queueing Systems" - Oper. Research - Vol. 13 - pp. 121-131 - 1965.

[4] GAVER and SHEDLER - "Processor Utilization in Multiprogramming Systems Via Diffusion Approximations" - Oper. Research 21 - pp. 569-576 - 1973.

[5] GELENBE E. - "Modèles de Systèmes Informatiques" Thèse Doctorat d'Etat ès Sciences Mathématiques Université Paris VI - 1973.

[6] 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.

[7] GELENBE E. - "On approximate Computer System Models" - J.A.C.M. Vol. 22 N° 2- April 1975.

[8] GELENBE E. - "Exact and approximate solution to probabilistic models of computer system behavior - Part I and II" - Proc. International School on Modelling and Measurement of Computer CNR and Universita di Bologna - Bologne - Février 1975.

[9] JACKSON - "Jobshop-Like Queuing Systems - Manag. Science 10 - 131-142 - 1963.
[10] KLEINROCK - "Communication Nets" - Mc Graw-Hill
New-York - 1964.

[11] KOBAYASHI H. - "Application of the Diffusion Approximation to Queueing Networks" Part I - J.A.C.M. 21, 2 - pp.316-328 - 1974.

[12] LITTLE J.D.C. - "A Proof for the Queueing Formula $L=\lambda w$" - Oper. Research - May 1961.

[13] POUZIN L. et GRANGE J.L. - "Cigale la machine de commutation de paquets" - Congrès AFCET - Novembre 1973.

[14] PRABHU N.V. - "Queues and Inventories" - New York - Wiley 1965.

[15] REISER and KOBAYASI - "Accuracy of the Diffusion Approximation for Some Queueing Systems" IBM J. Res. Develop. 18, 2 - pp. 110-124 - March 1974.

[16] RUBIN I. - "Path Delays in Communication Networks" - Appl. Math. Optimization - Vol. 1, N° 3 - 1974.

[17] GELENBE E. and PUJOLLE G. - "Probabilistic models of computer systems" Part II - Proc. International Symposium on Computer Performance Modeling, Measurement and Evaluation - Cambridge Massachusetts - March 1976.

## APPENDIX

**Proof** : First we are going to analyse the two queues tandem case, the second station being limited at one unity. $t_k$, $s_k$, $r_k$, are arrival times in the system, departure times of the first service, and departure times of the second service, respectively, and $t_k'$, $s_k'$, $r_k'$, the same times but for the two inversed stations. We want to show that $E(r_k-t_k) = E(r_k'-t_k')$ (in mean the packet k takes the same time to go through the system in a direction or in the other). Denote $S_{i,k}$, the service time of customer k in service i. We suppose that means of interarrival and service times are stationary $(E(S_{i,k}) = E(S_{i,k+1}), \forall k$ and $E(t_{k+1}-t_k) = E(t_k-t_{k-1}), \forall k)$. We have :

$$s_k = \sup(s_{k-1} + S_{1,k}, t_k + S_{1,k}, r_{k-1})$$

$$s'_k = \sup(s'_{k-1} + S_{2,k}, t_k + S_{2,k}, r'_{k-1})$$

$$r_k = s_k + S_{2,k}$$

$$r'_k = s'_k + S_{1,k}$$

$$\text{so } r_k - t_k = \sup(s_{k-1} + S_{1,k}, t_k + S_{1,k}, r_{k-1}) + S_{2,k} - t_k \\ = \sup(s_{k-1} + S_{1,k} - t_{k-1}, t_k - t_{k-1} + S_{1,k}, \\ r_{k-1} - r_{k-1}) + S_{2,k} - (t_k - t_{k-1})$$

Evidently we have : $E(r_i - t_i) = E(r'_i - t_i)$, because the system is empty.

Now assume (recurrent assumption) that $E(r_i - t_i) = E(r'_i - t_i)$ for all i strictly inferior to k, we have from the preceding calculus and from the assumptions :

$$E(r_k - t_k) = \sup(E(s_{k-1} - t_{k-1}) + E(S_{1,k}), E(t_k - t_{k-1}) + E(S_{1,k}), E(r_{k-1} - t_{k-1})) + E(S_{2,k}) - E(t_k - t_{k-1})$$

and with the recurrent assumption :

$$E(r_k - t_k) = \sup(E(s_{k-1} - t_{k-1}) + E(S_{1,k}), E(t_k - t_{k-1}) + E(S_{1,k}), E(r_{k-1} - t_{k-1})) + E(S_{2,k}) - E(t_k - t_{k-1})$$

so

$$E(r_k - t_k) = \sup(E(s_{k-1} - t_{k-1}) + E(S_{1,k}), E(t_k - t_{k-1}) + E(S_{1,k}), E(s'_{k-1} - t_{k-1}) + E(S_{1,k-1})) + E(S_{2,k}) - E(t_k - t_{k-1})$$

As $E(S_{1,k}) = E(S_{1,k-1})$ we have

$$E(r_k - t_k) = \sup(E(s_{k-1} - t_{k-1}), E(t_k - t_{k-1}), E(S_{k-1})) + E(S_{1,k}) + E(S_{2,k}) + E(t_k - t_{k-1})$$

with the symmetry of the result we have :

$$E(r_k - t_k) = E(r'_k - t_k)$$

Now suppose that we have two queues with an intermediate waiting room limited to M. This system is equivalent with M+1 stations in serie, the first one with infinite storage and rate $\mu_1$, and the following ones limited at one packet, with an infinite
service rate except the last one which have a rate $\mu_2$. As we have shown that it is possible to permute the order of two stations (even if the first station is of limited capacity, since the interar-rival processes are arbitrary), we may permute the stations of rate $\mu_1$ and $\mu_2$ by successive permutations. So, we may permute two stations with any intermediate storage. Now for a K queues system, we may put stations in any order by successive permutations. ☐

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

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

<figure><img src="image_7.png" /><figcaption>Figure 6</figcaption></figure>

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

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

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

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