Data link layer

➢ The Data Link Layer is the second layer in the OSI (Open Systems Interconnection) model,
lying just above the Physical Layer.
➢ Its main job is to provide reliable communication between directly connected nodes over
a physical medium.

Function of Data Link Layer

1) Framing
o Converts raw bits from the physical layer into structured frames.
o Frames contain the data plus control information like addresses, checksums, etc.

2) Error Detection and Correction

o Detects errors that may occur in the physical layer transmission.
o Techniques: Parity Bits, CRC (Cyclic Redundancy Check), Checksums, etc.
1
 Data link layer …
3) Flow Control
o Prevents a fast sender from overwhelming a slow receiver.
o Uses mechanisms like Stop-and-Wait, Sliding Window Protocol, etc.

4) Access Control (Medium Access Control)

o In shared media (like Ethernet or Wi-Fi), it controls which device can access the medium and when.
o Techniques include CSMA/CD (Ethernet) and CSMA/CA (Wi-Fi).

5) Physical Addressing
o Adds MAC (Media Access Control) addresses to the frames so that devices on the same network
can identify each other.
o MAC address is unique for every network interface card (NIC).

2
Data link layer …

3
 IEEE 802 standards
▪ The IEEE 802 is a set of networking standards created by the Institute of Electrical and Electronics
Engineers (IEEE) for local area networks (LANs) and metropolitan area networks (MANs).
▪ It defines how data is transmitted over a network at Layer 1 (Physical Layer) and Layer 2 (Data Link
Layer) of the OSI model.

4
DLL Sub-layer

5
 DLL Sub-layer
IEEE 802 Layers (in Data Link Layer)
The Data Link Layer is split into two sublayers:
[Link] (Logical Link Control) – IEEE 802.2
Handles error checking and control.
[Link] (Media Access Control) – Defined by standards like:
a) 802.3 for Ethernet
b) 802.11 for Wi-Fi
Handles addressing (MAC address) and access to the medium.

6
 DLL Sub-layer
1) LLC Sublayer (Logical Link Control)

What it does:
▪ Works above MAC.
▪ Provides error checking and flow control.
▪ Allows multiple network protocols (like IP, IPX) to work over the same MAC.

Key Tasks:
▪ Identifies protocol type (like IP or ARP)
▪ Adds control info in the header
▪ Ensures data integrity

Example: Tells whether the frame is carrying IP data or ARP data.

7
 DLL Sub-layer
2) MAC Sublayer (Media Access Control)

What it does:
▪ Adds MAC address (physical address) to frames.
▪ Controls when and how devices use the network.
▪ Detects collisions on the medium.
▪ Used in both wired (Ethernet) and wireless (Wi-Fi) networks.

Key Tasks:
▪ Frame formatting
▪ Access control (who can send data)
▪ Error detection (e.g., CRC)

Example: In Ethernet (IEEE 802.3), MAC decides when a device can send data using CSMA/CD.

8
 Data link layer Frame
o Framing is the process of dividing a stream of bits received from the network layer into
manageable units called frames.
o It also involves adding headers and sometimes trailers to define the beginning and end of
each frame.

1. FLAG
▪ Marks the start and end of a frame.
▪ Used in Bit stuffing and Byte stuffing
▪ A unique pattern is used as a flag (e.g., 01111110 in HDLC).
▪ Two flags are used: one at the beginning and one at the end of the frame.

9
 Data link layer Frame …
2. HEADER
o It Carries control information needed to deliver the frame.
o Contains
▪ Source and Destination MAC Address
▪ Frame type / Protocol info
▪ Sequence numbers (in reliable protocols)
▪ Control bits (ACK, NAK, etc.)

3. TRAILER
o Used for error detection and sometimes padding.
o Contains:
▪ CRC (Cyclic Redundancy Check)
▪ Checksum
10
 Data link layer Frame …
There are two main categories of framing methods:

Framing
Techniques

Fixed Size Variable Size

Framing Framing

Character
Byte Stuffing Bit Stuffing
Count

11
 Data link layer Frame …
1) Fixed Size Framing
o All frames are of same size.
o No need for start or end delimiters.
o Receiver divides the bit stream into frames based on size.

