IRIA
laboria

laboratoire de recherche
en informatique
et automatique

MODELS OF
TANDEM NETWORKS OF QUEUES
MOTIVATED BY
PACKET SWITCHING

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

Marek I. IRLAND, Guy PUJOLLE

Rapport de Recherche N° 256

Octobre 1977

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20
MODELS OF TANDEM NETWORKS OF QUEUES
MOTIVATED BY PACKET SWITCHING

Marek I. Irland*, Guy Pujolle**

Résumé :

Dans les réseaux d'ordinateurs utilisant la technique de la commutation de paquets, les nœuds possèdent des tampons de taille finie. Deux stratégies sont étudiées dans ce papier lorsqu'un débordement de capacité se produit :

- retransmission d'une copie à partir du nœud précédent,

- retransmission d'une copie à partir de l'hôte origine.

Un réseau de files d'attente en tandem est utilisé pour modéliser un chemin particulier (source-destination). Ce modèle permet la comparaison des deux stratégies. On montre que les temps de réponse moyens sont pratiquement identiques dans les deux cas, et que de petites capacités de mémorisation sont suffisantes pour bien approcher le temps de réponse minimum.

Abstract :

In packet-switched communications networks, store-and-forward switches have finite waiting room. Two strategies, switch-retransmission and host-retransmission, are studied in this paper for dealing with packets rejected because of switch overflow. In the switch-retransmission method a packet rejected at one switch will be retransmitted from a backup copy held at the preceding switch, in host-retransmission a lost packet is retransmitted by its origin host. Tandem queueing networks are used to model a single source-destination communications path and to compare the two retransmission strategies. It is found that the mean total delay is similar for both strategies and a small amount of waiting room is sufficient for near minimum delay performance.

* Computer Communications Networks Group, University of Waterloo, Waterloo, Ontario (Canada)

**Institut de Recherche d'Informatique et d'Automatique, LABORIA, Rocquencourt - 78150 Le Chesnay (France)
# 1. Introduction

A packet-switched communications network consists of packet switches interconnected by transmission links. Besides providing the switching function, packet switches connect subscribers (host computers) to the network. Subscriber messages are broken into packets, typically up to 255 characters long, and transmitted packet by packet between switches until the destination subscriber is reached. Of course, each packet has to carry information about its destination in the header. Buffering techniques are employed to hold packets which may have to queue in a switch until forwarded to the next switch or the destination subscriber.

Packet-switched networks have usually been modelled as networks of queues, assuming infinite waiting room, and consequently no traffic loss [5]. On the other hand, real packet switches have finite waiting room, typically sufficient for about twenty packets. Thus, buffer overflow is possible, particularly under heavy traffic. In [4] Irland studied buffer management methods in a switch to minimize the probability of overflow. In the present paper our objective is to investigate strategies for dealing with packets rejected because of overflow.

The most common technique, here called *switch-retransmission*, is used in the ARPA Network, in which, if a packet cannot be accepted by a switch, it is retransmitted
from a backup copy held in the preceding switch [6].
Another technique which we call *host-retransmission* is used
in the CYCLADES Network [12]. Here the network drops a
packet which arrives at a full switch, to be resent later by
the source subscriber. It has often been assumed that the
switch-retransmission method is obviously the superior one.
Our analysis will show that, at least from one point of
view, this assumption is unfounded.

For the sake of simplicity we will consider a single
source-destination path, with no interfering traffic, which
can be modelled as a tandem network of queues. In Section 2
several earlier models of tandem queueing networks are
reviewed. In Section 3 our models are formulated; they are
analysed in Sections 4 and 5, with numerical examples given
in Section 6.

## 2. Earlier Work on Tandem Networks with Blocking

