CSMA/CD and Ethernet timing

The original 10 Mb/s budget combines 46.38 microseconds of round-trip delays with 4.8 microseconds of jam time. Compare that 51.18-microsecond total with the 512-bit-time slot, then inspect the original backoff and efficiency models.

Carrier sensing cannot remove propagation uncertainty

CSMA/CD (carrier sense multiple access with collision detection) is how classic Ethernet let many computers share one cable. Three rules make it up. A station listens before it sends and waits while the cable is busy (carrier sense). It keeps listening while it sends and stops as soon as it hears another signal (collision detection). After a collision it waits a random number of slot times, and the range doubles with every further collision (binary exponential backoff). One timing rule follows from the physics: a sender must still be transmitting when news of a collision gets back from the far end, which is why an Ethernet frame is at least 64 bytes long. Today’s switched links are full duplex, with nothing shared and so nothing to collide, and CSMA/CD survives only as a half-duplex mode in the standard.

The ALOHA lesson showed what random access costs when stations send blindly: at most 18.4 % or 36.8 % of the channel gets through. On a cable a station can do better, because it can hear whether anyone else is sending. Robert Metcalfe added this carrier sense to the ALOHA idea when he designed Ethernet at Xerox PARC, and Leonard Kleinrock and Fouad Tobagi analysed several versions of it in a paper of their own. The versions differ in what a station does when it finds the channel busy:

• 1-persistent: wait until the channel goes quiet, then send at once. Ethernet works this way: after the last bit of a passing frame it waits the interframe gap, 9.6 µs at 10 Mb/s, and starts sending if it has a frame.
• Non-persistent: back off for a random time and listen again, which wastes some idle time but avoids a pile-up of stations that were all waiting for the same frame to end.
• p-persistent: on a slotted channel, send in the first idle slot with probability p, otherwise wait a slot.

Listening cannot prevent every collision, because a signal takes time to travel. A station that hears silence is hearing the past: another station may have started a moment ago, and its first bit is still on its way down the cable. Once a frame’s first bit has reached every station, everyone defers to it, so collisions can only happen in that first stretch, one one-way propagation time long. That is why carrier sense does so much better than ALOHA when the propagation time is small compared with the time it takes to send a frame.

Keep local silence distinct from the arrival time of another station’s signal.

The jam keeps a detected collision visible

Distinguish collision detection from completion of a successful data frame. The extra jam signal belongs to the failed attempt’s declared timing budget. Its receiver interpretation, length and retry behaviour follow the stated specification. A teaching model may omit physical signal details while still illustrating that budget, but it should name those omissions. Keep the original specification table and measured arithmetic beside that limited model.

A station on a cable can do one more thing that an ALOHA radio could not: notice the collision while it is still sending. The 1982 Ethernet specification of Digital, Intel and Xerox (DIX Ethernet, the basis of the IEEE 802.3 standard) has the station keep sending for at least 32 and at most 48 more bits after it detects a collision, a jam, so that the collision lasts long enough for every transmitting station to notice it. Then it stops and backs off.

Two things follow. A collision now wastes only about one round trip of the cable instead of a whole frame. And the pieces of collided frames that reach the receivers are short, so the specification tells a receiver to treat any frame of fewer than 64 octets as a collision fragment and to discard it.

Read the original 48-bit jam as part of collision detection and retry timing.

The frame must outlast the declared round-trip budget

Collision detection only works if the sender is still sending when the collision reaches it. Picture the worst case:

Station A starts. Its first bit needs one one-way delay τ to reach station B at the far end. Just before it arrives, B hears an idle cable and starts too, and at once it hears A and stops. B’s signal now has to travel all the way back, and it reaches A only after almost 2τ. If A has finished its frame by then, it never learns that the frame was destroyed. So a frame must last at least one round trip:

where R is the bit rate, d the length of the cable and v the speed of the signal, about 2 × 10⁸ m/s in copper.

Classic Ethernet turned this into one number, the slot time of 512 bit times, 51.2 µs at 10 Mb/s. The DIX specification gives the slot three jobs at once: it is an upper bound on how long a station needs to take hold of the cable, an upper bound on the length of a collision fragment, and the unit of time for retransmissions. To do them, the slot must be longer than the collision round-trip budgetcollision round-trip budget: The propagation, electronics, detection and other specified delays used to determine whether a transmitting station can still detect a collision. of the largest network the rules allow, plus the longest jam. The specification’s own budget shows where the 512 bits go:

"""Where the 512-bit slot of 10 Mb/s Ethernet goes.

The worst-case round-trip delays of the largest network allowed by the Ethernet
Version 2.0 specification of Digital, Intel and Xerox (Table 7-1), in microseconds,
grouped by what causes them. One bit time at 10 Mb/s is 0.1 microseconds.
"""

BUDGET = {
    "cable: 1,500 m of coaxial cable": 12.99,
    "cable: 1,000 m of point-to-point links": 10.26,
    "cable: 300 m of transceiver cables": 3.08,
    "transceivers and encoders": 2.70 + 2.10 + 1.95 + 2.00,
    "repeaters and link electronics": 1.20 + 0.80 + 0.40 + 0.40,
    "carrier sense and collision detect": 1.00 + 1.00,
    "signal rise times and timer tolerance": 6.00 + 0.30 + 0.20,
}

BIT_TIME_US = 0.1
JAM_BITS = 48            # the longest jam a station may send

for part, us in BUDGET.items():
    print(f"{us:6.2f} µs  {part}")
round_trip = sum(BUDGET.values())
jam = JAM_BITS * BIT_TIME_US
cable = sum(us for part, us in BUDGET.items() if part.startswith("cable"))
print(f"{round_trip:6.2f} µs  worst-case round trip ({round_trip / BIT_TIME_US:.0f} bit times)")
print(f"{jam:6.2f} µs  plus the longest jam ({JAM_BITS} bits)")
print(f"{round_trip + jam:6.2f} µs  must fit in one slot: 512 bit times = {512 * BIT_TIME_US:.1f} µs")
print(f"cable alone is {cable:.2f} µs, {cable / round_trip:.0%} of the round trip")

 12.99 µs  cable: 1,500 m of coaxial cable
 10.26 µs  cable: 1,000 m of point-to-point links
  3.08 µs  cable: 300 m of transceiver cables
  8.75 µs  transceivers and encoders
  2.80 µs  repeaters and link electronics
  2.00 µs  carrier sense and collision detect
  6.50 µs  signal rise times and timer tolerance
 46.38 µs  worst-case round trip (464 bit times)
  4.80 µs  plus the longest jam (48 bits)
 51.18 µs  must fit in one slot: 512 bit times = 51.2 µs
cable alone is 26.33 µs, 57% of the round trip

Only 57 % of the round trip is cable; transceivers, repeaters and the time it takes to recognise a signal take the rest. With the jam, the total, 51.18 µs, just fits in 51.2 µs. A frame of 512 bits is 64 bytes: 6 bytes of destination address, 6 of source address, 2 of type, 46 of data and 4 of frame check sequence. A shorter message is padded to 46 bytes of data, whatever the real length of the cable.

Compare the original 51.18-us total with its 51.2-us slot rather than using cable delay alone.

A fixed bit slot covers less distance at a higher rate

The minimum frame grows with the bit rate, so the same cable that suits a 10 Mb/s network does not suit a faster one:

"""The shortest frame that still detects every collision, cable delay only.

A sender must still be transmitting when news of a collision gets back from the
far end, so a frame needs at least 2 * distance / speed seconds on the wire:
L_min = 2 * distance * rate / speed bits. Signals travel at about 2 * 10**8 m/s.
"""
import math

SPEED = 200_000_000       # metres per second

RATES = {"10 Mb/s": 10_000_000, "100 Mb/s": 100_000_000, "1 Gb/s": 1_000_000_000}


def bits_needed(rate, distance):
    return math.ceil(2 * distance * rate / SPEED)


print("rate         200 m      2,800 m")
for name, rate in RATES.items():
    print(f"{name:9} {bits_needed(rate, 200):6,} bits  {bits_needed(rate, 2_800):7,} bits")

print()
print("cable that a slot can cover, before any electronics:")
for name, rate, slot in [("10 Mb/s", 10_000_000, 512), ("100 Mb/s", 100_000_000, 512), ("1 Gb/s", 1_000_000_000, 512), ("1 Gb/s", 1_000_000_000, 4096)]:
    print(f"  {name:9} {slot:4}-bit slot: {slot * SPEED / (2 * rate):7,.1f} m")

rate         200 m      2,800 m
10 Mb/s       20 bits      280 bits
100 Mb/s     200 bits    2,800 bits
1 Gb/s     2,000 bits   28,000 bits