Advantages:
o Simple and fast.

Disadvantages:
o Wastes space if data doesn’t exactly fit the frame size.
o No flexibility for variable-size data.

2) Variable size Framing

Frame size varies based on the size of the data. To identify the start and end of a frame,
special techniques are used.
a) Character Count
b) Byte Stuffing
c) Bit Stuffing 12
 Data link layer Frame …
a) Character Count
o Frame begins with a byte that indicates the total number of bytes in the frame.
o Receiver reads the count and extracts that many bytes.

13
 Data link layer Frame …
b) Byte Stuffing
Byte stuffing is the process of adding 1 extra byte whenever there is a flag or escape
character in the text

14
 Data link layer Frame …
c) Bit Stuffing
Bit stuffing is the process of adding one extra 0 whenever five consecutive 1’s follow a 0 in the
data, so that the receiver does not mistake the pattern 0111110 for a flag

15
 Error Control
Error control in the Data Link Layer (DLL) ensures reliable transmission of data by detecting and
possibly correcting errors that occur during transmission .

Types of Errors:
1) Single-bit Error:
Only one bit in the frame is
altered.

2) Burst Error:
Two or more bits in the frame are
altered (common in real networks). 16
 Error Control …
Error Detection Techniques :
These methods detect whether an error occurred in the transmitted frame.

a) Parity Check c) Cyclic Redundancy Check (CRC)

o In this technique, One extra bit called o Treats data as a long binary number and
as parity bit is sent along with the divides it by a generator polynomial.
original data bits. Parity bit helps to o Appends the remainder as CRC bits.
check if any error occurred in the data o Receiver performs same division to check
during the transmission. remainder.
o Simple o Very powerful and detects:
o Only detects single-bit errors. ▪ Single-bit errors
▪ Double-bit errors
b) Checksum ▪ Burst errors up to 32 bits (depending
o Adds up all data bytes and appends the on polynomial)
sum. o Used in: Ethernet, HDLC
o Receiver checks if the total is correct.
o Used in IP, UDP, TCP
o Less reliable for burst errors. 17
 Error Control …
Error Correction Techniques
These methods correct the errors without retransmission.

a) Hamming Code
o Adds redundant bits that can locate and correct single-bit errors.
o Used in memory and real-time systems.

b) Forward Error Correction (FEC)

o Redundant data is sent along with original data to enable correction at the receiver.
o Common in wireless communication (e.g., satellite links).
o No retransmission needed

18
 Error Control …
Retransmission Techniques :
o Any time an error is detected in an exchange, specified frames are retransmitted. This
process is called automatic repeat request (ARQ)
o i.e. If an error is detected, ARQ protocols ask for retransmission.

19
 Flow Control
o Flow Control is a technique used in the Data Link
Layer to prevent the sender from overwhelming
the receiver with too much data too quickly.
o It ensures that data is sent at a rate that the
receiver can process and store without loss.

Why Flow Control is Needed?

o Sender is often faster than receiver.
o Receiver may not have enough buffer space.
o Without control, data may get dropped or
corrupted.

20
 Flow Control …
1) Noiseless Channel
a) Simplest
o The Simplest Protocol is a basic data
transmission protocol used for theoretical
understanding of data link layer operations

Assumptions of Simplest Protocol:

o Error-free communication
o No flow control needed
o Receiver is always ready to receive the next
frame
o Only one-way communication (from sender to
receiver) Working:
o Data link is reliable ▪ Sender sends one frame at a time
continuously.
▪ Receiver immediately processes the frame
and waits for the next.
▪ No ACK (Acknowledgment) or NAK is used.
▪ No retransmission mechanism.
21
 Flow Control …
Advantages:
o Very simple and easy to understand
o No overhead of acknowledgments or retransmissions

Disadvantages:
o Not practical in real-world networks
o Cannot handle:
▪ Frame loss
▪ Errors
▪ Buffer overflow at receiver
o No way to confirm if data was received

22
 Flow Control …