An early study of tandem networks of queues, with finite
waiting room between servers, was published by Hunt [3].
Poisson arrivals and exponential service times were assumed.
The problem considered was one in which a sequence of ser-
vice operations must be performed on "customers". Hence, as
in other work motivated by operational research applica-
tions, it was assumed that when a customer has completed
service in one station but cannot proceed because the next
station's queue is full, the server in the first station
becomes *blocked* until its customer can proceed. An analytic
solution and some numerical results were obtained for a two-station system, and partially for a three-station system. Konheim and Reiser [7] provided a new analysis of the two-station tandem network with blocking, also under the exponential service time assumption. The solution was in terms of a computational algorithm.

Avi-Itzhak [1] analysed the tandem queueing network with blocking where the service times are constant, although possibly different, in each station. Delay distributions and other characteristics of such queueing processes were obtained for an arbitrary number of stations. It turns out that in this system the order of stations and the amount of storage in queues other than the first one have no influence on the delay. In fact, the delay of any customer equals the sum of: 1) the time the same customer would have spent in a single-station system with a constant service time taken to be the longest service time in the original tandem system, and 2) the total of the remaining service times. Similar results, from the point of view of packet-switched communications networks, were used by Rubin [13]. Labetoulle and Pujolle [8] provided some extensions.

Neuts [10] studied tandem blocking networks under more general service time distributions than exponential or constant. The results for the two-station case were obtained in terms of functional equations only, though the stability conditions for the system were found.
It appears that the main difficulty in analysing tandem blocking systems is that blocking induces explicit dependence between the effective service time (service plus blocked time) in one station and the state of the queue in the next. Hence, the system cannot be easily decomposed.

Kleinrock [5] modelled a communications path by a tandem queuing network with infinite waiting room and exponential service times which represent packet transmissions over links. In a real packet-switched network each packet maintains its length as it travels from switch to switch. This implies that transmission times of the same packet over different links are proportional; thus, service times are not independent. The solution for stable state probability distribution is not known under these circumstances. Instead, a simplifying assumption was made by which a new packet length is chosen from an exponential distribution in each station. With this so-called independence assumption each station in the network behaves as if it were an independent M/M/1 system and the stable state distribution has a simple product form.

We will also model a communications path by a tandem network with exponential service times, but with finite waiting room. Unlike in the blocking networks discussed at the beginning of this section, our "customers" are destructible packets which can be retransmitted. Kleinrock's independence assumption will be used to make network decomposition possible.
## 3. Tandem Networks with Retransmission

We consider two models, switch-retransmission and host-retransmission, as shown in Figures 1 and 2. For both models we make the following assumptions.

- External arrivals occur only at the initial station, $\theta$, which represents the host computer; they obey a Poisson process with mean rate $\lambda$.

- Packet length is an exponential random variable. The transmission or retransmission time of a packet is proportional to its length; hence the service time for link $n$ is an exponential random variable with mean $1/p_n$.

- For the purpose of analysis, Kleinrock's independence assumption is in effect.

- While station 0 has infinite waiting room, each remaining station, $n>0$, can queue up to $p_n$ packets.

- A packet which arrives at a full station is refused. The probability of packet refusal at station $n>0$ is denoted by $p_n$. The destination subscriber never refuses a packet; we define $p_{n+1}=0$.

The difference between the two systems is that a refused packet will be retransmitted from the preceding station in the first system, and from the initial station in the second.

We will also assume that the stable state probability distributions exist for both models. (The equilibrium conditions can be found in [11].)
### 4. Analysis of the Switch-Retransmission Model

Consider a single station $n>0$ in Figure 1. For the purpose of approximate analysis assume that at station $n+1$ a packet is refused randomly with probability $p_{n+1}$. We will replace our station, with its retransmission loop, by a simple queue with service time which represents the total time of the first transmission and all retransmissions of the same packet. With probability $1-p_{n+1}$ this new service time will follow an exponential distribution, with probability $(1-p_{n+1})p_{n+1}$ it will follow an Erlang-2 distribution, etc. In general, with probability $(1-p_{n+1})p_{n+1}^i$ an Erlang-$i+1$ distribution will be followed because the packet will be retransmitted $i$ times after its first transmission. Hence the new service time is also an exponential random variable, with mean $1/\nu_n$ where $\nu_n = (1-p_{n+1})p_n$.

