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

HAL
open science

# Performance of the HDLC protocol

Jacques Labetoulle, Guy Pujolle

► To cite this version:

Jacques Labetoulle, Guy Pujolle. Performance of the HDLC protocol. [Research Report] IRIA-RR-352, IRIA. 1979, pp.11. hal-04716611

HAL Id: hal-04716611

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

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
Inw: 06408. RR352

IRIA
laboria

Institut de Recherche
d'Informatique
e t d'Automatique

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

laboratoire de recherche
en informatique (115)
et automatique

PERFORMANCE OF
THE HDLC PROTOCOL

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

Jacques LABETOULLE
Guy PUJOLLE

Rapport de Recherche N° 352

May 1979

11p.
PERFORMANCE OF THE HDLC PROTOCOL

Jacques Labetoulle, Guy Pujolle

IRIA-LABORIA

Résumé :

Le but de cet article est d'évaluer les performances du protocole standard HDLC (high-level data link control) utilisé pour la transmission des paquets entre deux nœuds d'un réseau de communication. De plus nous proposons et analysons des améliorations qui peuvent être apportées à ce protocole. Le modèle mathématique du protocole HDLC permet de calculer ses performances en fonction du degré d'anticipation en tenant compte des délais de propagation, des temps de gestion propre, et des caractéristiques du trafic.

Abstract :

The purpose of this paper is first to evaluate the performance of the HDLC (high-level data link control) protocol, then to suggest and analyse some possible improvements. The mathematical model of the HDLC protocol developed here allows us to compute its performance as a function of the window width according to the characteristics of the traffic and taking into account the transmission delays and the overheads.

<figure><img src="image_4.png" /></figure>
The most important parameter of HDLC is the anticipation factor. This anticipation factor or window width of a node is defined as follows. Consider two nodes i = 1, 2 communicating with each other along two parallel channels. Each channel is used to transmit packets in one direction. $N_i$ is the window width of node i : this node can send up to $N_i$ packets to the other node before stopping and waiting for an acknowledgement; in other words, $N_i$ is the maximum number of unacknowledged packets which node i is allowed to send before it must stop and wait for an acknowledgement.

In fact a node stores the unacknowledged packets (up to $N_i$) and removes them at the reception of a positive acknowledgement.

The anticipation factor of HDLC has been fixed to 7 (or 127 in an extended mode). It may be reduced to a smaller value at the establishment of the link, or by using type U frames. So we consider this parameter as constant during a session, because for us, a session is included between two sequences containing type U frames.

HDLC provides two types of negative acknowledgements when a packet has been lost during the transmission or is in error :

- the "selective reject" demands only the retransmission of the packet in error.

- the "reject" or "non selective reject" demands the retransmission of the packet in error and of all the packets which have been sent after it.

The choice between selective reject and reject can be modified only by using type U frames, so it cannot be altered during a session.

Two other mechanisms are possible to recover errors : Checkpoint Retransmission (p/F-Bit recovery) and timeout recovery. As we study only the maximum throughput of the procedure these two last mechanisms will not be used.

## 2. SUMMARY OF PREVIOUS RESULTS

In a previous paper [3] we have described a simplified model for HDLC from which we have established explicit formulae for the maximum throughput with and without loss of packets due to transmission errors. In that model we have neglected the effects of propagation delays and we have assumed that the acknowledgements always come back with the first packet arriving from the other node. (We shall see in the next part that these assumptions are rough approximations of the reality). We use the following definitions :

- the *activity* of a channel is defined to be the proportion of time the channel is busy sending packets to the other node. The *maximum activity* is the

## Introduction

International organizations such as ISO or CCITT are making great effort for the protocol standardization and already are producing such outputs as X.25 and HDLC recommendations. The performance evaluation of this last protocol has lagged somewhat behind, though considerable progress has been made in understanding the aspects which influence their behaviour. The HDLC (High-level Data Link Control) protocol [1], [2], is a node-to-node standard procedure.

