Citation
Comparative performance analysis of local area networks

Material Information

Title:
Comparative performance analysis of local area networks
Creator:
Shvarzberg, Leonid M
Publication Date:
Language:
English
Physical Description:
ix, 83 leaves : illustrations ; 29 cm

Thesis/Dissertation Information

Degree:
Master's ( Master of science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Electrical Engineering, CU Denver
Degree Disciplines:
Electrical engineering

Subjects

Subjects / Keywords:
Local area networks (Computer networks) ( lcsh )
Local area networks (Computer networks) ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references.
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Electrical Engineering.
General Note:
Department of Engineering
Statement of Responsibility:
by Leonid M. Shvarzberg.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
28246808 ( OCLC )
ocm28246808
Classification:
LD1190.E54 1992m .S52 ( lcc )

Full Text
COMPARATIVE PERFORMANCE
ANALYSIS
OF LOCAL AREA NETWORKS
bY
Leonid M. Shvarzberg
B. S.,! Moscow Institute of Telecommunications
i MOSCOW, USSR, 1987
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Electrical Engineering
i i
1992


Shvarzberg, Leonid M. (M.S., Electrical Engineering)
Comparative Performance Analysis of Local Area
Networks
Thesis directed by Associate Professor Douglas A. Ross
ABSTRACT
LAN is a data communications facility providing
high-speed switched connections between processors,
peripherals and terminals within a single building
or campus. This thesis is concerned with performance
analysis of local area networks. The particular
media access technique tends to dictate several
different implementations that may have different
performance models and thus have different
performance.
Performance analysis means the development and
study of mathematical models that predict the
performance of networks. Most existing models
consider the shared LAN channel as a distributed
M/G/l queue. In order to derive an accurate
mathematical model the arrival statistics must be
determined. Although Poisson arrival statistics is
i-
used in most mathematical models, it tends to over-
emphasize the actual number of packets in the system


This thesis for the Master of Science
degree by
Leonid M. Shvarzberg
has been approved for the
Department of
Electrical Engineering
by
Miloje S. Radenkovic
Boris Stilman
Date


because it does not consider the packet length. Non
overlapping arrival statistics predicts the queue's
behavior more accurately because it considers both
the packet and gap length.
The performance of different media access
methods can be compared for different arrival
statistics and different packet length distribution
The form and content of this abstract are
approved. I recommend its publication.
Signed
iv


to my parents


ACKNOWLEDGEMENTS
I would like to express my appreciation to
Dr. Douglas A. Ross for his help. I would also like
to thank Professor Joe E. Thomas for his guidance
and support.
Special thanks is given to my wife Elena and
daughter Lisa for their patience and constant
encouragement to finish.
vi


CONTENTS
CHAPTER
INTRODUCTION ................................ 1
1. TOKEN RING NETWORKS.......................... 4
1.1 Basic Operations ............................ 4
1.2 Preliminary Definitions ..................... 7
1.3 Delay Analysis...............................10
1.4 Multiple-Token Mode of Operations............15
1.5 Single-Token Operations .................... 16
1.6 Single-Packet Operation Mode ............... 19
1.7 Performance Evaluation ..................... 20
1.8 Delay Analysis for Non-overlapping Arrivals 24
1.9 Exponentially Distributed Packet Lengths . 25
1.10 Fixed Length Packets ....................... 27
1.11 Comparative Performance Evaluation .... 28
2. TOKEN BUS NETWORKS..........................33
2.1 Basic Operations .......................... 33
2.2 Performance Analysis ....................... 34
2.3 Non-overlapping Arrival Statistics .... 40
2.4 Exponentially Distributed Packet Lengths . 40
2.5 Fixed Length Packets ....................... 41
3. ETHERNET.....................................44
3.1 Basic Operations .......................... 44
3.2 Delay Analysis..............................50
vii


4. COMPARATIVE PERFORMANCE, ETHERNET, TOKEN
BUS AND TOKEN RING ..........................60
5. DISCUSSION AND CONCLUSION....................65
APPENDIX
A. Computer programs ......................... 69
BIBLIOGRAPHY ..................................... 83
viii


FIGURES
Figure
1.1 Token Ring network........................... 5
1.2 Pattern of activities for a Token Ring network 10
1.3 Performance of 50-stations Token Ring ... 22
1.4 Performance of 100-stations Token Ring ... 23
1.5 Comparison of non-overlapping and Poisson
statistics for multiple-token operation mode 31
1.6 Comparison of non-overlapping and Poisson
statistics for single-token operation mode . 32
2.1 Token passing bus..............................35
2.2 Performance curves for the Token bus .... 39
2.3 Comparative performance curves for the Token
bus. Non-overlapping and Poisson statistics . 43
3.1 Ethernet network ............................. 46
3.2 Calculation of virtual transmission time for
CSMA/CD........................................47
3.3 Worst-case detection of collision ............ 48
3.4 Tradeoff performance curves for Ethernet . 59
4.1 Comparative performance curves for Ethernet,
Token Ring and Token passing bus networks . 63
4.2 Comparative performance curves for Ethernet,
Token Ring and Token passing bus networks after
increase of normalized propagation delay "a" 64
ix


INTRODUCTION
In order to quantify a performance of the local
area networks it is necessary to define appropriate
performance criteria. The quantitative study of the
local area networks is usually carried out on two
levels: user level and network level. An obvious
and important performance measure on user level is a
response time. This is the time to transmit a packet
correctly from one user to another and receive a
response.. Due to stochastic behavior of a data flow
in computer communications networks useful
performance measures are defined as average values.
Therefore the user response is determined as the
mean (average) value.
In order to determine the average response time for
a specific network two procedures should be
implemented:
1. Define the average transfer delay for one-way
packet through the network (including physical
media and interfaces) as a function of load and
packet size.
2. Determine the delay for the user/station
interface.
1


After obtaining the information in steps 1,2 it is
possible'to compute average user-to-user response
time.
Average transfer delay is very significant measure
of performance for computer networks. This is the
time that a packet must wait in the interface buffer
before transmission plus the time required for the
packet to travel through the network to the station
of destination. Average transfer delay is usually
normalized value by the average channel transmission
time to obtain normalized average transfer delay.
T _TR
<|> *
Where R average transmission rate (in bit per
second)
X average packet length (in bit)
Another very significant measure of performance is
throughput. The throughput measures the average
number of bits (packets) per second that can be
processed through the network. The throughput is
usually normalized by dividing by the channel
transmission rate (in bits per second). The
normalized value of the throughput is usually
between 0 and 1.
2


kx
R
Where X input rate to a portion of a network
X average packet length (in bit)
R channel transmission rate (in bits per
second)
Since the achieving of maximum throughput and
minimum transfer delay is usually conflicting goals,
the important performance characteristic of the
local area networks is throughput versus delay
tradeoff curves.
The objective of this project is to evaluate the
performance of three basic types of local area
networks: ETHERNET, Token Ring and Token passing
bus.
The performance will be measured as throughput
versus transfer delay for different modes of
operations.
3


CHAPTER 1
TOKEN RING NETWORKS
1.1 Basic Operations
Token Ring Network (IEEE 802.5 standard)
consists of a set of stations that are serially
connected by a transmission medium (See Figure 1.1).
An access to the network is controlled by unique bit
pattern called a token that circulates in the ring.
The token can be in one of two possible states: busy
or idle (free). When the network is first activated
an idle token circulates around the ring from
station to station. A station cannot transmit a
packet until it captures the token. It then changes
the status of the token from "idle" to "busy" and
immediately starts transmitting the packet. The busy
token is then incorporated as part of the header of
data transmitted on the ring by the station. Thus
other stations on the ring can read the header, note
the busy token, and refrain from transmitting.
When there is no free token in the network the
station wishing to transmit, must wait until the
frame on the ring will make a round trip
4


Figure 1.1 Token Ring network.
5


and be purged by a transmitting station. The
transmitting station will insert a new free token on
the ring when both of the following conditions have
been met:
1. The station has completed transmission of
its frame.
2. The busy token has returned to the station.
When a transmitting station releases a new free
token, the next station downstream with data to send
will be able to seize the token and transmit its
packet. Therefore, the use of a token guarantees
that only one station at a time may transmit. Let us
consider the situation when there are no stations in
the ring that require transmission. The information
in the ring is processed serially through the
interface of each station. Therefore each station
introduces the propagation delay, i.e., the time
required to repeat the frame at a station. This
delay is termed the station latency. If all stations
are in listen mode, the token will circulate around
the ring in a time equal to the sum of all station
latencies plus the sum of all propagation delays
(time required for the frame to travel between two
stations). This composite time is called ring latency.
6


1.2 Preliminary Definitions
In order to obtain the average transfer delay
for the Token Ring network it is necessary to make
several assumptions:
* The arrivals are equally probable at any
station on the ring.
* The arrival process to each station is Poisson
with average arrival rate to each station X
packets / second.
* The average distance between each sending and
receiving stations is one half of the
distance around the ring.
* The stations are spaced so that the propagation
delays between each two stations are equal and
given by t/M where t is the total ring
propagation delay and H is the number of
stations.
* The station retains use of the ring until it
has transmitted all the data stored in the
transmit buffer (it is called an exhaustive
service).
7


