Data Link Layer: Framing, CRC, Sliding Window, ARP

The physical layer moves raw bits, and bits get corrupted, collide and arrive faster than a receiver can handle. The data link layer turns that unreliable bit pipe into a service the network layer can use: frames with clear boundaries, addressed to a neighbour, checked for errors and sent only when the medium is free. Its scope is a single link, from one node to the next; the network layer strings links together into paths. This note covers each of its jobs with worked examples.

What the data link layer does

• Framing: marking where each frame starts and ends.
• Physical addressing: source and destination MAC addresses in every frame.
• Error control: detecting damaged frames (CRC), and on some links retransmitting them.
• Flow control: not sending faster than the receiver can accept.
• Medium access control: deciding who transmits when many devices share a medium.

IEEE splits the layer into an upper LLC (logical link control) sublayer, which faces the network layer, and a lower MAC (media access control) sublayer, which handles addressing and medium access.

Framing

The receiver sees a stream of bits and must find frame boundaries. Four methods:

1. Byte stuffing: a FLAG byte marks each end of the frame, so a FLAG or ESC inside the data gets an ESC in front of it. A FLAG B ESC C goes out as A ESC FLAG B ESC ESC C, and the receiver drops each ESC and keeps the byte after it.
2. Bit stuffing: the flag is 01111110, six 1s in a row. After any five 1s the sender inserts a 0, so 011111110 goes out as 0111110110 with the stuffed bit at position 7. The receiver deletes the 0 after any five 1s.

PPP uses byte stuffing; HDLC uses bit stuffing. Either way the receiver undoes the rule, so the data can never be mistaken for a boundary.

Error detection

Parity

A parity bit makes the count of 1s even (even parity) or odd. The data 1011001 has four 1s, so its even parity bit is 0 and 10110010 is sent. Single parity detects any odd number of flipped bits but misses any even number. Two-dimensional parity arranges data in a grid with a parity bit per row and column; it can detect all 1-, 2- and 3-bit errors and can locate and correct a single-bit error.

Checksum

The sender adds the data words in one's complement arithmetic (a carry out of the top is wrapped round and added back) and sends the complement of the sum. Take 4-bit words 7, 11, 12, 0 and 6:

The Internet checksum used by IP, TCP and UDP is the same idea with 16-bit words. It is cheap but weak: swapping two words leaves the sum unchanged.

Cyclic redundancy check (CRC)

CRC treats bits as polynomial coefficients (1011 is x^3 + x + 1) and uses modulo-2 division, where subtraction is XOR and there are no carries. With a generator of degree r (r + 1 bits):

1. Append r zeros to the data.
2. Divide by the generator using XOR; the remainder has r bits.
3. Replace the appended zeros with the remainder and send this codeword.
4. The receiver divides the codeword by the same generator; a remainder of zero means no error was detected.

Worked example. Data 11010110, generator 1011 (degree 3), so three zeros are appended.

1. The generator 1011 has degree 3, so 3 zeros are appended to the data 11010110. The division runs on these 11 bits, and subtraction is XOR: no carries, no borrows.
2. Step 1: the leading bit is 1, so XOR the generator under it: 1101 ⊕ 1011 = 0110. The leading bit becomes 0 and the window moves one bit right.
3. Step 2: the leading bit is 1, so XOR the generator under it: 1100 ⊕ 1011 = 0111. The leading bit becomes 0 and the window moves one bit right.
4. Step 3: the leading bit is 1, so XOR the generator under it: 1111 ⊕ 1011 = 0100. The leading bit becomes 0 and the window moves one bit right.
5. Step 4: the leading bit is 1, so XOR the generator under it: 1001 ⊕ 1011 = 0010. The leading bit becomes 0 and the window moves one bit right.
6. Step 5: the leading bit is 0, so XOR 0000 — 0100 stays 0100. A zero leading bit means the generator does not go in here; the window just moves on.
7. Step 6: the leading bit is 1, so XOR the generator under it: 1000 ⊕ 1011 = 0011. The leading bit becomes 0 and the window moves one bit right.
8. Step 7: the leading bit is 0, so XOR 0000 — 0110 stays 0110. A zero leading bit means the generator does not go in here; the window just moves on.
9. Step 8: the leading bit is 1, so XOR the generator under it: 1100 ⊕ 1011 = 0111. The leading bit becomes 0 and the window moves one bit right.
10. After 8 steps only the last 3 bits can be non-zero: the remainder is 111. It replaces the appended zeros, and 11010110111 is the codeword that goes on the wire.
11. The receiver divides what arrives by 1011. The codeword leaves 000, so it is accepted; with the fourth bit flipped in transit it leaves 001, not zero, and the frame is discarded.

