Newsgroups: comp.dcom.lans.ethernet
Path: geraldo.cc.utexas.edu!cs.utexas.edu!howland.reston.ans.net!europa.eng.gtefsd.com!news.mathworks.com!newshost.marcam.com!charnel.ecst.csuchico.edu!csusac!csus.edu!netcom.com!seifert
From: seifert@netcom.com (Rich Seifert)
Subject: Re: Capture effect on BAckoffs?
Message-ID: 
Organization: Networks & Communications Consulting
X-Newsreader: TIN [version 1.2 PL1]
References: <3e2ikf$83f@lsi.lsil.com>
Date: Sat, 31 Dec 1994 19:55:13 GMT
Lines: 67

Kumar Bhattaram - 4738 (kumarb@lsil.com) wrote:

:    I would like to know what a "capture effect" is as applied to 
:    the 802.3 back-off algorithm is.
:  
:    Specifically, does it result in unfair advantage/disadvantage to
:    particular stations?
:  
:    What is the "capture" in the effect?
:

I will give a BRIEF description of this phenomenon here, as I am (literally
at the moment) writing a "White Paper" on this (and some other subjects) for
a client. I expect to be able to publish this paper freely, and will post it
(or a pointer to it) here.

Consider a pair of stations, each with an "infinite transmit queue", i.e.,
the stations are able to sustain load on the Ethernet. (The effect occurs even
if this is not the case, but it is easier to visualize it this way.)

Assume the network is initially quiet. Now this pair of stations has their
queue of frames to send. We are guaranteed that these stations will 
experience a collision upon seeing the channel free. (They both have a frame
to send.) Each will jam, abort, and calculate a backoff.

If they pick the same number (0 or 1), they will do this again. If they pick
different random numbers (which they will do, eventually), one (let's call
it A) will get the channel, and the other (B) will keep backing off. 
Let's say that A got the channel by picking 0, and B lost by picking 1.

Now, A finishes its transmission, but both stations still have a frame to send
So we go through this again. There will be a collision. But now, it
is the FIRST collision for station A (he has reset his collision counter as
a result of successfully sending the first frame), but the SECOND for B.
So when they go to pick random numbers, A will pick in the range of
[0..1], and B will pick in the range of [0...3]. The probability that B will
win over A is only 1 in 4 (B picks 0 and A picks 1). More likely, A will
win or there will be another collision. 

Assume A wins, we go through this again. But now its even worse, since it
will be collision number ONE for A (again!), but number THREE for B!

In all likelihood, A will be able to transmit sixteen frames, and B will
lose the backoff "dice toss" every time, until B gives up and discards the
frame after sixteen attempts. Now we are back on even ground (both stations
have the same collision count), and it is fair again. (Except that B has lost
a frame...)

So, we can see that A has "captured" the network for sixteen successive
transmissions, due to having won the first (or first couple) of collision
backoffs.

:    Are there alternative proposals to the Binary exp. backoff scheme?

Yes. One important one being considered by IEEE 802 at this time is
called BLAM (Binary Logarithmic Access Method). It is fully described in a
technical report available by anonymous ftp at the University of Toronto.
(I will check my records and post the path...). The developer is
Dr. Mart Molle, currently at UC Riverside. He is also chair of the IEEE
study group working on alternative backoff algorithms. (I am vice chair.)
:  

-- 
Rich Seifert                    Networks and Communications Consulting
seifert@netcom.com              10596 John Way 
(408) 996-0922                  Cupertino, CA 95014 
(408) 996-2860 FAX

"... specialists in Local Area Networks and Data Communications systems"