The purpose of this paper is first to evaluate the performance of the HDLC protocol. Then some possible improvements are suggested and analysed. To prove the accuracy of our approach we compare the solution we obtain to the results get by a measurement campaign conducted on the Cyclades network with a somewhat different node-to-node protocol.

## 1. DESCRIPTION OF THE PROTOCOL

We study the class of two way simultaneous Asynchronous Response Mode (ARM) of operation which performs point-to-point transmission of informations.

These are transmitted through three types of frames : (the usual notion of packet is here called frame)

- Type I frames : they contain a message to be transmitted and a header containing the number of the frame sent and the number of the last frame correctly received (corresponding then to a positive acknowledgement).

- Type S frames : they are supervisory frames whose aim is to synchronize the behaviour of two nodes communicating through an HDLC protocol. In particular, they can contain negative acknowledgements.

- Type U frames : they contain control informations and are devoted to establish a link and/or to modify the current parameters of the link.

We deal here with the stationary behaviour of a link under a certain load. So we have not taken into account type U frames which modify the working assumptions of the link.
activity of one channel when assuming that both channels have always at least one packet ready to be transmitted.

- the throughput of a channel is the mean number of packets sent by the channel per unit of time. The maximum throughput is the throughput of one channel when assuming that both channels have always at least one packet ready to be transmitted.

By using a well known result of Lavenberg [4], one knows that the system is stable if and only if the rate of arriving packets at each node is less than the maximum throughput. If that were not the case the number of packets waiting to be transmitted will grow indefinitely.

In the sequel of this paper we have always considered that the acknowledgements are always contained in the information frames. That is true for positive acknowledgements but only an approximation for negative ones. But we have seen that negative acknowledgements are contained in type S frames which are very short comparing with type I frames. So we shall include a type S frame inside the type I frame which follows it. In the case where a node has no information frames to send (either because its output queue is empty or because its anticipation factor is reached), this node will even send packets (of type S) providing positive or negative acknowledgements. In other words this means that a node receives packets, thus acknowledgements, at a rate independent on the state of the other node. This assumption will be used all over in the sequel of the paper.

We assume that packet lengths are exponentially distributed with mean $L_1$ and $L_2$ respectively in the direction $1 \to 2$ and $2 \to 1$. We denote $t_1$ and $t_2$ the maximum activities of nodes 1 and 2 and $T_1$ and $T_2$ their maximum throughput. $N_1$ and $N_2$ define the window width of the link $1 \to 2$ and the link $2 \to 1$ respectively, and $p$ denotes the probability that a packet is in error.

The results we obtained in [3] are the following :

$$t_1 = 1 - \left( \frac{L_2}{L_1 + L_2} \right)^{N_1} \qquad t_2 = 1 - \left( \frac{L_1}{L_1 + L_2} \right)^{N_2} \\ \text{and } T_1 = t_1/L_1 \qquad T_2 = t_2/L_2$$

A special case of interest occurs when the characteristics of packet traffic in both directions are identical. If we take $L_1 = L_2 = 1$ and $N_1 = N_2 = N$ we

$$\text{obtain : } t_1 = t_2 = 1 - \frac{1}{2^N}.$$

The other results we proved, concern the effects of transmission errors.

When "selective reject" is used then in the symmetrical case defined above :

$$t_1 = t_2 \approx 1 - \frac{1}{2^N} - p \left(1 + \frac{3}{2^{N+1}}\right).$$

The introduction of transmission errors and selective reject reduces the activity by a quantity

$$p\left(1 + \frac{3}{2^{N+1}}\right) \text{ only.}$$

When "reject" is used then

$$t_1 = t_2 \approx 1 - \frac{1}{2^N} - p\left(2 - \frac{4 + N}{2^{N+1}}\right), \text{ the activity is reduced by only } p\left(2 - \frac{4 + N}{2^{N+1}}\right).$$

