Link-layer services and framing

The link layer carries one frame across one link: from a laptop to its Wi-Fi access point, from a switch to a router, from one end of a fibre to the other. It never sees the whole path. Every hop runs its own link layer, so a packet that crosses the Internet travels in a new frame on every link it uses. The first job of any link layer is framing: the physical layer delivers a stream of bits, and the receiver has to work out where each frame starts and where it ends. This lesson lists the services a link layer can offer, shows where they run inside a computer, and builds the three classic ways of marking frames in Python: a length field, byte stuffing as PPP does it and bit stuffing as HDLC does it, with what each one costs.

What a link layer does for one hop

The network layer hands the link layer a packet and the address of the next hop. What the link layer then does depends on the link, but the possible services are few:

• Framing. It wraps the packet in a frame, with a header in front and often a trailer behind, and marks where each frame begins and ends.
• Addressing. On a link that many stations share, the header says which station the frame is for and which one sent it: Ethernet and Wi-Fi use 48-bit MAC addresses. A point-to-point link has only one possible receiver, so the address field of PPP always holds 0xFF, “all stations”.
• Error detection. A check value computed over the frame, usually a CRC called the frame check sequence (FCS), lets the receiver recognise a damaged frame and drop it.
• Reliable delivery. The receiver acknowledges each frame and the sender resends frames that were lost.
• Flow control. A receiver that is falling behind can ask the sender to pause.
• Medium access. When several stations share one medium, a set of rules decides who may send and when.

Links pick from this list the services that pay off for the errors they suffer and the stations that share them. Three common links show the range:

• Ethernet (IEEE 802.3) marks each frame with a preamble on the wire, addresses it with 48-bit MAC addresses and checks it with a 32-bit CRC. It sends no acknowledgements: a damaged frame is dropped and TCP recovers. Flow control is optional, with PAUSE frames, and full-duplex switched links need no medium access.
• Wi-Fi (IEEE 802.11) sends each frame after a radio preamble and header, with 48-bit MAC addresses and a 32-bit CRC, and acknowledges every unicast frame: a frame whose acknowledgement does not come back is sent again. Stations share the radio with CSMA/CA.
• PPP on a serial line (RFC 1661, RFC 1662) marks frames with a flag byte and byte or bit stuffing. It needs no addresses (the address field is always 0xFF) and checks frames with a 16-bit CRC by default, or a 32-bit one by agreement. It sends no acknowledgements and, with only two ends, needs no medium access.

Wi-Fi acknowledges frames because radio loses frames far more often than a cable does, and resending across one hop takes far less time than waiting for TCP at the far end to notice the loss; a cable loses so few frames to noise that Ethernet leaves recovery to the transport layer. Medium access gets the next module of its own.

Every service ends at the far end of the link. When a router forwards a packet, it takes the packet out of the frame it arrived in and builds a new frame for the next link, with new link-layer addresses and a new CRC. An error that happens inside the router, after the old CRC was checked and before the new one was computed, is invisible to both links; catching that kind of damage is a job for the checksums of the layers above.

Where the link layer runs

In a computer, the link layer is split between the network card and the operating system:

• The network card (a NIC: network interface card or controller). Its physical-layer part (the PHY) turns bits into signals on copper, light in fibre or radio waves, and back. Its MAC part adds the preamble and the CRC to each frame it sends, and on the way in it finds where frames begin, checks every CRC and drops frames that fail. Cards today take on more of the work as well, such as computing IP and TCP checksums.
• The driver connects the card to the operating system. Frames wait in memory that both can reach: the card reads frames to send from it and writes received frames into it. It then signals the operating system with an interrupt, and the kernel collects the new frames in batches (Linux calls this machinery NAPI).
• The operating system builds the frame header: its own MAC address, the next hop’s MAC address (found with ARP on IPv4 or Neighbor Discovery on IPv6, in later lessons) and the type of packet inside. On the way in, it reads the type field and hands the packet to IPv4, IPv6 or ARP.

So the preamble and the CRC exist only between two network cards. Linux, for example, offers an rx-fcs setting that asks the card to keep the FCS at the end of each received frame so that capture tools can read it, and an rx-all setting that asks it to keep damaged frames too. Without such a request the card removes the CRC and drops damaged frames, which is why a capture on your own computer almost never shows a frame’s CRC, or a frame that failed it.