cable that a slot can cover, before any electronics:
  10 Mb/s    512-bit slot: 5,120.0 m
  100 Mb/s   512-bit slot:   512.0 m
  1 Gb/s     512-bit slot:    51.2 m
  1 Gb/s    4096-bit slot:   409.6 m

At 10 Mb/s, 2.8 km of cable (the largest station separation the DIX specification allows) needs only 280 bits of round trip, comfortably inside 512. At 100 Mb/s the same distance would need 2,800 bits, so a 100 Mb/s collision domain that keeps the 512-bit slot must be about ten times smaller, and the slot covers at most 512 m of cable before any electronics are counted. At 1 Gb/s a 512-bit slot covers only 51.2 m. When the IEEE 802.3z task force designed half-duplex Gigabit Ethernet, it wanted at least 200 metres, two 100-metre runs to the desktop, and its bit budget exceeded 512 bit times even with short cables. Its answer was carrier extensioncarrier extension: Non-data symbols that extend medium occupancy for the declared half-duplex gigabit slot budget while leaving the frame's data and FCS unchanged.: the slot became 4,096 bit times (512 bytes) at 1 Gb/s, and a short frame is followed by non-data symbols until the signal has lasted a full slot. The data and the frame check sequence stay exactly as they were, so a 64-byte frame is still a 64-byte frame.

Keep frame bytes separate from the original 4,096-bit-time medium occupancy.

The exponent stops at ten and the attempt limit is separate

After a collision, both senders must try again, and if they both retried after the same delay they would collide again. Ethernet picks the delay at random, in whole slot times, from a range that doubles with every collision of the same frame. The DIX specification defines the wait before the n-th retransmission as a uniformly distributed random integer r with 0 ≤ r < 2^k, where k = min(n, 10); after 16 attempts, the first one and 15 retries, the station gives up and reports an error. It is called truncated backofftruncated backoff: A retry delay rule whose exponential choice range stops growing at a stated exponent cap, with a separate limit on attempts. because the doubling stops at 1,024 slots.

"""Truncated binary exponential backoff, collision by collision.

After the n-th collision of a frame, a station waits r slot times, with r drawn
uniformly from 0 .. 2**k - 1 and k = min(n, 10). After 16 attempts it gives up.
One slot time at 10 Mb/s is 512 bit times, 51.2 microseconds.
"""

SLOT_US = 51.2
BACKOFF_LIMIT = 10
ATTEMPT_LIMIT = 16


def duration(us):
    return f"{us:7.1f} µs" if us < 1000 else f"{us / 1000:7.2f} ms"


print("collision  choices  mean wait")
worst = 0
for n in range(1, ATTEMPT_LIMIT + 1):
    if n == ATTEMPT_LIMIT:
        print(f"{n:9}  the frame is dropped: excessive collisions")
        break
    choices = 2 ** min(n, BACKOFF_LIMIT)
    mean_slots = (choices - 1) / 2
    worst += choices - 1
    if n <= 4 or n >= 10:
        print(f"{n:9}  {choices:7}  {mean_slots:5.1f} slots = {duration(mean_slots * SLOT_US)}")
    elif n == 5:
        print("      ...")
print(f"longest possible total wait: {worst:,} slots = {worst * SLOT_US / 1000:.1f} ms")

collision  choices  mean wait
        1        2    0.5 slots =    25.6 µs
        2        4    1.5 slots =    76.8 µs
        3        8    3.5 slots =   179.2 µs
        4       16    7.5 slots =   384.0 µs
      ...
       10     1024  511.5 slots =   26.19 ms
       11     1024  511.5 slots =   26.19 ms
       12     1024  511.5 slots =   26.19 ms
       13     1024  511.5 slots =   26.19 ms
       14     1024  511.5 slots =   26.19 ms
       15     1024  511.5 slots =   26.19 ms
       16  the frame is dropped: excessive collisions
longest possible total wait: 7,151 slots = 366.1 ms

After a first collision a station waits 0 or 1 slot, on average 25.6 µs at 10 Mb/s. By the tenth collision it chooses among 1,024 slots, an average wait of 26.19 ms, and in the very worst case a frame spends 7,151 slots, about 0.37 seconds, waiting before it is dropped. The specification adds that these values are the most aggressive a station may use: an implementation may wait longer, never less.