From this analysis, we can conclude that if the probability to have a packet in error is acceptable (less than 0.01), its effect can be neglected.

So, in the sequel of this study we shall assume that transmissions are conducted on high quality lines so that the effect of packets in error is negligible.

### 3. THE MATHEMATICAL MODEL

In the previous section, we chose very simplifying assumptions, and in particular, we neglected the propagation delays and the overheads of each node. Let us describe the successive steps of the life of a packet.

As soon as the transmission is completed at the emitting node, at time $t_o$, the receiving node must wait for a fixed propagation delay $C$ before the last octet arrives. Then an overhead $\delta$ is spent to verify the correctness of the frame and to build the corresponding acknowledgement. This acknowledgement will not be sent in the frame being transfered at time $(t_o + C + \delta)$ by the node. (The packet actually being transfered cannot be modified). Thus the acknowledgement will be sent in the following packet, which achieves its transmission at time $t_1$. For the same reasons as previously it will be available for the emitting node at time $t_1 + C + \delta$. This behaviour is schematized in figure 1.

<figure><img src="image_5.png" /><figcaption>Figure 1: the successive steps of the life of a packet.</figcaption></figure>

Thus we can see that the acknowledgement is always contained in the second packet available at the sender after the time $t_o + 2(C+\delta)$ and never before because the first packet received after $t_o + 2(C+\delta)$ was being transmitted at time $t_o + C + \delta$ (when the packet arrives at the second node) and thus cannot contain the acknowledgement.

Let us call $Q_1$ and $Q_2$ the two queues which contain the packets waiting to be transmitted by node 1 and node 2. The distribution of arrival times in these two queues are assumed to be exponential, with parameter $\lambda_1$ and $\lambda_2$ respectively. We shall assume that the acknowledgements arrive at each node at a rate independent of the state of the other node (we have seen why in the previous section). We shall use the following notations:

- $L_1$ and $L_2$ are the mean packet lengths in the direc-
tions 1 → 2 and 2 → 1 respectively and these
lengths are exponentially distributed; v is the
speed of the line. So the mean transmission times
on the two links are $\mu_1^{-1} = L_1/v$ and $\mu_2^{-1} = L_2/v$.
Let $R = 2$ ($C + \delta$) corresponds to the total const-
tant delays. Let us denote by $S = R + 2/\mu_2$, the
mean round trip delay for the acknowledgement.
($1/\mu_2$ for the packet being transmitted at time
$t_o + C + \delta$ and $1/\mu_2$ for the packet containing the
acknowledgement).

The behaviour of the protocol in one direction (node 1 towards node 2) can then be described by the set of servers of figure2.

<figure><img src="image_6.png" /><figcaption>Figure 2 : the mathematical model</figcaption></figure>

The packets are supposed to arrive into the queue $Q_1$ according to a Poisson process of parameter $\lambda_1$. They are served, if the maximum window width is not reached, by an exponential server with a rate $\mu_1 = v/L_1$.

When the transmission of a packet is completed (end of service of the server $\mu_1$), it enters a station $A_i$, with constant service time $R$, corresponding to the sum of all the delays.

After this station, the packet enters the first buffer in the position $B_i$. It will enter the second buffer, in position $B'_i$, when a packet arrives from the other node. At the same instant of time, all the packets of the first buffer will enter the second buffer and all the packets of the second buffer will leave the system. Recall that we consider only positive acknowledgements, so no packets have to be sent again. As we have seen before, the interarrival times of packets from the second node are exponentially distributed with parameter $\mu_2 = v/L_2$ and they contain the acknowledgements of all the packets of the second buffer. Let us note that at a given time, there can be only one packet in the positions $A_i, B_i$, and $B'_i$, for $1 \le i \le N_1$, so there is no more than $N_1$ packets waiting for their acknowledgement.

That model represents the behaviour of a line opera-
ting under HDLC protocol. Unfortunatly this system is

