UNIT-2

Data Link Layer and Medium Access Sub Layer:

Error Detection and Error Correction - Fundamentals,

• Block coding,
• Hamming Distance,
• CRC;

Flow Control and Error control protocols –

• Stop and Wait,
• Go back – N ARQ,
• Selective Repeat ARQ,
• Sliding Window,
• Piggybacking,
• Random Access,

Multiple access protocols –

• Pure ALOHA,
• Slotted ALOHA,
• CSMA/CD,
• CDMA/CA

Error Detection and Error Correction - Fundamentals,�

• Data can be corrupted during transmission. Some applications require that errors be detected and corrected.
• Error is a condition when the receiver’s information does not match the sender’s.

Types of Errors:

• Errors can be of three types, namely single bit errors, multiple bit errors, and burst errors.

1.Single bit error

2. Burst error

3. Multiple bits error

​

1.Single bit error�

• Single bit error − In a single-bit error, only 1 bit in the data unit has changed.

​

​

2.Burst error 

• Burst error − A burst error means that 2 or more bits in the data unit have changed.
• In the received frame, more than one consecutive bits are corrupted.

​

​

3. Multiple bits error�

• Multiple bits error − In the received frame, more than one bits are corrupted.

​

​

Error Detection Methods�

​

To detect errors, a common technique is to introduce redundancy bits that provide additional information.

Various techniques for error detection include:

1. Simple(Single) Parity Check
2. Two-Dimensional Parity Check
3. Cyclic Redundancy Check (CRC)
4. Checksum

​

​

1.Single Parity Check�

• Single-bit parity is a single error detection method that involves adding an extra bit to a data transmission.

It works as:

• 1 is added to the block if it contains an odd number of 1’s, and
• 0 is added if it contains an even number of 1’s

​

2.Two-Dimensional Parity Check�

• Two-dimensional Parity check bits are calculated for each row, which is equivalent to a simple parity check bit.
• Parity check bits are also calculated for all columns, then both are sent along with the data.
• At the receiving end, these are compared with the parity bits calculated on the received data.

3.Cyclic Redundancy Check (CRC)�

• In CRC, a sequence of redundant bits, called cyclic redundancy check 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 the same number. If at this step there is no remainder, the data unit is assumed to be correct and is therefore accepted.
• A remainder indicates that the data unit has been damaged in transit and therefore must be rejected.

​

CRC Working:

We have given data word of length n and divisor of length k.

• Step 1: Append (k-1) zero’s to the original message
• Step 2: Perform modulo 2 division
• Step 3: Remainder of division = CRC
• Step 4: Code word = Data with append k-1 zero’s + CRC

​

4. Checksum�

• Checksum error detection is a method used to identify errors in transmitted data.
• The process involves dividing the data into equally sized segments and using a 1’s complement to calculate the sum of these segments.
• The calculated sum is then sent along with the data to the receiver.
• At the receiver’s end, the same process is repeated and if all zeroes are obtained in the sum, it means that the data is correct.

Checksum – Operation at Sender’s Side

1. the data is divided into k segments each of m bits.
2. On the sender’s end, the segments are added using 1’s complement arithmetic to get the sum. The sum is complemented to get the checksum.
3. The checksum segment is sent along with the data segments.

Checksum – Operation at Receiver’s Side

1. At the receiver’s end, all received segments are added using 1’s complement arithmetic to get the sum. The sum is complemented.
2. If the result is zero, the received data is accepted; otherwise discarded.

​

Example

Error Correction

• When the data is sent from the sender side to the receiver's side it needs to be detected and corrected. So an error correction method is used for this purpose.

Following are the two ways through which error correction can be handled:

Backward Error Correction:

• In this method, When any error is found in the data at the receiver's end. Then the request for resending the whole data unit is sent by the receiver.

Forward Error Correction:

• In this method, an error-correcting code is used by the receiver that automatically corrects the errors.

​

Error Correction Techniques�

• Hamming code:

​

Block coding

Flow Control and Error control protocols

• Stop and Wait
• Sliding Window
• Go back–N ARQ
• Selective Repeat ARQ
• Piggybacking

​

Simplest Protocol

• The simplest protocol is a data link layer protocol used for noiseless channels. It is also known as the Elementary Data Link Protocol.
• As the simplest protocol is used in noiseless channels, it has no error control and no flow control.
• In the simplest protocol, we assume that the receiver is always ready to handle any frames coming from the sender immediately.
• The simplest protocol is a unidirectional protocol in which the data frames travel in only one direction from the sender to the receiver.
• There is no acknowledgment (ACK). Also, as there is no data loss in the transmission, there is no need for data re-transmission.
• The processing time of the simplest protocol is very short, hence it can be neglected as the sender, and the receiver are always ready to send and receive data.
• In the simplest protocol, the sender is always ready to send data frames.

​

Simple Protocol

Stop and Wait

• It is a data-link layer protocol which is used for transmitting the data over the noiseless channels.
• It provides unidirectional data transmission which means that either sending or receiving of data will take place at a time.
• It provides flow-control mechanism but does not provide any error control mechanism.
• The idea behind the usage of this frame is that when the sender sends the frame then he waits for the acknowledgment before sending the next frame.