To compute the mean arrival rate, $\lambda_n$, at station $n$ we must include all transmissions and retransmissions from station $n-1$; hence $\lambda_n = \lambda/(1-p_n)$. We will make a simplifying assumption that these arrivals form a Poisson process. In fact, it is possible to prove that the interarrival times at station $n$ are exponentially distributed if $p_{n+1}=p_n$, under a sufficient condition of Gelenbe and Muntz [2]. If all stations are identical, $p_{n-1}$ and $p_n$ may be considered approximately equal. Moreover, if there had been an infinite number of queues in tandem, the equality would have been exact. The approximation deteriorates as the server speeds
or the queuing capacities diverge. In this paper we
presume that all stations $n>0$ are similar.

To summarize, each station $n>0$ is treated as an M/M/1/K system with service rate $v_n$ and arrival rate $\lambda_n$. Hence the stable state probability that k packets are queued in station n, including any packet in service, is

$$P_n(k) = \rho_n^k \frac{1-\rho_n}{1-\rho_n^{M_n+1}} \quad \text{where} \quad \rho_n = \lambda_n / v_n$$

The probability that a packet is refused at this station is

$$\rho_n = \rho_n(M_n) = \rho_n^{M_n} \frac{1-\rho_n}{1-\rho_n^{M_n+1}}$$

Therefore, the behaviour of station n is defined by the following system of equations, with two unknown variables $\lambda_n$ and $\rho_n$: $\lambda_0=\lambda$, $\rho_0=0$, and for $n=1,...,N$,

$$\lambda_n = \lambda / (1 - \rho_n)$$

$$\rho_n = \left(\frac{\lambda_n}{v_n}\right)^{M_n} \frac{1 - \frac{\lambda_n}{v_n}}{1 - \left(\frac{\lambda_n}{v_n}\right)^{M_n+1}} \quad \text{where} \quad \frac{v_n}{1 - \rho_n^{M_n+1}} = \frac{1}{1 - \left(\frac{\lambda_n}{v_n}\right)^{M_n}}$$

Note that $v_n$ depends on $\rho_n$. But if we begin to solve the equations for the last station first, we have $\rho_{N+1}=0$ and so we can compute, one after another, the pairs $(\lambda_n, \rho_n)$ for $n=N$ to $n=1$. Finally, we compute the mean delay for each station $n=1,2,...,N$ by Little's formula [9] as follows.

$$W_n = \lambda^{-1} \sum_{k=1}^{M_n} k \rho_n(k)$$
Station 0 is an M/M/1 system; hence its mean delay is

$$W_0 = \frac{1}{(1-p_1)\mu_0 - \lambda}$$

The mean total delay is $T = \frac{N}{\sum_{n=0}^{\infty} W_n}$.

## 5. Analysis of the Host-Retransmission Model

In this section we shall study the model depicted in Figure 2 by computing the mean total delay under the following retransmissions schemes from the initial station.

a) A rejected packet instantaneously returns to the initial station. This is an idealized model in which information about rejection travels with infinite speed; the rejected packet is actually destroyed and it is its backup copy which "returns" to the initial station.

b) A rejected packet returns to the initial station after a delay d; i.e., d is the time from the packet rejection at some station $n>0$ until its return to station 0. This model is motivated by host retransmissions on receiving a notification about packet rejection.

c) A rejected packet reenters the initial station after a timeout $D$ from the time of its original arrival into the network. $D$ is assumed to be sufficiently large to ensure that the probability is negligible of retransmitting a packet that arrived at the destination host.

The arrival process to the initial station consists of external arrivals and the retransmission traffic; we assume that this joint process is Poisson. The arrival processes
to the succeeding stations are approximated by Poisson processes. This approximation is good, in spite of the fact that a departure process from a finite-queue station is not exactly Poisson, if queue limit is large or server utilization is high. We base our study of the host-retransmission models on the behaviour of M/M/1/K systems.