not solvable. However, to obtain some results we have
replaced it by a much more simpler model shown in fi-
gure 3.

<figure><img src="image_7.png" /><figcaption>Figure 3 : the simplified mathematical model</figcaption></figure>

The characteristics of this new model are the follo-
wing.

- The external arrivals and the first station are identical to the previous model.

- Queues A, B and B' are replaced by an unique system of $N_1$ servers in parallel with a mean service time

$$
S = R + 2 \mu_2^{-1}
$$

The distribution of the service times of this station
with $N_1$ parallel servers is the sum of two exponential
distributions and of a constant one.

The mathematical model is then of the type M/M/1 → .
/G/N₁/N₁. In that system as in the first model when a
customer cannot enter the second station it is blocked
in the first one, or what it is equivalent,it begins
again its service.

If we study the maximum throughput, we have to consider that the first queue $Q_1$ is never empty, so we have to evaluate the throughput of the system shown in figure 4 :

<figure><img src="image_8.png" /><figcaption>Figure 4 : the mathematical model to obtain the maximum throughput.</figcaption></figure>
This system is an M/G/N₁/N₁ queue with loss, and the solution is given by Cohen [5]; we obtain directly the maximum throughput T₁:

$$T_1 = \mu_1 \left( 1 - \frac{\frac{N_1}{\rho N_1!}}{1 + \rho + \frac{\rho^2}{2!} + \dots + \frac{\rho^{N_1}}{N_1!}} \right)$$

with $\rho = \mu_1$. $S = \mu_1 (R + 2/\mu_2)$.

The activity of the channel is therefore :

$$t_1 = \frac{T_1}{\mu_1}.$$

Let us remark that this result is only function of the mean of the service times and not of their distributions.

## 4. RESULTS AND IMPROVEMENTS FOR A TERRESTRIAL CHANNEL

We now give the results obtained with the model shown in figure 4.

In the sake of simplicity and to be able to compare the results, we shall assume that the unit of time is equal to 1/μ₁. The performance measure used is provided by the activity of the channel.

We have chosen our parameters from measurements made on the french network CYCLADES [6] for 48, 19.2 and 4.8 K bits/sec lines.

For a link of 500 km length the measured propagation delays are of 3 ms for 48 and 19.2 lines and 10 ms for 4.8 lines. These times are mainly due to the overheads of the modems used in the network. The sender and receiver overheads are equal to 5 ms, and we consider two different mean packet lengths : 300 and 1000 bits. The numerical values are summerized on tables 1, 2 and 3.

<table><thead><tr><th rowspan="2">capacity of the line</th><th colspan="2">transmission times for packets of</th><th colspan="2">overhead for</th></tr><tr><th>1000 bits</th><th>300 bits</th><th>1000 bits</th><th>300 bits</th></tr></thead><tbody><tr><td>48</td><td>21 ms</td><td>6.2 ms</td><td>16 ms</td><td>16 ms</td></tr><tr><td>19.2</td><td>52 ms</td><td>15.6 ms</td><td>16 ms</td><td>16 ms</td></tr><tr><td>4.8</td><td>208 ms</td><td>62.5 ms</td><td>30 ms</td><td>30 ms</td></tr></tbody></table>

### Table 1

Results of a measurement campaign conducted on the Cyclades network.

<table><caption>Table 2
Symmetrical traffic</caption><thead><tr><th rowspan="2">capacity of the line</th><th rowspan="2">μ₁</th><th colspan="2">1000 bits packets</th><th colspan="2">300 bits packets</th></tr><tr><th>μ₂</th><th>S</th><th>μ₂</th><th>S</th></tr></thead><tbody><tr><td>48</td><td>1</td><td>1</td><td>2.76</td><td>1</td><td>4.6</td></tr><tr><td>19.2</td><td>1</td><td>1</td><td>2.3</td><td>1</td><td>4</td></tr><tr><td>4.8</td><td>1</td><td>1</td><td>2.15</td><td>1</td><td>2.5</td></tr></tbody></table>

