Path: utzoo!utgpu!news-server.csri.toronto.edu!csri.toronto.edu!mart
Newsgroups: comp.dcom.lans
From: mart@csri.toronto.edu (Mart Molle)
Subject: Re: Ethernet collisions
Message-ID: <1990Dec14.163357.2361@jarvis.csri.toronto.edu>
Summary: You have to try hard to get Ethernet to saturate at 37% utilization
Organization: CSRI, University of Toronto
References: <467@pirates.UUCP> <2184@cybaswan.UUCP> <1990Dec11.174941.12301@zoo.toronto.edu> <1990Dec14.191255.20529@freedom.msfc.nasa.gov>
Date: 14 Dec 90 21:33:57 GMT
Lines: 67

In article <1990Dec14.191255.20529@freedom.msfc.nasa.gov> cornutt@freedom.msfc.nasa.gov (David Cornutt) writes:
>The percent utilization of the channel capacity of an Ethernet (or any
>CSMA-type network) depends not so much on the total volume of traffic as
>on the number of nodes that have traffic ready to transmit simultaneously. 
>As Henry Spencer noted in a previous article, an Ethernet with only one
>node transmitting can get pretty close to 100% utilization.  (Such
>situations do occur; we have an application here where there may be about
>70 nodes on a net, but only one or two nodes generating the lion's share of
>the traffic.)  The limiting factor is the probability of getting a
>collision, which is roughly proportional to the number of nodes that are
>generating large amounts of traffic.  There is a derivation in the
>Tannenbaum book (*Computer Networks*, second edition, Prentice Hall, 1988)
>which can be expanded to show the expected utilization for n number of
>nodes transmitting (or attempting to) simultaneously.  The theoretical
>worst case occurs about n = 100, where the channel utilization is down to
>about 37%.  (I have seen values close to this in a campus network that I
>once worked on.)  In practice, an Ethernet starts to break down at this
>point as controllers begin giving up due to exceeding their max retry
>settings.

Pay no attention to Tananenbaum's calculation of Ethernet throughput.  It is
a gross simplification, based on a model first put forward by Metcalfe and
Boggs in 1976 that assume slotted operation, ``global queue in the sky''
backoff algorithm, etc.  Also, you've neglected to include their full model
which includes the effect of packet lengths.  Basically, this model says
the channel consists of a repeating pattern of ``cycles'' each of which
consists of a run of [short] ``wasted'' slots (whose analysis is assumed
to be the same as slotted Aloha) followed by a single [long] ``useful'' slot.
The 37% figure you quote above is for minimal-length packets, where ``useful''
slots are the same size as ``wasted'' slots and the whole thing degenerates
into slotted Aloha.  If you make the ``useful'' slots bigger (i.e., you put
a non-trivial amount of data into each packet), then the model predicts
much higher attainable throughputs.  For example if the ``useful'' slots
are 1/a times longer than ``wasted'' slots, the capacity is about

	1/ (1 + a * (e-1)),

where e is the base of the natural logarithm and 1/e is the capacity of
slotted Aloha.

If you want a more accurate analysis of the throughput for unslotted
1-persistent CSMA/CD used in Ethernet, go read the articles by Sohraby,
Molle and Venetsanopoulos, and by Takagi and Kleinrock, in IEEE Transactions
on Communications, February 1987.  (BTW, neither paper appears in the 
widely referenced ``Myths and Reality'' paper from Sigcomm 88, which
includes an earlier paper by Takagi and Kleinrock that gave totally wrong
answers due to errors in the analysis....)  These papers show that CSMA/CD
can get very high channel efficiencies even in the limit of infinitely
many active stations.  However, they fail to include the truly bizarre
influences of the truncated binary exponential backoff algorithm used
on Ethernet and thus are not the last word on the subject.

>There are ways to make CSMA networks get better utilization under these
>conditions by introducing a random go/no-go decision into retransmissions. 

[Description of p-persistent CSMA deleted]

There are lots of other CSMA protocols in the world that look better than
Ethernet.  I don't think p-persistent stands out in any way in this group.
Obviously, there are other reasons (like compatibility) that make people
stick with the standard...

Mart L. Molle
Computer Systems Research Institute
University of Toronto
Toronto, Canada M5S 1A4
(416)978-4928