Data Link Layer Functions and Protocol

Error detection and error correction techniques

Error occurs when the information received at the destination does not match the data sent by
the source. This discrepancy is often caused by noise in the transmission medium, which can
distort digital signals and introduce errors in the binary bits traveling from sender to receiver.
As a result, a bit representing 0 may change to 1, or a bit representing 1 may change to 0.
Such errors are particularly significant in data communication systems, as they compromise
the reliability of transmitted information.

Data transmission is often implemented at the Data Link Layer or Transport Layer of the OSI
Model, where it may get scrambled by noise or corrupted during transit. To address this issue,
error-detection codes are added to digital messages as extra bits of data. These codes help
identify errors that may have occurred during transmission, ensuring greater accuracy and
reliability in communication. Techniques such as parity bits, checksums, and cyclic
redundancy checks (CRC) are commonly used to detect errors.

Types of Errors
There may be three types of errors:

Error Detection Methods

Errors in received frames are detected using techniques such as Parity Check, Cyclic
Redundancy Check (CRC), and Checksum. In all these methods, extra bits are added to the
actual data being transmitted. These additional bits, known as error-detection codes, help the
receiver verify whether the received data matches the data that was originally sent.
 Parity Check involves adding a single bit to ensure that the total number of 1s in the
data is either even or odd, depending on the chosen parity.

 Checksum: The checksum technique involves dividing the data into blocks,
calculating the sum of all the blocks, and appending this sum (or a representation of
it) as extra bits to the data. The receiver recalculates the checksum and compares it to
the transmitted value to detect any discrepancies..
Suppose we have data to be transmitted:
makefile
Data: 10101010 11001100
1. Divide the data into blocks (e.g., 8 bits per block):
Block 1: 10101010
Block 2: 11001100
2. Add the blocks together:
10101010
 11001100
1 10110110 (carry the 1)
3. Take the 1's complement of the sum (invert the bits):
11001001 (Checksum)
4. This checksum 11001001 is sent along with the data.
At the receiver’s end, the blocks of data are added again, and the checksum is
verified.
Calculation Image
 Cyclic Redundancy Check (CRC): This method uses polynomial division. The data
is treated as a large binary number, and it is divided by a predefined polynomial. The
remainder from this division is appended to the data. The receiver performs the same
division operation and checks if the remainder matches the transmitted one. If there’s
a mismatch, it indicates that errors occurred during transmission.

Example:
Let’s say we have the following data to send, and we are using a simple CRC-8
polynomial for error checking, x^3 + x + 1, which is 1011 in binary.

 Data to transmit: 1101011011

 Divisor (CRC polynomial): 1011

1. Append zeros to the data:

Since the divisor is of degree 3 (i.e., 4 bits), we append 3 zeros to the end of the data:

1101011011 000
2. Perform polynomial division: We divide 1101011011 000 by 1011 using binary
division.
 1101011011000 ÷ 1011 = 1000000001 (remainder: 101)
3. Transmitted data:
The remainder (101) is appended to the data:

Data: 1101011011 Remainder: 101

Transmitted: 1101011011101
4. Receiver check:
The receiver performs the same division on the received data (1101011011101). If the
remainder is 000, it indicates no errors. If the remainder is non-zero, an error is
detected.

Error Correction

Once errors are detected in a network, the erroneous bits need to be replaced with the correct
sequence so that the receiver can accept and process the data. This process of fixing errors is
known as Error Correction. There are two primary methods used for error correction in
networks:
1. Forward Error Correction (FEC)

In Forward Error Correction (FEC), the receiver is responsible for detecting and
correcting errors without needing any retransmission from the sender. This is done by adding
redundant bits (error-detection or error-correction codes) to the original data before
transmission. These extra bits allow the receiver to correct the errors, which minimizes the
need for retransmission and reduces delays.

 Advantages:
o No need for retransmissions, which makes FEC highly suitable for real-time
applications like video streaming, satellite communications, and VoIP.
o Reduces network congestion by avoiding the overhead of sending the same
data multiple times.

 Disadvantages:
o Increased overhead due to the extra error-correction bits.
o Can be less efficient when error rates are very high, as it may not be able to
correct all errors without retransmission.

2. Backward Error Correction (BEC)

In Backward Error Correction (BEC), the sender is responsible for retransmitting the data
when errors are detected. The receiver signals the sender to resend the corrupted data or the
entire message. This process ensures that the data is accurate and reliable, but it requires
feedback from the receiver to the sender.

 Advantages:
