Bnv= 02537 RR207

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

AN ANALYTIC EVALUATION
OF THE PERFORMANCE
OF THE
"SEND AND WAIT" PROTOCOL

Guy FAYOLLE
Erol GELENBE
Guy PUJOLLE

Rapport de Recherche N° 207
Décembre 1976

26p
AN ANALYTIC EVALUATION OF THE PERFORMANCE
OF THE "SEND AND WAIT" PROTOCOL

G. Fayolle*, E. Gelenbe**, G. Pujolle*

RÉSUMÉ

Nous étudions le protocole "send and wait" dans un contexte "hôte-hôte" en vue d'optimiser ses performances. L'analyse que nous présentons permet de choisir la valeur du "time-out" qui maximise le débit du nœud, ou minimise le délai moyen de transit, ou encore qui minimise la probabilité de pertes de paquets par débordement des mémoires tampons du nœud.

ABSTRACT

In this study, we are concerned with a simple error control protocol, the "send and wait" protocol, which use the classical technique of positive acknowledgement and time-out periods. We first analyse the influence of the time-out on the packet transmission rate. Then we use a queueing analysis to obtain the ergodicity condition and to compute the buffer queue length probability distribution. Finally we compute buffer overflow when a finite number of packets are allowed to enter the node. This analysis allows us to obtain optimum values of the time-out in order to maximize throughput, or to minimize average transit delay through the node or buffer overflow probabilities.

<footnote>* IRIA - LABORIA - B.P. 105 - 78150 Le Chesnay (France)</footnote>

<footnote>** Département de mathématiques, Université Paris-Nord, av. J.B. Clément - 93 Villetaneuse (France)</footnote>
# 1. INTRODUCTION.

In heterogeneous computer networks architecture, a hierarchy of three basic levels of protocols seems now to be agreed [1], [2], [3] :

i) user to user (process level).

ii) host to host (transport network level)

iii) nock to nock (telecommunication system level)

This paper rather deals with the "host to host" level the main functions of which are, roughly speaking, the following ones : dynamic establishment of connections between pair of adresses , reassembly of messages, error and flow controls. In [4] flow control is described as "the set of mechanisms whereby a flow of data can be maintened within limits compatible with the amount of available ressources". But, before implementing a mechanism which prevents the network from being overloaded, there is a need to have error control schemes to evaluate their efficiency.

In this study we are concerned with a simple (perhaps the simplest one) error control protocol, the "send and wait" (SW) protocol, which uses the henceforth classical technics of positive acknoledgment and time-out periods (see sections 2). An analytical model (based on queueing theory and diffusion approximations) is presented.

Optimal values of the time-out period are computed and compared for each of three performance measures :

- buffer throughput (maximized)

- response time (minimized)

- loss rate - buffer overflow (minimized)

Numerical experiments are driven in each case.
## 2. THE SEND AND WAIT (SW) PROTOCOL.

The send and wait protocol (often called "Stop and Wait") is one of the simplest schemes designed to insure secure communication between two nodes. It operates as follows. When node A has to transmit a sequence of packets to node B, it stops after each packet transmission to wait for node B to return an acknowledgment (ACK) signifying correct reception. This wait will last at most T time units (the time-out) : after this time if A has not received an ACK it assumes that the packet has not been received correctly and it retransmits the packet once again. This procedure is repeated until an ACK is received before a dealine, and A then transmits the next packet. Figure 1 is an illustration of this protocol. Although it is relatively simple, it is of interest to analyse the SW protocol for three reasons: (i) it can serve as a basis of comparison with other more elaborate protocols, (ii) several features of SW exist in other more elaborate protocols, and (iii) it is used in practice.

In this section we shall first analyse the influence of the time-out T on the packet transmission rate of the buffer. In particular we will derive an expression yielding the *optimum value of the time-out*, which maximizes this transmission rate.

