2 of 32

Data Link Layer

In the OSI model, the data link layer is a 4th layer from the top and 2nd layer from the bottom.
The communication channel that connects the adjacent nodes is known as links, and in order to move the datagram from source to the destination, the datagram must be moved across an individual link.
The main responsibility of the Data Link Layer is to transfer the datagram across an individual link.
The Data link layer protocol defines the format of the packet exchanged across the nodes as well as the actions such as Error detection, retransmission, flow control, and random access.
The Data Link Layer protocols are Ethernet, token ring, FDDI and PPP.
An important characteristic of a Data Link Layer is that datagram can be handled by different link layer protocols on different links in a path. For example, the datagram is handled by Ethernet on the first link, PPP on the second link.

3 of 32

Services provided by the Data Link Layer

4 of 32

Services provided by the Data Link Layer

Framing & Link access: Data Link Layer protocols encapsulate each network frame within a Link layer frame before the transmission across the link. A frame consists of a data field in which network layer datagram is inserted and a number of data fields. It specifies the structure of the frame as well as a channel access protocol by which frame is to be transmitted over the link.

Reliable delivery: Data Link Layer provides a reliable delivery service, i.e., transmits the network layer datagram without any error. A reliable delivery service is accomplished with transmissions and acknowledgements. A data link layer mainly provides the reliable delivery service over the links as they have higher error rates and they can be corrected locally, link at which an error occurs rather than forcing to retransmit the data.

Error detection: Errors can be introduced by signal attenuation and noise. Data Link Layer protocol provides a mechanism to detect one or more errors. This is achieved by adding error detection bits in the frame and then receiving node can perform an error check.

5 of 32

Services provided by the Data Link Layer

Flow control: A receiving node can receive the frames at a faster rate than it can process the frame. Without flow control, the receiver's buffer can overflow, and frames can get lost. To overcome this problem, the data link layer uses the flow control to prevent the sending node on one side of the link from overwhelming the receiving node on another side of the link.

Error correction: Error correction is similar to the Error detection, except that receiving node not only detect the errors but also determine where the errors have occurred in the frame.

Half-Duplex & Full-Duplex: In a Full-Duplex mode, both the nodes can transmit the data at the same time. In a Half-Duplex mode, only one node can transmit the data at the same time.

6 of 32

Error Detection

When data is transmitted from one device to another device, the system does not guarantee whether the data received by the device is identical to the data transmitted by another device. An Error is a situation when the message received at the receiver end is not identical to the message transmitted.

7 of 32

Error Detecting Techniques:

The most popular Error Detecting Techniques are:

Single parity check
Two-dimensional parity check
Checksum
Cyclic redundancy check
AD

8 of 32

Single Parity Check

Single Parity checking is the simple mechanism and inexpensive to detect the errors.
In this technique, a redundant bit is also known as a parity bit which is appended at the end of the data unit so that the number of 1s becomes even. Therefore, the total number of transmitted bits would be 9 bits.
If the number of 1s bits is odd, then parity bit 1 is appended and if the number of 1s bits is even, then parity bit 0 is appended at the end of the data unit.
At the receiving end, the parity bit is calculated from the received data bits and compared with the received parity bit.
This technique generates the total number of 1s even, so it is known as even-parity checking.

9 of 32

Single Parity Check

10 of 32

Checksum

A Checksum is an error detection technique based on the concept of redundancy.

It is divided into two parts:

Checksum Generator
Checksum Checker

11 of 32

Checksum Generator

A Checksum is generated at the sending side.

Checksum generator subdivides the data into equal segments of n bits each, and all these segments are added together by using one's complement arithmetic.

The sum is complemented and appended to the original data, known as checksum field. The extended data is transmitted across the network.

Suppose L is the total sum of the data segments, then the checksum would be ?L

12 of 32

Checksum Generator

A Checksum is generated at the sending side.
The Sender follows the given steps:
The block unit is divided into k sections, and each of n bits.
All the k sections are added together by using one's complement to get the sum.
The sum is complemented and it becomes the checksum field.
The original data and checksum field are sent across the network.

13 of 32

Checksum Checker

A Checksum is verified at the receiving side. The receiver subdivides the incoming data into equal segments of n bits each, and all these segments are added together, and then this sum is complemented. If the complement of the sum is zero, then the data is accepted otherwise data is rejected.

The Receiver follows the given steps:
The block unit is divided into k sections and each of n bits.
All the k sections are added together by using one's complement algorithm to get the sum.
The sum is complemented.
If the result of the sum is zero, then the data is accepted otherwise the data is discarded.

14 of 32

Checksum Example

Consider the data unit to be transmitted is-

10011001111000100010010010000100

Consider 8 bit checksum is used.

15 of 32

Checksum Example

At sender side,

The given data unit is divided into segments of 8 bits as-

Now, all the segments are added and the result is obtained as-

10011001 + 11100010 + 00100100 + 10000100 = 1000100011
Since the result consists of 10 bits, so extra 2 bits are wrapped around.
00100011 + 10 = 00100101 (8 bits)
Now, 1’s complement is taken which is 11011010.
Thus, checksum value = 11011010

16 of 32

Checksum Example

The data along with the checksum value is transmitted to the receiver.
At receiver side,

The received data unit is divided into segments of 8 bits.
All the segments along with the checksum value are added.
Sum of all segments + Checksum value = 00100101 + 11011010 = 11111111
Complemented value = 00000000
Since the result is 0, receiver assumes no error occurred in the data and therefore accepts it.

