Exponential Backoff in Ethernet

Imagine a bustling conference room where multiple participants are eager to speak. When two people start talking simultaneously, a social protocol kicks in—typically, both pause, perhaps exchange an awkward glance, and one yields to the other. But what if three, five, or even fifty people all tried to speak at once? What rules would govern who speaks next, and how would the system prevent everyone from repeatedly interrupting each other?

This is precisely the challenge facing Ethernet networks. When multiple stations detect a shared medium is idle and transmit simultaneously, a collision occurs—both transmissions are corrupted and must be retried. The genius of Ethernet lies not in preventing collisions entirely (which would sacrifice efficiency) but in resolving collisions gracefully through a mechanism called Binary Exponential Backoff (BEB).

Before diving into the specifics of Binary Exponential Backoff, we must understand why backoff is necessary in the first place. This requires examining the fundamental problem that CSMA/CD networks face after detecting a collision.

The Collision Detection Phase:

When a station transmits on an Ethernet network, it simultaneously monitors the medium for signals that indicate another station is also transmitting. If the station detects a collision (the combined signal amplitude exceeds what a single transmission would produce), it immediately:

1. Ceases the current transmission
2. Sends a jam signal (32 bits of alternating 1s and 0s) to ensure all stations detect the collision
3. Prepares to retransmit the frame

The critical question then arises: When should the station attempt retransmission?

Why Random Delay is Essential:

To break the symmetry that causes repeated collisions, each station must wait a random amount of time before retransmitting. This randomization ensures that the probability of all stations choosing the same moment to retransmit is negligible. However, choosing the right range for this random delay is non-trivial:

• Too narrow a range: Multiple stations still likely to choose similar delays, causing repeated collisions
• Too wide a range: Stations waste time waiting unnecessarily when the medium is free, reducing throughput
• Fixed range: Cannot adapt to varying levels of network congestion

This analysis reveals a fundamental insight: the backoff range must adapt dynamically to network conditions. Binary Exponential Backoff provides exactly this adaptation, using collision history as the signal for congestion level.

The term exponential in Binary Exponential Backoff refers to how the range of possible waiting times grows with each successive collision. To appreciate this design choice, we must understand the mathematical properties that make exponential growth uniquely suitable for collision resolution.

The Contention Window:

In Ethernet, time is measured in slot times—the fundamental unit derived from the round-trip propagation delay of the network (for 10 Mbps Ethernet, one slot time equals 51.2 μs). The contention window defines the range from which a station randomly selects its waiting time:

• After collision n, the contention window spans from 0 to 2^n - 1 slot times
• The station randomly selects an integer k from this range
• The actual waiting time is k × slot_time

Why Exponential Growth?

The choice of exponential growth is not arbitrary—it provides optimal adaptation to network congestion:

1. Collision as Information: Each collision signals that the previous backoff range was insufficient. By doubling the range, the algorithm makes a proportional response to increased contention.

2. Convergence Guarantee: Mathematical analysis proves that with exponential backoff, the probability of eventual successful transmission approaches 1, even with many competing stations.

3. Bandwidth Efficiency: Under light load, stations experience few collisions, keeping backoff ranges small and maintaining high throughput. Under heavy load, the expanding window prevents collision storms.

4. Self-Stabilizing: If the network becomes congested, the expanding backoff windows automatically reduce the transmission attempt rate, allowing the network to recover.

The prefix binary in Binary Exponential Backoff carries specific technical meaning that distinguishes this algorithm from other exponential backoff variants. Understanding this distinction reveals important implementation and performance characteristics.

Binary = Base 2 Exponential Growth:

The backoff window grows by powers of 2 (binary growth):

• 2¹ = 2 options after first collision
• 2² = 4 options after second collision
• 2³ = 8 options after third collision
• And so on...

This is contrasted with other possible bases:

• Ternary exponential: 3¹, 3², 3³... (grows faster)
• Decimal exponential: 10¹, 10², 10³... (grows much faster)
• Subexponential: √2, (√2)², (√2)³... (grows slower)

The Uniform Random Selection:

Another critical aspect of 'binary' refers to the uniform distribution used when selecting from the contention window. Each value in the range [0, 2^n - 1] has equal probability of being selected:

Probability of selecting any specific k = 1 / 2^n

This uniform randomness is essential because:

1. No station has inherent advantage: Everyone has equal probability of getting 0 (immediate retry) or higher values
2. Collision probability is calculable: With uniform distribution, collision probability after n collisions is approximately 1/2^n for two stations
3. Maximum entropy: Uniform distribution provides maximum unpredictability, minimizing patterns that could cause synchronized collisions

To truly understand why Binary Exponential Backoff works, we must examine its mathematical properties. This analysis proves that the algorithm guarantees eventual success and quantifies expected performance.

