RIA
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>

FINITE AND INFINITE
SOURCE MODELS FOR
COMMUNICATION SYSTEMS
UNDER POLLING

Michel SCHOLL
Dominique POTIER

Rapport de Recherche N° 308

Mai 1978
# FINITE AND INFINITE SOURCE MODELS FOR COMMUNICATION SYSTEMS
## UNDER POLLING

Michel Scholl*, Dominique Potier*

Résumé :

Les modèles à source Infinie (MSI) sont souvent utilisés pour prédire les performances des systèmes de transmission de données dans lesquels le nombre d'utilisateurs est élevé (bien que fini) et tels que chaque utilisateur ne génère que rarement des données. On se propose d'étudier dans cette note la précision d'une telle prédiction, lorsqu'une technique de POLLING est utilisée pour multiplexer m groupes géographiquement éparpillés de n utilisateurs chacun (chaque groupe rassemble n utilisateurs proches les uns des autres). Cette étude de précision est faite grâce à une comparaison des délais moyens stationnaires d'un message prédits respectivement par le MSI et un modèle à source finie plus réaliste. Bien que la prédiction du MSI est pessimiste lorsque le trafic total est peu intense, elle peut devenir optimiste lorsque le trafic est élevé. Une formule simple donne une idée sur le signe de l'erreur (prédiction optimiste ou pessimiste) suivant la valeur de l'overhead dû au temps perdu à interroger (poll) les utilisateurs.

Abstract :

Infinite Source Models (ISM) are very often used for predicting the performance of Communica-
tion System in which the number of data sources is large (but finite) each source generating sparse
traffic. Of interest to this note is the accuracy of such a prediction, when a Polling technique is
used for multiplexing m geographically scattered groups of n local data users each. The accuracy
study is done by comparing the stationary expected message delay predicted by the ISM to that
predicted by a more realistic Finite Source Model. Although the ISM prediction is pessimistic at
light input loads it may become optimistic under heavy load conditions. A rule of thumb is deri-
ved which gives an idea on whether the ISM is optimistic or pessimistic according to the value of
the control overhead (time lost in Polling the terminals).
# I. INTRODUCTION

The growing need for access to computers and data communication channels creates a formidable problem of allocating these large expensive resources among an ever increasing number of users. In this note we restrict our attention to local distribution, i.e to the allocation of a data communication channel to a set of N geographically dispersed data sources (terminals) which are to be connected to a central facility (computer).

One basic configuration that allows multiple access to the data channel is illustrated on Fig. 1, where a multi-point tree set of lines connects m geographically scattered repeaters to a central computer. Each repeater connects to the computer a number of local terminals. For the sake of simplicity, we assume that this number of terminals is the same at each repeater : n = N /m.

Of interest to this note is the consideration of the Polling technique [1] widely used for local distribution. A central processor (poller) at the computer asks (polls) the N terminals one by one in a preassigned sequence whether they have anything to transmit (the poller broadcasts a polling message containing information about the address of the user being polled). After transmitting each address the poller waits for a reply from a terminal and either receives a message or goes on to the next terminal in sequence. The time interval necessary for switching from a terminal to the next one in sequence (polling + waiting for reply) is denoted by r. This Polling technique known as Roll-Call Polling [1] was modelled and analyzed by Konheim and Meister [2].

However, if we are in the presence of the configuration shown on Fig. 1, the poller does not have to monitor the switching from one terminal, say i, to terminal (i mod N + 1) if both terminals belong to the same set, i.e if they are attached to the same repeater. In this case, the transmission from terminals of the same set is directly monitored by the repeater (or by the terminals themselves). Since, in general, terminals of the same set are geographically gathered, the switching time between any two of them may be considered as negligible, compared to r. Let a cycle be the time interval between two successive visits to the same terminal. The overhead per cycle (total time lost for message transmission, per cycle) is then equal to m x r. This is the time necessary to poll m terminals (each of them is the first terminal in sequence attached to one among m repeaters).
<figure><img src="image_2.png" /><figcaption>Fig. 1. Multipoint Tree : m repeaters, n terminals/repeater</figcaption></figure>