Why finding the boundaries is hard

The physical layer hands up nothing but bits. A receiver that starts listening in the middle of a transmission, or that has just lost a few bits to noise, has to find the start of the next frame from those bits alone. There are four ways to make that possible:

• A length field at the start of each frame says how many bytes follow.
• Byte stuffing: a flag byte marks each end of a frame, and an escape byte protects any flag byte inside the data.
• Bit stuffing: a flag pattern of bits marks each end, and the sender inserts a 0 bit into any run of 1s that could look like it.
• Markers in the line code: the physical layer has signal patterns that never stand for data, and uses them to mark the start and the end of a frame.

Length fields: simple until one byte is wrong

A length field costs only its own byte or two, and the receiver can cut frames apart without looking at the data. The trouble starts when the length itself is damaged:

"""Framing with a length byte in front of every message, and what one damaged length byte does."""


def frame(messages):
    """Put each message after one byte that holds its length."""
    out = bytearray()
    for m in messages:
        out.append(len(m))
        out += m
    return bytes(out)


def unframe(stream):
    """Cut a stream back into messages by trusting every length byte."""
    messages, i = [], 0
    while i < len(stream):
        n = stream[i]
        messages.append(stream[i + 1 : i + 1 + n])
        i += 1 + n
    return messages


sent = [b"GET", b"temp=31", b"ok", b"bye"]
stream = frame(sent)
print("on the link:", stream.hex(" "))
print("received:   ", unframe(stream))

damaged = bytearray(stream)
damaged[4] ^= 0b0000_0001  # noise flips the lowest bit of the second length byte: 7 becomes 6
print()
print("on the link:", bytes(damaged).hex(" "))
print("received:   ", unframe(bytes(damaged)))

on the link: 03 47 45 54 07 74 65 6d 70 3d 33 31 02 6f 6b 03 62 79 65
received:    [b'GET', b'temp=31', b'ok', b'bye']

on the link: 03 47 45 54 06 74 65 6d 70 3d 33 31 02 6f 6b 03 62 79 65
received:    [b'GET', b'temp=3', b'\x02ok\x03bye']

One flipped bit turned the second length from 7 into 6. The receiver took temp=3 as the second message, read the 1 that followed (byte 0x31, which is 49) as the next length, and swallowed the rest of the stream as one message. Four messages became three, and nothing in the stream lets the receiver find its place again: every boundary after a damaged length is lost.

Length fields work well where something else already marks the boundaries or keeps bytes from being damaged. TCP delivers a stream of bytes without loss, so a length prefix in front of each message is the usual way to frame messages on top of it (the socket programming module does exactly that). Inside an Ethernet frame, whose ends are marked by the physical layer, the two bytes after the addresses may also hold a length: values up to 1500 are a length, while values of 0x0600 (1,536) and more are an EtherType, which names the protocol inside, such as 0x0800 for IPv4 or 0x86DD for IPv6.

Byte stuffing: a flag and an escape

PPP, the Point-to-Point Protocol, carries IP packets over serial lines and modems, and its HDLC-like framing (RFC 1662) is byte stuffing in its classic form:

• The flag byte 0x7E (binary 01111110) marks the start and the end of every frame. One flag between two frames is enough, and the receiver checks every byte it gets for it.
• The escape byte 0x7D marks a changed byte. Before sending, every 0x7E and every 0x7D inside the frame is replaced by 0x7D followed by the original byte XOR 0x20: 0x7E goes out as 7D 5E, and 0x7D as 7D 5D.
• The receiver removes each 0x7D and XORs the byte after it with 0x20. A flag byte can now only ever be a frame boundary.

"""PPP-style byte stuffing (RFC 1662, section 4.2): a flag byte marks each end, an escape byte protects the data."""
import random

FLAG = 0x7E  # 0111 1110, sent before and after every frame
ESC = 0x7D  # 0111 1101, "the next byte was changed"


def byte_stuff(payload):
    """Frame a payload: flag, the data with FLAG and ESC escaped, flag."""
    out = bytearray([FLAG])
    for b in payload:
        if b in (FLAG, ESC):
            out += bytes([ESC, b ^ 0x20])  # 0x7E is sent as 7D 5E, 0x7D as 7D 5D
        else:
            out.append(b)
    out.append(FLAG)
    return bytes(out)


