Self-checkedTier 1 8 min readcn.mac-protocols

Medium access: ALOHA, CSMA and CSMA/CD

How stations that share one channel decide who may transmit: random access with ALOHA (pure and slotted, throughput G e^(-2G) and G e^(-G) with maxima 1/(2e) and 1/e), carrier sensing (the persistence variants of CSMA), collision detection and binary exponential backoff, the minimum frame length 2 d R / v that makes collision detection work, and the efficiency of CSMA/CD; formulas are checked by simulation and exact enumeration.

Why it exists

On a shared cable (or a radio channel) only one station may transmit at a time; two simultaneous transmissions collide and both are destroyed. A multiple access protocol is the rule by which stations take turns without a central controller. This is the medium access control (MAC) sublayer of the data link layer. GATE asks for the throughput of ALOHA, the working of CSMA/CD and the minimum frame size.

Prerequisites

You need transmission and propagation delay (performance metrics).

Precise definitions

Multiple access protocols fall into three families (quoted classification): random access (ALOHA, CSMA, CSMA/CD, CSMA/CA: stations transmit when they have data and handle collisions), controlled access (polling, token passing, reservation: stations take turns) and channelisation (TDMA, FDMA, CDMA: the channel is divided in advance). This page treats random access.

Let the frame time $T_f = L/R$ be the time to transmit one frame. Let $G$ be the offered load: the average number of frame transmission attempts (new frames plus retransmissions) per frame time; let $S$ be the throughput: the average number of frames per frame time that are transmitted successfully. $S \le G$ , and $S = 1$ would mean the channel is always busy with good frames.

Pure ALOHA. A station sends whenever it has a frame; if no acknowledgement comes, it waits a random time and resends. A frame is received correctly only if no other frame overlaps it. Another frame starting within $T_f$ before or after its start overlaps it: the vulnerable period is $2 T_f$ .

S = G\,e^{-2G}, \qquad S_{max} = \tfrac{1}{2e} \approx 0.184 \text{ at } G = \tfrac12 .

Slotted ALOHA. Time is divided into slots of length $T_f$ and stations may start only at the beginning of a slot. Frames either collide completely or do not overlap at all; the vulnerable period is $T_f$ .

S = G\,e^{-G}, \qquad S_{max} = \tfrac{1}{e} \approx 0.368 \text{ at } G = 1 .

(These formulas assume that attempts form a Poisson process with $G$ per frame time.)

Carrier sense multiple access (CSMA). A station listens before it transmits and does not start if the channel is busy. This reduces collisions but cannot remove them: two stations can start within the propagation delay of each other. Variants decide what to do when the channel is busy (quoted): 1-persistent (keep listening and send immediately when it becomes idle; collisions are certain if two stations are waiting), non-persistent (wait a random time and listen again), $p$ -persistent (slotted channel: send in the idle slot with probability $p$ , else wait for the next slot).

CSMA/CD (collision detection). A station also listens while it transmits. If it detects another signal, it stops, sends a short jam signal so everybody notices, and waits a random time before trying again (binary exponential backoff). Used in classic Ethernet (Ethernet). For the station to detect a collision it must still be transmitting when the collision reaches it, which gives the minimum frame length below.

How it works

ALOHA

Throughput of ALOHA against the offered load: start

Computed by a script, not typed

offered load	pure ALOHA S	slotted ALOHA S
G = 0.1
G = 0.25
G = 0.5
G = 1.0
G = 1.5
G = 2.0
G = 3.0

Step 0

Maximum of pure ALOHA 0.1839 = 1/(2e) at G = 0.5; maximum of slotted ALOHA 0.3679 = 1/e at G = 1. Frame arrivals are a Poisson process (the standard model); a Monte Carlo simulation agrees to within 0.01.

0 / 7

computed by script: exact integer and fraction arithmetic, address calculations on bit patterns. python3 scripts/gen-cn2-traces.py

