UNIT II: THE DATA LINK LAYER

The Data Link Layer: Transmission Media, Guided and Un-guided media,Data Link
Layer Design Issues, Services Provided To the Network Layer, Error detecting and Error
Correcting codes, Elementary Data Link Protocols, Sliding Window Protocols, HDLC,
PPP. Multiple Access Protocols Wired Lans: Ethernet, Fast Ethernet, Gigabit Ethernet

1. Transmission Media
Transmission media refers to the physical channel or path through which data
travels from the source to the destination. Media are broadly categorized into
guided (wired) and unguided (wireless).

1.1 Guided Media (Wired)

Guided media use a physical conduit to confine the electromagnetic waves.

1.1.1 Twisted-Pair Cable

Consists of two insulated copper wires twisted together to reduce crosstalk

(electromagnetic interference between adjacent pairs).

●​ UTP (Unshielded Twisted Pair): Most common; used in LANs (e.g., Cat
5e, Cat 6). Low cost, easy installation.
●​ STP (Shielded Twisted Pair): Contains a metallic foil shield around the
pair to enhance protection against external noise, but is bulkier and more
expensive.
●​ Application: Telephony, Ethernet (up to 10 Gbps depending on category).

1.1.2 Coaxial Cable

Consists of a central copper core surrounded by an insulator, a braided shield,

and an outer jacket. The shield provides excellent noise immunity.

●​ Types: Thinnet (flexible) and Thicknet (stiffer, longer distance).

●​ Application: Cable television, long-distance telephone transmission
(historically), and older Ethernet standards. Offers higher bandwidth and
better shielding than UTP.

© 2025 [Link] team. All rights reserved.

1.1.3 Fiber-Optic Cable

Transmits data as pulses of light through a glass or plastic core. This uses the
principle of total internal reflection.

●​ Advantages: Extremely high bandwidth, very long distance capability,

complete immunity to electromagnetic interference (EMI), and highly
secure (difficult to tap).
●​ Types:
○​ Multimode Fiber: Uses a thicker core; multiple light rays travel at
different angles. Used for shorter distances (LANs).
○​ Singlemode Fiber: Uses a very thin core; light travels along a single
path. Used for extremely long distances (WAN backbones, undersea
cables).

1.2 Un-guided media (Wireless)

Unguided media transmit electromagnetic waves without using a physical

conductor; the signal propagates through air, vacuum, or water.

1.2.1 Radio Waves

Omni-directional transmission across a wide frequency range (typically 3 kHz to

1 GHz).

●​ Characteristics: Easily penetrate walls. Used for broadcasting, mobile

communication (cellular networks), and long-distance connectivity.
●​ Examples: AM/FM radio, common Wi-Fi frequencies (e.g., 2.4 GHz).

1.2.2 Microwaves (Terrestrial and Satellite)

High-frequency radio waves (1 GHz to 300 GHz).

●​ Terrestrial Microwave: Directional; requires line-of-sight between

antennas (e.g., dish antennas on towers). Used for high-speed
communication over land where cabling is impractical.
●​ Satellite Microwave: Uses satellites orbiting Earth to relay signals.
Provides coverage over massive geographic areas (WANs) and is crucial
for global communication.

© 2025 [Link] team. All rights reserved.

1.2.3 Infrared

High-frequency waves used for short-range communication in confined areas (up

to a few meters).

●​ Characteristics: Cannot penetrate walls or objects. Secure for indoor use.

●​ Examples: TV remote controls, short-range device communication.

2. Data Link Layer Design Issues

The primary function of the Data Link Layer is transforming the unreliable
physical transmission medium into a reliable link for the Network Layer. This
involves handling several critical design issues:

2.1 Services Provided To the Network Layer

The Data Link Layer abstracts the physical medium and provides services to the
Network Layer (Layer 3):

1.​ Connectionless Service: Frames are sent independently without prior

connection setup. If a frame is lost, the Data Link Layer does not attempt
recovery (e.g., in Ethernet).
2.​ Connection-Oriented Service (Reliable): The layer establishes a
connection, transfers frames, and terminates the connection. This
guarantees delivery, handles sequencing, and recovers lost frames. Used
on unreliable physical channels (e.g., wireless links).

2.2 Framing

The Network Layer passes packets (datagrams) to the Data Link Layer. The Data
Link Layer must encapsulate these packets into frames. Framing is the process
of demarcating the start and end of a packet so the receiver knows exactly where
the data begins and ends.

●​ Methods of Framing:
○​ Character Count: Specifies the number of characters in the frame
header. Flaw: If the count is corrupted, synchronization is lost.