​

Stop and Wait

• Sender side:
• Rule 1: Sender sends one data packet at a time.
• Rule 2: Sender sends the next packet only when it receives the acknowledgment of the previous packet.
• Receiver side:
• Rule 1: Receive and then consume the data packet.
• Rule 2: When the data packet is consumed, receiver sends the acknowledgment to the sender.

​

Working of Stop and Wait protocol�

• The above figure shows the working of the stop and wait protocol.
• If there is a sender and receiver, then sender sends the packet and that packet is known as a data packet.
• The sender will not send the second packet without receiving the acknowledgment of the first packet.
• The receiver sends the acknowledgment for the data packet that it has received. Once the acknowledgment is received, the sender sends the next packet.
• This process continues until all the packet are not sent.

1. Lost Data 

• Sender waits for an infinite amount of time for an acknowledgment.
• Receiver waits for an infinite amount of time for a data.

2. Lost Acknowledgement�

• Sender waits for an infinite amount of time for an acknowledgment.

3. Delayed Acknowledgement/Data�

• Suppose the sender sends the data and it has also been received by the receiver.
• The receiver then sends the acknowledgment but the acknowledgment is received after the timeout period on the sender's side.
• As the acknowledgment is received late, so acknowledgment can be wrongly considered as the acknowledgment of some other data packet.

Sliding Window Protocol�

• The sliding window is a technique for sending multiple frames at a time.
• It controls the data packets between the two devices where reliable and gradual delivery of data frames is needed. It is also used in TCP (Transmission Control Protocol).
• In this technique, each frame has sent from the sequence number.
• The sequence numbers are used to find the missing data in the receiver end.
• The purpose of the sliding window technique is to avoid duplicate data, so it uses the sequence number.

• Let us suppose that the sender's window size is taken as 4. So, the sequence number of the data frame will be in the range of 00 to (2N−1)(2N−1) i.e. 0, 1, 2, 3, 0, 1, 2, 3, and so on.
• The steps of data transmission can be:
• The sender sends multiple frames.
• The receiver receives the frames and sends back an ACK.
• Again the sender sends the next frame.
• If the receiver does not send back an ACK in the specified time then the sender sends back the frame as the frame is either lost or damaged in the last transmission.
• This process is continued till all the frames have been received by the receiver.

​

Types of Sliding Window Protocol�

• Sliding window protocol has two types:
• Go-Back-N ARQ
• Selective Repeat ARQ

​

Go-Back-N ARQ�

• Go Back N ARQ is a sliding window protocol which is used for flow control purposes. Multiple frames present in a single window are sent together from sender to receiver.

Working of Go-Back-N ARQ Protocol:

1. Data packets are divided into multiple frames. Each frame contains information about the destination address, the error control mechanism it follows, etc. These multiple frames are numbered so that they can be distinguished from each other.

​

• 2. The integer 'N' in Go Back 'N' ARQ tells us the size of the window i.e. the number of frames that are sent at once from sender to receiver. Suppose the window size 'N' is equal to 4. Then, 4 frames (frame 0, frame 1, frame 2, and frame 3) will be sent first from sender to receiver.

• 3. The receiver sends the acknowledgment of frame 0. Then the sliding window moves by one and frame 4 is sent.

4. The receiver sends the acknowledgment of frame 1. Then the sliding window moves by one and frame 3 is sent

• 5. The sender waits for the acknowledgment for a fixed amount of time. If the sender does not get the acknowledgment for a frame in time, it considers the frame to be corrupted. Then the sliding window moves to the start of the corrupted frame and all the frames in the window are retransmitted.
• For example, if the sender does not receive the acknowledgment for frame 2, it retransmits all the frames in the windows i.e. frames [2, 3, 4, 5].

​

Characteristics of Go-Back-N ARQ�

Given below are the characteristics of the Go-Back-N ARQ protocol.

• The size of the sender window in Go Back N ARQ is equal to N.
• The size of the receiver window in Go Back N ARQ is equal to 1.
• When the acknowledgment for one frame is not received by the sender or the frames received by the receiver are out of order, then the whole window starting from the corrupted frame is retransmitted.
• Go-Back-N ARQ follows the principle of pipelining i.e. a frame can be sent by the sender before receiving the acknowledgment of the previously sent frame.

​

Selective Repeat ARQ�

• Selective-Repeat ARQ is a flow control protocol that allows the sender to transmit a number of frames without waiting for individual acknowledgments.
• If an acknowledgment is not received, only the specific frame(s) that were not acknowledged are resent.

The steps of data transmission can be:

• The sender sends frames 0 and 1.
• The receiver receives the frames and sends back ACK 0 and ACK 1.
• Again the sender sends the frames 2 and 3.
• The receiver only receives the frame 3. So it sends back NACK 2 which means that the 2nd frame is lost and needs to be re-transmitted.
• So, the sender sends back frame 2 and this process is continued till all the frames have been received by the receiver.

​