Why doubling? A collision is evidence that more than one station is competing, and each further collision suggests there are more still. The ALOHA lesson found that random access works best when each of n competitors sends in a slot with a probability of about 1/n. Doubling the range after each collision reaches a range of about n slots within a few collisions, without anyone counting the stations. The original simplified slot simulation starts several stations with one frame each, illustrating contention and range growth. It does not model every physical CSMA/CD detail or the standard sixteen-attempt drop:

"""Binary exponential backoff at work: n stations, one frame each, all ready at once.

Time runs in slots. A station sends when its waiting time is up; if it is the only
sender in that slot, its frame gets through (frames here last one slot), otherwise
every sender in the slot has collided and draws a new wait. The generator is
seeded, so every run prints the same numbers.
"""
import random

TRIALS = 2_000


def run(stations, rng):
    collisions = [0] * stations       # collisions each station's frame has had
    wait = [0] * stations             # slots until each station sends again
    waiting = set(range(stations))
    slot = 0
    while waiting:
        senders = [s for s in waiting if wait[s] == 0]
        if len(senders) == 1:
            waiting.discard(senders[0])
        else:
            for s in senders:
                collisions[s] += 1
                k = min(collisions[s], 10)
                wait[s] = rng.randrange(2 ** k) + 1   # + 1: the wait starts after this slot
        for s in waiting:
            if s not in senders:
                wait[s] -= 1
        slot += 1
    return slot, sum(collisions), max(collisions)


rng = random.Random(7)
print("stations  slots to finish  collisions a frame  worst frame")
for stations in [2, 3, 5, 10]:
    results = [run(stations, rng) for _ in range(TRIALS)]
    slots = sum(r[0] for r in results) / TRIALS
    per_frame = sum(r[1] for r in results) / (TRIALS * stations)
    worst = max(r[2] for r in results)
    print(f"{stations:8}  {slots:15.1f}  {per_frame:18.2f}  {worst:6} collisions")

stations  slots to finish  collisions a frame  worst frame
       2              6.8                1.64       5 collisions
       3             10.7                2.03       5 collisions
       5             19.6                2.72       6 collisions
      10             48.1                3.81       7 collisions

With ten stations all ready at once, every frame got through within 48 slots on average. A frame met 3.8 collisions on average and never more than 7, far from the limit of 16. The growing range also gives the backoff its weak point: a frame that has collided many times waits on average far longer than a newcomer, so under heavy load a station that has been unlucky tends to stay unlucky for a while.

Compare the capped 1,024-choice range with the separate sixteen-attempt limit.

Efficiency estimates depend on the contention model

Efficiency is the share of time the cable carries frames that get through when every station always has something to send. It depends on one ratio, the the propagation-to-frame ratiopropagation-to-frame ratio: One-way propagation time divided by frame transmission time, used with the assumptions of a stated contention-efficiency model.:

Under heavy load, each successful frame is preceded by a contention period: a run of slots, each lasting 2τ, in which stations collide until one of them gets through on its own. If the stations behave as well as they can, each such slot succeeds with a probability of about 1/e (the slotted ALOHA result), so a frame waits on average about e slots. That gives

Metcalfe and Boggs described a heavy-load model of this kind in their paper on the first Ethernet. The approximation $E \approx 1/(1 + 5a)$ is the rounded form most often quoted, and some versions also count the time the frame’s last bit needs to reach the far end, which gives $1/(1 + 6.44a)$. They all say the same thing, and a numerical question will tell you which one it wants:

"""CSMA/CD efficiency under heavy load, with three common versions of the model.

a = one-way propagation time / frame transmission time. Each frame waits for a
contention period of about e slots of 2 * tau before it gets the channel, which
gives E2; E1 is the rounded form, and E3 also counts the time the frame's last bit
needs to reach the far end. "Worst case" is the largest 10 Mb/s network, whose
round trip uses a whole 51.2-microsecond slot (tau = 25.6 microseconds).
"""
import math

CASES = [
    # label, rate in bit/s, one-way propagation time in microseconds, frame bytes
    ("10 Mb/s, worst case, 64 B", 10_000_000, 25.6, 64),
    ("10 Mb/s, worst case, 1518 B", 10_000_000, 25.6, 1518),
    ("10 Mb/s, 200 m, 64 B", 10_000_000, 1.0, 64),
    ("100 Mb/s, 200 m, 64 B", 100_000_000, 1.0, 64),
    ("100 Mb/s, 200 m, 1518 B", 100_000_000, 1.0, 1518),
]