The arrival rate at station n+1 is $\lambda_{n+1} = \lambda_n (1-p_n)$ for n=1,...,N-1; if we conveniently denote by $\lambda_{N+1}$ the departure rate from the last station, N, then the preceding equation is also valid for n=N. The probability of refusal is

$$P_n = \frac{1-p_n}{1-\prod_{n}^{M} p_{n-1}} \quad \text{where} \quad \prod_{n}^{M} p_n = \lambda_n / \mu_n$$

Hence we have to solve the following system of equations.

$$\lambda_n = \lambda_{n+1} / (1-p_n)$$

$$P_n = \frac{1-p_n}{1-\prod_{n}^{M} p_{n-1}}$$

We also know that the departure rate from the last station is equal to the external arrival rate into the network, i.e., $\lambda_{N+1} = \lambda$. Thus, beginning with the last station, we can compute $(\lambda_n, p_n)$ for n=N to n=1. By Little's formula, the mean delay in station n is

$$v_n = \frac{\sum_{k=1}^{M} k p_n(k)}{\lambda_n (1-p_n)}$$

where $P_n(k) = \frac{\lambda_n^k (1-p_n)}{(k-1)!(1-p_n)^{M-n}}$ and $p_n = \lambda_n / \mu_n$.
The initial station is an M/M/1 system with service rate $\lambda_0$ and arrival rate $\lambda_0 = \lambda + \sum_{i=1}^{N} p_i \lambda_i$. The mean delay is $W_0 = \mu_0^{-1} (1-p_0)^{-1}$.

We derive below the mean total delay for the entire tandem system, in the three cases described at the beginning of this section.

### a) Instantaneous return.

Let $T_n$ be the mean total delay of the first $n+1$ stations, from packet arrival in the system until its successful entrance in station $n+1$. We have

$$T_0 = W_0 / (1-p_1) \quad \text{and} \quad T_n = \frac{T_{n-1} + W_n}{1-p_{n+1}} \quad \text{for } n=1, \dots, N-1.$$

Then the mean total delay is $T=T_{N-1}+W_N$.

### b) Return after delay $\delta$.

$$T_n = (T_{n-1} + W_n) + 2(T_{n-1} + W_n) + dp_{n+1} (1-p_{n+1}) + \dots \\ + (k+1)(T_{n-1} + W_n) + kdp_{n+1}^k (1-p_{n+1}) + \dots$$

$$\text{Thus, } T_0 = \frac{W_0}{1-p_1} \quad \text{and} \\ \text{The mean total delay is again } T=T_{N-1}+W_N.$$

$$T_n = (T_{n-1} + W_n) \frac{1 - dp_{n+1}}{1 - p_{n+1}} \quad \text{for } n = 1, \dots, N-1.$$

The mean total delay is again $T=T_{N-1}+W_N$.

### c) Return after timeout $\ell$.

$$T_n = (T_{n-1} + W_n)(1-p_{n+1}) + (D+T_{n-1} + W_n)p_{n+1}(1-p_{n+1}) + \dots \\ + (kD+T_{n-1} + W_n)p_{n+1}^k(1-p_{n+1}) + \dots$$

$$\text{Thus, } T_n = \frac{dp_{n+1}}{1-p_{n+1}} + T_{n-1} + W_n \quad \text{for } n=0, 1, \dots, N-1.$$

The mean total delay is $T=T_{N-1}+W_N$.
## 6. Numerical Examples and Accuracy

In the preceding section we obtained algorithms to compute the mean delay in tandem queueing networks. The method is based on an equivalence of stations; the arrivals into these stations are assumed to be Poisson. This is rigorous in the case of two stations in tandem, or when there is an infinite number of stations; in all other situations the method leads only to an approximation. Thus, it is important to know how accurate it is. Since there are no exact analytical methods, we carried out simulations to verify our results.