We shall then use a queueing analysis to compute the buffer queue length probability distribution. This will allow us to evaluate the effect of T on important performance measures such as the average packet delay in the output buffer and the overflow probabilities in the case of finite buffer capacity. We shall show that the values of T for optimizing each performance measure must be chosen differently, and obtain analytical results and numerical comparisons for each case.
## 2.1 Optimum Time-out to Maximize Buffer Throughput.

On Fig. 1, is shown the sequence of transmissions from the output buffer with the SW protocol whose behaviour is described above. We shall need some assumptions in order to carry out our analysis :

(a) the time duration of transmission of a packet from the buffer is a random variable X with general probability distribution function $G(x) \triangleq \text{Pr} [X \le x]$; this duration is independent and identically distributed for all the packets,

(b) with probability L a packet will not be acknowledged (L is the probability of packet loss or of erroneous transmission, etc.),

(c) for a packet which will be acknowledged, the time delay separating the end of transmission of the packet and the receipt of the ACK at the transmitting node is a random variable Y (independent from one transmission to the other) of general probability distribution function $B(x) \triangleq \text{Pr} [Y \le x]$.

Let Z be the random variable denoting the time during which the SW protocol would wait for an ACK if a time-out did not exist (i.e. $T=\infty$). Then

$$ (1) \quad Z = \begin{cases} \infty & \text{with probability L} \\ B(x) & \text{with probability } (1-L) \end{cases} $$

Let us define

$$ (2) \quad A(x) \triangleq \text{Pr} [Z \le x] = \begin{cases} B(x)(1-L) & \text{for } x < \infty \\ 1 & \text{for } x = \infty \end{cases} $$

The probability that an ACK is not received before the time-out occurs, and that the current transmission has to be repeated, is

$$ (3) \quad D \triangleq 1-\text{A}(T) = 1 - B(T) (1-L) $$
We can conclude that, with probability $D^{n-1}(1-D)$, the transmission of a packet will be repeated n times until an ACK is received before a time-out. Let $\tau_n$ be the total transmission delay (including all the "send" and "wait" intervals) for a packet, given that it has to be transmitted n times before the ACK precedes the time-out. Then<fnref n="1" />)

$$ (4) \quad E(\tau_n) = n E[X] + (n-1)T + \int_0^T \frac{tdA(t)}{(1-D)} $$

The expected value of the total transmission delay $E(\tau)$ is then

$$ (5) \quad E[\tau] = \sum_{n=1}^{\infty} E(\tau_n) D^{n-1}(1-D) = \frac{E[X] + DT + \int_{0}^{T} tdA(t)}{(1-D)} $$

It is of interest to determine the value of T, call it $T_1$, which will minimize the average time $E(\tau)$ separating the instant at which a given packet's transmission begins and the instant at which it is correctly acknowledged.

Differenciating (5) we must have at $T = T_1$:

$$ \frac{d}{dT} E[\tau] = 0, \quad \frac{d^2}{dT^2} E[\tau] > 0, $$

This implies :

$$ (6) \quad \left. \frac{dA}{dx} \right|_{x=T_1} = \frac{A(T_1)(1-A(T_1))}{E[X] + T_1 - \int_0^T A(t)dt} $$

Therefore if we wish to minimize the effective transmission delay of a packet we should set $T$ to the value $T_1$ solution of (6).

<footnote n="1">¹) $E[\tau]$ will denote the expected value of the random variable.</footnote>
On fig. 2 is shown $1/E[τ]$ as a function of T for various probability distribution functions A(x).

Another view of the time-out's role might emphasize its function of "deciding" whether a packet is lost or not; i.e if an ACK does not arrive by time, T then it is "safe" to assume that it is lost. In this context we should choose T so as to minimize the probability that the ACK will arrive in some time T + ε given that it has not arrived in time T, i.e the probability of a false alarm, where ε is some acceptable delay. We wish to minimize

$$ 
\begin{aligned}
& \mathrm{Pr} \left[ Y \le T + \varepsilon \mid Y > T \right] \\
& = (A(T + \varepsilon) - A(T)) / (1 - A(T))
\end{aligned}
$$

This will be achieved at $T = T_2$ for which

