The Data Link Layer
Position of the data-link layer
Framing
1
Data Link Layer is logically divided into 2
sublayers depending upon functionality
Vijay S. Katta 3
Functions of MAC Sublayer
Functions of MAC Sublayer:
1. Framing: Divides data into frames for transmission.
2. Addressing: Provides unique MAC addresses for devices on a network.
3. Error Detection: Uses CRC (Cyclic Redundancy Check) for error detection.
4. Access Control: Controls access to the shared medium (e.g., CSMA/CD in
Ethernet, CSMA/CA in Wi-Fi).
5. Flow Control: Prevents data congestion between sender and receiver.
6. Packet Prioritization: Manages Quality of Service (QoS) for different types of
data.
7. Collision Handling: Detects and resolves collisions in a shared medium.
2
Functions of Data Link Control (DLC)
Sublayer:
1. Establishing and Terminating Links: Manages the establishment and
termination of communication links.
2. Error Control: Ensures error-free transmission using techniques like Automatic
Repeat request (ARQ).
3. Flow Control: Prevents overwhelming the receiver by regulating the data flow.
4. Data Sequencing: Ensures frames are delivered in the correct order.
5. Acknowledgment Mechanism: Confirms the receipt of frames.
6. Logical Link Control (LLC): Provides multiplexing of network protocols on the
same network interface.
Summary:
• MAC sublayer: Focuses on physical addressing and medium access control.
• DLC sublayer: Ensures reliable, error-free communication between devices.
Data Link Layer Design Issues
• Services Provided to the Network
Layer
• Framing
• Line Discipline
• Error Control
• Flow Control
3
Functions of the Data Link
Layer (2)
Relationship between packets and
frames.
Services Provided to Network
Layer (2)
Placement of the data link protocol.
4
Data link layer duties
Framing
Framing
Framing
1. A character Count.
fig(a) Without errors..
fig(b) With one error.
5
Framing (2) Character flag with
character stuff
(a) A frame delimited by flag bytes.
(b) Four examples of byte sequences before
and after stuffing.
Framing (3) Bit flag with bit
stuffing
Bit stuffing
(a) The original data.
(b) The data as they appear on the line.
(c) The data as they are stored in receiver’s memory
after destuffing.
6
Data Link Control sublayer
Design Issues
7
ENQ/ACK
8
ENQ/ACK
Multipoint Discipline
9
Select
Poll
10
Error Detection
and Correction
Types of Errors
Detection
Correction
Note:
Data can be corrupted during
transmission. For reliable
communication, errors must be
detected and corrected.
11
Types of Errors
Single-bit error
12
Multiple-bit error
Burst error
13
Error Detection
Note:
Error detection uses the
concept of redundancy, which
means adding extra bits for
detecting errors at the
destination.
14
Error Detection Methods
VRC
15
LRC
VRC and LRC
16
Cyclic Redundancy Check
Polynomial
17
Polynomial and Divisor
Figure 9-14
Standard Polynomials
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
18
Table of Standard polynomials
Name Polynomial Application
CRC-8 x8 + x2 + x + 1 ATM header
CRC-10 x10 + x9 + x5 + x4 + x 2 + 1 ATM AAL
ITU-16 x16 + x12 + x5 + 1 HDLC
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10
ITU-32 LANs
+ x8 + x7 + x5 + x4 + x2 + x + 1
Example:1
Data :- 100100
Divisor :- x3 + x2 +1
Solution:-
Divisor :- 1101
Use modulo 2 Division
(X-OR Operation)
19
Binary division in a CRC generator
10.9 Binary division in CRC checker
20
Calculation of the polynomial code checksum.
Example
It is obvious that we cannot choose x (binary 10) or x2 + x
(binary 110) as the polynomial because both are divisible
by x.
However, we can choose x + 1 (binary 11) because it is
not divisible by x, but is divisible by x + 1. We can also
choose x2 + 1 (binary 101) because it is divisible by x + 1
(binary division).
21
Example
The CRC-12
x12 + x11 + x3 + x + 1
which has a degree of 12, will detect all burst errors
affecting an odd number of bits, will detect all burst
errors with a length less than or equal to 12.
Data Unit and Checksum
22
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.
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.
23
Example 7
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
1 0 1 0 1 0 0 1
0 0 1 1 1 0 0 1
--------------------------------------------------
Sum 1 1 1 0 0 0 1 0
Checksum 00011101
The pattern sent is 10101001 00111001 00011101
Example
Now suppose the receiver receives the pattern sent in Example 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 111 11111
Complement 0 0 0 0 0 0 0 0 means that the pattern is OK.
24
Figure 9-17
Error Correction
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
Hamming Code
25
Hamming Code
Hamming Code
26
Example of Hamming Code
Single-bit error
27
Error
Detection
Error-Correcting Codes
Use of a Hamming code to correct burst
errors.
28
Data Link
Control
and
Protocols
Flow and Error Control
Flow Control
Error Control
29
Note:
Flow control refers to a set of
procedures used to restrict the amount
of data that the sender can send before
waiting for acknowledgment.
Note:
Error control in the data link layer is
based on automatic repeat request,
which is the retransmission of data.
30
Figure Taxonomy of protocols discussed in this chapter
11.61
Figure 10-15
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
31
11-4 NOISELESS CHANNELS
Let us first assume we have an ideal channel in which
no frames are lost, duplicated, or corrupted. We
introduce two protocols for this type of channel.
Topics discussed in this section:
Simplest Protocol
Stop-and-Wait Protocol
11.63
Figure 11.6 The design of the simplest protocol with no flow or error control
11.64
32
Figure 11.7 Flow diagram for Example 11.1
11.65
Design of Stop-and-Wait Protocol
11.66
33
Stop and Wait
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
Normal operation
34
Figure 10-11
Sliding Window
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
Figure 10-12
Sender Sliding Window
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
35
Receiver Sliding Window
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
Figure 10-14
Sliding Window Example
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
36
Figure 10-14-continued
Sender
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
Figure 10-14-continued
Receiver
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
37
Error Control ARQ
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
Error Control ARQ
38
Stop and wait ARQ
Stop and wait ARQ ,Lost Data
frame
39
Stop and wait ARQ, Lost ACK
frame
Stop and wait ARQ Damaged
Frame
40
Sliding Window ARQ
WCB/McGraw-Hill © The McGraw-Hill Companies, Inc., 1998
Error Control ARQ
41
Go-Back-n-ARQ (Error detected
in frame)
Go-Back n ARQ, Lost Data
frame
42
Go-Back n ARQ, Damaged data
frame
Go-Back-n, Lost ACK frame
43
Selective Repeat/Selective
reject ARQ
Protocol Efficiency
-STOP AND WAIT ARQ
-SLIDING WINDOW ARQ
44
Frame Transmission Time (tf):
The time required to transmit the entire frame
from the sender to the communication
medium.
It depends on the frame size (L in bits) and the
data rate (R in bits per second).
This is the time taken by the sender to
push all bits of the frame into the
network.
◼ Formula:
𝑡𝑓= Bits per frame/ data rate =L/R
Propagation Time (tp):
It is the time required for a single bit to travel
from the sender to the receiver.
It depends on the distance (d) between sender
and receiver and the propagation speed (v) of
the signal in the medium.
Formula:
tp = distance/propagation speed
This measures how quickly the bits reach the
destination, regardless of frame size.
45
Real time example comparision
Imagine you are sending a letter to a
friend and waiting for a reply.
• tft(Transmission Time) → Time
taken to write and send the letter.
• tpt (Propagation Time) → Time
taken for the letter to reach your
friend.
Example
Given Data:
• Frame size = 100 bits
• Propagation time per bit = 1 sec
• Data rate = 1 Bits/sec
46
Understanding Propagation Time (tp):
• Propagation time is independent of frame
size.
• If one bit takes 1 second to propagate, then
all bits in the frame experience the same
propagation delay simultaneously.
• Total propagation time for the whole
frame is still 1 second (not 100 seconds in
given example).
Understanding Frame Transmission Time
(tf):
• Frame transmission time (tf) depends on the data rate
(R).
• If the data rate is 1 bit per second, then transmitting
100 bits frame will take:
• tf=Frame size/ Data rate
• =100 bits/1bps
• =100 sec
• So in this case, frame transmission time = 100 sec.
47
Conclusion:
• If the data rate is 1 bit/sec, then the frame
transmission time (tf) = 100 sec.
• The propagation time (tp) remains 1 sec
because all bits are in transit together.
• Total time for last bit to reach = tf + tp =
100 sec + 1 sec = 101 sec.
Performance calculation
Performance = (The actual time spent sending data)/ (The total time
required for one complete communication cycle)
Performance = tf/ (tf +2tp)
48
Key Insights
1. If tf>>tp (large frames, high data rate, or short distance):
◼ Performance approaches 1, meaning most of the time is used
for transmission.
◼ Example: Fiber-optic networks with high bandwidth and
short distances.
2. If tp>>tft (small frames, long distance, or slow
transmission rate):
1. Performance decreases significantly, meaning more time is
spent waiting.
2. Example: Satellite communication, where propagation delay is
large.
49
Example1
Example 2
50
Example 3
Example 4
51
Example 4 Continue
Example 5
52
Example 5 Continue + Example 6
Example 7
53
