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

HAL
open science

# A study of flows in an x25 environment

Jacques Labetoulle, Guy Pujolle, Noufissa Mikou

► To cite this version:

Jacques Labetoulle, Guy Pujolle, Noufissa Mikou. A study of flows in an x25 environment. [Research Report] IRIA-RR-327, IRIA. 1978, pp.20. hal-04716553

HAL Id: hal-04716553

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

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
Inv: 04308- RR327

RIA

laboria

(115)

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

A STUDY OF FLOWS
IN AN X25 ENVIRONMENT

20p.

Jacques LABETOULLE
Noufissa MIKOU
Guy PUJOLLE

Rapport de Recherche N° 327
Septembre 1978

RR 327
A STUDY OF FLOWS IN AN X25 ENVIRONMENT

Jacques Labetoulle*, Guy Pujolle*Noufissa Mikou**

Résumé :

Cette étude est une première approche qui permet d'évaluer les performances d'un réseau d'ordinateurs à circuits virtuels. Les recommandations X25 étant appelées à servir de normes internationales pour de tels réseaux, nous avons choisi d'analyser des réseaux bâts suivant ce schéma. Nous avons construit plusieurs modèles qui permettent de calculer analytiquement le temps de réponse et la condition de stabilité de ce type de réseaux d'ordinateurs.

Abstract :

This study is a first approach allowing to evaluate the performance of a computer network with
virtual circuits. Recommendations X25 being required as an international standard for such net-
works, we have chosen to analyse networks built following this scheme. We have developed several
models allowing to compute analytically the response time and the stability conditions of this type
of computer networks.

* IRIA/LABORIA - 78150 Le Chesnay

**Université PARIS XIII
# INTRODUCTION

During the past years, an increasing number of researchers have worked on the problem of predicting the performance of computer networks. The main results have been obtained for packet switching networks and for the behavior of node to node protocols. In the same period, virtual circuits networks has been introduced and to our knowledge no study has been published thus far concerning the analytical study of such networks. A considerable effort has been expended on the standardization of networks that leads to think that analytical results will have important consequences on the implementation of future networks.

In the near future the recommended protocol X.25 will be employed in a number of packet switching networks. As such it is very important that its performance be well understood. After reviewing the main characteristics of X25 a mathematical model is developed to allow us to compute its performance and to contribute to the understanding of the behavior of this protocol.

# BASIC CONSIDERATIONS ON X25

The recommendation X.25 contains three levels of interface [1]

* **Level 1** : the physical, electrical, functional and procedural characteristics to establish, maintain and disconnect the physical link between the hardware units.

* **Level 2** : the link procedure for data transmission. (It is a subset of the HDLC protocol).

* **Level 3** : the packet format and control procedures for the exchange of packets in the network.

Here we only deal with the level 3, and mainly with the performance allowed by the control procedures.

X25 flow control is negotiated between two terminal equipments by a virtual channel, as shown in Figure 1. (For the sake of simplicity, we shall assume there are no permanent virtual connections)
<figure><img src="image_3.png" /><figcaption>Figure 1</figcaption></figure>

Each data packet transmitted in a virtual connection is sequentially numbered. The sequence numbering scheme of the packets is performed modulo 8 or 128. Only data packets contain this sequence number called the packet send sequence number $P(S)$.

The maximum data field length of data packets is 128 octets. Additionally some implementations may support other maximum data field lengths from the following list of powers of two, i.e. 16, 32, 64, 256, 512, and 1024 octets. In the sequel, we shall assume packet lengths exponentially distributed around a mean value.

## PROCEDURE FOR FLOW CONTROL

The flow control for a virtual connection is based upon authorizations from the receiver. A window is defined as the ordered set of L consecutive packets send sequence numbers of the data packets authorized to cross the interface. Namely, the window size L specifies how many packets may be transmitted from A to B, without to be acknowledged. The value of L does not exceed 7 or 127 with the extended scheme.

The main tool for the control of data flow of a virtual connection is provided by Receive Ready (RR) and Receive not Ready (RNR) packets.
RR packets are used by the receiver to indicate that it is
ready to receive the L data packets within the window starting with
P(R) the number of the last packet it has correctly received. This
corresponds to a positive acknowledgement (of P(R) and previous ones).

RNR packets are used by the receiver to indicate a temporary
inability to accept additional data packets. In the same time it indi-
cates the last packet P(R) correctly received.

