Error Control in Data Link layer

Error Control 

Error control in data link layer is the process of detecting and correcting data frames that have been corrupted or lost during transmission.

In case of lost or corrupted frames, the receiver does not receive the correct data-frame and sender is ignorant about the loss. Data link layer follows a technique to detect transit errors and take necessary actions, which is re-transmission of frames whenever error is detected or frame is lost. The process is called Automatic Repeat Request (ARQ).

Error control can be done in two ways.

1. Error Detection : Error detection involves checking whether any error has occurred or not.The number of error bits and the type of error does not matter.

2. Error Correction : Error correction involves finding or calculating the exact number of bit's that has been corrupted and the location of the corrupted bit's. 

For both Error detection and Error correction, the sender needs to send some additional bits along with the data bits.

The receiver performs necessary checks based upon the additional redundant bits. If it finds that the data is free from errors, it removes the redundant bits before passing the message to the upper layer.

Error Detection Techniques

There are four main techniques for detecting errors in frames namely Parity Check, Checksum, CRC and LRC.

1. Parity Check

The parity check is done by adding an extra bit, called Parity bit to the data to make a number of 1's either even in case of even parity or odd in case of odd parity.

Parity check also known as "Vertical Redundancy Check"(VRC). In this method, a redundant bit also called parity bit is added to each data unit.

This method include even parity and odd parity.Even parity means the total number of 1's in data is to be even and odd parity means the total  number of 1's in data is to be odd.

While creating a frame, the sender counts the number of 1's in it and adds the parity bit in the following way

• In case of even parity: If a number of 1's is even then parity bit value is 0. If the number of 1's is odd then parity bit value is 1.

• In case of odd parity: If a number of 1's is odd then parity bit value is 0. If a number of 1's is even then parity bit value is 1.

On receiving a frame, the receiver counts the number of 1's in it. In case of even parity check, if the count of 1's is even, the frame is accepted, otherwise, it is rejected. A similar rule is adopted for odd parity check.

The parity check is suitable for single bit error detection only.

Example: If the source wants to transmit data unit 1100111 using even parity to the destination. the source will have to pass through even parity generator.

The scheme makes the total number of 1's even that's why it's called even parity checking.

2. Checksum

In Checksum Error Detection scheme, the data is divided into k segments each of m bits.

At the sender's end the segments are added using 1's compliment arithmetic to get the sum. The sum is complemented to get the checksum.

The checksum segment is sent along with the data segments to the receiver.

At the receiver's end all received segments (included checksum) are added using 1's complement arithmetic to get the sum. The sum is complemented again. 

If the result is 0, the received data is accepted otherwise discarded( rejected).

3. CRC

CRC stands for Cyclic redundancy Check. Unlike checksum scheme, which is based on addition, CRC is based on binary division.

In CRC, a sequence of redundant bits, are appended to the end of the data unit so that the resulting data unit becomes exactly divisible by a second, predetermined binary number.

At the destination, the incoming data unit is divided by then same number. If at this step there is no reminder, the data unit is assumed to be correct and is therefore accepted.

A reminder indicates that the data unit has been changed in transit and therefore must be rejected.

Example : Original Message - 1010000 and 

                  Generator polynomial -x^3 +1 (1.x^3+ 0.x^2+0.X^1+1.x^0)

                  According to polynomial the CRC Generator will be 1001.

If CRC generator is of n bits then append (n-1) zeros in the end of original message.

4. LRC

LRC stands for Longitudinal Redundancy Check. It is also called two dimensional parity check.In this method , data which the user wants to send is organized in the form of rows and columns.In order to detect an error, a redundant bit is added to the whole block and this block is sent to the receiver along with the data.

At the receiver's end these are compared with the parity bits calculated on the received data.After checking data for errors, receiver accepts the data and discards the redundant row of bits.

Example : If a block of 32 bits is to be transmitted, it is divided into matrix of four rows and eight columns.

In this matrix of bits, a parity bit (odd or even) is calculated for each column. It means 32 bits data plus 8 redundant bits are transmitted to the receiver. Whenever data reaches at the destination, receiver uses LRC to detect an error in data.

Advantage : LRC is used to detect burst errors.

Example : Suppose 32 bit data plus LRC that was being transmitted is hit by burst error of length 5 and some bits are corrupted.

The LRC received by the destination does not match with newly corrupted LRC. The destination comes to know that the data is erroneous,so it discards the data.

Note : The main problem with LRC is that,if two bits in one data units are damaged and two bits in exactly the same position in another data unit are also damaged, then the LRC will not able to detect the error.