Data Link Layer
The Data Link Layer is the second layer of the network stack, sitting between the Physical
layer and the Network layer. Its main role is to package raw bits from the Physical layer into
frames and provide reliable data transfer across a single link. In practice, the Data Link layer
ensures that packets from the Network layer are encapsulated into frames (with headers and
trailers) for transmission, and that errors and lost frames on the link are handled. Each frame
typically contains a header (with source/destination link addresses), a payload (carrying the
network-layer packet), and a trailer with an error-check (e.g., a CRC). The Data Link layer’s job
is to take these frames from the sender’s network layer, transmit them over the physical link,
and deliver them to the receiver’s network layer. In doing so it offers various services
(unacknowledged delivery, reliable transfer, flow control, etc.) to the layers above.
Services to the Network Layer
The Data Link layer can offer different service classes to the Network layer, depending on the
protocol. Three common options are:
● Unacknowledged Connectionless Service: Each frame is sent independently with no
acknowledgments. If a frame is lost or corrupted, the Data Link layer does not attempt to
recover it – it simply delivers or discards frames as they arrive. Ethernet is a classic
example of this service: it uses a simple MAC framing with source/destination MAC
addresses and a frame check sequence (FCS) but does not acknowledge individual
frames. This “best-effort” service is appropriate when the link error rate is very low or
when real-time delivery is needed (e.g. streaming voice).
● Acknowledged Connectionless Service: Each frame is still sent independently (no
explicit “connection” setup), but the receiver acknowledges each frame. The sender
uses a timer: if an acknowledgment (ACK) does not arrive in time, the sender retransmits
the frame. This provides reliability over an unreliable link. For example, wireless 802.11
(Wi-Fi) uses this service: every data frame can be ACKed at the MAC layer, and lost
frames are retransmitted. Because each frame is acknowledged individually, the sender
always knows whether a frame arrived, allowing timely recovery from losses.
● Connection-Oriented Service: Before sending data, the sender and receiver perform a
handshake to establish a connection. They agree on parameters, and then all frames
on this connection are numbered and tracked. The Data Link layer guarantees that each
frame sent is received exactly once and in order. This effectively provides a reliable byte
stream to the Network layer. Such service is used on long, error-prone links (satellite or
long-haul circuits) where overhead is acceptable to ensure reliability. (After data transfer,
the connection is released to free resources.)
Framing
To deliver packets, the Data Link layer breaks the raw bit stream into frames. Each frame
contains a header (e.g. link-layer addresses and control fields) and a trailer (often a checksum
or CRC). The payload is the packet from the Network layer. In practice, the data link protocol
must mark the start and end of each frame. Common framing methods include:
● Length/Byte Count: A field (usually in the header) specifies the number of bytes in the
frame. The receiver reads this count to know where the frame ends. (This is simple but
fragile: if the count is corrupted by noise, the receiver loses sync.)
● Byte Stuffing (Flag Bytes): A special flag byte (often 0x7E) marks frame boundaries.
For example, in PPP (Point-to-Point Protocol) and HDLC, the bit-pattern 01111110
(0x7E) is used as a frame flag. Whenever this flag pattern occurs in the data, the
transmitter inserts (stuffs) an escape byte (e.g. 0x7D) beforehand. This way, the receiver
can unambiguously detect flag sequences as frame delimiters. (PPP is actually
byte-oriented: it treats 0x7E as a special flag and uses an escape 0x7D when data
contains 0x7E.)
● Bit Stuffing (Flag Bits): Similar to byte stuffing, but at the bit level. With HDLC framing,
the frame begins and ends with the bit pattern 01111110 (0x7E). Whenever the
sender’s data contains five consecutive 1-bits, the transmitter automatically inserts a
0-bit. The receiver removes (“destuffs”) this extra bit on reception. This guarantees that
01111110 only appears as a flag between frames.
● Physical Coding Violations: On some links, special signal patterns outside the normal
code space can mark frame boundaries. (This is a more advanced technique, used in
certain physical-layer codes.)
These framing methods ensure the receiver can locate each frame boundary and recover even
if errors occur. For example, PPP frames always begin and end with 0x7E, and any occurrence
of 0x7E in the data is escaped, allowing the receiver to find frame boundaries by scanning for
the flag byte.
Error Detection and Correction
Because links are imperfect (noise can flip bits), the Data Link layer uses error-detection
codes in each frame. Typically the sender computes a checksum over the frame (often using a
CRC – Cyclic Redundancy Check) and includes it in the trailer. On receipt, the receiver
recomputes the code and compares it. If the codes differ, the frame is known to be corrupted
and can be discarded. Common error-detection techniques include:
● Parity Bit: A simple method where one extra bit is added so that the total number of
1-bits is even (even parity) or odd (odd parity). For example, even parity appends a 0 or
1 so that the sum of bits is even. Even parity detects any single-bit error (and any odd
number of bit errors) but fails if two bits flip. (Parity is cheap and can detect single-bit
errors but is not foolproof against multiple errors.)
● Checksum: A block checksum (like Internet checksum) divides the data into words and
adds them (often in one’s-complement arithmetic), placing the final sum (or its
complement) in the frame. The receiver adds up the words again and checks if the sum
is correct (zero). This catches many common error patterns but is weaker than CRC.
● Cyclic Redundancy Check (CRC): A powerful code used in Ethernet, Wi-Fi, etc. CRC
treats the frame bits as coefficients of a polynomial and divides by a fixed “generator”
polynomial. The remainder of this binary division (the CRC bits) is appended to the
frame. When the receiver divides the incoming frame by the same polynomial, a zero
remainder indicates no error; any nonzero remainder means a transmission error
occurred. For example, a 32-bit CRC (as in Ethernet) can detect virtually all common
error patterns (single-bit errors, double-bit errors, odd-number of errors, burst errors up
to 32 bits, etc. ).
● Hamming Codes (Error-Correcting Codes): To not only detect but also correct errors,
the frame can include extra parity bits arranged to locate single-bit errors. A Hamming
code places parity (check) bits at power-of-two positions in the bit sequence. Each parity
bit covers a specific set of data bits (by XOR). For instance, an (11,7) Hamming code
has 7 data bits and 4 check bits at positions 1, 2, 4, and 8. This yields a Hamming
distance of 3, meaning it can correct any single-bit error in the 11-bit codeword.
In the example above, each colored column shows which bits each parity bit checks. If one bit is
flipped in transmission, the pattern of parity-check bits (the syndrome) directly identifies the
erroneous bit position. The receiver then flips that bit back and recovers the original data.
Hamming codes thus allow single-bit error correction (and detection of double-bit errors) with
relatively low overhead (here 4 parity bits for 7 data bits).
Overall, error-detection adds redundancy so the receiver can detect errors, and optionally
error-correcting codes add enough redundancy to fix some errors. Common practice at the
Data Link layer is to use an error-detecting code (CRC or parity) and rely on retransmission if
errors are detected.
Automatic Repeat reQuest (ARQ) Protocols
If a frame is detected as bad (or if it is lost), the Data Link layer must recover it. The usual
approach is an ARQ (Automatic Repeat reQuest) protocol: the sender transmits frames and
waits for acknowledgments (ACKs) from the receiver. If an ACK does not arrive within a timeout
interval, the sender assumes the frame (or its ACK) was lost and retransmits. Negative ACKs
(NAKs) may also be used to explicitly indicate a bad frame. Sequence numbers are attached to
frames so the receiver can discard duplicates: each frame is given a unique number, and the
receiver only accepts a new frame if its sequence number is fresh. Timers and sequence
numbers together ensure that each frame is ultimately delivered exactly once.
As an example, Stop-and-Wait ARQ is a simple ARQ protocol: the sender sends one frame
(e.g. Frame 0) and then waits for its ACK. Only after the ACK arrives does the sender send the
next frame (Frame 1). The figure illustrates normal operation and cases where a frame or its
ACK is lost. If an ACK does not arrive before the timeout, the sender retransmits the same
frame. In all cases, frames carry sequence numbers (0,1 in stop-and-wait) so that the receiver
knows whether a frame is new or a duplicate; duplicates are discarded. This stop-and-wait
scheme is simple but inefficient if the round-trip time is large relative to the frame transmission
time, since the link sits idle while waiting for each ACK.
To improve efficiency, sliding-window ARQ protocols allow multiple frames “in flight” before
needing an ACK. In a window protocol, the sender may transmit up to N frames in sequence
(window size = N) without waiting, and the receiver maintains a corresponding receive window.
The receiver grants permission by implicitly or explicitly telling the sender how many frames it
can send. For example, the receiver might say “you may send me n frames now; after those,
stop and wait for further permission”. As ACKs come back, the sender “slides” the window
forward and sends new frames. Go-Back-N and Selective Repeat are common sliding-window
schemes. These protocols regulate the flow of frames and handle retransmissions (Go-Back-N
resends all frames after a loss, Selective Repeat resends only the lost frames). In all cases,
acknowledgments (ACKs) and retransmissions make the link appear reliable to higher layers.
Flow Control
Flow control ensures that a fast sender does not overwhelm a slow receiver. For example, a
powerful server could easily transmit frames faster than a low-end client can process them. If
unchecked, the client’s buffers could overflow. Two general approaches exist:
● Feedback-Based Flow Control: The receiver sends feedback to the sender, effectively
granting “credits” or permission to send more data. This is often implemented via the
sliding-window ACK scheme above: the receiver’s ACKs implicitly let the sender know
how many more frames it may send. In simple stop-and-wait, an implicit window of 1 is
enforced: the sender must wait for each ACK. In more advanced window protocols, the
receiver advertises a larger window. For example, the receiver might say “I can handle 5
frames” and the sender may send 5 frames before stopping. This ensures the sender
never has more than the allowed number of unacknowledged frames outstanding.
● Rate-Based Flow Control: The sender’s rate is limited by a built-in clock or pacing,
without explicit feedback. For instance, the link layer hardware might be designed to run
at “wire speed” so that overflow virtually never occurs, or the hardware imposes a
maximum transmission rate. This is less common at the link layer; more often, flow
control is handled by buffering and ACK-based windows.
In summary, data link flow control typically uses a sliding window with a receiver-advertised
window size. The link-layer hardware or protocol ensures that “Window Size” unacknowledged
frames are not exceeded.
Data Link Protocol Examples
Many data link layer protocols illustrate these concepts:
● HDLC (High-Level Data Link Control): An older, bit-oriented protocol. It uses bit
stuffing with flags (0x7E) as described above. HDLC frames include an address, control,
and FCS fields. (PPP’s framing is based on HDLC.)
● PPP (Point-to-Point Protocol): A ubiquitous protocol for point-to-point links (dial-up,
DSL, etc.). PPP frames begin and end with the HDLC flag byte 0x7E. It is byte-oriented:
an escape byte (0x7D) is used to byte-stuff any occurrence of 0x7E or 0x7D in the
payload. PPP supports both error detection (via CRC) and optional link configuration
(using its Link Control Protocol (LCP)) to negotiate options before data transfer.
● Stop-and-Wait, Go-Back-N, Selective-Repeat ARQ: These are basic protocol
schemes (often taught in textbooks) that implement the ARQ mechanisms above. In
stop-and-wait, the window size is 1. Go-Back-N uses a fixed window and retransmits all
frames after a lost frame. Selective-Repeat maintains buffers to retransmit only specific
lost frames. (Tanenbaum’s text provides detailed examples, though we omit the
algorithmic details here.) Each uses sequence numbers, ACKs (and possibly NAKs), and
timers as described.
● Ethernet (IEEE 802.3): A widely used LAN technology. An Ethernet frame starts with a
7-byte preamble and a start-frame delimiter, then a header containing destination and
source MAC (hardware) addresses, followed by a type/length field and payload (up to
1500 bytes), and ends with a 4-byte Frame Check Sequence (FCS). The FCS is a 32-bit
CRC that detects any in-transit corruption. Ethernet is inherently unacknowledged and
connectionless at the MAC level (recovery is left to higher layers). Originally it used
CSMA/CD (carrier-sense and collision detection) for access; modern full-duplex switches
simply forward frames without collisions. Key abbreviations: MAC = Media Access
Control (the sublayer that manages Ethernet addressing), FCS = Frame Check
Sequence (the CRC field).
● IEEE 802.11 (Wi-Fi): A wireless LAN standard. Wi-Fi frames (at the MAC layer) have a
Frame Control field at the start and an FCS (32-bit CRC) at the end. Unlike Ethernet,
802.11 typically uses an acknowledged data link service: after sending a data frame,
the sender expects a short ACK frame (at the MAC layer) from the receiver. If no ACK
arrives in a short time, the data frame is retransmitted (a simple ARQ mechanism).
802.11 also implements MAC-layer flow control via a sliding window (via Sequence and
Acknowledgment numbers in the header). The many 802.11 frame types (data, control,
management) all include the Frame Check Sequence. (802.11 uses CSMA/CA with
collision avoidance for channel access.)
● DOCSIS (Cable Modems): The Data Over Cable Service Interface Specification defines
the data link layer for cable modem networks. In DOCSIS, IP packets are encapsulated
in fixed-size MPEG-transport frames for transmission over the shared coax network.
Each DOCSIS data frame is identified by a special MPEG packet ID (PID 0x1FFE) so
that cable carriers can distinguish data from video streams. The DOCSIS MAC layer
includes a header and CRC similar to Ethernet’s framing (in fact, DOCSIS often uses an
Ethernet-like header as defined in ISO 8802-3). Upstream (from modem to headend),
DOCSIS uses TDMA: the Cable Modem Termination System (CMTS) grants time slots to
each modem. Downstream, the channel is broadcast (like a one-to-many link). From the
data link perspective, DOCSIS provides reliable delivery via ACK/NAK and timing control
over the noisy cable medium.
Summary of Key Concepts
● Framing: The data link layer encapsulates network-layer packets into frames with
headers/trailers, using methods like byte- or bit-stuffing to delimit frames.
● Error Detection: Each frame carries a checksum (parity, simple sum, or CRC) to detect
errors. Common techniques: single-bit parity, checksums, or a CRC (e.g. 32-bit CRC in
Ethernet).
● Error Correction: With special codes (e.g. Hamming codes), the data link layer can
correct some bit errors. A Hamming code of distance 3 can correct 1-bit errors by
inserting parity bits at positions 1,2,4,8….
● Error Control (ARQ): For reliable transfer, the link layer uses ACKs, timeouts, and
retransmissions. In Stop-and-Wait ARQ, the sender sends one frame and waits for an
ACK. Sliding-window ARQ (Go-Back-N, Selective Repeat) allows multiple unacked
frames and uses sequence numbers to manage retransmissions.
● Flow Control: Prevents sender from overrunning receiver. Typically done with a sliding
window: the receiver implicitly (via ACKs) or explicitly tells the sender how many frames
it can send before stopping. Alternatively, a rate-limit can be imposed.
● Services to Network Layer: The link layer may be unreliable (unacknowledged) or
reliable (acknowledged/connection-oriented). Ethernet’s service is unacknowledged and
connectionless; Wi-Fi’s MAC is acknowledged connectionless; X.25 or PPP can offer
connection-oriented service.
● Real-world Technologies: Ethernet (IEEE 802.3), Wi-Fi (IEEE 802.11), and DOCSIS all
implement data link layer framing and error control. For example, each Ethernet frame
ends with a 32-bit CRC FCS, and each Wi-Fi frame ends with an FCS and is typically
acknowledged by the receiver.
Each acronym used above is defined at first use: CRC (Cyclic Redundancy Check), ARQ
(Automatic Repeat reQuest), ACK (acknowledgment), PPP (Point-to-Point Protocol), HDLC
(High-level Data Link Control), etc. Through framing, error checks, retransmissions, and flow
control, the Data Link layer provides an essential hop-by-hop reliable service (of varying
sophistication) to support network-layer communication.
Sources: Concepts and examples are drawn from Tanenbaum & Wetherall (Computer
Networks, 6th Ed.) and supplemented by standard networking references, among others.