© 2025 [Link] team. All rights reserved.

 ○​ Start/End Flags with Character Stuffing: Uses special flag bytes
(e.g., 01111110) to mark frame boundaries. If the flag pattern
appears in the data, an escape byte is inserted (stuffed) to
distinguish it from the boundary flag.
○​ Start/End Flags with Bit Stuffing: Uses a flag pattern (e.g.,
01111110). If five consecutive '1's appear in the data stream, a '0' is
automatically inserted (stuffed) to prevent the pattern from matching
the flag. This is used in bit-oriented protocols like HDLC.
○​ Physical Layer Coding Violations: Used in high-speed LANs (e.g.,
Ethernet) where the physical coding scheme guarantees that certain
bit sequences cannot occur in valid data, using those reserved
sequences for frame boundaries.

2.3 Error Control

Ensuring that transmitted frames arrive at the destination without corruption. This
is often managed by adding redundancy in the form of Error Detecting and
Correcting Codes.

2.4 Flow Control

A mechanism to prevent a fast sender from overwhelming a slow receiver. If the

receiver's buffer fills up, it must signal the sender to slow down transmission.

●​ Techniques: Feedback mechanisms (receiver sends status reports) or

Rate-based mechanisms (sender limits its transmission rate).

3. Error Detecting and Error Correcting codes

Transmission media are noisy, leading to bit errors (a 0 flips to a 1, or vice versa).
Error control techniques are essential for reliable communication.

3.1 Error Detection Codes

These codes add enough redundancy to allow the receiver to determine if an

error has occurred, but usually not where it occurred.

© 2025 [Link] team. All rights reserved.

3.1.1 Parity Check

●​ Concept: The simplest form. A single bit (parity bit) is added to the data
block to make the total number of '1's either odd (odd parity) or even (even
parity).
●​ Limitation: Can only detect an odd number of bit errors (1, 3, 5, etc.).
Cannot detect an even number (2, 4, etc.).

3.1.2 Checksum

●​ Concept: The sender treats the data as a sequence of integers, calculates

their sum, and then takes the one's complement of that sum to create the
checksum. This checksum is appended to the data. The receiver re-sums
the data and the checksum; if the result is all 1s, the data is accepted.
●​ Application: Widely used in the Internet Layer (IP header) and Transport
Layer (TCP/UDP).

3.1.3 Cyclic Redundancy Check (CRC)

●​ Concept: A powerful, widely used error detection technique based on

polynomial arithmetic. The data (M) is treated as a high-order polynomial,
and it is divided by a predefined generator polynomial (G). The remainder
of the division (the CRC check bits) is appended to the message.
●​ Strength: CRC codes can reliably detect all single-bit errors, all double-bit
errors, any odd number of errors, and all burst errors shorter than the
degree of the generator polynomial.
●​ Application: Standardized for use in Ethernet, Wi-Fi, and other common
Data Link protocols.

3.2 Error Correcting Codes (ECC)

These codes contain enough redundant bits to allow the receiver to not only
detect an error but also precisely locate and correct the flipped bits.

3.2.1 Hamming Code

●​ Concept: A specific linear block code capable of detecting up to two

simultaneous bit errors and correcting all single-bit errors. It strategically
places parity bits in positions that are powers of two (1, 2, 4, 8, etc.).

© 2025 [Link] team. All rights reserved.

 ●​ Mechanism: The parity bits are calculated based on overlapping sets of
data bits. The receiving system recalculates the parity bits and combines
the results to form a syndrome word. The numerical value of the
syndrome word indicates the exact position of the error, allowing for
correction by simply flipping that bit.
●​ Application: Used primarily in memory (RAM) and other situations where
retransmission is difficult or impossible (e.g., satellite links).

4. Elementary Data Link Protocols

Elementary protocols are the foundational building blocks that illustrate the basic
principles of flow and error control.

4.1 Unrestricted Simplex Protocol

●​ Assumption: Ideal channel (no errors, infinite processing speed, infinite

buffer space).
●​ Function: Sender just sends data as fast as possible, and the receiver
immediately accepts it. Purely conceptual; unusable in real-world
scenarios.

4.2 Simplex Stop-and-Wait Protocol

●​ Assumption: Ideal channel (no errors) but with limited processing

speed/buffer space (introduces flow control).
●​ Mechanism: The sender sends one frame and immediately waits for an
acknowledgment (ACK) from the receiver before sending the next frame.
●​ Flow Control: Achieved by forcing the sender to wait. This is very
inefficient due to long idle times, especially over high-latency links.

4.3 Simplex Protocol for Noisy Channel