<table><caption>Table 3
Dissymmetrical traffic
300 bits on 1 → 2
1000 bits on 2 → 1</caption><thead><tr><th>Capacity of the line</th><th>μ₁</th><th>1/μ₂</th><th>S</th></tr></thead><tbody><tr><td>48</td><td>1</td><td>3.3</td><td>9.2</td></tr><tr><td>19.2</td><td>1</td><td>3.3</td><td>8.6</td></tr><tr><td>4.8</td><td>1</td><td>3.3</td><td>7.1</td></tr></tbody></table>

We have plotted on figure 5 some results concerning the activity of the channel versus the window width. We have represented both analytical and simulation results. Notice that we have simulated the model shown in figure 2. Each curve is obtained with one value of S. This yields the following conclusions :

1) Our simplifying assumptions to solve the model of figure 2 are good since the analytical results are in agreement with the simulation results.

2) The choice of the HDLC window width is good for symmetrical traffics. We obtain activities greater than 90%. But a dissymmetrical traffic associated with high capacity lines (19.2 and 48K bits/sec.) leads to a degradation of performance. A window width of 15 should give quite better results.

On figure 6, we have fixed the window to 7, and S is varying. We have plotted on this curve some points corresponding to the previously given values of line speeds and packet lengths. Here also, the degradation of performance when the traffic becomes dissymmetrical appears.
<figure><img src="image_9.png" /><figcaption>Figure 5 : Activity versus the window width for various mean transmission times</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 6 : Activity versus the mean transmission S for a window width equal to 7</figcaption></figure>

The model presented in this paper points out that available anticipation may happen to get exhausted, thus leading to underuse of the line capacity. An approach is to reduce acknowledgement return delay, thus reducing anticipation needed to compensate it. The field is which is given the number of the last packet to be acknowledged is situated in the header of the frame. However, acknowledgements are really available only when the last bit of the carrying packet is received because the CRC (Cyclic Redundancy Checksum) cannot be checked before that time. This suggest a way to speed up acknowledgement return [6] : acknowledgement octet should be piggy-backed at the end of the packet rather than at the beginning. Then while a packet is

transmitted, received packets can cause its acknowledgement field to be updated until its transmission is completed. It is assumed here that there is "mutual exclusion" between transmission process and update process to access the acknowledgement field. But machine hardware generally takes care of this.

The mathematical model is always this shown in figure 2, but the last box B' no longer exists. We show in figure 7, the improvement obtained in the cases already treated in figure 6.

We see that the improvement is very sensitive, especially for dissymmetrical cases.
<figure><img src="image_11.png" /><figcaption>**Figure 7:** activity versus the mean transmission time for a window width equal to 7 with the improvement.</figcaption></figure>

## 5. RESULTS AND IMPROVEMENTS FOR A SATELLITE CHANNEL

We are interested now by channels, with very high propagation delays. In the case of a geostationary satellite channel the distance is about 72.000 km, which corresponds to a propagation delay of 250 ms. Figure 8 shows throughput measurements as a function of N for two satellite channels of 100 and 200 kbaud. Let us recall that the HDLC protocol can provide in an extented mode, a window width equals to 127. This yields the conclusion that the maximum window width is sufficient to obtain good performance.

Now if we deal with short packets (250 bits) we show in figure 9, the activity on the satellite channel versus the window width. The main conclusion is that the activity reached for a window width of 127 is less than 0.5. More than half of the time the channel is unused. As a conclusion we think that the choice of the HDLC window width is not always optimal.

Activity

<figure><img src="image_12.png" /><figcaption>**Figure 8:** activity of a satellite channel versus the window width.
Mean packet length = 1Kbit.</figcaption></figure>

Several possibilities of improvement can be proposed: either the window width is widened or (and it is what we suggest) the short packets should be assembled in longer packets to obtain a length between 1000 and 2000 bits. If the new mean packet length is 1000 bits, the new activity of the satellite channel is shown in figure 10 for the two cases considered in figure 9.