The remainder is 111, so the codeword is 11010110111. Dividing 11010110111 by 1011 leaves 000, so the receiver accepts it. If the fourth bit flips in transit (11000110111), the remainder is 001, not zero, and the error is detected. The program below runs the same division.

#include <iostream>
#include <string>
using namespace std;

string remainderOf(string work, const string& generator) {
    size_t n = generator.size() - 1;
    for (size_t i = 0; i + n < work.size(); i++) {
        if (work[i] == '1') {
            for (size_t j = 0; j < generator.size(); j++)
                work[i + j] = work[i + j] == generator[j] ? '0' : '1';
        }
    }
    return work.substr(work.size() - n);
}

int main() {
    string data = "11010110", generator = "1011";
    string remainder = remainderOf(data + string(generator.size() - 1, '0'), generator);
    string codeword = data + remainder;
    string corrupted = codeword;
    corrupted[3] = corrupted[3] == '0' ? '1' : '0';
    cout << "data       " << data << "\n";
    cout << "generator  " << generator << "\n";
    cout << "remainder  " << remainder << "\n";
    cout << "codeword   " << codeword << "\n";
    cout << "check      " << remainderOf(codeword, generator) << "\n";
    cout << "corrupted  " << corrupted << " -> " << remainderOf(corrupted, generator) << "\n";
    return 0;
}

public class Main {
    static String remainderOf(String dividend, String generator) {
        char[] work = dividend.toCharArray();
        int n = generator.length() - 1;
        for (int i = 0; i + n < work.length; i++) {
            if (work[i] == '1') {
                for (int j = 0; j < generator.length(); j++)
                    work[i + j] = work[i + j] == generator.charAt(j) ? '0' : '1';
            }
        }
        return new String(work, work.length - n, n);
    }

    public static void main(String[] args) {
        String data = "11010110", generator = "1011";
        String remainder = remainderOf(data + "0".repeat(generator.length() - 1), generator);
        String codeword = data + remainder;
        char[] bits = codeword.toCharArray();
        bits[3] = bits[3] == '0' ? '1' : '0';
        String corrupted = new String(bits);
        System.out.println("data       " + data);
        System.out.println("generator  " + generator);
        System.out.println("remainder  " + remainder);
        System.out.println("codeword   " + codeword);
        System.out.println("check      " + remainderOf(codeword, generator));
        System.out.println("corrupted  " + corrupted + " -> " + remainderOf(corrupted, generator));
    }
}

def remainder_of(dividend, generator):
    work = list(dividend)
    n = len(generator) - 1
    for i in range(len(work) - n):
        if work[i] == "1":
            for j, g in enumerate(generator):
                work[i + j] = "0" if work[i + j] == g else "1"
    return "".join(work[-n:])


data, generator = "11010110", "1011"
remainder = remainder_of(data + "0" * (len(generator) - 1), generator)
codeword = data + remainder
corrupted = codeword[:3] + ("1" if codeword[3] == "0" else "0") + codeword[4:]
print("data       " + data)
print("generator  " + generator)
print("remainder  " + remainder)
print("codeword   " + codeword)
print("check      " + remainder_of(codeword, generator))
print("corrupted  " + corrupted + " -> " + remainder_of(corrupted, generator))

function remainderOf(dividend, generator) {
  const work = dividend.split("");
  const n = generator.length - 1;
  for (let i = 0; i + n < work.length; i++) {
    if (work[i] === "1") {
      for (let j = 0; j < generator.length; j++) work[i + j] = work[i + j] === generator[j] ? "0" : "1";
    }
  }
  return work.slice(work.length - n).join("");
}

const data = "11010110";
const generator = "1011";
const remainder = remainderOf(data + "0".repeat(generator.length - 1), generator);
const codeword = data + remainder;
const corrupted = codeword.slice(0, 3) + (codeword[3] === "0" ? "1" : "0") + codeword.slice(4);
console.log("data       " + data);
console.log("generator  " + generator);
console.log("remainder  " + remainder);
console.log("codeword   " + codeword);
console.log("check      " + remainderOf(codeword, generator));
console.log("corrupted  " + corrupted + " -> " + remainderOf(corrupted, generator));

