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: firstname.lastname@example.org (Rich Seifert) Subject: Re: Capture effect on BAckoffs? Message-ID:
Organization: Networks & Communications Consulting X-Newsreader: TIN [version 1.2 PL1] References: <email@example.com> Date: Sat, 31 Dec 1994 19:55:13 GMT Lines: 67 Kumar Bhattaram - 4738 (firstname.lastname@example.org) 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 email@example.com 10596 John Way (408) 996-0922 Cupertino, CA 95014 (408) 996-2860 FAX "... specialists in Local Area Networks and Data Communications systems"