Data Link Layer Fundamentals

Data Link Layer Overview

The data link layer is the second layer of the OSI reference model, sitting above the physical layer and below the network layer. Its core task is to provide reliable and efficient data transfer between adjacent nodes — the two nodes connected directly by a physical link.

The physical layer only transmits a raw bit stream and is not concerned with the meaning or structure of those bits. The data link layer organizes the bit stream into frames, and uses mechanisms such as error control and flow control to turn a physical link that may corrupt data into a data link that appears error-free to the network layer.

Main Functions of the Data Link Layer

1. Framing

The IP datagrams (packets) handed down by the network layer are encapsulated into frames following a defined format. Control information is added to the head and tail of the frame so that the receiver can identify the start and end of each frame within the received bit stream.

The central problem framing must solve is: how does the receiver distinguish the boundaries of one frame inside a continuous bit stream?

2. Error Control

Noise and interference on a physical link can flip bits during transmission (a 0 becoming a 1, or a 1 becoming a 0). Error control covers two things:

• Error detection: finding out whether transmission produced errors
• Error correction: finding errors and repairing them automatically

Common error-detection codes include parity check and cyclic redundancy check (CRC); the common error-correction code is Hamming code.

3. Flow Control

The sender’s transmission rate is limited so that it does not exceed the receiver’s ability to receive and process, which prevents the receiver’s buffer from overflowing and losing data. The common mechanism is the sliding window protocol.

4. Reliable Transmission

Acknowledgment (ACK) and retransmission mechanisms ensure that data reaches the receiver correctly and in order. When a frame is corrupted or lost, the sender transmits it again.

5. Medium Access Control (MAC)

When several nodes share the same broadcast channel, as in Ethernet, rules are needed to govern how nodes access the channel and avoid collisions. This is the responsibility of the medium access control sublayer (the MAC sublayer).

Framing Methods

Framing works by adding special markers at the start and end of a frame so that the receiver can identify the frame boundaries. Four framing methods are commonly used.

1. Character Count

A field in the frame header states the number of bytes in the frame. By reading this count field, the receiver learns the length of the frame and therefore where the frame ends.

Advantages: simple, no padding required Disadvantages: if the count field itself is corrupted in transit, the receiver cannot identify the frame boundary correctly, and every subsequent frame becomes misaligned (frame synchronization is lost)

This method was used in DECNET’s DDCMP protocol.

2. Character Stuffing

Special control characters serve as the start and end markers of a frame. For example:

• FLAG (a flag byte such as 0x7E) delimits the frame
• when the data contains a byte identical to FLAG, an escape character ESC (such as 0x7D) is inserted before it
• if the data contains ESC, another ESC is inserted before it

After receiving an ESC, the receiver knows the next byte is data rather than a control character, and deletes the ESC.

Advantages: recovery from errors is possible (finding the FLAG again restores synchronization) Disadvantages: depends on a specific character set and is therefore coupled to the character encoding; stuffing and destuffing add processing overhead

This method was used in the early BISYNC protocol and in PPP (asynchronous mode).

3. Bit Stuffing

A special bit pattern (such as 01111110, that is, six consecutive 1 bits) serves as the frame delimiter.

Sender: whenever five consecutive 1 bits appear in the data, a 0 bit is inserted after them. The data therefore never contains six consecutive 1 bits.

Receiver: whenever five consecutive 1 bits arrive, the next bit is checked:

• if it is 0, the 0 is removed (restoring the data)
• if it is 1, the pattern is the frame delimiter (01111110)

4. Physical Layer Violations

Encoding patterns that are unused in the physical layer encoding are used as frame delimiters. In Manchester encoding, for example, every bit has a transition in its middle (high to low means 1, low to high means 0), so the absence of a transition is a violation and can mark the start and end of a frame.

Advantages: no padding, and the data is unaffected Disadvantages: depends on a specific physical layer encoding, so it is not general-purpose

This method was used in LANs such as 802.5 Token Ring.

Error Control

Parity Check

Parity check is the simplest error-detection code. A parity bit is appended after the data bits so that the number of 1 bits in the whole codeword (data bits plus parity bit) is odd (odd parity) or even (even parity).

Odd parity: the parity bit makes the total number of 1 bits odd Even parity: the parity bit makes the total number of 1 bits even

For example, the data 1011001 contains four 1 bits:

• odd parity: the parity bit is 1 (4+1=5, odd), and the codeword is 10110011
• even parity: the parity bit is 0 (4+0=4, even), and the codeword is 10110010

The receiver counts the 1 bits in the received codeword; if the agreed parity is not satisfied, transmission went wrong.

Detection capability: it detects an odd number of bit errors but not an even number, so its detection capability is weak and it is generally used where requirements are modest (such as ASCII transmission).

Cyclic Redundancy Check (CRC)

CRC is the most widely used error-detection code today: it has strong detection capability and high computational efficiency, and almost every modern network protocol (Ethernet, PPP, USB, and so on) uses it.

The Basic Idea of CRC

Treat the data to be sent as the coefficients of a polynomial $M(x)$. Choose a generator polynomial $G(x)$ (agreed in advance by both ends), perform modulo-2 division of $M(x)$ by $G(x)$, and the remainder $R(x)$ is the CRC code. The remainder $R(x)$ is appended to the data and sent.

The receiver performs modulo-2 division of the received data (including the code) by the same $G(x)$. A remainder of 0 means no error; a non-zero remainder means an error occurred.

The Steps of CRC Computation

Let the data be $k$ bits and let the generator polynomial $G(x)$ have degree $r$ (that is, $G(x)$ has $r+1$ bits):