Pure ALOHA tops out at $18.4$ percent of the channel; slotted ALOHA doubles that to $36.8$ percent by halving the vulnerable period. Beyond the optimum more offered load reduces throughput (more collisions). With $n$ stations each transmitting in a slot with probability $p$ the chance that exactly one transmits is $n p (1-p)^{n-1}$ , maximal at $p = 1/n$ :

Slotted ALOHA with n stations, each transmitting with probability 1/n: start

Computed by a script, not typed

stations	P(a slot is used successfully)
1 station
2 stations
3 stations
5 stations
10 stations
50 stations
100 stations

Step 0

A slot is successful when exactly one station transmits.

0 / 7

computed by script: exact integer and fraction arithmetic, address calculations on bit patterns. python3 scripts/gen-cn2-traces.py

and it tends to $1/e$ as $n$ grows.

Binary exponential backoff

After the $i$ -th collision of the same frame the station chooses $K$ at random from $0, 1, \dots, 2^{\min(i, 10)} - 1$ and waits $K$ slot times; after $16$ failed attempts it gives up (the Ethernet constants, quoted). The range doubles after each collision, so the stations spread out quickly:

Binary exponential backoff: start

Computed by a script, not typed

event	range of K	values	mean wait (slots)	P(two stations collide again)	P(still colliding after this round)
after collision 1
after collision 2
after collision 3
after collision 4
after collision 5
after collision 6
after collision 7
after collision 8

Step 0

K is chosen uniformly from 0 … 2^min(i, 10) - 1 after the i-th collision; after 16 attempts the frame is dropped (values from the standard, quoted; the table shows i up to 8).

0 / 8

computed by script: exact integer and fraction arithmetic, address calculations on bit patterns. python3 scripts/gen-cn2-traces.py

Two stations that have just collided choose from $\{0, 1\}$ after the first collision and collide again with probability $1/2$ ; after the second, from $\{0, \dots, 3\}$ , probability $1/4$ ; the probability that they are still colliding after $i$ rounds is $2^{-i(i+1)/2}$ .

Minimum frame length

Station A starts at time $0$ on a cable with one-way propagation delay $\tau$ . The worst case: station B starts just before A's first bit reaches it, at $\tau - \varepsilon$ . B notices at once; A notices when B's signal reaches it, at $2\tau - \varepsilon$ . A must still be transmitting then (otherwise A believes its frame was sent successfully). Hence the transmission time of a frame must be at least $2\tau$ :

\frac{L_{min}}{R} \ge 2\tau = \frac{2d}{v} \quad\Longrightarrow\quad L_{min} = \frac{2 d R}{v},\qquad d_{max} = \frac{L\,v}{2R}.

Minimum frame length for collision detection: start

Computed by a script, not typed

network	round-trip time 2d/v	minimum frame (bits)	minimum frame (bytes)
10 Mbps, 1 km
10 Mbps, 2.5 km
100 Mbps, 200 m
1 Gbps, 200 m
10 Mbps, 2 km, v = 2.5 × 10^8 m/s

Step 0

A sender must still be sending when the news of a collision, at worst after twice the end-to-end propagation delay, arrives. Signal speed as stated. The standard's 512-bit minimum (64 bytes, 51.2 µs at 10 Mbps) includes margins for repeaters and is larger than the bare value for 2.5 km.

0 / 5

computed by script: exact integer and fraction arithmetic, address calculations on bit patterns. python3 scripts/gen-cn2-traces.py

For $10$ Mbps and $2.5$ km at $2 \times 10^8$ m/s: $2\tau = 25$ µs, $L_{min} = 250$ bits. The standard Ethernet minimum is $512$ bits ( $64$ bytes, $51.2$ µs at $10$ Mbps) to allow for repeaters and the jam signal. The faster the network the shorter the cable must be, or the longer the minimum frame.

Efficiency of CSMA/CD

Consider a busy network: each successful frame is preceded by a contention interval made of slots of length $2\tau$ . If each of $k$ ready stations transmits in a slot with probability $1/k$ , a slot is successful with probability $(1 - 1/k)^{k-1}$ :

