3.2 CSMA, CSMA/CD & Exponential Backoff Algorithm

Back to Computer Networks Notes

📚Module 03: Data Link Layer: MAC Sublayer & EthernetTopic 3.2⏱️13 min read

🎯High-Yield For:Semester Exams (All Universities) • Placement Technical Rounds • Engineering Foundations

💡 Core Intuition: The Polite Classroom Conversation

🍳 The Everyday Analogy: "Listen Before You Speak"

In ALOHA, people behave like unruly toddlers: whenever a thought pops into their head, they shout it out immediately without checking whether someone else is already talking. This blind shouting causes constant collisions and wastes over 63% of the room's conversational time.

Carrier Sense Multiple Access (CSMA) introduces basic conversational etiquette:

1. Carrier Sensing ("Listen Before You Speak"): Before uttering a word, you pause and listen to the room. If someone else is currently speaking, you keep your mouth shut. You only start talking when the room is dead silent.
2. Collision Detection ("Listen While Speaking"): What if you and a friend sitting across the table both notice silence at the exact same millisecond and begin speaking simultaneously? In CSMA/CD, you do not mindlessly recite your entire 5-minute speech. You listen to your own voice while speaking. The instant you hear someone else talking over you, you stop speaking immediately, yell a brief "Sorry, go ahead!" (Jamming Signal), and roll a pair of dice to decide how many seconds to wait before trying again (Randomized Exponential Backoff).

💻 Bridging to Computer Science

In broadcast computer networks, an electrical or optical transmitter can sense the voltage or radio energy present on the physical cable before injecting its own bits.

By adding Carrier Sense (CS), the vulnerable collision window shrinks drastically from the entire frame transmission time ($T_t$) down to the physical propagation delay of the wire ($T_p$). By adding Collision Detection (CD), stations abort collided transmissions immediately rather than transmitting corrupt bits to completion, freeing the channel for productive data.

---

📑Table of Contents

• 🎧 CSMA Foundations & The Vulnerable Window (T_p)
  • Why Do Collisions Still Occur in CSMA?
  • Vulnerable Time in CSMA
• 🔁 The Three Persistence Strategies (1-Persistent, Non-Persistent, p-Persistent)
  • The Hybrid Approach: p-Persistent CSMA
• ⚡ CSMA/CD Mechanics & Transceiver Energy Sensing
  • Transceiver Energy Sensing
• 📏 The Golden Minimum Frame Size Derivation (T_t \ge 2 T_p)
  • The Problem
  • The Worst-Case Scenario Analysis
  • The Formal Constraint
• 🎲 Binary Exponential Backoff Algorithm Internals
  • The Algorithm Rules
  • Contention Window Growth Table
  • Why Exponential Doubling?
• 📈 CSMA/CD Channel Efficiency & Parameter 'a'
  • The Engineering Implications of Parameter 'a'
• 📶 Why Collision Detection Fails in Wireless (CSMA/CA)
• 🏭 Real-World Production Context: How Automotive CAN Bus & DOCSIS Adapted CSMA
  • 1. Automotive Controller Area Network (CAN Bus & CSMA/CR)
  • 2. Cable Broadband Internet (DOCSIS Contention Slots)
• 📐 Numerical Applications & Worked Examples
  • Example 1: Calculating Minimum Frame Size
  • Example 2: Determining Signal Propagation Speed
  • Example 3: Backoff Race Probability Between Two Stations
  • Example 4: Gigabit Ethernet Frame Size Constraint
• 🎯 Exam & Interview Pitfall Check

---

🎧 CSMA Foundations & The Vulnerable Window ($T_p$)

In pure ALOHA, any station transmits blindly whenever a frame arrives. Carrier Sense Multiple Access (CSMA) requires every station to sense the shared medium before transmitting.

Why Do Collisions Still Occur in CSMA?

If every station listens before transmitting, how can collisions happen at all?

The root cause is Propagation Delay ($T_p$): electrical and optical signals do not travel instantaneously; they propagate down copper or fiber at approximately $2 \times 10^8\text{ m/s}$ (roughly $5\text{ }\mu\text{s}$ per kilometer).