o It is more reliable in scenarios where data integrity is critical, as the sender can
resend the data until the receiver gets a correct copy.
o Does not require additional overhead in terms of error-correction bits at the
receiver side.

 Disadvantages:
o Retransmissions increase network traffic and delay, which may affect
performance in time-sensitive applications.
o Requires more sophisticated protocols to handle retransmissions,
acknowledgments, and error detection.

3. Hamming Code (A Widely Used Error Correction Technique)

One of the most widely used error correction methods is the Hamming Code, which was
designed by R.W. Hamming. This technique enables the correction of single-bit errors and
the detection of double-bit errors. It works by adding parity bits to the data in such a way
that the receiver can identify and correct errors without needing retransmission.

How Hamming Code Works:

1. Adding Parity Bits:

In Hamming code, the data is split into blocks, and additional parity bits are added to
 the data. The number of parity bits is determined based on the length of the data. The
key idea is to place the parity bits in positions that are powers of 2 (i.e., positions 1, 2,
4, 8, etc.).
2. Parity Bit Calculation:
Each parity bit checks a specific set of data bits, ensuring that the total number of 1s
in those bits (including the parity bit) is even. This helps the receiver detect which bit
has been corrupted.
3. Error Detection and Correction:
When the receiver receives the data, it checks the parity of the data using the same
method and compares it to the received parity bits. If a discrepancy is found, the
receiver can pinpoint the exact position of the corrupted bit and correct it. If multiple
errors are detected, the receiver will know the data is corrupt and may request
retransmission.

Example of Hamming Code:

Consider the data:

Data: 1011

We need to add parity bits to it.

1. Step 1: Determine the number of parity bits (we need 3 parity bits for 4 data bits).
o Parity positions are: 1, 2, and 4.

2. Step 2: Add parity bits to the data:

_ _ 1 _ 0 1 1
P1 P2 D1 P4 D2 D3 D4

3. Step 3: Calculate the parity bits using even parity:

o P1 checks positions 1, 3, 5, and 7.
o P2 checks positions 2, 3, 6, and 7.
o P4 checks positions 4, 5, 6, and 7.

After calculating, the encoded data might look like:

1 0 1 1 0 1 1
P1 P2 D1 P4 D2 D3 D4

The receiver checks the parity bits and if an error is detected, it can correct the error
by flipping the bit at the incorrect position.

COMPUTER NETWORKS LAB

Simulate Cyclic Redundancy Check (CRC) error detection algorithm for noisy channel.
Python program:

import random
def xor(a, b):
return ''.join('0' if a[i] == b[i] else '1' for i in range(1, len(b)))

def mod2_division(data, divisor):

pick = len(divisor)
temp = data[:pick]
while pick < len(data):
temp = xor(temp, divisor if temp[0] == '1' else '0' * len(divisor)) + data[pick]
pick += 1
return xor(temp, divisor if temp[0] == '1' else '0' * len(divisor))

def encode_data(data, divisor):

appended_data = data + '0' * (len(divisor) - 1)
remainder = mod2_division(appended_data, divisor)
return data + remainder, remainder

def simulate_noise(data):
noisy_bit = [Link](0, len(data) - 1)
data = list(data)
data[noisy_bit] = '1' if data[noisy_bit] == '0' else '0'
return ''.join(data), noisy_bit

# Input data and divisor

data = input("Enter data: ")
divisor = input("Enter divisor: ")

# Encode data with CRC

encoded_data, crc = encode_data(data, divisor)
print(f"Encoded Data: {encoded_data}")

# Simulate noisy channel

noisy_data, position = simulate_noise(encoded_data)
print(f"Received Data: {noisy_data} (Noisy bit: {position})")

# Error detection
remainder = mod2_division(noisy_data, divisor)
print("Error detected." if [Link]('0') else "No error detected.")

Input:
Enter data: 1011001
Enter divisor: 1101

Output:

Encoded Data: 1011001110

Received Data: 1011011110 (Noisy bit: 4)
Error detected.
Same Program in Python
import random

def xor(a, b):

"""Perform XOR operation between two binary strings."""
return ''.join(['0' if a[i] == b[i] else '1' for i in range(1, len(b))]) + a[len(b):]

def mod2_division(dividend, divisor):

"""Perform modulo-2 division."""
pick = len(divisor)
temp = dividend[:pick]

while pick < len(dividend):

if temp[0] == '1':
temp = xor(temp, divisor) + dividend[pick]
else:
temp = xor(temp, '0' * pick) + dividend[pick]
pick += 1

