EC-11.2 The Link: Encoding, Framing and Catching Errors

What this is and why it exists

This is the layer where the communication module and the networking module meet. It is also the one readers skip fastest on their way to addresses and routing.

It is worth the time for one reason. Everything above this layer is designed around a link that mostly works and occasionally does not. The occasionally is what gives the rest of the design its shape.

If you have ever wondered why a transport protocol is as complicated as it is, the answer starts here.

The vocabulary

• Line code — a rule for representing bits as voltage or light on a medium.
• Framing — deciding where one message begins and ends in a stream of bits.
• Bit stuffing — inserting an extra bit so that data cannot imitate a delimiter.
• Parity — one extra bit chosen so the total count of ones is even or odd.
• Checksum — a value computed from the data and sent along with it.
• Cyclic redundancy check — a remainder from a polynomial division, used as a strong check value.
• Forward error correction — extra bits allowing errors to be repaired without asking again.
• Sliding window — allowing several messages to be outstanding before an acknowledgement.

The mental model

Bits do not exist on a wire. Voltages do, and a line code is the rule connecting the two.

The naive rule, high for one and low for zero, has a specific failure. A long run of identical bits gives the receiver nothing to synchronise on. Its idea of where each bit boundary falls then drifts away from the sender's.

Line codes fix that by guaranteeing transitions. Some encode each bit as a transition rather than a level. Some map groups of bits to slightly longer groups chosen to contain transitions. Both cost something, in bandwidth or in extra bits, and that cost is why several codes exist rather than one.

Framing is the next problem and it is often underestimated. The receiver sees a stream and must decide where one frame starts.

Three approaches are in use. Send a length first, which fails badly if the length itself is corrupted. Use a special pattern as a delimiter, which requires escaping any occurrence of that pattern inside the data. Or use a code violation, a signal pattern the line code cannot otherwise produce, which is the cheapest when the physical layer allows it.

Now error checking, in increasing order of strength. A single parity bit catches any odd number of flipped bits and misses every even number, which is half of all possible errors. It is nearly free and nearly useless on a noisy link.

A checksum adds the data in fixed-size pieces and sends the total. Stronger, and it still misses errors that cancel each other, which is not a rare pattern in practice.

The cyclic redundancy check is what almost every real link actually uses. The frame is treated as one very large number and divided by a chosen constant, and the remainder is sent along. The receiver repeats the division including the remainder and expects zero.

Two properties make it standard. It catches every burst of errors shorter than the check value, and bursts are what real interference produces. And it is a shift register and a few gates in hardware, so it costs almost nothing at any speed.

The last decision is what to do about an error once found. Detecting it and asking again is cheap: a few bits per frame, and a retransmission only when something went wrong. It needs a return path and it costs a round trip.

Correcting it in place costs extra bits on every frame, whether or not anything went wrong. It is the only option when asking again is impossible or too slow. That is why it appears on deep space links, on stored media and on radio links.

Finally, keeping the link busy. Sending one frame and waiting for an answer leaves the link idle for a whole round trip. On a long fast path that is most of the time.

Allowing several frames to be outstanding fills that gap, and the number needed grows with the delay and the rate. That single idea reappears at the transport layer, where it decides the throughput of every connection you will ever use.

What you should now be able to explain or do

• Explain why a receiver needs transitions and what a line code does about it.
• Compare the three framing methods and name the failure mode of each.
• Say what parity and a checksum each miss, and why a cyclic check is used instead.
• Compute a cyclic check by polynomial division and verify one at the receiver.
• Choose between detecting and correcting, given a return path and a delay.
• Work out the window size needed to keep a link of a given rate and delay busy.

Check yourself