●​ Assumption: Channel is noisy (errors and losses can occur).

●​ Mechanism: Adds error control (e.g., sequence numbers and timers). If an
ACK is not received before a timer expires, the sender retransmits the
frame.

© 2025 [Link] team. All rights reserved.

 ●​ Issue: Requires 1-bit sequence numbers (0 or 1). However, the sender
can still receive a duplicate ACK or send a duplicate frame due to lost
ACKs, which 1-bit sequence numbers handle properly.

5. Sliding Window Protocols

The primary issue with Stop-and-Wait is low efficiency. Sliding Window
Protocols improve efficiency by allowing the sender to transmit multiple frames
before receiving an acknowledgment, managing a "window" of acceptable
unacknowledged frames.

5.1 Go-Back-N (GBN) Protocol

GBN is an efficient protocol that utilizes a cumulative acknowledgment system.

●​ Window Size: The sender maintains a window of size N > 1 . The

receiver's window size is always 1.
●​ Sender Mechanism: The sender can transmit up to N frames without
receiving an ACK. When the receiver sends an ACK for frame k , it
implicitly acknowledges all frames up to k-1 (cumulative
acknowledgment).
●​ Error Recovery: If a single frame ( i ) is lost or corrupted, the receiver
discards all subsequent frames (frames i+1, i+2, \dots ) until frame i is
correctly received. The sender, upon timing out, retransmits frame i and
all subsequent frames it had already sent (Go Back N frames).
●​ Efficiency: More efficient than Stop-and-Wait, but inefficient in high-error
environments as many correctly received frames are unnecessarily
retransmitted.

5.2 Selective Repeat (SR) Protocol

SR is the most efficient and complex of the sliding window protocols.

●​ Window Size: Both the sender and receiver maintain a window of size N .
Crucially, the maximum effective window size is N \le 2^k / 2 (where k is
the number of bits in the sequence number) to prevent ambiguity between
old and new frames.
●​ Sender Mechanism: The sender transmits frames within its window.

© 2025 [Link] team. All rights reserved.

 ●​ Receiver Mechanism: The receiver accepts and buffers any correct
frame, even if it arrives out of sequence. It sends a Negative
Acknowledgment (NAK) or an ACK only for the specific frame number it
has received (non-cumulative).
●​ Error Recovery: If frame i is lost, the sender only retransmits frame i
when the timer expires or a NAK is received. Subsequent frames are not
retransmitted, leading to high efficiency and better use of bandwidth.
●​ Complexity: Requires more complex buffering and sequence
management at the receiver.

6. Specific Data Link Protocols

Specific standardized protocols define the exact frame format, control fields, and
procedures used in synchronous and asynchronous communication.

6.1 High-level Data Link Control (HDLC)

HDLC is a bit-oriented, synchronous protocol used for point-to-point and

multipoint links. It uses the bit stuffing mechanism for framing.

●​ HDLC Frame Structure:​

○​ Flag (8 bits): Marks start/end (01111110).

○​ Address (8/16 bits): Secondary station address (not used in
point-to-point links).
○​ Control (8/16 bits): Defines frame type and carries sequence
numbers (N(S), N(R)) for flow and error control.
○​ Information (Variable): The data payload (Network Layer packet).
○​ FCS (16/32 bits): Frame Check Sequence (CRC) for error detection.
○​ Flag (8 bits): Marks start/end (01111110).
●​ Frame Types (Defined by the Control Field):​

○​ I-Frame (Information): Carries user data and performs flow/error

control.

© 2025 [Link] team. All rights reserved.

 ○​ S-Frame (Supervisory): Carries flow/error control commands
(ACKs, NAKs, requests to suspend transmission).
○​ U-Frame (Unnumbered): Used for link setup and disconnect.

6.2 Point-to-Point Protocol (PPP)

PPP is the standard protocol for carrying IP packets over dial-up or dedicated
point-to-point links (e.g., a home computer connecting to an ISP).

●​ Design Goals: PPP is robust, extensible, and supports many different

network protocols (not just IP).​

●​ PPP Components:​

1.​ Framing Method: Uses a byte-stuffing technique similar to HDLC

framing.
2.​ Link Control Protocol (LCP): Responsible for establishing,
configuring, and testing the data-link connection (e.g., determining
authentication methods and handling link quality).
3.​ Network Control Protocol (NCP): A family of protocols used to
configure parameters for various network-layer protocols (e.g., IPCP
for configuring IP addresses).
●​ PPP Phases:​

1.​ Dead: Link is down.