An important performance measure of such communication systems is the expected message delay T defined as the average time elapsing from the generation of a message at a terminal until the end of its transmission. T may be predicted from Konheim and Meister's analysis [2] by using the following Infinite Source Model (ISM):

Consider that the m buffered repeaters are served according to the Roll-Call Polling policy. Then consider that messages are "generated" at each repeater (and not anymore at the terminals) according to a Poisson Point Process with intensity $A_{in}$, where $A_{in}$ is the mean aggregate rate of messages generated at all the terminals attached to this repeater. Messages "generated" at a repeater are queued in its buffer, until the repeater is polled, at which time the buffer is completely emptied (the repeater seizes control of the channel until he has no message to transmit).

ISM'S are very often used for predicting the performance of communication systems in which the number of data sources in large (but finite), each source generating sparse traffic (see for example [3,4,5]).
ISM's are preferred to Finite Source Models (FSM) for three main reasons [3] :

(1) The analytical solution of FSM's is usually more complex or may even not exist.

(2) It is sometimes easier to measure the mean message rate observed at a subsystem (repeater) than to measure the message generation rate at each individual data source (terminal).

(3) Finally, the value of N does not explicitly appear in the ISM (the value of n either) and therefore need not be known exactly (N may even fluctuate) when applying the model to a real configuration.

However, one of the strong assumptions made when using ISM's is that the rate of message arrivals to the subsystem (repeater) is independent of the queue length. In fact, because of the finite source nature of the message generation (there are at most N messages waiting for transmission at a given point in time), the rate of generation is not constant as queue length varies; it decreases and drops to zero, as queue length increases up to N. Nevertheless the rate of generation does not vary much if n is large enough.

The purpose of this note is to show how accurate the ISM is in predicting the expected message delay in the Polling system depicted in Fig.1.

Fortunately, the analytical solution of the FSM exists for the configuration shown on Fig.1. It is presented in section 2. The expected message delay as predicted by the ISM [2] is given in section 3.

Since both (finite and Infinite Source) models can be solved explicitly, we can compare their predictions for various values of r, m and n. This is done in section 4. As expected, when n is fairly large the ISM is shown to accurately predict the performance of the system. Furthermore, under heavy load conditions, the ISM is pessimistic if $r < \frac{1}{m}$, optimistic otherwise.

## 2. FINITE SOURCE MODEL

The main analytical results are due to Mack et al [6] who derived the expected cycle time (time interval between successive visits to the same terminal) when the message transmission time P is constant, i.e. when all messages are equal in length. In a companion paper, Mack [7] studied the case where message lengths are variable and did not get a closed form solution. We restrict one attention to the constant length case; packet switched communication systems are examples of systems in which messages (packets) are constant in length [8].

We make the following definitions and assumptions :

(I) Terminals are polled one by one in a fixed order say 1,2,...,n,n+1,...,2n,..., (m-1)n+1,..., mn,1,2,...n, etc, where terminals jn+1,jn+2,...,(jmodN+1)n, are attached to the jth repeater, j=1,2,...,m. When a terminal is polled, it may
transmit a message if it has generated one since the last visit; if not, a negative reply is received and the next terminal in sequence is polled.

(II) Each terminal has a probability $A\delta t + 0$ ($\delta t$) of generating a message in an interval of time $\delta t$, only if this terminal has no message waiting for transmission or being transmitted. Thus the terminal's thinking time is exponentially distributed with parameter $1/A$. Let $\lambda$ be the message generation rate normalized with respect to $P$: $\lambda = A/P$.

