Exponential Backoff - Learning Module

Loading content...

0/228

Collision Handling

The Art of Graceful Recovery

When two stations transmit simultaneously on a shared Ethernet segment, their signals interfere, creating a garbled mess that neither station's NIC can decode. This is a collision—an inevitable consequence of distributed systems where no central coordinator dictates who may speak. But unlike human conversation where collisions cause confusion and frustration, Ethernet handles collisions with remarkable precision.

The collision handling process in CSMA/CD Ethernet is a carefully choreographed sequence of detection, notification, and recovery. Every step is engineered to ensure that all participating stations recognize the collision, abort their transmissions promptly, and prepare for orderly retransmission using the Binary Exponential Backoff algorithm we explored previously.

What You Will Learn

This page examines the complete collision handling lifecycle: how collisions are detected at the physical layer, why jam signals are necessary, the precise timing constraints that govern Ethernet's operation, and how the protocol ensures no station is left unaware of a collision event.

Collision Detection Mechanisms

Collision detection is the foundation of CSMA/CD's efficiency advantage over CSMA alone. Rather than transmitting entire frames and discovering collisions only after the fact (when ACKs fail to arrive), Ethernet stations detect collisions during transmission and abort immediately. But how exactly does a station detect that another station is also transmitting?

Physical Layer Detection:

Ethernet uses several methods depending on the physical medium:

1. Amplitude Detection (Coaxial Ethernet):

In original 10BASE5 and 10BASE2 coaxial Ethernet, stations monitor the voltage levels on the cable. During normal single transmission, the signal has characteristic voltage levels. When two stations transmit simultaneously:

Their signals superimpose
The combined amplitude exceeds the threshold for a single transmission
The NIC detects this 'DC level shift' and identifies a collision

Collision Detection Methods by Medium
Medium Type	Detection Method	Physical Mechanism	Detection Time
10BASE5 (Thick Coax)	Voltage threshold	Combined signal amplitude exceeds single-transmission threshold	< 1 bit time
10BASE2 (Thin Coax)	Voltage threshold	Same as thick coax, lower voltage thresholds	< 1 bit time
10BASE-T (Twisted Pair)	Simultaneous Tx/Rx	Presence of signal on receive pair while transmitting	< 1 bit time
100BASE-TX (Fast Ethernet)	MLT-3 violation	Signal encoding violation during transmission	< 1 bit time
1000BASE-T (Gigabit)	Hybrid circuit	Echo cancellation detects external signal during transmission	< 1 bit time

2. Simultaneous Transmit/Receive Detection (Twisted Pair):

In 10BASE-T and later twisted-pair Ethernet, separate wire pairs are used for transmitting (pins 1,2) and receiving (pins 3,6). When using a hub (not a switch):

The hub broadcasts all received signals to all ports
If station A transmits, the hub sends A's signal to all other ports, including back to A's receive pair
Station A monitors its receive pair while transmitting
If A sees a signal it didn't send, another station must be transmitting
Collision detected!

3. Hub Signal Collision Enforcement:

Hubs implement collision detection support:

When a hub detects signals on multiple ports simultaneously
It transmits a special collision presence signal on all ports
This signal is distinguishable from normal data
All stations receiving this signal know a collision occurred

Switches Eliminate Collisions

Modern Ethernet switches create point-to-point connections between each port. Since traffic is not broadcast to all ports, collisions become impossible on switched networks. This is why CSMA/CD is effectively obsolete in modern networks, though the protocol remains in the standard for backward compatibility.

The Collision Window

The collision window is the critical time period during which a station remains vulnerable to collisions after beginning transmission. Understanding this window is essential for proper Ethernet design and explains why minimum frame size requirements exist.

Defining the Collision Window:

When station A begins transmitting, its signal propagates outward at roughly 2/3 the speed of light through the network medium. Station B at the far end of the network might begin transmitting just before A's signal reaches it—B's carrier sense showed the medium as idle.

For A to detect this collision, B's signal must travel back to A. The worst-case scenario occurs when:

A begins transmitting
B begins transmitting just before A's signal arrives (one propagation delay later)
B's signal takes another propagation delay to reach A
Total time: two propagation delays = round-trip time