b) Stop and Wait
o Sender sends a data packet to the receiver.
o Sender stops and waits for the acknowledgement for the sent
packet from the receiver.
o Receiver receives and processes the data packet.
o Receiver sends an acknowledgement to the sender.
o After receiving the acknowledgement, sender sends the next
data packet to the receiver.

Advantages:
o Simple to implement.

Disadvantages:
o Low efficiency, especially on long-delay (high-latency) links.

23
 Flow Control …
2) Noisy Channel
Sliding Window Protocol
o Allows sender to send multiple frames before waiting for ACK.
o Uses a window to define the number of unacknowledged frames allowed.

Components:
o Sender Window Size (N): Maximum frames sender can send without ACK.
o Receiver Window Size: Number of frames the receiver can buffer.

Advantages:
o High efficiency.
o Keeps pipeline full and better use of bandwidth.

Disadvantages:
o More complex.
o Needs sequence numbers and buffering.

24
 Flow Control …
a) Stop and Wait ARQ
o The communication channel is noisy.
o Errors may get introduced in the data during the transmission.
o Stop and wait ARQ works similar to stop and wait protocol.
o It provides a solution to all the limitations of stop and wait protocol.
o Stop and wait ARQ includes the following three extra elements.

25
 Flow Control …
Stop and wait ARQ is a one bit sliding window protocol where-
•Sender window size = 1
•Receiver window size = 1

Thus, in stop and wait ARQ,

Minimum number of sequence numbers required
= Sender Window Size + Receiver Window Size
=1+1
=2

Thus,
Minimum number of sequence numbers required in Stop and Wait ARQ = 2.
The two sequence numbers used are 0 and 1.

26
 Flow Control …
Problem of Lost Data Packet-

▪ Time out timer helps to solve the problem of lost data

packet.
▪ After sending a data packet to the receiver, sender starts
the time out timer.
▪ If the data packet gets acknowledged before the timer
expires, sender stops the time out timer.
▪ If the timer goes off before receiving the acknowledgement,
sender retransmits the same data packet.
▪ After retransmission, sender resets the timer.
▪ This prevents the occurrence of deadlock.

27
 Flow Control …
Problem of Lost Acknowledgement-

•Sequence number on data packets help to solve the

problem of delayed acknowledgement.
•Consider the acknowledgement sent by the receiver
gets lost.
•Then, sender retransmits the same data packet after its
timer goes off.
•This prevents the occurrence of deadlock.
•The sequence number on the data packet helps the
receiver to identify the duplicate data packet.
•Receiver discards the duplicate packet and re-sends the
same acknowledgement.

28
 Flow Control …

Problem of Damaged Packet-

•If receiver receives a corrupted data packet from the

sender, it sends a negative acknowledgement (NAK) to
the sender.
•NAK requests the sender to send the data packet
again.

29
 Flow Control …
Difference between Stop-and-wait & stop-and-wait ARQ

30
 Flow Control …
b) GO Back N ARQ

o Go-Back-N ARQ is a retransmission protocol Go-Back-N ARQ Working:

used in the Data Link Layer for error control
and flow control. Sender Side:
o It allows the sender to send multiple frames o Maintains a window of N frames.
before waiting for an acknowledgment, but o Can send N frames continuously without
if any frame is found in error, it goes back waiting for ACK.
and retransmits that frame and all frames o If no ACK is received for a frame within
after it. timeout:
▪ Resend that frame and all following
▪ Sender Window Size = N (N frames can be frames, even if some were received
sent without ACK) correctly.
▪ Receiver Window Size = 1 (can accept only
the next expected frame) Receiver Side:
▪ Frames are numbered modulo N (e.g., 0 to o Accepts only in-order frames.
N−1) o If frame is in order → send ACK.
o If out-of-order frame arrives → discard it, send
ACK for last correctly received frame.
31
 Flow Control …
c) Selective ARQ
It is an advanced version of Go-Back-N ARQ, designed to efficiently retransmit only the erroneous or
lost frames rather than retransmitting all subsequent frames.

Working:
o Sender transmits multiple frames up to a certain window size.
o Receiver checks each frame:
▪ If correct: it sends an ACK (acknowledgment).
▪ If incorrect: it discards the bad frame and sends a NACK (negative acknowledgment) or does
not send an ACK.
o Sender: Retransmits only those frames for which NACKs were received or ACKs were missing after
timeout.
o Receiver buffers the out-of-order correct frames until the missing frame is received.
32
 Flow Control …