data       11010110
generator  1011
remainder  111
codeword   11010110111
check      000
corrupted  11000110111 -> 001

A generator of degree r with a non-zero constant term detects every burst error of length r or less, and one with x + 1 as a factor detects every odd number of bit errors. Longer bursts slip through only with probability about 2^−r, which is why Ethernet's 32-bit CRC is so strong.

Error correction: Hamming code

To correct one bit among m data bits, r check bits are needed with 2^r ≥ m + r + 1. For m = 4 that gives r = 3, the Hamming(7,4) code. Check bits sit at the positions that are powers of 2 (1, 2, 4); check bit p covers every position whose binary number has that bit set.

Encode 1011 with even parity, then correct an error.

1. The data bits 1011 go into positions 3, 5, 6, 7; positions 1, 2 and 4, the powers of 2, are check bits. Check bit c covers every position whose binary number has c's bit set, so the groups overlap.
2. Group 1 covers positions 1, 3, 5, 7. Positions 3, 5, 7 hold 1, 0, 1: 2 ones, so even parity makes p1 = 0.
3. Group 2 covers positions 2, 3, 6, 7. Positions 3, 6, 7 hold 1, 1, 1: 3 ones, so even parity makes p2 = 1.
4. Group 4 covers positions 4, 5, 6, 7. Positions 5, 6, 7 hold 0, 1, 1: 2 ones, so even parity makes p4 = 0.
5. 0110001 arrives instead of 0110011. The receiver rechecks every group: group 1 still has even parity, but groups 2 and 4 now have odd parity, so c1 = 0, c2 = 1 and c4 = 1.
6. Read the checks as a binary number, c4 c2 c1 = 110 = 6: position 6 is the only one inside both failing groups and outside the passing one. Flipping it back restores 0110011.

The codeword is 0110011. If 0110001 arrives instead, the rechecks give c1 = 0, c2 = 1 and c4 = 1, and c4 c2 c1 = 110 = 6 is the position to flip back. Hamming(7,4) has a minimum distance of 3, so it corrects one error or detects two (detecting d errors needs distance d + 1; correcting t needs 2t + 1).

Flow control: stop-and-wait and sliding windows

With stop-and-wait, the sender sends one frame and waits for its acknowledgement (ARQ, automatic repeat request, resends on timeout). With transmission time Tt and propagation delay Tp, its efficiency is Tt / (Tt + 2Tp) = 1 / (1 + 2a), where a = Tp / Tt.

Worked example. 1,000-bit frames on a 1 Mbps link give Tt = 1 ms; with Tp = 10 ms, a = 10 and efficiency = 1 / 21, about 4.8 per cent. A sliding window of N frames gives N / (1 + 2a), so 21 frames in flight keep the link fully busy. With m-bit sequence numbers, Go-Back-N allows a window of at most 2^m − 1, so it needs m = 5 (window up to 31); Selective Repeat allows at most 2^(m−1), so it needs m = 6 (window up to 32).

1. Go-Back-N: the receiver accepts only the frame it expects next, so it discards 3, 4, 5 and 6 even though they arrived intact. When frame 2's timer runs out the sender goes back and resends 2, 3, 4, 5, 6: 12 transmissions for 7 frames.
2. Selective Repeat: the receiver buffers 3 to 6 and acknowledges each one, so the sender resends only frame 2. When it arrives, frames 2 to 6 go up to the network layer in order: 8 transmissions in all.

Stop-and-wait needs just 1-bit sequence numbers (0 and 1), so it is also called the alternating bit protocol.

MAC addresses and ARP

A MAC address is 48 bits, written as six hexadecimal bytes such as 00:1A:2B:3C:4D:5E. The first three bytes are the manufacturer's OUI (organisationally unique identifier). FF:FF:FF:FF:FF:FF is the broadcast address. MAC addresses are flat and identify an interface on its local link; IP addresses are hierarchical and identify where it sits in the internet.

ARP maps an IPv4 address to a MAC address on the local network. When 192.168.1.10 wants to send to 192.168.1.20:

1. It checks its ARP cache; on a miss it broadcasts a request to FF:FF:FF:FF:FF:FF: "Who has 192.168.1.20? Tell 192.168.1.10", including its own MAC address.
2. Only 192.168.1.20 replies, with a unicast frame carrying its MAC address.
3. The sender caches the answer for a few minutes and sends its frame.