print("E1 = 1/(1 + 5a)  E2 = 1/(1 + 2e·a)  E3 = 1/(1 + (2e + 1)·a)")
print()
print(f"{'':27} {'a':>5}  {'E1':>5}  {'E2':>5}  {'E3':>5}")
for label, rate, tau_us, size in CASES:
    frame_us = size * 8 / rate * 1_000_000
    a = tau_us / frame_us
    e1, e2, e3 = 1 / (1 + 5 * a), 1 / (1 + 2 * math.e * a), 1 / (1 + (2 * math.e + 1) * a)
    print(f"{label:27} {a:5.3f}  {e1:5.1%}  {e2:5.1%}  {e3:5.1%}")

E1 = 1/(1 + 5a)  E2 = 1/(1 + 2e·a)  E3 = 1/(1 + (2e + 1)·a)

                                a     E1     E2     E3
10 Mb/s, worst case, 64 B   0.500  28.6%  26.9%  23.7%
10 Mb/s, worst case, 1518 B 0.021  90.5%  89.7%  88.1%
10 Mb/s, 200 m, 64 B        0.020  91.1%  90.4%  88.8%
100 Mb/s, 200 m, 64 B       0.195  50.6%  48.5%  44.3%
100 Mb/s, 200 m, 1518 B     0.008  96.0%  95.7%  95.0%

Minimum-size frames on the largest 10 Mb/s network spend most of their time contending: about 27 %. Full-size frames on the same network reach about 90 %, and so do minimum-size frames on 200 m of cable. At 100 Mb/s over the same 200 m, the frame time shrinks ten-fold, a grows ten-fold, and minimum-size frames fall to about 50 %. Long frames and short cables keep CSMA/CD efficient; at fixed propagation time and frame size, an increased rate raises this model’s ratio and lowers its estimated efficiency.

Read the original 28.6, 26.9 and 23.7 percentages as model-dependent estimates.

A full-duplex two-ended link has no shared collision domain

Twisted-pair and fibre Ethernet links connect exactly two devices, and in full-duplex mode both of them can send and receive at the same time. When a computer is connected to a switch port, nothing else is on the link, so there is nothing to sense, nothing to collide with and nothing to back off from. In this full-duplex mode CSMA/CD is simply switched off. IEEE 802.3-2022 still specifies the CSMA/CD protocol for shared, half-duplex media, and repeaters for speeds up to 1000 Mb/s, alongside full-duplex operation. In practice the half-duplex mode has faded: RFC 3635, which defines Ethernet’s standard management counters, notes that interfaces of 10 Gb/s and faster do not support half duplex and that very few 1000 Mb/s interfaces do, and its collision counters never increase on an interface in full-duplex mode.

Two consequences are worth remembering. On a full-duplex link the cable length is limited by the physical layer, how far the signal stays clean, and no longer by the slot time. And the 64-byte minimum frame remains, kept for compatibility rather than for collision detection. Switching moved the sharing problem from the cable into the switch, which now decides what to do when two frames want the same output port, the subject of the next module.

Separate the original full-duplex access link from competition for one switch output.

Practise the original access and frame contracts

Interview questions

Why must an Ethernet frame on a shared cable be at least 64 bytes long? So that a sender is still transmitting when news of a collision arrives from the farthest point of the network. In the worst case another station starts just before the first bit reaches it, and that collision takes a whole round trip to come back, so a frame must last at least the round-trip time. The 10 Mb/s rules budget less than 464 bit times for the round trip of the largest allowed network and up to 48 bits for the jam, and both fit in a slot of 512 bits, which is 64 bytes. A station that finished sending before the collision got back would think its frame had been delivered. Shorter frames are padded, and receivers discard anything shorter as a collision fragment.

Key takeaways

• CSMA/CD is three rules: listen and defer while the cable is busy, stop and jam when a collision is heard, then wait a random number of slot times before trying again.
• A sender must still be sending when a collision gets back from the far end: L_min = 2τR = 2dR/v.
• At 10 Mb/s the slot is 512 bit times (51.2 µs), so frames are at least 64 bytes; half-duplex gigabit stretched the slot to 4,096 bit times with carrier extension.
• Backoff: after the n-th collision wait r slots, 0 ≤ r < 2^min(n, 10); give up after 16 attempts.
• Efficiency falls as a = τ/T_frame grows: about 1/(1 + 5a), so long frames and short cables keep it high.
• Full-duplex links have no shared medium and therefore no collisions; CSMA/CD remains in IEEE 802.3 only for half-duplex operation.