In Figures 3 and 4 we produced numerical results obtained by our approximate method. With five or ten stations in tandem, we plotted the expected delay of the system as a function of the number of buffers in each station (a buffer can contain one packet) for different arrival rates into the system. We assumed every station to be identical, with the mean service time equal to one unit of time.

In Figures 5 and 6 we then plotted the arrival rate as a function of the number of buffers for different values of mean delay (as before, all the stations are identical).

In Tables 1 to 4, comparisons with simulations are listed in some cases. Simulation results are given with 90% confidence intervals. Note that almost all the approximate results are inside the confidence intervals. Exceptions occur for arrival rates which are close to saturation conditions. We conclude that the approximation is satisfactory.
It is obvious that the fewer retransmissions there are, the smaller the mean total delay is. Hence, provided the queueing delay had remained the same, the smallest mean total delay would have been obtained if each station had an infinite number of buffers. However, it is important to note that the minimal delay is approached rapidly with only a small number of buffers.

We define the optimal buffer number to be the smallest number of buffers to have the mean delay which differs at most 1% from the minimum. For example, with 5 stations and switch-retransmissions, if $\lambda=0.6$, the optimal number of buffers is 5; with host-retransmissions, it is 9 buffers. Under identical assumptions, but with 10 stations in series, we obtain 6 and 14 buffers respectively.

Obviously, for a given mean delay, the maximal arrival rate would have been obtained if waiting room had been infinite. However, in Figures 5 and 6 we show that, as before, this rate is approached rapidly, with a difference of less than 1%.

Also, it is important to observe that the difference between the mean delay for the two retransmission techniques, host and switch-retransmissions, is not significant. Thus, it is difficult to select the best technique on the basis of the minimal delay only.
## 7. Conclusions

In this paper we compared two methods of dealing with the overflow problem in packet switches: switch-retransmission and host-retransmission. We based our comparison on approximate analytic models of tandem queuing networks, and verified the results by simulation.

It turns out that for both retransmission strategies a small amount of waiting room in each switch is sufficient to obtain near minimal delay. Furthermore, both strategies exhibit similar delay performance; thus other considerations will be required to determine the best choice. They may include the cost of storing backup copies of packets in switches vs. hosts, and the ease of implementation.

Transient behaviour of each method may also have to be taken into account; this is an area for further research. Intuitively, host-retransmissions may be favoured here because, in a congested situation in which overflow occurs, packets immediately retransmitted from the preceding switch would further aggravate congestion. Also, switch-retransmission may cause backing up of congestion from one switch to the preceding switches.

Finally, the subscriber may not trust the network internal retransmission procedure and decide to implement his own recovery protocol in the host.
References

[1] B. Avi-Itzhak, "A Sequence of Service Stations with Arbitrary Input and Regular Service Times", Management Science, vol. 11, no. 5, March 1965, pp. 565-571.

[2] E. Gelenbe and R.R. Muntz, "Poisson Departure Processes and Queueing Networks", Acta Informatica, to appear.

[3] G.C. Hunt, "Sequential Arrays of Waiting Lines", Operations Research, vol. 4, 1956, pp. 674-683.

[4] M.I. Irland, "Buffer Management in a Packet Switch", IEEE Transactions on Communications, to appear.

[5] L. Kleinrock, Communication Nets: Stochastic Message Flow and Delay, McGraw-Hill, New York, 1964; reprinted by Dover, New York, 1972.

[6] L. Kleinrock, Queueing Systems, Volume 2: Computer Applications, Wiley, New York, 1976.

[7] A.G. Konheim and M. Reiser, "A Queueing Model with Finite Waiting Room and Blocking", Journal ACM, vol. 23, no. 2, April 1976, pp. 328-341.

[8] J. Labetoulle and G. Pujolle, "A Study of Queueing Networks with Deterministic Service and Application to Computer Networks", Proc. ACM/SIGMETRICS and IFIP/WG7.3 International Symposium on Computer Performance Modeling, Cambridge, Mass., March 1976.