The retransmission of packets in error is provided by Reject
Packet (RP) specifying a logical channel number and a sequence number
P(R). This packet acknowledges all the frames until P(R) and asks the
retransmission of the packet in error P(R) + 1 and of all the packets
which has been sent after it.

We shall assume our network free of errors.

FLOW CONTROL PARAMETERS

The parameters of main importance for the implementation of
flow control are window size and data throughput class. In the X25
recommendation the selection of these two parameters is not provided,
and the aim of this study is to give an idea of performance which can
be obtained changing these parameters.

For each direction of a virtual connection, a throughput class
and a window size must be selected independently of one another. If
these parameters are not specified when the connection is set up,
standard values will be used. Indeed these last parameters are not
specified in X25 recommendation because they depend on the architec-
ture and the state of the system and only a mathematical model or a
real implementation may allow to provide these values.

A throughput class indicates how much octets shall be transmitted
on the average during one seconde. In the X25 recommendation, 16 diffe-
rent throughput classes are recommended 1, 2, 4, 8 ... 4096 octets/s.
It is obvious that for a certain window width the virtual connec-
tion cannot provide any throughput. Moreover, there exists a strong
dependency between these two parameters and the state of the network.
So the acceptance of a virtual connection knowing the two flow control
parameters implies the allocation of corresponding ressources of the
network, otherwise the connection is refused. In this last case the
network is congested.

THE MODELS

To study the relations between these two parameters and the
state of the system, we are going to introduce three models : a satu-
rated model and two non-saturated models.

The saturated model is a closed queueing network with N₁ nodes.
Between two any nodes any number of connections can be considered,
but we assume in a first step the window width equal to 1 for each
connection. The saturation is due to the fact that a closed network
is considered ; namely when a packet is arrived at the destination
node, it is immediately replaced by a new packet entering the origin
node. So we have a certain number of virtual connections with always
one and only one packet inside.

Now, if we consider a window width equal to L > 1, it is equi-
valent in our network to assume L virtual connections between the
same terminal nodes with a window width equal to 1 for each one.

The two non saturated models are open networks build from the
previous closed model where we have added an input queue behind each
virtual circuit. The service of this input queue is a scheduler which
allow to enter the virtual connection if no packet is into this cir-
cuit and to held back packets to be transmitted if the virtual circuit
is busy. The difference between the two models comes from the fact
that we take into account or not the acknowledgement frames. In the
first case, we assume an immediate acknowledgement when the packet
reaches its destination. In the second one, the return time of the
acknowledgement frames RR or RNR is taken into account.
## II - SOLUTIONS OF THE MATHEMATICAL MODELS

For the first model, a known solution can be used : BCMP's theorem [2]. Indeed considering each packet of a virtual circuit belonging to one class of customer, we obtain a case which can be solved by BMCP results assuming the service times are exponentially distributed. This solution is not satisfying because of both reasons : it cannot be used for the two open models and it does not allow to study network with a large number of nodes (the number of virtual connections or classes of customers increases rapidly with the number of nodes).

Let $\mu_i^{-1}$ be the mean service time at station i. We assume that at this time is added hardware and software overheads due to the HDLC procedure used for the data transmission between nodes. For open queueing network, we denote by $\lambda_j$ the packet arrival rate to the queue given access to the j-th virtual connection. We assume that the transformation of messages into packets is already done. We have described in the previous sections three kinds of models (one for the saturated case and two for the non saturated one). We have also mentioned that the first model can theoretically be solved using BCMP technics, but that the sizes of the problems we are dealing with forbid this kind of solution. So we are now developing a new technique to solve the models. First, we will give an intuitive approach which will give a set of equations we are able to solve, this solution being only approximative. Then we will show how it is possible to get an exact solution and the comparison of the two methods will show the degree of approximation we do using the intuitive solution. First let us give some definitions and notations. We suppose we have N physical lines and M virtual circuits. The matrix ($q_{ij}$, $1 \le i \le N, 1 \le j \le M$) represents the "routing" of the virtual circuits. The quantity $q_{ij}$ equals 1 if the virtual circuit j uses the line i and 0 if not. The waiting time (including service time) of a packet of the virtual circuit j at station i is denoted by $W_{ij}$. (In fact $W_{ij}=0$ if $q_{ij}=0$).
By extention we call customer j a packet using the virtual circuit j, and there is no confusion because we have supposed that there is only one packet into the circuit j at a given time.

