Unit-2

Data Link Layer (Layer 2)

Data Link Layer
Transmission Delay & Propagation Delay
IP, MAC & Port Address
❖ MAC Address is added with packet to from
frame
Error Detection
• Only the ability to detect an error but not correct them
• To fix an error, the receiver must request a retransmission

• Methods
• Parity Checking
• 2D parity Check
• Checksum
• Cyclic Redundancy Check (CRC)
Parity Checking
• Simple-bit parity is a simple 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
2D 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.
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
• Firstly, the data is divided into k segments each of m bits.
• 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.
• The checksum segment is sent along with the data segments.
Checksum (Cont’d)
• Checksum – Operation at Receiver’s Side
• At the receiver’s end, all received
segments are added using 1’s
complement arithmetic to get the
sum. The sum is complemented.
• If the result is zero, the received data
is accepted; otherwise discarded.
Cyclic Redundancy Check (CRC)
• Unlike the checksum scheme, which is based on addition, CRC is
based on binary division.
• 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
Cyclic Redundancy Check (CRC) (Cont’d)
• CRC Working
• We have given dataword 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

• Note:
• CRC must be k-1 bits
• Length of Codeword = n+k-1 bits
• Example: Let’s data to be send is 1010000 anthe d divisor in the form of polynomial
is x 3 +1. CRC method is discussed below.
Cyclic Redundancy Check (CRC) (Cont’d)

CRC Checksum
Cyclic Redundancy Check (CRC) (Cont’d)
Cyclic Redundancy Check (CRC) (Cont’d)
Error Correction
• In the digital world, error correction can be done in two ways:

• Backward Error Correction When the receiver detects an error in the data
received, it requests back the sender to retransmit the data unit.

• Forward Error Correction When the receiver detects some error in the data
received, it executes error-correcting code, which helps it to auto-recover and
correct some kinds of errors.
Hamming Code
Hamming Code (Cont’d)

Message bit k=4

𝟐𝒑 ≥ p+k+1
𝟐𝒑 ≥ p+5

If p=1 if p=2 if p=3

𝟐𝟏 ≥ 6 X 𝟐𝟐 ≥ 7 X 𝟐𝟑 ≥ 8 √

Minimum value of p = 3 bits

Hamming code (n,k) = (7,4)
Hamming Code (Cont’d)

𝒑𝟏 = 𝟐𝟎 = 1 p=n-k=7-4=3
𝒑𝟐 = 𝟐𝟏 = 2
𝒑𝟒 = 𝟐𝟐 = 4

How to calculate Parity bits 𝑫𝟕 𝑫𝟔 𝑫𝟓 𝒑𝟒 𝑫𝟑 𝒑𝟐 𝒑𝟏

For 𝒑𝟏 calculation, check 1 bit and skip 1 bit 𝒑𝟏 = 𝑫𝟑 ⊕𝑫𝟓 ⊕𝑫𝟕

Even
For 𝒑𝟐 calculation, check 2 bits and skip 2 bits 𝒑𝟐 = 𝑫𝟑 ⊕𝑫𝟔 ⊕𝑫𝟕 Parity
For 𝒑𝟒 calculation, check 4 bits and skip 4 bits 𝒑𝟒 = 𝑫𝟓 ⊕𝑫𝟔 ⊕𝑫𝟕
Message bit k = 5
𝟐𝒑 ≥ p+k+1
𝟐𝒑 ≥ p+6

If p=1 if p=2 if p=3 if p=4

𝟐𝟏 ≥ 7 X 𝟐𝟐 ≥ 8 X 𝟐𝟑 ≥ 9 X 𝟐𝟒 ≥ 10 √

Minimum value of p = 4 bits

Hamming code (n,k) = (9,5)

𝒑𝟏 = 𝟐𝟎 = 1 p = n - k = 9 - 5 = 4 bits
𝒑𝟐 = 𝟐𝟏 = 2
𝒑𝟒 = 𝟐𝟐 = 4
𝒑𝟖 = 𝟐𝟑 = 8
Bit Position

𝑫𝟗 𝒑𝟖 𝑫𝟕 𝑫𝟔 𝑫𝟓 𝒑𝟒 𝑫𝟑 𝒑𝟐 𝒑𝟏

Calculate Parity bits

For 𝒑𝟏 calculation, check 1 bit and skip 1 bit 𝒑𝟏 = 𝑫𝟑 ⊕𝑫𝟓 ⊕𝑫𝟕 ⊕𝑫𝟗 = 0
For 𝒑𝟐 calculation, check 2 bits and skip 2 bits 𝒑𝟐 = 𝑫𝟑 ⊕𝑫𝟔 ⊕𝑫𝟕 = 1
For 𝒑𝟒 calculation, check 4 bits and skip 4 bits 𝒑𝟒 = 𝑫𝟓 ⊕𝑫𝟔 ⊕𝑫𝟕 = 0
For 𝒑𝟖 calculation, check 8 bits and skip 8 bits 𝒑𝟖 = 𝑫𝟗 = 0

