CSMA/CD Collision Detection & Minimum Frame Size
“L >= 2 * T_p * Bandwidth, binary exponential backoff, and collision domains.”
1.Evolution of Random Access: ALOHA to CSMA/CD
§ 4.1.In broadcast channels where multiple stations share a single physical medium, Medium Access Control (MAC) protocols arbitrate who transmits.
1. Pure ALOHA: Stations transmit whenever they have data. If two frames overlap even by a single bit, a collision occurs. Vulnerable time = 2 * T_fr. Maximum throughput S_max = 1 / (2e) approx 18.4% (at traffic load G = 0.5).
2. Slotted ALOHA: Time is partitioned into discrete slots of length T_fr. Stations can only begin transmitting at the beginning of a time slot. Vulnerable time = T_fr. Maximum throughput S_max = 1 / e approx 36.8% (at G = 1).
3. CSMA (Carrier Sense Multiple Access): 'Listen before talk'. Stations sense the channel first: 1-persistent (transmits immediately when idle; causes collision if two are waiting), Non-persistent (waits random time before sensing again if busy), p-persistent (transmits with probability p in next slot).
4. CSMA/CD: 'Listen before talk and listen while talking'. As soon as a collision is detected during transmission, the station aborts immediately and broadcasts a 32-bit jam signal to notify all stations.
2. The Golden Rule of CSMA/CD: Minimum Frame Size Derivation
A transmitting station MUST continue transmitting until the round-trip signal has had time to return. If the frame is too short, the transmission finishes before the collision signal returns, and the collision goes undetected!
Worst-Case Scenario: Station A and Station B are at opposite ends of a cable separated by propagation delay T_p.
At t = 0: Station A starts transmitting.
At t = T_p - epsilon: Just before A's signal reaches B, Station B senses an idle line and starts transmitting.
Immediately at t = T_p: A collision occurs near B.
The collision signal takes another T_p to travel back to A.
Station A receives the collision signal at time t = 2 * T_p.
To detect this collision while still transmitting, Transmission Time T_t must be AT LEAST 2 T_p: T_t >= 2 T_p.
Since T_t = L / Bandwidth (B): L / B >= 2 T_p => L_min = 2 T_p * B.
Standard 10 Mbps Ethernet: Round-trip time 2 T_p = 51.2 microseconds. L_min = (10 10^6 bps) (51.2 10^-6 s) = 512 bits = 64 bytes!
3.Binary Exponential Backoff Algorithm
§ 4.3.After a collision in CSMA/CD, the transmitting station waits for a random backoff time before attempting retransmission.
Algorithm: After collision number n (1 <= n <= 15):
1. Set k = min(n, 10).
2. Pick an integer r uniformly at random from the range [0, 2^k - 1].
3. Wait for backoff duration T_backoff = r Slot_Time (where Slot_Time = 2 T_p = 51.2 microseconds in standard Ethernet).
4. After 16 consecutive collisions, the station aborts transmission and reports a network failure to higher layers.
What is the probability that two colliding stations pick the SAME backoff slot after collision n = 2? Range is [0, 2^2 - 1] = [0, 3] (4 choices). Total outcomes = 4 * 4 = 16. Matching pairs = 4. Probability = 4 / 16 = 1/4 = 1 / (2^k).
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-level numerical drilling and PYQ analysis.
Step-by-step conceptual walkthroughs with worked GATE numericals.
Clear whiteboard lectures for foundational and semester exam coverage.