The Data Link Layer

The physical layer delivers a stream of bits that may be corrupted, and several machines may be shouting into the same wire.

The organising fact is that the data link layer has three jobs: mark where frames begin and end, detect or correct the errors the physical layer introduced, and arbitrate access when the medium is shared.

Everything in this chapter is one of those three, and the recurring theme is that each job is solved by adding redundancy of some kind, whether a delimiter, a checksum or a backoff interval.

The second organising fact is that the efficiency of any sliding window protocol is governed by a single ratio, the propagation delay divided by the transmission delay. Once that number is known, every utilisation formula follows.

The third is that a shared medium forces a minimum frame size. A sender must still be transmitting when the furthest collision could reach it, otherwise it will never learn that its frame was destroyed.

1. Framing

Framing marks where one frame ends and the next begins, and four methods exist.

A character count field states the frame length. It is simple and catastrophically fragile: one corrupted count desynchronises the receiver permanently.

Byte stuffing delimits frames with a flag byte and escapes any occurrence of that byte inside the payload with an escape byte, escaping the escape byte in turn. It assumes byte-oriented data.

Bit stuffing uses the flag pattern 01111110 and, whenever the sender emits five consecutive ones in the payload, inserts a zero. The receiver removes any zero following five ones, and the flag can therefore never appear in the data.

Physical layer coding violations use signal patterns that encode no data bit, which costs no bits at all but requires a coding scheme with spare patterns.

Bit stuffing is the method to know for the exam, because it is the one that produces computable answers.

2. Error Detection

A single parity bit detects any odd number of bit errors and misses every even number. Two-dimensional parity, adding a parity bit per row and per column, detects all one, two and three bit errors and corrects any single one.

A checksum sums the data as integers and transmits the complement, and is used by IP, TCP and UDP. It is cheap and weak, missing errors that cancel out.

A cyclic redundancy check treats the message as a polynomial over the field with two elements, divides by a generator polynomial, and appends the remainder.

With a generator of degree $r$, exactly $r$ check bits are appended, and the receiver divides the whole received frame by the same generator, expecting a zero remainder.

CRC properties are what make it standard. A generator with more than one term detects all single-bit errors. A generator with the factor $x+1$ detects all odd numbers of errors. A degree-$r$ generator detects all burst errors shorter than or equal to $r$.

Errors are detected, not corrected, and the frame is discarded and retransmitted.

3. Error Correction and Hamming Distance

The Hamming distance between two codewords is the number of positions in which they differ.

The minimum distance of a code determines its power.

To detect up to $d$ errors, the minimum distance must be at least $d+1$, since fewer errors then cannot reach another valid codeword.

To correct up to $d$ errors, the minimum distance must be at least $2d+1$, so that any corrupted word remains nearer its original than any other codeword.

Hamming codes place parity bits at power-of-two positions. Bit position $2^k$ checks every position whose binary representation has bit $k$ set.

With $r$ parity bits, $2^r$ must be at least $m+r+1$, where $m$ is the number of data bits, since the syndrome must name every position plus the no-error case.

The syndrome, read as a binary number, gives the position of the single error directly, which is the elegance of the construction.

4. Flow Control and Sliding Windows

Stop-and-wait sends one frame and waits for its acknowledgement.

Define $a$ as propagation delay divided by transmission delay. Then the sender is busy for one transmission time out of a cycle lasting $1+2a$ transmission times.

Utilisation is therefore $\frac{1}{1+2a}$, which collapses on long or fast links where $a$ is large.

Sliding window protocols keep several frames outstanding. With window size $N$, utilisation becomes $\frac{N}{1+2a}$, capped at 1.

The window size needed for full utilisation is therefore $N\ge 1+2a$.

Go-back-N discards every frame after a lost one and retransmits from the lost frame onward. The receiver needs no buffer beyond one frame, and the sender window is at most $2^m-1$ for an $m$-bit sequence number.

Selective repeat buffers out-of-order frames and retransmits only what was lost. It needs receiver buffering, and both windows are at most $2^{m-1}$.

The tighter bound for selective repeat is not arbitrary. If the windows could be larger, a retransmitted old frame could be mistaken for a new one, because the receiver cannot tell which lap of the sequence space it is on.

5. Medium Access

Pure ALOHA transmits whenever a frame is ready. A frame is destroyed if any other transmission begins within one frame time before or after it, giving a vulnerable period of two frame times.

Its throughput is $G{e}^{-2G}$, maximised at $G=0.5$ giving about 0.184.

Slotted ALOHA forces transmissions to start at slot boundaries, halving the vulnerable period to one frame time.

Its throughput is $G{e}^{-G}$, maximised at $G=1$ giving about 0.368, exactly double.

Carrier sense multiple access listens before transmitting.

One-persistent CSMA transmits as soon as the channel goes idle, which guarantees a collision if two stations were both waiting. Non-persistent CSMA waits a random time before sensing again, reducing collisions and adding delay. P-persistent CSMA transmits with probability $p$ in each idle slot.