Contention slots in CSMA/CD: start

Computed by a script, not typed

stations	P(contention slot succeeds)	mean contention slots
2 stations ready
5 stations ready
10 stations ready
100 stations ready
1000 stations ready

Step 0

Each contention slot has the length 2τ (round-trip time); the mean number of slots before a success tends to e.

0 / 5

computed by script: exact integer and fraction arithmetic, address calculations on bit patterns. python3 scripts/gen-cn2-traces.py

which tends to $1/e$ , so the mean number of contention slots is about $e$ and

\text{efficiency} = \frac{T_f}{T_f + 2\tau \cdot e} = \frac{1}{1 + 2 a e}, \qquad a = \frac{\tau}{T_f} = \frac{d R}{v L}.

The efficiency falls as $a$ (propagation delay compared with frame time) grows, which is why long, fast networks need big frames. Other textbooks give slightly different constants (see the verification notes); questions state the formula to use.

Worked examples

EX 1ALOHA throughput

Easy

$G = 0.5$ : pure ALOHA $S = 0.5\,e^{-1} = 0.1839$ ; slotted $S = 0.5\,e^{-0.5} = 0.3033$ . At $G = 1$ : pure $0.1353$ , slotted $0.3679$ . If the channel rate is $1$ Mbps and frames are $1000$ bits ( $T_f = 1$ ms), pure ALOHA at its best delivers $0.184$ frames per ms, that is $184$ kbps.

EX 2Minimum frame size

Medium

$10$ Mbps, cable $1$ km, signal speed $2 \times 10^8$ m/s: $2\tau = 10$ µs, $L_{min} = 10^7 \times 10^{-5} = 100$ bits ( $12.5$ bytes). With $1$ Gbps over $200$ m: $2\tau = 2$ µs, $L_{min} = 2000$ bits ( $250$ bytes).

EX 3Backoff probabilities

Medium

Two stations collide for the first time. Both pick from $\{0, 1\}$ : they collide again with probability $1/2$ (both $0$ or both $1$ ), succeed in the next slot... with probability $1/2$ (one picks $0$ and the other $1$ ). After a second collision they pick from $\{0, \dots, 3\}$ : collide again with probability $1/4$ . Probability that three rounds of collision happen in a row: $1/2 \times 1/4 \times 1/8 = 1/64$ .

EX 4Typical questions

GATE level

(a) "Maximum efficiency of pure ALOHA / slotted ALOHA?" $1/(2e) \approx 18.4$ percent, $1/e \approx 36.8$ percent. (b) "Vulnerable time of pure ALOHA with frame time $T$ ?" $2T$ . (c) "Why is a minimum frame size needed in CSMA/CD?" So the sender is still transmitting when a collision signal returns. (d) "Bandwidth $10$ Mbps, propagation $25.6$ µs: minimum frame?" $2 \times 25.6$ µs $\times 10$ Mbps $= 512$ bits. (e) "After the 3rd collision, the range of $K$ ?" $0$ to $7$ .

Cheat box

Pure ALOHA $S = G e^{-2G}$ , max $1/(2e) = 0.184$ at $G = 0.5$ ; slotted $S = G e^{-G}$ , max $1/e = 0.368$ at $G = 1$ .
Vulnerable period: pure $2T_f$ , slotted $T_f$ .
CSMA: listen first; CSMA/CD: listen while sending, jam, backoff.
Backoff after the $i$ -th collision: $K \in 0 \dots 2^{\min(i,10)} - 1$ slots; give up after $16$ .
$L_{min} = 2dR/v$ (transmission time $\ge 2\tau$ ); Ethernet: $512$ bits.
Efficiency about $1/(1 + 2ae)$ with $a = \tau / T_f$ (formula varies by book).

Traps and GATE patterns

Connections

Builds on

Delay, throughput and bandwidth-delay product

Unlocks

