# Analysis of flow-controls in switched data networks by an unified model

Guy Pujolle

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

## To cite this version:

Guy Pujolle. Analysis of flow-controls in switched data networks by an unified model. [Research Report] IRIA-RR-291, IRIA. 1978, pp.8. hal-04716511

HAL Id: hal-04716511

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

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
<figure><img src="image_3.png" /></figure>

laboria

laboratoire de recherche
en informatique
et automatique

ANALYSIS OF
FLOW-CONTROLS IN
SWITCHED DATA NETWORKS
BY AN UNIFIED MODEL

Guy PUJOLLE

Rapport de Recherche N° 291

Avril 1978

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20
ANALYSIS OF FLOW-CONTROLS IN SWITCHED DATA NETWORKS
BY AN UNIFIED MODEL

Guy Pujolle

IRIA/LABORIA

Résumé :

A partir d'une présentation unifiée des contrôles de flux dans les réseaux à commutation de paquets, un modèle mathématique est proposé pour en comparer les effets. Grâce à ce modèle, nous prouvons tout d'abord la nécessité d'un contrôle de flux. En l'absence d'un tel mécanisme, un phénomène d'effrondement apparaît dès que la charge s'accroît. Ensuite, nous comparons les débits qui peuvent être obtenus par les différents types de contrôles de flux, toujours à partir du modèle mathématique.

Abstract :

A mathematical model of a packet switching network is developed, based on an unified presenta-
tion of flow-controls, otherwise a thrashing phenomenon occurs when the traffic is over a certain
value. Then, we compare the performance of the main flow controls, using the mathematical
model.

Cet article sera présenté en Septembre 78, à Kyoto (Japon) au Fourth International Conference on Computer Communication (ICCC 78).
# 1. INTRODUCTION

The main computer networks use a packet switching network (P.S.N) to communicate with each other. These networks possess flow-controls, but they are all distinct and often very different from each other.

The purpose of this paper is to compare the performance of these flow-controls. To do this, we introduce a unified mathematical model based on a unified presentation of the flow-controls. The model uses a single source destination path. The study of the node transmission procedures allows to take into account the overheads due to the traffic.

Firstly we prove the necessity of a flow-control. Without controls a thrashing phenomenon occurs and the throughput decreases when the traffic rate (or the utilization) goes to 1. Secondly, we compare several flow-controls. Suggestions are given for their use.

# 2. THE UNIFIED FLOW-CONTROL

In a switched data network, several levels of communication can be found. We limit here to three levels [1] (figure 1).

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

- level 0 which corresponds to the communication between nodes in the switched data network,

- level 1 which corresponds to the communication between hosts,

- level 2 which corresponds to the communication between users in the computer network.

The communications at each level must be governed by a protocol. Moreover, protocols between levels 0-1

and 1-2 are necessary. They allow the compatibility of the three levels, and then they must be determined by these three levels. The control of flows is one of the functions of these protocols.

Therefore, the flow-control in a packet switching network is defined by the superposition of three levels that must be compatible. As the last level (user) is difficult to govern due to the random behavior of users, often only two levels of control exist.

Now at each level we must define the possible controls. Examining carefully the existing networks or research papers on the subject, we can see that only two important control tools exist : thresholds and preallocations [2]. It is only the manner of applying these tools which provides global control flow techniques.

Therefore a flow control is determined by the knowledge of thresholds and allocations at the level 0 and at the level 1 (eventually at the level 2). In this way, practically all existing flow-controls can be reformulated and new flow control techniques could be studied.

At the end-to-end level (host level), among the threshold possibilities we have:

## A - limitation of numbers

- global number limited (by credits or by a control center)

- a limited number by routes

- a limited number by users

## B - limitation by unit of time

- without variation in the time

- according to the state of the buffers

- according to the load on the lines.

For the allocations of buffers we have only two possibilities

- total preallocation

- partial preallocation.

At the node to node level, thresholds and allocations can be:

- threshold
  size of available buffers
  load on links
  age of packets (time-out)

- request for allocation in the following node.
That list is not exhaustive, but practically all the existing flow controls are represented.

We give briefly some examples on the main computer networks.

**Arpanet [3]** : level 1 - threshold to 8 by user with a partial preallocation (at the output node);

level 0 - threshold on the size of available buffers (8).

**Datapac [4]** : level 1 - threshold on the number by route. This threshold varies with the state of the network;

level 0 - threshold on the size of available buffers (8).

**Cyclades [5]** : level 1 - threshold by unit of time taking into account the load on the links;

level 0 - threshold on the size of available buffers (5).

**NPL [6]** : level 1 - threshold on the global number in the network. This threshold is obtained by the utilization of credits;

level 0 - no supplementary flow control; (a packet can enter a node only if it possesses a credit).

**Transpac [7]** : level 1 - total preallocation

level 0 - no control.

### 3. NODE-TO-NODE TRANSMISSION PROCEDURE

In the modeling of store-and-forward communication lines we have to know the behavior of nodes. This behavior is very dependent on the node-to-node transmission procedure. Two types of procedure can be allowed

1. without anticipation,

2. with anticipation.

The "send and wait" procedures [8] (TMM for example in Cyclades) belong to the first category. Before transmitting a new frame, the previous one must be acknowledged, HDLC or MV8 (used in Cyclades) belong to the second category.

We are going to analyse the behavior of "without anticipation" procedures. On the time axis of figure 2, we have represented the state of the sender and the receiver during the transmission of a packet.

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

In that diagram $\tau$ represents the time that the previous packet if any takes to finish its transmission. The acknowledgement (ACK) comes back to the receiver either "piggyback" (inside a packet) or in a control packet. We denote by $S$, the service time, namely the total time necessary for the transmission of a packet. This mean service time $S$ is given by :

$$S = \omega_{00} + \omega_{01} + \omega_{02} + \frac{L}{v} + \omega_{10} + \omega_{11} + \omega_{12} + \frac{1}{v} + \tau$$

where

- $L$ is the total length of the packet;

- $l$ is the length of the packet which returns the ACK,

- $v$ is the line capacity,

- $\tau$ is the time necessary for the transmission of the end of the preceding packet (or 0 if there is no preceding packet).

The various overheads are due mainly to the switching of the processes. On the average we can take the following values [9] measured on the Cyclades network :

$$\omega_{00} = \omega_{10} \approx 5 \text{ms} \quad \omega_{01} = \omega_{11} \approx 3 \text{ms}$$

$$\omega_{02} = \omega_{12} = \begin{cases} 10 \text{ms on a } 4.8 \text{ kbit/s link} \\ 3 \text{ms on the others.} \end{cases} \quad \text{we assume } 500 \text{ km line length.}$$

We have to note the variation of $l$ and $\tau$ according to the load on the lines. If the load is light $l$ is only the length of an ACK (generally 7 octets) and $\tau = 0$. In heavy traffic $l$ and $\tau$ are respectively a packet length and half a packet length on the average. (For a "send and wait" procedure $l$ is always the length of an ACK).

If we assume that mean packet length is 1000 bits the average of the service time $S$ is between two values given in the table 1, ($L$ is expressed in Kbits) for a "send and wait" procedure.

<table><caption>Table 1</caption><thead><tr><th>line capacity</th><th>minimum of S (ms)</th><th>minimum of S if L=1kb</th><th>maximum of S (ms)</th><th>maximum of S if L=1kb</th></tr></thead><tbody><tr><td>4.8</td><td>48 + 213 L</td><td>261</td><td>155 + 213 L</td><td>368</td></tr><tr><td>19</td><td>28 + 54 L</td><td>82</td><td>55 + 54 L</td><td>109</td></tr><tr><td>48</td><td>26 + 22 L</td><td>48</td><td>37 + 22 L</td><td>59</td></tr></tbody></table>

