Computer Networks - Unit 2

What is the Data Link Layer?

The Data Link Layer is the second layer of the OSI model. It helps data travel safely
and correctly between two devices that are directly connected, like a computer and a
router on the same network.

What does it do?

1. Framing – It breaks the data into small pieces called frames so the receiver
knows where each piece of data starts and ends.

2. Addressing – It adds the physical (MAC) address of the sender and receiver so
the data reaches the correct device.

3. Error Detection – It checks for errors that may have happened during
transmission.

4. Flow Control – It manages how fast data is sent, so the receiver doesn't get
overloaded.

Simple Example
Think of sending a letter in an apartment building:

You put the message in an envelope (framing).

You write the correct room number (MAC address).
You make sure the letter is not torn (error detection).
You don't send too many letters at once (flow control).

Need of Data Link Layer

1. Reliable Data Transfer (Between Neighboring Devices): It ensures that data is
transferred correctly from one device to another on the same network (like from
your laptop to the Wi-Fi router).

2. Error Detection & Correction: It checks for errors in the data during
transmission and can correct small errors or ask for retransmission if needed.

3. Framing: It divides data into frames (small packets) so the receiver knows
where the data starts and ends.

4. Flow Control: It prevents the fast sender from overwhelming a slow receiver by
managing the data flow rate.

5. MAC Addressing: It uses MAC addresses to identify devices uniquely on the local
network (like LAN).

The Data Link Layer ensures error-free, well-organized, and device-to-device

communication on the same network segment using framing, addressing, and error
control.

Services Provided by the Data Link Layer:

 1. Framing
It divides the data into small blocks called frames, so the receiver knows
where each message starts and ends.

2. Physical Addressing
It adds the MAC address (hardware address) of the sender and receiver to each
frame. This helps the data reach the correct device on a local network.

3. Error Detection
It checks if the data was damaged during transmission. If there’s an error, it
can request the sender to resend the data.

4. Flow Control
It prevents the sender from sending data too fast for the receiver to handle.

5. Access Control
In a network where multiple devices share the same communication medium (like
Wi-Fi), it decides which device can send data at a given time to avoid
collisions.

What is Framing?
Framing is the process of dividing data into smaller chunks called frames before
sending it over the network.

Why is Framing needed?

So the receiver can understand where each message starts and ends.
It helps in organizing data for easy and reliable communication.
It allows the receiver to detect errors in each frame separately.

Simple Example:

Imagine sending a big paragraph by SMS. You break it into multiple small messages
(frames), so each one can be sent and read clearly.

What is Flow Control?

Flow Control is a method used to control the speed of data transmission between two
devices.

Why is Flow Control needed?

Because sometimes:

The sender is fast, and

The receiver is slow.

If the sender keeps sending too quickly, the receiver's buffer (temporary storage) can
overflow, and data may get lost.

What Flow Control does:

It slows down the sender when needed.
It lets the receiver catch up and process the data properly.

Simple Example:
Imagine a teacher (sender) reading notes to a student (receiver). If the teacher talks
too fast, the student can’t write everything down. So, the student asks the teacher to
slow down — that’s flow control.

What is Error Control?

Error control means detecting and fixing errors that happen when data is sent from one
device to another.

Why is Error Control needed?

When data travels through wires or wireless signals, it can get corrupted due to noise
or interference.
Error control helps to:

Find those errors.

Fix them or ask the sender to resend the data.

How it works:
1. The sender adds extra bits (like checksums or CRC) to help detect errors.
2. The receiver uses those bits to check if the data is correct.
3. If there’s a problem, it can:
Request a resend, or
Fix the error if possible.

Simple Example:

Imagine you send a note to a friend, and they reply, "Some words are missing, please
resend."
That’s error control — making sure the message is received correctly.

What are Data Link Layer Protocols?

Data Link Layer protocols are rules and methods that help devices communicate
correctly on the same network.

These protocols handle tasks like:

Framing
Error detection
Flow control
Access control

Why are they needed?

To make sure that:

Data is sent and received without errors

Devices don’t talk at the same time
Data reaches the correct device

Elementary Protocols
Elementary Protocols in the Data Link Layer of the OSI Model are simple communication
protocols used to understand how data is transmitted between two directly connected
nodes. They are mainly used for learning and simulation purposes, not real-world
networking.

Types of Elementary Protocols:

1. Unrestricted Simplex Protocol

One-way data transmission without error or flow control.

2. Simplex Stop-and-Wait Protocol

One-way communication with sender waiting for an acknowledgment before

sending the next frame.

3. Simplex Protocol for a Noisy Channel

One-way communication with error handling using acknowledgments and

timeouts.

1-bit Protocol (Stop-and-Wait ARQ)

The 1-bit protocol is a simple error and flow control method in the Data Link Layer,
often called the Stop-and-Wait Automatic Repeat reQuest (ARQ). It uses only 1 bit (0
or 1) for numbering frames.

