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

HAL
open science

# Validation and prediction of performance in the cigale network

François Eyries, Guy Pujolle

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

## To cite this version:

François Eyries, Guy Pujolle. Validation and prediction of performance in the cigale network. [Research Report] IRIA-RR-314, IRIA. 1978, pp.15. hal-04716570

HAL Id: hal-04716570

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

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_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_4.png" /></figure>

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

VALIDATION AND PREDICTION
OF PERFORMANCE
IN THE CIGALE NETWORK

(118)

François EYRIES
Guy PUJOLLE

Rapport de Recherche N° 314

Juin 1978

15p.
VALIDATION AND PREDICTION OF PERFORMANCE
IN THE CIGALE NETWORK

François Eyries, Guy Pujolle

IRIA

Résumé :

Des campagnes de mesures ont été effectuées sur le réseau d'ordinateurs CYCLADES. Les résultats obtenus sont comparés aux performances prédites par un modèle mathématique. Les critères de comparaison sont : le débit maximum, le temps de réponse et le nombre de paquets en transit dans le réseau.

Une fois le modèle mathématique validé par ces résultats de mesures, il est utilisé pour prédire les performances du réseau sous diverses hypothèses. Nous permettons à quatre facteurs importants de varier :

- la distribution de la longueur des paquets,

- la capacité des lignes de transmission,

- le nombre de tampons disponibles dans les nœuds

- la procédure de ligne.

Cette étude mène aux résultats suivants :

- il est préférable d'avoir une longueur de paquet constante,

- les capacités des lignes doivent être équilibrées,

- un petit nombre de tampons est suffisant pour atteindre un débit presque maximal,

- les performances obtenues en utilisant la procédure MV8 avec anticipation sont meilleures que celles provenant d'une utilisation de procédures du type «send and wait».

Abstract :

A measurement campaign has been conducted on the CYCLADES computer network. The results obtained are compared with the performance predicted by a mathematical model. Maximum throughput, response time and number of packets transiting through the network are the three criteria used to compare the performance. Measurements on the real system are obtained with a packet generator.

One the mathematical model has been validated by measurements, it can be used to predict computer network performance under different circumstances.

We allow four important factors to vary :

- the packet length distributions,

- the line speeds,

- the number of buffers (i.e. node capacity),

- the line procedures.

This study yields the following results :

- it is preferable to have a constant packet length,

- capacity of lines must be balanced,

- a small buffer size is sufficient to obtain the near maximum throughput,

- the CYCLADES MV8 line procedure with anticipation gives better performance than the CYCLADES «send and wait» line procedure.
## 1. Introduction

Over the past ten years have been presented numerous models of Computer Systems. The validation of the predicted results by comparisons with measures on the real system are very rare. Many times, comparisons with simulated systems only are available.

As measurement campaigns have been conducted on some Computer Networks such as ARPA [1], CYCLADES [2], new validations are possible. In this paper we present results of a measurement campaign on the CYCLADES Network [2] and the performance predicted by a mathematical model.

In section 1, we give the characteristics of the measured system. Section 2 develops the mathematical models corresponding to the measured network. The next section is devoted to the comparisons of both types of results. In section 4 we use the validated mathematical models to design performance improvements in the computer networks.

## 2. Measures on the real system : the CIGALE machine

CIGALE is the store-and-forward packet switching machine of the CYCLADES Network [3,4]. Presently two types of measurements are conducted on CIGALE : external and internal.
François EYRIES and Guy PUJOLLE

The first one is conducted from the IRIA IRIS-80- SIRIS-8 Computer which is a CYCLADES host. They are not operating measurements : we observe the behaviour of CIGALE at some well defined points and under precise conditions.

## 2.1. Measurement tools.

They consist of :

- A traffic generator (MESCIG) which sends packets into CIGALE under various conditions. These packets follow a route and return to the origin. For this, we use a facility of CIGALE which allows us to force the packet to follow a route defined in the beginning of the packet text ("forced routing").

- An observer (OBSERVER) which contains :

a - an on-line measurement system which memorizes for each returned packet the values of some state variables (LENGTH, TRIP DELAY, INTERSEND and RECEIVE DELAY, etc...)