1. Left shift: shift the data $M$ left by $r$ bits (append $r$ zero bits to the end of the data) to obtain $M \cdot 2^r$
2. Modulo-2 division: divide $M \cdot 2^r$ by $G$ using modulo-2 arithmetic (exclusive OR) to obtain the $r$-bit remainder $R$
3. Append: append the remainder $R$ to the data $M$, giving the transmitted codeword $T = M \cdot 2^r + R$

A CRC Computation Example

Problem: let the data be $M = 101001$ (6 bits) and the generator polynomial be $G(x) = x^3 + x^2 + 1$, that is, $G = 1101$ (4 bits, $r=3$). Find the CRC code.

Solution:

1. Shift the data left by 3 bits: $M \cdot 2^3 = 101001000$
2. Perform modulo-2 division by $G = 1101$:

        110101      (quotient, not needed)
    ___________
1101|101001000
     1101
     ----
      1110
      1101
      ----
       0111
       0000
       ----
        1110
        1101
        ----
         0110
         0000
         ----
          1100
          1101
          ----
           001    (remainder R = 001)

3. The remainder is $R = 001$, so the CRC code is 001
4. The transmitted codeword is $T = 101001001$

After the receiver obtains 101001001, division by 1101 leaves a remainder of 0, so the frame arrived without error.

Common Generator Polynomials

Hamming Code

Hamming code is an error-correction code proposed by Richard Hamming in 1950. It not only detects errors but can also correct single-bit errors.

Basic Principle

Several parity bits are inserted among the data bits, and each parity bit performs a parity check over a specific set of bits. When a single-bit error occurs, the results of several parity groups point to the position of the error, which allows the error to be located and corrected.

Encoding Rules for Hamming Code

Let the data consist of $m$ bits and the parity bits consist of $k$ bits. The following must hold:

$2^k \geq m + k + 1$

The parity bits are placed at the positions that are powers of two (that is, positions 1, 2, 4, 8, …), and the data bits occupy the remaining positions.

Each parity bit $P_i$ (located at position $2^{i-1}$) checks all positions whose binary index has a 1 in the $i$-th bit.

A Hamming Code Example

Problem: the data is 1011 (4 bits). Find the Hamming code.

Solution:

1. Determine the number of parity bits: $m=4$ and we need $2^k \geq 4+k+1$. For $k=3$, $2^3=8 \geq 8$, so the condition holds. Hence $k=3$ parity bits, and the total length is $n=4+3=7$.

2. Position layout (parity bits at positions 1, 2, and 4):

3. Compute the parity bits (even parity):

   • $P_1$ (position 1) covers positions 1, 3, 5, 7: $P_1 \oplus D_1 \oplus D_2 \oplus D_4 = 0$, that is, $P_1 \oplus 1 \oplus 0 \oplus 1 = 0$, so $P_1 = 0$
   • $P_2$ (position 2) covers positions 2, 3, 6, 7: $P_2 \oplus D_1 \oplus D_3 \oplus D_4 = 0$, that is, $P_2 \oplus 1 \oplus 1 \oplus 1 = 0$, so $P_2 = 1$
   • $P_3$ (position 4) covers positions 4, 5, 6, 7: $P_3 \oplus D_2 \oplus D_3 \oplus D_4 = 0$, that is, $P_3 \oplus 0 \oplus 1 \oplus 1 = 0$, so $P_3 = 0$

4. The Hamming code is: 0 1 1 0 0 1 1 (positions 1 through 7)

Error Correction with Hamming Code

After the receiver obtains the codeword, it checks each parity group and combines the results into a binary number (the correction factor). A correction factor of 0 means there is no error. A non-zero correction factor is the position number of the erroneous bit, and inverting that bit corrects the error.

For example, suppose 0110011 is received and bit 5 is corrupted, giving 0110111:

• Parity group 1 (positions 1, 3, 5, 7): $0 \oplus 1 \oplus 1 \oplus 1 = 1$ (error)
• Parity group 2 (positions 2, 3, 6, 7): $1 \oplus 1 \oplus 1 \oplus 1 = 0$ (correct)
• Parity group 3 (positions 4, 5, 6, 7): $0 \oplus 1 \oplus 1 \oplus 1 = 1$ (error)
• Correction factor = $P_3 P_2 P_1 = 101_2 = 5$, so bit 5 is in error and is corrected by inversion.

Worked Examples

Example 1: CRC Computation

The data to be sent is 1101011011 and the generator polynomial is $G(x) = x^4 + x + 1$ (that is, $G = 10011`). Find the CRC code and the transmitted codeword.

11010110110000 ÷ 10011
10011
-----
 10011
 10011
 -----
  00001
  00000
  -----
   00011
   00000
   -----
    00110
    00000
    -----
     01100
     00000
     -----
      11000
      10011
      -----
       10110
       10011
       -----
        01010
        00000
        -----
         1010    (remainder R = 1010, 4 bits)

Example 2: Hamming Code Encoding

The data is 1001 (4 bits). Using even parity, find the Hamming code.

Example 3: Analyzing a Framing Method

A data link layer protocol uses bit stuffing with the flag pattern 01111110. If the sender’s data is 011111101111101111110, write the actual bit sequence transmitted after bit stuffing.

Exercises

Exercise 1

Briefly describe the main functions of the data link layer, and explain why framing is needed.

Exercise 2

The data is 1101 and the generator polynomial is $G(x) = x^3 + x + 1$ (that is, $G=1011$). Find the CRC code.

1101000 ÷ 1011
1011
----
 1100
 1011
 ----
  1110
  1011
  ----
   101    (remainder)

Glossary