(III) It takes a constant time $r_i$, $i=1, \dots, N$, to switch from terminal $i$ to terminal $imodN+1$. We have already assumed (see Introduction) that $r_i=0$ if $i$ and $imodN+1$ are attached to the same repeater, and that $r_i=r$, otherwise. We have:

$$ \sum_{i=1}^{N} r_{i} = mr $$

where $r$ is normalized with respect to $P$.

The cycle is more precisely defined as starting at the instant where channel control is switched from terminal $i$ to terminal $imodN+1$ (end of message transmission or negative reply received from $i$) and ending when control is switched again from $i$ to $imodN+1$. Thus a cycle where no terminal transmits lasts $mrP$ seconds, a cycle where one terminal transmits lasts $(mr+1)$ seconds, etc...

We respectively denote by $\tau$ and $T$, the expected cycle time and the expected message delay normalized with respect to $P$. Recall that the message delay is the time elapsing from the generation of a message until the end of its transmission.

### THEOREME I. (Mack et al. [6])

The stationary expected cycle time predicted by the FSM is given by:

$$ \tau = mr + Nb \quad (1) $$

$$ \text{where } b = \left[ \sum_{k=0}^{N-1} \binom{N-1}{k} \prod_{i=0}^{k} \left( e^{\frac{\lambda}{i}} - 1 \right) \right] / \left[ \sum_{k=1}^{N} \binom{N}{k} \prod_{i=0}^{k-1} \left( e^{\frac{\lambda}{i}} - 1 \right) \right] \quad (2) $$

Knowing $\tau$, we easily get $T$ by observing that under steady state conditions, the total input rate, i.e. the average (total) number of messages generated every $P$ seconds, denoted by $\lambda_{in}$, is equal to the total throughput rate, i.e. the average (total) number of messages transmitted every $P$ seconds, denoted by $\lambda_{out}$.

Since each terminal generates one message every $(T + 1/\lambda)$ $P$ seconds on the average, we have:

$$ \lambda_{in} = \frac{N}{T+1/\lambda} \quad (3) $$
The mean number of messages transmitted in one cycle is equal to $\tau$-mr. Then we have :

$$ \lambda_{\text{out}} = \frac{\tau - mr}{\tau} $$

and from Eq. (1) :

$$ \lambda_{\text{out}} = \frac{Nb}{mr+Nb} \quad (4) $$

Equating the right-hand sides (RHS) of Eqs. (3) and (4), we finally get :

$$ T = N + \frac{mr}{b} - \frac{1}{\lambda} \quad (5) $$

where b is given by Eq. (2). Equivalently from Eq. (3) we have

$$ T = \frac{N}{\lambda_{\text{in}}} - \frac{1}{\lambda} \quad (6) $$

Observe that :

$$ \lambda_{\text{in}} = \frac{Nb}{mr+Nb} = \frac{n}{nb+r} \quad (7) $$

As $\lambda$ goes to zero (light traffic), b goes to zero. So does $\lambda_{\text{in}}$. One easily shows that :

$$ \lim_{\lambda \to 0} T = 1 + \frac{mr}{2} \quad (8) $$

As $\lambda$ goes to infinity (i.e. as soon as a terminal has transmitted a message, it generates another one) b goes to 1. Then :

$$ \lim_{\lambda \to \infty} \lambda_{\text{in}} = \frac{N}{N+mr} \quad (9) $$

One easily shows that

$$ \lim_{\lambda \to \infty} T = N + mr = m(n+r) \quad (10) $$

Furthermore, we get after some calculations :

$$ \lim_{r \to 0} T = N - \frac{1}{\lambda} \left( 1 - \left[ \sum_{k=1}^{N-1} \binom{N-1}{k} \prod_{l=1}^{k} (e^{\lambda i_{l-1}} + 1) \right]^{-1} \right) \quad (11) $$