Difference between Stop-and-Wait , Go-Back-N & Selective ARQ

33
 Link Layer Addressing
Link Layer Addressing is how devices on the same local network identify and communicate
with each other.

What is a Link Layer Address?

o Also called a MAC address (Media Access Control).
o A unique hardware address burned into every network interface card (NIC).
o Used to identify devices within the same network (like LAN).

Format of MAC Address

o 6 bytes (48-bit) address, usually written in hexadecimal:
o Example: [Link]

o Divided into two parts:

▪ First 3 bytes (24 bits) : Manufacturer ID (OUI)
▪ Last 3 bytes (24 bits) : Device-specific ID

34
 ARP Protocol
ARP (Address Resolution Protocol)
o ARP (Address Resolution Protocol) is a network protocol used to find the MAC address of a device
from its IP address in a local network.
o It works at the Data Link Layer (Layer 2) but uses information from the Network Layer (Layer 3).

Why ARP is Needed ?

When a device wants to send data on a LAN:
▪ It knows the IP address of the destination.
▪ But it needs the MAC address to actually send the frame.
▪ ARP is used to find the MAC address for that IP.

Example (ARP in Action)

Suppose computer A wants to send data to computer B:
▪ A knows B’s IP address, but not its MAC address.
▪ A uses ARP (Address Resolution Protocol) to ask: “Who has IP X.X.X.X?”
▪ B replies with its MAC address.
▪ A now sends data using B’s MAC address at the link layer.

35
 Random Access
➢ Random Access Control is a media access control (MAC) method used when multiple devices share a
communication channel (like in Ethernet or Wi-Fi).
➢ It allows any device to transmit at any time, without permission, making it simple but sometimes
prone to collisions.
Random
Access
Protocol

ALOHA CSMA CSMA/CD CSMA/CA

Pure Slotted
ALOHA ALOHA

36
 ALOHA
o ALOHA is a random access protocol used to control how multiple devices share a single
communication channel, like in wireless networks or satellites.
o It was one of the earliest MAC protocols, developed at the University of Hawaii.
o Devices send whenever they want.
o If collision → wait random time and retransmit.

a) Pure ALOHA b) Slotted ALOHA

▪ Devices transmit anytime without ▪ Devices transmit only in time slots (i.e. Time
checking ([Link] sends a data frame is divided into equal slots).
anytime). ▪ Devices can only send at the beginning of a
▪ If no collision → success. slot.
▪ If collision → device waits a random time ▪ If two or more send in same slot →
and retransmits. collision.
▪ Slotted ALOHA reduces collision risk by
synchronizing transmissions.

37
 ALOHA …
➢ This figure illustrates how collisions occur in a
Pure ALOHA system.
➢ It shows four stations (devices) trying to send
frames at random times over a shared channel.

▪ Station 1, Station 2, Station 3, and Station 4 all

try to send frames.
▪ Station 1 starts sending a blue frame.
▪ Station 2 starts sending a black frame shortly
after Station 1.
▪ Their frames overlap in time, causing a collision ▪ Again, Station 1 and Station 2 try to send new
(shown by the grey area). frames.
▪ Similarly, Station 3 and Station 4 also overlap ▪ Their transmissions overlap again, causing
with these frames. another collision.
▪ So, all four frames in this region are considered ▪ Meanwhile, Station 3 successfully sends a blue
corrupted and must be retransmitted. frame after the collision window — no overlap
here → successful transmission.

38
 ALOHA …
This figure shows how Slotted ALOHA works
and how collisions happen when multiple
stations transmit in the same time slot.

1) Slot 1
▪ Only Station 1 transmits.
▪ No collision.
▪ Successful transmission.

2) Slot 2 4) Slot 4
▪ Stations 2, 3, and 4 transmit at the same ▪ Only Station 4 transmits.
time. ▪ Successful transmission.
▪ Collision occurs.
▪ None of the data is received correctly. 5) Slot 5
▪ Only Station 3 transmits.
3) Slot 3 ▪ Successful.
▪ Stations 1, 2, and 3 transmit again.
▪ Another collision. 6) Slot 6
▪ Data is lost again. ▪ No transmission (idle slot). 39
 CSMA