The difficulty that arises is the dependence of the transmission time on the load of the lines.

In the sequel, we assume a symmetrical traffic and we denote by $\rho$ the load on the line. If $\rho=0$ then the service time $S$ is minimum; and if $\rho=1$ the service time $S$ is maximum. We shall adopt a linear variation of the mean service time $S$ between its maximum and its minimum. $L$ is the mean packet length expressed in kbits.

$$\begin{cases} \text{line capacity } 4.8 \text{ Kb/s } S(\rho) = 213L + 48 + 107 \rho \\ 19 \qquad S(\rho) = 54L + 28 + 27 \rho \\ 48 \qquad S(\rho) = 22L + 26 + 11 \rho \end{cases}$$

These mean service times can be written in the general form :

$$(1) \quad S(\rho) = C_a L + C_b + C_c \rho$$

If an error occurs during the transmission or if the packet is rejected due to a lack of memory in the next node, a backup copy is retransmitted after a time out $T$. Let $p$ be this probability, then the mean transmission time becomes

$$(2) \quad S(\rho) = (C_a L + C_b + C_c \rho) (1-p) + T_p$$

Generally $T$ is between 200 and 1200 ms.

The transmission error probability is less than 0.01 and can be neglected. However $p$ is not negligible when the system is close to saturation.

### 4. THE UNIFIED MATHEMATICAL MODEL

In this section, we consider a particular route inside the store-and-forward P.S.N.

Such a route is modeled as a tandem queueing network. The system consists of $K + 1$ queues. A customer (cor-
responding to a packet of data) goes through the system joining the $(i+1)$-th queue after the $i$-th device for $0 \le i \le K-1$.

The first station 0, corresponding to the host, is assumed to have an infinite number of buffers. We assume that one packet and only one can be memorized in one buffer. All the other stations get a finite number $M_i$ of buffers (there is room for only $M_i$ packets at station i). This finite size corresponds to the storage facility of a node.

The unified mathematical model is described on figure 3

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

In the Figure 3, customers of station C represent the credits. If the queue is empty the host must wait for a credit before transmitting a packet. The number of credits in the packet-switching network is denoted by $N$. When a packet goes out of the network a credit comes towards the host. It passes through the station R which represents if necessary the return time of the credit (and the positive ACK). When a customer flows from station 0 to station 1 a credit disappears.

The main flow-controls can be characterized as follows.

At the node-to-node level thresholds are characterized by the number of available buffers $M_i$, $i=1,...,K$. When a threshold is reached, two alternatives exist for arriving packets.

1. The switch - retransmission, namely the packet is lost and a backup copy is retransmitted from the preceding switch (example ARPA).

2. The host - retransmission, namely the packet is lost and a backup copy is retransmitted from the host, (for example Cyclades).

Preallocation at the node level is modeled by a service time including the request for allocation. $M_i$ represents the number of buffers which can be allocated and blocking corresponds to a refusal to the request.

For each end-to-end flow-control, an associate model is included in the general system of Figure 3, in the following way :

A - limitation of numbers : we have the whole model of figure 3.

B - limitation by unit of time : stations R and C do not exist. The service rate of the host cannot go up above a value determined by the limitation. Moreover, this limitation can depend on the state of the buffers or on the load on the lines.

C - for total preallocation, we adopt the model without stations R and C. The service time of the host includes the request for allocation. The maximum number of preallocated buffers is $M_i$ for the node i, therefore the maximum number of packets in transit in the P.S.N is $\inf_{i=1,...,K} M_i$.

For partial preallocation the previous schemes are superposed.

## 5. RESOLUTION OF THE UNIFIED MATHEMATICAL MODEL

In a real P.S.N each packet maintains its length as

it travels from node-to-node, then service time are not independent. We make here the independence assumption of Kleinrock [10], and a new packet length is chosen in each station. Moreover, we shall assume that service times are exponentially distributed in each station.