CSMA with collision detection aborts as soon as a collision is sensed, which is what Ethernet does on shared media, and requires the minimum frame size derived below.

CSMA with collision avoidance is used in wireless, where a station cannot listen while transmitting, so collisions cannot be detected and must be avoided through backoff and optional request-to-send handshakes.

Binary exponential backoff picks a random wait from $0$ to $2^k-1$ slots after the $k$-th collision, capping $k$ at 10 and giving up after 16 attempts.

6. Ethernet and Bridging

The minimum frame size follows from collision detection. A sender must still be transmitting when the worst-case collision signal returns, so transmission time must be at least twice the propagation delay across the network.

For classic 10 Mbps Ethernet with a 2500 metre maximum span and repeaters, the round-trip worst case is about 51.2 microseconds, which at 10 Mbps is 512 bits, or 64 bytes.

Raising the rate to 100 Mbps while keeping 64 bytes forces the span down by a factor of ten, which is why fast Ethernet segments are shorter. Gigabit Ethernet instead added carrier extension to keep useful distances.

A hub is a physical layer repeater and joins everything into one collision domain. A bridge or switch operates at the data link layer and separates collision domains, forwarding only where necessary.

Switch learning is the mechanism worth understanding. A switch reads the source address of every arriving frame and records which port it came from. When forwarding, it looks up the destination: if known, it sends only to that port; if not, it floods to every port but the arrival port.

The spanning tree protocol prevents loops. A loop in a switched network causes broadcast frames to circulate forever, since there is no time-to-live field at the data link layer, so the protocol elects a root and disables redundant links.

A broadcast storm is what happens without it. One broadcast frame entering a loop is duplicated at every switch on every pass, and the traffic grows until the segment is unusable.

A switch is therefore not a transparent improvement on a hub in every respect. It divides collision domains but not the broadcast domain, which is why virtual LANs exist: they partition one physical switch into several broadcast domains that a router must join.

7. Worked Examples

Example 1. Apply bit stuffing to the payload 0111111011111011111110 and show what the receiver recovers.

The rule: after five consecutive ones, insert a zero.

Scan left to right. The bits are 0, then 111110, then 11111, then 011111, then 110.

Position by position. After the leading 0, five ones appear at positions 2 to 6, so a zero is stuffed after position 6. The next bit is the original 1, then 0.

Continuing, the next run of five ones triggers another stuffed zero, and so on.

The stuffed output is 0111110101111100111110110, where each inserted zero follows exactly five ones.

The receiver's rule is the mirror image: on seeing five ones followed by a zero, delete the zero.

On seeing five ones followed by a one, the receiver knows it is a flag or an error, since the sender could never have produced six consecutive ones in the payload.

That is the whole point of the scheme. The flag 01111110 contains six ones and is therefore unambiguous, and no payload can imitate it.

The overhead is bounded: in the worst case of all ones, one bit is added every five, giving 20 percent, and on typical data it is negligible.

Example 2. Compute the CRC for the message 1101011011 with generator 10011.

The generator has degree 4, so append 4 zeros to the message, giving 11010110110000.

Divide by the generator using modulo-2 arithmetic, which is exclusive-or with no carries.

The division proceeds by aligning the generator under the leftmost 1 and taking the exclusive-or, then shifting.

The remainder of this standard computation is 1110.

The transmitted frame is the original message with the remainder appended, that is 11010110111110.

The receiver divides the received frame by the same generator.

A zero remainder means no detected error; any non-zero remainder means the frame is discarded.

Why this works: appending the remainder makes the transmitted polynomial exactly divisible by the generator, because subtracting the remainder in modulo-2 arithmetic is the same as adding it.

The detection guarantee follows from the generator's degree. Any error burst shorter than or equal to 4 bits changes the polynomial by an amount that the degree-4 generator cannot divide, so the remainder becomes non-zero.

Example 3. How many parity bits are needed to correct a single error in 8 data bits, and where do they go?

The requirement is $2^r\ge m+r+1$, since the syndrome must identify any of the $m+r$ positions or report no error.

Try $r=3$: $2^3=8$, while $m+r+1=8+3+1=12$. Insufficient.

Try $r=4$: $2^4=16\ge 8+4+1=13$. Sufficient.

So 4 parity bits are needed, giving a 12-bit codeword.

They go at positions 1, 2, 4 and 8, the powers of two.

Each checks the positions whose index has the corresponding bit set. The parity bit at position 1 checks positions 1, 3, 5, 7, 9, 11. The bit at position 2 checks 2, 3, 6, 7, 10, 11. The bit at 4 checks 4, 5, 6, 7, 12. The bit at 8 checks 8, 9, 10, 11, 12.

On reception, recompute all four parities and read the results as a 4-bit binary number, least significant first.

That number is the position of the erroneous bit, and zero means no error, which is why the construction is so economical.