Let us denote by $N_{ij}$ the mean number of packets the customer j finds in the station i when it enters this station (not including itself). We immediately see that :

$$ (1) \qquad W_{ij} = (N_{ij} + 1) / \mu_i $$

when $\mu_i$ represents the transmission rate of packets at station i.

This formula is obvious since we suppose a First come First service discipline at each station. To evaluate $N_{ij}$ we suppose that the queue i is in a steady state when customer j arrives. In that case we have :

$$ (2) \qquad N_{ij} = \sum_{\substack{k=1 \\ k \neq j}}^{M} p_i(k) $$

where $p_i(k)$ is the steady state probability that customer k is in station i.

In the first model (the saturated one), we have :

$$ (3) \qquad p_i(k) = \frac{q_{ik} W_{ik}}{N \sum_{\ell=1}^{M} q_{\ell k} W_{\ell k}} $$

that means that $p_i(k)$ is equal to the ratio of the mean time spent by customer k in station i over the total time spent by customer k in all the stations it goes through.

For the non saturated cases we define :

$t_k$ which is equal to the mean time the packet k uses to go through the network.
$t_k^*$ which is the mean time spent by the acknowledgement frame RR or RNR to go through the inverse of the virtual connection k. As RR and RNR packet lengths are very small, we assume their own service times neglectible (but not their waiting time).

With these assumptions added to the fact that we always consider the network at instants where we suppose it is in a steady state, we can say that $p_i(k)$ is equal to the product of the probability that the queue of virtual connection k is not empty ($\lambda_k * t_k$ or $\lambda_k * (t_k + t_k^*)$) by the ratio of the time spent in queue i over the time spent by the customer k in the system ($t_k$ or $t_k + t_k^*$).

This gives :

$$ (4) \qquad P_i(k) = q_{i,k} * W_{i,k} * \lambda_k $$

This intuitive approach comes from Little's formula applied to the customers of class k.

We can remark that $N_{i,j}$ will not depend on the policy we consider (with or without acknowledgements) but will only depend on the flow of customers of class k which is $\lambda_k$.

Equations (1), (2) and (4) leads to the linear system of equations

$$ (5) \qquad \mu_i W_{i,j} - 1 = \sum_{\substack{k=1 \\ k \neq j}}^{M} q_{i,k} W_{i,k} \quad \lambda_k $$

For the saturated model, the set of equations is :

$$ (6) \qquad \mu_i W_{i,j} - 1 = \sum_{\substack{k=1 \\ k \neq j}}^{M} \frac{q_{ik} W_{i,k}}{N} \quad \sum_{\ell=1}^{N} q_{\ell k} W_{\ell,k} $$

Let us now consider the saturated case again to show how to find the exact solution. A recent work done by Sevcik and Mitrani [3] has shown that in a BCMP network (and that is the case of the saturated sys-
tem) the state in which a customer j sees the system when it enters a queue is the steady state of the system composed of the global population minus customer j.

So

$$ (7) \qquad N_{ij} = \tilde{N}_i (K - \{j\}) $$

where $\tilde{N}_i (K - \{j\})$ represents the steady state of queue i in the network when it is charged by the population K minus customer j. We see then, it is possible to solve exactly the problem using and inductive model.

The real set of equations we have to solve should be :

$$ (8) \qquad \mu_i W_{i,j}(K) - 1 = \sum_{\substack{k=1 \\ k \neq j}}^{M} \frac{q_{i,k} W_{i,k}(K-\{j\})}{N} + \sum_{\ell=1}^{N} q_{\ell,k} W_{\ell,k}(K-\{j\}) $$

in which the argument we have added to the variables $W_{i,j}$ represents the population.

This study shows that the intuitive solution differs from the exact one only by the fact that we replace $W_{i,k} (K - \{j\})$ by $W_{i,k}(K)$. The error goes to zero when the population increases towards the infinity. As networks under study are very large (at least 40 virtual circuits) the error can be neglected.

For the non saturated cases, the error is more difficult to evaluate because the network of queues we consider is not of the BCMP class (anyway the solution is not on a product form). As a consequence it is not proved that the state in which a customer sees the system when entering a station is a steady state. But it is intuitive that we can state it as almost true if the population is large. In that case the rest of the previous arguments is still true and we can assume that the approximations we do are of the same order of magnitude as in the saturated case.
To fix the ideas, we have compared the exact and approximate
solution in a network with two queues and three customers (for the
saturated case), and we have seen that the error is never greater
than 10 %. We are sure that the error is much smaller for a popula-
tion of 50 or 100 customers.