CSMA (Carrier Sense Multiple Access)
CSMA is a random access protocol used in
networks to avoid collisions before sending data.

CSMA Working Steps:

o Sense the channel (check if it's busy).
o If idle → transmit the data.
o If busy → wait until it becomes free.

This diagram shows a space/time model of a collision in CSMA

▪ It shows two computers (B and C) trying to send data at almost the same time in a network.
▪ Computer B starts sending at time t₁.
▪ Computer C doesn’t know B is sending (because B's signal hasn't reached C yet).
▪ So, C also starts sending at time t₂.
▪ The signals from B and C crash into each other — this is a collision.
▪ The area where the signals overlap (gray part) is where data is lost.
40
 CSMA/CD
CSMA/CD – Carrier Sense Multiple Access with Collision Detection
CSMA/CD is a method used in wired networks (like Ethernet) to avoid data collisions when multiple
devices try to send data at the same time.

How it works:
a) Sense the channel:
Is the line free? If yes, then send data.
Send data.
b) Keep listening:
While sending, check for collision by detecting noise.
c) If collision happens:
Stop sending immediately.
Send a jamming signal (to inform others about the collision).
Wait a random time (backoff).
Try again.

41
 CSMA/CD …
This diagram explains collision and abortion in
CSMA/CD (Carrier Sense Multiple Access with
Collision Detection) in a simple timeline format.

▪ Station A starts sending data at time t₁.

▪ The data starts traveling along the medium
toward the other stations.
▪ Before C hears A's data, it also starts sending its
own data at time t₂.
▪ Collision happens in the middle of the network
(between A and C) where both signals overlap.
▪ Both A and C detect the collision:
• A detects the collision first at time t₄.
• C detects it later at time t₃. ▪ Both stations wait for a random time
▪ After detecting collision, both A and C stop (backoff time).
transmitting (they abort), following the ▪ Then they try to resend their data.
CSMA/CD protocol.

42
 CSMA/CA
CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)

How CSMA/CA Works:-

4)Receiver Replies with CTS (Clear to Send):
1) Carrier Sense (CS):
▪ If the channel is clear, the receiver
▪ The station listens to the channel.
sends CTS.
▪ If the channel is idle, it proceeds.
▪ If the channel is busy, it waits until it
5) Data Transmission Begins:
becomes idle.
▪ Only after receiving CTS, the station
sends the actual data.
2) Wait for Interframe Space (IFS):
▪ Even after the channel is idle, it waits for
6) Acknowledgment (ACK):
a small time (IFS) to ensure no one else
▪ After receiving the data, the receiver
starts.
sends an ACK.
3) Send RTS (Request to Send):
▪ The station sends a short signal to the
receiver asking permission to send data.

43
 CSMA/CA …
The diagram Figure 12.17 CSMA/CA and NAV shows
how CSMA/CA (Carrier Sense Multiple Access with
Collision Avoidance) works using RTS/CTS signals
and NAV (Network Allocation Vector) to prevent
collisions in wireless communication (like Wi-Fi).

A = Source (wants to send data)

B = Destination (receiver)
C, D = Other stations nearby (should stay silent to
avoid collision)

44
 CSMA/CA …
1) A waits for DIFS (Distributed Inter-Frame 4) C and D set NAV (Network Allocation Vector)
Space) ▪ C and D hear CTS, so they set their NAV
▪ A checks the channel. If idle, waits for — this is a timer that tells them to stay
DIFS time (a small gap). silent for the given duration.
▪ This is collision avoidance: other stations
2) A sends RTS (Request To Send) won’t try to transmit during that time.
▪ A sends a small control message: “Can I
send data?” 5) A sends the actual Data
▪ This includes duration information ▪ Now that the channel is clear, A sends
(how long data + ACK will take). the full data frame.
3) B replies with CTS (Clear To Send) 6) B sends ACK (Acknowledgement)
▪ B replies with CTS, saying “Yes, go ▪ After receiving data, B waits a SIFS (Short
ahead”. Inter-Frame Space) and sends ACK.
▪ It also includes the same duration info. ▪ This tells A the data was received
successfully.