Several criteria can be used to evaluate the performance of the models. In this paper we use the throughput of the system versus the traffic rate in the host. By traffic rate we mean the ratio of the arrival rate and the service rate. The customers which are rejected out of the network and which come back in the host are counted in the arrival rate. This traffic rate is identical to the service activity of the host, when a steady state exists.

From a given traffic $\rho$ in the host, we shall compute the probability $p$ that a customer is rejected out of the P.S.N and comes back into the host. Then, the transmission time is obtained by relation 2 :

$$S(\rho) = (C_a L + C_b + C_c \rho)(1-\rho) + T_p, \quad \rho \le 1.$$

Therefore we obtain the total arrival rate $\lambda^*$ as $\lambda^* = \rho/S(\rho)$. This rate is the sum of external arrivals and recycling packets therefore the throughput of the system will be : $\lambda = \lambda^*(1-\rho)$.

### Study of the model without either credit scheme or preallocation.

1. node-retransmission : the only recycling customers come from station 1, then $S(\rho)=(C_a L+C_b + C_c \rho)(1-p_1)+T_p$

and $\lambda = [\rho/S(\rho)](1-p_1)$ where $p_1$ is the probability that a customer is rejected at station 1.

2. host-retransmission : in this case, rejected customers come from all the stations. If $p_i$ is the probability that a packet is rejected by station i, $\lambda$ is given by the following :

$$(3) \qquad \lambda = \lambda^*[1-p_1-(1-p_1)p_2-\dots-(1-p_1)\dots(1-p_{K-1})p_K].$$

In this case $S(\rho) = C_a L + C_b + C_c \rho$ and is independent of T (we assume the transmission errors negligible). We obtain $\lambda^* = \rho/S(\rho)$, then $\lambda$ is computed from the relation 3.

To be realistic we assume that our queueing system is a particular path inside a general network such that all the service times are equal. In this case the probabilities $p_i$ are computed by a numerical algorithm described in Irland - Pujolle [11] in the two protocol cases.

### Study of the general unified flow control model.

The model has been described in figure 3. We assume that if a packet cannot enter a node, it is retransmitted from the previous node.

The solution we propose is to use an equivalent station. The closed network representing the model of the P.S.N itself can be replaced by a single queue with a state dependent service rate $v(j)$, $j=1,...,N$ ($N$ is the total number of credits, namely the total number of packets in the P.S.N plus the free credits). We have to study a closed queueing network with finite buffer size. As no analytical method is available to study such a queueing system, we adopt a simulation just to compute the utilization $A_j^K$ of the server K, when there are $j$ customers in the closed network. We have assumed in this simulation that the service time of the credit queue equals the host service time. The equivalent service rate is obtained as $v(j)=\mu_{K}A_j^K=\mu_{Q}A_j^K$ (because we always assume all the servers identical).

The equivalent system is described on figure 4
<figure><img src="image_7.png" /><figcaption>Figure 4. packet switching networks</figcaption></figure>

The probability p for a customer rejection is easy to compute, for a given ρ. It is with a good approximation the solution of

$$p = \frac{\frac{(\mu_o \rho)^N}{\nu(1) \dots \nu(N)}}{1 + \frac{\mu_o \rho}{\nu(1)} + \dots + \frac{(\mu_o \rho)^N}{\nu(1) \dots \nu(N)}}$$

(See the appendix for the proof and the values of the coefficients).

Therefore S(ρ) and λ* can be computed. The throughput of the system is now: λ = λ*(1-p). This value obviously depends of N, the total number of credits. If there are as many credits as the total number of buffers in the P.S.N we come back to one of the previous cases. If N ≤ inf (Mᵢ) there is never retransmission in the P.S.N and we can study the equivalent closed network assuming infinite buffer size. (Method of Gordon and Newell [13] is used).

The flow control corresponding to a total preallocation is identical to a credit scheme with exactly N = inf (Mᵢ) credits. In this case each packet i=1,...,K

has a buffer reserved by node.

## 6. RESULTS