So Codeword is 001100110
0 0 1 1 0 1 1 1 0
𝑫𝟗 𝒑𝟖 𝑫𝟕 𝑫𝟔 𝑫𝟓 𝒑𝟒 𝑫𝟑 𝒑𝟐 𝒑𝟏

Calculate Parity bits

For 𝒑𝟏 calculation, check 1 bit and skip 1 bit 𝒑𝟏 = 𝑫𝟑 ⊕𝑫𝟓 ⊕𝑫𝟕 ⊕𝑫𝟗 = 0 √
For 𝒑𝟐 calculation, check 2 bits and skip 2 bits 𝒑𝟐 = 𝑫𝟑 ⊕𝑫𝟔 ⊕𝑫𝟕 = 1 √
For 𝒑𝟒 calculation, check 4 bits and skip 4 bits 𝒑𝟒 = 𝑫𝟓 ⊕𝑫𝟔 ⊕𝑫𝟕 = 0 X
For 𝒑𝟖 calculation, check 8 bits and skip 8 bits 𝒑𝟖 = 𝑫𝟗 = 0 √

𝒑𝟖 𝒑𝟒 𝒑𝟐 𝒑𝟏 = √ X √ √ = 0100 = 4
Error Syndrome 0 0 0 0 0 1 0 0 0

Received data 0 0 1 1 0 1 1 1 0
⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕

Corrected data 0 0 1 1 0 0 1 1 0
 Time required for one frame

T = 𝑻𝒕 +𝑻𝒑 +𝑻𝒑𝒓 +𝑻𝒕𝒂 +𝑻𝒑

Where
𝑻𝒕 = Transmission time
𝑻𝒑 = Propagation time
𝑻𝒑𝒓 = processing time of frame at receiver side
𝑻𝒕𝒂 = Transmission of acknowledgment from receiver side
𝑳 (𝒃𝒊𝒕𝒔)
𝑻𝒕 = 𝐓𝐭𝐚 and 𝐓𝐩𝐫 is very very small
𝑩 (𝒃𝒑𝒔) 𝑫 (𝒎)
𝑻𝑷 =
𝒗 (𝒎\𝒔𝒆𝒄)
So total time required for one frame is T = 𝑻𝒕 + 2𝑻𝒑
𝑢𝑠𝑒𝑓𝑢𝑙𝑙 𝑡𝑖𝑚𝑒 (𝒕𝒓𝒂𝒏𝒔𝒎𝒊𝒔𝒔𝒊𝒐𝒏 𝒕𝒊𝒎𝒆) 𝑻𝒕
• Efficiency (ɳ) = =
𝑇𝑜𝑡𝑎𝑙 𝑡𝑖𝑚𝑒 𝑻𝒕 + 2𝑻𝒑
1
ɳ = 𝑻𝒑
1+2( 𝑻 )
𝒕
𝟏 𝑻𝒑
ɳ= where a =
+ 2𝒂
𝟏 𝑻𝒕
𝑳 (𝒃𝒊𝒕𝒔 𝒑𝒆𝒓 𝒇𝒓𝒂𝒎𝒆)
• Throughput / Bandwidth utilization =
𝑻 (𝑻𝒐𝒕𝒂𝒍 𝒕𝒊𝒎𝒆)
/ Effective bandwidth
𝑳
Throughput =
𝑻𝒕 + 2𝑻𝒑

𝑻𝒕 .𝑩
Throughput = = ɳ.B = Efficiency*Bandwidth
𝑻𝒕 + 2𝑻𝒑
Difference Between CSMA/CA and CSMA/CD
CSMA/CA CSMA/CD
CSMA / CA is effective before a collision. CSMA / CD is effective after a collision.

CSMA / CA is commonly used in wireless networks. CSMA / CD is used in wired networks.

CSMA/ CA minimizes the possibility of collision. It only reduces the recovery time.

CSMA / CA will first transmit the intent to send for data CSMA / CD resends the data frame whenever a conflict
transmission. occurs.

CSMA / CA is used in 802.11 standard. CSMA / CD is used in 802.3 standard.

It is more efficient than simple CSMA(Carrier Sense Multiple

It is similar to simple CSMA(Carrier Sense Multiple Access).
Access).

It is the type of CSMA to detect the collision on a shared

It is the type of CSMA to avoid collision on a shared channel.
channel.

It is work in MAC layer. It also work in MAC layer.