$$ (7) \quad \frac{dA}{dT} \Big|_{T=T_2+\varepsilon} \cdot (1-A(T_2)) = \frac{dA}{dT} \Big|_{T=T_2} \cdot (1-A(T_2+\varepsilon)) $$

## 2.2 Distribution of effective transmission time in presence of the SW protocol

We have seen in Section 2.2 that in presence of SW protocol the effective transmission time of a packet from the buffer is modified due to the wait for an acknowledgement and the time-out mechanism. The distribution of the effective transmission time has an important influence on performance measures associated with the buffer; that is why we propose to give an explicit expression for this distribution. In Section 2.4 we shall discuss the effect this distribution has on buffer behaviour. Let V be the total effective time; note that in 2.1 we have computed $E(τ)=E[V]$ its average value. Let $F(x) \triangleq \mathrm{Pr}[V \le x]$; the Laplace transform of the density will be

$$ (8) \quad f^*(s) = \int_{0}^{\infty} e^{-sx} dF(x) $$
and we have (see also (4), (5))

$$ (9) \quad f*(s) = \sum_{n=1}^{\infty} D^{n-1}(1-D) g*(sn) e^{-s(n-1)T} \frac{a_T^*(s)}{(1-D)} $$

where

$$ g*(s) = \int_{0}^{\infty} e^{-sx} dG(x) $$

is the Laplace transform of the density of packet transmission time,

$$ a_T^*(s) = \int_{0}^{T} e^{-sx} dA(x) $$

and

$$ e^{-sT} = \int_{0}^{\infty} e^{-sx} \delta(x-T) dx $$

where $\delta(x)$ is the Dirac delta function. In (9) we are simply using the fact that if a packet is acknowledged after n transmissions [which will occur with probability $D^{n-1}(1-D)$] then the effective transmission time is simply n times $X$ plus $(n-1)$ times $T$, plus the wait time. Notice that

$$ \mathrm{Pr} [nX \le x] = \mathrm{Pr}[X \le x/n] = G(x/n) $$

so that the Laplace transform of the density of nx is

$$ \begin{aligned} \int_{0}^{\infty} e^{-sx} d \mathrm{Pr}[nX \le x] &= \int_{0}^{\infty} e^{-sn \cdot x/n} dG(x/n) \\ &= \int_{0}^{\infty} e^{-sny} dG(y) = g*(sn) \end{aligned} $$

which has been used in (9) : i.e. since the *same* packet is being retransmitted n times we cannot assume that the corresponding n transmission times are independent (they are in fact identical).

If the analysis being carried out involves a more general (e.g. host to host) transmission than a node to node transmission between neighbouring nodes, it may be reasonable to assume that, due to fluctuations in the
conditions of the network, the times for successive retransmissions are indeed independent and possibly non-identically distributed. This can also be the case if, after each time-out, the sender chooses a new route for its retransmission. Such a situation would exist if the sender concludes that the lack of an acknowledgement is the result of line failure or of excessive congestion. In the case of independent and identically distributed retransmission times of the same packet, the Laplace transform of the density function of total effective transmission time becomes :

