Computer Networks_22CS008

Data Link Layer

Lecture (40-42)
Prepared By Dr. Chetna

Department of Computer Science and Engineering,

Chitkara University, Punjab
Index

1. Types of Errors
2. Redundancy
3. Error Detection
4. Error Correction
Types of Errors

Errors are introduced into the binary data transmitted from the sender to the
receiver due to noise during transmission. The error can be a single-bit error, multi-
bit error, or burst error. Error detection methods are used to check whether the
receiver has received correct data or corrupted data. And error correction is used to
correct the detected errors during the transmission of data from sender to receiver.

■ Single bit error :-

Only one bit in the data unit has changed.

■ Multiple bit error :-

When more than one bits are corrupted.

■ Burst error :-
It means that two or more bits in the data unit has changed.
Single Bit Error

The following figure shows the Single bit error

Figure 1 Single-bit error

Basic concepts

 Networks must be able to transfer data from one device to another with complete
accuracy.
 Data can be corrupted during transmission.
 For reliable communication, errors must be detected and corrected.
 Error detection and correction are implemented either at the data link layer or the
transport layer of the OSI model.
• Single bit errors are the least likely type of errors in serial data transmission
because the noise must have a very short duration which is very rare. However, this
kind of errors can happen in parallel transmission.

Example:

★ If data is sent at 1Mbps then each bit lasts only 1/1,000,000 sec. or 1μs.
★ For a single-bit error to occur, the noise must have a duration of only 1 μs, which is
very rare.
Burst Error

The following figure shows the Burst error

Figure 2 Burst error

Burst Error( cont..)

Figure 3 Two errors

The term burst error means that two or more bits in the data unit have changed from 1
to 0 or from 0 to 1. Burst errors does not necessarily mean that the errors occur in
consecutive bits, the length of the burst is measured from the first corrupted bit to the
last corrupted bit.
Burst Error( cont..)
Burst error is most likely to happen in serial transmission since the duration of noise is
normally longer than the duration of a bit.

 The number of bits affected depends on the data rate and duration of noise.
Example:
 If data is sent at rate = 1Kbps then a noise of 1/100 sec can affect 10 bits.(1/100*1000)
 If same data is sent at rate = 1Mbps then a noise of 1/100 sec can affect 10,000 bits.
(1/100*106)
Error detection

Error detection means to decide whether the received data is correct or not
without having a copy of the original message.

Error detection uses the concept of redundancy, which means adding extra
bits for detecting errors at the destination.
Redundancy

■ Instead of repeating the entire data stream, a shorter group of bits may be
appended to the end of each unit.

■ This technique is called Redundancy because the extra bit are redundant to the
information. They are discarded as soon as the accuracy of the transmission has
been determined.

There are basically four types of redundancy checks. They are:

1. 1. VRC (Vertical Redundancy Check).

2. 2. LRC (Longitudinal Redundancy Check).
3. 3. CRC (Cyclical Redundancy Check).
4. 4. Checksum
Redundancy Checks

Figure 4 Redundancy Example

Redundancy Checks

Four types of redundancy checks are used in data communications

Figure 5 Redundancy Checks

Vertical Redundancy Check

• It is also known as parity check

• It is least expensive mechanism for error detection
• In this technique, the redundant bit called parity bit is appended to every data unit
so that the total number of 1s in the unit becomes even (including parity bit)
Vertical Redundancy Check

1100001
Data
Checking function

1100001 | 1 Even – parity

Is total number generator
of 1s even
?
Receiver 1

Sender
Figure 6 Vertical Redundancy Check
Vertical Redundancy Check (VRC)

Figure 7 Vertical Redundancy Check

Parity Check

Note:

In parity check, a parity bit is added to

every data unit so that the total
number of 1s is even
(or odd for odd-parity).
Example 1
Suppose the sender wants to send the word world. In
ASCII the five characters are coded as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent
11101110 11011110 11100100 11011000 11001001
Example 2
Now suppose the word world in Example 1 is received by
the receiver without being corrupted in transmission.
11101110 11011110 11100100 11011000 11001001
The receiver counts the 1s in each character and comes up
with even numbers (6, 6, 4, 4, 3). The data are accepted.
Example 3
Now suppose the word world in Example 1 is corrupted
during transmission.
11111110 11011110 11101100 11011000 11001001
The receiver counts the 1s in each character and comes up
with even and odd numbers (7, 6, 5, 4, 4). The receiver
knows that the data are corrupted, discards them, and asks
for retransmission.
LONGITUDINAL REDUNDANCY CHECK
LRC

11100111 11011101 00111001 10101001

10101001
00111001
11011101
11100111

LRC 10101010

11100111 11011101 00111001 10101001 10101010

Data plus LRC