if temp[0] == '1':
temp = xor(temp, divisor)
else:
temp = xor(temp, '0' * pick)

return temp

def encode_data(data, divisor):

"""Encode data by appending CRC."""
appended_data = data + '0' * (len(divisor) - 1)
remainder = mod2_division(appended_data, divisor)
return data + remainder, remainder

def add_noise(data):
"""Introduce noise by flipping a random bit."""
noisy_data = list(data)
position = [Link](0, len(data) - 1)
noisy_data[position] = '1' if noisy_data[position] == '0' else '0'
return ''.join(noisy_data), position

def detect_error(received_data, divisor):

"""Detect error in received data."""
remainder = mod2_division(received_data, divisor)
return remainder != '0' * (len(divisor) - 1), remainder

# Input data and divisor

data = input("Enter data: ")
divisor = input("Enter divisor (generator polynomial): ")
# Step 1: Encode data with CRC
encoded_data, crc = encode_data(data, divisor)
print(f"Original Data: {data}")
print(f"Encoded Data (Data + CRC): {encoded_data}")
print(f"CRC: {crc}")

# Step 2: Simulate noisy channel

noisy_data, noisy_bit = add_noise(encoded_data)
print(f"Transmitted Data: {encoded_data}")
print(f"Received Data (after noise): {noisy_data}")
print(f"Noisy bit position: {noisy_bit}")

# Step 3: Error detection at the receiver

error_detected, remainder = detect_error(noisy_data, divisor)
if error_detected:
print("Error detected in received data.")
else:
print("No error detected in received data.")
print(f"Remainder after checking: {remainder}")

Input:
Enter data: 1011001
Enter divisor (generator polynomial): 1101

Output:
Original Data: 1011001
Appended Data: 1011001000
Remainder (CRC): 110
Encoded Data (Data + CRC): 1011001110
Transmitted Data: 1011001110
Received Data (after noise): 1011001010
Noisy bit position: 5
Error detected in received data.

Data-Link Control: Framing and Flow Control

In the data-link layer of networking, two critical functions ensure efficient and reliable
communication between two directly connected devices: framing and flow control.

Framing refers to the process of dividing the continuous stream of data into smaller,
manageable units known as frames. These frames serve as the building blocks for
communication between sender and receiver. Framing helps to define the boundaries of each
message and ensures synchronization between devices. Additionally, it allows for error
detection within individual frames. There are different techniques for framing, such as
character-oriented framing, where special characters (e.g., STX for start and ETX for end)
are used to mark frame boundaries, typically in ASCII-based systems. Another method is bit-
oriented framing, which uses bit patterns (such as a flag 01111110) to define frame
boundaries, common in protocols like HDLC. Framing also includes physical layer framing,
which utilizes signals or time slots to separate frames.

Flow control, on the other hand, regulates the rate at which data is sent from the sender to the
receiver to prevent data overload. Without flow control, a sender could transmit data faster
than the receiver can process, leading to data loss or congestion. One simple flow control
mechanism is the Stop-and-Wait protocol, where the sender transmits one frame and waits
for an acknowledgment (ACK) from the receiver before sending the next frame. This method
is straightforward but can be inefficient, especially for high-latency or high-bandwidth
networks. A more advanced flow control technique is the Sliding Window protocol, which
allows the sender to transmit multiple frames before waiting for an acknowledgment. In this
method, each frame is assigned a unique sequence number, and the receiver provides
feedback in the form of a window that specifies how much data it can handle. The sliding
window approach is more efficient because it enables pipelined transmission, reducing idle
time.

Error Recovery Protocols: Stop-and-Wait ARQ (Automatic Repeat Request)

The Stop-and-Wait ARQ (Automatic Repeat Request) is a reliable data delivery method
used for error and flow control between the sender and receiver, especially over noisy
communication channels or links. This protocol is a type of Sliding Window Protocol that
ensures reliable transmission by confirming that each data frame is received successfully
before proceeding with the next one.

In the Stop-and-Wait ARQ protocol, the sender sends a data frame and then stops to wait
for an Acknowledgment (ACK) from the receiver. The ACK indicates that the receiver has
successfully received the transmitted frame. Once the sender receives the ACK, it proceeds to
send the next data frame. If an error occurs during transmission, or the acknowledgment is
not received, the sender will retransmit the frame until it receives a valid ACK. This process
of waiting for an acknowledgment before sending the next frame is the reason it is called
Stop-and-Wait.