SOLUTION OF THE MODELS

For the closed network, from equation (5) an iterative method
can be used to derive the solution.

Now for the open model, from equation (5), we have :

$$
(9) \quad (\lambda_j + \mu_i)W_{ij} - 1 = \sum_{k=1}^{M} q_{ik} W_{ik} \lambda_k \quad \text{if } q_{ij}=1
$$

if not, (i.e qij=0), then Wij=0.

The second term of (9) is independent on j, then

$$
(10) \quad (\lambda_j + \mu_i) W_{ij} = (\lambda_k + \mu_i) W_{ik}
$$

or

$$
(11) \quad W_{ik} = \frac{\lambda_j + \mu_i}{\lambda_k + \mu_i} W_{ij}
$$

Equations (9) and (11) lead to

$$
(12) \quad W_{ij} = (\lambda_j + \mu_i)^{-1} \left(1 - \sum_{k=1}^{M} q_{ik} \frac{\lambda_k}{\lambda_k + \mu_i}\right)^{-1}
$$

From (12) the round trip delay of a virtual connection is accord-
ing to the model $t_j = \sum_{i=1}^{N} q_{ij} W_{ij}$ or (if acknowledgements (ACK) are
counted)

$$
t_j + t_j^* = \sum_{i=1}^{N} q_{ij} W_{ij} + \sum_{i=1}^{N} q_{ij}^* W_{ij}
$$

where the $q_{ij}^*$'s are the "routing" probabilities of the ACK ($q_{ij}=1$ if
the ACK of the virtual connection j go through station i, 0 otherwise)
Now an important criteria of performance can be evaluated : the stability condition or the maximum throughput. Indeed the stability condition is obtained when there is at least one virtual connection saturated, namely when there are always at least one packet ready to be transmitted on this circuit. For this virtual circuit j, $t_j$ [or $t_j + t_j^*$] represents exactly the mean response time, namely the time necessary to transmit effectively one packet. Therefore the system is stable if and only if

$$ \forall j, \ 0 < j \le M \quad \lambda_j t_j < 1 \quad [\text{or} \ \lambda_j(t_j + t_j^*) < 1]. $$

If the previous condition is satisfied, so there exists idle periods in each virtual connection and $t_j^{-1}$ represents only the rate of service of the circuit j. Assuming the response time of each station exponentially distributed we can easily compute the squared coefficient of variation of the response time of each virtual circuit :

$$ Ks_j = \frac{\sum q_{ij}(W_{ij})^2}{[t_j]^2} $$

The mean response time of virtual connection j is now given by Kintchine Pollaczek formula :

$$ \bar{t}_j = t_j \left[ 1 + \frac{\lambda_j t_j (1+Ks_j)}{2(1-\lambda_j A(j))} \right]. $$

## EXAMPLES AND CONCLUSIONS

As an example we take the 7-node network described on Figure 2. Nodes A to G are computers used for packet buffering and switching. Nodes A' to G' are terminal equipments. Packet routing is assumed fixed and summarized in table 1. The routes which are not indicated on table 1 are chosen by the smallest number of nodes which are cross-ed. We assume that packet lengths are exponentially distributed and packets arrive to the terminal equipment as a Poisson process. We
<figure><img src="image_4.png" /><figcaption>Figure 2</figcaption></figure>

<table><caption>Table 1</caption><thead><tr><td>Source</td><td>Destination</td><td>Via</td></tr></thead><tbody><tr><td>A'</td><td>F'</td><td>C</td></tr><tr><td>B'</td><td>F'</td><td>C</td></tr><tr><td>C'</td><td>G'</td><td>F</td></tr><tr><td>D'</td><td>G'</td><td>F</td></tr><tr><td>C'</td><td>C', D'</td><td>B</td></tr><tr><td>F'</td><td>A', B'</td><td>C</td></tr></tbody></table>
assume that packets arriving from the outside of the network have
identical destination probabilities.

The packet switching network shown in Figure 2 can be repre-
sented as a queueing network with 16 internal queues and an input
queue for each virtual circuit.

There are 42 possible terminal node - terminal node connections.
At each virtual connection corresponds an inverse virtual connection
which processes the acknowledgements.