Figure 8 Longitudinal Redundancy Check

Two-dimensional parity

Figure 9 Two-dimensional parity-check code

CRC generator and checker

Figure 10 CRC generator and checker

Sender’s steps

Note:

The sender follows these steps:

The unit is divided into k sections, each of n bits.

All sections are added using one’s complement to get

the sum.
The sum is complemented and becomes the checksum.

The checksum is sent with the data.

Receiver’s steps

Note:

The receiver follows these steps:

The unit is divided into k sections, each of n bits.

All sections are added using one’s complement to

get the sum.
The sum is complemented.

If the result is zero, the data are accepted:

otherwise, rejected.
Example 4
Suppose the following block of 16 bits is to be sent using a
checksum of 8 bits.
10101001 00111001
The numbers are added using one’s complement
10101001
00111001
------------
Sum 11100010
Checksum 00011101
The pattern sent is 10101001 00111001 00011101
Example 5
Now suppose the receiver receives the pattern sent in Example 7
and there is no error.
10101001 00111001 00011101
When the receiver adds the three sections, it will get all 1s, which,
after complementing, is all 0s and shows that there is no error.
10101001
00111001
00011101
Sum 11111111
Complement 00000000 means that the pattern is OK.
Example 6
Now suppose there is a burst error of length 5 that affects 4 bits.
10101111 11111001 00011101
When the receiver adds the three sections, it gets
10101111
11111001
00011101
Partial Sum 1 11000101
Carry 1
Sum 11000110
Complement 00111001 the pattern is corrupted.
Correction

Retransmission

Forward Error Correction

Burst Error Correction

Difference between VRC and
LRC
Sr.No. Vertical Redundancy Check (VRC) Longitudinal Redundancy Check (LRC)
1. It stands for Vertical Redundancy Check. It stands for Longitudinal Redundancy Check.

2. In this redundant bit called parity bit is added to each In this redundant row of bits is added to the
data unit. whole block.

3. VRC can detect single bit errors. LRC can detect burst errors.
4. It is also known as parity checker. It is also known as 2-D parity checker.

5. The advantage of using VRC is that it can checks all The advantage of using LRC over VRC is that it
single bit errors but can check odd parity only in the can check all the burst errors.
case of change of odd bits.

6. It is not capable of checking the burst error in case of If two bits in data unit is damaged and also in
change of bits is even. other data unit the same bits are damaged at
same position, then it is not capable of detecting
such kind of error.
Hamming Code
Data and redundancy bits

Number of Number of Total

data bits redundancy bits bits
m r m+r
1 2 3
2 3 5
3 3 6

4 3 7

5 4 9

6 4 10

7 4 11

r
2 m  r  1
Positions of redundancy bits in Hamming code

3 2 1 0
2 ,2 ,2 ,2
Redundancy bits calculation

Figure 11 Example of Redundancy Bit Calculation

Example of redundancy bit calculation

Figure 12 Example of Redundancy Bit Calculation

Error detection using Hamming code

Figure 13 Example of Hamming Code

Burst error correction Example

Figure 14 Burst Error Correction Example

Multiple Choice Questions
What identifier is used at the data link layer to uniquely identify an Ethernet
device?
1.IP address
2.MAC address
3.sequence number
4.TCP port number
5.UDP port number
What attribute of a NIC would place it at the data link layer of the OSI model?
6.attached Ethernet cable
7.IP address
8.MAC address
9.RJ-45 port
10.TCP/IP protocol stack
A technician has been asked to develop a physical topology for a network that
provides a high level of redundancy. Which physical topology requires that every
node is attached to every other node on the network?
11.bus
12.star
13.hierarchical
14.mesh
15.ring
Multiple Choice Questions
Which two engineering organizations define open standards and protocols that
apply to the data link layer? (Choose two.)
1. International Organization for Standardization (ISO)
2. Internet Assigned Numbers Authority (IANA)
3. International Telecommunication Union (ITU)
4. Electronic Industries Alliance (EIA)
5. Internet Society (ISOC)
What is true concerning physical and logical topologies?
6. Physical topologies are concerned with how a network transfers frames.
7. The logical topology is always the same as the physical topology.
8. Physical topologies display the IP addressing scheme of each network.
9. Logical topologies refer to how a network transfers data between devices.
What method is used to manage contention-based access on a wireless network?
10.token passing
11.CSMA/CA
12.priority ordering
13.CSMA/CD
Practice Questions

• https://www.netacad.com/portal/learning
• https://pinoybix.org/2017/07/mcq-in-network-layer-internet-protocol-forouzan
.html
• https://edurev.in/course/quiz/attempt/-1_Test-Ipv4--IP-Packet/0decdb37-7206-
4824-afdd-d47013a5c4cd