$$ (g') \quad \hat{f}^*(s) = \sum_{n=1}^{\infty} D^{n-1}(1-D)[g^*(s)]^n e^{-s(n-1)T} a_T^*(s)/(1-D) $$

which is different from (9).

## 2.3 Analysis of the buffer queue with the SW protocol : the infinite buffer case.

In this section we shall analyse the buffer queue under the same assumptions as those of Section 2.2. In addition we assume that packets arrive to the buffer according to a Poisson process of rate $\lambda$, and that buffer capacity is infinite. In Section 2.4 the case of finite buffer capacity will be examined.

We must distinguish two cases :

- The case where a packet retransmission after a time-out occurs along a channel in which the statistical conditions are different from those during the previous transmission, or when a new route is used for each retransmission. This case is of interest for host to host protocols, or in protocols governing transmissions spanning several nodes. Its analysis is presented in (i)

- The case where the retransmission time of a packet is strictly identical during each successive retransmission. This case, analysed in (ii) is of interest for protocols concerning neighbouring nodes.
### i) The case of independent retransmissions

In this section we analyze the buffer assuming that retransmission times for the same packet are independent and identically distributed. The assumption is of interest in the case of host to host protocols; it is reasonable to assume that conditions in the channel will be independent from one transmission to the other due to global traffic fluctuations. It may be assumed that retransmission times are identically distributed if global traffic rates are identical on the channel, as is the case if some stationary state has been achieved.

Let {$N_t, t \ge 0$} be the stochastic process representing the number of packets in queue in the buffer including the one being transmitted and for $n \ge 0$, $t \ge 0$, let $p(n,t)=\text{Pr}[N_t=n]$. An analysis of this stochastic process will be carried out using the imbedded Markov chain (IMG) method. Consider the buffer queue at the instants $t_1 < t_2 < \dots < t_k < \dots$, when either (i) an acknowledgement is received and a packet is removed from the queue, or (ii) a deadline occurs and the packet which was transmitted last is transmitted once more because an acknowledgement has not yet been received. Let

$\hat{\Pi}_k(n) \triangleq p(n, t_k^+)^*$; we first write the equations which are satisfied by the $\hat{\Pi}_k(n)$, $k=1,2,\dots,n=0,1,\dots$. These are, for $n=0,1,\dots$

$$ (11) \quad \hat{\Pi}_{k+1}(n) = \sum_{j=0}^{n} \int_{0}^{T} \hat{\Pi}_{k}(n+1-j) v_{j}(t) \, dA(t) \\ \qquad + \int_{0}^{T} \hat{\Pi}_{k}(0) v_{n}(t) \, dA(t) + \sum_{j=0}^{n} \hat{\Pi}_{k}(n-j)(1-A(T)) v_{j}(T) $$

where

$$ (12) \quad v_j(t) = \sum_{k=0}^{j} g_k e^{-\lambda_k t} \frac{\lambda_k}{(j-k)!} \quad , \quad j \ge 0 $$

<footnote>* $t_k^+$ denotes the instant just after $t_k$</footnote>
and

$$ (13) \quad g_k = \int_0^\infty dG(t) \frac{(\lambda t)^k}{k!} e^{-\lambda t}, \quad k \ge 0 $$

Notice that $g_k$ is the probability of k packet arrivals to the output buffer during an epoch of transmission of a packet from the node. Furthermore, $v_j(t)$ is the probability of j packet arrivals to the buffer during a service epoch plus an interval of length $t$. Equation (11) can now be explained. The first and second term on the right-hand side concern cases when an acknowledgement is received before the deadline; the first term denotes a transition from n+1-j packets in queue at $t_k^+$ to n at $t_{k+1}^+$, implying that j arrivals have occured in $]t_k^+, t_{k+1}^+]$ and one departure (since we are dealing with a case where an acknowledgement is received before the deadline. In the second term the number in queue at $t_k^+$ is 0: therefore an arrival (which compensates for the removal from the queue which has occured at $t_{k+1}^+$) must have occured before the transmission and the subsequent wait epoch (which terminates before the deadline) takes place. The third and last terms in (11) concern the case when no acknowledgement is received before the deadline : $(1-A(T))$ is the probability of this event ; the passage from state (n-j) at $t_k^+$ to state n at $t_{k+1}^+$ is due to j arrivals which occur with probability $N_j(T)$.

Now define the generating functions

$$ (14) \quad \hat{P}(x) = \sum_{n=0}^{\infty} \hat{\Pi}(n) x^n, \quad \hat{V}(x;t) = \sum_{j=0}^{\infty} v_j(t) x^j, \quad |x| \le 1 $$

where we have dropped the dependence on k. Clearly the stochastic process $\{N_{t_k}, k=1,2,\dots\}$ is a Markov chain and it is easily established that it is aperiodic and irreducible [6]. Denote by $\hat{\Pi}(n)$ the stationary probability distribution

$$ \hat{\Pi}(n) = \lim_{k \to \infty} \hat{\Pi}_k(n) $$

if it exists. For its existence, it suffices that it be a solution of (11) with

$$ (15) \quad \sum_0^\infty \hat{\Pi}(n) = 1, \quad \Pi(n) > 0 \quad \text{for } n=0,1,\dots $$
From (11) we obtain

$$ (16) \quad \hat{P}(x) = \frac{1}{x} \left[ \hat{P}(x) - \hat{\Pi}(0) \right] \int_{0}^{T} V(x,t) \, dA(t) + \hat{\Pi}(0) \int_{0}^{T} V(x,t) \, dA(t) + P(x) V(x,T) [1 - A(T)] $$

$$ (17) \quad \hat{P}(x) = \frac{(1-1/x) \hat{\Pi}(0) \int_{0}^{T} V(x,t) \, dA(t)}{1 - \left[V(x,T)D + \frac{1}{x} \int_{0}^{T} V(x,t) \, dA(t)\right]} $$

where $D \neq 1 - A(T)$ is the probability that an ACK will **not** be received before the deadline.

Notice that $\lim_{x \to 1} P(x)$ is an indeterminate form. After applying

1'Hôpital's rule we obtain

$$ (18) \quad \hat{P}(1) = \frac{\hat{\Pi}(0) (1-D)}{\lambda \left[ E[X] + DT + \int_{0}^{T} tdA(t) \right] - (1-D)} $$

where we have used

$$ V(1,t) = 1, \text{ and } \lim_{x \to 1} \frac{d}{dx} V(x,t) = \lambda(t+E[X]) $$

Using $P(1) = 1$, we obtain

$$ (19) \quad \hat{\Pi}(0) = 1 - \lambda \left[ E[X] + TD + \int_{0}^{T} tdA(t) \right] / (1-D) $$

Clearly then the equilibrium probabilities solution of (11), satisfying (15) exist only if $\hat{\Pi}(0) > 0$, i.e. if

$$ (20) \quad \lambda < (1-D) / [E[X] + TD + \int_{0}^{T} tdA(t)] $$
The above relationship is the stability condition for the node operating with the SW protocol.

$$ \text{Let } E(\hat{\tau}) \text{ be } [E[X] + \text{TD} + \int_{0}^{T} \text{tdA}(t)]/(1-D). $$

Substituting (19) in (17) we obtain $P(x)$ the generating function for the stationary probability of buffer queue length at the instants $\{t_k^+, k \ge 1, \dots\}$:

$$ (21) \quad \hat{P}(x) = \frac{(x-1) \hat{\Pi}(0) \int_{0}^{T} e^{-\lambda t(1-x)} G^*(\lambda t(1-x)) dA(t)}{x - [x \hat{D} e^{-\lambda T(1-x)} G^*(\lambda T(1-x)) + \int_{0}^{T} e^{-\lambda t(1-x)} G^*(\lambda t(1-x)) dA(t)]} $$

The buffer queue length can also be analyzed at instants of effective removal of a packet from the queue. The system analyzed is then simply the classical M/G/1 queue [5] and the generating function for the stationary probability distribution of queue length is

$$ \hat{P}_1(x) = \frac{(x-1)\hat{\Pi}(0) \hat{f}*(\lambda(x-1))}{x - \hat{f}*(\lambda(x-1))} $$

the average queue length in stationary state being

$$ (22) \quad \hat{M} = \lambda E[\hat{\tau}] + \frac{(\lambda E[\hat{\tau}])^2 [1 + \lambda^2 \text{Var}(\hat{\tau})]}{2(1 - \lambda E[\hat{\tau}])} $$

and the average response time $\hat{R}$ is available from Little's formula $\hat{R} = \hat{M}/\lambda$, where

$$ (23) \quad \text{Var}(\hat{\tau}) = \text{Var}(X)/(1-D) + \gamma $$

and

$$ (24) \quad \gamma = \int_{0}^{T} t^2 dA(t)/(1-D) + \left[ \int_{0}^{T} \text{tdA}(t)/(1-D) \right]^2 $$

### (ii) The case of identical retransmission times.

If we assume that precisely the same channel conditions prevail from one transmission to the other, as is the case for node to node communication between adjacent nodes of a network, it is no longer possible
to consider that successive retransmission times for the same packet are independent. However we can apply standard the analysis techniques of the M/G/1 queue [5] if we consider that the "service" time of the buffer is the total time necessary for effectively transmitting a packet, including all successive retransmission times and waiting periods. The Laplace transform of the probability density function of this equivalent service time is given in (9), its expected value is $E[\tau]$ in (5), and its variance can be computed from (9):

$$ (25) \quad \mathrm{Var}(\tau) = \frac{1+D}{(1-D)} \mathrm{Var}(X) + \gamma $$

where $\mathrm{Var}(X)$ is the variance of the transmission time of a packet, and $\gamma$ is given by (24).

If $\{\hat{N}_t, t \ge 0\}$ is the stochastic process representing buffer queue length and

$\Pi(k) \stackrel{\Delta}{=} \lim_{t \to \infty} \mathrm{Pr} [N_t=k]$, $k=0,1,\dots$, we use classical results

for the M/G/1 queue to obtain the generating function [5]:

$$ \begin{align} (26) \quad P(x) &\stackrel{\Delta}{=} \sum_{k=0}^{\infty} \Pi(k)x^k \\ &= \frac{\Pi(0)(x-1)f*(\lambda(x-1))}{x - f*(\lambda(x-1))} \end{align} $$

The stationary queue length distribution exists if

$$ (27) \quad \lambda < (1-D)/[E[X] + TD + \int_{0}^{T} tdA(t)] $$

which is the same condition as (20). The average queue length is

$$ (28) \quad M = \lambda E[\tau] + \frac{(\lambda E[\tau])^2 [1 + \lambda^2 \mathrm{Var}(\tau)]}{2(1 - \lambda E[\tau])} $$

and the average response time is obtained using Little's formula

$$ (29) \quad R = E[\tau] + \frac{\lambda(E[\tau])^2 [1 + \lambda^2 \mathrm{Var}(\tau)]}{2(1 - \lambda E[\tau])} $$
Notice that $E[\hat{\tau}] = E[\hat{\tau}]$ : then the difference between $\hat{R}$ and $\hat{R}$ is due to the fact that $Var(\hat{\tau}) \neq Var(\hat{\tau})$. In particular :

$$ (30) \quad \hat{R} - \hat{R} = \frac{D}{1-D} \frac{[\lambda E(\tau)]^2 \mathrm{Var}(X)}{2\lambda(1-\lambda E[\tau])} $$

This leads to an interesting and useful remark.

**Remark :**

Consider a host to host transmission which can use several alternate routes. Suppose that successive transmissions of a given packet along one route will lead to exactly identical transmission delays. Suppose also that delays on alternate routes have the same distribution, but are independent. It is nevertheless preferable to *change* route for each retransmission of the same packet.

### (iii) Time-out optimization to minimize average response time

The results of Sections 2.3 (i) and (ii), and in particular equations (22) and (28) allow us to examine the choice of the time-out $T$ in order to minimize average queue lengths (or equivalently average response times) at a node.

Define :

$$ (31) \quad \begin{aligned} \rho &\triangleq \lambda E[\hat{\tau}] = \lambda E[\tau] , & \hat{K} &\triangleq \lambda^2 \mathrm{Var}(\hat{\tau}) \\ K &\triangleq \lambda^2 \mathrm{Var}(\tau), & \hat{K}' &\triangleq \frac{d\hat{K}}{dT} , & \rho' &\triangleq \frac{d\rho}{dT} , & K' &\triangleq \frac{dK}{dT} \end{aligned} $$

Then from (22), (28) :

$$ \hat{M} = \rho + \rho^2 \frac{1+K}{2(1-\rho)} , \quad M = \rho + \rho^2 \frac{1+K}{2(1-\rho)} $$

We readily see that $\hat{M}$ is minimized by setting $T=T_2$ such that
$$ (32) \quad \hat{K}'|_{T=T_2} = \rho' \left[ \frac{2(1-\rho)}{\rho^2} + \frac{1+K(2-\rho)}{\rho(1-\rho)} \right] $$

and M is minimized by setting $T=T_3$ such that

$$ (33) \quad K'|_{T=T_3} = \rho' \left[ \frac{2(1-\rho)}{\rho^2} + \frac{1+K(2-\rho)}{\rho(1-\rho)} \right] $$

Notice that $\rho' = 0$ at $T=T_1$, so that

$$ \frac{d\hat{M}}{dT}|_{T=T_1} > 0, \quad \frac{dM}{dT}|_{T=T_1} > 0 $$

and $T_2 < T_1$, $T_3 < T_1$. Therefore the time-out chosen for minimizing response time is smaller than that for maximizing throughput.

## 2.4 Finite buffer capacity.

In this section we shall analyse the buffer overflow under the same assumptions as these of section 2.3 except for buffer capacity which is finite. A maximum of N packets is allowed in the node. If the node is full, an arriving customer is rejected.

In this section we treat both the cases of independent and identical retransmissions. $Var(\hat{\tau})$ would be replaced by $Var(\hat{\tau})$ to obtain the second case ($E(\hat{\tau}) = E(\hat{\tau})$).

When we have a stationary probability distribution for queue length it is easy to pass from the M/G/1 case to the M/G/1/N case, by the following system [7]. Let $\hat{M}_N(n)$ be the stationary probability distribution with a buffer capacity of N.

$$ (34) \quad \hat{M}_N(n) = \begin{cases} K_N \hat{\Pi}(n) & \text{if } 0 \le n < N \\ 1 - \left[1 - K_N(1-\rho)\right]/\rho & \text{if } n = N \end{cases} $$

$$ (35) \quad \text{and } K_N = \frac{1}{N-1} \sum_{n=0}^{N-1} \hat{\Pi}(n) $$
In our case the difficulty is to find $\hat{\Pi}(n)$ because the generating function for the stationary probability of buffer queue length is complicated (21). To avoid this difficulty we are going to use the approximation by a diffusion process [8]. Let $m=\hat{\Pi}(0)$ and $f(x)$ the continuous stationary probability distribution obtained by diffusion [8]:

$$ (36) \quad f(x) = \begin{cases} \frac{m\lambda}{\beta} [e^{\gamma x} - 1] & 0 \le x \le 1 \\ \frac{m\lambda}{\beta} [1 - e^{-\gamma}] e^{\gamma x} & x \ge 1 \end{cases} $$

$$ \text{with } \gamma=2\beta/\alpha \quad \beta=\gamma-\mu \quad \alpha=\lambda+K_s \mu \quad \rho=\lambda/\mu $$

$$ \text{where } \mu = 1/E(\tau) \quad \text{and} \quad K_s = \frac{\text{Var}(\tau)}{[E(\tau)]^2}. $$

Now we can apply the formulas (34) and (35):

$$ S = \sum_{n=0}^{N-1} \hat{\Pi}(n) = m + \int_{0}^{N-1} f(x) dx $$

$$ (37) \quad S = m - \frac{\lambda m}{\beta} \left[ 1 + \frac{1}{\gamma} (1 - e^{\gamma}) \right] + \frac{\lambda m}{\beta \gamma} (1 - e^{-\gamma}) \left[ e^{\gamma(N-1)} - e^{\gamma} \right] \\ K_N = \frac{1}{1 - \rho [1 - S]} $$

and the buffer overflow is given by $\hat{\Pi}_N(N)$:

$$ (38) \quad \hat{\Pi}_N(N) = 1 - \frac{1}{\rho} \left[ 1 - \frac{1-\rho}{1-\rho[1-S]} \right] \quad S \text{ is given by (37).} $$

$\hat{\Pi}_N(N)$ is a function of T. The time $T_4$ which minimizes $\hat{\Pi}_N(N)$ is obtained for

$$ \frac{\partial \hat{\Pi}_N^{(N)}}{\partial T} \Big|_{T=T_4} = 0 \quad \text{and} \quad \frac{\partial^2 \hat{\Pi}_N^{(N)}}{\partial T^2} \Big|_{T=T_4} > 0 $$

On Fig. 3 is shown $\hat{\Pi}_N^{(N)}$, the buffer overflow as a function of T for various probability distribution functions $A(x)$.
## CONCLUSION

In the preceding model, we obtained different optimal values for the "time-out" period, depending on the considered performance measures : throughput, delay, loss rate.

Although the SW protocol is not among the most elaborate ones, a considerable investigation remains to be done, especially in what concerns the mixing of "time-out"and "flow control" mechanisms in a several-hosts model.
REFERENCES

[1] METCALFE, R.M., "Packet communication" M.I.T. Project, MAC Report TR 114
December 1973 (Ph.D. Thesis) Harvard University.

[2] LE LANN, G. ; LE GOFF, H. "Advances in performance evaluation of communication protocols", Proceedings of ICCC 76, 361-366, August 1976.

[3] ZIMMERMANN, H. "High level protocols standardization : technical and political issues", Proceedings of ICCC 76, 373-375, August 76.

[4] POUZIN, L. "Flow control in data networks:methods and tools", Proceedings of ICCC 76, 467-474, August 1976.

[5] KLEINROCK, L. , "Queueing system, Vol I : Theory", Wiley Intersuenie, 1975.

[6] CINLAR, E. "Markov processes" John Wiley and Son, 1975.

[7] REISER, M. ; KOBAYASHI, H. "The effects of service time distributions on systems performance", Proceedings of IFIP 74, 230-234, 1974.

[3] GELENBE, E. "On approximate computer models" J-ACM 21, 316-328, 1975.

[9] CERF, V. ; KAHN, R. "A protocol for packet network intercommunication"
*IEEE Trans. on Com.*, 22, May 1974.

[10] DANTHINE, A. ; BREMER, J. , "Definition, représentation et simulation de protocoles dans un contexte réseaux" - Proceedings of A.I.M., Liège 1975.
<figure><img src="image_2.png" /><figcaption>Figure 1a</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 1b</figcaption></figure>
FAJOLLE
GELENBE
PUJOLLE

2

Maximal rate of
interarrival

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

Maximal rate of interarrival as a function of
time-out T for various probability distribution
function A(x).

G(x) is exponential distribution with a rate 10:

The expected value of A(x) is 1.

Maximal rate of
interarrival

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

Maximal rate of interarrival as a function of time-out T
for various probability distribution function A(x)

G(x) is exponential distribution with a rate 10.

The expected value of A(x) is 1.
Buffer overflow

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

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

Buffer overflow $\hat{\Pi}_N(N)$ when $N=4$.

$G(x)$ is the exponential distribution with a rate 10.

The expected value of $A(x)$ is 1.

Packets arrive with a Poisson process of rate $\lambda = 0.75$

Buffer overflow $\hat{\Pi}_N(N)$ when $N=y$

$G(x)$ is the exponential distribution with a rate 1

The expected value of $A(x) = 1$

packets arrive with a Poisson process of rate $\lambda = 0.75$
Maximal rate of
interarrival

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

Maximal rate of interarrival as a function of time-out $T$ for various probability distribution function $A(x)$.

$G(x)$ is exponential distribution with a rate 10: The expected value of $A(x)$ is 1.
Maximal rate of interarrival as a function of time-out T for various probability distribution function A(x) G(x) is exponential distribution with a rate 10. The expected value of A(x) is 1.

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

Buffer overflow $\hat{\Pi}_N(N)$ when $N=4$.
$G(x)$ is the exponential distribution with a rate 10.
The expected value of $A(x)$ is 1.
Packets arrive with a Poisson process of rate $\lambda = 0.75$
<figure><img src="image_11.png" /><figcaption>Figure 3b</figcaption></figure>

Buffer overflow $\hat{\Pi}_N(N)$ when $N=y$

$G(x)$ is the exponential distribution with a rate 1

The expected value of $A(x) = 1$

packets arrive with a Poisson process of rate $\lambda = 0.75$