b - an off-line analysis system which gives from the memorized data, various analysis edited in graphic form.

## 2.2. Routes and traffic under study.

The routes are defined from the nodes depicted in Figure 1

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

Between these nodes :

- The lines have neither the same speed nor the same length : from 4.8 Kbits/sec to 48 Kbits/sec for the speed, from some meters to 600 KM for the length.

- Two different line-procedures are used :

a - the CII-HB standard procedure TMM characterized by the fact that a new packet is sent only after the reception of the acknoledgement (ACK) of the previous packet. When the ACK does not come back, the packet is resent at the end of a time-out (now 300 milliseconds in CIGALE on the 48 kbits/sec line and 1200 on the other lines).

b - the multichannel procedure MV8 akin to HDLC procedures. It is possible to send up to 8 packets before reception of any ACK.

Computers at each node are CII-HB MITRA 15. In each node the received packet is switched towards an output line according to the destination of the packet and the routing tables. Each output line has a queue which contains at most five packets. When a packet is switched and the queue is full, a dropped packet is ignored by the user because an end-to-end protocol is in charge of resending the dropped packet (end-to-end transport protocol in CYCLADES).

Six routes have been measured. Among them, we study the following ones*: (half the routes only are described)

<footnote>* Route 0 is just a loop on the IRIS 80. Route 2 uses the service ECHO (which returns the received packet to its source) [6].</footnote>
## VALIDATION AND PREDICTION OF PERFORMANCE
IN THE CIGALE NETWORK

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

### The traffic

The packet generator has been used to send packets from the IRIS 80 at the maximum possible speed. That is, a new packet is transmitted as soon as the ACK of the previous packet comes back (TMM procedure handles the input output of IRIS 80, cf. Fig. 1).

This maximum rate takes into account the following overheads: packet building time (numbering, send time recording), packet sending time by IRIS 80, ACK waiting, task switching, and possibly online retransmission.

The route under study is saturated by the input traffic. The other traffic on the route is negligible with respect to the generated traffic. All the packets sent by the traffic generator during one run are of the same (constant) length : the text length is taken from 24 to 255 bytes, that is from 51 to 282 bytes for the total length.

### 3. The mathematical models

#### 3.1. Tandem queues

The mathematical models, that we can associate with the routes described in the previous section, are tandem queueing systems presented in Figure 2.

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

Their features are :

a - The output of the server i is the input of the server i+1.

b - The intermediate queues are of finite length; only a fixed finite number $M_i$ of customers may wait between servers :

$$M_i = 5 \text{ for the queues } i, 1 \le i \le k.$$

c - On the contrary the queue before the first server may grow without bound : it is the host (IRIS 80).

d - If an intermediate queue is full and another customer completes service at the preceding server, he is dropped.

e - We assume that interarrivals and service times are independent and identically distributed (cf. [5] concerning this assumption).
## 3.2. Servers

### 3.2.1. TMM Server

The TMM procedure is expounded in Figure 3.

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

The service time S can be written as :

$$S = \omega_{00} + \omega_{01} + \omega_{02} + \frac{\ell_1 + \ell_2}{v} + \omega_{10} + \omega_{11} + \omega_{12} + \frac{\ell_3}{v}$$

Where :

$\ell_1 + \ell_2$ is the total length of the packet

($\ell_1$ = text length, $\ell_2$ = header length)

$\ell_3$ is the ACK length equal to 7 bytes.

$v$ is the line speed.

$\omega_{00}, \omega_{10}$ are due to the task switching and eventually software work of the packet.

$\omega_{01}, \omega_{11}$ are the software delay of the writing on both systems.

$\omega_{02}, \omega_{12}$ are due to the propagation delay, and depend on the modems used and the line length.

If a transmission error occurs, the packet is retransmitted at the end of a time out T. The model of one effective transmission with the TMM procedure is described on Figure 4 :

<figure><img src="image_10.png" /><figcaption>Figure 4</figcaption></figure>
## VALIDATION AND PREDICTION OF PERFORMANCE
IN THE CIGALE NETWORK