It is an example of Elementary Protocol.

How it works (in simple terms):

1. Sender sends a frame with a sequence number (0 or 1).
2. Sender waits for an acknowledgment (ACK) before sending the next frame.
3. Receiver gets the frame, processes it, and sends back an ACK with the same
sequence number.
4. Sender receives the ACK, flips the bit (0 to 1 or 1 to 0), and sends the next
frame.

Why 1 bit?
Since the sender sends only one frame at a time, just two numbers (0 and 1) are
enough to keep track of which frame is being sent or acknowledged.

Features:
Simple to implement.
Handles errors and duplicate frames.
Efficient only for short-distance communication (slow for long-distance due to
waiting time).

Advantages of 1-bit Protocol (Stop-and-Wait ARQ):

1. Simple and Easy to Implement
Uses basic logic with minimal resources.
2. Reliable Transmission
Ensures every frame is acknowledged before sending the next.
3. Error Handling
Can detect lost or damaged frames using timeouts and retransmissions.
4. Avoids Duplicate Frames
Sequence numbers (0 or 1) help identify duplicates.

Disadvantages of 1-bit Protocol:

 1. Low Efficiency
Only one frame is sent at a time; the sender waits idle until ACK is received.
2. Wasted Time on Long-Distance Links
High round-trip delay reduces throughput significantly.
3. Poor Bandwidth Utilization
Network capacity is underused due to waiting between frames.
4. Not Scalable
Inefficient for high-speed or high-volume data transfer.

Sliding Window Protocol (in short and simple):

Sliding Window Protocol is a data link layer method for efficient and reliable
transmission of multiple frames at once. It allows the sender to send several frames
before needing an acknowledgment, using a "window" of frame sequence numbers.

How it Works:
Sender Window: Limits how many frames the sender can send without ACK.
Receiver Window: Limits how many frames the receiver can accept in sequence.
When an ACK is received, the window slides forward, allowing more frames to be
sent.

There are two main types:

Go-Back-N: If one frame is lost, all following frames are resent.

Selective Repeat: Only the missing or damaged frames are resent.

Advantages:
1. High Efficiency
– Multiple frames sent at once increases throughput.
2. Better Bandwidth Utilization
– No waiting after every frame like in Stop-and-Wait.
3. Reliable Data Transfer
– Ensures frames are received correctly and in order.

Disadvantages:
1. Complex Implementation
– Requires more memory and logic to manage windows and buffers.
2. More Processing Overhead
– Needs to track multiple frames and manage ACKs for each.
3. Selective Repeat is Harder
– Handling out-of-order frames makes the receiver more complex.

Go-Back-N Protocol:
Go-Back-N is a type of Sliding Window Protocol used in the Data Link Layer for sending
multiple frames efficiently.

How It Works (in simple terms):

1. Sender sends multiple frames (up to a fixed window size) without waiting for
individual ACKs.
2. If all frames are received correctly, the receiver sends back ACKs.
3. If one frame is lost or has an error, the receiver ignores it and all the
following frames.
 4. Sender "goes back" and resends the lost/damaged frame and all frames after it.

Example:
Sender sends frames 1, 2, 3, 4, 5.
Frame 2 gets lost.
Receiver ignores frames 3, 4, 5.
Sender resends frames 2, 3, 4, 5.

Key Points:
Uses sequence numbers for tracking frames.
Receiver does not store out-of-order frames.
Sender handles retransmission when timeout or NAK (Negative ACK) occurs.

Advantages:
Better than Stop-and-Wait (sends multiple frames).

Simpler than Selective Repeat.

Disadvantages:
Wastes bandwidth if many frames are sent after a lost one (they get discarded).

Resends more frames than necessary.

Selective Repeat Protocol (Simple Explanation):

Selective Repeat is a Sliding Window Protocol that sends multiple frames like Go-Back-
N, but it’s smarter about retransmission.

How It Works (in simple terms):

1. Sender sends multiple frames at once (within window size).
2. If a frame is lost or damaged, only that specific frame is resent.
3. Receiver stores correct frames, even if they come out of order.
4. Once the missing frame is received, the receiver rearranges the order and sends
ACKs.

Example:
Sender sends frames 1, 2, 3, 4.
Frame 2 is lost.
Receiver stores 3 and 4.
Sender resends only frame 2.
Receiver reorders: 1, 2, 3, 4.

Key Points:
More efficient than Go-Back-N.
Receiver must have buffer to store out-of-order frames.
Needs individual ACKs for each frame.

Advantages:
Saves bandwidth by resending only the missing frames.
More efficient for high-speed or error-prone networks.

Disadvantages:
More complex to implement.
 Receiver needs extra memory and logic to reorder frames.

Hybrid ARQ (Automatic Repeat reQuest) – Simple Explanation:

