how does exponential backoff algorithm help avoid collisions?

Have a question or want to start a discussion? Post it! No Registration Necessary.  Now with pictures!

Threaded View
Hello,
I'm reading "802.11 Wireless Networks The Definitive Guide".
I chapter 3 there is a note on contention-based access:
"If the medium is not idle, stations defer to each other and employ an orderly exponential backoff algorithm to avoid collisions."

I read about the backoff algorithm on Wikipedia and it looked like it was an algorithm designed to resend frames based on probability of concurrent events (other stations sending their own frames at the same time).

I don't quite understand how does that help with avoiding collisions (two stations sending frames at the same time).
If stations don't talk to each other (only to AP, at least in infrastructure mode), then they can't know the exact time when their respective frames are sent.

Wouldn't such random scheme cause a race condition of sorts?
I'd appreciate it if someone could explain (in detail) how backoff algorithm helps in this situation.
Thanks a lot,

M


Re: how does exponential backoff algorithm help avoid collisions?
My knowledge of Ethernet comes from the 80s and 90s, but I believe the
exponential backoff strategy is still the same...

Quoted text here. Click to load it

I think that's two parts, of which the first part is "wait until the
receiver says the channel goes idle before starting transmission."

Quoted text here. Click to load it

Not probability in the abstract, but in the particular case where a
sending station determines that a collision probably just occurred.

Quoted text here. Click to load it

Let's be sure we're discussing the same thing...

When you say "talk to each other", what matters is not the Ethernet
source and destination address or routing but the signals on the
channel.  The Ethernet backoff rule applies when a sending station is
able to detect that a collision has occurred.  In a wireless topology

        s1 ----- AP ----- s2,

the backoff only applies to s1 or s2 if they're able to detect each
other's signals.  Each station runs its receiver while transmitting and
observes the received signal strength.  If it goes above some threshold,
there must be at least one other station transmitting at the same time
and thus a collision is assumed by the sender.  If s2's signal at s1 or
s1's signal at s2 is too weak, there may be a collision at the AP, but
one or both senders won't know their packet was lost.  Then it's up to
other mechanisms (such as TCP) to request retransmission (if desired).

(Fancier rules could, in theory, be applied at the AP.  The AP
presumably hears s1 and s2 and can detect collisions from them with its
outgoing packets.  The simple approach retransmits.  If the AP somehow
knows that s1 and s2 can't hear each other, maybe it could be smart
enough to know retransmission isn't necessary, but that's an area I'm
not familiar with.  APs clearly are capable of using multiple antennas
to boost their signal in a particular direction to improve reception at
the intended destination.)


Quoted text here. Click to load it

1) Exponential backoff reduces the presented load on the channel by all
   the competing senders.  The greater the unused bandwidth, the less
   likely a randomly timed transmission will collide.

2) >2 stations may be participating in the collision.

3) For any stations not at the same N times past the initial collision,
   different backoff times should reduce the odds of another collision.

HTH,
 -WBE

Site Timeline