The Link Layer: Role and Services

A node in link-layer terminology is any device that runs link-layer protocols: hosts, routers, switches, and wireless access points all qualify (plain physical-layer repeaters and hubs do not, since they have no notion of a frame). A link is the communication channel that connects adjacent nodes along a communication path — it may be a physical wire or fiber, a shared wireless channel, or even a switched LAN that logically behaves like a link connecting many nodes. Two nodes are adjacent if a link directly joins them, with no intervening router in between. The link layer's unit of data is the frame: a chunk of bits with a well-defined beginning and end, carrying an encapsulated network-layer datagram (typically an IP packet) inside a link-layer header and, often, a trailer. The crucial conceptual shift from the network layer is scope. The network layer's forwarding table and routing algorithms reason about the entire path from source to destination across many links and many different link-layer technologies (Ethernet on the first hop, a leased-line protocol in the core, Wi-Fi on the last hop). The link layer, by contrast, is deliberately myopic: a given link-layer protocol instance only knows about its own link and the node on the other end of it. This is why a single IP datagram, as it crosses the Internet, gets encapsulated and de-encapsulated by a different link-layer protocol at every hop — this is exactly the mechanism formalized in Encapsulation Across Layers, where each layer wraps the payload from the layer above with its own header before handing it down to the physical layer for transmission as raw bits. Because each link is different — different physical media, different numbers of nodes sharing the channel, different error characteristics — link-layer protocols vary enormously in what they offer. A protocol on a reliable point-to-point fiber optic link might do almost nothing beyond framing. A protocol on a lossy wireless channel shared by many stations might additionally implement retransmission, flow control, and heavy error correction. The link layer is best understood not as one fixed protocol but as a menu of services that a concrete protocol (Ethernet, Wi-Fi's 802.11, PPP, cable's DOCSIS) selects from, tailored to the medium and the traffic it must carry.

The link layer's mechanism decomposes cleanly into three stages that every implementation must address, in this order of dependency: first delimit frames (framing), then decide who may transmit and when (link access), then apply whatever additional services (error detection, flow control, reliability) the protocol promises on top.

1. Framing. The sender's link-layer adapter takes a network-layer datagram, wraps it with a header (containing at least source and destination link-layer — MAC — addresses) and often a trailer (containing an error-detection code), and transmits the resulting frame as a bit stream via the physical layer. The receiver's adapter must recover frame boundaries from an undifferentiated stream of bits. There are three classical framing strategies:

• Byte counting. The header carries an explicit length field stating how many bytes follow. The receiver reads the count, then reads exactly that many bytes as the frame body. This fails catastrophically if the length field itself is corrupted or misread — the receiver then loses synchronization with all subsequent frames until some external resynchronization occurs. (DDCMP, an old link protocol, used this scheme.)
• Byte/character stuffing with sentinel flags. A reserved flag byte (e.g., `0x7E`) marks both start and end of a frame. If the flag byte value happens to occur naturally inside the payload, the sender "stuffs" an escape byte before it, and the receiver undoes this on reception. This is what PPP (Point-to-Point Protocol) does.
• Bit stuffing. Instead of stuffing whole bytes, the sender treats the payload as a raw bit stream and inserts a single `0` bit after every run of five consecutive `1` bits, so the reserved flag pattern `01111110` can never appear accidentally inside the payload. The receiver removes these stuffed bits before interpreting the frame. HDLC and, historically, Ethernet's underlying physical encoding relatives use this idea.