Hybrid ARQ is a smart method that combines error detection and error correction to
make data transmission more reliable and efficient.

How It Works (in simple terms):

1. Sender adds error-checking and correction bits (like in Forward Error
Correction – FEC).
2. Receiver first tries to fix small errors using the correction bits.
3. If errors are too big to fix, the receiver asks the sender to resend the data
(like in ARQ).
4. So, it tries to fix errors without retransmission, but falls back to ARQ if
needed.

Types:
Type-I Hybrid ARQ: Error correction + retransmission of the same data.
Type-II/III Hybrid ARQ: Adds extra bits during retransmission to improve
correction.

Advantages:
Fewer retransmissions, saves time and bandwidth.
More reliable in poor network conditions.

Disadvantages:
More complex than basic ARQ.
Needs extra processing and memory for error correction.

Protocol Verification:
Protocol verification is the process of checking whether a communication protocol
works correctly — meaning it follows all rules, avoids errors (like deadlocks), and
handles all possible situations properly.

1. Finite State Machine (FSM) Models

What it is:

A Finite State Machine (FSM) is a model that represents a system using a finite number
of states, transitions, and inputs. It’s like a flowchart that shows how a protocol
moves from one step to another.

Components:
States: Different situations the system can be in (e.g., Waiting for ACK,
Sending Frame).
Transitions: Movement from one state to another triggered by an event (e.g.,
receiving a frame).
Inputs/Outputs: Events or actions that cause transitions or are generated as a
result.

Use in Protocols:

FSM helps you trace all possible actions in a protocol and verify:
 Are all states reachable?
Are there deadlocks or infinite loops?
Is every input handled properly?

Good for:
Protocols with sequential steps

2. Petri Net Models

What it is:

A Petri Net is a graphical and mathematical tool used to model systems with concurrent
(parallel) processes — great for complex communication protocols.

Components:
Places (circles): Represent conditions or resources (e.g., buffer full/empty).
Transitions (rectangles/bars): Represent events or actions (e.g., send,
receive).
Tokens (dots): Represent the current state or active process. Tokens move
between places via transitions.

Use in Protocols:

Petri nets can model:

Multiple processes happening at the same time

Synchronization and mutual exclusion
Deadlocks, conflicts, or resource contention

Good for:
Protocols with parallel activities
Systems with shared resources or timing issues

Comparison:

Feature FSM Petri Net

Style State-based Graph-based with tokens

Handles
Not well Very well
Concurrency

Visual Complexity Simple More detailed

Step-by-step protocol Parallel processes,

Use Case
logic synchronization

Best For Simple protocols Complex, concurrent protocols

Address Resolution Protocols

Address Resolution Protocols are a group of protocols used to map between logical
addresses (IP addresses) and physical addresses (MAC addresses) in a computer network.
These protocols are essential for data communication within a local area network (LAN)
where devices need to locate each other using their hardware addresses.

They operate at the Network Layer (Layer 3) and are crucial in ensuring that data
reaches the correct destination within the same network.
1. ARP (Address Resolution Protocol)
Definition: ARP is used to map an IP address to a MAC address.

Working: When a device wants to send data to another device on the same network
but knows only its IP address, it sends an ARP request (a broadcast message)
asking,
"Who has this IP address?"
The device with that IP responds with its MAC address.

Purpose: Enables devices to fill in their ARP tables to send Ethernet frames
correctly.

Example: Device A wants to send data to IP 192.168.1.5 . It sends an ARP

request, and Device B replies with its MAC address.

2. RARP (Reverse Address Resolution Protocol)

Definition: RARP is used to map a MAC address to an IP address.

Working: A device that only knows its hardware (MAC) address sends a RARP
request to a RARP server. The server replies with the corresponding IP address.

Purpose: Used by diskless devices (like early terminals or embedded systems)

that do not have stored IP configuration.

Limitation: Requires a RARP server on the same local network and has been
largely replaced by BOOTP and DHCP in modern networks.

3. GARP (Gratuitous ARP)

Definition: GARP is a type of ARP message that a device sends to announce its
own IP-to-MAC mapping to the network.

Working: A device sends an ARP request with its own IP as both the sender and
target IP address, essentially saying,
"This is my IP and MAC address."

Purpose:

To update other devices’ ARP tables.

To detect IP address conflicts.

Used when a device joins the network or changes its IP/MAC address.

No reply is expected for GARP.

Comparison Table

Protocol Full Form Function Direction Used For

Address
IP address Forward Sending data
ARP Resolution
MAC address Lookup within LAN
Protocol

RARP Reverse Address MAC address Reverse IP assignment

 Resolution IP address Lookup for diskless
Protocol devices

Announces own IP conflict

Self-
GARP Gratuitous ARP IP-MAC detection, ARP
Announcement
mapping table updates