Layering, Switching and the Data Link Layer
Section 10 of the Computer Science paper, the last of its ten. Networking is taught as layering because layering is the actual design: each layer solves one problem, hands a unit down, and assumes the layer below it works. Getting the boundaries right answers a surprising number of questions on its own — routing is the network layer, medium access is the data link layer, reliability appears at both, and a bridge is not a router. Then switching, which is the one genuine three-way choice in the subject: circuit switching reserves capacity and wastes it when idle, packet switching shares capacity and cannot promise anything, and virtual circuits sit between by setting up a path once and then labelling. The data link layer is where the arithmetic starts. Framing has to make the frame boundary unambiguous even when the payload contains the delimiter, which is what bit stuffing is for. Error detection is three techniques with three different guarantees, and the examinable one is CRC, which is polynomial long division you can run in a minute. Medium access answers the question of what happens when two stations transmit at once, and its most examined consequence is a lower bound on frame size: a station must still be transmitting when a collision reaches it, so a frame cannot be shorter than the round-trip time allows. And the sliding-window efficiency formula W/(1 + 2a) appears here and again at the transport layer, which is worth noticing rather than learning twice.
Three Ways to Move a Message
| Aspect | Circuit | Packet (datagram) | Virtual circuit |
|---|---|---|---|
| Setup before data | Yes — a path is reserved | None | Yes — once, then labels |
| Do all units follow one path? | Yes | No — each is routed alone | Yes |
| Can they arrive out of order? | No | Yes | No |
| Address in each unit | None needed after setup | Full destination address | A short circuit id |
| Idle capacity | Wasted — reserved regardless | Shared with everyone | Shared (bandwidth is not reserved) |
🎯 The delay comparison, and when circuit switching wins
For a message of L bits over N hops at rate R, packet switching sends it as one unit and pays the store-and-forward cost at every hop: roughly N × L/R. Circuit switching pays a setup handshake once and then streams, so the transmission cost is L/R with no per-hop store-and-forward — but it must pay the setup first. So the honest rule is about message length against setup cost: circuit switching wins for long continuous transfers, packet switching wins for short bursty ones, and the crossover is where the setup time equals the store-and-forward penalty you avoided. The refinement that makes packet switching actually fast is pipelining: split the message into P packets and the hops overlap, so the total becomes roughly (L/R) + (N−1)(L/PR) rather than N × L/R — the first packet pays the full pipeline fill and the rest arrive behind it. That is why packet size appears in delay questions at all, and why very large packets and very small ones are both slow.Framing and Error Detection, Both Run
A receiver has to find where a frame begins and ends. The flag-byte approach delimits with a fixed pattern — HDLC uses 01111110 — and then has to guarantee that pattern never appears inside the payload. Bit stuffing does it: the sender inserts a 0 after every run of five 1s, so six consecutive 1s can only be the flag. Run it on 0111111111111110 and you get 011111011111011110, two bits longer, with no 01111110 anywhere inside. The receiver strips a 0 whenever it follows five 1s, recovering the original exactly. Note the cost is data-dependent — a payload of all 1s grows by one bit in six, which is why the worst-case frame expansion is a real quantity and not a rounding error.
🧠 CRC is long division you can finish in a minute
Given data 1101011011 and generator 10011 (degree 4), append 4 zeros, divide by the generator using XOR instead of subtraction, and the 4-bit remainder is the CRC. Running it gives remainder 1110, so the transmitted frame is 11010110111110. The receiver does not recompute and compare: it divides the whole received frame by the same generator and accepts if the remainder is 0000, which it is here. That asymmetry is the point — the sender appends a remainder chosen to make the total divisible, so the receiver only has to check divisibility. Three facts follow and all three get asked. A generator of degree r produces an r-bit CRC and needs r appended zeros. It detects all single-bit errors provided the generator has at least two terms, and all odd-numbered error bursts if (x + 1) divides the generator. And it detects every burst shorter than or equal to r bits. CRC is a detection code only — it cannot correct, and any option claiming otherwise is wrong.| Scheme | What it computes | Guarantee |
|---|---|---|
| Single parity bit | One bit making the count of 1s even (or odd) | Detects odd numbers of bit errors only; two errors are invisible |
| Internet checksum | 16-bit ones-complement sum with end-around carry | Cheap in software; misses some reordering and compensating errors |
| CRC | Remainder of polynomial division, r bits | Detects every burst of length ≤ r; still cannot correct |
| Hamming code | r parity bits with 2r ≥ m + r + 1 | Corrects one bit error — the only scheme here that corrects |
ℹ️ Hamming parity bits: solve the inequality, do not recall the table
To correct a single-bit error in an m-bit data word you need r parity bits satisfying 2r ≥ m + r + 1. The reasoning is a counting argument worth doing once: the r parity bits must encode which of the m + r codeword positions is wrong, plus the case nothing is wrong, so r bits must address m + r + 1 outcomes. Solve it rather than memorise: m = 4 needs r = 3 (2³ = 8 ≥ 8, exactly tight — the (7,4) code), m = 7 needs r = 4 (16 ≥ 12), m = 8 needs r = 4 (16 ≥ 13), and m = 32 needs r = 6 (64 ≥ 39). Note m = 4 and the (7,4) code make the inequality an equality, which is why that code is the standard example: it wastes nothing. And the general relation between distance and capability: a code with minimum Hamming distance d detects up to d − 1 errors and corrects up to ⌊(d − 1)/2⌋, so single-error correction needs d = 3, and d = 4 buys you correction of one plus detection of two.Medium Access, and the Frame That Must Not Be Short
CSMA/CD listens before transmitting and keeps listening while it transmits, so it can abort on a collision instead of wasting the whole frame. That only works if the station is still transmitting when the collision signal gets back to it — otherwise it finishes, believes it succeeded, and the collision is silently lost. So the transmission time must be at least the round-trip propagation time, which gives a lower bound on frame length: L ≥ 2 × Tp × B.
🎯 Ethernet’s 64 bytes is larger than the formula demands, deliberately
Run the bound at classic Ethernet parameters: 10 Mbps, a maximum span of 2500 m, signal speed 2 × 10⁸ m/s. One-way propagation is 2500 / (2 × 10⁸) = 12.5 µs, so the round trip is 25 µs, and L ≥ 25 µs × 10 Mbps = 250 bits, which is 32 bytes once you round up. But Ethernet mandates a 64-byte minimum frame — 512 bits — and 512 bits at 10 Mbps is exactly 51.2 µs, the standard’s slot time. The gap is not an error in either number: the 51.2 µs budget covers repeater latency and a safety margin, not bare propagation, so the formula gives a lower bound and the standard picks a larger round figure above it. Two things follow for exam use. When a question gives you distance and bandwidth, compute the bound — do not answer 64 bytes reflexively. And notice what the bound does as bandwidth rises: at 100 Mbps over the same 2500 m it becomes 2500 bits, ten times larger, which is precisely why fast Ethernet shrank the maximum span instead of growing the minimum frame.| Window W | Tt | Tp | a | Efficiency |
|---|---|---|---|---|
| 1 (stop-and-wait) | 1 ms | 20 ms | 20 | 2.44% |
| 1 | 100 µs | 200 µs | 2 | 20% |
| 5 | 100 µs | 200 µs | 2 | 100% |
| 7 | 100 µs | 200 µs | 2 | 100% (capped) |
⚠️ The window is capped twice — by 1 + 2a and by the sequence numbers
Efficiency is W/(1 + 2a) and it cannot exceed 1, so the useful window is W = 1 + 2a and anything larger buys nothing — with a = 2 that means W = 5 already saturates the link, and W = 7 is wasted capacity. The second cap is independent and is the one questions pair with it: with m-bit sequence numbers, Go-Back-N allows a window of at most 2m − 1 while Selective Repeat allows only 2m−1. So 3-bit sequence numbers give GBN 7 and SR 4; 4-bit give 15 and 8. The reason SR is half is worth knowing rather than accepting: the receiver accepts out-of-order frames into its own window, so if the send and receive windows together could exceed the sequence space, a retransmitted old frame is indistinguishable from a new one. Go-Back-N has a receive window of exactly 1, so it only needs to keep the send window one short of the space. The examinable consequence: given m and a, the achievable efficiency is min(1, min(2m−1 or 2m−1, 1+2a) / (1+2a)) — and when the sequence-number cap bites first, adding bandwidth does not help.ℹ️ A learning bridge floods once and then never again
Ethernet bridging is one algorithm with three rules, and it is examined as a trace. On receiving a frame on port p, the bridge (1) learns: records that the source MAC lives on port p; (2) forwards: if the destination MAC is in the table, sends only out that port; (3) floods: if the destination is unknown, sends out every port except p. So the first frame to a new host is flooded and every frame after it is forwarded — which is why a bridge table fills up from traffic rather than configuration, and why a question asking how many ports see frame k depends on what frames 1..k−1 taught the bridge. Two consequences: a bridge separates collision domains because each port is its own segment, but it does not separate broadcast domains, since a broadcast destination is flooded by rule 3. And loops between bridges are fatal — a flooded frame circulates forever — which is why the spanning tree protocol exists: it disables ports until the topology is a tree.Key takeaways
- Routing is the network layer, medium access the data link layer; a switch is not a router.
- OSI adds only session and presentation over TCP/IP; both fold into the application layer.
- A switch separates collision domains but not broadcast domains; a router separates both.
- Only datagram switching can deliver out of order; both circuit and virtual circuit cannot.
- Bit stuffing inserts a 0 after five 1s: 0111111111111110 becomes 011111011111011110.
- CRC: append r zeros, divide by the generator, and the receiver accepts on a zero remainder.
- CRC detects every burst of length ≤ r and corrects nothing; only Hamming corrects.
- Hamming parity bits solve 2r ≥ m + r + 1 — m = 8 needs r = 4.
- Minimum CSMA/CD frame is 2·Tp·B — 250 bits at 10 Mbps over 2500 m, below Ethernet’s 512.
- Efficiency is W/(1 + 2a), capped at 1; sequence numbers cap W at 2m−1 (GBN) or 2m−1 (SR).
Practice questions (8)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
A CSMA/CD network runs at 10 Mbps over a maximum span of 2500 m, with signals propagating at 2 × 10⁸ m/s. The minimum frame size in bits is ______
Numerical answer — type the value.
Show answer
Answer: 250
250 bits. A station must still be transmitting when a collision signal returns to it, so the transmission time has to be at least the round-trip propagation time. One-way propagation is 2500 / (2 × 10⁸) = 12.5 µs, so the round trip is 25 µs, and the frame must occupy the link that long: L = 25 × 10⁻⁶ × 10 × 10⁶ = 250 bits. Two errors are worth naming. Using one-way delay instead of the round trip halves it to 125 — but a collision has to travel to the far end and the jam signal back, which is why the 2 is there. And answering 512 applies Ethernet’s mandated 64-byte minimum instead of computing the bound: 512 bits is what the standard chose, and it is deliberately larger than 250 because the 51.2 µs slot time budgets repeater latency and a safety margin as well as propagation. When a question hands you distance and bandwidth, it wants the bound.A message of 10 data bits 1101011011 is protected by a CRC with generator 10011. The 4-bit CRC appended to the message is ______ (write the bits, e.g. 0101)
Numerical answer — type the value.
Show answer
Answer: 1110
1110. The generator 10011 has degree 4, so append four zeros to get 11010110110000 and divide by 10011 using XOR in place of subtraction. The 4-bit remainder is 1110, so the transmitted frame is 11010110111110. Check it the way the receiver does: divide the whole transmitted frame by 10011 and the remainder is 0000, which is the acceptance test — the sender picks a remainder that makes the total divisible, so the receiver never recomputes and compares, it just checks divisibility. Two habits prevent most errors here. Append exactly degree zeros, not one fewer, and keep the CRC width equal to the degree: a degree-4 generator always yields 4 bits, so an answer of a different length is wrong before it is checked. And use XOR throughout — there are no borrows in this arithmetic.A sliding-window protocol has a = Tp/Tt = 2. What is the smallest window size that achieves 100% link utilisation?
Show answer
Answer: B — 5
5. Efficiency is W/(1 + 2a), capped at 1, so utilisation reaches 100% exactly when W ≥ 1 + 2a = 1 + 4 = 5. The reading behind the formula: a station sends W frames back to back, then must wait for the first acknowledgement, which arrives one round trip (2a frame-times) after the first frame left plus the frame time itself — so 1 + 2a frame-times of work keeps the link busy continuously. Option A gives 3/5 = 60% and option C gives 4/5 = 80%, both short. Option D works but is not the smallest — W = 7 gives 7/5, capped to 100%, so the extra two frames of window buy nothing and the question asked for the minimum. Worth pairing with the second, independent cap: with 3-bit sequence numbers Go-Back-N could not exceed 7 anyway, and Selective Repeat could not exceed 4 — so on this link SR with 3-bit sequence numbers would be stuck at 80% no matter how it was tuned.Which of the following are true?
Show answer
Answer: A — A bridge separates collision domains; C — A hub forwards a collision along with the data; D — A router separates both collision and broadcast domains
A, C and D. A is true because each bridge port is its own segment with its own contention: a collision on one port never reaches another. C is true and is what a hub is — a physical-layer repeater copies bits with no notion of an address, so a collision is just more bits to copy, which is why a hub keeps one collision domain across all its ports. D is true because a router terminates both: it is a separate segment per interface, and it does not forward broadcasts. B is false, and it is the one worth remembering: a bridge floods a frame whose destination is unknown or is the broadcast address out of every other port, by the third rule of the learning algorithm — so a broadcast crosses a bridge unchanged and the broadcast domain is unchanged with it. Separating broadcast domains needs a router, or a VLAN configured on the switch, which is a way of making one switch behave as several.A Hamming code must correct any single-bit error in an 8-bit data word. The minimum number of parity bits required is ______
Numerical answer — type the value.
Show answer
Answer: 4
4. The r parity bits must identify which of the m + r codeword positions is corrupted, plus the case that nothing is corrupted — that is m + r + 1 outcomes, and r bits can name at most 2r of them, giving 2r ≥ m + r + 1. With m = 8: r = 3 gives 8 ≥ 12, false; r = 4 gives 16 ≥ 13, true. So 4 parity bits and a 12-bit codeword. Solve the inequality rather than recalling a table, because the same one answers every variant: m = 4 needs r = 3 (8 ≥ 8, exactly tight — the famous (7,4) code, which wastes nothing), m = 7 needs 4, and m = 32 needs 6. The commonest wrong answer is 3, from checking 2³ ≥ m + 1 and forgetting that the parity bits themselves occupy positions that can also be corrupted. And note what this code does not do: single-error correction needs minimum distance 3, which detects two errors but corrects only one — a double error is silently mis-corrected.With bit stuffing and the flag 01111110, the data 0111111111111110 is transmitted as:
Show answer
Answer: B — 011111011111011110
011111011111011110. Walk the data inserting a 0 after every fifth consecutive 1, counting from the start of each run. The input is a 0 then thirteen 1s then a 0. After the first five 1s insert a 0 (giving0111110), which resets the count; the next five 1s trigger another insertion (111110); the remaining three 1s and the trailing 0 pass through. That yields0 11111 0 11111 0 111 0= 011111011111011110, two bits longer than the 16-bit input. Option A misses the point of the rule: stuffing does not look for the whole flag in the data, it pre-empts it by making six consecutive 1s impossible in the payload, so the only place the flag can appear is as a real delimiter. Options C and D miscount the runs — the reliable method is to reset the counter to zero the moment a 0 is emitted, whether that 0 was original data or stuffed. The receiver reverses it mechanically: delete any 0 that directly follows five 1s.Which statement about circuit switching and datagram packet switching is correct?
Show answer
Answer: B — Circuit switching reserves capacity that is wasted when idle; datagram switching shares it but promises nothing
That is the trade in one sentence, and everything else follows from it. Reserving a path guarantees the rate and the ordering and cannot be shared while idle; sharing the links gives statistical multiplexing and therefore no guarantee about delay, jitter or ordering. Option A is half right at most: only datagram switching can reorder, because each packet is routed independently and may take a different path — a circuit is one fixed path, so units arrive in the order sent, and the same is true of a virtual circuit. Option C inverts the defining property: the absence of setup is what makes a datagram network a datagram network; it is the virtual circuit that sets up once and then labels. Option D describes datagram switching — after a circuit is established the units need no destination address at all, which is exactly the overhead the setup buys back, and a virtual circuit carries only a short circuit identifier.A protocol uses 4-bit sequence numbers. The maximum window sizes for Go-Back-N and Selective Repeat respectively are:
Show answer
Answer: B — 15 and 8
15 and 8. With m = 4 the sequence space holds 2⁴ = 16 numbers. Go-Back-N keeps a receive window of exactly one — it accepts only the next expected frame — so it needs the send window to be one short of the space to keep a retransmission distinguishable from a new frame: 2m − 1 = 15. Selective Repeat accepts out-of-order frames into a receive window of its own, so the send and receive windows together must not exceed the space, giving each at most 2m−1 = 8. Option C reverses them, which is the commonest error and is worth a check: SR is the more capable protocol but has the smaller maximum window, because capability at the receiver is what costs sequence space. Option A forgets that using the whole space makes an old retransmission indistinguishable from a fresh frame. Option D applies Go-Back-N’s rule to both. Worth pairing with the efficiency cap: a window is useless beyond 1 + 2a, so on a link with a = 2 both protocols saturate at W = 5 and neither limit bites.