Let Nm be the average number of packets with average
length X bits stored at a particular station when a
free token arrives at this station. Then the ring
channel with the capacity R is available to this
station for transmission. Since the exhaustive
service is assumed, the time required to empty the
station buffer (or average service time) can be
expressed as,
T=NmX/R (1.1)
After the buffer is emptied access to the channel
will be given to another station in a time equal to
a walk time, w. The time necessary to complete the
transmission of the information stored in the
interface buffer of the particular station is
defined as an average cycle time and can be
expressed as,
Tc = M[NmX/R + W] (1.2)
since the average time required to empty the buffer
and transfer to the station of destination are
assumed to be equal. The average number of packets
waiting transmission is defined by the average
arrival rate X packets/second, and the average cycle
8


(1.3)
time Tc as
Nm = XTC
Using (1.1) and (1.2) we can derive an expression
for Tc as
Mw
1 -MkX/R
(1.4)
The throughput S is defined as the ratio of the
total average arrival rate to the total capacity of
the network.
s = MXx/R
And the average cycle time is
(1.5)
,rp MW
c 1-S
(1.6)
9


1.3 Delay Analysis.
The average waiting time, W, is the time that
arriving packet must wait in the station's buffer
before transmission. It can be divided into two
component delays:
1. The waiting delay, W,, is involved due to other
stations on the ring are being served.
2. Waiting delay, W2, in the station buffer while
that particular station is being served.
W = Wj + w2
Figure 1.2 shows the pattern of activities for a
Token Ring network.
service station 1 , Walk time v service station 1 ! Walk service service time v station M station 1
(I jOTo pT B
Tc

time
Figure 1.2 Pattern of activities for a Token Ring
network
10


From a point of view of a station i, the cycle
consists of the time when the station is being
served and the time when it is idle. Defining the
parameter
p = Ax/R (1.7)
We can express from equation (1.1) the average
service time as,
T = pTc
The remaining part of the cycle when the station is
idle is therefore, Tc (1 P) Since we have assumed
that the arrival process to each station is Poisson
with average arrival rate A packets/second then for
a large number of packets, the average time W, these
packets must wait for service is one half of the
idle interval.

(1-p) Tc
(1.8)
From (1.4) and (1.7) we can express Wx in terms of
more basic parameters:
w Mw{l-p)
1 2(1 -Mp)
(1.9)
11


The walk time w for Token Ring networks consists of
a propagation delay t/M plus the station latency B/R
seconds.
W = B/R + T/M = T'/M (1.10)
Using Equation (1.5) we can define the time delay Wj
in terms of throughput:
ri,- t'd -s/m U.H)
1 2(1 -S)
The second component of the average waiting time W2
is the time that the packet must wait in the
interface buffer before being transmitted after the
station begins receiving service. In order to obtain
an expression for W2 we will consider a network with
zero walk time, i.e a station is always being served
when there are packets in the network. Therefore M
individual queues (M interface buffers in the
network) can be regarded as one cumulative queue
with one aggregate arrival rate AM. Thus the network
can be considered as the distributed M/G/l queue.
The average time delay for M/G/l queue is given by:
T- 1 + P+^Ca2 (1.12)
pC 2 p C (1 -p)
Where C average channel rate (bit/second)
1/M average message length (bit/message)
12


Therefore 1//JC denotes the average service time
(the time required to process a message over the
channel once processing begins).
To apply equation (1.12) to an average waiting time
W2 we will note that the average service time for
Token Ring network is X/R.
Since a packet length X a random variable we can
express the variance of the service time a2 in (1.12)
as (}P/R2 (X/R)2). After substitution in (1.12) we
will have:
rt (MX)X2/R2 (1.13)
2 2 (1-Mp)
Recalling the equation (1.5) we can derive the
expression of W2 in terms of throughput as
W2 =
sx2
2XR{1-S)
(1.14)
Finally, the average waiting time for Token Ring
network is:
ff_ t7(1 -S/M) ^ SX2
2(1 -s) 2XR(1-S)
(1.15)
The average transfer time for Token Ring networks is
the sum of the average waiting time, the average
transmission time and the average propagation delay.
13


The average time to transmit a packet is equal to
X/R. The average propagation delay in the Token Ring
is equal to one half of the ring latency t'/2,
since it was assumed that packets travel, on the
average, half way around the ring from source to
destination station.
Also we should define a notion of effective service
time E that is the total time starting the moment
when the channel began processing the packet until
the moment when the ring became free to process
another packet. The notation of E must be used to
compute the network throughput:
S/=MXE (1.16)
While notation S is reserved for S = M\X\R as
previously.
Thus the final expression for the average transfer
time of the Token Ring network is:
^ S& (1.17)
R 2 2(1 -s') 2E(1-S')
The average transfer delay is evaluated for
different modes of operation of the network.
There are three basic modes of operation on Token
Ring networks: multiple-token, single-token and
single-packet operations.
14


1.4 Multiple Token Mode of Operation
For multiple-token operations a new free token
is generated by the transmitting station immediately
after the last bit of the packet leaves the station.
Therefore there is always one idle token along with
several busy tokens in the ring. The network channel
remains busy transmitting the packets as long as any
station has information to transmit. The average
service time for this mode is X/R and the second
moment is X2/R2. Equation (1.18) gives average
transfer delay for multiple token operations mode:
-s/m ^ sx* (i.i8)
R 2 2(1 -S) 2XR{1-S)
Average transfer delay can be derived for two
special cases: the packets have fixed length and
exponentially distributed packet lengths.
Fixed length packets.
( 5? = (x)2 )
, sx (1.19)
R 2 2(1 -S) ZX(1 -S)
15


Exponentially distributed packets lengths.
( 2? = 2 (x)2 )
T=Z+il+i!lli£/M.+JE/z. d.20)
R 2 2(1 -S) (1-5)
1.5 single Token Operations
This mode of operations requires that a
transmitting station waits for arrival of its own
busy token. It then can erase it and generate a new
token. Therefore there is never more than one token
in the ring. When the packet transmission time is
greater then the ring latency t', the station will
receive its busy token before it finished 7
transmitting. In this case, the station must erase
busy token, and continue transmitting data. Only
after the last bit of the packet left the station,
the new idle token can be generated. If the packet
transmission time is less than the ring latency, the
average transfer delay for single token mode will
differ considerably from that of multiple token
mode due to increase of the effective service time.
The effective service time is increased because the
ring channel is tied up during the periods when the
transmitting station is waiting for its busy token
16


to return, in order to evaluate the average transfer
delay for a single token operation mode, it is
necessary to define a normalized ring latency a'.
a
/_ _y
X/R
(1.21)
Average effective service time varies for packets
with fixed length and packets with exponentially
distributed lengths.
For fixed length X = X constant. Therefore if
X/R > t or a' < 1, single token operation is the
same as multiple token operation and average
transfer delay is the same as in equation (1.18).
However when a' > 1 average effective service time
is greater than transmission time X/R and is equal
to t', because the ring is idle until the busy token
is purged.
Since E = t' we can substitute S' in equation
(1.16) as
s'=Mk\'=Mk (X/R) a'=Sa' (1.22)
After appropriate substitutions in equation (1.17)
we can obtain an expression for average transfer
delay for single token operations with fixed
packet length and a' > 1 :
17