We assume that all the stations are identical: all the lines have the same speed 4.8, 19 or 48 kb/sec. and the pool of buffers at each station equals M(Mᵢ=M, i=1,...,K). Mean packet length is 1kb.

### Results of the model without either threshold scheme or preallocation scheme.

On figure 5, some curves have been drawn, representing both the situations of node-retransmission and host-retransmission. On these results it is difficult to appreciate the better method and only other considerations (as reassembling of packets) could show the efficiency of one or the other method.

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

As node-retransmission seems better, though its performance is comparable to host-retransmission, in the sequel we study only the former case.

We study the model under several different assumptions. The number of queue in series is 3, 6 or 9, the memory size at each station is 2,5 or 8 buffers and three speeds are available: 4.8, 19 or 48 kbit/sec.

Results of the throughput versus the traffic rate are described by the curves in figure 6, 7 and 8.

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

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

<figure><img src="image_11.png" /><figcaption>Figure 8</figcaption></figure>
Several important conclusions can be noted.

- A thrashing phenomenon exists when the traffic rate increases. But when the traffic rate approaches one, the throughput does not become zero.

- The maximum of the throughput is obtained for a value of ρ less than 0.8. This maximum is an unstable point. Without flow control the maximal throughput is obtain for ρ=1.

- A flow control must allow to increase the throughput, in preventing the thrashing.

## Results of the model with a flow-control.

The flow-control using a threshold on the number of retransmission by unit of time can be studied on the same model. This threshold corresponds to a value ρ* of ρ and we can consider that for a traffic rate above this value ρ* the throughput stays constant and equals the throughput obtained for ρ*.

This method can be very efficient if it is possible to find the limitation corresponding to the maximum throughput. However, in a general network, according to the destination of a packet, the line capacities and the sizes of the pools of buffers, the maximum throughput does not correspond to the same limitation. In Cyclades or Datapac the two flow-controls use such a limitation varying according to the state of the system.

<figure><img src="image_12.png" /><figcaption>Throughput Vs. Traffic rate/
Number of credits, 6 stat.,
5 buf., 48 Kbits/sec line.</figcaption></figure>

<caption>Figure 9</caption>

On figure 9, we give the throughput when a credit scheme is used, for different values of N the number of credits. The model we use is composed of six stations with five buffers. The number of credits varies from N=5 to N=25. The former case corresponds to a preallocation scheme : there is never loss of packets from the P.S.N. The latter case is identical to a previous one : there is always a free credit in the credit queue. We have assumed that the queue R does not exist. The advantage of the preallocation scheme is that no thrashing phenomenon exists. Above a certain value of the traffic rate, the throughput is approximately constant. However, this constant value is far from the maximum value.

If the number of credits is too high we find again the cases treated on figure 6, 7 and 8. A thrashing phenomenon occurs when ρ approaches one, namely when the system is near saturation a degradation of the system happens.

Now for a "good" value of N (the number of credits)

the maximum throughput is close to the maximum found in the scheme without control. When the traffic rate approaches 1, the throughput decreases but slowly.

## 8. CONCLUSIONS

Firstly we have shown that a flow-control is necessary in P.S.N. Without a flow-control a thrashing phenomenon occurs when the traffic rate reaches a value close to 1. Several flow-controls have been modeled and the comparisons of the results can be interpreted as follows. The preallocation technique allows one to obtain a certain throughput which is not decreasing even when the system is saturated. We are sure that whatever the conditions of traffic, always a certain amount of service will be rendered. However, the maximum throughput is very low in relation with the throughput obtained by otheir flow-controls.

Limitation of the number by unit of time, gives efficient results if it is easy to find the accurate limitation corresponding to the near maximum throughput. If the network is well balanced or very simple as a tandem queueing system, the value of the limitation can be obtained. But in a complex network, this limitation will have to change with the state of the network. A system of control packets must be created, for the hosts know the state of the system.