Collision Probability Analysis:

Consider two stations that have just experienced their n-th collision. Each will independently select a random value from [0, 2^n - 1]. What is the probability they collide again?

Expected Number of Attempts:

For two stations contending, what is the expected total number of collisions before successful transmission?

Probability of Eventual Success:

A crucial property of BEB is that every station eventually succeeds with probability 1 (almost surely). We can prove this:

P(failure forever) = P(collision on attempt 1) × P(collision on attempt 2) × ...
                   = (1/2) × (1/4) × (1/8) × (1/16) × ...
                   = Π (1/2^n) for n=1 to ∞
                   = 0

Therefore: P(eventual success) = 1

This guarantee is critical for protocol correctness—no station is permanently locked out (though it might take longer under very heavy load).

The slot time is the foundational time unit in Ethernet's Binary Exponential Backoff algorithm. Understanding slot time is essential because all backoff delays are expressed as multiples of this unit, and it directly determines the minimum frame size requirement.

Definition and Derivation:

Slot time is defined as the time required to:

1. Transmit the smallest legal frame
2. Detect if a collision occurred at the farthest point in the network
3. Receive the collision signal back at the transmitting station

The Round-Trip Requirement:

Slot time must be at least as long as the round-trip time (RTT) of the network. This ensures that a transmitting station can detect a collision before finishing its frame. The calculation involves:

1. Propagation delay: Time for signal to travel from sender to farthest station
2. Return propagation: Time for collision signal to travel back
3. Component delays: Repeaters, hubs, and NICs add processing delays
4. Jam signal time: Time to transmit 32-bit jam signal

Binary Exponential Backoff was not invented in isolation—it emerged from decades of research into multiple access protocols and was shaped by practical engineering constraints. Understanding this history illuminates why certain design choices were made.

Origins in ALOHA:

The intellectual ancestor of BEB is the ALOHA protocol developed at the University of Hawaii in 1970. ALOHA used random retransmission after collisions but with a fixed waiting time range. This approach:

• Worked well for light loads (max efficiency ~18.4% for pure ALOHA)
• Collapsed under heavy load as collision probability approached 1
• Provided no mechanism for load adaptation

Evolution to Ethernet:

Bob Metcalfe and David Boggs at Xerox PARC recognized that ALOHA's fixed backoff was inadequate for the high-speed local network they envisioned. Their key insights were:

1. Carrier sensing reduces collisions by only transmitting when medium is idle
2. Collision detection stops wasted transmission immediately
3. Adaptive backoff must respond to network congestion

Why Binary Specifically?

The choice of base 2 (binary) was driven by practical considerations:

1. Computational simplicity: In 1970s hardware, multiplying by 2 was a simple bit-shift, while other multiplications required arithmetic units
2. Sufficient adaptation rate: Base 2 doubles the window each collision—aggressive enough to handle congestion but not so aggressive as to cause unnecessary delays
3. Analytical tractability: Binary makes mathematical analysis simpler, enabling provable performance guarantees
4. Precedent in computer science: Powers of 2 were familiar to engineers and well-understood

To appreciate Binary Exponential Backoff's design, we should examine alternatives that were considered or used in other protocols. Each alternative reveals tradeoffs that make BEB's balance particularly elegant.

1. Fixed Backoff (No Adaptation):

The simplest approach—always wait a random time in a fixed range [0, W]:

• Advantage: Simple implementation, predictable behavior
• Disadvantage: If W is too small, collisions persist under load; if W is too large, unnecessary delays under light load
• Used in: Simple sensor networks with known, stable populations

2. Linear Backoff:

Window grows linearly with each collision: W(n) = W(0) + n × k

• Advantage: Gentler growth, better for environments with frequent transient collisions
• Disadvantage: Too slow to respond to sudden heavy load—collision storms can develop before window grows large enough
• Analysis: Under heavy load with N stations, expected collisions grow as O(N) rather than O(log N)

3. Polynomial Backoff:

Window grows as a polynomial function: W(n) ∝ n^k for some k > 1

• Advantage: Tunable aggressiveness between linear and exponential
• Disadvantage: No proven stability guarantees, more complex analysis
• Academic interest: Studied theoretically but rarely used in practice

4. p-Persistent with Backoff:

Combines persistence (transmit with probability p) with backoff:

• Advantage: Additional knob for tuning behavior
• Disadvantage: Additional complexity, harder to set optimal p
• Used in: Some early CSMA protocols, hybrid approaches

We've established the foundational understanding of Binary Exponential Backoff. Let's consolidate the key principles:

What's Next:

With the fundamentals established, the next page examines collision handling in detail—what exactly happens when stations detect collisions, how they coordinate their responses, and the specific mechanisms Ethernet uses to ensure all parties recognize the collision event.