Error and Flow Control in Data Link Layer (DLL)

Any ideal network must be able to guarantee the error-free transmission of data to the destination host in DLL.  For most of the applications, a system must guarantee that the data received is identical to the data transmitted. There are many factors that eventually alter the data and can corrupt the transmitted bits.

Data can be corrupted during transmission. Some applications generally require that the errors be detected and corrected . Some applications can tolerate a small fraction of error. For instance, random errors in audio or video transmissions may be tolerable but the same is not acceptable in case of a text message.

Let us first understand the type of errors that may get introduced during transmission :

Single-Bit Error : The term single-bit error means that only 1 bit of a given data unit (such as a byte, character, or packet) is changed from 1 to 0 or from 0 to 1.

Burst Error : The term burst error simply means that 2 or more bits in the data unit have changed from 1 to 0 or from 0 to 1. For example,  0100010001000011 was sent, but 0101110101100011 was received. Note that any burst error does not necessarily mean that the errors occur in consecutive bits.

Process of Error control in DLL

The process starts with the receiver sends back some feedback (positive or negative) to convey the information about whether it has received a frame or not.

A positive acknowledgement (feedback) ACK indicates successful and error-free delivery of a frame. Whereas a negative acknowledgement (NAK) means that something has gone wrong and that particular frame needs to be retransmitted.

Due to the presence of noise burst a frame may vanish completely. So the receiver does not receive anything and it does not react at all (no acknowledgement).

This problem is overcome by, introducing a timer in the data link layer. Its function of this timer is as follows.

Error Detection and Correction in DLL

When the transmission of digital signals takes place between two systems such as computers, the signal may get contaminated due to the addition of “Noise” to it . The noise can introduce an error in the binary bits travelling from one system to the other. That means a 0 may change to 1 or a 1 may change to 0.

The correction of errors is simply more difficult than detection. In error detection, we are looking only to see if there is an error . The answer is a simple yes or no. The main concept in detecting or correcting errors is redundancy. In order to detect or correct errors, we need to send some extra bits with our data.

In error correction, we have to know the exact number of bits that are corrupted and more importantly, their exact location in the message. The number of errors and the size of the message is important factors.

Forward Error Correction (FEC) Versus Retransmission in DLL

There are two main methods of error correction. Forward error correction is basically the process in which the receiver tries to guess the message by using redundant bits. This is possible, if the number of errors is small.

Correction by retransmission is a technique in which the receiver initially detects the occurrence of an error and asks the sender to resend the message. Resending of data happen until a message arrives that the receiver believes is error-free (usually, not all errors can be detected).

Checksum for error detection

As each word is transmitted, it is added to the previously sent word and the sum is retained at the transmitter. The final carry is ignored.Each successive word is added in this manner to the previous sum. At the end of the transmission, the sum (called a checksum) up to that time is transmitted.

The errors normally occur in a burst. The parity check method is not useful in detecting the errors under such conditions. The checksum error detection method can be used successfully in detecting such errors.

In this method, a “checksum” is transmitted along with every block of data bytes. In this method, an eight-bit accumulator is used to add 8-bit bytes of a block of data to find the”checksum byte”. Hence the carries of the MSB (most significant bit) are ignored while finding out the checksum byte.

Cyclic Redundancy Check (CRC)

This is a type of polynomial code in which a bit string is represented in the form of polynomials with coefficients of only 0 and 1 .  Polynomial arithmetic uses a modulo-2 arithmetic i.e. addition and subtraction are identical to EXOR.

For CRC code the sender and receiver should agree upon a generator polynomial i.e. G(x). A codeword can be generated for a given data word (message) polynomial M(x) with the help of long division.

CRC works on the principle of binary division. A sequence of redundant bits called CRC or CRC remainder is appended at the end of the message. We will call this word as appended message word.

At the receiver, this codeword is divided by the same generator word which corresponds to G (x). There is no error if the remainder of this division is zero. But a non-zero remainder indicates the presence of errors in the received codeword.

Error Correction Methods in DLL

In the error correction techniques, codes are generated at the transmitter by adding a group of parity bits or check bits . The source generates the data (message) in the form of binary symbols. The encoder accepts these bits and adds the check (parity) bits to them to produce the code words.

These codewords are transmitted towards the receiver. The check bits are used by the decoder to detect and correct the errors. Let us now see two error correction techniques  (approaches) :

1. Forward error correction (FEC) 

In FEC the receiver searches for the most likely correct code word. When any error is detected, the distance between the received invalid codeword and all the possible valid codewords is obtained.The nearest valid codeword (the one having minimum distance) is the most likely be the correct version of the received codeword.

Let us see the FEC methods now : 

       2. Linear block codes : To generate an (n, k) block code, the encoder accepts the information in the form of block of successive “k” bits . At the end of each such block (of k message bits) it adds (n – k) parity bits, As these bits do not contain any information, they are called as “redundant” bits. 

These codes have an important property that any two codewords of a linear code can be added in a modulo-2 adder to produce a third codeword in the code. Non-linear codes do not exhibit such a property. All the practically used codes are linear codes.

In any linear block code, the exclusive OR (XOR) of any two valid codewords creates another valid codeword . 

        3. Hamming Codes :  Hamming code is basically a linear block code-named after its inventor. One of the central concepts present in coding for error control is the idea of the Hamming distance. It is an error-correcting code. The parity bits are inserted in between the data bits . 

The 7 – bit Hamming code is used commonly, but the concept can be extended to any number of bits. The Hamming distance between any two words (of the same size) is the number of differences between the corresponding bits. We show the Hamming distance between two words x and y as d(x, y). 

When any codeword is corrupted during transmission, the Hamming distance between the sent and received codewords is the number of bits affected by the error. In other words, the Hamming distance between the received codeword and the sent codeword is the number of bits that are corrupted during transmission.

To guarantee the detection of up to ‘s’ errors in all cases, the minimum Hamming distance in a block code must be D(min) =  s + 1

        4. Cyclic codes : Cyclic codes are special linear block codes with one extra property. In a cyclic code, if any code word is cyclically shifted (rotated), the result is another codeword .  For example, if let say 1011000 is a codeword and cyclically left-shift, then 0110001 is also a codeword. We have already discussed the CRC method above. Please refer that.

Cyclic codes basically have a very good performance in detecting single-bit errors, double errors, an odd number of errors, and burst errors. They can easily be implemented in hardware and software. They are especially fast when implemented in hardware. 

ARQ Technique of Error Detection (automatic repeat request)

In the ARQ system of error control, when an error is detected, a request is made for the retransmission of that signal. Therefore a feedback channel is required for sending the request for retransmission.

In ARQ system less number of check bits (parity bits) are required to be sent. This will increase the ratio for an (n,k) block code if transmitted using the ARQ system. A return transmission path and additional hardware in order to implement repeat transmission of codewords will be needed.

The bit rate of forwarding transmission must make allowance for the backward repeat transmission.The bit rate of the return transmission which involves the return transmission of ACK/NAK signal is low as compared to the bit rate of the forward transmission. Therefore the error probability of the return transmission is negligibly small.

In order to detect and correct corrupted frames, we need to add redundancy bits to our data frame. Error correction in ARQ is done by keeping a copy of the sent frame and retransmitting of the frame when the timer expires. 

In the next post we will see the different types of ARQ techniques in detail . So stay tuned.