In simpler terms, the protocol sends a data frame, waits for an acknowledgment from the
receiver, and then either proceeds with the next frame or retransmits the frame if an error is
detected. This mechanism ensures that data is delivered reliably, despite the presence of
errors in the communication channel. However, it can be inefficient for high-speed or long-
distance communication due to the idle wait time between frames.

How Stop-and-Wait ARQ Works:

1. Sender sends a frame to the receiver.

2. The receiver acknowledges the reception of the frame by sending an Acknowledgment
(ACK) back to the sender.
3. If the sender receives the ACK, it proceeds to send the next frame.
4. If the ACK is not received or the receiver detects an error (using error detection methods
like CRC), the sender retransmits the same frame.
5. The sender waits for an ACK before sending the next frame (hence the term "Stop-and-
Wait").
Steps in Stop-and-Wait ARQ:

1. Frame Transmission: The sender sends a data frame to the receiver.

2. ACK or NAK: The receiver checks the frame for errors. If no error is detected, the receiver
sends an ACK (Acknowledgment). If an error is detected, the receiver sends a NAK (Negative
Acknowledgment).
3. Retransmission: If the sender does not receive the ACK (due to either an error in the frame
or loss of the acknowledgment), it retransmits the frame.

Diagram of Stop-and-Wait ARQ

Sender Receiver
| |
|------------------- Frame 1 ------------------->| (Send Frame 1)
| |
|<------------------- ACK 1 --------------------| (Receiver sends ACK
1)
| |
|------------------- Frame 2 ------------------->| (Send Frame 2)
| |
|<------------------- ACK 2 --------------------| (Receiver sends ACK
2)
| |
|------------------- Frame 3 ------------------->| (Send Frame 3)
| |
|<------------------- NAK 3 --------------------| (Receiver sends NAK 3
- error detected)
| |
|------------------- Frame 3 ------------------->| (Sender retransmits
Frame 3)
| |
|<------------------- ACK 3 --------------------| (Receiver sends ACK
3)
| |

Explanation of the Diagram:

 The sender sends Frame 1 to the receiver.

 The receiver acknowledges Frame 1 by sending ACK 1 back to the sender.
 The sender then sends Frame 2.
 The receiver acknowledges Frame 2 with ACK 2.
 When the sender sends Frame 3, the receiver detects an error, sends NAK 3 (Negative
Acknowledgment), and the sender retransmits Frame 3.
 Once the receiver successfully receives Frame 3, it sends ACK 3 to indicate the successful
receipt.

Advantages of Stop-and-Wait ARQ:

 Simple to implement and understand.

 Ensures reliable communication over unreliable channels.
Disadvantages of Stop-and-Wait ARQ:

 Inefficient for high-speed or long-distance communication because the sender must wait for
an ACK before sending the next frame, leading to idle periods.
 The transmission rate is limited by the round-trip delay between the sender and receiver.

Go-back-n ARQ

The Go-Back-N ARQ (Automatic Repeat Request) protocol is an error control mechanism
used in data communication to ensure reliable data transmission over an unreliable or noisy
channel. It is a type of Sliding Window Protocol, where the sender can send multiple frames
before needing an acknowledgment, but the receiver only acknowledges the last correctly
received frame. If a frame is lost or corrupted, all subsequent frames need to be retransmitted,
which helps in maintaining the integrity of the data stream.

How Go-Back-N ARQ Works:

1. Multiple Frames Sent: The sender can send N frames before waiting for an
acknowledgment. This allows the sender to utilize the available bandwidth efficiently by
transmitting several frames in parallel, reducing the idle time during communication.
2. Acknowledgment: The receiver sends an acknowledgment (ACK) for the last correctly
received frame. This allows the sender to track the progress of transmission and understand
which frames need to be retransmitted if any errors are detected.
3. Retransmission: If any frame is lost or contains an error, the receiver will discard it and all
subsequent frames. The sender will then retransmit the lost frame and all the frames that
follow, ensuring that the receiver gets the correct sequence of data.

Go-Back-N ARQ Diagram:

mathematica
Copy code
Sender Receiver
| |
|------------ Frame 0 ----------------->| (Send Frame 0)
|------------ Frame 1 ----------------->| (Send Frame 1)
|------------ Frame 2 ----------------->| (Send Frame 2)
|------------ Frame 3 ----------------->| (Send Frame 3)
| |
|<----------- ACK 3 -------------------| (Receiver sends ACK 3 -
Acknowledges Frame 3)
| |
|------------ Frame 4 ----------------->| (Send Frame 4)
|------------ Frame 5 ----------------->| (Send Frame 5)
| |
|<----------- NAK 2 -------------------| (Receiver detects error, sends
NAK for Frame 2)
| |
|------------ Frame 2 ----------------->| (Sender retransmits Frame 2)
|------------ Frame 3 ----------------->| (Sender retransmits Frame 3)
|------------ Frame 4 ----------------->| (Sender retransmits Frame 4)
| |
 |<----------- ACK 4 -------------------| (Receiver sends ACK 4 -
Acknowledges Frame 4)
| |

Key Points:

 Sliding Window: The sender can send multiple frames (N frames) without waiting
for each acknowledgment. This sliding window mechanism ensures efficient use of
the communication link while keeping track of the transmission process.
 Retransmission: If any frame is lost or corrupted, all subsequent frames (from the
lost/corrupted frame onward) are retransmitted, even if they were sent correctly the
first time. This ensures that the receiver gets all frames in the correct order without
skipping any.

Advantages of Go-Back-N ARQ:

 Efficiency: More efficient than Stop-and-Wait ARQ because multiple frames can be sent
without waiting for each acknowledgment. This allows the sender to maintain a continuous
flow of data without waiting for each individual acknowledgment.
 Error Control: Handles errors and ensures that the receiver gets the correct data, even in the
presence of errors or packet loss. This is crucial in networks with high error rates, such as
wireless communication systems.

Disadvantages of Go-Back-N ARQ:

 Retransmission Overhead: If an error occurs in one frame, the sender must retransmit not
only the erroneous frame but all subsequent frames as well, leading to inefficiencies in high-
error environments. This retransmission overhead can significantly increase the time
required to complete data transmission.
 Receiver Load: The receiver has to process frames in order and discard any out-of-order
frames. If multiple frames are retransmitted, the receiver may need to process a large
number of frames in a short amount of time, which can increase the load on the receive

Point - to - Point Protocol (PPP) is a communication protocol of the data link layer that is
used to transmit multiprotocol data between two directly connected (point-to-point)
computers. It is a byte - oriented protocol that is widely used in broadband communications
having heavy loads and high speeds. Since it is a data link layer protocol, data is transmitted
in frames. It is also known as RFC 1661.

Services Provided by PPP

The main services provided by Point-to-Point Protocol are −

 Defining the frame format of the data to be transmitted.
 Defining the procedure of establishing link between two points and exchange of data.
 Stating the method of encapsulation of network layer data in the frame.
 Stating authentication rules of the communicating devices.
 Providing address for network communication.
 Providing connections over multiple links.
 Supporting a variety of network layer protocols by providing a range os services.

Components of PPP

Point - to - Point Protocol is a layered protocol having three components −

 Encapsulation Component − It encapsulates the datagram so that it

can be transmitted over the specified physical layer.
 Link Control Protocol (LCP) − It is responsible for establishing,
configuring, testing, maintaining and terminating links for transmission. It
also imparts negotiation for set up of options and use of features by the
two endpoints of the links.
 Authentication Protocols (AP) − These protocols authenticate
endpoints for use of services. The two authentication protocols of PPP are
−
o Password Authentication Protocol (PAP)
o Challenge Handshake Authentication Protocol (CHAP)
 Network Control Protocols (NCPs) − These protocols are used for
negotiating the parameters and facilities for the network layer. For every
higher-layer protocol supported by PPP, one NCP is there. Some of the
NCPs of PPP are −
o Internet Protocol Control Protocol (IPCP)
o OSI Network Layer Control Protocol (OSINLCP)
o Internetwork Packet Exchange Control Protocol (IPXCP)
o DECnet Phase IV Control Protocol (DNCP)
o NetBIOS Frames Control Protocol (NBFCP)
o IPv6 Control Protocol (IPV6CP)
 Explore our latest online courses and learn new skills at your own pace.
Enroll and become a certified expert to boost your career.

PPP Frame
PPP is a byte - oriented protocol where each field of the frame is
composed of one or more bytes. The fields of a PPP frame are −

 Flag − 1 byte that marks the beginning and the end of the frame. The bit
pattern of the flag is 01111110.
 Address − 1 byte which is set to 11111111 in case of broadcast.
 Control − 1 byte set to a constant value of 11000000.
 Protocol − 1 or 2 bytes that define the type of data contained in the
payload field.
 Payload − This carries the data from the network layer. The maximum
length of the payload field is 1500 bytes. However, this may be negotiated
between the endpoints of communication.
 FCS − It is a 2 byte or 4 bytes frame check sequence for error detection.
The standard code used is CRC (cyclic redundancy code)