As might have been expected, Eq. (11) is equivalent to Eq. (44') in [9]. The latter equation gives the expected message delay for the machine interference model (MIM) solved by Takács in [9] (if $r = 0$, our model and the MIM are identical).

### 3. INFINITE SOURCE MODEL.

To complete the description of this model (see Introduction) we make the following assumptions :
(1) each repeater generates messages according to a Poisson Point Process with intensity $\lambda_{in}/mP$ (every P seconds, each repeater generates $\lambda_{in}/m$ messages on the average)

(2) each repeater has a buffer with infinite size, where messages queue up and are served in a First-Come-First-Served order.

**THEOREME 2** (Konheim and Meister [2]):

The stationary expected message delay predicted by the ISM is given by:

$$T = 1 + \frac{\lambda_{in}}{2(1-\lambda_{in})} + \frac{r}{2} \left(1-\frac{\lambda_{in}}{m}\right) \left(1+\frac{m}{1-\lambda_{in}}\right) \quad (12)$$

**Proof:**

the time axis is slotted, each slot of size $\tau$ accommodating a single data unit (e.g. a byte, a group of bytes, etc...) [2]. Each message transmission starts at the beginning of a slot and lasts an integer number of slots S. Each time the channel is switched from one repeater to the next one, it is not available for data transmission during a (constant) interval (polling + reply interval) equal to an integer number of slots denoted by k. Then the stationary expected message delay (waiting + transmission) expressed in number of slots is given by Theorem 6.3 in [2]:

$$D = S + \frac{m\sigma^2}{2(1-m\mu)} + \frac{(1-\mu)}{2} \left[ 1 + \frac{mk}{1-m\mu} \right] \quad (13)$$

where $\mu$ and $\sigma^2$ are the expectation and variance of the number of slots required to transmit the messages generated at a repeater during one slot.

Without loss of generality, k is taken equal to 1. Then we have:

$$\tau = r \times P$$

$$\text{and} \quad S = 1/r$$

To get the mean delay T normalized with respect to P, we have to multiply the RHS of Eq. (13) by r:

$$T = 1 + r' \frac{m\sigma^2}{2(1-m\mu)} + \frac{r}{2} (1-\mu) \left[ 1 + \frac{m}{1-m\mu} \right] \quad (14)$$

Since the message generation process at each repeater is Poisson with intensity $\lambda_{in}/mP$, we have:

$$\mu = \frac{\lambda_{in}}{mP} \quad \tau \times S = \frac{\lambda_{in}}{mP} \quad \tau \times \frac{P}{\tau} = \frac{\lambda_{in}}{m} \quad (15)$$

$$\sigma^2 = \frac{\lambda_{in}}{mP} \quad \tau \times S^2 = \frac{\lambda_{in}}{mr} \quad (16)$$

Substituting Eqs. (15) and (16) into Eq (14) we get Eq. (12).
## 4. DISCUSSION

Two preliminary remarks are noteworthy:

(a) The ISM is definitively inaccurate, under very heavy traffic conditions, since it predicts an infinite mean delay as $\lambda_{in}$ goes to 1, i.e. as $\lambda$ goes to infinity (Eq.(12)), while the expected delay should remain bounded by $m(n+r)$ (Eq.(10)), according to the FSM.

(b) In equilibrium $\lambda_{in}$ can also be referred to as the channel utilization [4]. Indeed, if we were able to perfectly schedule the message into the available channel space with absolutely no control overhead, we could achieve a maximum throughput equal to 1. Since, within each cycle, $m \times r \times P$ seconds are wasted for control, the maximum achievable throughput (the maximum channel utilization), called the channel capacity $C$ [4] under Polling (FSM) is less than one:

$$ \lambda_{in} \quad C = \frac{N}{N+mr} = \frac{n}{n+r} \quad (17) $$

$C$ is achieved when $\lambda$ goes to infinity, i.e. when $b=1$ (Eq. (7)).

However, the ISM predicts a full utilization of the channel (with infinite delays). When one repeater is saturated and keeps the channel for its own use, there is no changeover and therefore the maximum achievable throughput is $\lambda_{in} = 1$ message/ message transmission time.

Remark (b) is illustrated on Fig.2 where the channel capacity is plotted versus $r$ (Eq.(17)) for various values of $n$. From the above remarks, it is clear that the error introduced by the ISM is rather significant when the number of terminals per repeater is small ($n < 4$), for all values of $m$.

Let us now compare the expected message delay as predicted by the FSM, denoted by $T_n$ to the expected message delay as predicted by the ISM and denoted by $T_\infty$, for various values of $n$ and $r$. The value of $m=64$ repeaters is chosen in the sequel of this comparison. The numerical results are shown in Tables 1 and 2 where $r$ is respectively chosen equal to .01 and .1. For each value of $r$, two basic configurations are studied: a) $n=1$ (roll-call Polling for $m$ terminals), b) $n=16$ (64 groups of 16 terminals each). For a given couple of values ($n,r$), $T_n$ is a function of the traffic generated at the terminals, or equivalently, a function of the mean thinking time $1/\lambda$ at each terminal (Eqs.(2) and (5)), while $T_\infty$ is a function of the mean "observed" input rate $\lambda_{in}$ at the repeaters (Eq. (12)). However, to each value of $\lambda$ corresponds one value of $\lambda_{in}$ (Eq.(7)) and therefore $T_\infty$ can also be expressed as a function of $\lambda$.