Example 4. A 1 Mbps link has a one-way propagation delay of 10 milliseconds and frames of 1000 bits. Compute the utilisation of stop-and-wait and the window size needed for full utilisation.

Transmission time is $1000/10^6=1$ millisecond.

Propagation delay is 10 milliseconds, so $a=10/1=10$.

Stop-and-wait utilisation is $\frac{1}{1+2a}=\frac{1}{21}\approx 4.76$ percent.

The sender transmits for 1 millisecond and then waits 20 milliseconds for the round trip, which is exactly what the formula says.

For full utilisation the window must satisfy $N\ge 1+2a=21$ frames.

With a 5-bit sequence number, go-back-N permits a window of $2^5-1=31$, which is sufficient.

Selective repeat permits only $2^{5-1}=16$, which is not, so a 6-bit sequence number would be needed there.

This asymmetry is worth carrying. For the same utilisation target, selective repeat needs one more sequence bit than go-back-N, and it buys that with far lower retransmission cost on a lossy link.

Example 5. A CSMA/CD network runs at 100 Mbps over 1 kilometre with a signal speed of $2\times 10^8$ metres per second. Compute the minimum frame size.

One-way propagation delay is $\frac{1000}{2\times 10^8}=5$ microseconds.

Round-trip is 10 microseconds.

The sender must still be transmitting when a collision signal from the far end could return, so transmission time must be at least 10 microseconds.

At 100 Mbps, 10 microseconds carries $100\times 10^6\times 10\times 10^{-6}=1000$ bits, which is 125 bytes.

So the minimum frame size is 1000 bits.

Consider what happens if a shorter frame is sent. A station transmits 500 bits, finishes after 5 microseconds, and considers the frame delivered.

A collision that began at the far end 4 microseconds in reaches the sender at 9 microseconds, by which time the sender has stopped listening.

The frame is destroyed and the sender never learns, so the loss is left for a higher layer to detect after a timeout, which defeats the purpose of collision detection entirely.

The general relation is $L\ge 2\times d\times R/v$, and it shows why raising the rate forces either shorter cables or larger minimum frames.

Example 6. Compare pure and slotted ALOHA at $G=0.5$ and at $G=1$, and explain the factor of two.

Pure ALOHA throughput is $S=G{e}^{-2G}$.

At $G=0.5$: $S=0.5\times e^{-1}=0.5\times 0.368=0.184$. This is its maximum.

At $G=1$: $S=1\times e^{-2}=0.135$, which is lower, since the channel is now overloaded.

Slotted ALOHA throughput is $S=G{e}^{-G}$.

At $G=0.5$: $S=0.5\times e^{-0.5}=0.5\times 0.607=0.303$.

At $G=1$: $S=1\times e^{-1}=0.368$. This is its maximum.

The factor of two in peak throughput comes entirely from the vulnerable period.

In pure ALOHA a frame is destroyed by any transmission starting within one frame time before or after it, a window of two frame times.

Slotting forces all transmissions to begin at slot boundaries, so a frame can only be destroyed by another frame in the same slot, halving the window to one frame time.

Halving the vulnerable period doubles the exponent's denominator, which is exactly the difference between $e^{-2G}$ and $e^{-G}$.

Note that even slotted ALOHA wastes 63 percent of the channel, which is why carrier sensing was invented, and why Ethernet reaches far higher utilisation despite using the same random access idea.

Summary

The data link layer frames, detects errors and arbitrates a shared medium, and every mechanism here adds redundancy of some kind.

Framing uses character counts, byte stuffing, bit stuffing or coding violations. Bit stuffing inserts a zero after five ones so the flag 01111110 can never appear in data, with a worst-case overhead of 20 percent.

A single parity bit catches odd error counts only. A CRC with a degree-$r$ generator appends $r$ bits and detects every burst up to length $r$, all single-bit errors, and all odd error counts if $x+1$ divides the generator.

Detecting $d$ errors needs minimum distance $d+1$; correcting $d$ needs $2d+1$. A Hamming code needs $r$ parity bits satisfying $2^r\ge m+r+1$, placed at powers of two, and the syndrome names the erroneous position directly.

With $a$ the ratio of propagation to transmission delay, stop-and-wait achieves $1/(1+2a)$ and a window of $N$ achieves $N/(1+2a)$, so full utilisation needs $N\ge 1+2a$. Go-back-N allows a window of $2^m-1$, selective repeat only $2^{m-1}$.

Pure ALOHA peaks at 0.184 and slotted ALOHA at 0.368, the factor of two coming from halving the vulnerable period. CSMA variants differ in what they do when the channel is busy, and collision detection needs the frame to last at least a round trip.

The minimum frame size is $2dR/v$, which is 64 bytes for classic Ethernet and is why faster Ethernet either shortened cables or extended carriers.

Switches learn source addresses, flood unknown destinations, and rely on the spanning tree protocol because data link frames carry no time-to-live. A switch divides collision domains but not the broadcast domain, which is what virtual LANs address.