2.​ Establish: LCP brings the line up and negotiates parameters.
3.​ Authenticate: Optional phase using protocols like PAP or CHAP.
4.​ Network: NCP configures the Network Layer (IP).
5.​ Terminate: Link closure.

7. Multiple Access Protocols

When multiple nodes share a single broadcast channel (like a bus or a radio
frequency), a mechanism is needed to coordinate their transmissions to avoid
collisions. These mechanisms are called Medium Access Control (MAC)
protocols.

© 2025 [Link] team. All rights reserved.

7.1 Channel Partitioning

Divides the channel into smaller, independent "pieces" (time slots, frequencies, or
codes) that are allocated to each user.

●​ Time Division Multiple Access (TDMA): Divides time into fixed-length

slots; each station gets a slot.
●​ Frequency Division Multiple Access (FDMA): Divides the channel into
frequency bands; each station transmits on its own band.
●​ Code Division Multiple Access (CDMA): Allows all stations to transmit
simultaneously over the entire bandwidth; signals are separated using
unique coding sequences.

7.2 Random Access Protocols

Nodes access the channel randomly, but use collision avoidance or detection
techniques.

7.2.1 ALOHA

●​ Pure ALOHA: Simplest model. Stations transmit whenever they have data.
If a collision occurs, the sender waits a random amount of time and
retransmits. Very low efficiency (max throughput 18%).
●​ Slotted ALOHA: Time is divided into discrete slots. Stations are only
allowed to transmit at the beginning of a slot. Halves the vulnerable period
for collisions, increasing max throughput to 37%.

7.2.2 Carrier Sense Multiple Access (CSMA)

Stations first listen to the channel (carrier sensing) before transmitting.

●​ CSMA/Persistence: Defines what a station does if the channel is busy:

○​ 1-Persistent: Transmit immediately with probability 1 when the
channel becomes idle.
○​ Non-Persistent: Wait a random amount of time and sense again.
○​ p-Persistent: Used for slotted channels; transmit with probability p .

7.2.3 Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

The protocol used by traditional Ethernet.

© 2025 [Link] team. All rights reserved.

 ●​ Mechanism: A station senses the carrier. If idle, it transmits. If busy, it
waits. Crucially, the station continues to listen while transmitting.
●​ Collision Detection: If two stations transmit simultaneously, they detect
the collision quickly (by sensing an abnormal signal level), immediately
stop transmitting, send a brief jam signal to notify others, and then wait a
random backoff time before attempting retransmission.
●​ Requirement: For collision detection to work, the frame must be long
enough so that the sender is still transmitting when the signal reaches the
furthest possible point and returns (round-trip time). This defines the
minimum Ethernet frame size.

8. Wired LANs: Ethernet Standards

Ethernet, defined by the IEEE 802.3 standards, is the most common LAN
technology.

8.1 Classic Ethernet (IEEE 802.3)

●​ Data Rate: 10 Mbps.

●​ Media Access: Uses CSMA/CD to manage shared access on bus or
hub-based networks.
●​ Naming Convention: Base (Bandwidth in Mbps) Base (Signaling Type)
Media Type. E.g., 10BASE5 (10 Mbps, Baseband, 500m thick coaxial).

8.2 Fast Ethernet (100 Mbps)

Developed to meet the demand for higher bandwidth in the 1990s.

●​ Data Rate: 100 Mbps.

●​ Standard: IEEE 802.3u.
●​ Technology: Primarily uses Twisted Pair (UTP) Cat 5 or better.
●​ MAC Protocol: Initially designed for shared hubs using CSMA/CD, but
became most effective when implemented over switches (creating
point-to-point connections), effectively bypassing the contention inherent in
CSMA/CD while maintaining the frame format.
●​ Naming Examples: 100BASE-TX (Cat 5 UTP), 100BASE-FX (Fiber
Optic).

© 2025 [Link] team. All rights reserved.

8.3 Gigabit Ethernet (1000 Mbps)

A major leap forward in speed, allowing high-performance backbone networking.

●​ Data Rate: 1000 Mbps (1 Gbps).

●​ Standard: IEEE 802.3z (fiber) and 802.3ab (copper).
●​ CSMA/CD Adaptation: In Gigabit Ethernet over shared media (hubs), the
time required to detect a collision became too small relative to the speed.
Thus, Gigabit Ethernet introduced carrier extension and frame bursting to
ensure the minimum collision detection window was met. However, it is
almost exclusively deployed in full-duplex, switched environments,
where CSMA/CD is disabled entirely as there are no collisions.
●​ Naming Examples: 1000BASE-LX (Long wavelength fiber), 1000BASE-T
(Cat 5e/6 UTP).

© 2025 [Link] team. All rights reserved.