We first note that when the number of terminals is large, e.g. $n=16$, $N=mn=1024$ (see Tables 1.b and 2.b) the ISM is extremely accurate, even under very heavy traffic conditions (when $r=.1$ and $\lambda_{in} = .98$, $(T_\infty - T_{16})/T_{16} < 5\%$). For a given value of $N$, the smaller $n$ is (see the above remark (a)) and Fig.2), and/or the smaller $r$ is, the better
the ISM approximation is.

The accuracy of the ISM decreases with increasing values of $\lambda$. This degradation may become significant for small values of N. When $n=1$ (see Tables 1. a and 2. a), and $r = .1(.01)$, $(T_\infty - T_1)/T_1$ reaches 20% (25%) if $\lambda_{in} = .906(.88)$.

This is illustrated on Fig.3 and Fig.4 where $T_\infty$ and $T_1$ are plotted versus $\lambda_{in}$ respectively for $r = .01$ and $r = .1$. The curves are labelled by the corresponding values of $\lambda$. Observe that when $\lambda_{in} = \lambda = 0$, then $T_\infty = T_1 = 1 + mr/2$, and when $\lambda_{in} = C = n/(n+r) = 1/(1+r)$, then $T_1 = N + mr = m(1+r)$.

From Tables 1 and 2, we finally note that the ISM is always pessimistic at light input loads, i.e. $T_\infty > T_1$, for all values of n and r, if $\lambda_{in}$ is not too large. Surprisingly this is not true anymore under heavy traffic conditions : if r is large enough, for large values of $\lambda_{in}$, the ISM prediction may become optimistic, e.g. if $r = .1$, and if $.9 \le \lambda_{in} \le 1/(1+r) \approx .91$, then $T_\infty < T_1$ (see Fig.4).

To complete this discussion, let us fix m and n and let us find the value of $r$, denoted by $r_o$ such that :

$$ \lim_{\lambda \to \infty} T_n(\lambda) \triangleq T_n(\lambda = \infty) = \lim_{\lambda \to \infty} T_\infty(\lambda) \triangleq T_\infty(\lambda = \infty) $$

from Eq. (10), we have

$$ T_n(\lambda = \infty) = m(n+r) = T_\infty(\lambda_{in} = \frac{n}{n+r}) \quad (18) $$

If m is not too small, say $m \ge 16$, the following approximation of $T_\infty$ is fairly good :