We shall assume in the examples that all the possible virtual
connections are set up, namely there exists 42 virtual connections.
In a first step we assume that all the circuits have the same window
width. We recall that the study of a virtual circuit with a window
width L is provided by the study of L virtual circuits of window width
1.

We assume in the examples that all the links have the same capa-
city and that the mean number of transmissions by unit of time is
10 (μ=10). The mean service time 0.1 takes into account the diverse
overheads due to the node-node procedure.

Two viewpoints can be examined about the performance. The first
one is to obtain the better performance for the global network. For
this reason we shall consider that all the virtual connections have
the same window width. In the second one, (a user viewpoint) for a
given network, we shall change only the window width of a particular
user.

We show in Figure 3, the response time of four virtual connections
versus the window width L :

virtual connection 1 : node A' to node D'

virtual connection 2 : node A' to node F'

virtual connection 3 : node D' to node G'

virtual connection 4 : node E' to node G'.
<figure><img src="image_5.png" /></figure>

Response time versus window width when $L\lambda = 1$ and $\mu = 10$

<caption>Figure 3</caption>
<figure><img src="image_6.png" /></figure>

Maximal throughput of each virtual connection versus
the window width (identical for each circuit)

<caption>Figure 4</caption>
We have to note that the response time decreases when the window width increases, but not at all linearly. Moreover, above the value four, the response time almost no longer changes.

The maximal throughput of each virtual connection as a function of the window width is shown in Figure 4. The bottleneck of the network is queue 3, therefore virtual connection $A' \to D'$. We assume as in the previous example that all the window widths of all the virtual connections increase alltogether of 1. As expected, the maximal throughput increases but becomes almost constant as soon as the window width is above 4.

However, we have to note that the number of buffers necessary to set up all the virtual connection increases with the window width $L$. For example for the output link numbered 3, 8L buffers are necessary for the allocation of virtual circuits.

We see on the previous example that the throughput class allowing more than 1.2 packet by unit of time is provided by window width greater than or equal 2.

But the most important remark is the fact that the throughput increases only a few with the window width. This is due to the heavy load the system has to support. We shall see that the same conclusion is not verified if the network is not saturated by the existing virtual circuits.

Now we assume that all the window widths of the 42 virtual connections are equal to one and we are going to increase only the window width of one circuit. Two examples are treated one connection ($A' \to D'$) which uses heavy load queues and one connection ($E' \to G'$) which uses light load queues.

The response time and the maximal throughput of both studied circuits when $\mu=10$ and $\lambda=1$, is shown in Figures 5 and 6.
We see that the response time practiquely does not change in relation with the Figure 3 (in dotted line we show results obtained in this last Figure). This proves that in steady state, the response time is only somewhat improved when increasing the window width. On the contrary, the maximal throughput of just a virtual connection can be greatly improved in the same condition. We see on Figure 6 that the maximal throughput of circuit E' → G' increases from 2.6 to 8 when the window width increases from 1 to 10. Indeed the queues used by this virtual connection are not at all saturated by other users as it is almost the case for the other circuit under study. So for the A' → D' circuit, the maximal throughput increases only slightly and becomes constant rapidly.

As a final conclusion we have remarked that the main two flow control parameters are very dependent on the state of the system. So, several tables are necessary to give the correspondances between the throughput classes and the window widths according to the state of the system. We can only summarize our approach by the following principles when a virtual connection asks to be set up : if the queues utilized by the circuit are under heavy load a small window width should be chosen, a large window width does not allow neither more throughput, nor better response time; if the queues utilized by the circuit are under light load the throughput increases with the window width and an adequate throughput class can be chosen.
— results obtained on Figure 3

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

Response time of circuit A' → D' and E' → G' versus window width of these connections when $\lambda=1$, $\mu=10$ and $L=1$ for the other connections

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

Maximal throughput of virtual connection A' → D' and E' → G'
versus the window width of these circuits
μ=10, L=1 and λ=1 for the other connections.
REFERENCES

[1] CCITT : Recommendation X.25. Orange Book, Vol. VIII. 2, Geneva, 1977.

[2] Baskett F., Chandy K.M., Muntz R.R., Palacios F.G., "Open, closed and mixed networks of queues with different classes of customers", J. ACM 22, 248-260, 1975.

[3] Sevcik K.C., Mitrani I, "The distribution of queueing network states at input and output instants", Rapport de Recherche IRIA-LABORIA n° 307, 1978.