Collision Window Analysis

Timing Analysis

Collision Window Duration = Round-Trip Time (RTT)
 
For 10 Mbps Ethernet:
┌─────────────────────────────────────────────────────────────┐
│ Time 0:      Station A starts transmitting                  │
│              A's signal begins propagating toward B         │
│                                                             │
│ Time τ:      A's signal reaches station B (maximum prop.)   │
│              But B started transmitting at time (τ - ε)     │
│              B didn't see A's carrier—medium appeared idle  │
│                                                             │
│ Time 2τ:     B's signal reaches station A                   │
│              A detects collision (overlapping signals)      │
│              Collision window closes                        │
└─────────────────────────────────────────────────────────────┘
 
Where τ = one-way propagation delay (≈25.6 μs for max 10BASE5)
Collision window = 2τ = 51.2 μs = 1 slot time
 
Critical requirement:
- Station must still be transmitting when collision signal arrives
- Therefore: Minimum transmission time ≥ Collision window
- For 10 Mbps: Min frame = 51.2 μs × 10 Mbps = 512 bits = 64 bytes

Late Collisions: The Danger Zone

A 'late collision' occurs when a collision is detected after the collision window has passed. This should never happen in a properly designed network and indicates a serious problem: cable too long, too many repeaters, or a malfunctioning NIC. Late collisions are not retried by the normal backoff algorithm and result in frame loss.

After the Collision Window:

Once a station has transmitted for one full slot time without detecting a collision, it has 'captured' the channel—all other stations will have heard its carrier and deferred. The station can complete its transmission without collision (barring hardware failures).

This is sometimes called the contention period followed by the transmission period:

Contention period (first 51.2 μs at 10 Mbps): Station vulnerable to collisions
Transmission period (remainder of frame): Channel captured, no collision possible

The Jam Signal

When a collision is detected, the transmitting station doesn't simply stop transmitting—it first sends a jam signal. This seemingly wasteful additional transmission serves critical purposes in ensuring proper collision handling.

Jam Signal Specifications:

Per IEEE 802.3, the jam signal:

Is exactly 32 bits (4 bytes) long
Contains a pattern that is not a valid CRC
Can be any bit pattern except one that could be interpreted as a valid frame fragment
Common implementation: alternating 1s and 0s (10101010...)
Must be transmitted at full line speed

Jam Signal Timing at Different Speeds
Ethernet Speed	Jam Signal Duration	Jam Signal Bits	Purpose
10 Mbps	3.2 μs	32 bits	Reinforce collision detection
100 Mbps	0.32 μs	32 bits	Same purpose, 10× faster
1000 Mbps	0.032 μs	32 bits	Same purpose, 100× faster

Why the Jam Signal is Necessary:

The jam signal serves multiple essential functions:

1. Ensuring Collision Propagation:

In large networks, a collision might occur at a point far from some stations. The collision itself produces a small burst of garbled signal. This burst might be too short for distant stations to reliably detect as a collision. The jam signal:

Extends the duration of the abnormal signal
Guarantees that all stations see the collision indication
Prevents any station from thinking the collision fragment was just noise

2. Invalidating Partial Frames:

When a collision occurs, the receiver might have captured some valid-looking bits before the collision corrupted the signal. Without the jam:

A receiver might store a partial frame
The CRC might (rarely) accidentally be valid
The partial frame could be misprocessed

The jam signal ensures:

The CRC is definitely invalid
Receivers discard the entire fragment
No ambiguity about frame validity

Collision and Jam Signal Timeline

Event Sequence

Time →
 
Station A     ████████████░░░░JJJJ░░░░░░░░░░░░░░░░░░░░
                 ^           ^    ^
                 │           │    └── Jam complete, A goes
                 │           │        to backoff
                 │           └── Collision detected,
                 │               jam begins
                 └── Transmission starts
 
Station B         ████████░░░░JJJJ░░░░░░░░░░░░░░░░░░░░
                    ^      ^    ^
                    │      │    └── Jam complete, B goes
                    │      │        to backoff
                    │      └── Collision detected,
                    │          jam begins
                    └── Transmission starts
 