Delay, throughput and bandwidth-delay productuses Ethernet, frames and minimum frame sizePrerequisite of Ethernet, frames and minimum frame sizeuses Switches, learning bridges and VLANscontrasts with

Across subjects

No cross-subject links yet.

Within this subject

Delay, throughput and bandwidth-delay productuses Ethernet, frames and minimum frame sizeimplemented-by Error detection: parity, checksum and CRCuses

Ethernet is CSMA/CD with these parameters (Ethernet); modern switched Ethernet has no collisions at all. A detected-bad frame is dropped using the CRC (error detection). The factor $a = \tau/T_f$ is the same quantity that governs the utilisation of stop-and-wait (performance metrics).

PYQs

9 previous year questions from your book. I re-solved each one myself (7 by running or simulating, 2 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2024 · NATQ4 · page 533 of the book

Consider an Ethernet segment with a transmission
speed of 108 bits/sec and a maximum segment length
of 500 meters. If the maximum speed of propagation
of the signal in the medium is 2×108 meters/sec, then
the minimum frame size (in bits) required for
collision detection is __________.

GATE 2021 · NATQ10 · page 534 of the book

Consider a network using the pure ALOHA medium
access control protocol, where each frame is of length
1,000 bits. The channel transmission rate is
1Mbps(= 106 bits per second). The aggregate
number of transmissions across all the nodes
(including new frame transmissions and retransmitted
frames due to collisions) is modelled as a Poisson
process with a rate of 1,000 frames per second.
Throughput is defined as the average number of
frames successfully transmitted per second. The
throughput of the network (rounded to the nearest
integer) is ____________

GATE 2018 · NAT · 2 marksQ11 · page 534 of the book

Consider a simple communication system where
multiple nodes are connected by a shared broadcast
medium (like Ethernet or wireless).

The nodes in the system use the following carrier-
sense based medium access protocol.

A node that receives a packet to transmit will carrier-
sense the medium for 5 units of time.

COMPUTER NETWORK

If the node does not detect any other transmission
in this duration, it starts transmitting its packet in
the next time unit.

If the node detects another transmission, it waits
until this other transmission finishes and then
begins to carrier-sense for 5 time units again.

Once they start to transmit, nodes do not perform
any collision detection and continue transmission
even if a collision occurs.

All transmissions last for 20 units of time.

Assume that the transmission signal travels at the
speed of 10 meters per unit time in the medium.

Assume that the system has two nodes P and Q,
located at a distance d meter from each other.

P starts transmitting a packet at time t=0 after
successfully completing its carrier-sense phase.
Node Q has a packet to transmit at time t=0 and
begins to carrier-sense the medium.

The maximum distance d (in meters, rounded to the
closest integer) that allows Q to avoid a collision
between its proposed transmission and P's ongoing
transmission is _______.

GATE 2016 · NATQ18 · page 536 of the book

A network has a data transmission bandwidth of
20×106 bits per second. It uses CSMA/CD in the
MAC layer. The maximum signal propagation time
from one node to another node is 40 microseconds.
The minimum size of a frame in the network is
______ bytes.

GATE 2016 · MCQQ19 · page 536 of the book

In an Ethernet local area network, which one of the
following statements is TRUE?

(a)A station stops to sense the channel once it starts transmitting a frame.
(b)The purpose of the jamming signal is to pad the frames that are smaller than the minimum frame size.
(c)A station continues to transmit the packet even after the collision is detected.
(d)The exponential backoff mechanism reduces the probability of collision on retransmissions

GATE 2015 · NATQ21 · page 536 of the book

Consider a LAN with four nodes S1,S2,S3,S4. Time
is divided into fixed-size slots, and a node can begin
its transmission only at the beginning of a slot. A
collision is said to have occurred if more than one
node transmits in the same slot. The probabilities of
generation of a frame in a time slot by S1,S2,S3 and
S4 are 0.1, 0.2, 0.3, and 0.4, respectively. The
probability of sending a frame in the first slot without
any collision by any of these four stations is
__________.

GATE 2007 · MCQ · 2 marksQ36 · page 539 of the book

In a token ring network, the transmission speed is
107 bps and the propagation speed is 200 metres/μs.
The 1-bit delay in this network is equivalent to:

(a)500 metres of cable
(b)200 metres of cable
(c)20 metres of cable
(d)50 metres of cable

GATE 2007 · MCQ · 2 marksQ37 · page 539 of the book

There are n stations in a slotted LAN. Each station
attempts to transmit with a probability p in each
time slot. What is the probability that ONLY one
station transmits in a given time slot?

(a)np(1 - p)n-1
(b)(1 - p)n-1
(c)p(1 - p)n-1
(d)1 - (1 - p)n-1

GATE 2005 · MCQ · 2 marksQ44 · page 540 of the book

Suppose the round trip propagation delay for a 10
Mbps Ethernet having 48-bit jamming signal is 46.4
μs. The minimum frame size is:

(a)94
(b)416
(c)464
(d)512

Self-check

Question 1

Slotted ALOHA, $G = 2$ . What is the throughput?

Show answer

$S = 2 e^{-2} = 0.2707$ .

Question 2

A CSMA/CD network at $100$ Mbps has minimum frame $512$ bits and signal speed $2 \times 10^8$ m/s. Maximum cable length by the formula?

Show answer

$d = L v/(2R) = 512 \times 2 \times 10^8 / (2 \times 10^8) = 512$ m.

Question 3

Why does the backoff range double?

Show answer

A collision suggests many stations are competing; choosing from a larger range makes a repeated collision less likely.

Revision card

One-screen revision

Pure ALOHA $G e^{-2G}$ (max 18.4 percent), slotted $G e^{-G}$ (max 36.8 percent).
CSMA/CD: listen, jam, binary exponential backoff.
$L_{min} = 2dR/v$ ; Ethernet $512$ bits.
Collisions possible within one propagation delay.

References

·Kurose, Ross, Computer Networking: A Top-Down Approach (8th edition), Chapter 6, Section 6.3 (Multiple access links and protocols)
·Tanenbaum, Wetherall, Computer Networks (5th edition), Chapter 4 (The medium access control sublayer), Sections 4.1 and 4.2
·Forouzan, Data Communications and Networking (5th edition), Chapter 12 (Multiple access)

Verification

scripts/enum-checks/cn_net_check.py: the throughput formulas S = G e^(-2G) (pure ALOHA) and S = G e^(-G) (slotted) agree with a Monte Carlo simulation of Poisson arrivals (200000 frames per load, tolerance 0.01) at G = 0.25, 0.5, 1, 1.5, their maxima were located by scanning (G = 0.5 and G = 1); the slotted success probability n p (1-p)^(n-1) is maximal at p = 1/n for n = 2..19 and agrees with simulation; after the i-th collision two stations choose from the same range of 2^min(i,10) values and collide again with probability 2^-min(i,10), confirmed by simulation for i = 1..5; the mean number of contention slots 1/(1-1/k)^(k-1) increases towards e from below (2.0 at k = 2, 2.7169 at k = 1000); the minimum frame length L = 2dR/v is the exact condition of the timing model in which the second station starts just before the first bit reaches it. THE CSMA/CD EFFICIENCY FORMULA: the page derives 1/(1 + 2 a e) from the contention-slot model (a = tau / frame time); textbooks give different versions (for example 1/(1 + 5a) as an approximation, 1/(1 + 6.44a) in other books): these are QUOTED/NEEDS VERIFICATION and exam questions state which to use. The persistence variants, the parameters of Ethernet backoff (cap 10, 16 attempts, 51.2 microsecond slot) and CSMA/CA are QUOTED from the textbooks. Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (CRC remainders, binomial tail, checksums); long C programs were not re-read line by line (they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Hamming code (error correction)

Ethernet, frames and minimum frame size