how does exponential backoff algorithm help avoid collisions?

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,

My knowledge of Ethernet comes from the 80s and 90s, but I believe the exponential backoff strategy is still the same...

m asked:

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

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

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.)

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