(1.23)
T_ X^ x' ^ x'd-Sa'/M) + Sa'x'
R 2 2(1 -Sa') 2(1 -5a')
When packets have exponentially distributed lengths
effective service time also becomes exponentially
distributed random variable with probability
distribution function expressed as,
1 e'Ry/x y > t'
FE(y) = (1.24)
0 y < t r
After evaluating the first and the second moments of
E we have:
E=X/Re~a,+x/
E2=(x,)2+2(X/R)2e~a(l+al) (1.25)
Substituting the results of equation (1.25) into the
equation (1.17) we will have an expression of
average transfer delay for packets with
exponentially distributed lengths in single token
operations mode:
r_ x' ^ x'[l-S(e-a'+a') /M] +/Xv S[(a')z+2(l+a') e~a' (1.26)
R 2 2 [l-S'(e_a+a/) ] R 2 [1 -S(e~a+a/)]
18


1.6 Single Packet Operation Mode
In this mode of operation only one packet at a time
circulates in the ring. A new free token is
generated after the source station had received its
packet back and purged it. Therefore there is a
delay from the moment when the last bit of the
packet is received and until the moment when the new
free token is generated. This delay is equal to r'.
The average effective service time is therefore:
E = X/R + T' (1.27)
And the second moment is:
Es= (X/R) 2+2zrX/R+ (x') 2 (1.28)
After substituting equations (1.27) and (1.28) into
(1.17) we will have an expression of the average
transfer delay for single packet operations mode:
T; .Vd-d +a')S/M) S[XI+(Rx/)z+2XRxl] (1.29)
R 2 2(1-(1 +a')S) 2RX[1- (1+aO S)
For fixed packed length the average transfer delay
is:
T/T/(l-(l +a')S/M) S(X/R) (1+a7)2 (1.30)
R 2 2(1-(1 +a')S) 2(1-(1 +a')S)
For exponentially distributed packet lengths the
average transfer delay is:
19


(1.31)
r-^T^T^l-q +a')S/M) ^S{X/R) [(1+aV+l]
R 2 2(1-(1 +a')S) 2X(1-(1 +a')S)
1.7 Performance Evaluation
In this section we will compare the performance
of tree different modes of operation of the Token
Ring network. For all modes the transfer delay is
normalized by units of mean transmission time:
T=T/(X/R). Parameters of the network are chosen
equal for all modes. The Token Ring is 2 km. long,
channel transmission rate is 5 Mbps, an average
packet length is 1000 bit. Figures 1.3 and 1.4
display the plots of average transfer delay versus
throughput, the performance tradeoff functions. The
curves show, that for all modes of operation the
average delay increases less rapidly when packets
have fixed length. However, the packet length
distribution has significant impact on the transfer
delay only when channel utilization is high
(S > 0.8). Single packet mode is least preferable
because the transfer delay is increased by the walk
time from the station of destination to the original
station. Maximum obtainable throughput for this mode
is 1/(1 + a') which is less than for other modes. In
20


order to evaluate the sensitivity of different inodes
of operation to network parameters we will change
the ring latency by increasing the number of
stations on the ring (equation 1.10). After
increasing the number of stations from 50 (Figure
1.3) to 100 (Figure 1.4) we can see that the
performance of single packet mode is deteriorating
more rapidly. At the same time, multiple token
mode turns out to be less sensitive to the change of
network parameters. However in practice this mode
has not been adopted because the use of multiple
tokens leads to more complex and unreliable systems.
i
Single packet mode has best performance parameters
when packets have fixed length. When the channel
utilization increases, the average transfer delay
levels to a fixed time and is not sensitive to the
change of network parameters. This quality makes
single packet operation mode very attractive for
most of commercial applications.
21


Delay ,T
Fixed Lengths Packets
Exponentially Distributed Packets
Figure 1.3 Performance of the 50-stations Token
Ring
22


Delay I
Fixed Lengths Packets
Exponentially Distributed Packets
Throughput* S Throughput* S
Figure 1.4 Performance of the 100-stations Token
Ring
23


1.8 Comparative Delay Analysis for Non-Overlapping
Arrivals
Earlier we have based our analysis of the
system performance on the assumption that the
packets arrive to the station in a Poisson
distributed pattern and departure times are
independent of arrivals. This assumption does not
consider the packet lengths and this may imply that
packets can overlap. However, in the real networks
overlapping of packets is not permitted. Therefore
the Poisson statistics over-estimate the actual
number of packets in the station buffer and
therefore over-estimate the actual transfer delay as
well.
In this section we will compare the performance of
the Token Ring network assuming non-overlapping
packets arrivals and the network which performance
analysis was based on Poisson statistics.
The mathematical approach and methodology of the
theory of non-overlapping arrivals nave been
developed in [5]. Therefore the derivations will not
be noted. The theory has been developed for fixed
length packets and packets with exponentially
distributed lengths. As it was mentioned in Section
24


1.3 we can consider the network as distributed
M/G/l queue. The most important parameter of a
queue's performance is the mean queue occupancy
E(n). This parameter directly affects the system
average delay time. E(n) is given by equation (1.32)
E{n) =-£ +
2
2 (1-p)
(1.32)
Where a2 variance of the number of packets
arriving in the service interval.
1.9 Exponentially Distributed Packet Lengths
We have assumed non-overlapping arrival
statistics for the station buffer. The variance the
variable length packet arrivals during the interval
(0;t) is:
$*2 aW211-6X11 (1 (133
Where Tp mean packet length
Tg mean length of the "gap" between
arriving packets.
In order to simplify this expression we will make
several assumptions. The average service time is
equal to the average packet length Tp. The average
25


service rate is then 1/Tp. The channel utilization is
then p = XTp. The average time between arrivals is
(Tp + Tg) The average arrival rate is then X = 1/ (Tp
+ Tg) Therefore the term XTg in equation (1.13) is
equal to (1 p). Finally, the variance of arrivals
in an average service time Tp is given in equation
(1.34).
Oz=p[p2+(l-p)2] (1.34)
Substituting (1.34) into (1.32) gives the mean queue
occupancy for the M/G/l model using non-overlapping
packet arrivals with variable packet lengths.
E(n) =P+P(1 p) +p3
2 2 2 (1-P)
(1.35)
The average waiting time is related to the mean
queue occupancy as E(T) = E(n)/X
Recalling the equations (1.5) and (1.7) we can
express the average waiting time in terms of
throughput as,
EiiT) E[2-3 [S'/M) +2 (S'/M) 2] (1.3
2 {l-iS'/M)
Having added E(T) to the network delay (equation
(1.11)) we will have an expression for the average
transfer delay for variable lengths packets:
26


(1.37)
T_ t'^ x'a-S'/M) +E[2-3(S'/M) +2{S'/M)2]
2 2(l-5/)
1.10 Fixed Length Packets
In this case the variance of packets arrivals
during an interval (0,t) is given in equation
(1.38).
a2^(t) =]£ n2pn(t) -Ut)
(1.38)
Using X=l/(Tp + Tg) XTp=p and XTg=l-p, this
expression can be simplified as,
a2=p(l-p)2
Thus the mean number of packets in the queue can be
obtained from (1.32) and is
i?(n)=|+|(l-p)
Z Z
(1.39)
Recalling the equations (1.5) and (1.7) and applying
the Little's theorem, we can obtain the average
waiting time in terms of throughput:
E(T) = (2-)
2 M
(1.40)
27


Therefore the average transfer delay is:
2 2(1-S,/) M
(1.41)
1.11 Comparative Performance Evaluation
In this section we compare the average transfer
delay of non-overlapping network with the network
that assumed Poisson arrivals. The analysis was
performed for multiple-token operations and single
token operation modes.
The average transfer delays of the network with
assumed non-overlapping arrival statistics and
exponentially distributed packet lengths are given
by equation (1.42)
t'(1 -S/M) X/R[2-3 (S/M) +2 (S/M) 2] (1.42)
2 2(1 -S) 2(1-{S/M)
for multiple-token operations, and
T_ t/ ^ x' (1 -S (e ~fl/+a') /M) f
2 2(1 -S{e-a'+a'))
(X/R) e~a'+xl) (2-3 {S{e-a'+a') /M) +2 (S^e^'+a') /M)2
2 (1 -S(e-*'+a') /Af)
for single-token operations.
In the case of fixed packet length the average
transfer delays are :
28


'=jr_'++X/R (2 jS j
2 2 (1-S) M'
for multiple-token operations and
t'.. t'q-ga'/M) /fl_ 5a'v
2 2(1-53') J*
for single-token operations mode.
Figures 1.5 and 1.6 display the performance tradeoff
functions for both Poisson and non-overlapping
arrival statistics. These curves show that the
networks with assumed non-overlapping arrivals have
smaller mean transfer delay that was predicted by
Poisson statistics. However if the channel
utilization increases (S>0.9) the average transfer
delays for both models become close to equal (see
Figure 1.6 for variable packets). This effect can be
explained by the fact that at high utilization the
gaps between packets shrink to zero and non-
overlapping model actually becomes a Poisson model.
In particular interest is the case of fixed packet
lengths. In this case non-overlapping model gives
lowest transfer delay which becomes close to
constant as the channel utilization increases. This
means that the network is less sensitive to the
29


increasing of the traffic. It may be concluded that
non-overlapping model is very beneficial theoretical
approach to the design of communications protocols
for Token Ring networks.
I
30


Auerage normalized delay
Multiple-token node,oar lable lengths
Multiple-token node>fixed length:
Figure 1.5 Comparison of Non-overlapping and Poisson
statistics for multiple-token operation
mode.
31


Average nornalized delay
Single-token nodejfixed packets
1.2,------------i------------,
Singletoken node variable packets
1.1
1
9>
£ B .9 {-
o
^ e.B
o
M
~ B .7
V
p.
0.6 -
o
% 8.5 -
St
e
0.4 -
0.3
0.2
N.
0.5
Throughput # S
Figure 1.6 Comparison of Non-overlapping and Poisson
statistics for single-token operation
mode.
32


CHAPTER 2
TOKEN BUS NETWORKS
2.1 Basic Operations
Token passing bus is IEEE 802.4 standard.
Figure 2.1 shows a general idea of Token bus. Also
it employs the same topology that Ethernet, the
medium access control used in this standard is
similar to Token Ring. The stations on the bus form
a logical ring; that is, the stations are assigned
logical positions in an ordered sequence, with the
last member of the sequence followed by first. Each
station knows the identity of the stations preceding
and following it. The physical ordering of the
stations on the bus is irrelevant and independent of
the logical ordering. A control bit pattern (token)
regulates the right of access. The token frame
contains a destination address. The station
receiving the token is granted control of the bus
channel for a specified time. The station may
transmit one or more frames and may poll stations
and receive responses. When the station finishes
transmitting its data, or its access time limit is
reached (whichever happens first), it passes the
33


token on to the next station in logical sequence.
The next station now ready to process data. Also the
basic principles of operation for the Token bus are
largely the same as for the Token ring, stations on
the bus are passive rather than active and thus
there is no station latency or delay. The fact that
the stations are passive has a positive implication
on reliability and a negative implication with
respect to regeneration of signals. Since token
passing is essentially a broadcast protocol, it is
possible for stations on a logical ring to receive
messages while they are not permitted to transmit,
i.e., not members of a logical ring.
2.2 Performance Analysis
There are a number of operational differences
between token rings and token buses that have
significant implication on the performance of local
area networks.
1. Token ring networks have additional transfer
delay due to the process of regeneration of the
signal at each station around the ring. This
delay does not exist on a bus because the
signal is transmitted from the end to the end
on the channel without interruption or
34


A
Figure 2.1 Token passing bus.
35


regeneration in the same manner as for a random
access bus.
2. On the token bus the token can be passed
over comparatively long distance (i.e., from
the one end of the cable to the other) in order
to satisfy the logical sequence of stations.
Therefore the propagation delay of the token
bus is longer than one of the token ring where
the token is passed from a station to its
nearest neighbor.
3. The time to transfer between stations, or
walk time for a token ring is given by equation
(1.10) as the sum of a station latency and a
propagation delay. For the token bus, however,
walk time is the time to transfer the token
plus the propagation delay between two
successive stations in the logical ring.
Recall from the Chapter 1 that the average transfer
delay is the sum of two waiting delays W, and W2. The
waiting delay W2 is involved due to other stations on
the bus is being served and the waiting delay W2 in
the station buffer while the particular station is
being served. The average transfer delay for token
36


bus network is:
, t_Mw(1-S/M) + SXZ (2.1)
2(1-5) 2XR(1-S)
The walk time, w, depends on the average propagation
delay between stations. This delay is determined by
the assumption that transfer between any two
stations is equally likely. The solution of this
problem in probability is well known, assuming that
the number of stations is relatively large and gives
approximately one-third the length of the bus as the
average spacing between randomly chosen stations, or
an average time delay of t/3 seconds. Using the
average delay of t/3 seconds, the walk time can be
expressed as
W=xt/R+T/3 (2.2)
Where Xj is the control token frame in bit.
The average transfer delay, T, can be obtained from
(2.1) by adding average propagation time t/3 and
packet transfer time X/R to yield
T_ X^_ T ^ Mw (1 -S/M) ^ SX* (2.3)
J? 3 2(1 -S) 2XR (1 -S)
For fixed length packets, X2 = (X)2 and after
37


substitution of (2.2) the expression of the average
transfer delay becomes
T_X^ T S/M) ^ t(m-S) + SX (2.4
R 3 2R(1-S) 6(1 -S) 2R(1-S)
For exponentially distributed packet lengths,
Xs = 2(X)2 and the corresponding average transfer
delay is given by
t_ x +MXt(l-S/M) ^-(m+2-3S)x (2.5
R (1-5) 2R(1-S) 6(1-5)
The curves of normalized average transfer delay T
versus throughput S are shown on Figure 2.2. The
transfer delay is normalized by units of mean
transmission time: T=T/(X/R). The bus in this
example is 2 km long, the channel transmission rate
is 10 Mbps, The token frame length is 12 bytes and
an average packet length is 950 bits.
38


Average normalized delay
Fixed packet length
Throughput,S
Uartable packet lengths
Throughput S
Figure 2.2 Performance curves for the Token bus.
39


2.3 Non-overlapping Arrival Statistics
In this section we will derive the expressions
of the average transfer delay for the Token bus
network with assumed non-overlapping arrival
statistics. Also we will compare the performance of
the network assuming Poisson arrival statistics and
non-overlapping statistics. The analysis will be
carried out for both cases of packet length
distribution: fixed length and exponentially
distributed lengths.
2.4 Exponentially Distributed Packet Lengths
As we recall from the Chapter 1, a local area
network channel can be considered as a M/G/l queue.
The average number of packets waiting service in
this queue is
S(n)=| + |(l-p) +
P3
2(l-p)
(2.6)
Recalling the expression of the variance of non-
overlapping arrivals given in equation (1.34) and
applying the Little's theorem we can write down the
equation of the average waiting time:
40


(2.7)
_ (2-3 +2 ( 2) )
E(T)=j-______M sM
2 (1-)
M
Having added the propagation time t/3, packet
transmission time X/R and the network delay to
E(T), we will obtain the expression of the average
transfer delay of the Token bus network with assumed
non-overlapping arrival statistics for exponentially
distributed packet lengths case.
S S2
X^-Z^MjXjR+x/2) (1S/M) + x (2~3M+2(M }) (2.8
R 3 2(1-S') R 2(1-)
1 M
2.5 Fixed Length Packets
In this case the average number of packets
waiting service in the M/G/l queue is given in [1]
and is
E(n) (1-p) (2.9)
Recalling the equations (1.5) and (1.7) we can
express the average waiting time in terms of
throughput:
41


E(T) = (2-)
2 R M
(2.10)
Now we can obtain the expression of the average
transfer delay of the Token bus network for fixed
packet length case.
T_X, X MlXjR+x/Z) (1 -S/m X S) (2.
R 3 2(1-5) 2 R M
Figure 2.3 displays the performance tradeoff
functions for both Poisson and non-overlapping
arrival statistics. The comparisons show the results
that are similar to the Token Ring networks. The
network with assumed non-overlapping arrival
statistics has smaller transfer delay that was
predicted by Poisson statistics. For high channel
utilization the difference between delays becomes
negligible due to the fact that at high utilization
gaps between packets shrink to zero and non-
overlapping statistics becomes close to Poisson
model. Therefore the non-overlapping arrival
statistics approach also can be applied to the
problem of the design of Token bus protocols.
42


Average normalized delay!
Variable packet lengths
zee 1
IBB -
160 -
140
1Z0
100
80
60 1
40 Jr
20 P / 'f- //
0
8 0.5 1
Throughput's
Fixed packet length
Figure 2.3 comparative performance curves for
the Token bus. Non-overlapping and
Poisson statistics.
43


CHAPTER 3
ETHERNET
3.1 Basic Operations
Ethernet is IEEE 802.3 standard. Figure 3.1
shows the general idea of Ethernet. In terms of
topology it is a bus network. All the devices are
connected to the main coaxial cable via
transceivers. Ethernet is an example of baseband
network, only one computer at a time can use the
network. When a computer wants to transmit some data
on the network, it first must determine if anyone
else is using it. If so, it must wait. If not, it
will start transmitting the data while still
listening to the channel. This is done to check that
the data being transmitted is not being corrupted,
the most probable reason for which is another
computer on the network transmitting data at the
same time. This is known as a "collision". If the
collision occurs, then both computers must give up
and try again later. They wait a random time
interval before trying to send the data again. This
process is known as CSMA/CD (Carrier Sense Multiple
Access / Collision Detection). There is a number of
CSMA/CD operation modes. They differ as to how they
handle the channel access if the line is sensed
44


busy. In a non-persistent mode the following
algorithm is carried out.
1. If the channel is sensed idle,the packet is
transmitted;or
2. If the channel is sensed busy, the station uses
the backoff algorithm to reschedule the packet to a
later time. After the backoff the channel is sensed
again and this algorithm is repeated.
In a p-persistent scheme a station will resume to
transmit data with a probability p once the channel
becomes idle. Therefore the station will postpone
the transmission for the end-to-end propagation
delay interval t with a probability (1-p).
Ethernet standard uses 1-persistent scheme, the one
in which the station attempts the transmission as
soon as the channel is sensed idle. If a collision
is detected and transmission aborted, the station
will attempt a retransmission after a random time
interval. This random interval is doubled each time
the collision is detected, up to some finite value
when the station gives up and notifies upper levels
about transmission failure. This doubling of the
transmission interval is called a binary backoff.
45


A
Figure 3
1 The Ethernet network
46


By focusing on stations A and B (Fig 3.1) we can get
maximum or worst-case time required to transmit
data. All components of this time are shown in
Figure 3.2.
X/R
2r
szr
£ zr
Figure 3.2 Calculation of virtual transmission time
for CSMA/CD.
This time consists of a time required to transmit a
packet X/R, plus a time r required to sense
successful completion of the transmission, plus
multiples of 2r units of time required to resolve
collisions, once detected. CSMA/CD has a vulnerable
period r seconds long. If a station begins
transmitting, another station cannot detect it (and
hence defer or back off its own transmission) until
after the propagation delay of r seconds. If the
collision occurred between stations A and B, then in
the worst case it takes A and B 2t seconds to detect
the collision and immediately turn off their
transmissions.
47


A B
T Imo

Figure 3.3 Worst-case detection of collision
As it shown in Figure 3.3, station A starts
transmitting a packet at some initial time. Just
before A's packet arrives at B,B starts its own
transmission. This is a case of collision which A
can detect only after the transfer delay r seconds.
Therefore the total time to detect a collision is 2r
seconds. If we denote an average number of
retransmissions while the collision occurs as J then
it would take 2tJ units of time to resolve the
collision. The total time to transmit a packet is:
tv=m+'z+2sJ=m[l+a (1+2J) ]; a=^/m ^
where m=X/R packet transmission time. In order to
find average number of retransmissions we will
assume that a length of collision interval
(see Figure 3.2) is geometrically distributed in
units of 2t with parameter v. Therefore the
collision interval is 2t seconds long with
48


probability v, two 2t units long with probability
p(l-p), three units long with probability p(l-p)2 and
so forth. Thus the collision will be resolved after
the interval of 2t seconds with the probability p.
Given this assumption the average number of
retransmissions will be:
go
J-=£ kv (l-v)M=l/v
*=i *J z
Let's assume that n stations attempt the
transmission during the same 2t time interval, the
probability of exactly one station transmitting in
2t interval is p. The probability of successful
transmission of one station is therefore
j=np (1-p)nI (3.3)
If p=l/n and n 1
v = (l- )n (3.4)
n
Thus the maximum probability of resolving the
collision is equal to e'1 and equation (3.1) becomes:
tv=m[1+a (l+2e) ]
(3.5)
49


Knowing minimal virtual transmission time tv we can
find maximum possible channel arrival rate
K** f l/tv (3.6)
Recalling equation (1.7) for channel utilization p
we can express maximum channel throughput as:
Sx~km< l+a(l+2e)
1+6.44a
(3.7)
where a = T/m =t/(X/R) is a normalized propagation
delay.
Therefore better channel utilization is obtainable
for smaller a, i.e. if the bus is relatively short,
so that t is small, the packet length is relatively
long and the channel bit rate is not too high.
3.2 Delay Analysis
In this section we will evaluate the average
transfer delay for SCMA/CD networks. In order to
accomplish this task we shall use the embedded
Markov chain model approach which was developed in
[3]. The state of the model is the number of packets
in the system. A key element of the analysis of the
embedded Matkov chain is the arrival process. Let
Ii+1 denote the idle interval after transmission of
the i'th packet, and Ci+, be the contention period
50


(the period when two or more stations try to
transmit simultaneously). Let nj indicate the number
of packets in the system after the departure of i'th
packet. Let a^, denote the number of packets that
arrive in the interval Ij+i+Ci+, and bi+, denote the
number of packets that arrive during the
transmission of the (i+l)st packet. Now we can find
the state equation of the system at the embedded
points:
ni*l=ni+ai*l +bi +1 1
(3.8)
In this section we consider the case when the
arrival statistics is assumed to be Poisson. The
probability of j arrivals in the slot of T = 2t
seconds is therefore :
pj=
e~XT(kT) i
-7 I
.7=1,2, . .
(3.9)
The conditioned probability of j arrivals given
there is one arrival in the slot is
p'r-
pj
(i-p0)
(3.10)
The probability of one arrival during the interval
Ii+1+Ci+1 given H; = 0 is:
51


(3.11)
P[ai+1=l / i2i=0] =P'r
p[&!+!= j+k / i2i=0] =P,jRk
In nj=l successful transmission begins immediately
and there is neither idle nor collision interval. We
have
P[ai+i=0/ni=1] =1
(3.12)
If there are more than one packet in the system
after departure of i'th packet, i.e if nj > 1, there
is no idle interval, but there is a collision
period. In this case we have
PlS-i+i-k/nj)!.] Rk (3.13
Where Rk indicates the probability of k arrivals
during a contention period. The duration of the
contention period is assumed to be exponentially
distributed given by this equation:
Pr \.Ci+1=kT/collision] = (l-v)*_1v (3.14
Where Ci+, denotes the duration of the (i+l)th
collision period and v is the probability of
successful transmission. Since packets arrival
statistics is assumed to be Poisson we can find the
probability generating function of the number of
arrivals:
52


R(z) =v [e*r(1 z) (1-v) ] -1 (3. IE
The probability generating function of the number
of packets arriving during the transmission if the
i'th packet ( bi+, in equation (3.8)) is derived in
[5] and can be expressed as:
B(z) (1-z)) (3.16
where ££(s) is the Laplace transform of the density
of the time required to transmit a packet.
The probability generating function of the system
state is defined as
Pi(z)=E[zIil]='£zkP[ni=k]
k=0
Finally the probability generating function for
the number of packets in the system can be derived
from the system state equation (3.8). Let
qy= P(Hj=j)
and
j=0
Then we can write down the system state equation as:
53


Qi*i=E(z
ni+ai+i+*i-M-1
= ( qQ\.zP'i+R{z)Y^P jZJ]+-
J= 2
+22 (2) £^(2) i?(2) {q^+q^z.
(3.18)
If the average arrival rate to the system is less
than the average departure rate, i.e X(m + t +T/i>) <
1, then there is a steady-state solution and we have
lim 0itl(2) =lim Q{z) =Q(z)
(3.19)
After solving the equation (3.18) for Q(z) we have
Q(z) =-
( q0 [P\z+R(2) ^ P'jZ j] +zq1-R(2) (q0 +qxz) )B(z)
3=2
(3
z-R(z) B(z)
As we can see in equation (3.20) the probability -
generating function for the number of messages in
the system is expressed in terms of two unknowns, q0
- the probability of zero packets in the system and
qx the probability of one packet in the system.
The event that the system is empty is the union of
two disjoint events:
1. System is empty at the last embedded point
and only one arrival in the slot that ended the
idle period.
.20)
54


2. One packet in the system at the last point
and no new arrivals during the packet
transmission.
These conditions lead to the equation
q0(l-e'XT) =q0XTe~KTB(0) +g1.B(0) (l-e'AT)
or
q1B(0)=q0[ i-^.eB(0) 3 (3.21)
1-e
Where B(0) is the probability of no arrivals during
the transmission period. We let z=l in the equation
(3.20) . Normalized conditions Q(1)=1,B(1)=1 and
R(l)=1 combined with the equation (3.21) will yield
the equation of probability of none packets in the
system.
Q=_______1 -X(T/\+m+x)_____ (3.22)
0 [XT/(l-e-XT)] ~[XT/vB(Q)]
where m is the average number of slots to transmit a
packet.
The average number of packets in the system can be
derived from the equation of the probability -
generating function, Q'(l), using the results of
(3.20) ,(3.21) and (3.22). After applying the
Little's theorem we can write down the equation of
55


average transfer delay for SCMA/CD protocols.
T==jz?+t+2t ( +1/v)
2
-(
1-e'
2 [B(0) v-(l-e_2iT)
) [2/X+2tv-6t]
(3
^ X [mz+2mx+x2+2 (m+2x) (2t/v) +4t2 (1+2 (1-v) /v2]
1-X (jn+T-2x/v)
As in the case of performance studies of Token Ring
networks the transfer delay is normalized by the
units of the average packet transmission time
m = X/R. The final expression of the average
normalized transfer delay of the Ethernet network is
given by the equation (3.24).
T/ (X/R) 1 WiOM4e+2)a+5a*+4e(2e-l)a*] tl2
2 (l-p[l+(2e+l) a])
(l-e-2ap) ( +2ae_1-6a)
__________P__________
2 [Fp(X) e-^-l+e"2^]
+ a
(3
Where a/2 is the normalized average source-
destination, propagation time comparable to the term
t'/2 in the,equation (1.17) for the Token Ring. The
function Fp(X) is the Laplace transform of the packet
length distribution function f(t)
.23)
.24)
56


Fp(X) =ffU) e'ktdt
(3.25)
o
when packets have deterministic (fixed) length
and for exponentially distributed packet lengths
The tradeoff performance functions for Ethernet are
shown on Figure 3.4. These curves show that the
performance CSMA/CD is strongly dependent on the
normalized transfer delay, a=r/(X/R). As indicated
for a=0.01 saturation is quite close to unity and
the system behaves like an M/G/l queue and Ethernet
performs very well up to relatively high throughput.
After increasing the parameter a (for example we
have increased the length of the bus or we have
increased the channel transmission rate) the
performance of the system has been affected
tremendously. This becomes apparent if we recall
equations (3.6) and (3.24). From the denominator of
the first term of equation (3.24) we can see that
when the throughput p=Xx/R approaches to its maximum
FpU)=e~* ; -|- =1
(3.26)
(3.27)
57


value as denoted in equation (3.6) the average
transfer delay becomes increasingly unbounded. The
same effect takes place if we decrease the average
packet length. Parameter a is increased again ( in
our case from 0.01 to 0.1 ) and the system
performance deteriorates for relatively low
throughput. This can be explained by the fact that
the carrier sense and collision detection
mechanism brake down as the packet length X
decreases, approaching the end-to-end delay t.
Relatively more collisions take place and the
performance deteriorates much faster. For low
channel utilization (small p) the average transfer
time approaches to the minimal value of
in=W2; P-0 (3.2S
Thus during the low traffic in the channel the
station can transmit the packet immediately with no
waiting and very little probability of collision.
58


Average normalized delay
Uartable packet lengths
Fixed packet length
Throughput S
s
TS
o
N
e
h
ft

Throughput#S
Figure 3.4 Tradeoff performance curves for Ethernet.
59


CHAPTER 4
COMPARATIVE PERFORMANCE, ETHERNET, TOKEN BUS AND
TOKEN RING
In this section we will compare the tradeoff
performance functions for the Ethernet Token bus and
Token Ring networks. The curves are shown in the
Figure 4.1 iand 4.2. It is apparent that for low load
the performance of all models does not differ
significantly. However the results do differ
significantly in the range of operations
0.2 < S < 0.8. Here delays differ by factor 2 to 3.
The average transfer delay of the Token bus is
I
larger than the Token ring and Ethernet because of
significant increase of transfer delay for this
protocol. The token frame must be transmitted to the
next station in logical sequence and processed by
the receiving station. Therefore the time to process
the token is included in the transfer delay. It
would appear from these results that the Token Ring
is to be preferred to Ethernet and Token bus.
However the CSMA/CD strategy which is implemented in
Ethernet is much simpler. It is also more reliable
because the stations are connected to the common bus
60


via the passive taps. Therefore the failure of one
station will have no effect on the operations of the
network. Also additional stations can be connected
to the network without interrupting normal
operations. Ethernet is a good practical solution to
the local area network problem for small networks
that operate at relatively moderate bit rates with
many highly bursty stations connected. The
performance of Ethernet is good unless a lot of
stations are trying to use it at once (throughput is
not too high). When loading does increase,the
performance deteriorate rapidly and the transfer
delay becomes unbounded. At the same time the
topology of the Token Ring makes this network less
reliable than Ethernet. All stations on the Token
Ring are linked to the channel via serially
connected active repeaters. This makes network more
vulnerable to the failures of the each station. Also
the process of adding or removing the additional
equipment to the network becomes disruptive to the
normal operations of the network.
Figure 4.2 shows the performance tradeoff functions
after we have changed the network parameters. The
Ethernet turns out to be most sensitive to the
change of channel parameters (such as the increase
61


of the normalized propagation delay a). As we have
stated earlier, a=r/(X/R). Here we have obtained
the increase of parameter a by increasing the
channel transmission rate R from 10 mbps to 100
mbps. As we can see on the Figure 4.2, the network
transfer delay becomes unbounded for lower
throughput for the Token Ring and Ethernet while the
performance of the Token bus has been improved
significantly.
The Token bus protocol combines the advantages
of both the Ethernet and the Token ring. It has
simple topology and reliability of the Ethernet and,
at the same time, it does not have the throughput
bounds which is inherent to CSMA/CD. The
disadvantages of this protocol, such as
comparatively large transfer delay, can be overcome
by implementing a high data-rate communication
media, such as optical fiber.
62


Delay ,I
Variable packet lengths
Fixed packet length
Figure 4.1 Comparative performance curves for
Ethernet,Token Ring and Token passing bus
networks.
63


Delay jT
450
Fixed packet length
Variable packet lengths
Throughputj S
Throughput, S
Figure 4.2 Comparative performance curves for Ethernet,
Token Ring and Token passing bus networks
after increase of normalized propagation
delay a''.
64


CHAPTER 5
DISCUSSION AND CONCLUSION
The key characteristics of the LAN performance
is the average transfer delay and the throughput. In
order to achieve a good performance, a local area
network should combine low transfer delay with high
throughput which are conflicting goals. Therefore
the performance is usually evaluated as transfer
delay versus throughput tradeoff functions.
The performance of Token Ring network is
evaluated in Chapter 1. Multiple-token mode of
operations of the Token Ring seems to have best
performance parameters when packets lengths are
exponentially distributed. However this mode is
less reliable because the use of multiple tokens
leads to more complex systems. Single-token mode has
the best,performance parameters when packet lengths
are deterministic (fixed). For this mode the average
transfer delay is close to constant for all range of
throughput. Therefore the network is less sensitive
to the increase of traffic. This is why the single-
token mode is adopted by most of commercial
applications.
65


The performance of the Token passing bus was
evaluated in Chapter 2. The delay study show that
the performance of this type of LAN strongly depends
on the channel propagation delay. Due to the fact
|
that the token frame is transmitted to the next
station in logical sequence which can be located on
the other end of the bus, the propagation delay can
have a significant impact on overall network
performance;. If the channel length is comparatively
long and this transmission rate is not too high, the
performance of the Token passing bus is lower than
the performance of the Token Ring or Ethernet.
However the Token passing bus does not have the
throughput bounds inherent to other types of LAN.
The use of high data-rate communications media, such
as optical fiber can improve the network
performance.
The performance of Ethernet is studied in the
Chapter 3. This is CSMA/CD type of network. It was
shown that this protocol has comparatively good
performance parameters for low throughput. However
the network performance deteriorates very rapidly
when the channel parameters have been changed. Any
increase of the channel transmission rate induces
the unbounded increase of the average transfer delay
66


for lower throughput. However a simple topology and
reliability make Ethernet very attractive for many
of commercial applications of LAN.
All existing studies of local area networks
performance were based on the assumption that packet
arrivals follow Poisson statistics and that
departure times are independent of arrivals. This
assumption does not consider the packet lengths and
this may imply that packets can overlap. However all
real protocols do not allow overlapping of packets.
Thus the data link level protocols based on Poisson
arrival statistics over-estimate the actual number
of packets in the station buffer and therefore over-
estimate the average transfer delay as well. In
Chapters 1 and 2 we have studied the performance of
the Token Ring and Token passing bus assuming non-
overlapping arrival statistics. The theory of non-
overlapping packet arrivals has been developed in
[5]. The studies show the decrease of the average
transfer delay for the networks which arrival
statistics has been assumed to be non-overlapping in
comparison with Poisson arrival statistics.
The best performance have the networks where packets
lengths are deterministic (constant). Therefore non-
overlapping, packets arrival model offer a good
67


theoretical alternative for the design of
communications protocols for local area networks.
68


APPENDIX A
COMPUTER PROGRAMS
A.l Performance of the Token Ring
clc
echo on
% TR.M BY LEONID SHVARZBERG
% this program computes and plots performance
% characteristics for
% the Token Ring network with following parameters:
% Ring length 2 km
% Average packet length 1000 bit
% Channel bit rate 10 Mbps
% The ring performance is evaluated for
% multiple-token,single-token and single-packet
% operation modes
% for fixed lengths packets and packets with
exponent i a1ly
% distributed lengths
pause % press any key to continue ...
S = [0:0.001:0.99]; %define throughput range
X=1000; %this is average packet
length(bit)
R=10*10^6; %define the channel bit rate
(Mbps)
M =input('enter:number of stations= ')
%the number of stations
%on the ring
tau = 5*10A(-6); %define the propagation
delay
%(microseconds)
B = 2; %the length of the ring
(km)
taul=tau + M*B/R; %here we compute the ring
latency
%(microseconds)
mtf=(X/R)+(taul/2)+(taul*(1-S/M))./(2*(1-S))+(S*(X/R
))/(2*(1-S));
%here we compute the average
transfer
operations
%delay for multiple-token
%mode and fixed length packets
MTF=mtf/(X/R); %here we compute the average
%normalized transfer delay
mte=(X/R)+(taul/2)+(taul*(1-S/M))./(2*(1-S))+(S*(X/R
))./(i-s);
69


transfer %here we compute the average %delay for multiple-token
operations %mode and exponentially distributed %packet lengths
MTE=mte/(X/R); %here we compute the average %normalized transfer delay
al=taul/(X/R); latency %here we compute normalized ring
stf=(X/R)+(taul/2)+(taul*(1-(S*al)/M))./(2*(1-S*al))
+(S*(al*taul))./(2*(1-S*al));
%here we compute the average
transfer %delay for single-token operations
% STF=stf/(X/R); normalized %mode and fixed length packets %here we compute the average %transfer delay
b=exp(-al)+al;
c=2*(1+al)*exp(-al);
ss=[0:0.01:.. 99* (1/b) ];
ste=(X/R)+(taul/2)+(taul*(l-ss*b/M))./(2*(l-ss*b))+(
ss*(X/R)j*(alA2+c)./(l-ss*b);
transfer %here we compute the average %delay for single-token operations %mode and exponentially distributed %packet lengths
% STE=ste/(X/R); normalized %here we compute the average %transfer delay
% a=al+l;
D=(X/R)*aA2;
s=[0:0.01:.99*(1/a)];
%
spf=(X/R)+(taul/2)+taul*(1-(s*a)/M)./(2*(l-s*a))+(s*
D)/(2*(l-s*a));
transfer %here we compute the average %delay for single-packet operations %mode and fixed length packets
70


%
SPF=spf/(X/R);
average
delay
%
%here we compute the
%normalized transfer
E=(X/R)*(aA2+l);
spe=(X/R)+(taul/2)+taul*(1-(s*a)/M)./(2*(l-s*a))+(s*
E)./(2*(l-s*a));
%here we compute the average
transfer
%delay for single-packet operations
%mode and exponentially distributed
%packet lengths
%
SPE=spe/(X/R); %here we compute the
average %normalized
i %transfer delay
%
pause% press any key for plot...
clg
subplot(121)
plot(S,MTE,ss,STE,s,SPE),title('Exponentially
Distributed: Packets'),
xlabel('Throughput, S'),ylabel('Delay ,T')
text(.7,20,;SP'),text(.9,3,'MT'),text(.9,100,'ST')
subplot(122)
plot(S,MTF,S,STF,s,SPF),title('Fixed Lengths
Packets'),
xlabel('Throughput, S'),ylabel('Delay ,T')
text(.7,20,'SP'),text(.85,10,'MT'),text(.9,3,'ST')
A.2 Non-overlapping and Poisson statistics
clc
echo on
% TRSTOV.M BY LEONID SHVARZBERG
% this program computes and plots performance
% characteristics for
% the Token Ring network with following parameters:
% Ring length 2 km
% Average packet length 1000 bit
% Channel bit rate 5 Mbps
% The number of stations 50
% The ring performance is evaluated for single-token
% operations mode
71


% for fixed lengths packets and packets with
exponent i ally
% distributed lengths. Poisson arrival statistics
and
% non-overlapping model are compared
pause % press any key to continue ...
S = [0:0.001:0.99]; %define throughput range
X=1000; %this is average packet
length(bit)
R=5*10A6; %define the channel bit rate
(Mbps)
M = 50;
the ring
tau = 5*10A(-6);
B = 2;
taul=tau + M*B/R;
latency
%(microseconds)
al=taul/(X/R);
%the number of stations on
%define the propagation delay
%(microseconds)
%the length of the ring (km)
%here we compute the ring
%here we compute normalized
% ring latency
tpf=(X/R)+(taul/2)+(taul*(1-(S*al)/M))./(2*(1-S*al))
+(S*(al*taul))./(2*(1-S*al));
%here we compute the average
transfer %delay for
single-token operations
%mode and fixed length packets
%where Poisson arrivals are
assumed
%
TPF=tpf/(X/R); %here we compute the average
normalized %transfer delay
%
x=exp(-al)+al;
ss=[0:0.01:0.99*(1/x)];
y=((X/(R*exp(-al))+taul))*(2-3*(ss*x/M)+2*(ss*x/M).*
(ss*x/M))./(2*(l-ss*x));
toe=(taul/2)+((taul)*(l-(ss*x)/M))./(2*(l-ss*x))+y;
%this is the average transfer
%delay for single
%token operations mode given
%non-overlapping
%arrivals statistics
TOE=toe/(X/R); %this is normalized delay
b=exp(-al)+al;
s=[0:0.01:.99*(1/b)];
c=2*(1+al)*exp(-al);
72


tpe=(X/R)+(taul/2)+(taul*(l-s*b/M))./(2*(l-s*b))+(s*
(X/R))*(alA2 + c)./(l-s*b);
%here we compute the average
transfer
%delay for single-token operations
%mode and exponentially distributed
%packet lengths
%
TPE=tpe/(X/R); %here we compute the average
%normalized transfer delay
%
tof=(taul/2)+(taul)*(l-(S*al)/M)./(2*(1-S*al))+(taul
)*(l-(S*al)/M);
%this is the average transfer delay
for the
%system with assumed non-overlapping
arrivals %and fixed length packets
TOF=tof/(X/R);
pause% press any key for plot...
clg
subplot(122),
plot(s,TPE,ss,TOE),title('Single-token mode,
variable packets'),
xlabel('Throughput,S'),ylabel('Average normalized
delay, T'),
text(0.9,2,'N.'),text(.9,120,'P.'),
subplot(121),
plot(S,TPF,S,T0F),title('Single-token mode,fixed
packets'),
xlabel('Throughput,S'),ylabel('Average normalized
delay, T')
text(.5,.3,'N.'),text(.5,1.08,'P.')
A.3 Performance of the Token passing bus
clc
echo on
% TB.M BY LEONID SHVARZBERG
% this program computes and plots performance
% characteristics for
% the Token bus network with following parameters:
% the bus length 2 km
% Average packet length 950 bits
% The token frame length 96 bits
% Channel bit rate 10 Mbps
% The network performance is evaluated
73


% for fixed lengths packets and packets with
exponentially
% distributed lengths
pause % press any key to continue ...
S = [0:0.01:0.99]; %define throughput range
X=950; %this is average packet
length(bit)
Xt=96; %this is the token frame
length(bit)
R=10*10A6; %define the channel bit rate
(Mbps) i
M = input('enter:number of stations = ')
%the number, of stations on the ring
tau=input('enter:propagation delay= ')
tau = tau*10/v (-6) ; %define the propagation delay
%(microseconds)
B = 2; %the length of the bus (km)
tf1=(X/R) + (tau/3) + (M*Xt*(1-S./M)+S.*X)./(2 *R.*(1-S))
+(tau*(M-S))./(6*(1-S));
%here we compute the average
transfer %delay
%for fixed packet length mode
TFl=tf1/(X/R); %here we compute
%the average normalized
%transfer delay
tel=X./(R*(1-S))+(M*Xt*(1-S./M))./(2*R*(1-S))+((M+2-
3*S)* tau)./(6*(1-S));
%here we compute the average
transfer delay
%for exponentially distributed
packet 1 %lengths mode
TEl=tel/(X/R); %here we compute the average
%normalized transfer delay
tau=input('enter:propagation delay= ')
tau = tau*10A(-6); %define the propagation delay
%(microseconds)
B = 2; %the length of the bus (km)
tf2=(X/R)+(tau/3)+(M*Xt*(1-S./M)+S.*X)./(2*R.*(1-S))
+(tau*(M-S))./(6*(1-S));
%here we compute the average
transfer %delay
%for fixed packet length mode
TF2=tf2/(X/R); %here we compute the average
% normalized transfer delay
te2=X./(R*(1-S))+(M*Xt*(1-S./M))./(2*R*(1-S))+((M+2-
3*S)* tau)./(6*(1-S));
%here we compute the average
transfer delay
74


TE2=te2/(X/R);
%for exponentially distributed
%packet lengths mode
%here we compute the average
%normalized transfer delay
pause% press any key for plot...
clg
subplot(122)
plot(S,TE1),title('Variable packet lengths'),
xlabel('Throughput,S'),ylabel('Average normalized
delay, T')
subplot(121)
plot(S,TF1),title('Fixed packet lengths'),
xlabel('Throughput^'),ylabel('Average normalized
delay, T')
, i
A,4 Non-overlapping and Poisson statistics for the
Token bus
clc
echo on
% TBOV.M BY LEONID SHVARZBERG
% this program computes and plots performance
% characteristics for
% the Token bus network with following parameters:
% the bus length 2 km
% Average packet length 950 bits
% The token frame length 96 bits
% Channel bit rate 10 Mbps
% The network performance is compared for Poisson
% and non-overlapping statistics
% for fixed lengths packets and packets with
exponentially
% distributed lengths
pause % press any key to continue ...
S = [0:0.01:0.99]; %define throughput range
X=950; %this is average packet
length(bit)
Xt=96; %this is the token frame
length(bit)
R=10*10~6; %define the channel bit rate
(Mbps)
M = input('enter:number of stations = ')
%the number,of stations on the ring
tau=input('enter:propagation delay= ')
tau = tau*10A(-6); %define the propagation delay
%(microseconds)
B = 2; %the length of the bus (km)
75


tf1=(X/R)+(tau/3)+(M*Xt*(1-S./M)+S.*X)./(2*R.*(1-S))
+(tau*(M-S))/(6*(1-S));
%here we compute the average
%transfer delay
%for fixed packet length mode
TFl=tf1/(X/R); %here we compute the average
%normalized transfer delay
tel=x./(R*(1-S)) + (M*Xt*(1-S./M)). / ( 2 *R*(1-S)) + ((M+2-
3*S)* tau). / (6*(1-S));
%here we compute the average
transfer delay
%for exponentially distributed
%packet lengths mode
TEl=tel/(X/R); %here we compute the average
%normalized transfer delay
tfOV=(X/R)+(tau/3)+(M*(Xt/R+tau/3)*(1-S/M))./(2*(1-S
))+(X/(2*R))*(2-S/M);
%here we compute the average
transfer %delay
%for fixed packet length mode
TF2=tfov/(X/R); %here we compute the average
%normalized transfer
delay
C=(X/R)*(2-3*(S/M)+2*(S.*S)/M)./(2*(1-S/M));
teov=X/R+taix/3+M* (Xt/R+tau/3) (1-S/M) / (2* (1-S) )+c;
%here we compute the average
transfer delay
%for exponentially distributed
%packet lengths mode
TE2=teov/(X/R); %here we compute the average
%normalized transfer delay
pause% press any key for plot...
clg
subplot (121)
plot(S,TE1,S,TE2),title('Variable packet length'),
xlabel('Throughput,S'),ylabel('Average normalized
delay, T')
text(.9,5,'N'),text(.8,20,'P'),
subplot(122)
plot(S,TF1,S,TF2),title('Fixed packet length')
text(.9,5,'N'),text(.8,20,'P'),
76


A.5 Performance of the Ethernet
clc
echo on
% ETH.M BY LEONID SHVARZBERG
% this program computes and plots performance
% characteristics for
% the Ethernet network with following parameters:
% The bus length 2 km
% Average packet length 1000 bit
% Channel bit rate 10 Mbps
% The number of stations 50
% The network performance is evaluated
% for fixed lengths packets and packets with
exponentially
% distributed lengths
pause % press any key to continue ...
X=1000; %this is average packet
length(bit)
R=10*10A6; %define the channel bit rate
(Mbps)
M = 50; %the number of stations on
the bus
t=input('enter:propagation delay(microseconds)= ')
tau = t*lOA(-6); %define the propagation delay
%(microseconds)
B = 2; %the length of the bus (km)
a=tau /(X/R) %this is a propagation delay
%(microseconds)
S=[0.001:.01:.99/(l+6.44*a)]; %this is a thrughput
range
e=exp(1);
tell=S*(l+(4*e+2)*a+5*aA2+4*e*(2*e-l)*aA2)./(2*(1-S*
(l+(2*e+l)*a))) ;
te21=((l-exp(-2*a*S)).*((2)./S+2*a*l/e-6*a))./(2*(ex
p(-S-S*a-l)-1+exp(-2*S*a)));
te31=1+2 *e*a+a/2;
TEl=tell+te2l+te31;
%here we compute the
normalized %average
transfer delay for SCMA/CD
%network
%exponentially distributed
packet
%lengths case
tf11=S*(2+(4*e+2)*a+5*aA2+4*e*(2*e-l)*aA2)./(2*(1-S*
(l+(2*e+l)*a)));
w=exp(-2*S*a);
tf21=((1-exp(-2*a*S)).*((2)./S+2*a*l/e-6*a))./(2*(((
77


1)./(1+S)).*exp(-S*a-l)-1+w));
tf31=l+2*e*a+a/2;
%here we compute the normalized
average %transfer delay for SCMA/CD
network
%fixed packet lengths case
TFl=tf11+tf21+tf31;
t=iriput (' enter: propagation delay (microseconds) = ')
tau = t*10A(-6); %define the propagation delay
%(microseconds)
B = 2; %the length of the bus (km)
a=tau /(X/R) %this is a propagation delay
%(microseconds)
S2=[0.001:.01:.99/(l+6.44*a)]; %this is a
throughput range
tel2=S2* (l+:(4*e+2) *a+5*aA2+4*e*(2*e-l) *a~2) ./ (2*(1-S
2*(1+(2*e+l)*a)));
te22=((l-exp(-2*a*S2)).*((2)./S2+2*a*l/e-6*a))./(2*(
exp(-S2-S2*a-1)-1+exp(-2*S2*a)));
te32=l+2*e*a+a/2;
TE2=tel2+te22+te32;
normalized
%here we compute the
%average transfer delay for
SCMA/CD . %network
%exponentially distributed
packet %lengths case
tf12=S2*(2+(4*e+2)*a+5*a*2+4*e*(2*e-l)*aA2)./(2*(1-S
2*(l+(2*e+l)*a)));
w=exp(-2*S2*a);
tf22=((l-exp(-2*a*S2)).*((2)./S2+2*a*l/e-6*a))./(2*(
((1)./(1+S2)).*exp(-S2*a-1)-1+w));
tf32=l+2*e*a+a/2;
%here we compute the normalized
average %transfer
%delay for SCMA/CD network
%fixed packet lengths case
TF2=tf 12H-tf 22+tf 32 ;
t=input('enter:propagation delay(microseconds)= ')
tau = t*10A(-6); %define the propagation delay
%(microseconds)
B = 2; %the length of the bus (km)
a=tau /(X/R) %this is a propagation delay
%(microseconds)
S3=[0.001:.01:.99/(l+6.44*a)]; %this is a thrughput
range
tel3=S3*(l+(4*e+2)*a+5*aA2+4*e*(2*e-l)*a*2)./(2*(1-S
3*(1+(2*e+l)*a)));
te23=((1-exp(-2*a*S3)).*((2)./S3+2*a*l/e-6*a))./(2*(
78


exp(-S3-S3*a-l)-l+exp(-2*S3*a)));
te33=l+2*e*a+a/2;
TE3=tel3+te23+te33;
normalized
%here we compute the
%average transfer delay for
S CMA/CD %network
%exponentially distributed
packet %lengths case
tfl3=S3*(2+(4*e+2)*a+5*aA2+4*e*(2*e-l)*aA2)./(2*(1-S
3*(1+(2*e+l)*a)));
w=exp(-2*S3*a);
tf23=((1exp(-2*a*S3)).*((2)./S3+2*a*l/e-6*a))./(2*(
((1)./(1+S3)).*exp(-S3*a-l)-1+w));
tf33=l+2*e*a+a/2;
%here we compute the normalized
average %transfer
%delay for SCMA/CD network
%fixed packet lengths case
TF3=tf13+tf23+tf33;
pause% press any key for plot...
clg
subplot(121) ,
plot(S,TE1,S2,TE2, S3,TE3),title('Exponentially
distributed packet lengths'),
xlabel('Throughput,S'),ylabel('Average normalized
delay, T')
text(.3,60,'a=0.1'),text(.7,40,'a=0.05'),text(.8,30,
'a=.01'),
subplot(122),
plot(S,TF1,S2,TF2,S3,TF3),title('Fixed packet
lengths'),
xlabel('Throughput,S'),ylabel('Average normalized
delay, T')
text(.3,90,'a=0.1'),text(.7,60,'a=0.05'),text(.8,55,
'a=.01')
A,6 Comparative performance characteristics
clc
echo on
% ETHTRTB.M BY LEONID SHVARZBERG
% this program compares the performance of the
% Ethernet,Token Ring and Token Bus networks with
% following parameters:
% channel length 2 km
% Average packet length 1000 bit
% Channel bit rate 10 Mbps
79


% The number of stations 50
% The networks performance is evaluated
% for fixed lengths packets and packets with
exponentially
% distributed lengths
pause % press any key to continue ...
X=1000; %this is average packet
length(bit)
R=10*10A6; %define the channel bit rate
(Mbps)
M = 50; %the number of stations on
the bus
t=input('enter:propagation delay(microseconds)= ')
M =input('enter:number of stations= #)
tau = t*10A(-6); %define the propagation delay
%(microseconds)
B = 2; %the length of the bus (km)
a=tau /(X/R) %this is a propagation delay
%(microseconds)
S=[0.001:.01:.99/(l+6.44*a)]; %this is a throughput
range
e=exp(l);
tell=S*(l+(4*e+2)*a+5*aA2+4*e*(2*e-l)*aA2)./(2*(1-S*
(l+(2*e+l)*a)));
te21=((1-exp(-2*a*S)).*((2)./S+2*a*l/e-6*a))./(2*(ex
p(-S-S*a-1)-1+exp(-2*S*a)));
te31=1+2 *e*a+a/2;
TE=tell+te2l+te31;
%here we compute the normalized average
transfer
%delay for SCMA/CD network
%exponentially distributed packet lengths
case
tf11=S*(2+(4*e+2)*a+5*aA2+4*e*(2*e-l)*aA2)./(2*(1-S*
(l+(2*e+l)*a)));
w=exp(-2*S*a);
tf21=((1-exp(-2*a*S)).*((2)./S+2*a*l/e-6*a))./(2*(((
1)./(1+S)).*exp(-S*a-1)-1+w));
tf31=l+2*e*a+a/2;
%here we compute the normalized
average %transfer
%delay for SCMA/CD network
%fixed packet lengths case
TF=tf11+tf21+tf31;
S1=S;
s=[0:0.001:0.99]; %define throughput range
X=1000; %this is average packet
length(bit)
R=5*10A6; %define the channel bit rate
80


(Mbps)
%on the ring (microseconds)
taul=tau + M*B/R; %here we compute the ring
latency
%(microseconds)
al=taul/(X/R); %here we compute normalized ring
latency
%
stf=(X/R)+(taul/2)+(taul*(l-(s*al)/M))./(2*(l-s*al))
+(s*(al*taul))./(2*(l-s*al));
%here we compute the average
transfer
%delay for single-token operations
%mode and fixed length packets
%
STF=stf/(X/R); %here we compute the average
normalized
%transfer delay
%
b=exp(-al)+al;
c=2*(1+al)*exp(-al);
ss=[0:0.01:.99*(l/b)];
ste=(X/R)+(taul/2)+(taul*(l-ss*b/M))./(2*(l-ss*b))+(
ss* (X/R)) (al^+c)./ (l-ss*b);
%here we compute the average
transfer
%delay for single-token operations
%mode and exponentially distributed
%packet lengths
STE=ste/(X/R);
S = [0:0.01:0.99];
X=950;
length(bit)
Xt=96;
length(bit)
R=10*10A6;
%here we compute the average
%normalized transfer delay
%define throughput range
%this is average packet
%this is the token frame
%define the channel bit rate
(Mbps)
t=(X/R)+(tau/3)+(M*Xt*(l-S./M)+S.*X)./(2*R.*(1-S))+(
tau*(M-S))./(6*(1-S));
%here we compute the average
%transfer delay
%for fixed packet length mode
T=t/(X/R); %here we compute the average
%normalized
transfer delay
tl=X./(R*(1-S))+(M*Xt*(1-S./M))./(2*R*(1-S))+((M+2-3
81


*S)*tau)./(6*(1S));
%here we compute the average
%transfer delay
%for exponentially
distributed packet %lengths mode
Tl=tl/(X/R); %here we compute the average
%normalized transfer delay
pause% press any key for plot...
clg
subplot(121)
plot(S1,TE,ss,STE,S,T1),title('Exponentially
Distributed Packets'),
xlabel('Throughput, S'),ylabel('Delay ,T')
text(.55,40,'ET'),text(.89,3,'TR'),text(.8,100,'TB')
subplot(122)
plot(SI,TF,s,STF,S,T),title('Fixed Lengths
Packets'),
xlabel('Throughput, S'),ylabel('Delay ,T')
text(.6,40,'ET'),text(.8,3,'TR'),text(.8,100,'TB')
82


BIBLIOGRAPHY
1) Walter C. Giffin, Transform Techniques for
Probability Modeling, Academic Press, New York, NY,
1975.
2) Joseph L Hammond,Peter J.P.O'Reilly, Performance
Analysis of Local Computer Networks, Addison-
Wesley Publishing Company, Reading, MA, 1988
3) Jeremiah F. Hayes, Modeling and Analysis of
Computer Communications Networks, Plenum Press, New
York, NY, 1984.
4) Jeffrey Scott Meis, Non-Overlapping Queueing
Models, Master's thesis. University of Colorado at
Denver. Department of Electrical Engineering and
Computer Science. Denver, CO, 1991.
5) Douglas A. Ross, Theory of Non-overlapping Packet
Arrivals, Computer Society Press,
Washington DC, 1989.
6) Misha Schwartz, Telecommunications Networks:
Protocols, Modeling and Analysis, Addison-Wesley
Publishing Company, Reading, MA, 1987.
83