Medium        ░░░░████████████▓▓JJJJ░░░░░░░░░░░░░░░░░░
                         ^   ^
                         │   └── Combined jams on medium
                         └── Collision point (garbled signal)
 
Legend:
████ = Valid preamble/data
▓▓   = Collision (garbled signal)
JJJJ = Jam signal
░░░░ = Idle medium
 
The jam signal ensures ALL stations detect the collision,
even if they're far from the collision point.

The 32-Bit Choice

Why exactly 32 bits for the jam signal? It's a balance: long enough to propagate across the maximum network span and be reliably detected, but short enough to minimize wasted bandwidth. 32 bits at 10 Mbps takes 3.2 μs—about 1/16 of a slot time—sufficient for reliable detection without excessive overhead.

The Complete Collision Response Sequence

When a collision occurs, each involved station executes a precisely defined sequence of actions. This deterministic response ensures that all stations properly abort, notify, and prepare for organized retransmission.

Step-by-Step Collision Handling:

Collision Response Protocol

•Collision Detection: NIC hardware detects abnormal signal conditions indicating multiple simultaneous transmissions.
•Immediate Transmission Halt: Station stops transmitting its current frame data. The partially transmitted frame is abandoned.
•Jam Signal Transmission: Station transmits exactly 32 bits of jam signal to reinforce collision notification to all stations.
•Collision Counter Increment: Station increments its retry counter for this frame (starts at 0).
•Retry Limit Check: If retry counter exceeds maximum (typically 16), abort frame and report error to upper layer.
•Backoff Calculation: Using BEB, select random k from [0, 2^min(n,10) - 1] where n is the collision count.
•Backoff Wait: Wait for k slot times while monitoring the medium (slot time = 51.2 μs at 10 Mbps).
•Carrier Sense: After backoff expires, check if medium is idle.
•Retransmission: If idle, begin transmitting the complete frame from the beginning (preamble, SFD, and all).

Collision Handling State Machine

State Transitions

                           ┌────────────────┐
                           │   IDLE STATE   │
                           │   (waiting)    │
                           └───────┬────────┘
                                   │ Frame to transmit
                                   ▼
                           ┌────────────────┐
                           │ CARRIER SENSE  │◄────────────────────┐
                           │ (check medium) │                     │
                           └───────┬────────┘                     │
                       ┌───────────┴───────────┐                  │
                   Busy│                       │Idle              │
                       ▼                       ▼                  │
                ┌────────────┐          ┌─────────────┐           │
                │   DEFER    │          │  TRANSMIT   │           │
                │(wait idle) │          │  (sending)  │           │
                └─────┬──────┘          └──────┬──────┘           │
                      │                    ┌───┴───┐              │
                      │              Collision│   │Success        │
                      │                       ▼   ▼               │
                      │         ┌────────────────┬────────────┐   │
                      │         │   COLLISION    │   DONE     │   │
                      │         │   DETECTED     │ (complete) │   │
                      │         └───────┬────────┴────────────┘   │
                      │                 │                         │
                      │                 ▼                         │
                      │         ┌─────────────┐                   │
                      │         │TRANSMIT JAM │                   │
                      │         │ (32 bits)   │                   │
                      │         └──────┬──────┘                   │
                      │                │                          │
                      │                ▼                          │
                      │         ┌──────────────┐                  │
                      │         │ RETRY COUNT  │                  │
                      │         │ n = n + 1    │                  │
                      │         └──────┬───────┘                  │
                      │            ┌───┴────┐                     │
                      │       n≤16 │        │ n>16                │
                      │            ▼        ▼                     │
                      │   ┌─────────────┐ ┌────────────┐          │
                      │   │  BACKOFF    │ │ ABORT      │          │
                      │   │ wait k×slot │ │(report err)│          │
                      │   └──────┬──────┘ └────────────┘          │
                      │          │                                │
                      └──────────┴────────────────────────────────┘

Frame Retransmission is Complete

When retransmitting after a collision, the station sends the entire frame from scratch—including preamble and Start Frame Delimiter. There is no mechanism to resume from where the collision occurred, as the receiver has no reliable way to know what was already correctly received.