For example, consider Station $A$ and Station $B$ situated at opposite ends of a $1\text{ km}$ cable:

• At $t = 0$, Station $A$ senses the medium, finds it idle, and begins transmitting Frame $A$.
• At $t = T_p - \epsilon$ (just before $A$'s electrical wavefront reaches $B$), Station $B$ senses the line. Because $A$'s signal has not yet arrived at $B$, Station $B$ also senses the line as idle and begins transmitting Frame $B$.
• Moments later, the two electrical wavefronts collide on the wire, corrupting both frames.

1. Station $A$ senses the medium at $t = 0$, finds it idle, and begins transmitting.
2. Station $B$, located at the opposite end of a $1\text{ km}$ cable, has a frame to send at $t = 4.9\text{ }\mu\text{s}$.
3. Station $B$ senses the cable. Because Station $A$'s electrical wavefront has only traveled $980\text{ meters}$ and has not yet reached Station $B$, Station $B$ detects zero signal on the wire!
4. Station $B$ concludes the wire is idle and starts transmitting its own frame.
5. A few meters later, the two electrical wavefronts collide, corrupting both transmissions.

Vulnerable Time in CSMA

The vulnerable time in CSMA is the time required for a signal to propagate from one extreme end of the medium to the other:

$\Large V_{t,\text{CSMA}} = T_p$

Compare the vulnerable collision windows across the three random-access protocols:

Protocol	Vulnerable Period ($V_t$)	Primary Collision Vulnerability
Pure ALOHA	$2 \times T_t$	Complete and partial frame overlaps anywhere in time.
Slotted ALOHA	$1 \times T_t$	Coinciding transmissions starting at the same slot clock boundary.
CSMA	$1 \times T_p$	Propagation blind-spot before wavefront reaches remote nodes.

Because in typical local networks the propagation delay ($T_p$) is orders of magnitude smaller than the frame transmission time ($T_t$) (i.e. $T_p \ll T_t$), CSMA drastically slashes collision rates compared to ALOHA.

---

🔁 The Three Persistence Strategies (1-Persistent, Non-Persistent, p-Persistent)

When a station senses the line and discovers it is busy (another station is currently transmitting), what should it do? The MAC layer implements one of three persistence strategies:

Contrasting channel aggression, idle channel waste, and collision probability

Greedy Strategy

1-Persistent CSMA

🎯

Dominant Architecture / DomainStandard Ethernet (IEEE 802.3)

• •Continuously monitors the line while busy.
• •The instant the line becomes idle, transmits immediately (Probability = 1.0).
• •Advantage: Zero wasted channel idle time after a frame finishes.
• •Disadvantage: If 2 or more stations were waiting during an ongoing transmission, both transmit immediately upon line idle, causing a guaranteed collision.

"Greedy: Maximizes immediate channel utilization but guarantees collision on contention."

Cautious Strategy

Non-Persistent CSMA

🎲

Dominant Architecture / DomainLow-Traffic Shared Busses

• •Senses the line once. If busy, stops monitoring immediately.
• •Waits for a random amount of time (backoff) before sensing the line again.
• •Advantage: Drastically reduces collisions because waiting stations retry at different times.
• •Disadvantage: Channel may sit completely idle even when stations have frames ready to send.

"Cautious: Slashes collisions but incurs channel idle-time penalty."

The Hybrid Approach: $p$-Persistent CSMA

Used on slotted channels to find an optimal mathematical compromise between 1-persistent greed and non-persistent waste:

1. The station continuously senses the channel.
2. When the channel becomes idle, the station:
   • With probability $p$: Transmits immediately.
   • With probability $q = 1 - p$: Defers and waits until the beginning of the next slot.
3. At the next slot:
   • If the line is still idle, it repeats the test (transmits with probability $p$).
   • If the line has become busy (another node transmitted), it treats this as a collision and runs the backoff procedure.

$\text{Optimal choice: } p = \frac{1}{N} \quad \text{where } N \text{ is the number of active contending nodes}$

---

⚡ CSMA/CD Mechanics & Transceiver Energy Sensing

In basic CSMA, once a station begins transmitting, it pumps its entire frame onto the wire regardless of whether a collision happened. If two $1500\text{-byte}$ frames collide in the first $5\text{ microseconds}$, the remaining $1.2\text{ milliseconds}$ of transmission time is completely wasted transmitting garbage bits.

CSMA with Collision Detection (CSMA/CD) upgrades the station transceiver to full-duplex operation:

Architecture Flow

Lifecycle of a frame transmission with active collision detection and backoff

🎧Stage 1

Carrier Sensing

Sense line voltage. If busy, apply 1-persistent wait. If idle, start sending.

→

Line Idle

📡Stage 2

Transmit & Listen

Pump frame bits while simultaneously monitoring line energy level.

→

Collision Detected

⚡Stage 3

Jamming Signal

Abort frame immediately and broadcast 32-48 bit jam sequence.

→

Line Alerted

🎲Stage 4

Exponential Backoff

Increment collision counter, compute random backoff slot, and retry.

Transceiver Energy Sensing

How does a network interface card (NIC) know a collision occurred on copper wiring?

• Idle Channel: Line voltage is $0\text{ V}$.
• Normal Transmission: One station transmits; signal amplitude varies within standard limits (e.g. $-1\text{ V}$ to $+1\text{ V}$).
• Abnormal / Collision Level: Two electrical signals combine constructively and destructively, causing the line voltage and energy level to exceed standard operational limits (roughly doubling the normal voltage amplitude). The physical comparator in the transceiver detects this abnormal threshold and triggers the MAC collision interrupt.

---

📏 The Golden Minimum Frame Size Derivation ($T_t \ge 2 T_p$)

This is one of the most critical foundational principles in computer networking.

The Problem

A station only monitors the line for collisions while it is actively transmitting. Once the last bit of a frame exits the transmitter, the station tears down its transmission state, clears its buffer, and assumes the frame was delivered successfully!

If a collision occurs but the returning collision notification reaches the sender after it has finished transmitting its entire frame, the sender will never know its frame was destroyed, resulting in silent packet loss!

The Worst-Case Scenario Analysis

Consider two stations, $A$ and $B$, separated by the maximum cable distance in the network. The one-way propagation delay between them is $T_p$.

Space-Time Protocol Ladder

Step 1 of 5

Station A must remain actively transmitting until the returning collision signal arrives at t = 2·Tp

💡Click or hover any packet flight arrow, timer event, or step button to inspect protocol mechanics in real time

📡Transmitter

Station A (Transmitter)

Lifeline Rail (t ↓)

💻Receiver

Station B (Contender)

Lifeline Rail (t ↓)

1Frame A Transmission(t = 0 (Starts transmitting))

2Frame B Collision StartLost(t = Tp - ε (Senses wire: IDLE!))

⚡Collision at Station B(t = Tp (Destructive overlap))

4Collision Signal ReturnLost(Noise travels back to A)

⏰Collision Detected at A(t = 2·Tp (A MUST be transmitting))

Step 1 of 5station_a ➔ station_b✅ Delivered SuccessfullyFrame A Transmission

Station A senses the wire idle at t = 0 and begins transmitting Frame A. The electrical wavefront propagates down the copper cable toward Station B.

1. At time $t = 0$, Station $A$ begins transmitting.
2. At time $t = T_p - \epsilon$ (an infinitesimal instant before $A$'s signal reaches $B$), Station $B$ senses the line. Since $A$'s signal has not yet arrived, $B$ senses idle and begins transmitting.
3. A collision occurs immediately at Station $B$.
4. The distorted collision signal requires another full propagation delay ($T_p$) to travel all the way back across the cable from $B$ to $A$.
5. The collision noise finally arrives at Station $A$ at time: $t_{\text{detect}} = T_p + T_p = 2 T_p$

The Formal Constraint

For Station $A$ to detect the collision, Station $A$ must still be actively transmitting when the collision signal arrives at $2 T_p$. Therefore, the frame transmission time ($T_t$) must be greater than or equal to twice the propagation delay:

$\Large T_t \ge 2 \times T_p$

Recall that $T_t = \frac{L}{B}$, where $L$ is frame length in bits and $B$ is bandwidth in bps, and $T_p = \frac{\text{Distance } d}{\text{Velocity } v}$.

Substituting:

$\frac{L}{B} \ge 2 \times T_p \implies \Large L_{\min} = 2 \times T_p \times B = 2 \times \left(\frac{d}{v}\right) \times B$

$\text{Alternatively, maximum cable length: } \Large d_{\max} = \frac{L \times v}{2 \times B}$

Why Traditional Ethernet Frames Are At Least 64 Bytes (512 bits): In the original $10\text{ Mbps}$ Standard Ethernet ($802.3$), maximum collision domain length with repeaters was $\sim 2.5\text{ km}$, yielding a worst-case round-trip propagation delay ($2 T_p$) of $\approx 51.2\text{ }\mu\text{s}$. $L_{\min} = 2 T_p \times B = (51.2 \times 10^{-6}\text{ s}) \times (10 \times 10^6\text{ bps}) = \mathbf{512\text{ bits} = 64\text{ bytes}}$ If a payload is smaller than 46 bytes, Ethernet hardware forcibly injects padding bytes to pad the frame to 64 bytes specifically to satisfy this physical $2 T_p$ condition!

---

🎲 Binary Exponential Backoff Algorithm Internals

When a collision is detected, stations abort transmission, send a $32\text{-to-}48\text{ bit}$ Jamming Signal (to ensure all nodes register the collision), and execute the Truncated Binary Exponential Backoff (BEB) algorithm to schedule retransmission.

The Algorithm Rules

Let $k$ denote the number of consecutive collisions experienced by a given frame ($k = 1, 2, 3, \dots$).

1. Set the contention parameter $n = \min(k, 10)$.
2. Pick a random integer $R$ uniformly from the discrete set: $R \in \left\{ 0, 1, 2, 3, \dots, (2^n - 1) \right\}$
3. Compute the Backoff Wait Time ($T_B$): $\Large T_B = R \times \text{Slot Time}$ where $\text{Slot Time} = 2 T_p$ (512 bit times in standard Ethernet).
4. After waiting $T_B$, the station attempts to retransmit the frame.
5. Abort Condition: If the frame suffers $k = 16$ consecutive collisions, the station declares an unrecoverable link error, aborts transmission, and reports network failure to higher layers.

Contention Window Growth Table

Collision Number ($k$)	Window Exponent $n = \min(k, 10)$	Contention Range ($0 \le R < 2^n$)	Number of Possible Choices ($2^n$)
1st Collision	1	$\{0, 1\}$	2 choices
2nd Collision	2	$\{0, 1, 2, 3\}$	4 choices
3rd Collision	3	$\{0, 1, \dots, 7\}$	8 choices
4th Collision	4	$\{0, 1, \dots, 15\}$	16 choices
5th Collision	5	$\{0, 1, \dots, 31\}$	32 choices
$\dots$	$\dots$	$\dots$	$\dots$
10th Collision	10	$\{0, 1, \dots, 1023\}$	1,024 choices
11th to 15th	10 (capped)	$\{0, 1, \dots, 1023\}$	1,024 choices (fixed)
16th Collision	—	ABORT (Drop Frame & Report Error)	—

Why Exponential Doubling?

• Under light network load, collisions are rare. Choosing from $\{0, 1\}$ ensures colliding stations retransmit almost immediately without unnecessary delay.
• Under heavy network congestion, many stations are contending. Doubling the window with each collision rapidly spreads the contending stations across a wider time horizon, preventing repeated collision avalanches.

---

📈 CSMA/CD Channel Efficiency & Parameter '$a$'

Channel efficiency ($\eta$) in CSMA/CD depends fundamentally on the dimensionless parameter:

$\Large a = \frac{T_p}{T_t}$

The theoretical channel efficiency is derived as:

$\Large \eta = \frac{1}{1 + 2 e \cdot a} \approx \frac{1}{1 + 5.44 a} \quad \text{or commonly modeled as} \quad \Large \eta = \frac{1}{1 + 5a}$

The Engineering Implications of Parameter '$a$'

• When $a \to 0$ ($\eta \to 100\%$): $T_t \gg T_p$ (transmission time is huge compared to propagation delay). Frames are large, or cable lengths are short. The instant a transmission begins, its wavefront covers the entire cable before other stations attempt to transmit, yielding near-perfect channel utilization.
• When $a$ increases ($\eta$ drops): $T_p$ is large compared to $T_t$. As link speeds jumped from $10\text{ Mbps}$ to $100\text{ Mbps}$ to $1\text{ Gbps}$, $T_t$ shrank proportionally. To keep $a$ reasonably small at Gigabit speeds without blowing up minimum frame sizes, networks had to abandon shared-bus CSMA/CD and transition to Full-Duplex Switched Ethernet.

---

📶 Why Collision Detection Fails in Wireless (CSMA/CA)

While CSMA/CD works brilliantly on guided copper cables, it cannot be implemented on wireless LANs (Wi-Fi / IEEE 802.11) for two fundamental physical reasons:

1. Massive Transmit/Receive Power Disparity (Dynamic Range Problem): In wireless radio, radiated signal power attenuates rapidly with distance according to the inverse-square law ($P \propto \frac{1}{d^2}$ or $\frac{1}{d^4}$). When a wireless NIC transmits, its own local antenna radiates at, say, $+20\text{ dBm}$ ($100\text{ mW}$). A distant frame arriving from across the room might reach the antenna at $-70\text{ dBm}$ ($0.0001\text{ mW}$). The local transmitter completely deafens its own receiver; detecting a remote collision over the roar of its own broadcast is practically impossible.
2. Hidden Terminal Problem: Node $A$ can hear Node $B$, and Node $C$ can hear Node $B$, but $A$ and $C$ are out of radio range of each other (hidden by distance or a concrete wall). If $A$ and $C$ both sense the channel, both detect silence, and both transmit to $B$ simultaneously. A collision occurs at $B$, yet neither $A$ nor $C$ can detect it!

Therefore, wireless networks use CSMA with Collision Avoidance (CSMA/CA) using Interframe Spaces (IFS), Random Contention Windows, Receiver ACKs, and optional RTS/CTS (Request to Send / Clear to Send) handshakes.

---

🏭 Real-World Production Context: How Automotive CAN Bus & DOCSIS Adapted CSMA

Although classic Ethernet bus architectures transitioned to full-duplex switches, the foundational principles of CSMA and collision resolution remain critical in mission-critical embedded systems and telecommunications:

1. Automotive Controller Area Network (CAN Bus & CSMA/CR)

Modern automobiles contain over 70 Electronic Control Units (ECUs) managing engine timing, anti-lock braking (ABS), steering, and infotainment over a single shared two-wire differential bus (CAN Bus).

• The High-Stakes Dilemma: In an automobile, an ABS brake trigger cannot afford randomized exponential backoff delays. If the brake ECU collides with a stereo volume adjustment, waiting $10\text{ ms}$ could be fatal.
• The Solution — Non-Destructive Bitwise Arbitration (CSMA/CR): CAN bus uses Carrier Sense Multiple Access with Collision Resolution. Bit 0 is configured as Dominant (driven voltage) and bit 1 as Recessive (passive resistor pull). Every message begins with an identifier indicating its priority (lower numerical ID = higher priority). Nodes transmit their ID bit-by-bit while simultaneously reading the bus voltage. If an ECU transmits a recessive 1 but reads back a dominant 0, it realizes a higher-priority message is sharing the wire, immediately yields without corrupting the message, and becomes a receiver. The highest-priority safety message proceeds through the bus without a single microsecond of delay or packet destruction!

2. Cable Broadband Internet (DOCSIS Contention Slots)

Your home coaxial cable internet (DOCSIS standard) connects thousands of suburban subscribers over a shared coaxial trunk to the Cable Modem Termination System (CMTS) at the ISP headend.

• Downstream data from ISP to homes is purely scheduled (TDM broadcast).
• Upstream data from homes to the ISP is divided into discrete minislots. When your cable modem has upstream packets to send, it uses a Slotted Contention Window with Exponential Backoff to request dedicated bandwidth slots from the CMTS. Once the request succeeds, the CMTS grants scheduled collision-free timeslots for the actual data transmission.

---

📐 Numerical Applications & Worked Examples

Example 1: Calculating Minimum Frame Size

Problem Statement: A broadcast network using CSMA/CD operates at a transmission bandwidth of $20\text{ Mbps}$ ($20 \times 10^6\text{ bps}$). The maximum signal propagation time between any pair of nodes is $40\text{ microseconds}$. Determine the minimum size of a frame (in bytes) required for proper collision detection.

Step-by-Step Solution:

1. Given Parameters:
   • Bandwidth $B = 20 \times 10^6\text{ bps}$
   • Maximum propagation delay $T_p = 40\text{ }\mu\text{s} = 40 \times 10^{-6}\text{ s}$
2. Apply CSMA/CD Minimum Frame Size Condition: $T_t \ge 2 \times T_p$ $\frac{L_{\min}}{B} = 2 \times T_p \implies L_{\min} = 2 \times T_p \times B$
3. Compute Frame Length in Bits: $L_{\min} = 2 \times (40 \times 10^{-6}\text{ s}) \times (20 \times 10^6\text{ bps}) = 2 \times 40 \times 20 = \mathbf{1600\text{ bits}}$
4. Convert to Bytes: $\text{Frame Size in Bytes} = \frac{1600\text{ bits}}{8\text{ bits/byte}} = \mathbf{200\text{ bytes}}$

---

Example 2: Determining Signal Propagation Speed

Problem Statement: Consider a CSMA/CD network transmitting at $100\text{ Mbps}$ ($10^8\text{ bps}$) over a $1\text{ km}$ cable without repeaters. If the network standard dictates a minimum frame size of $1250\text{ bytes}$, calculate the signal propagation velocity in the cable (in $\text{km/s}$).

Step-by-Step Solution:

1. Identify Frame Size in Bits: $L = 1250\text{ bytes} \times 8\text{ bits/byte} = 10,000\text{ bits} = 10^4\text{ bits}$
2. Compute Transmission Time ($T_t$): $T_t = \frac{L}{B} = \frac{10^4\text{ bits}}{10^8\text{ bps}} = 10^{-4}\text{ s} = 100\text{ }\mu\text{s}$
3. Relate $T_t$ to $T_p$ via CSMA/CD Constraint: $T_t = 2 \times T_p \implies T_p = \frac{T_t}{2} = \frac{100\text{ }\mu\text{s}}{2} = 50\text{ }\mu\text{s} = 5 \times 10^{-5}\text{ s}$
4. Calculate Velocity ($v$): $T_p = \frac{\text{Distance } d}{v} \implies v = \frac{d}{T_p} = \frac{1\text{ km}}{5 \times 10^{-5}\text{ s}} = \frac{1}{0.00005} = \mathbf{20,000\text{ km/s}}$ (In $\text{m/s}$: $20,000\text{ km/s} = 2 \times 10^7\text{ m/s}$.)

---

Example 3: Backoff Race Probability Between Two Stations

Problem Statement: Stations $A$ and $B$ are the only two nodes on a shared Ethernet bus. Both attempt to transmit a frame simultaneously, collide, and execute Binary Exponential Backoff. Station $A$ wins the first backoff race and transmits successfully. Immediately upon completion of $A$'s frame, both $A$ and $B$ attempt to transmit their next frames and collide again. Calculate the probability that Station $A$ wins the second backoff race.

Step-by-Step Solution:

1. Analyze Collision Counts for Both Stations at the Second Collision:
   • Station $A$ succeeded on its prior attempt, so its collision counter reset to 0. For this new frame, this collision is its 1st collision ($k_A = 1$).
     • Station $A$'s contention range: $R_A \in \{0, 1\}$.
   • Station $B$'s original frame has now suffered its 2nd consecutive collision ($k_B = 2$).
     • Station $B$'s contention range: $R_B \in \{0, 1, 2, 3\}$.
2. List All Possible Outcome Pairs $(R_A, R_B)$: Since $A$ chooses independently from 2 options and $B$ chooses from 4 options, there are $2 \times 4 = 8$ equally likely outcomes: $\{(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3)\}$
3. Identify Winning Condition for Station $A$: Station $A$ wins the backoff race if and only if its chosen backoff multiplier is strictly smaller than $B$'s ($R_A < R_B$):
   • If $R_A = 0$: $A$ wins if $R_B \in \{1, 2, 3\}$ $\implies$ 3 winning pairs: $(0,1), (0,2), (0,3)$.
   • If $R_A = 1$: $A$ wins if $R_B \in \{2, 3\}$ $\implies$ 2 winning pairs: $(1,2), (1,3)$.
4. Calculate Total Probability: $\text{Total Winning Outcomes for } A = 3 + 2 = 5$ $P(A \text{ wins}) = \frac{5}{8} = \mathbf{0.625 \ (62.5\%)}$ (Note: This asymmetric advantage illustrates the "Capture Effect" in Ethernet, where a recently successful station with a smaller backoff window tends to dominate the channel over an unlucky colliding station.)

---

Example 4: Gigabit Ethernet Frame Size Constraint

Problem Statement: A Gigabit Ethernet network ($B = 1\text{ Gbps} = 10^9\text{ bps}$) is deployed over a copper cable with a signal velocity of $2 \times 10^8\text{ m/s}$. The maximum cable segment between any two stations is $200\text{ meters}$. Calculate the minimum frame size required to maintain CSMA/CD collision detection.

Step-by-Step Solution:

1. Calculate Propagation Delay ($T_p$): $T_p = \frac{\text{Distance } d}{v} = \frac{200\text{ m}}{2 \times 10^8\text{ m/s}} = 10^{-6}\text{ seconds} = 1\text{ }\mu\text{s}$
2. Apply $L_{\min} = 2 \times T_p \times B$: $L_{\min} = 2 \times (10^{-6}\text{ s}) \times (10^9\text{ bps}) = 2 \times 10^3 = \mathbf{2000\text{ bits}}$
3. Convert to Bytes: $L_{\min} = \frac{2000\text{ bits}}{8\text{ bits/byte}} = \mathbf{250\text{ bytes}}$

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Why does the minimum frame size formula include a factor of 2 ($2 T_p$ instead of just $T_p$)? Because of the worst-case round-trip travel time. If station $A$ transmits at $t=0$, its signal takes $T_p$ to reach station $B$ at the far end of the cable. If $B$ begins transmitting just before $A$'s wavefront arrives, the resulting collision signal takes an additional $T_p$ to travel back from $B$ to $A$. Thus, $A$ only detects the collision at time $2 T_p$. $A$ must still be transmitting when that collision arrives.
• What is the Ethernet "Capture Effect"? When two stations contend for an Ethernet bus, the station that successfully transmits a frame resets its backoff counter to $k=1$ (window $\{0, 1\}$), while the losing station increments its counter to $k=2$ (window $\{0, 1, 2, 3\}$). On subsequent contentions, the successful station has a statistical probability advantage ($\ge 62.5\%$), repeatedly "capturing" the channel while starving the other node.

Common Interview Traps

• Trap: Confusing bits and bytes in $L_{\min}$ calculations. The formula $L_{\min} = 2 T_p \times B$ produces the frame size in bits (since $B$ is in bits/second). Always remember to divide by 8 when an interview or semester question asks for the answer in bytes.
• Trap: Believing CSMA/CD is used in modern Gigabit and 10-Gigabit Ethernet. While Gigabit Ethernet standards defined "Carrier Extension" to allow CSMA/CD with 512-byte minimum frames, virtually 100% of modern Ethernet deployments use full-duplex switched connections (dedicated point-to-point links to a switch). With dedicated pairs for Tx and Rx, collisions are physically impossible, making CSMA/CD completely inactive in modern wired networks!

---

🗺️View Complete Computer Networks Roadmap & Syllabus

← Previous Topic3.1 Random Access Protocols: Pure ALOHA & Slotted ALOHANext Topic →3.3 Ethernet Frame Format (IEEE 802.3) & Minimum Frame Size