With this last improvement, the standard satellite mode is sufficient to ensure a "good activity" of the satellite channel until 300 kbits/s. lines, whatever the characteristics of the traffic.

Another possible improvement can be based on the multiplexing of the satellite link into several virtual subchannels on which a simple HDLC protocol is implemented.

With such a protocol the window width is enlarged (above 127) but the maximum number of frames to be retransmitted is only 128 at the maximum.
<figure><img src="image_13.png" /><figcaption>**Figure 9** : Activity on satellite channel versus the window width.
Mean Packet length = 0.25 Kbit.</figcaption></figure>

## 6. MEAN RESPONSE TIME OF HDLC

We try here to evaluate the mean time a packet spends to be transferred via an HDLC protocol, that is, the elapsed time between its instant of arrival into $Q_1$, and the arrival of the corresponding acknowledgement. For that problem, we shall use the model previously shown in figure 3. The notations will be the same as in the previous section. In the sequel we shall assume the input rate $\lambda_1$ is smaller than the maximum throughput obtained in the previous section, so that a steady state exists.

The system being markovian, it is possible to write transition equations. Let $P(n, m)$ represent the probability there are n packets in $Q_1$ and m packets waiting for their acknowledgement.

$$ (\lambda_1 + \mu_1 + m \mu_2) p(n, m) = \lambda'_1 p(n-1, m) + \mu_1 p(n+1, m-1) + (m+1) \mu_2 p(n, m+1), \quad 0 < m < N_1, \quad n \ge 0 $$

$$ (\lambda_1 + m \mu_2) p(0, m) = \mu_1 p(1, m-1) + (m+1) \mu_2 p(0, m+1), \quad 0 < m < N_1 $$

$$ (\lambda_1 + \mu_1) p(n, 0) = \lambda_1 p(n-1, 0) + \mu_2 p(n, 1), \quad n > 0 $$

$$ \lambda_1 p(0, 0) = \mu_2 p(0, 1) $$

$$ (\lambda_1 + N_1 \mu_2) p(n, N_1) = \mu_1 p(n-1, N_1) + \mu_1 p(n+1, N_1-1), \quad n > 0 $$

$$ (\lambda_1 + N_1 \mu_2) p(0, N_1) = \mu_1 p(1, N_1-1) $$

$$ \text{Setting } q_i = p(0, i), \rho = \mu_1/\mu_2 \text{ and } P(i) = \sum_{j=0}^{\infty} p(j, i) \text{ and summing the equations, we obtain:} $$

$$ P(N_1) = P(N_1) $$

$$ P(N_1 - 1) = q_{N_1 - 1} + (N_1/\rho) P(N_1) $$

$$ \vdots \\ N_1 - 1 \\ P(i) = \sum_{j=i}^{N_1-1} \frac{j!}{i! \rho^{j-i}} q_j + \frac{N_1!}{i! \rho^{N_1-i}} P(N_1) \\ \vdots \\ N_1 - 1 \\ P(0) = \sum_{j=0}^{N_1-1} \frac{j!}{\rho^j} q_j + \frac{N_1!}{\rho^j} P(N_1) $$

We can sum these equations to obtain :

$$ \begin{aligned} 1 = & q_0 + q_1 [1 + 1/\rho] + q_2 [1 + 2/\rho + 2/\rho^2] + \dots + \\ & q_j \left[ \frac{j!}{j!(j-1)!} \rho + \frac{j!}{(j-1)! \rho^j} + \dots + \frac{j!}{(j-i)! \rho^i} + \dots + \frac{j!}{\rho^j} \right] + \dots + \\ & + q_{N_1-1} \left[ 1 + \frac{(N_1-1)!}{(N_1-2)! \rho} + \dots + \frac{(N_1-1)!}{\rho^{N_1-1}} \right] + \dots + \\ & + P(N_1) \left[ 1 + \frac{N_1!}{(N_1-1)! \rho} + \dots + \frac{N_1!}{(N_1-i)! \rho^i} + \dots + \frac{N_1!}{\rho^i} \right] \end{aligned} \quad (1) $$