$$ T_{\infty}(\lambda_{in}) = 1 + \frac{\lambda_{in} + mr}{2(1-\lambda_{in})} \quad (19) $$

Substituting Eq. (19) into Eq. (18), we have :

$$ mr(n+r) - 2 - n = 0 \quad (20) $$

The positive solution of Eq. (20) is :

$$ r_o = \frac{2 - mn + \sqrt{(mn)^2 + 4}}{2m} $$

Then, if $m \ge 16$, $r_o \approx \frac{1}{m}$

Obviously, if $r \le r_o$, then $T_n(\lambda = \infty) \le T_\infty(\lambda = \infty)$ and if $r > r_o$, then

$$ T_n(\lambda = \infty) > T_\infty(\lambda = \infty) $$
Therefore, we may conclude that if $rm \le 1$ and $m$ is not too small (say $m \ge 16$), the ISM prediction in terms of expected message delay is pessimistic for all values of $\lambda_{in}$ ($\le C = \frac{m}{n+r}$), while if $rm > 1$, there exists a range ($\lambda_0 \le \lambda_{in} \le \frac{m}{n+r}$) where the ISM predicts an expected message delay $T_\infty(\lambda_{in})$ larger than the expected delay $T_n(\lambda_{in})$ predicted by the FSM.

The latter point may be interpreted as follows :

Clearly, both models predict the same expected cycle time (see Eqs.(1) and (7) and Theorem 6.1 in [2]) :

$$ \tau = \frac{mr}{1-\lambda_{in}} \qquad (21) $$

and therefore the same mean number of messages served during one cycle :

$$ k = \lambda_{in} \frac{mr}{1-\lambda_{in}} $$

### Trend 1

Any message generated at a given terminal*, say i, experiences two sources of delay:

(1) the delay until the next visit to i (the same, on the average, in both models for a given value of $\lambda_{in}$),

(2) the delay imposed by messages already buffered at i : 0 in the FSM, $d_2 > 0$ where $E\{d_2\}$ increases with increasing values of $\tau$ (i.e. with increasing values of $\lambda_{in}$) in the ISM.

This explains why, at least at light input loads, the ISM is slightly pessimistic (Tables 1 and 2) the degradation increasing with increasing values of $\lambda_{in}$.

However, the latter trend may be neutralized by the following one under heavy traffic conditions :

### Trend 2

If $\lambda_{in}$ is large enough, $k$ is close to $N$, then with the ISM, a message generated at i during the visit to i (one or more messages are transmitted from i during this cycle), does not incur any delay due to Polling (there is no overhead for this message) while, with the FSM, at most one message is transmitted from i in any cycle and therefore, all messages experience a delay due to Polling. Therefore for a given value of $k$ and this for a given value of $\lambda_{in}$, there is a saving in delay with the ISM.

<footnote>* To explain the following trends, we take the example of $n=1$ terminal/repeater. Similar interpretations may be given when $n > 1$.</footnote>
If $\lambda_{in} \approx \frac{n}{n+r}$ (i.e. $\lambda \approx \infty$), with the FSM, most of the messages experience an overhead of mrP seconds, while for the same mean number of messages transmitted in a cycle, this is not true with the ISM: Some messages even experience no overhead (if generated at a terminal when this terminal controls the channel).

It is not surprising then, that this trend becomes significant when mr is around 1, i.e. when the overhead incurred by any message ($\lambda_{in} \approx \frac{n}{n+r}$) is of the order of one message transmission time.

If $mr > 1$, trend 2 is then more important than trend 1, since even close to the "saturation" point ($\lambda_{in} = \frac{n}{n+r}$), the component $d_2$ is still small (the probability there are more than one message buffered at each repeater is still small) [2]. This explains that under heavy traffic conditions the ISM prediction may be optimistic.