17 of 32

Cyclic Redundancy Check (CRC)

In CRC technique, a string of n 0s is appended to the data unit, and this n number is less than the number of bits in a predetermined number, known as division which is n+1 bits.

Secondly, the newly extended data is divided by a divisor using a process is known as binary division. The remainder generated from this division is known as CRC remainder.

Thirdly, the CRC remainder replaces the appended 0s at the end of the original data. This newly generated unit is sent to the receiver.

18 of 32

Cyclic Redundancy Check (CRC)

The receiver receives the data followed by the CRC remainder. The receiver will treat this whole unit as a single unit, and it is divided by the same divisor that was used to find the CRC remainder.

If the resultant of this division is zero which means that it has no error, and the data is accepted.

If the resultant of this division is not zero which means that the data consists of an error. Therefore, the data is discarded.

19 of 32

CRC Generator

Suppose the original data is 11100 and divisor is 1001.
A CRC generator uses a modulo-2 division. Firstly, three zeroes are appended at the end of the data as the length of the divisor is 4 and we know that the length of the string 0s to be appended is always one less than the length of the divisor.
Now, the string becomes 11100000, and the resultant string is divided by the divisor 1001.
The remainder generated from the binary division is known as CRC remainder. The generated value of the CRC remainder is 111.
CRC remainder replaces the appended string of 0s at the end of the data unit, and the final string would be 11100111 which is sent across the network.

20 of 32

CRC Checker

The functionality of the CRC checker is similar to the CRC generator.
When the string 11100111 is received at the receiving end, then CRC checker performs the modulo-2 division.
A string is divided by the same divisor, i.e., 1001.
In this case, CRC checker generates the remainder of zero. Therefore, the data is accepted.

21 of 32

Error Correction

Error Correction codes are used to detect and correct the errors when data is transmitted from the sender to the receiver.

Error Correction can be handled in two ways:

Backward error correction: Once the error is discovered, the receiver requests the sender to retransmit the entire data unit.
Forward error correction: In this case, the receiver uses the error-correcting code which automatically corrects the errors.
A single additional bit can detect the error, but cannot correct it.

22 of 32

Error Correction

For correcting the errors, one has to know the exact position of the error. For example, If we want to calculate a single-bit error, the error correction code will determine which one of seven bits is in error. To achieve this, we have to add some additional redundant bits.

Suppose r is the number of redundant bits and d is the total number of the data bits. The number of redundant bits r can be calculated by using the formula:

2^r>=d+r+1

The value of r is calculated by using the above formula. For example, if the value of d is 4, then the possible smallest value that satisfies the above relation would be 3.

23 of 32

Hamming Code

Parity bits: The bit which is appended to the original data of binary bits so that the total number of 1s is even or odd.

Even parity: To check for even parity, if the total number of 1s is even, then the value of the parity bit is 0. If the total number of 1s occurrences is odd, then the value of the parity bit is 1.

Odd Parity: To check for odd parity, if the total number of 1s is even, then the value of parity bit is 1. If the total number of 1s is odd, then the value of parity bit is 0.

24 of 32

Algorithm of Hamming code

An information of 'd' bits are added to the redundant bits 'r' to form d+r.

The location of each of the (d+r) digits is assigned a decimal value.

The 'r' bits are placed in the positions 1,2,.....2^k-1.

At the receiving end, the parity bits are recalculated. The decimal value of the parity bits determines the position of an error.

25 of 32

Relationship b/w Error position & binary number

26 of 32

Example of Hamming code

Suppose the original data is 1010 which is to be sent.

Total number of data bits 'd' = 4
Number of redundant bits r : 2^r >= d+r+1

2^r>= 4+r+1

Therefore, the value of r is 3 that satisfies the above relation.
Total number of bits = d+r = 4+3 = 7;

27 of 32

Determining the position of the redundant bits

The number of redundant bits is 3. The three bits are represented by r1, r2, r4. The position of the redundant bits is calculated with corresponds to the raised power of 2. Therefore, their corresponding positions are 1, 2¹, 2².

The position of r₁ = P₃,P₅,P₇
The position of r₂ = P₃,P₆,P₇
The position of r₄ = P₅,P₆,P₇
Representation of Data on the addition of parity bits:

28 of 32

Determining the Parity bits

Determining the r₁ bit
The r1 bit is calculated by performing a parity check on the bit positions whose binary representation includes 1 in the first position.

We observe from the above figure that the bit positions that includes 1 in the first position are 1, 3, 5, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at these bit positions corresponding to r₁ is even, therefore, the value of the r1 bit is 0.

29 of 32

Determining the Parity bits

Determining r₂ bit
The r2 bit is calculated by performing a parity check on the bit positions whose binary representation includes 1 in the second position.

We observe from the above figure that the bit positions that includes 1 in the second position are 2, 3, 6, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at these bit positions corresponding to r₂ is odd, therefore, the value of the r2 bit is 1.

30 of 32

Determining the Parity bits

Determining r₄ bit
The r4 bit is calculated by performing a parity check on the bit positions whose binary representation includes 1 in the third position.

We observe from the above figure that the bit positions that includes 1 in the third position are 4, 5, 6, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at these bit positions corresponding to r₄ is even, therefore, the value of the r4 bit is 0.

31 of 32

Determining the Parity bits

Data transferred is given below:

Suppose the 4th bit is changed from 0 to 1 at the receiving end, then parity bits are recalculated.

32 of 32

Thanks!

Any questions?

You can find me at:

minhazularefin21@gmail.com