It is also possible to write a trivial equation meaning that the flow which enters $Q_1$ leaves this queue :

$$ \lambda_1 = \mu_1 [1 - P(N_1) - q_0 - q_1 - \dots - q_{N_1-1}] \quad (2) $$

To solve these equations, we need to know all the $q_j$'s, for $0 \le j < N_1$. It is impossible to know these values in practice, but Pujolle and Potier [7] have shown that in such a system, it is possible to get a very accurate approximation assuming that local balances [8] are satisfied at the points (0,0), (0,1),...,(0,$N_1$-1).

The local balance equations lead to :
$$ \lambda_1 q_i = (i + 1) \mu_2 q_{i+1} \quad (3) $$

that gives

$$ q_i = \left[ \frac{\lambda_1}{\mu_2} \right]^i / i! q_0 $$

By replacing the $q_i$'s by their values in (2) and (3), we obtain:

$$ P(N_1) = 1 - \frac{\lambda_1}{\mu_2} - A q_0 \quad (4) $$

$$ P(N_i) = C_i = 1 - B q_0 \quad (5) $$

and thus:

$$ P(N_1) = \frac{1 - r - A/B}{1 - AC/B} \quad (6) $$

with $r = \lambda_1 / \mu_2$

$$ A = 1 + r + \frac{r^2}{2\mu} + \dots + \frac{N_1 - 1}{(N_1 - 1)!} $$

$$ B = 1 + r(1 + \frac{1}{\rho}) + r^2(\frac{1}{2\mu} + \frac{1}{\rho} + \frac{1}{\rho^2}) + \dots $$

$$ + r^{N_1 - 1} \left[ \frac{1}{(N_1 - 1)!} + \frac{1}{(N_1 - 2)! \rho} + \dots + \frac{1}{(N_1 - i)! \rho^{i-1}} + \dots + \frac{1}{\rho^{N_1 - 1}} \right] $$

$$ C = 1 + \frac{N_1!}{(N_1 - 1)! \rho} + \dots + \frac{N_1!}{(N_1 - i)! \rho^i} + \dots + \frac{N_1!}{\rho^{N_1}} $$

Because of the blocking of the system by saturation, it is not easy to evaluate the time spent by a packet in the first server. We have developed in [9] a method, called isolation method, to evaluate this time and thus to replace the first queue by an M/G/1 queue. The study made in [9] leads to replace the server $\mu_1$ by an equivalent server whose characteristics are given in figure 10. The queue is then solved using Pollaczek-Khintchine formula.

<figure><img src="image_14.png" /><figcaption>Figure 10: the equivalent server.</figcaption></figure>

The reader interested by the problem will find in [9] the physical reasons which have conducted to the notion of "equivalent server". We just give here the meaning of the parameters p and q which appear on figure 10.

p represents the probability that a packet finds the system saturated after a first service. It has been shown that p is equal to $P(N_1)$ (the steady state probability that the second queue is full).

So with probability 1-p the packet leaves the first queue and enters one of the services $S_i$ of figure 3. With probability p it starts a new service $\mu_1$ and will find the system still saturated with probability q. The quantity q has been shown to be equal to $\mu_1 / (\mu_1 + M\mu_2)$.

The same behaviour will be repeated as far as the packet finds the system non saturated (with probability 1-q).

In [9] we have also shown how to compute the mean and the squared coefficient of variation of such a server. The results, applied to this special case, give:

$$ \tilde{\mu}^{-1} = \mu_1^{-1} \left[ 1 + \frac{p}{1 - q} \right] $$