Critical Timing Constraints

The collision handling mechanism depends on precise timing relationships. Violating these constraints can cause subtle but serious network problems including late collisions, undetected collisions, and frame loss.

Inter-Frame Gap (IFG):

After a frame transmission completes (whether successfully or after a collision's jam signal), all stations must observe an inter-frame gap before transmitting:

96 bit times at any Ethernet speed
9.6 μs at 10 Mbps
960 ns at 100 Mbps
96 ns at 1 Gbps

The IFG serves several purposes:

Allows receiver electronics to recover
Provides time for carrier sense to stabilize
Ensures frames remain distinguishable
Gives stations time to process collision backoff

Critical Timing Parameters for 10 Mbps Ethernet
Parameter	Value	Bits at 10 Mbps	Purpose
Slot Time	51.2 μs	512 bits	Round-trip time, backoff unit
Inter-Frame Gap	9.6 μs	96 bits	Minimum gap between frames
Jam Size	3.2 μs	32 bits	Collision reinforcement signal
Preamble	5.6 μs	56 bits	Receiver clock synchronization
SFD	0.8 μs	8 bits	Frame start marker
Min Frame	51.2 μs	512 bits	Ensures collision detection
Max Frame	1.214 ms	12,144 bits	Limits channel monopolization

Collision Detection Timing:

The precise timing of collision detection is critical:

Maximum Collision Detection Time:
= Maximum round-trip propagation delay
+ Repeater delays
+ Transceiver delays
+ Signal rise/fall times
< Slot time (by specification)

If collision detection takes longer than one slot time, the transmitting station might finish sending a minimum-sized frame before detecting the collision—a late collision.

Jam Signal Timing:

The 32-bit jam must be transmitted:

Immediately after collision detection
Before the station stops transmitting
At full line speed (no rate changes)

This ensures the jam overlaps with and extends the collision indication, making it unmistakable.

Gigabit Timing Challenges

At 1 Gbps, 512 bits take only 0.512 μs to transmit—too short for practical network diameters. Gigabit Ethernet addresses this with 'carrier extension,' padding minimum frames to 512 bytes (4,096 bits) for collision detection purposes. This introduces inefficiency but maintains CSMA/CD compatibility.

Multi-Station Collision Scenarios

While the simplest collision involves two stations, real-world networks can experience multi-station collisions where three or more stations transmit simultaneously. This introduces additional complexity in collision resolution.

How Multi-Station Collisions Occur:

Consider a scenario where the medium has just become idle after a transmission:

Multiple stations have frames queued, waiting for idle medium
All stations detect the new idle state at approximately the same time
All begin transmission after their respective IFG periods
Because they're using the same timing reference (the previous transmission's end), they start nearly simultaneously
Collision involves 3, 4, or even more stations

Multi-Station Collision Example

Timeline

Previous Frame Ends → All Stations See Idle → IFG → Contention
 
Time:     0         96 bits    Variable (due to skew)
          │         │          │
          ▼         ▼          ▼
          ┌─────────┬──────────┬─────────────────────────────
          │ Frame X │   IFG    │  Station A transmits
          │  ends   │          │  Station B transmits    ← Collision!
          │         │          │  Station C transmits
          │         │          │  Station D transmits
          └─────────┴──────────┴─────────────────────────────
 
All four stations experience collision simultaneously.
Each independently:
1. Detects collision (amplitude/signal anomaly)
2. Sends 32-bit jam
3. Increments collision counter (n=1)
4. Selects random k from [0,1]
5. Waits k slot times
 
Possible outcomes after first collision:
- 0,0,0,0 → All four collide again
- 0,0,0,1 → Three collide, one succeeds
- 0,0,1,1 → Two pairs collide
- 0,1,1,1 → One succeeds, three collide later
- 1,1,1,1 → All retry at same time, all collide again
(16 possible combinations, only some lead to success)

Collision Probability with Multiple Stations:

With N stations all experiencing their n-th collision:

Each selects from [0, 2^n - 1]
Probability no two select the same value = (Product as stations select unique values)