Limitation by unit of time will allow to obtain large throughput but with the condition to have a complex and expensive control system. Thrashing phenomenon can appear with bad management.

Credit scheme can be considered as an intermediate method. The maximum throughput is not so hight as in the previous scheme, but there is not really thrashing in saturation conditions. Moreover, the simplicity of this scheme can be a good reason for its implementation.

At the node-to-node level, host retransmission and node retransmission have comparable performance. However if reassembling of packets or response time [12] are important, node-retransmission seems to give better results.

To summerize, the conclusions could be :

- limitation in number by unit of time for small networks

- credit scheme for large networks

- preallocation if a precise amount of data must be transmitted.

## APPENDIX

We assume that the distribution of the interarrival times in the second station is a Markov renewal process. This is not quite true because the dependance due to the feed-back. The second station is a M/M/1/N queue and the probability of rejection p is given by :

$$ (A1) \quad p = \frac{\frac{(\mu_o \rho)^N}{\nu(1) \dots \nu(N)}}{1 + \frac{\mu_o \rho}{\nu(1)} + \dots + \frac{(\mu_o \rho)^N}{\nu(1) \dots \nu(N)}} $$

$$ \text{where } \mu_o^{-1} = (C_a L + C_b + C_c \rho)(1-p) + Tp $$

So p is obtained as the solution of equation A1 where µ₀ and ρ depend on p.

## REFERENCES

1. A. Danthine, J. Bremer, "Définition, représentation et simulation de protocoles dans un contexte réseaux", Proc. of the A.I.M, Liège, 1975.
2. W. Chou, M. Gerla, "A unified flow and congestion control model for packet networks", Proc. of ICCC 76, Toronto, 475-482, Toronto, 1976.

3. J.M. Mc Quillan et al., "Improvements in the design and performance of the ARPA network", Proc. of the FJCC, 1972.

4. P.M. Cashin, "Datapac network protocols", Proc. of ICCC 76, Toronto, 150-155, 1976.

5. L. Pouzin, "Cigale, the packet switching machine of the Cyclades computer network" IFIP Congress, Stockholm, 155-159, 1974.

6. R.A. Scantlebury, P.T. Wilkinson, "the national physical laboratory data communication network", Proc. ICCC 74, Stockholm, 223-228, 1974.

7. A. Danet et al. "The french packet switching service: the transpac network", Proc. of ICCC 76, Toronto, 251-260, 1976.

8. G. Fayolle, E. Gelenbe, G. Pujolle, "An analytic evaluation of the "send and wait" protocol", to appear in IEEE Trans. on Com. and IRIA/LABORIA Research Report 207, 1976.

9. J.L. Grangé, P. Mussard, "Performance measurements of line control protocols in the Cigale network", Proc. of Computer Network Protocols Symposium, Liège, 1978.

10. L. Kleinrock, Communication nets - stochastic message flow and delay, McGraw-Hill, New York, 1964.

11. M. Irland, G. Pujolle, "Models of tandem networks of queues motivated by packet switching" IRIA Research Report n° 256, 1977.

12. J. Labetoulle, G. Pujolle, "Modelling of packet switching communication networks with finite buffer size at each node", Proc. International Symposium on Computer Performance Modelling, Yorktown Height, 515-536, 1977.

13. W.J. Gordon, G.F. Newell, "Closed queueing systems with exponential servers", Operations Research 15, 254-265, 1967.

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

Guy PUJOLLE was born in 1949 in Paris. He obtained his Maîtrise de Mathématiques from Université Paris VII in 1972. After graduate work in probability theory at Université Paris VI, he joined the research group on Computer System modelling at IRIA/LABORIA and obtained his Doctorat de Troisième Cycle degree in febru ary 1975. The subject of his works is the analysis of networks

of queues with finite capacity and blocking using some approximation techniques, and the application of these results to multiprogramming systems and to computer networks. Dr. PUJOLLE has published several papers in this and related areas. He is presently interested in protocols, and in the performance prediction of computer networks.