45
 HDLC
➢ High-Level Data Link Control.
➢ It is a bit-oriented protocol developed by ISO for reliable communication.

Features of HDLC:
o Bit-oriented protocol → Uses bit patterns for framing (not characters).
o Works at Data Link Layer (Layer 2 of OSI model).
o Error detection → Uses CRC (Cyclic Redundancy Check).
o Reliable communication → Supports flow and error control.

46
 HDLC …
Types of Stations in HDLC:

[Link] Station
o Controls the operation of the link.
o Responsible for initiating communication.
o Sends commands to secondary stations.
o Maintains error and flow control.

[Link] Station
o Works under the control of the primary station.
o Cannot start communication on its own.
o Sends responses back to the primary.

[Link] Station
o Has features of both primary and secondary.
o Can send commands and responses.
o Used in peer-to-peer communication.

47
 HDLC …
Modes of Communication (based on stations):

[Link] Response Mode (NRM)

o Primary → controls communication.
o Secondary → only responds when asked.
o Example: Mainframe computer with
terminals.

[Link] Response Mode (ARM)

o Secondary can initiate transmission (with
permission).
o Less common.

[Link] Balanced Mode (ABM)

o Combined stations communicate directly.
o Most flexible, used in modern peer-to-
peer systems.

48
 HDLC …
HDLC Frame:
o Flag → 01111110 (marks start & end of a frame).
o Address → Identifies the secondary station.
o Control → Defines type of frame (I, S, or U).
o Information → Actual data (only in I-frames).
o FCS (Frame Check Sequence) → Error detection (CRC).

49
 HDLC …
Types of HDLC Frames:

1) I – frame
➢ Information Frame
➢ Used to carry user data & some control information.

Control field format (8 bits):

o 0 → indicates this is an I-frame.
o N(S) → Send sequence number (for flow control).
o P/F → Poll/Final bit (used for commands & responses).
o N(R) → Receive sequence number (acknowledges last correctly received frame).

50
 HDLC …
2) S – Frame

➢ Supervisory Frame
➢ Used for flow control and error control, not for user data.

Control field format (8 bits):

o 10 → indicate S-frame.
o SS bits (2 bits) indicate the type of supervisory function:
▪ 00 → RR (Receive Ready) → ACK, ready for next
frame.
▪ 01 → REJ (Reject) → NACK, retransmit from this
frame.
▪ 10 → RNR (Receive Not Ready) → Temporary stop
(buffer full).
▪ 11 → SREJ (Selective Reject) → NACK for only one
frame (selective retransmission).
o P/F → Poll/Final bit.
o N(R) → Next expected frame number.

51
 HDLC …
3) U – Frame

➢ Unnumbered Frame
➢ Used for control, link management, and special purposes

Management Information:
o The Information field of a U-frame can be used for
management/control data.
o This is not user payload, but rather link management
details exchanged between stations.
o Example: parameters for establishing a session,
configuration data, or error reporting details.
Management information used for:
o Link setup
Control field format (8 bits): o Error diagnostics
o 11 → indicates this is an U - frame. o Configuration
o M → 5-bit modifier bits (define the exact type of U- o Control signaling
frame).
o P/F → Poll/Final bit.
52
 HDLC …
modifier bits (5-bit) in U – Frame:

53
 VLAN
o Virtual Local Area Network
o It is a logical (virtual) network created inside a physical LAN.
o Devices in the same VLAN can communicate as if they are on the same LAN, even if they are connected
to different physical switches.
o VLAN divides one physical network into multiple smaller logical networks.
o VLAN is created by a Switch, NOT by a Hub.

Why VLAN? (Need)

o Segmentation → Break a big network into smaller groups.
o Security → Users in one VLAN cannot directly access another VLAN.
o Reduced Broadcasts → Each VLAN has its own broadcast domain → less traffic.
o Flexibility → Devices can be grouped by department (HR, Finance, Students, Faculty, etc.) not by
physical location.
54