def byte_unstuff(frame):
    """Undo byte_stuff(): drop the flags, and restore each byte that follows an escape."""
    out, escaped = bytearray(), False
    for b in frame[1:-1]:
        if escaped:
            out.append(b ^ 0x20)
            escaped = False
        elif b == ESC:
            escaped = True
        else:
            out.append(b)
    return bytes(out)


payload = bytes([0x41, 0x7E, 0x42, 0x7D, 0x43])
framed = byte_stuff(payload)
print("payload:", payload.hex(" "))
print("framed: ", framed.hex(" "))
print("back:   ", byte_unstuff(framed).hex(" "))

rng = random.Random(1662)
cases = {
    "a line of text": b"meter 17 reads 231 V",
    "100,000 random bytes": rng.randbytes(100_000),
    "1,000 flag bytes": bytes([FLAG]) * 1000,
}
print()
for name, data in cases.items():
    f = byte_stuff(data)
    assert byte_unstuff(f) == data
    escapes = len(f) - 2 - len(data)
    print(f"{name}: {len(data):,} bytes in, {len(f):,} on the link, {escapes:,} escaped ({escapes / len(data):.2%})")

payload: 41 7e 42 7d 43
framed:  7e 41 7d 5e 42 7d 5d 43 7e
back:    41 7e 42 7d 43

a line of text: 20 bytes in, 22 on the link, 0 escaped (0.00%)
100,000 random bytes: 100,000 bytes in, 100,783 on the link, 781 escaped (0.78%)
1,000 flag bytes: 1,000 bytes in, 2,002 on the link, 1,000 escaped (100.00%)

The run shows both costs. Two of the 256 possible byte values need escaping, so random data should grow by about 2/256, or 0.78 %, and the 100,000 random bytes grew by 781 bytes, 0.78 %. A payload made of nothing but flag bytes doubles in size, plus the two flags. Any protocol that accepts data from outside, so that a sender can choose its bytes, has to size its buffers and time limits for that worst case, not for the average.

RFC 1662 also lets the two ends escape more than the minimum. On asynchronous links (modems and serial ports that send one byte at a time) the default is to escape every control byte below 0x20 too, because some equipment between the ends swallows or changes them. The ends can negotiate a smaller set once the link is up.

The big win over a length field is recovery. If noise damages a frame, the frame fails its CRC and is dropped, but the next flag byte still starts the next frame. One frame is lost, not the rest of the stream.

Bit stuffing: a flag pattern and inserted zeros

HDLC and PPP on bit-synchronous links, which send a continuous stream of bits rather than separate bytes, mark frames with the same pattern 01111110, but as bits that may start anywhere, not as a byte. To make sure the data can never contain six 1s in a row, the sender inserts a 0 after every run of five 1s, and the receiver removes every 0 that directly follows five 1s (RFC 1662, section 5.2):

"""HDLC bit stuffing (RFC 1662, section 5.2): a 0 goes in after every five 1s, so the flag 01111110 never appears in data."""
import random

FLAG = "01111110"


def bit_stuff(bits):
    """Insert a 0 after every run of five 1s; also return where the inserted bits are."""
    out, inserted, ones = [], [], 0
    for b in bits:
        out.append(b)
        ones = ones + 1 if b == "1" else 0
        if ones == 5:
            inserted.append(len(out))
            out.append("0")
            ones = 0
    return "".join(out), inserted


def bit_unstuff(bits):
    """Drop the 0 that follows every five 1s."""
    out, ones, skip = [], 0, False
    for b in bits:
        if skip:  # this is the inserted 0
            skip, ones = False, 0
            continue
        out.append(b)
        ones = ones + 1 if b == "1" else 0
        if ones == 5:
            skip = True
    return "".join(out)


data = "0111111011111111110"  # the flag pattern, then a run of ten 1s
stuffed, where = bit_stuff(data)
print("data:     ", data)
print("stuffed:  ", stuffed)
print("inserted: ", "".join("^" if i in where else " " for i in range(len(stuffed))).rstrip())
print("on the line:", FLAG + stuffed + FLAG)
print("unstuffed:", bit_unstuff(stuffed), bit_unstuff(stuffed) == data)
print("longest run of 1s after stuffing:", max(len(r) for r in stuffed.split("0")))