q is the frequency of a packet transmission error. Therefore the total average service time is as follows :

$$ \mu^{-1} = \frac{T_q}{1-q} + S $$

### 3.2.2. MV8 Server.

For the MV8 procedure the working diagram is described on Figure 5 :

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

and, taking into account the error frequency q, the total transmission time can be described by the model presented in Figure 6.

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

The service time without errors is :

$$ S' = \omega_{00} + \omega_{01} + \frac{\ell_1 + \ell_2}{\nu} $$

The total average service time is :

$$ \mu^{-1} = \frac{S'}{1-q} $$

We have assumed here that the anticipation factor or the window width (8 in MV8) is never reached.

### 3.3. Solving the model

To summarize, a route can be modeled by a tandem queueing system where the service rates are $\mu$ or $\mu'$ according to the protocol.

A similar queueing model with a general service process has been studied by Pujolle [8]. We recall briefly the solution and extend it to our case described on Figure 7.

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

We use a diffusion process approximation [10] to compute the probability of packet loss due to buffer overflow as follows :
François EYRIES and Guy PUJOLLE

$$p_i = \frac{\rho_i (1-\rho_i)}{e^{-\gamma_i (M_i - 1)} - \rho_i^2}$$

where

$$\rho_i = \frac{\lambda_i}{\mu_i}, \quad \gamma_i = 2 \frac{\beta_i}{\alpha_i}, \quad \beta_i = \lambda_i K s_{i-1} + \mu_i K s_i, \quad \alpha_i = \lambda_i - \mu_i$$

$Ks_i$ is the squared coefficient of variation of the service time at station i.

When $p_i$ is known, the arrival rate at the following station is :

$$\lambda_{i+1} = \lambda_i (1-p_i)$$

This allows the computation of $p_{i+1}$ and so on.

The maximum throughput of the overall system $\lambda_{max}$ is obtained when there is always at least one customer in the first queue : namely, $\lambda_1 = \mu_0$ (cf. Lavenberg [9]).

The throughput of the system is : $\lambda_k(1-p_k)$ equal to $\lambda_{max}$ if $\lambda_1 = \mu_0$.

Thus by a step by step procedure we obtain the maximum throughput. The expected length of each queue can also be found by the diffusion approximations : (see Gelenbe [10]). Let $E_i$ be the expected length of the queue at station i. The total number of customers in transit along this route of the network is :

$$E = \sum_{i=1}^{k} E_i$$

(The packets in the host are not counted). Applying Little's formula to each station we can write the mean total response time :

$$W = \sum_{i=1}^{k} \frac{E_i}{\lambda_i (1-p_i)}$$

Other measures of performance such as the ratio of the rate of dropped packets to the total effective throughput can be computed as :

$$r = \frac{\sum_{i=1}^{k} \lambda_i p_i}{\lambda_k (1-p_k)}$$

### 3.3. Value of the parameters

Preliminary measurements are necessary to the application of the mathematical model.

The values of the parameters are evaluated in [6,7,11] : the overheads $\omega_{00}$, $\omega_{10}$ are due to task switching and also to the software time related to packet transmission. On the average

$$\omega_{00} \approx \omega_{10} = 5 \text{ milliseconds.}$$

For the software time for a transmission, we take :

$$\omega_{01} \approx \omega_{11} \approx 3 \text{ milliseconds.}$$

For the propagation delay we take :

$$\begin{align*} \omega_{02} = \omega_{12} &= 10 \text{ millisec on the 4.8 KBaud line} \\ & 3 \text{ millisec on the 48 KBaud line} \\ & 0 \text{ for the other lines.} \end{align*}$$
## VALIDATION AND PREDICTION OF PERFORMANCE IN THE CIGALE NETWORK

The study of the number of retransmissions due to time-outs allows us to determine the transmission error frequency $q$. From [6, 11] we take $q = 2.10^{-3}$ for all the lines except the 48 Kbit/sec line for which $q = 5.10^{-2}$.

The time-out delay for retransmission in the TMM procedure is now 300 milliseconds on the 48 Kbits/sec line and 1200 milliseconds on the other lines.

The squared coefficient of variation of the service times is computed as follows :

$$K_s = q + \hat{K}_s(1-q).$$

Where $\hat{K}_s$ is the squared coefficient of variation of the transmission delay $S$.

When packets have a constant length, $\hat{K}_s = O_1$ we obtain $K_s = q$. The squared coefficient of variation of the total service time is not exactly constant.

When the distribution of the packet length is negative exponential, the distribution of the total service time is also negative exponential.

### 4. Results and validation

We now apply the method described in the previous sections, with the packet lengths given in Table 8.

<table><caption>Table 8</caption><thead><tr><th>Text length</th><th>Total length</th></tr></thead><tbody><tr><td>24 bytes</td><td>51 bytes = 408 bits</td></tr><tr><td>60</td><td>87 = 696</td></tr><tr><td>100</td><td>127 = 1016</td></tr><tr><td>140</td><td>167 = 1336</td></tr><tr><td>180</td><td>207 = 1656</td></tr><tr><td>220</td><td>247 = 1976</td></tr><tr><td>255</td><td>282 = 2256</td></tr></tbody></table>

On Figures 9 through 12 we can compare the network performance with constant length packets, given by :

a - the measurements on the network;

b - the mathematical model.

In these comparisons, the following criteria of performance are used :

- throughput in packets/second,

- useful throughput in bits/second,

- round trip delay in millisecond,

- number of packets in transit without the dropped packets.

### 5. Predictions of the mathematical models

Now that we have validated the mathematical models, we can predict the new performance obtained in varying some characteristics of the network. In the sequel, we shall use only one performance criterion : the receiver throughput in packets/second.

We allow four important factors to vary :

- the packet length distribution;

- the line speeds;
François EYRIES and Guy PUJOLLE

<figure><img src="image_14.png" /><figcaption>Throughput Vs. packet length</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Useful throughput Vs. packet length</figcaption></figure>
VALIDATION AND PREDICTION OF PERFORMANCE
IN THE CIGALE NETWORK

<figure><img src="image_16.png" /><figcaption>Figure 11
Trip delay Vs. packet length</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Figure 12
Number of packets in transit without the dropped packets Vs. packet length</figcaption></figure>
- the number of buffers (namely the node capacity);

- the line procedures.

These factors will vary independently of each others. The routes numbered 4 and 5 will be used for the comparisons. Three packet sizes are considered : 24, 140 and 255 octets, namely short, medium and large packets.

## 5.1. Packet length distribution

We allow the distribution of packet length to be exponentially distributed. We compare on Figure 13 the throughput obtained with this distribution. A dotted line represents the constant length case.

In this figure we can see that in the exponential case the throughput is less than that in the constant case. Indeed the throughput is included between these values namely the actual value is bounded by these two extreme cases.

<figure><img src="image_18.png" /><figcaption>Throughput Vs. packet length
(exponential transmission time, buffer size M)</figcaption></figure>

## 5.2. Line speed

If the speed of the 4.8 line varies from 4.8 to 48 Kb/sec, we obtain curves in Figure 14.

These curves show the importance of balanced lines. In the tandem queueing case where each station has approximately (because the losses) the same throughput, it is useless to have a line faster than the others. In the example, the replacement of a 4.8 Kb/sec line with a 19.2 Kb/sec line almost doubled the throughput of the system. On the contrary, the change from 19.2 to 48 modifies practically nothing.

In a general network, the problem of balancing the lines depends on the mean traffic.
## VALIDATION AND PREDICTION OF PERFORMANCE

### IN THE CIGALE NETWORK

#### 5.3. Buffer size

In CIGALE, output buffers allow the storage of 5 packets. What is the performance if we change this size? Figure 15 answers the question. The throughput of route 4 is given as a function of the number of buffers.

The best throughput is obtained for an infinite waiting room, this is obvious. But the maximum value of the throughput is reached quickly. In our example a pool of 5 buffers yields almost the maximum throughput in the exponential case. For constant packet this was already noticed elsewhere [14].

To determine the optimum pool size we have to solve a cost problem. In [13] the optimum is given with other line procedures.

<figure><img src="image_19.png" /><figcaption>Figure 14
Throughput Vs. link speed</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Figure 15
Throughput Vs. buffer size</figcaption></figure>
## 5.4. Protocol change

The influence of the line procedures is not very well known. The approach, that we take here, allows us to compare two types of procedures :

- TMM which is of the "send and wait" type,

- MV8 with anticipation, the performance of which must be comparable to that of HDLC procedures (MV8 anticipation factor is 8).

We give in Figure 16 the throughput of the various routes either with the standard line procedures (also given in Figure 1), and with the MV8 line procedure everywhere.

As expected, the latter case is better than the former, and the difference is significant and must be noted.

In the case of a constant packet length it is possible to show that the throughput is dependent almost only on the procedure used by the slowest line of the route. On the other hand, in the exponential case it is desirable to have MV8 handle lines everywhere on the same route.

<figure><img src="image_21.png" /><figcaption>Figure 16</figcaption></figure>

## 6. Conclusion

Throughput Vs. packet length/procedure

In this work, we have compared the performance obtained by measurements on the real network CIGALE and by a mathematical model, so as to validate the latter.

Then with the help of the model, we have studied how network performance may change if we change some of its features.

This study yields the following results :

- it is preferable to have a constant packet length,

- the capacity of the lines must be balanced,

- a small buffer size is sufficient to obtain the near maximum throughput, especially if packet length is constant,

- the CYCLADES MV8 line procedure with a window width of 8 gives better results than the CYCLADES "send and wait" line procedure (TMM).
VALIDATION AND PREDICTION OF PERFORMANCE
IN THE CIGALE NETWORK

References

[ 1 ] - L. Kleinrock, H. Opderbeck, "Throughput in the Arpanet", Proc. 4th data comm. Symp. 6.1, 6-11, 1975.

[ 2 ] - F. Eyries, M. Gien, "On line Performance Measurement in the CYCLADES Computer Network", Eurocom 77, Venezio, 1977.

[ 3 ] - L. Pouzin, "Presentation and Major Design Aspects of the CYCLADES Computer Network", Proc. 3rd ACM/IEEE, Data Comm. Symp., Tampa, 80-87, 1973.

[ 4 ] - L. Pouzin, "CIGALE, the Packet Switching Machine of the CYCLADES Computer Network", IFIP Congress, Stockholm, 155-159, 1974.

[ 5 ] - L. Kleinrock, Communication Nets. Stochastic Message Flow and Delays, Mac Graw-Hill, New York, 1964.

[ 6 ] - J.L. Grangé, P. Mussard, "Performance measurements of line control protocols in the CIGALE network", Computer Network Protocols Symposium, Liège, 1978.

[ 7 ] - J.L. Grangé, P. Maximovitch, "Mesure de Délais de Propagation en Ligne sur le Réseau CIGALE", Iria, Réseau CYCLADES, Mes 514, 1976.

[ 8 ] - G. Pujolle, "Ergodicity Conditions and Congestion Control in Computer Networks", 2nd Symp. on Mod. and Perf. Eval. of Comp. Syst., Striesa, 1976 (IRIA Research Report n° 190).

[ 9 ] - S.S. Lavenberg, "Stability and Maximum Departure Rate of Certain Open Queueing Networks, having Finite Capacity Constraints", IBM Research Report, RJ 1625, San Jose, 1975.

[10] - E. Gelenbe, "An Approximate Computer System model", J. ACM, 22, 2, 261-269, 1975.

[11] - P. Mussard, "Etude du Comportement de la Ligne à 48 KB/sec Paris Grenoble", IRIA, Réseau CYCLADES, Mes 522, 1977.

[12] - M. Irland, N. Cohen, "Simulation of Switch-Switch Protocol MV8 in CIGALE", Research Report CCNG. E53, Waterloo, 1976.

[13] - M. Irland, G. Pujolle, "Models of Tandem Networks of Queues Motivated by Packet switching", IRIA, Research Report, n° 256, 1977.

[14] - J. Labetoulle, G. Pujolle, "A study of Queueing Networks with Deterministic Service and Application to Computer Networks", Acta Informatica 7, 183-195, 1976.