[9] J.D.C. Little, "A Proof for the Queueing Formula $P=\lambda W$, Operations Research, vol. 9, 1961, pp. 383-387.

[10] M.F. Neuts, "Two Queues in Series with a Finite Intermediate Waiting Room", Journal of Applied Probability, vol. 5, 1968, pp. 123-142.

[11] G. Pujolle, "Files d'attente en série et application au taux de charge maximale d'un réseau d'ordinateurs", Revue d'Informatique de l'AFCET, P-2, May 1976.

[12] L. Pouzin, "Presentation and Major Design Aspects of the CYCLADES Computer Network", Proc. IEEE-ACM Third Data Communications Symposium, St. Petersburg, Florida, November 1973, pp. 80-87.

[13] I. Rubin, "Message Path Delays in Packet-Switching Communications Networks", IEEE Transactions on Communications, vol. CCM-23, no. 2, February 1975.
<figure><img src="image_2.png" /><figcaption>Figure 1

Switch-Retransmission Model</figcaption></figure>

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

Host-Retransmission Model</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Figure 3a
Mean Total Delay Vs. Number of Buffers
Switch-Retransmissions, 5 Stations</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 3b
Mean Total Delay Vs. Number of Buffers
Switch-Retransmissions, 10 Stations</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 4a
Mean Total Delay Vs. Number of Buffers
Host-Retransmissions, 5 Stations</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 4b
Mean Total Delay Vs. Number of Buffers
Host-Retransmissions, 10 Stations</figcaption></figure>

55

50

45

40

35

30

25

20

15

10

5

2

5

19

10

15

Number of
buffers
<caption>Figure 5a
Arrival Rate Vs. Number of Buffers
Switch-Retransmissions, 5 Stations</caption>

ARRIVAL RATE

<figure><img src="image_8.png" /></figure>
<figure><img src="image_9.png" /><figcaption>Figure 5b
Arrival Rate Vs. Number of Buffers: Switch-Pet-transmissions, 10 Stations</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 6a
Arrival Rate Vs. Number of Buffers:
Host-Retransmissions, 5 Stations</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Figure 6b
Arrival Rate Vs. Number of Buffers:
Host-Retransmissions, 10 Stations</figcaption></figure>
<caption>Table 1
Mean Total Delay
Switch-Retransmissions, 5 Stations
A-Approximate Analytic Results
S-Simulation: 90% Confidence Interval</caption>

Arrival rate

Number of buffers

<table><thead><tr><th></th><th></th><th>2</th><th>3</th><th>4</th><th>5</th><th>1</th></tr></thead><tbody><tr><td rowspan="2">0.1</td><td>A</td><td>5.52</td><td>5.55</td><td>5.56</td><td>5.56</td><td>5.56</td></tr><tr><td>S</td><td>5.44, 5.67</td><td>5.45, 5.63</td><td>5.37, 5.60</td><td>5.41, 5.63</td><td>5.46, 5.72</td></tr><tr><td rowspan="2">0.2</td><td>A</td><td>6.15</td><td>6.20</td><td>6.23</td><td>6.25</td><td>6.25</td></tr><tr><td>S</td><td>6.06, 6.47</td><td>6.01, 6.41</td><td>6.09, 6.47</td><td>6.01, 6.37</td><td>6.03, 6.36</td></tr><tr><td rowspan="2">0.3</td><td>A</td><td>7.00</td><td>7.00</td><td>7.07</td><td>7.11</td><td>7.14</td></tr><tr><td>S</td><td>6.98, 7.53</td><td>6.93, 7.71</td><td>6.76, 7.22</td><td>6.75, 7.19</td><td>6.78, 7.30</td></tr><tr><td rowspan="2">0.4</td><td>A</td><td>8.53</td><td>8.06</td><td>8.13</td><td>8.21</td><td>8.33</td></tr><tr><td>S</td><td>8.48, 9.65</td><td>8.00, 9.4</td><td>7.97, 8.95</td><td>7.92, 8.56</td><td>8.01, 8.78</td></tr><tr><td rowspan="2">0.5</td><td>A</td><td>52.81</td><td>9.79</td><td>9.60</td><td>9.68</td><td>9.98</td></tr><tr><td>S</td><td>45.42, 52.90</td><td>9.08, 1.03</td><td>9.54, 1.61</td><td>9.42, 1.03</td><td>10.4, 1.13</td></tr><tr><td rowspan="2">0.6</td><td>A</td><td></td><td>19.39</td><td>12.22</td><td>11.91</td><td>12.43</td></tr><tr><td>S</td><td></td><td>22.80, 30.42</td><td>12.25, 14.60</td><td>11.39, 13.1</td><td>11.80, 13.13</td></tr></tbody></table>
<caption>Table 2
Mean Total Delay
Switch-Retransmissions, 10 Stations
A-Approximate Analytic Results
S-Simulation: 90% Confidence Interval</caption>