rng = random.Random(1662)
print()
for name, bits in {
    "8,000 random bits": "".join(rng.choice("01") for _ in range(8000)),
    "8,000 ones": "1" * 8000,
}.items():
    s, ins = bit_stuff(bits)
    assert bit_unstuff(s) == bits
    print(f"{name}: {len(ins):,} bits inserted ({len(ins) / len(bits):.2%})")

data:      0111111011111111110
stuffed:   0111110101111101111100
inserted:        ^       ^     ^
on the line: 01111110011111010111110111110001111110
unstuffed: 0111111011111111110 True
longest run of 1s after stuffing: 5

8,000 random bits: 111 bits inserted (1.39%)
8,000 ones: 1,600 bits inserted (20.00%)

The carets mark the three inserted bits. The data held the flag pattern itself and a run of ten 1s, and after stuffing no run of 1s is longer than five, so the only six 1s on the line are the flags at the two ends. A receiver that sees seven or more 1s in a row knows the frame was aborted or damaged and discards it.

Bit stuffing costs at most one bit for every five data bits, 20 %, which is the all-ones case in the run; the random bits needed 1.39 %. Its weakness is the reverse of a length field’s strength: the receiver has to examine every bit, which is why the work is done in hardware.

Here are the three methods side by side, with the numbers from the runs above:

• Length field. It costs only the length bytes, but one damaged length loses every boundary after it. It suits streams that something else protects from damage, such as messages on top of TCP.
• Byte stuffing (PPP). It cost 0.78 % on random data and doubles a frame in the worst case; after damage, the next flag starts the next frame. It suits byte-oriented links: serial lines and modems.
• Bit stuffing (HDLC). It cost 1.39 % on random bits and never more than 20 %, one bit per five; after damage, the next flag starts the next frame. It suits bit-synchronous links, where hardware examines every bit.

How Ethernet marks its frames

Ethernet needs no stuffing at all, because its physical layer marks the boundaries. Every frame goes on the wire after a preamble of seven bytes of alternating 1s and 0s, which lets the receiver lock on to the signal, and a start frame delimiter, 10101011, whose last two 1s say that the frame begins with the next bit. Faster versions of Ethernet also mark the start and the end of each frame with code groups of their line code that never carry data, and the standard keeps a gap of at least 96 bit times between frames. The receiving card removes all of this, so software only ever sees whole frames, starting with the destination address.

The same idea explains a number you may have met on broadband connections. PPPoE (RFC 2516) carries PPP inside Ethernet frames, and each PPP frame there starts directly with its protocol number, with no flags and no escaping, because Ethernet already marks and checks the frame. What remains are 6 bytes of PPPoE header and 2 bytes of PPP protocol number, taken from Ethernet’s 1,500-byte payload, which is why a PPPoE connection carries IP packets of at most 1,492 bytes.

Interview questions

The physical layer already delivers bits. Why does a link layer still need framing? Bits on their own carry no boundaries, and the layers above work with whole packets. Framing lets the receiver find where each frame starts and ends, so that it can check each frame’s CRC, read its addresses and hand exactly one packet up. Good framing also lets a receiver that joined mid-stream, or lost bits to noise, find the next frame by itself: with flags, the next flag is always a boundary, while a single damaged length field can lose every boundary after it.

Key takeaways

• The link layer moves one frame over one link; every router builds a new frame, with new addresses and a new CRC, for the next link.
• Its possible services are framing, addressing, error detection, reliable delivery, flow control and medium access, and each link picks the ones that suit its errors and its stations: Wi-Fi acknowledges frames, wired Ethernet does not.
• The network card adds and checks the preamble and the CRC, the driver moves frames between the card and memory, and the operating system builds headers and reads the type field.
• A length field is cheap, but one damaged length loses every later boundary; it suits protocols on top of TCP.
• PPP’s byte stuffing escapes 0x7E and 0x7D with 0x7D and an XOR with 0x20: about 0.78 % extra on random data, up to double in the worst case.
• HDLC’s bit stuffing inserts a 0 after five 1s, so the flag 01111110 never appears in data: at most 20 % extra.
• Ethernet marks frames in its physical layer, with a preamble, a start frame delimiter and special line-code groups, and needs no stuffing.