This directory contains CSRI technical report #279:
Modelling the Exponential Backoff Algorithm
in CSMA/CD Networks
by
Zeljko Zilic and Mart L. Molle
It is a postscript file, about 40 pages long.
If you have the UNIX uncompress program, get the file report.ps.Z
Remember to transfer the file in binary mode. Uncompress, and
print on a postscript printer.
If you do not have uncompress, get the file report.ps in ascii mode,
and print it on a postscript printer.
This report was made available for anonymous ftp by: mart@csri.toronto.edu
Abstract
The medium access control protocol in Ethernet systems consists of
two parts: the 1-persistent CSMA/CD algorithm describes rules that
a ready station must follow while trying to acquire the medium, while
the binary exponential backoff algorithm determines how long a ready
station must wait before retrying after each failed attempt. Although
both algorithms are equally important in determining the actions of
each station, previous work on modelling the performance of Ethernet has
focused on the effects of 1-persistent CSMA/CD. In this work, we
describe three performance models that do incorporate the effects of
the backoff algorithm. First, we consider the domain of product-form
queueing networks, where we modify the well-known representation of
Ethernet as a load-dependent service center by Almes and Lazowska
to incorporate a more realistic service rate function. Second, we
consider the classical delay-throughput model of Sohraby et al.
We show that it can be augmented with a simple auxiliary model of the
retransmission delays, in which the number of attempts is geometric
and the mean interattempt times are determined by the backoff algorithm,
to give a good estimate of the response times except at very high loads.
And finally, we consider a detailed embedded Markov chain model of the
two station case. Although some useful results were obtained with a
truncated model (where we imposed unrealistically small limits on the
queue size at each station and on the maximum number of retransmissions
per packet), we believe that the complexity of this approach renders it
impractical. For the same computational effort, better results can be
obtained via simulation.