As N increases, more collisions are expected before successful transmission, but the exponential backoff still provides stability. The expected collisions grow as O(log N), not O(N).

Expected Collisions vs. Number of Contending Stations
Stations (N)	Expected Collisions	Probability of 1st-try Success	Typical Resolution Time
2	1-2	50%	< 5 slot times
4	2-3	~6%	< 10 slot times
8	3-4	~0.4%	< 20 slot times
16	4-5	~0.001%	< 50 slot times
32	5-6	~10^-9	< 100 slot times

BEB Handles Multi-Station Elegantly

The beauty of BEB is that each station operates independently—no coordination is required. Even with many stations colliding, the probability of successful transmission improves exponentially with each collision. The system is inherently stable regardless of how many stations participate.

Collision Types and Network Diagnosis

Network administrators and engineers must understand different collision types to diagnose network problems. Not all collisions are equal—some are normal operation, while others indicate serious issues.

Local Collisions (Normal):

These occur within the collision window (first 512 bit-times) and are handled normally by BEB:

Detected during transmission
Jam signal sent
Backoff and retry
Counted in NIC statistics as 'collisions'

Some local collisions are expected on any shared Ethernet segment, especially under moderate to heavy load.

Late Collisions (Problem!):

A late collision occurs after 512 bit-times have been transmitted:

Should never occur in a properly designed network
Indicates cable length violations, too many repeaters, or faulty equipment
Not retried by BEB—frame is simply lost
Upper layer protocols must detect and retry

Normal (Local) Collisions

•Occur within first 64 bytes of transmission
•Handled by BEB with automatic retry
•Normal part of CSMA/CD operation
•Slight increase under heavy load is expected
•NIC statistics track as 'Collisions'

Late Collisions (Errors)

•Occur after 64th byte
•NOT retried by BEB
•Indicate network design violations
•Cause frame loss
•NIC statistics track as 'Late Collisions'

Excessive Collisions:

When a frame experiences 16 consecutive collisions (the maximum retry limit), it is discarded:

Reported to upper layer as transmission failure
Indicates severe network congestion or malfunction
Should be very rare in healthy networks
May indicate a 'babbling NIC' that transmits continuously

Phantom Collisions:

False collision detections caused by:

Electromagnetic interference
Poor cable connections
Faulty NIC hardware
Impedance mismatches

These waste bandwidth through unnecessary backoffs and may indicate physical layer problems requiring investigation.

Diagnosing Collision Problems

If you see high collision rates: check cable lengths and quality, count repeaters (max 4 in path), verify proper termination (coaxial), and test NIC hardware. If you see late collisions: the network violates timing constraints—immediate investigation is required.

Summary: Collision Handling Mastery

We've comprehensively examined how Ethernet handles collisions—from detection to recovery. Let's consolidate the essential concepts:

Key Takeaways

•Detection mechanisms: Collisions are detected through amplitude changes, simultaneous Tx/Rx signals, or hub collision signals, depending on the physical medium.
•Collision window: The first slot-time (512 bit-times) is vulnerable to collisions; after this, the channel is 'captured.'
•Jam signal: A 32-bit signal that ensures all stations detect the collision and properly discard partial frames.
•Response sequence: Detection → abort → jam → increment counter → backoff → retry—a deterministic state machine.
•Timing precision: IFG, slot time, and jam duration are precisely specified to ensure reliable operation.
•Multi-station handling: BEB handles arbitrary numbers of colliding stations without requiring coordination.
•Late collisions: Indicate network design violations and cause frame loss—never acceptable in healthy networks.
•Diagnostic importance: Monitoring collision types helps identify network problems before they cause service degradation.

What's Next:

With collision detection and handling understood, we'll next examine the backoff algorithm in detail—the specific implementation of Binary Exponential Backoff including the formula, the truncation at 10 collisions, and practical implementation considerations.

Page Complete

You now understand how Ethernet detects and responds to collisions—the jam signal, timing constraints, and the complete collision handling lifecycle. This knowledge is essential for network design, troubleshooting, and understanding why Ethernet remains robust under varying loads.