The Data Link Layer: Framing, Error Control, MAC & Switching
The physical layer moves raw bits: voltages on copper, light pulses in fibre, radio symbols in the air. Bits on their own aren't useful. They get flipped by noise, they have no start or end, and when several machines share one wire they talk over each other. The data link layer (layer 2) turns that unreliable bit pipe into something the network layer can use: frames that are delimited, addressed, checked for corruption, and delivered to the right neighbour on the same link.
Every packet you have ever sent crossed layer 2 once per hop. Your laptop wraps an IP packet in an 802.11 frame for the access point, the access point re-wraps it in an Ethernet frame for the switch, the router strips that and builds a new frame for the next link, and so on. IP addresses stay the same end to end. MAC addresses change on every hop.
This page covers the classic textbook material (framing, CRC, Hamming codes, ARQ protocols, ALOHA, CSMA) with numbers worked step by step, then the practical side: Ethernet, ARP, switches, VLANs and spanning tree, and what they look like on Linux and in the cloud. For where layer 2 sits in the stack, see OSI Model & TCP/IP Stack. For how a frame gets from the NIC into the kernel, see The Linux Networking Stack.
What the Data Link Layer Does
| Responsibility | Question it answers | Mechanism |
|---|---|---|
| Framing | Where does a unit of data start and end? | Flags, byte/bit stuffing, length fields, preambles |
| Physical addressing | Which machine on this link is it for? | 48-bit MAC addresses |
| Error detection | Did the bits arrive intact? | Parity, checksums, CRC (Ethernet FCS) |
| Error correction (some links) | Can we fix it without resending? | Hamming codes, FEC (Wi-Fi, 5G, optical, ECC RAM) |
| Flow control | Is the sender overrunning the receiver? | Stop-and-wait, sliding windows, Ethernet PAUSE frames |
| Reliable delivery (some links) | Resend lost frames? | ARQ: stop-and-wait, Go-Back-N, Selective Repeat |
| Medium access control | Who gets to talk on a shared medium? | ALOHA, CSMA/CD, CSMA/CA, token passing |
IEEE splits the layer into two sublayers:
flowchart TB
NL["Network layer (IP)"] --> LLC
subgraph DLL["Data Link Layer"]
LLC["LLC sublayer (802.2): multiplexes protocols, optional flow/error control"]
MAC["MAC sublayer (802.3, 802.11): addressing, framing, channel access, FCS"]
LLC --> MAC
end
MAC --> PHY["Physical layer: encoding, signalling, medium"]
In modern Ethernet the LLC is very thin. The EtherType field does the protocol multiplexing and no link-level retransmission happens. Wi-Fi is different: it retransmits at layer 2 because radio loss rates are high. Keep that contrast in mind. Which layer retransmits is a design decision that depends on how lossy the link is.
Framing
The receiver sees a continuous stream of bits. Framing tells it where each frame begins and ends. There are four classic methods.
1. Character (Byte) Count
Put the length in a header field: "the next 57 bytes are this frame." It's simple and fragile. If noise corrupts the count, the receiver loses sync and every later frame boundary is wrong. Nobody uses a bare byte count on its own. Ethernet does carry a length/type field, but it relies on preambles and inter-frame gaps for synchronisation, not on the count.
2. Flag Bytes with Byte Stuffing
Start and end each frame with a special flag byte. PPP and HDLC-style framing use 0x7E (01111110). The problem: what if the payload itself contains 0x7E? The fix is to escape it. PPP uses an escape byte 0x7D, and any 0x7E or 0x7D in the payload is sent as 0x7D followed by the original byte XOR 0x20.
Worked example — payload 41 7E 42 7D 43:
| Step | Byte | Action | Emitted |
|---|---|---|---|
| start | — | opening flag | 7E |
| 1 | 41 | ordinary | 41 |
| 2 | 7E | flag inside data → escape, 7E ⊕ 20 = 5E | 7D 5E |
| 3 | 42 | ordinary | 42 |
| 4 | 7D | escape byte inside data → escape, 7D ⊕ 20 = 5D | 7D 5D |
| 5 | 43 | ordinary | 43 |
| end | — | closing flag | 7E |
On the wire: 7E 41 7D 5E 42 7D 5D 43 7E. The receiver strips the flags. Whenever it sees 7D, it drops it and XORs the next byte with 20. A real 7E can now only mean "frame boundary."
The cost is that overhead depends on the data. A payload made entirely of 7E bytes doubles in size.
3. Flag Bits with Bit Stuffing
HDLC works at the bit level. The flag is 01111110, which is six 1s in a row. The sender inserts a 0 after every run of five consecutive 1s in the data, so six 1s can never appear inside a frame. The receiver removes any 0 that follows five 1s.
Worked example:
Data: 0110111111111111110010
Stuffed: 011011111 0 11111 0 1111 0010
→ 011011111011111011110010
Walking through it: after 0110 we hit a run of 1s. After the fifth 1, insert 0. Counting starts again. Five more 1s, insert 0. The remaining four 1s don't reach five, so nothing is inserted before 0010.
A data pattern that looks exactly like the flag, 01111110, becomes 011111010 after stuffing. The receiver never sees six 1s in a row, so it can't mistake the data for a flag.
Why bit stuffing still matters
Bit stuffing has a second job besides framing. It guarantees transitions in the signal, so long runs of 1s don't leave the receiver's clock without edges to lock onto. Modern PHYs do this with line codes instead (8b/10b, 64b/66b), which also mark frame boundaries with special control symbols.
4. Physical-Layer Coding Violations
Use signal patterns that can't occur in valid data as delimiters. 8b/10b encoding (Gigabit Ethernet over fibre, PCIe up to gen 2, SATA) has K-codes that never appear as data symbols. 64b/66b (10G and faster) has control blocks. This is the most robust method because it costs no payload bandwidth.
The Ethernet II Frame
Ethernet combines a preamble for synchronisation, fixed-size addresses, a type field, and a CRC trailer.
7 bytes 1 6 6 (4) 2 46–1500 4
┌────────┬───┬─────────┬─────────┬──────────┬───────────┬──────────────┬─────┐
│Preamble│SFD│ Dst MAC │ Src MAC │802.1Q tag│ EtherType │ Payload │ FCS │
│10101010│ D5│ │ │(optional)│ / Length │ │CRC32│
└────────┴───┴─────────┴─────────┴──────────┴───────────┴──────────────┴─────┘
└── PHY: not counted in frame size ──┘└──────── 64 to 1518 bytes (1522 tagged) ───┘
| Field | Size | Purpose |
|---|---|---|
| Preamble | 7 B | 10101010 ×7, lets the receiver's clock lock on |
| SFD (Start Frame Delimiter) | 1 B | 10101011, the last two 1s mark "frame starts now" |
| Destination MAC | 6 B | Comes first so a switch can start forwarding before the frame finishes (cut-through) |
| Source MAC | 6 B | What switches learn from |
| 802.1Q tag | 4 B | Optional VLAN tag (see VLANs below) |
| EtherType / Length | 2 B | ≥ 0x0600 (1536) = EtherType: 0x0800 IPv4, 0x86DD IPv6, 0x0806 ARP, 0x8100 VLAN. ≤ 1500 = 802.3 length field |
| Payload | 46–1500 B | Padded up to 46 bytes if shorter |
| FCS | 4 B | CRC-32 over destination through payload |
After the frame comes a mandatory inter-frame gap of 12 byte times (96 bit times) of idle.
Worked example: what fraction of a link is actually data?
For a full-size frame carrying a 1500-byte IP packet, the bytes on the wire are:
- 8 (preamble + SFD) + 14 (header) + 1500 (payload) + 4 (FCS) + 12 (IFG) = 1538 bytes
- Efficiency = 1500 / 1538 = 97.5%. So a 10 Gbit/s link carries about 9.75 Gbit/s of IP packets at most.
For minimum-size frames (64 bytes from destination through FCS), the wire carries 64 + 8 + 12 = 84 bytes = 672 bits per frame:
- 10 Gbit/s ÷ 672 bits = 14.88 million frames per second. That's the famous "line rate" number for small-packet benchmarks, and it explains why kernel-bypass stacks exist (see The Linux Networking Stack).
Error Detection
Bits flip. Thermal noise, crosstalk, a cheap cable or a microwave oven can all do it. The receiver needs to notice, and the tool for that is redundancy: the sender adds check bits computed from the data, and the receiver recomputes them and compares.
The Hamming distance between two codewords is the number of bit positions where they differ. If a code's minimum distance is d:
- it can detect up to d − 1 bit errors
- it can correct up to ⌊(d − 1)/2⌋ bit errors
So to correct 1 error you need d = 3. To correct 1 and detect 2 you need d = 4 (SECDED, the scheme behind ECC memory).
Single Parity Bit
Append one bit so the total number of 1s is even (even parity) or odd (odd parity).
| Data | Count of 1s | Even parity bit | Sent |
|---|---|---|---|
1011001 | 4 | 0 | 10110010 |
1011011 | 5 | 1 | 10110111 |
It detects any odd number of bit errors and misses every even number. Minimum distance is 2, so it can't correct anything. It's fine where errors are rare and independent (old serial lines, some memory). It's poor where errors arrive in bursts, which is how they usually arrive on real links.
Two-Dimensional Parity
Arrange data in a grid. Add a parity bit for every row and every column, plus one corner bit.
Worked example — four data bytes, even parity:
data bits row parity
row 1: 1 0 1 1 0 0 1 0
row 2: 0 1 1 1 0 1 0 0
row 3: 1 1 0 0 1 1 1 1
row 4: 0 0 1 0 1 0 1 1
col parity: 0 0 1 0 0 0 1 0 ← corner = parity of the parity row (and of the parity column)
Now flip one bit, say row 2, column 3 (1 → 0). Row 2's parity check fails and column 3's parity check fails. The intersection pinpoints the bit, so any single-bit error can be corrected. Two-dimensional parity detects all 1-, 2- and 3-bit errors. It misses some 4-bit errors: four flips at the corners of a rectangle cancel out in both directions.
Checksums (Internet Checksum)
IP, TCP and UDP use a 16-bit one's complement sum. Treat the data as 16-bit words, add them, fold any carry back into the low 16 bits, then invert.
Worked example — an IPv4 header with the checksum field set to zero:
| Word | Hex |
|---|---|
| Version/IHL/TOS | 4500 |
| Total length | 0073 |
| ID | 0000 |
| Flags/Fragment offset | 4000 |
| TTL/Protocol | 4011 |
| Checksum (zero) | 0000 |
| Src IP high/low | C0A8 0001 |
| Dst IP high/low | C0A8 00C7 |
- Sum:
4500 + 0073 + 0000 + 4000 + 4011 + 0000 + C0A8 + 0001 + C0A8 + 00C7=0x2479C - Fold the carry:
0x479C + 0x2=0x479E - One's complement:
~0x479E=0xB861
The receiver sums every word including the checksum. If nothing was corrupted, the result is 0xFFFF.
Checksums are cheap to compute in software and easy to update incrementally (a router decrementing TTL can patch the checksum instead of recomputing it). They're also weak. Swapping two 16-bit words gives the same sum, and so do many multi-bit errors. That's why links use CRC underneath them.
Cyclic Redundancy Check (CRC)
CRC treats the bit string as a polynomial with coefficients in GF(2), where addition and subtraction are both XOR and there are no carries. Sender and receiver agree on a generator polynomial G(x) of degree r.
Sender:
- Append r zeros to the message M (this is M(x)·xʳ).
- Divide by G using modulo-2 long division.
- The r-bit remainder R is the CRC. Send M followed by R.
Receiver: divide the whole received frame by G. A remainder of 0 means no error was detected.
Worked Example: CRC with G(x) = x⁴ + x + 1
- Message M =
1101011011 - G = x⁴ + x + 1 → bits
10011(degree r = 4) - Dividend = M followed by four zeros =
11010110110000
The long division. At each step, if the leading bit of the current window is 1, XOR in the generator. If it's 0, shift.
1100001010 ← quotient (not needed)
┌───────────────
10011 │ 11010110110000
10011
─────
10011
10011
─────
00001
00000
─────
00010
00000
─────
00101
00000
─────
01011
00000
─────
10110
10011
─────
01010
00000
─────
10100
10011
─────
01110
00000
─────
1110 ← remainder R
The same computation as register states. XOR 10011 wherever the leading bit is 1:
| Step | XOR at bit position | Register after XOR |
|---|---|---|
| 0 | — | 11010110110000 |
| 1 | 0 | 01001110110000 |
| 2 | 1 | 00000010110000 |
| 3 | 6 | 00000000101000 |
| 4 | 8 | 00000000001110 |
Remainder = last 4 bits = 1110.
Transmitted frame: 1101011011 + 1110 = 11010110111110.
Receiver check: dividing 11010110111110 by 10011 leaves remainder 0000, so the frame is accepted. Flip any bit and the remainder becomes non-zero.
What CRC Catches
With a well-chosen r-bit generator, CRC detects:
- all single-bit errors (if G has more than one term)
- all double-bit errors (if G has a factor with three or more terms and the frame is shorter than the polynomial's period)
- all odd numbers of errors (if x + 1 is a factor of G)
- all burst errors of length ≤ r
- bursts of length r + 1 with probability 1 − 2⁻⁽ʳ⁻¹⁾, and longer bursts with probability 1 − 2⁻ʳ
Ethernet's CRC-32 misses a random corruption about once in 4 billion. Hardware computes it with a shift register and a few XOR gates, at line rate, for free.
| Name | Width | Used in |
|---|---|---|
| CRC-8 | 8 | ATM header, I²C/SMBus PEC |
| CRC-16-CCITT | 16 | HDLC, Bluetooth, X.25 |
| CRC-32 (IEEE) | 32 | Ethernet, Wi-Fi, gzip, PNG, SATA |
| CRC-32C (Castagnoli) | 32 | iSCSI, SCTP, ext4/Btrfs metadata, Kafka records |
CRC is not a security feature
CRC is linear, so an attacker can modify a frame and fix up the CRC to match. It protects against noise, not against adversaries. Integrity against attackers needs a MAC (HMAC, AEAD tags), which is what TLS and IPsec add. See TLS Handshake.
Error Correction: Hamming Code
Detection plus retransmission works when you can retransmit cheaply. When you can't (deep-space links, a disk sector, RAM, a one-way broadcast), you want forward error correction: enough redundancy for the receiver to fix the error itself.
The Hamming code corrects any single-bit error. The key idea is to put parity bits at positions that are powers of two (1, 2, 4, 8, …). Each parity bit covers the positions whose binary index has that bit set. When a bit flips, the parity checks that fail spell out its position in binary.
How Many Parity Bits?
With m data bits and r parity bits, the r checks must be able to name each of the m + r positions plus "no error":
| Data bits m | Parity bits r | Code |
|---|---|---|
| 4 | 3 | Hamming(7,4) |
| 7 | 4 | (11,7) |
| 11 | 4 | Hamming(15,11) |
| 26 | 5 | Hamming(31,26) |
| 57 | 6 | Hamming(63,57) |
| 64 | 7 | (71,64), plus an overall parity bit → (72,64) ECC DIMMs |
Coverage
| Parity bit | Position | Covers positions (binary index has this bit set) |
|---|---|---|
| p1 | 1 | 1, 3, 5, 7, 9, 11, … |
| p2 | 2 | 2, 3, 6, 7, 10, 11, … |
| p4 | 4 | 4, 5, 6, 7, 12, 13, … |
| p8 | 8 | 8–15, 24–31, … |
Worked Example: Encoding 1011 with Hamming(7,4), Even Parity
Lay out positions 1 to 7. Data bits go into the non-power-of-two positions 3, 5, 6, 7.
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Role | p1 | p2 | d1 | p4 | d2 | d3 | d4 |
| Value | ? | ? | 1 | ? | 0 | 1 | 1 |
Compute each parity bit so its group has an even number of 1s:
- p1 covers 1, 3, 5, 7 → data bits 1, 0, 1 → two 1s → p1 = 0
- p2 covers 2, 3, 6, 7 → data bits 1, 1, 1 → three 1s → p2 = 1
- p4 covers 4, 5, 6, 7 → data bits 0, 1, 1 → two 1s → p4 = 0
Codeword (positions 1→7): 0 1 1 0 0 1 1 = 0110011.
Worked Example: Correcting a Single-Bit Error
Bit 6 flips in transit. Received: 0 1 1 0 0 0 1.
Recompute each check over the received bits:
| Check | Positions | Received bits | Count of 1s | Result |
|---|---|---|---|---|
| c1 | 1, 3, 5, 7 | 0, 1, 0, 1 | 2 (even) | 0 |
| c2 | 2, 3, 6, 7 | 1, 1, 0, 1 | 3 (odd) | 1 |
| c4 | 4, 5, 6, 7 | 0, 0, 0, 1 | 1 (odd) | 1 |
Syndrome = c4 c2 c1 = 110 = 6. Bit 6 is wrong. Flip it back to get 0110011, then extract data from positions 3, 5, 6, 7: 1011. ✔
A syndrome of 000 means no error. Hamming(7,4) has distance 3, so it corrects one error but miscorrects two. Adding one overall parity bit (SECDED) separates the cases:
| Syndrome | Overall parity | Meaning |
|---|---|---|
| 0 | OK | No error |
| ≠ 0 | Fails | Single error at the syndrome position, so correct it |
| ≠ 0 | OK | Double error, detected but not correctable |
| 0 | Fails | The overall parity bit itself flipped |
Why Links Detect but Transport Retransmits
Ethernet checks the CRC and silently drops bad frames. It doesn't send a NAK and doesn't retransmit. TCP notices the gap later and resends. Why not fix it at the link?
- The end-to-end argument. Even with perfectly reliable links, data can be corrupted inside a router's memory, lost when a queue overflows, or delivered by a router that crashes mid-path. The endpoints have to check and retransmit anyway, so link-level reliability is redundant for correctness.
- Wired links are very clean. Bit error rates on copper and fibre are around 10⁻¹² or better. Building ARQ into every switch port to fix one frame in a billion isn't worth the complexity and buffering.
- Retransmission logic needs state. Per-neighbour windows and timers on every port of a 64-port switch is a lot of silicon for little benefit.
The exception proves the rule. Wi-Fi does retransmit at layer 2, because radio frame loss can reach several percent. Left to TCP, that loss would be read as congestion and would collapse throughput. Local recovery in microseconds beats end-to-end recovery after a 100 ms RTT. Cellular (HARQ in LTE and 5G) and satellite links make the same choice.
The rule of thumb
Link-layer reliability is a performance optimisation for lossy links. End-to-end reliability (TCP, QUIC) is what guarantees correctness. See TCP/IP Deep Dive for how TCP's loss recovery works, and UDP for what happens when nobody retransmits.
Flow and Error Control: ARQ Protocols
ARQ (Automatic Repeat reQuest) protocols give you reliable delivery over a lossy channel with three tools: acknowledgements, timeouts, and sequence numbers. The three classic designs are also the conceptual basis for TCP.
Notation used below:
- Tₜ = transmission time = frame size L / bandwidth B
- Tₚ = one-way propagation delay = distance / signal speed (about 2 × 10⁸ m/s in copper and fibre)
- a = Tₚ / Tₜ (how many frames fit "in flight" one way)
- RTT ≈ 2Tₚ (ignoring processing and ACK transmission time)
Stop-and-Wait ARQ
Send one frame. Wait for its ACK. Send the next. If the timer expires first, resend. One-bit sequence numbers (0, 1, 0, 1…) let the receiver spot duplicates when an ACK was lost rather than the frame.
sequenceDiagram
participant S as Sender
participant R as Receiver
S->>R: Frame 0
R->>S: ACK 1
S-xR: Frame 1 lost
Note over S: timer expires
S->>R: Frame 1 retransmitted
R-xS: ACK 0 lost
Note over S: timer expires again
S->>R: Frame 1 again
Note over R: duplicate seq 1, discard data but re-ACK
R->>S: ACK 0
S->>R: Frame 0 next frame
Without the sequence bit, the receiver would deliver frame 1 twice after the lost ACK. That's why even stop-and-wait needs sequence numbers.
Efficiency. Per cycle, the sender is busy for Tₜ and idle while the frame propagates and the ACK comes back:
If each frame is lost with probability p, each frame takes 1/(1 − p) attempts on average:
Worked example 1: a LAN. 100 Mbit/s, 1500-byte frames, 200 m of cable.
| Quantity | Calculation | Value |
|---|---|---|
| Tₜ | 12,000 bits ÷ 10⁸ bit/s | 120 µs |
| Tₚ | 200 m ÷ 2×10⁸ m/s | 1 µs |
| a | 1 / 120 | 0.0083 |
| η | 1 / (1 + 0.0167) | 98.4% |
Stop-and-wait is fine on a short link.
Worked example 2: a WAN. 10 Mbit/s, 1000-byte frames, Tₚ = 20 ms (about 4,000 km).
| Quantity | Calculation | Value |
|---|---|---|
| Tₜ | 8,000 bits ÷ 10⁷ bit/s | 0.8 ms |
| a | 20 / 0.8 | 25 |
| 1 + 2a | 51 | |
| η | 1 / 51 | 1.96% |
| Throughput | 0.0196 × 10 Mbit/s | 196 kbit/s |
You paid for 10 Mbit/s and get 196 kbit/s. The link sits idle 98% of the time waiting for ACKs. The fix is to keep many frames in flight.
Sliding Windows
Let the sender have up to N unacknowledged frames outstanding. If N frames take longer to transmit than a full round trip, the pipe stays full:
The window that fills the pipe is N ≥ 1 + 2a, which is exactly the bandwidth-delay product expressed in frames. In the WAN example, N = 51 frames gives 100% utilisation.
The same equation governs TCP: throughput ≤ window / RTT. That's why long fat pipes need large receive buffers.
Go-Back-N ARQ
- The sender has a window of up to N outstanding frames.
- The receiver has a window of size 1. It accepts only the next in-order frame and discards anything out of order.
- ACKs are cumulative: "ACK n" means everything before n arrived.
- On timeout, the sender resends the oldest unACKed frame and everything after it.
sequenceDiagram
participant S as Sender N=4
participant R as Receiver
S->>R: F0
S->>R: F1
S-xR: F2 lost
S->>R: F3
R->>S: ACK 1
R->>S: ACK 2
Note over R: F3 out of order, discard, re-ACK 2
R->>S: ACK 2 duplicate
S->>R: F4
S->>R: F5
Note over R: F4 and F5 discarded too
Note over S: timer for F2 expires, go back to 2
S->>R: F2
S->>R: F3
S->>R: F4
S->>R: F5
R->>S: ACK 6
Sequence-number constraint. With k-bit sequence numbers (2ᵏ values), the sender window must be at most 2ᵏ − 1. With N = 2ᵏ, here's what goes wrong: the sender sends frames 0…7 with 3 bits, every ACK is lost, and it resends 0…7. The receiver now expects frame 0 of the next cycle and can't tell the old 0 from a new 0.
Efficiency with errors (Tanenbaum's formulas, frame error probability p):
Each loss costs up to N retransmissions, so Go-Back-N degrades badly on lossy links with large windows.
Selective Repeat ARQ
- Sender window N and receiver window N.
- The receiver buffers out-of-order frames and ACKs each frame individually (or NAKs a gap).
- The sender resends only the frames that timed out or were NAKed.
sequenceDiagram
participant S as Sender N=4
participant R as Receiver N=4
S->>R: F0
S->>R: F1
S-xR: F2 lost
S->>R: F3
R->>S: ACK 0
R->>S: ACK 1
Note over R: F3 buffered, waiting for F2
R->>S: ACK 3
S->>R: F4
R->>S: ACK 4
Note over S: only F2 timer expires
S->>R: F2 resent alone
Note over R: deliver F2 F3 F4 in order
R->>S: ACK 2
Sequence-number constraint. The window must be at most 2ᵏ⁻¹, half the sequence space.
Why: take 2-bit numbers (0–3) with a window of 3. The sender sends 0, 1, 2. All three arrive, so the receiver's window slides to {3, 0, 1}. Then all three ACKs are lost. The sender times out and resends the old frame 0. The receiver has 0 in its window, accepts it as a new frame, and corrupts the data. With a window of 2 (= 2²⁻¹), the sender's old frames {0, 1} and the receiver's new window {2, 3} can never overlap.
Efficiency with errors:
Comparison
| Stop-and-Wait | Go-Back-N | Selective Repeat | |
|---|---|---|---|
| Sender window | 1 | N ≤ 2ᵏ − 1 | N ≤ 2ᵏ⁻¹ |
| Receiver window | 1 | 1 | N |
| Receiver buffering | None | None | N frames |
| ACK type | Individual | Cumulative | Individual (plus optional NAK) |
| On loss, resend | 1 frame | Lost frame + all after it | Only the lost frame |
| Max efficiency (no loss) | 1/(1+2a) | min(1, N/(1+2a)) | min(1, N/(1+2a)) |
| Best for | Short links, simple devices | Low-loss links, cheap receivers | High-delay or lossy links |
| Real-world relatives | Bluetooth L2CAP basic mode, TFTP | HDLC, old TCP behaviour without SACK | Wi-Fi block ACK, TCP with SACK, QUIC |
Worked Example: Choosing Sequence-Number Bits
The WAN above needs N ≥ 51 for full utilisation.
| Protocol | Condition | Smallest k | Max window |
|---|---|---|---|
| Go-Back-N | 2ᵏ − 1 ≥ 51 | 6 | 63 |
| Selective Repeat | 2ᵏ⁻¹ ≥ 51 | 7 | 64 |
And if you're stuck with 3-bit sequence numbers:
- GBN, N = 7: η = 7/51 = 13.7% → 1.37 Mbit/s
- SR, N = 4: η = 4/51 = 7.8% → 0.78 Mbit/s
With a fixed sequence space, GBN gets a larger window. SR uses each window slot more efficiently when frames are lost.
Worked Example: Counting Transmissions
Send frames 0–6 (7 frames) with window 3. Frame 3 is lost on its first transmission only.
Go-Back-3: send 0, 1, 2. ACKs slide the window and allow 3 (lost), 4, 5. The receiver discards 4 and 5. Timeout on 3, so resend 3, 4, 5, then send 6. Transmissions: 0 1 2 3 4 5 | 3 4 5 6 = 10
Selective Repeat: 0 1 2 3 4 5 6, then resend 3 = 8
The MAC Sublayer: Sharing a Medium
When many stations share one channel (a coax bus, a radio frequency), they need rules for who transmits when. Channel allocation protocols fall into three families:
| Family | Idea | Examples |
|---|---|---|
| Channel partitioning | Divide the channel into fixed slices | TDMA, FDMA, CDMA |
| Random access | Transmit when you have data, recover from collisions | ALOHA, CSMA, CSMA/CD, CSMA/CA |
| Taking turns | Pass permission around | Token Ring, polling, Bluetooth master/slave |
Pure ALOHA
ALOHAnet (University of Hawaii, 1971): transmit whenever you have a frame. If no ACK comes back, wait a random time and retry.
Let T be the frame time and G the average number of transmission attempts per frame time, new frames plus retries, modelled as Poisson. A frame sent at time t collides with anything starting in (t − T, t + T). That vulnerable period is 2T.
Maximised at G = 0.5: Sₘₐₓ = 1/(2e) ≈ 18.4%.
Slotted ALOHA
Divide time into slots of length T and allow transmissions only at slot boundaries. Frames now collide only if they start in the same slot, so the vulnerable period is T.
Maximised at G = 1: Sₘₐₓ = 1/e ≈ 36.8%. Slotting doubles the peak throughput, at the cost of clock synchronisation.
Worked example. A 200 kbit/s channel shared by many stations, 200-bit frames, so T = 1 ms. How many frames per second get through?
| Offered load | G | Pure ALOHA S = Ge⁻²ᴳ | Frames/s | Slotted S = Ge⁻ᴳ | Frames/s |
|---|---|---|---|---|---|
| 1000 frames/s | 1.0 | 1 × e⁻² = 0.135 | 135 | 1 × e⁻¹ = 0.368 | 368 |
| 500 frames/s | 0.5 | 0.5 × e⁻¹ = 0.184 | 184 | 0.5 × e⁻⁰·⁵ = 0.303 | 303 |
| 250 frames/s | 0.25 | 0.25 × e⁻⁰·⁵ = 0.152 | 152 | 0.25 × e⁻⁰·²⁵ = 0.195 | 195 |
S is successful frames per frame time, so frames/s = S × 1000. Pure ALOHA peaks at G = 0.5 (184 frames/s), slotted at G = 1 (368 frames/s). Past the peak, offering more load reduces useful throughput, because collisions eat the channel. That's the signature of every uncontrolled random-access scheme.
With a finite number of stations. N stations each transmit in a slot with probability p. A slot succeeds when exactly one station transmits:
It's maximised at p = 1/N, and as N → ∞ it tends to 1/e.
CSMA: Listen Before Talking
Carrier Sense Multiple Access: check whether the channel is busy before transmitting.
| Variant | If the channel is busy… | If the channel is idle… | Trade-off |
|---|---|---|---|
| 1-persistent | keep sensing, transmit the instant it goes idle | transmit | Low delay, but everyone waiting pounces at once |
| Non-persistent | wait a random time, then sense again | transmit | Fewer collisions, more idle time |
| p-persistent (slotted) | wait for the next slot | transmit with probability p, else defer one slot | Tunable middle ground |
CSMA can't eliminate collisions, because of propagation delay. Station A starts sending, and station B at the far end hasn't heard A's signal yet, sees an idle channel, and also starts. The longer the cable relative to frame time (bigger a), the worse this gets.
CSMA/CD: Collision Detection (Classic Ethernet)
On a wire, a transmitter can listen while it talks. If what it hears differs from what it sends, there's a collision. It then:
- stops sending data and transmits a 48-bit jam signal so every station notices the collision
- runs binary exponential backoff: after the nth consecutive collision, picks K uniformly from {0, 1, …, 2^min(n,10) − 1} and waits K × 512 bit times
- gives up after 16 attempts
flowchart TD
A["Frame ready"] --> B{"Channel idle?"}
B -- No --> B
B -- Yes --> C["Transmit and monitor"]
C --> D{"Collision detected?"}
D -- No --> E["Success"]
D -- Yes --> F["Send jam signal, n = n + 1"]
F --> G{"n greater than 16?"}
G -- Yes --> H["Abort, report error"]
G -- No --> I["Pick K from 0 to 2^min(n,10) - 1, wait K x 512 bit times"]
I --> B
Minimum Frame Size
For a collision to be detected, the sender must still be transmitting when the collision signal gets back to it. The worst case: A transmits, the signal reaches the far end B just before B starts sending, and B's signal then takes another Tₚ to travel back. So:
Worked example: classic 10 Mbit/s Ethernet. The standard allows 2500 m with up to four repeaters. Including repeater and transceiver delays, the worst-case round trip is budgeted at 51.2 µs, the slot time.
- Lₘᵢₙ = 51.2 µs × 10 Mbit/s = 512 bits = 64 bytes. That's where Ethernet's minimum frame comes from, and why short payloads are padded to 46 bytes.
Worked example: a hypothetical 1 Gbit/s bus. 2 km of cable at 2 × 10⁸ m/s:
- Tₚ = 2000 / 2×10⁸ = 10 µs
- Lₘᵢₙ = 2 × 10 µs × 10⁹ bit/s = 20,000 bits = 2,500 bytes
The faster the link, the shorter the frames are in time, so either frames get longer or the network gets smaller. Fast Ethernet kept 64-byte frames and shrank the collision domain to about 200 m. Gigabit Ethernet in half-duplex used carrier extension to pad the slot to 512 bytes. In practice everyone ran full-duplex switched links, where collisions can't happen, and 10 Gbit/s Ethernet dropped CSMA/CD and half-duplex entirely.
CSMA/CD efficiency (Kurose's approximation):
As a → 0 (short cable or long frames), efficiency approaches 1.
CSMA/CA: Collision Avoidance (Wi-Fi)
Wireless can't use collision detection:
- A radio's own transmission is millions of times stronger than a distant signal at its antenna. It can't hear a collision while it transmits. (Most Wi-Fi radios are half-duplex anyway.)
- The hidden terminal problem. A and C both reach the access point B but can't hear each other. Carrier sense at A says the channel is idle while C is transmitting.
A )))) B (((( C
└── range ──┘
└── range ──┘
A cannot hear C. Both collide at B.
So 802.11 avoids collisions instead and confirms delivery with link-layer ACKs:
- Sense the channel. If it's idle for DIFS, start a random backoff counter (slots from the contention window, initially 0 to CWmin).
- Count the backoff down only while the channel is idle. Freeze it while busy.
- Transmit when the counter reaches 0.
- The receiver waits SIFS (shorter than DIFS, so ACKs get priority) and sends an ACK.
- No ACK means a collision or loss is assumed. Double the contention window (up to CWmax) and retry, up to a retry limit (often 7).
Typical 802.11 OFDM timings (2.4/5 GHz): slot 9 µs, SIFS 16 µs at 5 GHz (10 µs at 2.4 GHz), DIFS = SIFS + 2 × slot = 34 µs, CWmin 15, CWmax 1023.
RTS/CTS and the NAV
For large frames, or when hidden terminals are a problem, the sender first reserves the channel:
sequenceDiagram
participant A as Station A
participant B as Access Point
participant C as Station C hidden from A
A->>B: RTS duration=D
B->>A: CTS duration=D minus RTS time
B-->>C: C also hears the CTS
Note over C: sets NAV, stays silent for the duration
A->>B: DATA frame
B->>A: ACK
Note over A,C: NAV expires, contention resumes after DIFS
Every station that hears the RTS or the CTS sets its Network Allocation Vector, a "virtual carrier sense" timer, to the advertised duration. C can't hear A, but it can hear B's CTS, so the hidden terminal stays silent. Collisions can now only hit the short RTS frames.
RTS/CTS adds overhead, so it's normally used only above an RTS threshold (frame size). The exposed terminal problem is the reverse: a station needlessly defers because it hears a transmission that wouldn't actually interfere with its own receiver. RTS/CTS helps there only partly.
| CSMA/CD (classic Ethernet) | CSMA/CA (802.11) | |
|---|---|---|
| Medium | Shared wire | Shared radio |
| Collision handling | Detect during transmission, abort, back off | Avoid with random backoff before sending |
| Delivery confirmation | None at layer 2 (CRC failures are dropped) | Every unicast frame ACKed |
| Hidden terminals | Not an issue on a bus | Mitigated with RTS/CTS + NAV |
| Status today | Obsolete (full-duplex switching) | Every Wi-Fi network (plus OFDMA scheduling in Wi-Fi 6/7) |
Ethernet Evolution
| Standard | Year | Speed | Medium | Topology / access |
|---|---|---|---|---|
| 10BASE5 "thicknet" | 1983 | 10 Mbit/s | Thick coax, 500 m | Bus, CSMA/CD |
| 10BASE2 "thinnet" | 1985 | 10 Mbit/s | Thin coax, 185 m | Bus, CSMA/CD |
| 10BASE-T | 1990 | 10 Mbit/s | Cat3 twisted pair, 100 m | Star via hub, CSMA/CD |
| 100BASE-TX | 1995 | 100 Mbit/s | Cat5, 100 m | Hub or switch, half/full duplex |
| 1000BASE-T | 1999 | 1 Gbit/s | Cat5e, 4 pairs, 100 m | Switched, full duplex in practice |
| 10GBASE-T / -SR | 2006/2002 | 10 Gbit/s | Cat6a / multimode fibre | Full duplex only, no CSMA/CD |
| 25/40/100GBASE | 2010–2016 | 25–100 Gbit/s | Fibre, DAC | Data centre server and spine links |
| 400/800GBASE | 2017–2024 | 400–800 Gbit/s | Fibre (PAM4) | Hyperscale spines, AI clusters |
Two things stayed constant through 40 years and a 80,000× speed increase: the frame format and the 48-bit MAC address. That backward compatibility is why Ethernet won.
MAC Addresses
A MAC address is 48 bits, written as six hex octets: 3c:22:fb:7a:10:0e.
3c : 22 : fb : 7a : 10 : 0e
└──────── OUI ──────┘ └─── device-specific ───┘
first octet 0x3c = 0011 11 0 0
│ └─ bit 0: I/G 0 = unicast, 1 = multicast/group
└─── bit 1: U/L 0 = globally unique (vendor), 1 = locally administered
| Address | Meaning |
|---|---|
ff:ff:ff:ff:ff:ff | Broadcast: every station on the segment |
01:00:5e:xx:xx:xx | IPv4 multicast (low 23 bits of the group IP) |
33:33:xx:xx:xx:xx | IPv6 multicast (low 32 bits of the group IP) |
01:80:c2:00:00:00 | STP BPDUs (never forwarded by bridges) |
x2, x6, xA, xE as the second hex digit | Locally administered: VMs, containers, randomised Wi-Fi MACs |
On Ethernet the bytes go out most significant byte first but least significant bit first within each byte, which is why the I/G bit is the first bit on the wire. A switch knows immediately whether a frame is unicast or group-addressed.
MAC randomisation
Modern phones and laptops use a random, locally administered MAC per Wi-Fi network (and sometimes rotate it daily) to stop tracking. Anything that keys on MACs — captive portals, DHCP reservations, "trusted device" lists — can break or misidentify devices because of it.
ARP: Mapping IP to MAC
IP decides the next hop's IP address (the destination itself if it's on-link, otherwise the gateway; see IP Addressing & Subnetting). To build the Ethernet frame, though, you need the next hop's MAC address. The Address Resolution Protocol (RFC 826) finds it.
sequenceDiagram
participant A as Host A 10.0.0.5
participant SW as Switch
participant B as Host B 10.0.0.9
participant C as Host C 10.0.0.7
Note over A: need MAC for 10.0.0.9, cache miss
A->>SW: ARP request to ff-ff-ff-ff-ff-ff, who has 10.0.0.9
SW->>B: flooded
SW->>C: flooded
Note over C: not my IP, ignore
Note over B: learns A's mapping from the request
B->>A: ARP reply unicast, 10.0.0.9 is at aa-bb-cc-00-00-09
Note over A: cache entry, then send the queued IP packet
ARP packet fields (28 bytes for IPv4 over Ethernet, EtherType 0x0806):
| Field | Value in a request |
|---|---|
| Hardware type | 1 (Ethernet) |
| Protocol type | 0x0800 (IPv4) |
| HLEN / PLEN | 6 / 4 |
| Operation | 1 = request, 2 = reply |
| Sender MAC / IP | A's MAC, 10.0.0.5 |
| Target MAC / IP | 00:00:00:00:00:00, 10.0.0.9 |
Key behaviours:
- Requests are broadcast, replies are unicast.
- The target learns the sender's mapping from the request, which saves a second exchange.
- Entries expire (on Linux, an entry goes from REACHABLE to STALE after roughly 15–45 s without confirmation, then is re-probed when used). That's how mappings recover after a NIC swap or IP move.
- ARP only resolves addresses on the local link. To reach 8.8.8.8 you ARP for your default gateway, never for 8.8.8.8.
Gratuitous ARP
A gratuitous ARP is an ARP request or reply announcing your own mapping, with sender IP = target IP. It's used for:
- Duplicate address detection. At boot, ARP for your own IP (with sender IP 0.0.0.0, an "ARP probe"). Any reply means someone else already has it.
- Cache refresh after failover. When a virtual IP moves to a standby node (keepalived/VRRP, Pacemaker), the new owner broadcasts gratuitous ARPs so every neighbour and switch updates its tables immediately instead of waiting for entries to expire.
- NIC or MAC change. Updating neighbours after a bond fails over.
ARP Spoofing (Defensive View)
ARP has no authentication, and most stacks accept unsolicited replies. Anyone on the same L2 segment can claim "the gateway's IP is at my MAC" and receive traffic meant for the gateway. That enables man-in-the-middle attacks or denial of service. It's the reason layer 2 is a trust boundary.
Defences:
| Defence | Where | How it works |
|---|---|---|
| Dynamic ARP Inspection (DAI) | Managed switches | Drops ARP packets whose IP-MAC pair doesn't match the DHCP snooping binding table |
| DHCP snooping | Managed switches | Builds the trusted IP-MAC-port table and blocks rogue DHCP servers |
| Port security | Switches | Limits MACs per port |
| Static ARP entries | Critical hosts | ip neigh replace 10.0.0.1 lladdr ... nud permanent (doesn't scale) |
| Segmentation | Network design | Small VLANs and client isolation on Wi-Fi limit who can attack whom |
| Encryption | End to end | TLS/SSH/IPsec make interception pointless even if ARP is poisoned |
| Detection | Monitoring | arpwatch and IDS alerts on MAC changes for the gateway IP |
Cloud VPCs mostly sidestep the problem. The hypervisor answers ARP itself from the provider's authoritative mapping, and spoofed source MACs or IPs are dropped (see Layer 2 in Cloud VPCs below).
Hubs, Bridges and Switches
| Device | Layer | What it does with a frame | Collision domains | Broadcast domains |
|---|---|---|---|---|
| Repeater / hub | 1 | Regenerates bits out of every port, no inspection | All ports share one | One |
| Bridge | 2 | Learns MACs, filters/forwards between a few segments (software, historically) | One per port | One |
| Switch | 2 | A multi-port bridge in hardware (ASIC), full duplex per port | One per port | One (per VLAN) |
| Router | 3 | Forwards by IP, rewrites L2 headers, does not forward broadcasts | One per port | One per port |
- A collision domain is the set of devices whose transmissions can collide. On a full-duplex switch port, there are no collisions at all.
- A broadcast domain is the set of devices that receive each other's broadcasts (ARP, DHCP discover). Only routers (or VLAN boundaries) split it.
MAC Learning
A switch keeps a MAC address table (also called the CAM table or forwarding database, FDB) mapping MAC → port. It is filled entirely by watching source addresses:
flowchart TD
A["Frame arrives on port P"] --> B["Learn: table src MAC = P, reset ageing timer"]
B --> C{"Dst is broadcast or multicast?"}
C -- Yes --> F["Flood to all ports except P (same VLAN)"]
C -- No --> D{"Dst MAC in table?"}
D -- No --> F
D -- Yes --> E{"Entry port equals P?"}
E -- Yes --> G["Filter: drop, dst is on the same segment"]
E -- No --> H["Forward out the entry port only"]
Entries age out, by default after 300 s on most switches. That way a host that moves ports gets relearned.
Worked example. A 4-port switch with an empty table. Hosts A (port 1), B (port 2), C (port 3), D (port 4).
| # | Frame | Learned | Table after | Action |
|---|---|---|---|---|
| 1 | A → B | A = 1 | {A:1} | B unknown → flood to 2, 3, 4 |
| 2 | B → A | B = 2 | {A:1, B:2} | A known → forward to port 1 only |
| 3 | C → A | C = 3 | {A:1, B:2, C:3} | Forward to port 1 |
| 4 | A → D | — | {A:1, B:2, C:3} | D unknown → flood to 2, 3, 4 |
| 5 | D → ff:ff… | D = 4 | {A:1, B:2, C:3, D:4} | Broadcast → flood to 1, 2, 3 |
| 6 | A → C | — | unchanged | Forward to port 3 only |
Unknown unicast flooding is why switches leak some traffic to everyone, and why an attacker who fills the table with fake MACs (MAC flooding) can turn a switch into a hub. Port security limits that.
Store-and-forward vs cut-through. Store-and-forward switches receive the whole frame and check the FCS before forwarding, so bad frames don't propagate. Cut-through switches start forwarding once the destination MAC has arrived, saving microseconds. That matters in low-latency trading and some HPC fabrics.
VLANs and 802.1Q Tagging
A VLAN splits one physical switch into several logical ones. Each VLAN is its own broadcast domain: an ARP broadcast in VLAN 10 never reaches VLAN 20. To get from one VLAN to another, traffic has to go through a router or an L3 switch.
Why VLANs exist:
- Smaller broadcast domains: less ARP/DHCP/mDNS noise and smaller failure blast radius
- Security segmentation: guests, IoT devices, servers and management on separate networks, with policy enforced at the router or firewall between them
- Flexibility: group by function rather than by which closet the cable runs to
The 802.1Q Tag
A 4-byte tag inserted between the source MAC and the EtherType:
┌─────────┬─────────┬───────────────────────────────┬───────────┬─────────
│ Dst MAC │ Src MAC │ TPID 0x8100 │ PCP │DEI│ VID │ EtherType │ Payload
│ 6 B │ 6 B │ 16 bits │ 3 b │1 b│ 12 bits│ 2 B │
└─────────┴─────────┴───────────────────────────────┴───────────┴─────────
| Field | Bits | Meaning |
|---|---|---|
| TPID | 16 | 0x8100 marks a tagged frame |
| PCP | 3 | Priority Code Point, 802.1p class of service 0–7 (voice traffic is usually 5) |
| DEI | 1 | Drop Eligible Indicator, droppable first under congestion |
| VID | 12 | VLAN ID: 4096 values, 0 and 4095 reserved → 4094 usable VLANs |
Port types:
- Access port: belongs to one VLAN. Frames go to and from the end host untagged. The switch adds or removes the tag internally.
- Trunk port: carries many VLANs between switches or to a hypervisor, tagged. One native VLAN may travel untagged.
QinQ (802.1ad) stacks two tags (outer TPID 0x88A8) so a provider can carry customers' VLANs inside its own. VXLAN replaces the 12-bit VID with a 24-bit VNI (16 million segments) and tunnels L2 frames over UDP/IP. That's how data centres and clouds build virtual L2 networks at scale (see Kubernetes CNI Networking).
VLAN hopping
Two classic attacks: switch spoofing (an attacker negotiates a trunk with DTP) and double tagging (a frame with two tags, where the outer one matches the native VLAN, gets stripped once and lands in the inner VLAN). Defences: disable auto-trunking on access ports, use an unused VLAN as the native VLAN, and tag the native VLAN explicitly on trunks.
Spanning Tree Protocol (STP)
Redundant links between switches are good for availability. They're catastrophic for Ethernet, which has no TTL. A single broadcast in a looped topology circulates forever and multiplies at every switch. That's a broadcast storm: links hit 100%, MAC tables thrash as the same source appears on different ports, and the network goes down in seconds.
STP (802.1D) solves this by logically blocking enough ports to turn the physical mesh into a loop-free tree. If an active link fails, it unblocks a backup.
The Algorithm
Switches exchange BPDUs (Bridge Protocol Data Units) to multicast 01:80:c2:00:00:00.
- Elect the root bridge: lowest Bridge ID = priority (default 32768) + MAC. Lower priority wins, then lower MAC.
- Each non-root switch picks one root port: its port with the lowest total path cost to the root. Ties go to the lowest sender bridge ID, then the lowest port ID.
- Each segment picks one designated port: the port on that segment with the lowest cost to the root. It forwards traffic for that segment. Ties go to the lowest bridge ID.
- Every other port blocks. It still listens to BPDUs but forwards no data.
Default port costs (802.1D-1998): 10 Mbit/s = 100, 100 Mbit/s = 19, 1 Gbit/s = 4, 10 Gbit/s = 2.
Worked Example
Three switches in a triangle, all 1 Gbit/s links (cost 4), all at default priority 32768:
- SW-A MAC
…:01, SW-B MAC…:02, SW-C MAC…:03
flowchart TB
A["SW-A (root) priority 32768, MAC ...01"]
B["SW-B MAC ...02"]
C["SW-C MAC ...03"]
A ---|"cost 4: A designated, B root port"| B
A ---|"cost 4: A designated, C root port"| C
B ---|"cost 4: B designated, C BLOCKED"| C
| Step | Decision | Reason |
|---|---|---|
| Root | SW-A | Equal priority, lowest MAC |
| SW-B root port | Port to A | Cost 4 direct, vs 8 via C |
| SW-C root port | Port to A | Cost 4 direct, vs 8 via B |
| A–B segment | A's port designated | The root's ports are always designated (cost 0) |
| A–C segment | A's port designated | Same |
| B–C segment | B's port designated | B and C both have root path cost 4, so it's a tie. B's bridge ID is lower |
| SW-C port to B | Blocked | Neither root nor designated |
If the A–C link fails, C stops receiving BPDUs from A on that port. It then starts using the B–C link: its port to B becomes the root port, with cost 8.
Timers and Faster Variants
Classic STP moves ports through blocking → listening (15 s) → learning (15 s) → forwarding, and waits a max age of 20 s to detect failures. That's 30–50 seconds of outage on a topology change.
| Variant | Standard | Notes |
|---|---|---|
| STP | 802.1D | 30–50 s convergence |
| RSTP | 802.1w | Proposal/agreement handshake, sub-second to a few seconds. The default today |
| MSTP | 802.1s | Maps groups of VLANs to separate spanning-tree instances, which balances load |
| PVST+ / Rapid PVST+ | Cisco | One tree per VLAN |
Edge ports that face hosts should be configured as PortFast / edge ports with BPDU Guard, so a host comes up instantly and any switch plugged in by mistake gets shut down. Modern data centres avoid STP entirely with L3 leaf-spine designs using ECMP routing, or with MLAG/EVPN, so every link carries traffic instead of half of them sitting blocked.
PPP: Point-to-Point Protocol
On a link with exactly two ends (serial lines, DSL, some WAN circuits), MAC addresses and channel access aren't needed. PPP (RFC 1661) provides:
- HDLC-like framing: flag
0x7E, byte stuffing with0x7D(worked example above), address0xFF, control0x03, a protocol field, payload, and a 16- or 32-bit FCS - LCP (Link Control Protocol): negotiates MTU, authentication method and compression, and detects looped links
- Authentication: PAP (cleartext password, avoid it) or CHAP (challenge-response, periodically repeated)
- NCPs (Network Control Protocols): one per network protocol. IPCP assigns the IPv4 address and DNS servers, IPv6CP sets up interface IDs
PPP lives on mostly as PPPoE on DSL and some fibre ISPs. The 8-byte PPPoE header cuts the MTU from 1500 to 1492. That's the most common cause of "some websites hang" problems when PMTUD is broken, and it's why routers apply TCP MSS clamping.
Layer 2 on a Linux Box
Links, Counters and Errors
# Interfaces, MACs, MTU, state
ip link show
# 2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP mode DEFAULT
# link/ether 3c:22:fb:7a:10:0e brd ff:ff:ff:ff:ff:ff
# Per-interface counters, including CRC/frame errors
ip -s -s link show eth0
# RX: bytes packets errors dropped missed mcast
# RX errors: length crc frame fifo overrun
# 0 412 0 0 0 <- non-zero crc = bad cable/optic/port
# Negotiated speed and duplex (a duplex mismatch causes late collisions and terrible throughput)
ethtool eth0 | grep -E 'Speed|Duplex|Link detected'
# Driver/NIC statistics: CRC errors, alignment errors, pause frames
ethtool -S eth0 | grep -iE 'crc|align|pause|drop'
# Ethernet flow control (802.3x PAUSE frames)
ethtool -a eth0
# Offloads: checksum, TSO/GSO, GRO, VLAN tag insertion/stripping
ethtool -k eth0 | grep -E 'checksum|segmentation|vlan'
Rising CRC errors
Rising rx_crc_errors almost always mean a physical problem: a damaged or overlong cable, a dirty fibre connector, a failing transceiver, or electrical interference. Software can't cause them. Swap the cable or optic before you debug anything else. CRC errors on one switch port but not others point at that link.
Seeing Frames
# -e prints the link-layer header (MACs, EtherType, VLAN tag)
sudo tcpdump -i eth0 -e -n -c 5
# 10:14:02.118 3c:22:fb:7a:10:0e > 00:1c:73:aa:01:02, ethertype IPv4 (0x0800), length 74: 10.0.0.5.51234 > 93.184.216.34.443: Flags [S] ...
# Only ARP
sudo tcpdump -i eth0 -e -n arp
# ... ff:ff:ff:ff:ff:ff, ethertype ARP (0x0806), length 42: Request who-has 10.0.0.1 tell 10.0.0.5, length 28
# ... 3c:22:fb:7a:10:0e, ethertype ARP (0x0806), length 60: Reply 10.0.0.1 is-at 00:1c:73:aa:01:02, length 46
# Only VLAN 10 frames on a trunk
sudo tcpdump -i eth0 -e -n vlan 10
# STP BPDUs (useful to see who thinks they're root)
sudo tcpdump -i eth0 -e -n 'ether dst 01:80:c2:00:00:00'
The Neighbour (ARP) Cache
ip neigh show
# 10.0.0.1 dev eth0 lladdr 00:1c:73:aa:01:02 REACHABLE
# 10.0.0.9 dev eth0 lladdr aa:bb:cc:00:00:09 STALE
# 10.0.0.42 dev eth0 FAILED <- nobody answered: host down or wrong subnet
arp -n # legacy net-tools equivalent
sudo ip neigh flush dev eth0 # clear (e.g., after an IP moved)
sudo ip neigh replace 10.0.0.1 lladdr 00:1c:73:aa:01:02 dev eth0 nud permanent # static entry
# Send ARP manually (iputils arping)
arping -I eth0 -c 3 10.0.0.1 # who is at 10.0.0.1, and does it answer?
arping -D -I eth0 -c 2 10.0.0.50 # duplicate address detection, exit status 1 if taken
sudo arping -U -I eth0 -c 3 10.0.0.50 # send gratuitous ARP announcing our own mapping
# ARP behaviour knobs (important for multi-homed hosts and load balancer DSR setups)
sysctl net.ipv4.conf.all.arp_ignore net.ipv4.conf.all.arp_announce
Neighbour states: INCOMPLETE (request sent) → REACHABLE (confirmed recently) → STALE (not confirmed lately, still usable) → DELAY/PROBE (re-verifying) → FAILED. A table full of FAILED entries points to a scanning process or a misconfigured route. A full table logs neighbour table overflow, which is fixed by raising net.ipv4.neigh.default.gc_thresh3 on large flat networks or Kubernetes nodes.
Bridges and VLANs in Software
Linux has a full learning switch built in. Docker's docker0, libvirt's virbr0 and many Kubernetes CNIs use it.
# Create a bridge and attach interfaces
sudo ip link add br0 type bridge
sudo ip link set eth1 master br0
sudo ip link set br0 up
# The MAC learning table (FDB)
bridge fdb show br br0
# 52:54:00:12:34:56 dev eth1 master br0
# 02:42:ac:11:00:02 dev veth3a1b master br0
bridge link show # port states (forwarding, blocking, ...)
sudo ip link set br0 type bridge stp_state 1 # enable kernel STP
# A tagged VLAN sub-interface on a trunk
sudo ip link add link eth0 name eth0.10 type vlan id 10
sudo ip addr add 10.10.0.5/24 dev eth0.10
sudo ip link set eth0.10 up
ip -d link show eth0.10 # shows "vlan protocol 802.1Q id 10"
Containers connect to bridges through veth pairs, a virtual cable with one end in the container's network namespace (see Namespaces & cgroups). From the bridge's point of view, each container is just another MAC on another port.
Layer 2 in Cloud VPCs
A cloud VPC looks like a LAN: you get a subnet, a gateway at .1, and ARP appears to work. Underneath it isn't a broadcast domain at all. It's an overlay (AWS's Nitro mapping service, Google's Andromeda, Azure's VFP) that encapsulates your frames and delivers them point to point.
| Classic LAN behaviour | In a typical cloud VPC (AWS/GCP/Azure) |
|---|---|
| ARP request broadcast to everyone | The hypervisor answers ARP itself from the control plane's mapping. Other VMs never see it |
| Broadcast and multicast work | No broadcast; multicast off by default (AWS Transit Gateway offers opt-in multicast) |
| Gratuitous ARP moves a VIP | Doesn't work. Move the IP through the API instead (reassign a secondary IP or ENI, update a route, or use a load balancer) |
| Any MAC/IP can be sent | Source/destination check drops spoofed traffic. You have to disable it explicitly for NAT instances or firewalls |
| VLANs for segmentation | Subnets, security groups and network ACLs. The provider uses VXLAN/Geneve-style encapsulation underneath |
| MTU 1500 | AWS supports 9001-byte jumbo frames inside a VPC. Traffic over the internet gateway or VPN is 1500 or less |
| STP and loops | Not your problem: the fabric is routed |
This explains a classic migration failure: an on-prem HA pair (keepalived with a floating VIP) moves to EC2 and failover "succeeds" but no traffic follows. The gratuitous ARP went nowhere. Use a route-table update, a secondary-IP move or an NLB instead. See AWS VPC Networking.
Practice Problems
1. CRC. Message 101110, generator G(x) = x³ + 1. Find the CRC and the transmitted frame. Then check whether a received frame 101010011 is accepted.
Solution
G = 1001, degree 3, so append three zeros: 101110000.
| Step | XOR at | Register |
|---|---|---|
| 0 | — | 101110000 |
| 1 | 0 | 001010000 |
| 2 | 2 | 000011000 |
| 3 | 4 | 000001010 |
| 4 | 5 | 000000011 |
Remainder = 011. Transmitted frame: 101110011.
Receiver check on 101010011: dividing by 1001 leaves remainder 100 ≠ 0, so an error is detected and the frame is dropped. (Dividing the correct frame 101110011 gives 000.)
2. Hamming code. (a) How many parity bits does Hamming need for 11 data bits? (b) Encode data 1001 with Hamming(7,4), even parity. (c) The receiver gets 0011101. Find and correct the error.
Solution
(a) Smallest r with 2ʳ ≥ 11 + r + 1: r = 4 gives 16 ≥ 16. 4 parity bits, so Hamming(15,11).
(b) Data in positions 3, 5, 6, 7 = 1, 0, 0, 1.
- p1 (1,3,5,7): 1, 0, 1 → two 1s → 0
- p2 (2,3,6,7): 1, 0, 1 → two 1s → 0
- p4 (4,5,6,7): 0, 0, 1 → one 1 → 1
Codeword = p1 p2 d1 p4 d2 d3 d4 = 0011001.
(c) Received 0 0 1 1 1 0 1:
- c1 (1,3,5,7): 0, 1, 1, 1 → odd → 1
- c2 (2,3,6,7): 0, 1, 0, 1 → even → 0
- c4 (4,5,6,7): 1, 1, 0, 1 → odd → 1
Syndrome c4c2c1 = 101 = 5. Flip bit 5: 0011001. Data = 1001. ✔
3. Stop-and-wait vs sliding window. A 1 Mbit/s link with 1000-bit frames and a one-way propagation delay of 10 ms. (a) Stop-and-wait efficiency? (b) Window size for 100% utilisation? (c) Minimum sequence-number bits for Go-Back-N and for Selective Repeat at that window?
Solution
Tₜ = 1000 / 10⁶ = 1 ms. a = 10 / 1 = 10. 1 + 2a = 21.
(a) η = 1/21 = 4.76% (47.6 kbit/s of useful throughput).
(b) N ≥ 21 frames.
(c) GBN: 2ᵏ − 1 ≥ 21 → k = 5 (window up to 31). SR: 2ᵏ⁻¹ ≥ 21 → k = 6 (window up to 32).
4. Satellite link. 50 Mbit/s geostationary link, RTT 540 ms, 1000-byte frames. (a) How many frames are needed in flight? (b) Throughput with 7-bit Go-Back-N sequence numbers?
Solution
Tₜ = 8000 / 5×10⁷ = 0.16 ms. 2Tₚ = 540 ms, so 2a = 540 / 0.16 = 3375.
(a) 1 + 2a = 3376 frames (about 3.4 MB in flight, the bandwidth-delay product).
(b) 7-bit GBN gives N = 127. η = 127 / 3376 = 3.76% → 1.88 Mbit/s. You'd need 12-bit sequence numbers (window 4095) to fill the pipe, which is why TCP added window scaling.
5. Go-Back-N vs Selective Repeat transmissions. Send frames 0–7 with window 4. Frame 2 is lost on its first transmission only. Count the total transmissions for each protocol.
Solution
GBN: send 0, 1, 2 (lost), 3. ACK 0 and ACK 1 slide the window to [2–5], so send 4, 5. The receiver discards 3, 4, 5. The timeout for 2 triggers resending 2, 3, 4, 5. Then 6, 7. Sequence: 0 1 2 3 4 5 | 2 3 4 5 | 6 7 = 12 transmissions.
SR: 8 originals + 1 retransmission of frame 2 = 9 transmissions.
6. Slotted ALOHA with finite stations. Ten stations each transmit in a slot with probability 0.1. What's the probability a given slot carries a successful frame? What p maximises it?
Solution
P(success) = N p (1 − p)ᴺ⁻¹ = 10 × 0.1 × 0.9⁹ = 1 × 0.387 = 0.387.
It's maximised at p = 1/N = 0.1, so this is already the optimum. As N → ∞ the maximum tends to 1/e ≈ 0.368.
7. CSMA/CD. (a) A 100 Mbit/s CSMA/CD network uses a 64-byte minimum frame. With signal speed 2 × 10⁸ m/s and no repeater delay, what is the maximum cable length? (b) For a 1 Gbit/s network 1 km long, what minimum frame size would be needed?
Solution
(a) Lₘᵢₙ = 2 Tₚ B → Tₚ = 512 / (2 × 10⁸) = 2.56 µs → distance = 2.56 µs × 2×10⁸ m/s = 512 m. The real standard limits a collision domain to about 205 m, leaving margin for hub and transceiver delays.
(b) Tₚ = 1000 / 2×10⁸ = 5 µs. Lₘᵢₙ = 2 × 5 µs × 10⁹ = 10,000 bits = 1,250 bytes.
8. Ethernet line rate. (a) What is the maximum number of 64-byte frames per second on 25 Gbit/s Ethernet? (b) What's the efficiency of carrying 1500-byte IP packets in 802.1Q-tagged frames?
Solution
(a) Each frame occupies 64 + 8 (preamble/SFD) + 12 (IFG) = 84 bytes = 672 bits. 25 × 10⁹ / 672 = 37.2 million frames/s.
(b) Wire bytes = 8 + 14 + 4 (tag) + 1500 + 4 (FCS) + 12 = 1542. Efficiency = 1500 / 1542 = 97.3%.
9. Bit and byte stuffing. (a) Bit-stuff 01111110 01111111 1. (b) PPP-stuff the payload 7D 7E 7E 01.
Solution
(a) Insert 0 after every run of five consecutive 1s, and restart the count after each insertion:
Input: 0 11111 1 0 0 11111 11 1
Output: 0 11111 0 1 0 0 11111 0 11 1
Stuffed result: 0111110100111110111 (17 bits in, 19 bits out).
(b) 7D → 7D 5D, 7E → 7D 5E, 7E → 7D 5E, 01 unchanged. With flags: 7E 7D 5D 7D 5E 7D 5E 01 7E.
10. Collision and broadcast domains. Router R has two interfaces. One goes to switch S1, the other to switch S2. S1 connects 3 hosts directly plus a hub; the hub connects 4 hosts. S2 connects 5 hosts. How many collision domains and broadcast domains are there? What changes if S2's hosts are split into VLANs 10 and 20, with R routing between them over a trunk?
Solution
Collision domains: R–S1 link (1) + R–S2 link (1) + S1's three host ports (3) + the hub segment including all 4 hub hosts (1) + S2's five host ports (5) = 11.
Broadcast domains: each router interface bounds one, so 2.
With VLANs on S2: collision domains are unchanged at 11 (the R–S2 trunk is still one link). Broadcast domains become 3: S1's side, VLAN 10 and VLAN 20.
11. STP. Four switches: SW1 (priority 32768, MAC …:0A), SW2 (priority 4096, MAC …:0F), SW3 (32768, …:01), SW4 (32768, …:02). Links: SW1–SW2, SW2–SW3, SW3–SW4, SW4–SW1, all 1 Gbit/s (cost 4). Which is root, which ports are root ports, and which port blocks?
Solution
Root: SW2. Priority 4096 beats 32768, whatever the MACs.
Root ports: SW1 → port to SW2 (cost 4). SW3 → port to SW2 (cost 4). SW4 has two paths, via SW1 or via SW3, both cost 8. Tie-break on lowest neighbour bridge ID: SW3 (32768:…01) < SW1 (32768:…0A), so SW4's root port faces SW3.
Segments: SW2's ports are designated on SW1–SW2 and SW2–SW3. On SW3–SW4, SW3 (cost 4) is designated. On SW1–SW4, SW1 has cost 4 and SW4 has cost 8, so SW1 is designated. SW4's port toward SW1 blocks.
Interview Questions
What happens at layer 2 when you ping a host on the same subnet for the first time?
The kernel sees the destination is on-link, finds no neighbour entry, and queues the ICMP packet. It broadcasts an ARP request to ff:ff:ff:ff:ff:ff, which the switch floods within the VLAN. The target learns the sender's mapping, replies unicast, and the switch learns both MACs along the way. The sender caches the reply and transmits the queued echo request in an Ethernet frame addressed to the target's MAC. If the host is on a different subnet, the ARP is for the default gateway instead.
Why does Ethernet have a minimum frame size? In CSMA/CD the sender must still be transmitting when a collision from the far end of the network reaches it, otherwise it believes the frame succeeded. The frame has to last at least one round-trip propagation time. With the 10 Mbit/s slot time of 51.2 µs, that's 512 bits = 64 bytes. Full-duplex switched Ethernet has no collisions, but kept the minimum for compatibility.
CRC vs checksum: why does Ethernet use CRC while TCP uses a checksum? CRC detects every burst up to its width and all odd error counts, and it's essentially free in hardware, which suits the link where noise causes burst errors. The Internet checksum is weaker (it misses reordered words and many multi-bit errors) but cheap in software and easy to update incrementally when routers change TTL. TCP's checksum is the end-to-end safety net for corruption that happens inside devices, where link CRCs don't apply.
Go-Back-N vs Selective Repeat: when would you choose each? GBN keeps the receiver trivial, with no buffering and cumulative ACKs, but each loss wastes up to a full window of retransmissions. It suits low-loss links. SR buffers out-of-order frames and resends only what was lost, which wins on high bandwidth-delay or lossy links, at the cost of receiver memory and halving the usable window relative to the sequence space (2ᵏ⁻¹ vs 2ᵏ − 1).
Why must the Selective Repeat window be at most half the sequence space? If all ACKs are lost, the sender retransmits its old window while the receiver has already advanced to the next one. If the two windows overlap, the receiver accepts an old frame as new. Keeping the window ≤ 2ᵏ⁻¹ guarantees the old and new windows are disjoint.
Why doesn't Wi-Fi use CSMA/CD? A radio can't hear a weak remote signal while its own strong transmission swamps the receiver. And hidden terminals mean the sender might not hear the colliding station at all, even though the receiver does. So 802.11 avoids collisions with random backoff, confirms each frame with a link-layer ACK, and can reserve the medium with RTS/CTS so hidden stations defer using the NAV.
What is the hidden terminal problem, and how does RTS/CTS solve it? A and C can both reach access point B but not each other, so carrier sense at A reports idle while C is transmitting to B, and the frames collide at B. With RTS/CTS, B's CTS is heard by everyone in B's range, including C, and they all set their NAV and stay quiet for the advertised duration.
Hub vs switch vs router? A hub repeats bits out of all ports: one collision domain, one broadcast domain. A switch learns MAC-to-port mappings and forwards each frame only where it needs to go: one collision domain per port, one broadcast domain per VLAN. A router forwards by IP between networks, rewrites the L2 header at every hop, and stops broadcasts, so each interface is its own broadcast domain.
How does a switch learn MAC addresses, and what is unknown-unicast flooding? On every frame, it records source MAC → ingress port with an ageing timer. For the destination, it forwards out the learned port if there is one, and if not it floods to every port in the VLAN except the ingress. That flooding is how the first frame to a silent host still gets there. It's also why a MAC-flooding attack that overflows the table turns the switch into a hub.
What is a broadcast storm, and how does STP prevent it? Ethernet frames have no TTL, so in a looped topology a broadcast is copied by every switch forever, saturating links and corrupting MAC tables within seconds. STP elects a root bridge by lowest bridge ID, picks each switch's lowest-cost root port and each segment's designated port, and blocks every other port, producing a loop-free tree. It unblocks backups when links fail. RSTP does this in about a second instead of 30–50 s.
What is gratuitous ARP used for, and why doesn't it work in AWS? A host announcing its own IP-to-MAC mapping is used for duplicate-address detection and, most importantly, to redirect neighbours instantly when a floating VIP fails over. In AWS the VPC fabric doesn't do broadcast ARP. The hypervisor answers ARP from the control plane's mapping, so the announcement goes nowhere. Failover has to go through the API instead (moving a secondary IP or ENI, changing a route, or using a load balancer).
How would you defend a network against ARP spoofing? On managed switches, enable DHCP snooping to build trusted IP-MAC-port bindings, then Dynamic ARP Inspection to drop ARP packets that contradict them. Use port security, small VLANs and client isolation to limit who shares a broadcast domain. Monitor for gateway MAC changes with tools like arpwatch. Most of all, encrypt end to end (TLS, SSH, IPsec) so a successful spoof yields nothing readable.
How many VLANs can 802.1Q support, and what do clouds use instead? The VLAN ID is 12 bits: 4096 values minus the reserved 0 and 4095 gives 4094. Multi-tenant clouds need millions of isolated segments, so they use overlays like VXLAN or Geneve with 24-bit identifiers (about 16 million), tunnelling L2 frames over routed L3 fabrics.
Your server's throughput is terrible and ip -s link shows rising CRC errors. What do you do?
CRC errors are physical: a bad cable, a dirty or failing optic, a damaged switch port, interference, or sometimes a speed/duplex negotiation problem. Check ethtool eth0 for speed and duplex, compare ethtool -S counters on both ends, and swap the cable or transceiver. Every frame that fails CRC is dropped silently, so TCP sees loss, backs off its congestion window, and throughput collapses.
Related
- OSI Model & TCP/IP Stack — where layer 2 sits among the others
- IP Addressing & Subnetting — deciding whether the next hop is on-link
- The Network Layer: Routing, ICMP, DHCP & IPv6 — the layer above: forwarding between links, and NDP replacing ARP in IPv6
- TCP/IP Deep Dive — sliding windows and retransmission end to end
- The Linux Networking Stack — what happens to a frame after the NIC accepts it
- Interrupts, DMA & Device Drivers — the NIC hardware path
- Namespaces & cgroups — veth pairs and bridges for containers
- Network Debugging — tcpdump and Wireshark in practice
- AWS VPC Networking — the cloud's virtual layer 2
- Kubernetes CNI Networking — bridges, VXLAN overlays and routed pod networks