In summary, the ISM was shown to accurately predict the stationary expected message delay when the number of terminals per repeater is fairly large ($n \ge 16$). Furthermore, under heavy load conditions, the delay prediction is pessimistic, approximately if the overhead per cycle (equal to $mr \times P$ seconds) is less than one message transmission time (P seconds), optimistic otherwise. At light input loads however, the ISM prediction is always slightly pessimistic.
<table><caption>Table 1. Comparison of the expected message delay as Predicted by the ISM (T<sub>∞</sub>) to the expected message delay as predicted by the FSM (T<sub>n</sub>) ; m = 64, r = .01</caption><thead><tr><th></th><th>λ</th><th>λ<sub>in</sub></th><th>T<sub>n</sub></th><th>T<sub>∞</sub></th></tr></thead><tbody><tr><td rowspan="6">(a)<br>n=1</td><td>0</td><td>0</td><td>1.32</td><td>1.32</td></tr><tr><td>5x10<sup>-3</sup></td><td>.3173</td><td>1.69</td><td>1.70</td></tr><tr><td>10<sup>-2</sup></td><td>.6237</td><td>2.60</td><td>2.68</td></tr><tr><td>1,5x10<sup>-2</sup></td><td>.8814</td><td>5.94</td><td>7.41</td></tr><tr><td>2x10<sup>-2</sup></td><td>.9742</td><td>15.69</td><td>32</td></tr><tr><td>5x10<sup>-2</sup></td><td>.9896</td><td>44.67</td><td>79</td></tr><tr><td></td><td>∞</td><td>.9901</td><td>64.64</td><td>81.50</td></tr><tr><td rowspan="8">(b)<br>n=16</td><td>0</td><td>0</td><td>1.32</td><td>1.32</td></tr><tr><td>3x10<sup>-4</sup></td><td>.3070</td><td>1.68</td><td>1.68</td></tr><tr><td>6x10<sup>-4</sup></td><td>.6134</td><td>2.61</td><td>2.62</td></tr><tr><td>8x10<sup>-4</sup></td><td>.8160</td><td>4.90</td><td>4.96</td></tr><tr><td>9x10<sup>-4</sup></td><td>.9138</td><td>9.54</td><td>10.03</td></tr><tr><td>9,5x10<sup>-4</sup></td><td>.9573</td><td>17.02</td><td>19.70</td></tr><tr><td>10<sup>-3</sup></td><td>.9866</td><td>37.89</td><td>59</td></tr><tr><td>1,2x10<sup>-3</sup></td><td>.9980</td><td>192.5</td><td>410.5</td></tr><tr><td></td><td>∞</td><td>.9994</td><td>1024.64</td><td>1367.67</td></tr></tbody></table>
<table><caption>Table 2. Comparison of the expected message delay as predicted by the ISM ($T_{\infty}$) to the expected message delay as predicted by the FSM ($T_n$) ; m = 64 , r = .1</caption><thead><tr><th></th><th>λ</th><th>λ<sub>in</sub></th><th>T<sub>n</sub></th><th>T<sub>∞</sub></th></tr></thead><tbody><tr><td></td><td>0</td><td>0</td><td>4.20</td><td>4.20</td></tr><tr><td></td><td>10<sup>-3</sup></td><td>.064</td><td>4.45</td><td>4.49</td></tr><tr><td></td><td>5x10<sup>-3</sup></td><td>.310</td><td>5.86</td><td>5.91</td></tr><tr><td></td><td>10<sup>-2</sup></td><td>.585</td><td>9.36</td><td>9.48</td></tr><tr><td></td><td>1.5x10<sup>-2</sup></td><td>.770</td><td>16.39</td><td>16.64</td></tr><tr><td rowspan="6">(a)<br>n=1</td><td>2x10<sup>-2</sup></td><td>.850</td><td>25.32</td><td>25.22</td></tr><tr><td>3x10<sup>-2</sup></td><td>.892</td><td>38.42</td><td>34.81</td></tr><tr><td>4x10<sup>-2</sup></td><td>.902</td><td>45.92</td><td>38.31</td></tr><tr><td>5x10<sup>-2</sup></td><td>.906</td><td>50.63</td><td>39.91</td></tr><tr><td>6x10<sup>-2</sup></td><td>.908</td><td>53.84</td><td>40.77</td></tr><tr><td>∞</td><td>.909</td><td>70.40</td><td>41.21</td></tr><tr><td></td><td>0</td><td>0</td><td>4.20</td><td>4.20</td></tr><tr><td></td><td>3x10<sup>-4</sup></td><td>.306</td><td>5.83</td><td>5.88</td></tr><tr><td></td><td>6x10<sup>-4</sup></td><td>.610</td><td>10.00</td><td>10.04</td></tr><tr><td></td><td>8x10<sup>-4</sup></td><td>.807</td><td>19.51</td><td>19.72</td></tr><tr><td></td><td>9x10<sup>-4</sup></td><td>.894</td><td>34.57</td><td>35.46</td></tr><tr><td rowspan="6">(b)<br>n=16</td><td>9.5x10<sup>-4</sup></td><td>.928</td><td>50.18</td><td>51.94</td></tr><tr><td>10<sup>-3</sup></td><td>.953</td><td>74.44</td><td>79.27</td></tr><tr><td>1.2x10<sup>-3</sup></td><td>.983</td><td>208.08</td><td>218.20</td></tr><tr><td>1.3x10<sup>-3</sup></td><td>.987</td><td>268.50</td><td>280.07</td></tr><tr><td>∞</td><td>.994</td><td>1030.40</td><td>596.20</td></tr></tbody></table>
<figure><img src="image_3.png" /><figcaption>Fig.2- Channel Capacity C versus Polling time r</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Fig.3- Expected message delay versus total Input rate, m=64, n=1, r=.01</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 4- Expected message delay versus total input rate, m=64, n=1, r=.1</figcaption></figure>
REFERENCES