If the destination is on another network (say 8.8.8.8), the host never ARPs for it: it ARPs for its default gateway and sends the frame to the router's MAC address, with the IP packet still addressed to 8.8.8.8. A gratuitous ARP announces a host's own mapping, to detect duplicate addresses or update caches after a failover.

The Ethernet frame

The preamble and start frame delimiter (SFD) only synchronise the receiver. EtherType names the payload (0x0800 IPv4, 0x86DD IPv6, 0x0806 ARP), and a frame runs from 64 to 1,518 bytes; a payload shorter than 46 bytes is padded.

Medium access: CSMA/CD vs CSMA/CA

CSMA/CD (carrier sense multiple access with collision detection) was classic half-duplex Ethernet's method: listen until the cable is idle, transmit while listening, and on a collision stop, send a jam signal and back off. After the n-th collision, a station waits K slot times (512 bit times), with K picked at random from 0 to 2^min(n, 10) − 1, and it gives up after 16 attempts. A sender must still be transmitting when news of a collision returns, so Tt ≥ 2Tp and the minimum frame is L = 2 × Tp × R: with Tp = 25.6 µs at 10 Mbps, L = 512 bits = 64 bytes.

1. A senses an idle cable and starts sending at time 0. Its signal needs the propagation delay Tp = 25.6 µs to reach B at the far end of the longest cable allowed.
2. Just before A's signal arrives, B still hears silence and starts sending too. The two signals collide next to B at once, but A cannot know until the collision's signal travels all the way back.
3. The news reaches A at 2 × Tp = 51.2 µs. A detects the collision only if it is still transmitting then, so a frame must last at least 2 × Tp × R = 512 bit times: 64 bytes at 10 Mbps.

Full-duplex switched Ethernet has no collisions, so CSMA/CD is unused there.

CSMA/CA (collision avoidance) is Wi-Fi's method. A radio cannot hear others while transmitting, and two stations may each hear the access point but not each other (the hidden terminal problem), so collisions cannot be detected. A station waits for the medium to be idle for a gap called DIFS plus a random backoff, then sends; the receiver acknowledges after a shorter gap (SIFS). No acknowledgement means a collision, so the station doubles its backoff range and retries. An optional RTS/CTS exchange reserves the medium first.

Common mistakes

• In CRC, forgetting to append r zeros (r = generator bits − 1), or subtracting with borrows instead of XOR.
• Saying parity detects all errors: it misses every even number of flipped bits.
• Giving Go-Back-N and Selective Repeat the same window limit: 2^m − 1 versus 2^(m−1).
• ARPing for a remote host's IP address: the host resolves its gateway's MAC address.
• Counting the preamble in Ethernet's 64-byte minimum frame.
• Saying Wi-Fi uses CSMA/CD.

Interview questions

Why does the receiver get a zero remainder when it divides a CRC codeword? The sender appended the remainder of dividing the shifted data by the generator. In modulo-2 arithmetic adding and subtracting are both XOR, so the codeword equals the shifted data minus its remainder, an exact multiple of the generator. Any error that is not itself a multiple of the generator leaves a non-zero remainder.

How many check bits does a Hamming code need for 7 data bits? Four, because the smallest r with 2^r ≥ 7 + r + 1 is 4 (16 ≥ 12, while 8 is less than 11). The code is Hamming(11,7), with check bits at positions 1, 2, 4 and 8.

Why must Selective Repeat's window be at most half the sequence space? If the window were larger, after a batch of lost acknowledgements the receiver could not tell retransmitted old frames from new frames that reuse the same sequence numbers. Keeping the window at 2^(m−1) makes the old and new windows never overlap.

What is the minimum frame size in Ethernet, and why? 64 bytes, from destination address to FCS. With CSMA/CD a station must still be transmitting when a collision from the far end of the longest allowed cable comes back, so a frame must last at least one round-trip time: 512 bit times at 10 Mbps.

What does a switch do with a frame for an unknown MAC address? It floods the frame out of every port except the one it arrived on. It learns addresses by recording the source MAC address of every frame against its incoming port, so once the destination replies, later frames go only to the right port.

Why can't Wi-Fi use collision detection? A transmitting radio's own signal drowns out anything it might hear, and with hidden terminals the colliding station may be out of range entirely. So Wi-Fi avoids collisions with waiting gaps, random backoff and optional RTS/CTS, and uses acknowledgements to discover failures.

Next, read NAT, DHCP and ports, and test the arithmetic with the Computer Networks (Intermediate) skill test.