2. Link access. If the link is a point-to-point link with exactly two nodes (e.g., a dial-up or leased line running PPP), there is no contention — either side may transmit whenever it has data, subject only to protocol-level flow control. If the link is a broadcast link shared by many nodes (classic Ethernet over a hub, or Wi-Fi's shared radio spectrum), a Medium Access Control (MAC) protocol must arbitrate who transmits and when, to avoid or manage collisions. This is the deep subject taken up separately in Multiple Access Protocols; here it suffices to note that link access is a service the link layer must provide whenever the underlying medium is shared, and that it is orthogonal to framing — you still frame the data the same way regardless of how access to the channel was won.

3. Additional services on top of the raw frame. Depending on the protocol, the adapter may also:

• Compute and append/verify an error-detection code (checksum, CRC) so the receiver can tell, with high probability, whether the frame was corrupted in transit. The mathematics of these codes is the subject of Error Detection and Correction; the link layer's role is simply to decide whether to use one and what to do if it signals corruption (discard silently, or request retransmission).
• Provide reliable delivery using acknowledgments and retransmissions, analogous to transport-layer reliability but scoped to a single hop. This is common on links with high error rates (old telephone-line modems, wireless links) and largely skipped on links that are already very reliable (modern fiber, most wired LANs), because redundant reliability mechanisms waste bandwidth and add latency without benefit.
• Provide flow control, pacing the sender so it does not overrun the receiver's buffer, again scoped to the single hop rather than the whole end-to-end path (the analogous end-to-end version lives in the transport layer).
• Perform half-duplex vs. full-duplex coordination, error correction (forward error correction, not just detection), and in switched LANs, address-based forwarding decisions inside switches.

Here is pseudocode for the sending and receiving adapter logic, generalized across framing styles and optional services, closely matching how a real network interface driver structures this work: ```pseudocode // SENDER SIDE — link-layer adapter transmitting a network-layer datagram function SEND_FRAME(datagram, dest_MAC, src_MAC, link_config): payload = datagram // opaque bytes from network layer header = build_header(src_MAC, dest_MAC, type = "IPv4") if link_config.uses_error_detection: code = compute_EDC(header + payload) // e.g., CRC-32 else: code = null frame_body = header + payload + code if link_config.framing == BYTE_COUNT: length_field = length(frame_body) frame = length_field + frame_body else if link_config.framing == BYTE_STUFFING: frame = FLAG + stuff_bytes(frame_body) + FLAG else if link_config.framing == BIT_STUFFING: frame = FLAG_BITS + stuff_bits(frame_body) + FLAG_BITS // Link access: acquire the medium if it is shared if link_config.is_broadcast_medium: wait_for_access_via_MAC_protocol(link_config) // see Multiple Access Protocols if link_config.reliable_delivery: send_and_await_ACK(frame, timeout = RTT_estimate, max_retries = N) else: transmit_bits(frame) // hand off to physical layer

// RECEIVER SIDE — link-layer adapter recovering frames from the bit stream function RECEIVE_FRAMES(bitstream, link_config): loop: if link_config.framing == BYTE_COUNT: length_field = read_bytes(bitstream, LENGTH_FIELD_SIZE) frame_body = read_bytes(bitstream, length_field) else if link_config.framing == BYTE_STUFFING: wait_for(bitstream, FLAG) // sync to start-of-frame raw = read_until(bitstream, FLAG) // read until closing flag frame_body = unstuff_bytes(raw) else if link_config.framing == BIT_STUFFING: wait_for(bitstream, FLAG_BITS) raw_bits = read_until(bitstream, FLAG_BITS) frame_body = unstuff_bits(raw_bits) header, payload, code = split(frame_body) if code != null: if compute_EDC(header + payload) != code: on_frame_error(header) // drop silently, or NACK, or request retransmit continue if header.dest_MAC == this_node.MAC or header.dest_MAC == BROADCAST: deliver_to_network_layer(payload) // pass datagram up the stack else: discard(frame_body) // not addressed to us ``` The figure below shows the layered picture: two adjacent nodes across one link, and the framed structure of the data that actually travels on the wire.

Time complexity of framing. Byte counting is $O(1)$ per frame to insert the length and $O(1)$ to strip it on receipt — the receiver does one length read and one bounded copy, no scan required. Byte stuffing and bit stuffing require scanning the payload once: sending costs $O(n)$ where $n$ is payload length, since every byte (or bit) must be examined for a potential match to the flag pattern, and unstuffing on the receiver is symmetric, $O(n)$. There is no way to do better than $O(n)$ for stuffing schemes, because correctness requires inspecting every byte/bit — an adversarial payload could contain the flag pattern anywhere, so no shortcut can skip inspection without risking a missed match.

Space complexity. Framing overhead is $O(1)$ additional bits per frame (a fixed-size header, trailer, and flag/length field), independent of payload size — this is what makes the layer efficient: constant metadata amortized over a payload of arbitrary size. Stuffing can, in the worst case (a payload that is entirely flag bytes, or entirely runs of five 1-bits), expand the transmitted size by up to roughly a factor of 2 (byte stuffing, one escape byte per payload byte in the worst case) or by 1 stuffed bit per 5 payload bits (bit stuffing, at most a 20% blow-up), but average-case overhead on real traffic is a small fraction of a percent, since the flag pattern is rare in typical payloads.

Correctness of framing (the key invariant). A framing scheme is correct if and only if it satisfies:

For byte-count framing this holds trivially as long as the length field itself is never corrupted — its correctness is entirely contingent on the integrity of that one field, which is why byte counting is fragile on noisy links (a single bit error in the length field desynchronizes the receiver for the rest of the session, an unrecoverable failure mode unless a higher layer resynchronizes). For stuffing schemes, correctness follows from an escaping invariant maintained by construction: every occurrence of the flag pattern inside the raw payload is preceded by an escape marker (byte stuffing) or interrupted by an inserted `0` bit (bit stuffing) before transmission, and the receiver reverses this transformation before interpreting the body. Because the transformation is a bijection between "raw payload" and "stuffed payload," and the flag pattern can never appear in a stuffed payload unescaped, the receiver can unambiguously locate frame boundaries by scanning for unescaped flags. This argument generalizes: as long as the stuffing rule guarantees the reserved pattern is uniquely identifiable post-encoding, decoding is unambiguous, which is exactly the property HDLC and PPP rely on.

Tradeoffs, stated honestly. Byte counting has zero framing overhead beyond the length field and no scanning cost, but a single corrupted length field can desynchronize an entire subsequent stream — a catastrophic, non-local failure mode. Stuffing schemes are self-synchronizing (a receiver that starts listening mid-stream can find the next flag and resynchronize immediately) and robust to isolated bit errors elsewhere in the frame, but they cost $O(n)$ scanning and unpredictable (though usually small) size expansion. Real protocols choose based on the link's error characteristics: noisy or shared links favor self-synchronizing stuffing; controlled, low-error environments can afford byte counting's simplicity. Adding reliability (ACK/retransmit) at the link layer trades latency and bandwidth for lower loss, which is why it's applied selectively — wireless 802.11 uses link-layer ACKs because wireless loss rates are high, but wired Ethernet typically does not bother, since bit errors are rare and end-to-end transport-layer reliability (TCP) already exists as a backstop.

Trace bit stuffing, the mechanism HDLC uses, on a concrete payload. The flag pattern is `01111110` (six 1-bits between two 0-bits). The bit-stuffing rule: whenever the sender's shift register has just transmitted five consecutive `1` bits from the payload, it inserts an extra `0`, regardless of what the next real payload bit is. The receiver reverses this: after seeing five consecutive `1` bits, it checks the next bit; if it's a `0`, it discards that bit (it was stuffed); if it's a `1`, that combined with the preceding five 1s signals a flag or an error condition. Suppose the raw payload bits (after header + data + CRC, before flags) are: ``` Raw payload: 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 ``` Walk the sender's logic left to right, counting consecutive 1-bits:

The transmitted stuffed sequence, with inserted bits shown in brackets: ``` Stuffed: 1 1 0 1 1 1 1 1 [0] 0 1 1 1 1 1 [0] 1 0 ``` Framed with the flag pattern at both ends: ``` Full frame: 01111110 1101111 1[0]0 1111 1[0]1 0 01111110 ^flag ^flag ``` Now trace the receiver, which scans the incoming bitstream after locating the opening flag `01111110`. It counts consecutive 1-bits; on reaching five, it inspects the next bit:

• After bit 8 (five 1s reached), the next received bit is `0` → this is recognized as a stuffed bit, discarded, and counting resets. The receiver has correctly recovered the original bit 9 (`0`) as the next payload bit.
• After bit 14 in the stuffed stream (again five 1s reached), the next bit is `0` → again a stuffed bit, discarded.
• If, at any such point, the next bit were also `1` (making six consecutive raw 1s), the receiver would recognize this as the flag pattern `01111110` if a `0` follows — i.e., end of frame — or, if a second `1` follows the run of six, this signals a framing error (something the physical layer or link is expected never to produce from a correctly stuffed stream, so its appearance indicates transmission corruption).

Reconstructing, the receiver strips the two flags and the two stuffed `0`s, and recovers exactly the original 16-bit raw payload — verifying the bijection property that makes bit stuffing correct. This is the mechanism that lets a protocol like HDLC or the historical version of PPP-over-HDLC-framing embed arbitrary binary payloads (which might otherwise contain the flag pattern by pure chance) without ambiguity, and it is precisely the self-synchronizing property that lets a receiver join an in-progress bitstream and correctly find the next frame boundary without needing any external clock or explicit length field.

The conceptual separation of the link layer from the network layer, and the framing techniques used to implement it, emerged from decades of practical networking engineering rather than a single theoretical breakthrough — but a few figures and moments defined the trajectory.

:::physicist[Robert Metcalfe|born 1946|Xerox PARC, co-inventor of Ethernet| Metcalfe and David Boggs designed Ethernet at Xerox PARC in the early 1970s, defining the frame format, MAC addressing, and the CSMA/CD access mechanism that became the dominant wired LAN link layer worldwide, foreshadowing the material in Multiple Access Protocols.

Every Ethernet switch in every office and data center operates entirely at the link layer, forwarding frames based on MAC addresses without ever inspecting IP headers — this is the mechanism that makes Ethernet switching fast and simple compared to IP routing. Wi-Fi access points implement the full menu of link-layer services simultaneously: framing (802.11 MAC frames), link access (CSMA/CA, foreshadowing Multiple Access Protocols), and link-layer acknowledgments for reliability over a notoriously lossy wireless medium. Cable and DSL modems run DOCSIS and PPPoE respectively at the link layer to get a subscriber's traffic from the home to the ISP's first router. Data center fabrics rely on link-layer flow control (e.g., Ethernet Priority Flow Control) to prevent buffer overflow between adjacent switches, a modern instance of the flow-control service described here. Even fiber-optic long-haul links between ISP routers run a link-layer protocol (often a variant of Ethernet framing or a synchronous protocol like SDH/SONET framing) to package IP datagrams for that one hop — meaning that essentially every packet that crosses the Internet is re-framed by a different link-layer protocol instance at every single hop of its journey, a fact hidden entirely from applications by the clean separation the link layer provides.

Ask the tutor: Can you walk through how CRC-based error detection would slot into the frame trailer we built in the worked example?