[1] MARTIN, J. *Teleprocessing Network Organization*, Prentice-Hall, Englewood Cliffs, New Jersey, 1970

[2] KONHEIM, A.G. and B. MEISTER. "Waiting lines and Times in a System with Polling", *Journal of the Association for Computing Machinery*, vol.21, N°3, July 1974, pp.470-490

[3] BUZEN, J.P. and P.S. GOLDBERG. "Guidelines for the use of infinite source queueing models in the analysis of computer system performance", National Computer Conference, *AFIPS Conference Proceedings*, vol 43, 1974, pp 371-374.

[4] KLEINROCK, L. and S.S. LAM. "Packet Switching in a Multi-access Broadcast channel: Performance Evaluation", *IEEE Transactions on Communications*, vol.COM.23, N° 4, April 1975, pp.410-423.

[5] KLEINROCK, L. and F.A. TOBAGI. "Packet Switching in Radio Channels, Part 1: Carrier Sense Multiple-Access Modes and their Throughput-Delay Characteristics", *IEEE Transactions on Communications*, vol.COM.23, N°12, December 1975, pp 1400-1416.

[6] MACK, C.T. MURPHY and N.L WEBB. "The Efficiency of N Machines Uni-Directionally Patrolled by One Operative when Walking Time and Repair Times are Constants," *J.R. Statist. Soc.*, B, 19, 1957, pp.166-172.

[7] MACK, C. "The Efficiency of N Machines Uni-Directionally Patrolled by One Operative when Walking Time is Constant and Repair Times are Variable", *J.R. Statisti Soc*, B, 19, 1957, pp.173-178.

[8] ROBERTS, L.G. "Data by the Packet," *IEEE Spectrum*, vol.11, N°2, February 1974, pp.46-51.

[9] TAKACS, L. "On a Stochastic Process Concerning Some Waiting Time Problems", *Theory of Probability and its Applications*, vol. II, N°1, 1957, pp.90-103.