Data Link Layer Protocols: Services, Framing, and Error Control

Posted on Oct 30, 2025 in Computers

Data-Link Layer Service Categories

Describe the three possible categories of services provided by the data-link layer:

Unacknowledged Connectionless Service

  • This service is appropriate when the error rate is very low, so recovery is left to higher layers.
  • It is also appropriate for real-time traffic, such as voice, where late data are worse than bad data.

Acknowledged Connectionless Service

  • No logical connections are used, but each frame sent is individually acknowledged.
  • Thus, the sender knows whether a frame has arrived correctly or been lost. If it has not arrived within a specified time interval, it can be sent again.
  • This service is useful over unreliable channels, such as wireless systems (e.g., 802.11 Wi-Fi).

Acknowledged Connection-Oriented Service

This is the most sophisticated service the data link layer can provide to the network layer. It is performed in three phases:

  1. Connection Establishment: Both sides initialize variables and counters needed to keep track of which frames have been received and which ones have not.
  2. Transmission: One or more frames are transmitted.
  3. Connection Release: The connection is released, freeing up variables, buffers, and other resources.

Data Link Protocol Framing Methods

The following character encoding is used in a data link protocol:

  • A: 01000111
  • B: 11100011
  • FLAG: 01111110
  • ESC: 11100000

Show the bit sequence transmitted (in binary) for the four-character frame “A B ESC FLAG” when each of the following framing methods is used:

a. Byte Count Framing

The frame starts with a byte count (5 bytes total: Count + A + B + ESC + FLAG).

00000101 01000111 11100011 11100000 01111110
(Count 5) (A)      (B)      (ESC)    (FLAG)

b. Flag Bytes with Byte Stuffing

The frame is delimited by FLAG bytes. If FLAG or ESC appear in the data, they must be stuffed (preceded by ESC).

01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110
(FLAG)   (A)      (B)      (ESC)    (ESC)    (ESC)    (FLAG)   (FLAG)

Byte and Bit Stuffing Algorithms

a. Output After Byte Stuffing

The following data fragment occurs in the middle of a data stream for which the byte stuffing algorithm is used: A B ESC C ESC FLAG FLAG D. What is the output after stuffing?

Output after stuffing will be:

A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D

b. Maximum Overhead in Byte Stuffing

What is the maximum overhead in the byte-stuffing algorithm and when can it happen?

The maximum overhead occurs when the payload consists entirely of ESC and FLAG bytes. In this case, there will be 100% overhead (since every byte must be duplicated by a preceding ESC byte).

c. Bit Stuffing Transmission

A bit string, 0111101111101111110, needs to be transmitted at the data link layer. What is the string actually transmitted after bit stuffing?

After five consecutive 1s in the data, a 0 is added. Therefore, the output is:

011110111110011111010

Why Frames Need Start and End Flag Bytes

You may want to optimize the frame by having only one starting flag byte instead of both at the beginning and at the ending, as the next frame’s starting flag byte will do the job of the ending flag byte of the current frame. Why possibly has this not been already followed?

If you could always count on an endless stream of frames, one flag byte might be enough. However, if a frame ends (without an ending flag byte) and there are no new frames for a long period (e.g., 15 minutes), the receiver will not know where the frame ended. Furthermore, the receiver would not know that the next byte received is actually the start of a new frame and not just noise on the line. Thus, the protocol is much simpler and more robust with both starting and ending flag bytes.

Hamming Distance of Dual Parity Code

To provide more reliability than a single parity bit can give, an error-detecting coding scheme uses one parity bit for checking all the odd-numbered bits and a second parity bit for all the even-numbered bits. What is the Hamming distance of this code?

Making one change to any valid character cannot generate another valid character due to the nature of parity bits. Making two changes to even bits or two changes to odd bits will give another valid character, so the Hamming distance of this code is 2.

Error Detection vs. Correction Overhead Comparison

Consider a typical LAN channel where errors are isolated and the rate is $10^{-6}$. If the block size is 1000 bits, error correction requires about 10 check bits per block. On the other hand, error detection requires 1 parity bit per block. Quantitatively compare and explain why you would prefer error detection rather than correction for 1 Megabit (Mb) of data transmission.

Error Detection Overhead Calculation (Assuming 1 Retransmission)

  • Number of blocks in 1 Mb: $10^6 / 1000 = 1000$ blocks.
  • Parity overhead: $1000 ext{ blocks} imes 1 ext{ bit/block} = 1000$ bits.
  • Total overhead for 1 retransmission (1000 blocks + 1000 parity bits): $2000$ bits.

Error Correction Overhead Calculation

  • Check bit overhead: $1000 ext{ blocks} imes 10 ext{ check bits/block} = 10,000$ bits.

Conclusion: Error detection requires 2,001 bits of overhead (1000 parity bits + 1001 bits for the retransmitted block) for a single error event, while error correction requires 10,000 bits of overhead regardless of errors. Since the error rate ($10^{-6}$) is very low on a typical LAN, the probability of needing retransmission is low. Thus, detection offers significantly less overhead (approximately 5 times less) per Mb of data transmission, making it the preferred choice in reliable environments like LANs.

Calculating the Internet Checksum (4-bit Word)

Suppose that a message 1001 1100 1010 0011 is transmitted using the Internet Checksum (4-bit word). What is the value of the checksum?

The one’s complement sum is calculated by summing the words modulo $2^4$ and adding any overflow of high-order bits back into the low-order bits:

  1. $0011 + 1010 = 1101$
  2. $1101 + 1100 = 1001$ (Sum) $+ 1$ (Carry) $= 1010$
  3. $1010 + 1001 = 0011$ (Sum) $+ 1$ (Carry) $= 0100$

The final sum is 0100. The Internet Checksum is the one’s complement of the sum, which is 1011.

Steps to Compute the Internet Checksum

Write down the steps to compute the Internet checksum to be sent:

  1. Arrange the data (e.g., 1500 bytes) as rows of 16-bit words.
  2. Initialize the checksum field in the last row with all ‘0’ bits.
  3. Add all the rows together using one’s complement arithmetic. If a carryover occurs (the sum exceeds 16 bits), the carry is added back to the previous result (the 16-bit wide block).
  4. Take the one’s complement of the final sum. This result is the Internet Checksum to be transmitted.