Arrival rate Number of buffers

<table><thead><tr><th></th><th></th><th>2</th><th>3</th><th>4</th><th>5</th><th>10</th></tr></thead><tbody><tr><td rowspan="2">0.1</td><td>A</td><td>11.04</td><td>11.10</td><td>11.11</td><td>11.11</td><td>11.11</td></tr><tr><td>S</td><td>]10.99, 11.34[</td><td>]10.92, 11.28[</td><td>]10.93, 11.28[</td><td>]11.05, 11.38[</td><td>]10.91, 11.26[</td></tr><tr><td rowspan="2">0.2</td><td>A</td><td>12.26</td><td>12.29</td><td>12.46</td><td>12.49</td><td>12.50</td></tr><tr><td>S</td><td>]12.24, 12.81[</td><td>]12.27, 12.78[</td><td>]12.24, 12.72[</td><td>]12.21, 12.73[</td><td>]12.18, 12.67[</td></tr><tr><td rowspan="2">0.3</td><td>A</td><td>13.93</td><td>13.95</td><td>14.12</td><td>14.22</td><td>14.29</td></tr><tr><td>S</td><td>]14.06, 15.43[</td><td>]13.89, 14.88[</td><td>]13.87, 14.62[</td><td>]13.88, 14.62[</td><td>]14.02, 14.80[</td></tr><tr><td rowspan="2">0.4</td><td>A</td><td>16.97</td><td>16.01</td><td>16.20</td><td>16.40</td><td>16.66</td></tr><tr><td>S</td><td>]18.45, 22.58[</td><td>]15.81, 17.62[</td><td>]15.71, 17.52[</td><td>]15.66, 17.18[</td><td>]16.14, 17.24[</td></tr><tr><td rowspan="2">0.5</td><td>A</td><td></td><td>19.38</td><td>19.05</td><td>19.28</td><td>19.94</td></tr><tr><td>S</td><td></td><td>]19.82, 22.96[</td><td>]18.93, 21.05[</td><td>]18.56, 20.17[</td><td>]18.88, 20.63[</td></tr><tr><td rowspan="2">0.6</td><td>A</td><td></td><td></td><td>24.11</td><td>23.58</td><td>24.65</td></tr><tr><td>S</td><td></td><td></td><td>]23.98, 27.71[</td><td>]23.41, 27.48[</td><td>]23.96, 26.68[</td></tr></tbody></table>
<table><caption>Table 3
Mean Total Delay
Host-Retransmissions, 5 Stations
A-Approximate Analytic Results
S-Simulation: 90% Confidence Interval</caption><thead><tr><th></th><th></th><th>2</th><th>3</th><th>4</th><th>5</th><th>10</th></tr></thead><tbody><tr><td rowspan="2">0.1</td><td>A</td><td>5.61</td><td>5.57</td><td>5.57</td><td>5.57</td><td>5.56</td></tr><tr><td>S</td><td>5.51, 6.73</td><td>5.50, 6.73</td><td>5.49, 6.70</td><td>5.50, 6.69</td><td>5.46, 5.72</td></tr><tr><td rowspan="2">0.2</td><td>A</td><td>6.50</td><td>6.26</td><td>6.25</td><td>6.25</td><td>6.25</td></tr><tr><td>S</td><td>6.26, 6.76</td><td>6.14, 6.49</td><td>6.10, 6.44</td><td>6.08, 6.46</td><td>6.03, 6.36</td></tr><tr><td rowspan="2">0.3</td><td>A</td><td>8.63</td><td>7.37</td><td>7.22</td><td>7.21</td><td>7.22</td></tr><tr><td>S</td><td>8.55, 9.49</td><td>7.16, 7.76</td><td>6.90, 7.66</td><td>6.90, 7.62</td><td>6.78, 7.30</td></tr><tr><td rowspan="2">0.4</td><td>A</td><td></td><td>9.00</td><td>8.41</td><td>8.32</td><td>8.33</td></tr><tr><td>S</td><td></td><td>8.79, 10.07</td><td>8.21, 9.32</td><td>7.79, 8.43</td><td>8.14, 8.96</td></tr><tr><td rowspan="2">0.5</td><td>A</td><td></td><td></td><td>10.83</td><td>10.27</td><td>9.97</td></tr><tr><td>S</td><td></td><td></td><td>10.79, 12.17</td><td>9.80, 11.10</td><td>9.24, 10.13</td></tr><tr><td rowspan="2">0.6</td><td>A</td><td></td><td></td><td></td><td>14.10</td><td>12.35</td></tr><tr><td>S</td><td></td><td></td><td></td><td>12.93, 16.27</td><td>11.79, 13.34</td></tr></tbody></table>
<table><caption>Table 4
Mean Total Delay
Host-Retransmissions, 10 Stations
A-Approximate Analytic Results
S-Simulation: 90% Confidence Interval</caption><thead><tr><th>Arrival rate</th><th></th><th></th><th></th><th></th><th></th><th>Number of buffers</th></tr></thead><tbody><tr><td rowspan="2">.1</td><td>A</td><td>11.47</td><td>11.14</td><td>11.11</td><td>11.11</td><td>11.11</td></tr><tr><td>S</td><td>]11.11, 11.52[</td><td>]10.89, 11.37[</td><td>]10.98, 11.37[</td><td>]11.08, 11.42[</td><td>]10.91, 11.26[</td></tr><tr><td rowspan="2">.2</td><td>A</td><td>15.16</td><td>12.77</td><td>12.53</td><td>12.50</td><td>12.50</td></tr><tr><td>S</td><td>]14.12, 15.25[</td><td>]12.29, 12.87[</td><td>]12.20, 12.74[</td><td>]12.19, 12.77[</td><td>]12.18, 12.61[</td></tr><tr><td rowspan="2">.3</td><td>A</td><td></td><td>15.85</td><td>14.57</td><td>14.24</td><td>14.29</td></tr><tr><td>S</td><td></td><td>]15.12, 16.43[</td><td>]13.74, 14.60[</td><td>]13.73, 14.44[</td><td>]14.02, 14.80[</td></tr><tr><td rowspan="2">.4</td><td>A</td><td></td><td></td><td>18.32</td><td>17.08</td><td>16.66</td></tr><tr><td>S</td><td></td><td></td><td>]16.97, 18.49[</td><td>]16.33, 17.51[</td><td>]16.14, 17.24[</td></tr><tr><td rowspan="2">.5</td><td>A</td><td></td><td></td><td></td><td>22.90</td><td>20.01</td></tr><tr><td>S</td><td></td><td></td><td></td><td>]21.22, 24.72[</td><td>]19.42, 21.26[</td></tr><tr><td rowspan="2">.6</td><td>A</td><td></td><td></td><td></td><td></td><td>25.22</td></tr><tr><td>S</td><td></td><td></td><td></td><td></td><td>]23.59, 26.12[</td></tr></tbody></table>