$$ \tilde{K}_s = -1 + \frac{\tilde{\mu}^2}{\mu_1^2} \left[ 2 + \frac{2p}{(1-q)^2} + \frac{2}{1-q} \right] $$

where p has to be replaced by the value previously computed $P(N_1)$.

Applying Pollaczek-Khintchine formula to this queue, we can derive the mean number in the queue and the mean response time.

We collect in figures 11 and 12 some analytical results compared with simulations. The curves obtained are parametrized by $S = R + 2/\mu_2$. We have plotted the steady state saturation probability $P(N_1)$ as well as the mean response time.

We can remark that analytical and simulation results are very close. The use of these curves is very easy : as soon as one knows the physical characteristics of the link, one just has to compute S and deduce the corresponding values for each $N_1$.
<figure><img src="image_15.png" /><figcaption>Figure 11: probability of saturation versus the window width.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Figure 12: response time versus the window width.</figcaption></figure>
## 7. ACCURACY AND CONCLUSION

The HDLC protocol called upon to become the basis of a great number of future networks. We think that models such as those we have presented here should be used to calibrate the parameters of communication protocols.

A last question is the accuracy of the results we obtain previously in relation with those of a real network.

Unfortunately, we have no available measurement results obtained on a channel provided with the HDLC protocol. However a measurement campaign has been conducted on the Cyclades network using a node-to-node protocol (MV8) somewhat different of HDLC but with a window width.

The main differences between HDLC and MV8 are the following ones :

- MV8 possesses height virtual channels in parallel which allow a window width equal to 8

- MV8 possesses three distinctive sorts of packets

- short packets, from 0 to 15 octets

- medium packets, from 16 to 127 octets

- long packets from 128 to 255 octets.

Each sort of packets has its proper output queue and at each class is allocated only certain virtual channels.

We show in figure 13, the results of a measurement campaign of a link under the MV8 node-to-node protocol. For the sake of comparison, we indicate the results obtained by the HDLC analytical model when the window width is 8. We give the throughput of the link $1 \to 2$ when the packet is 16 and 128 octets as a function of the length of packets circulating in the sens $2 \to 1$. The line under study is a 19,2 Kb/s. line.

Due to the three categories of packet length in the MV8 protocol, the curves are not regular and there is a jump when packet lengths change of category. Thus we indicate also in figure 12 the throughput obtained with 15 and 127 octets packet length.

On the view of the curves of figure 13 we can conclude that our analysis predicts surely with accuracy the activity of a link submitted to a node-to-node protocol with anticipation.

<figure><img src="image_17.png" /><figcaption>Figure 13: activity of the line A to B versus the text length of the B to A packets.</figcaption></figure>

## REFERENCES

[1] ISO/DIS 4335 High level Data Link Control procedures. Elements of procedures (1977).

[2] ISO/DIS 3309 HDLC, Frame Structure (1976).

[3] E. GELENBE, J. LABETOULLE, G. PUJOLLE "Performance evaluation of the protocol HDLC". Proc. of Computer Network protocols Symposium, Liège, Belgium, 1978.

[4] S.S. LAVENBERG "Stability and maximum departure rate of certain open queueing networks having finite capacity constraints" IBM Research Report RJ 1625, San Jose, California, 1975.

[5] J.W. COHEN "On regenerative processes in queueing theory" Lecture Notes, Springer-Verlag, 1976.

[6] J.L. GRANGE, P. MUSSARD "Performance measurements of line control protocols in the Cigale network" Proc. of Computer Network protocols Symposium, Liège, Belgium, 1978.

[7] G. PUJOLLE, D. POTIER "Réseaux de files d'attente àcapacité limitée avec des applications aux systèmes informatiques" RAIRO Computer Science 13,2,1979.

[8] K. M. CHANDY "The analysis and solutions for general queuing networks" Proc. of the Sixth Annual Princeton University, 1972.

[9] J. LABETOULLE, G. PUJOLLE "Isolation method in a network of queues" to appear in IEEE Trans. on Soft. Eng.