Computer Networks | Unit 3: Data Link Layer | Student Study Notes

COMPUTER NETWORKS

Unit 3: Data Link Layer

(8 Hours) | BCA / [Link] | Student Notes with PPT Figures

The Data Link Layer Engine — Framing, Flow & Error Control

Syllabus Coverage
3.1 Functions of the Data Link Layer
3.2 LLC and MAC Sub-layers
3.3 Framing & Flow Control (Stop-Wait, Go-Back-N, Selective Repeat)
3.4 Error Detection & Correction (Parity, Checksum, CRC, Hamming Code)
3.5 Channel Allocation: Pure ALOHA, Slotted ALOHA, CSMA Variants
3.6 Ethernet Standards: IEEE 802.3 (CSMA/CD), 802.4 (Token Bus), 802.5 (Token Ring)
3.7 Wireless LAN: FHSS, DSSS, CSMA/CA, Bluetooth, Wi-Fi
3.8 Virtual Circuit Switching, Frame Relay & ATM
3.9 DLL Protocols: HDLC and PPP

Page 1 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.1 Functions of the Data Link Layer (DLL)

The Three Core Problems: Framing (Boundary), Flow Control (Pace), Error Control (Noise)

Raw chaotic bits enter the DLL Processor — structured, paced, protected frames exit

What is the Data Link Layer?

The DLL is Layer 2 of the OSI model — between the Physical Layer (raw bits) and the Network
Layer (IP packets).

Page 2 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Simple analogy: Physical Layer = the road. Data Link Layer = the traffic management system.
It ensures data travels from one end of a link to the other — correctly, efficiently, without chaos.

Core Functions
(A) Framing: Divides the raw bit stream into discrete, identifiable units called Frames (Header +
Payload + Trailer).
(B) Physical Addressing (MAC): Each NIC has a 48-bit MAC address. DLL header carries source and
destination MAC.
(C) Error Detection: Appends FCS (CRC-32) so the receiver can detect bit corruption caused by
noise.
(D) Error Correction (FEC): Hamming codes let the receiver locate and correct single-bit errors
without retransmission.
(E) Flow Control: Sliding window mechanisms prevent a fast sender from overflowing the receiver's
buffer.
(F) Channel Access Control: Decides which station transmits when multiple devices share a medium:
CSMA/CD, CSMA/CA, Token Passing.

DLL Service Types

Setup
Service Type Acknowledgements Typical Use
Needed?
Unacknowledged Ethernet — errors are rare; TCP handles
No No ACKs
Connectionless reliability
Acknowledged Each frame ACKed Wi-Fi 802.11 — wireless links are
No
Connectionless individually unreliable
Acknowledged Frames sequenced +
Yes, first HDLC over WAN serial links
Connection-Oriented ACKed

Page 3 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.2 LLC and MAC Sub-layers

Why Two Sub-layers?
IEEE 802 splits the DLL into two parts to allow flexibility:

LLC (Logical Link Control — 802.2): UPPER sub-layer. Medium-INDEPENDENT.

Provides a consistent interface to the Network Layer regardless of physical technology.

MAC (Media Access Control — 802.3/802.11): LOWER sub-layer. Medium-SPECIFIC.

Handles access to the specific physical medium.

Result: The same LLC can work above Ethernet, Wi-Fi, Token Ring — without any changes.

LLC vs MAC Comparison

Feature LLC MAC
Position in DLL Upper sub-layer Lower sub-layer
802.3 (Ethernet), 802.11 (Wi-Fi), 802.5
IEEE Standard 802.2
(Token Ring)
Faces toward Network Layer above Physical Layer below
Framing, error control, flow control, Channel access, MAC addressing,
Key Responsibilities
multiplexing frame delimiting, CRC
Medium-SPECIFIC (Ethernet MAC
Medium dependency Medium-INDEPENDENT
differs from Wi-Fi MAC)

MAC Address Structure

48-bit MAC Address: Written as 2A:4B:B3:45:C3:B4
Bytes 1–3 = OUI (Organizationally Unique Identifier): IEEE assigns to the manufacturer.
Bytes 4–6 = Device ID: Manufacturer assigns to each individual NIC.

FF:FF:FF:FF:FF:FF = Broadcast address — deliver to ALL devices on the segment.

Note: MAC addresses work only within a single network segment.

Routers use IP addresses to move packets between segments.

Page 4 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.3 Framing and Flow Control Mechanisms

3.3.1 The Four Framing Methods

All Four Framing Methods — Character Count, Byte Stuffing, Bit Stuffing, Coding Violations

Method 1 — Character Count

Character Count: a single bit flip in the count field desynchronises all subsequent frames

Page 5 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

The Fatal Flaw of Character Count — cascading desynchronisation

Character Count
HOW IT WORKS:
First byte of each frame holds total byte count (including itself).
Example: Frame 1: [5 | A B C D] Frame 2: [4 | E F G]

FATAL FLAW:
If the count byte is corrupted by noise (5 becomes 4), the receiver draws a boundary
one byte too early. The rest of the stream is permanently misaligned.
All subsequent frames are lost — cascading failure.

STATUS: Rarely used in modern protocols due to this catastrophic vulnerability.

Page 6 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Method 2 — Byte Stuffing (PPP)

Byte Stuffing in PPP — ESC bytes injected wherever FLAG appears in data

Byte Stuffing (PPP) vs Bit Stuffing (HDLC) — side-by-side comparison

Byte Stuffing Rules (PPP: Flag=0x7E, Escape=0x7D)

Original data: A B [0x7E] C [0x7D] D
After stuffing: 0x7E | A B 0x7D 0x5E C 0x7D 0x5D D | 0x7E
^ Start flag ^ End flag

Page 7 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Receiver decoding rules:

ESC + 0x5E --> 0x7E (original FLAG byte restored)
ESC + 0x5D --> 0x7D (original ESC byte restored)

Used by: PPP (dial-up modem, DSL connections)

Method 3 — Bit Stuffing (HDLC)

Bit Stuffing in HDLC — a 0 is inserted after every five consecutive 1s

Bit Stuffing Rules (HDLC: Flag = 01111110)

THREAT: The flag pattern 01111110 could appear naturally inside data.
If it does, the receiver would mistakenly think the frame has ended.

SENDER RULE: Scan data bit by bit.

After every 5 consecutive 1s --> INSERT (stuff) a 0 bit.

RECEIVER RULE: Scan data bit by bit.

After every 5 consecutive 1s --> REMOVE (destuff) the next 0.

Worked Example:
Original: 0 1 1 1 1 1 1 0 1
Stuffed: 0 1 1 1 1 1 [0] 1 0 1 <-- 0 inserted after five 1s

The flag 01111110 will ONLY appear at genuine frame boundaries.

Used by: HDLC, USB (stuffs after 6 ones for clock recovery)

Page 8 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Method 4 — Physical Layer Coding Violations

Physical Coding Violations
Some encoding schemes have signal patterns that are ILLEGAL during normal data.
These illegal patterns can safely mark frame start and end — zero data overhead.

Example: Manchester encoding (used by 802.4 Token Bus):

Bit 1 = high-to-low transition at mid-bit
Bit 0 = low-to-high transition at mid-bit
No transition at all = ILLEGAL --> used as frame delimiter

3.3.2 Flow Control — The Pace Problem

Flow Control: High-capacity sender vs slow receiver buffer — buffer overflow destroys data

Page 9 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Feedback-based Control (preferred DLL approach) vs Rate-based Control

Why Flow Control is Needed

If a fast sender transmits faster than the receiver can process:
--> Receiver input buffer overflows
--> Frames are SILENTLY DROPPED (lost permanently)
--> Higher-layer protocols must retransmit everything, wasting bandwidth

SOLUTION — Feedback-Based Flow Control:

Receiver sends feedback (ACK / RNR — Receive Not Ready) back to the sender.
Sender adjusts rate based on feedback.
Used in HDLC, TCP.

Page 10 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.3.3 Stop-and-Wait ARQ

Stop-and-Wait: Send one frame, stop, wait for ACK, then send the next

Stop-and-Wait: The shaded IDLE WAITING GAP is pure wasted bandwidth

Stop-and-Wait — Four Scenarios

(a) NORMAL: Frame 0 sent --> ACK 0 received --> Frame 1 sent --> ...
(b) FRAME LOST: Frame never arrives --> sender timer expires --> retransmit same frame
(c) ACK LOST: Frame OK but ACK lost --> sender retransmits --> receiver discards duplicate,

Page 11 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

resends ACK
(d) DAMAGED: CRC error detected --> receiver sends NAK --> sender retransmits
immediately

Efficiency: eta = 1 / (1 + 2a) where a = propagation_delay /

frame_transmission_time

Numerical Example — Why Stop-and-Wait Fails on Long Links

Satellite link: Propagation delay = 250 ms, Frame tx time = 1 ms
a = 250 / 1 = 250
eta = 1 / (1 + 2 x 250) = 1 / 501 ≈ 0.2%

The link sits IDLE 99.8% of the time! Sliding Window protocols fix this.

3.3.4 Go-Back-N ARQ

Go-Back-N (Window=4): Frame 1 lost → NAK → Frames 1,2,3,4 ALL retransmitted — wasteful

Go-Back-N Rules
Window size N: sender can keep up to N unacknowledged frames in flight simultaneously.

On error: Retransmit the damaged frame AND ALL frames sent after it.
Receiver: Discards ALL out-of-order frames. Buffers only 1 frame at a time.

Advantage: Much higher throughput than Stop-and-Wait.

Disadvantage: Wastes bandwidth retransmitting already-received frames.

Efficiency (N < 2a+1): eta = N / (1 + 2a)

Page 12 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Efficiency (N >= 2a+1): eta = 1 (100% utilisation)

Numerical Example
Window N = 7, propagation a = 5
eta = 7 / (1 + 10) = 7/11 = 63.6%

If N = 11: eta = 11/11 = 100% (window completely fills the pipe)

3.3.5 Selective Repeat ARQ

Selective Repeat: Only Frame 2 retransmitted; Frames 3 and 4 buffered — maximum efficiency

Page 13 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Side-by-Side: Go-Back-N discards all; Selective Repeat buffers and fills the gap

Selective Repeat Rules

On error: Retransmit ONLY the specific damaged or lost frame.
Receiver: Accepts and BUFFERS out-of-order frames, reorders before delivery.
Receiver needs larger buffer = window size N frames.

Window size restriction: max window <= 2^(n-1) to prevent sequence number ambiguity
(n = number of bits in sequence number field)

Same efficiency formula as GBN — but with NO wasted retransmissions.

Page 14 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.3.6 ARQ Protocol Comparison

ARQ Efficiency Matrix — Stop-and-Wait (Low), Go-Back-N (Medium), Selective Repeat (High)

Windo Rcvr
Protocol Retransmit Scope Efficiency Best For
w Buffer
Stop-and-Wait 1 Current frame only 1 frame 1/(1+2a) Simple short links
Error frame + all
Go-Back-N Up to N 1 frame N/(1+2a) Low-error links
after
Up to
Selective Repeat Only the bad frame N frames N/(1+2a)* High-error/long-delay links
N/2

Page 15 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.4 Error Detection and Correction

Single Bit Error (brief static) vs Burst Error (sustained noise) — burst is the real threat

Types of Errors
Single-Bit Error: Only 1 bit flips. Most rare. Example: 10110 --> 10100
Multiple-Bit Error: 2+ non-adjacent bits flip.
Burst Error: A CONTIGUOUS run of bits corrupted by sustained interference.
Most common in practice — noise affects milliseconds = many bits.
Burst length = distance from first to last corrupted bit.

Page 16 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.4.1 Parity Check

Parity Check (scale balance) and Checksum (one's complement wrap-around addition)

Even Parity — Worked Example

Data: 1 0 1 0 1 1 0 (four 1s — already even)
Parity bit: 0 (keep total even)
Transmitted: 0 | 1 0 1 0 1 1 0

At receiver: recount all 1s. If count is ODD --> error detected.

DETECTS: All single-bit errors. Any ODD number of bit flips.

MISSES: Any EVEN number of flips (2, 4, 6 ... flips leave parity unchanged).
CANNOT: Correct errors — only detect them.

3.4.2 Checksum (One's Complement)

Checksum — Sender and Receiver Steps
SENDER: RECEIVER:
Seg1: 1001 1001 1001 1001
+ Seg2: 1110 0110 + 1110 0110
Sum: 10111 1111 + 0111 1111 (checksum)
Wrap carry: 1000 0000 = 1111 1111 --> all 1s --> NO ERROR
Complement: 0111 1111 <-- append

Used by: TCP and UDP (16-bit Internet Checksum), IPv4 header checksum.

Page 17 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.4.3 CRC — Cyclic Redundancy Check

CRC XOR Division — M=110010, G=1101: remainder 110 appended to form codeword 110010110

CRC Algorithm — Sender and Receiver

SENDER:
1. Given data M and generator G of degree r.
2. Append r zeros to M.
3. XOR-divide (M x 2^r) by G.
4. Remainder R = CRC / FCS value.
5. Transmit: original M followed by R.

RECEIVER:
1. Divide received codeword (M+R) by same G using XOR.
2. Remainder = 000 --> No error detected. Accept frame.
3. Remainder ≠ 000 --> Error detected. Discard frame.

CRC-32 (used in Ethernet): Detects ALL single-bit, double-bit, burst <= 32 bits errors.
Detects 99.99997% of all longer burst errors.

Generator
CRC Standard Used In
Degree
CRC-8 8 bits ATM header, SMBus
CRC-16 16 bits USB, HDLC, Modbus serial
CRC-32 32 bits Ethernet 802.3, Wi-Fi 802.11, ZIP, PNG, SATA
CRC-64 64 bits HDLC extended, iSCSI, ISO 3309

Page 18 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.4.4 Hamming Code — Error Correction (FEC)

Hamming(7,4): P1+P2 fail, P4 passes => syndrome 011 = position 3 => flip bit 3 to correct

Hamming(7,4) Construction
Positions: 1 2 3 4 5 6 7
Content: P1 P2 D1 P4 D2 D3 D4
(parity bits at powers of 2; data bits fill the rest)

P1 covers positions: 1, 3, 5, 7 (positions whose binary value has bit-0 set)

P2 covers positions: 2, 3, 6, 7 (positions whose binary value has bit-1 set)
P4 covers positions: 4, 5, 6, 7 (positions whose binary value has bit-2 set)

Each parity bit is set so XOR of all its covered positions = 0 (even parity).

Syndrome Error Location — Worked Example

Assume error occurred at position 5.
P1 covers position 5 --> P1 FAILS (contributes 1)
P2 does NOT cover 5 --> P2 PASSES (contributes 0)
P4 covers position 5 --> P4 FAILS (contributes 1)

Syndrome = P4 P2 P1 = 1 0 1 = binary 101 = decimal 5

--> Error is at bit position 5 --> FLIP bit 5 --> corrected!

No retransmission needed. Real use: ECC RAM in servers.

Page 19 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.5 Channel Allocation Techniques

The Problem
When multiple stations share a single broadcast channel:
Simultaneous transmissions COLLIDE and destroy each other's data.

Goal: Allocate the shared channel fairly and efficiently among N competing stations.

3.5.1 Pure ALOHA

Pure ALOHA — Operation
Simple rule: Transmit whenever you have data.
If collision occurs --> wait a RANDOM time --> retransmit.

Vulnerable period = 2t (a new frame can collide during [T-t, T+t])

Throughput: S = G x e^(-2G)
Maximum at G = 0.5: S_max = 0.5 x e^(-1) ≈ 18.4%

Even under ideal load, Pure ALOHA wastes 81.6% of channel capacity!

Pure ALOHA: S = G x e^(-2G) --> S_max ≈ 18.4% at G = 0.5

3.5.2 Slotted ALOHA

Slotted ALOHA — Key Improvement
Time is divided into SLOTS of exactly 1 frame-transmission-time each.
Stations may ONLY start transmitting at slot boundaries.
Partial overlaps are eliminated -- two frames either collide completely or not at all.

Vulnerable period = t (only half of Pure ALOHA's vulnerable period)

Throughput: S = G x e^(-G)
Maximum at G = 1.0: S_max = 1 x e^(-1) ≈ 36.8%

EXACTLY DOUBLE the throughput of Pure ALOHA!

Requirement: All stations must synchronise to slot boundaries (shared clock).

Slotted ALOHA: S = G x e^(-G) --> S_max ≈ 36.8% at G = 1.0

Property Pure ALOHA Slotted ALOHA

Timing Any time (fully async) Slot boundaries only (sync)
Vulnerable period 2t (two frame lengths) t (one frame length)
Maximum throughput ≈ 18.4% at G = 0.5 ≈ 36.8% at G = 1.0

Page 20 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Property Pure ALOHA Slotted ALOHA

Partial collisions Possible Impossible
Synchronisation Not required Required (shared clock)

3.5.3 CSMA Variants

CSMA — Carrier Sense Multiple Access: Listen before you transmit
1-Persistent: If idle --> transmit immediately (p=1). If busy --> keep listening, then transmit.
Highest collision rate when multiple stations wait simultaneously.

Non-Persistent: If idle --> transmit. If busy --> wait RANDOM time, sense again.
Lower collision rate, slightly higher idle time. Best overall throughput.

p-Persistent: If idle --> transmit with probability p, defer to next slot with (1-p).
Tunable trade-off between collision probability and delay.

Page 21 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.6 Ethernet Standards (IEEE 802)

Standard Protocol Speed Topology Use Case
10 Mbps to 400 General LAN — dominant
IEEE 802.3 CSMA/CD — Ethernet Bus or Star
Gbps worldwide
Industrial automation (now
IEEE 802.4 Token Bus 1, 5, or 10 Mbps Physical Bus
obsolete)
IBM corporate LAN (now
IEEE 802.5 Token Ring 4 or 16 Mbps Physical Ring
obsolete)
1 Mbps to 10+
IEEE 802.11 Wi-Fi CSMA/CA Wireless WLANs everywhere
Gbps

3.6.1 IEEE 802.3 — CSMA/CD (Ethernet)

CSMA/CD Algorithm — Step by Step
1. Assemble frame to send.
2. If channel idle for ≥ 96 bit-times (IFG = Inter-Frame Gap) --> start transmitting.
3. If channel busy --> wait until idle, then transmit (1-persistent).
4. While transmitting: continuously MONITOR channel for collision (received signal ≠
transmitted).
5. Collision detected --> STOP sending data immediately.
6. Send 32-bit JAM signal so ALL stations on the segment detect the collision.
7. Increment collision counter. If counter > 16 --> abort, report failure.
8. Binary Exponential Back-off: wait random number of slot-times from {0 ... 2^min(n,10)-1}.
9. Go back to step 2 and retry.

Why Ethernet Has a 64-Byte Minimum Frame Size

CSMA/CD requires the sender to still be transmitting when a collision signal returns.
At 10 Mbps on max 2500 m cable: round-trip propagation = 51.2 µs = 512 bits = 64 bytes.
Minimum Ethernet frame = 64 bytes. Shorter payloads are padded to 46 bytes of data.

3.6.2 Ethernet Frame Format (IEEE 802.3)

[ Preamble 7B ][ SFD 1B ][ Dst MAC 6B ][ Src MAC 6B ][ Length/Type 2B ][ Data 46-
1500B ][ FCS 4B ]
Preamble (7B): 10101010 x7 -- alternating bits let receiver sync its clock
SFD (1B): 10101011 -- 'frame starts now'
Dst MAC (6B): Unicast / Multicast (bit-0=1) / Broadcast (FF:FF:FF:FF:FF:FF)
Src MAC (6B): Always unicast (sender's NIC address)
Length/Type (2B): <= 1500 = data length; >= 0x0600 = EtherType (IPv4=0x0800)
Data (46-1500B): IP datagram. Padded to minimum 46 bytes if shorter.
FCS (4B): CRC-32 over Dst+Src+Length+Data. Checked by receiver.

Page 22 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.6.3 IEEE 802.4 — Token Bus

Token Bus — Physical Bus, Logical Ring
Physical layout: A ─────────── B ─────── C ─── D (shared coaxial bus)
Logical ring: A --> C --> D --> B --> A (order set by admin)

Only the station holding the TOKEN may transmit. NO COLLISIONS ever.
1. Token holder transmits queued frames.
2. Passes token to logical successor (not physical neighbour).
3. Process repeats around the logical ring.

Advantage: Deterministic access time -- vital for industrial real-time control.

Status: Largely OBSOLETE. Was used in MAP (Manufacturing Automation Protocol).

3.6.4 IEEE 802.5 — Token Ring

Token Ring — Detailed Operation
1. A FREE TOKEN circulates clockwise around the physical ring.
2. A station wanting to transmit captures the free token (changes FREE to BUSY).
3. Transmits its data frame -- the frame travels the ENTIRE ring.
4. Each station passes the frame along; DESTINATION station copies the data.
5. Frame returns to the originating station -- originator REMOVES the frame.
6. Originator releases a new FREE token for the next station.

Result: Deterministic. Fair. No collisions. Each station gets a turn.

Feature 802.3 Ethernet 802.4 Token Bus 802.5 Token Ring

Physical topology Bus or Star Physical Bus Physical Ring
Logical topology Bus Ring Ring
Access method CSMA/CD (random) Token Passing Token Passing
Collisions possible Yes -- CD + backoff No No
Access deterministic No Yes Yes
Original speed 10 Mbps 1/5/10 Mbps 4 or 16 Mbps
Current status Dominant (GbE, 10GbE) Obsolete Obsolete

Page 23 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.7 Wireless LAN: Spread Spectrum, Bluetooth, Wi-Fi

Wireless Challenges vs Wired Networks
Open shared medium -- any station in range can receive and interfere
Signal drops with distance (inverse-square law)
Multipath fading -- signal reflections cause interference
Half-duplex radio: cannot simultaneously transmit AND detect collisions --> CSMA/CD
impossible
Hidden station and exposed station problems

3.7.1 Hidden Station and Exposed Station Problems

Hidden Station Problem
Setup: A <--100m--> B <--100m--> C (A and C are out of each other's range)

Problem: A transmits to B. C senses channel, hears NOTHING (cannot hear A),

also starts transmitting to B. COLLISION at B.
Neither A nor C detects the collision.

Solution: RTS/CTS handshake (optional in 802.11).

Exposed Station Problem

B transmits to C. A (near B but far from C) wants to send to D (far from B).
A hears B's transmission and unnecessarily DEFERS --
even though A --> D would not interfere with B --> C at all.

Result: Wasted channel capacity.

3.7.2 Spread Spectrum Techniques

FHSS — Frequency Hopping Spread Spectrum
Transmitter and receiver use the SAME pseudo-random hopping sequence.
Hop simultaneously through 79 channels (1 MHz each) in the 2.4 GHz ISM band.

Bluetooth FHSS: 79 channels x 1 MHz, 1600 hops per second

IEEE 802.11 FHSS: 79 channels x 1 MHz, dwell time max 400 ms

Resistant to narrow-band jamming and eavesdropping.

DSSS — Direct Sequence Spread Spectrum

Each data bit is replaced by a longer CHIPPING CODE (Barker sequence: 11 chips).

Bit 1 --> chips: 1 0 1 1 0 1 1 1 0 0 0

Page 24 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Bit 0 --> chips: 0 1 0 0 1 0 0 0 1 1 1 (complement of above)

Signal spread over 22 MHz bandwidth. Even if some chips are corrupted,
the receiver can recover the original bit using cross-correlation.
Used by: IEEE 802.11b (11 Mbps)

3.7.3 Wi-Fi MAC — CSMA/CA (IEEE 802.11)

CSMA/CA — Collision Avoidance (because CD is impossible on radio)
1. Sense channel for DIFS (DCF Inter-Frame Space) time.
2. If idle --> transmit.
3. If busy --> wait until idle, then run BACKOFF procedure.
Pick random slot-count from contention window; count down when channel is idle.
4. Receiver sends ACK after SIFS (Short IFS) if frame received correctly.
5. No ACK received --> assume collision --> double contention window --> retry.

RTS/CTS Optional Mode (solves hidden station problem):

RTS: Sender broadcasts Request-to-Send -- nearby stations defer (set NAV timer).
CTS: Receiver replies Clear-to-Send -- ALL stations in receiver range also defer.
This ensures hidden stations cannot interfere during the data exchange.

3.7.4 Bluetooth (IEEE 802.15.1)

Parameter Value
Frequency band 2.400 to 2.4835 GHz (ISM band)
Number of channels 79 channels x 1 MHz spacing
Hopping rate 1,600 frequency hops per second
Spread spectrum FHSS
Range (Class 2) approximately 10 metres
Data rates BT 1.x: 1 Mbps BT 2.0+EDR: 3 Mbps BT 5.0: 2 Mbps (2x range)
Piconet 1 master + up to 7 active slaves (255 parked)
Security FHSS + 128-bit AES encryption (BT 4.2+)

Page 25 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.8 Virtual Circuit Switching, Frame Relay and ATM

3.8.1 Virtual Circuit Switching
Three Phases
PHASE 1 — SETUP:
Source sends call request. Each router along chosen path reserves resources
and records VCI mapping. Destination confirms. Circuit established.

PHASE 2 — DATA TRANSFER:

All packets follow the same pre-established path.
Each packet carries only a small VCI number (not a full address) -- very fast switching.

PHASE 3 — TEARDOWN:
Source sends release packet. Routers remove VCI entries, free resources.

Feature Virtual Circuit Datagram (IP)

Path Fixed -- all packets same route Each packet routed independently
Setup overhead Required None (stateless)
Packet header Small (VCI number only) Large (full src+dst address)
Ordering Guaranteed in-order delivery Can arrive out of order
QoS guarantee Yes -- resources reserved No -- best effort only
Fault tolerance Low -- path must rebuild on failure High -- packets reroute automatically
Examples ATM, Frame Relay, MPLS IP Internet, Ethernet

3.8.2 X.25 vs Frame Relay

Feature X.25 Frame Relay
Speed Up to 64 kbps Up to 45 Mbps (T3)
Error correction At every hop (L1-L3) Detection only (L1-L2)
Header overhead High Low (2-byte DLCI)
Era 1975-1995 1990s-2000s
Link assumption Analogue -- noisy Digital -- clean

3.8.3 ATM — Asynchronous Transfer Mode

ATM Fixed Cell = 53 bytes (Header 5B + Payload 48B)
WHY 53 BYTES?
Europe wanted 32-byte payload (low voice latency).
North America wanted 64-byte payload (data efficiency).
Compromise: 48 bytes payload + 5 bytes header = 53 bytes.

Page 26 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

ADVANTAGE of fixed size: Hardware switches process cells at full line speed.
No variable-length parsing needed -- enables Gbps switching in silicon.

Header fields:
VPI (8 bits): Virtual Path Identifier -- groups multiple VCIs between same two switches.
VCI (16 bits): Virtual Channel Identifier -- identifies specific virtual circuit.
HEC (8 bits): CRC-8 over header -- corrects single-bit header errors.
CLP (1 bit): Cell Loss Priority -- CLP=1 cells may be dropped under congestion.

Catego
Full Name Description Example Use
ry
CBR Constant Bit Rate Fixed guaranteed bandwidth + delay Voice calls, videoconferencing
VBR Variable Bit Rate Bursty traffic with QoS guarantee Compressed video (MPEG)
ABR Available Bit Rate Uses spare capacity, no strict QoS File transfer
Unspecified Bit
UBR Best-effort, no QoS Email, web browsing
Rate

Page 27 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

3.9 DLL Protocols: HDLC and PPP

3.9.1 HDLC — High-Level Data Link Control
What is HDLC?
HDLC is a bit-oriented, synchronous DLL protocol standardised by ISO.
It is the PARENT of virtually all modern synchronous DLL protocols:
PPP, LAPB (X.25), LAPD (ISDN), LAP-F (Frame Relay) -- all derived from HDLC.

Station Types
Station Type Role Issues / Receives
Controls the link. Polls secondaries. Manages error recovery.
Primary Issues Commands
Usually a router.
Operates under primary control. Cannot initiate without being
Secondary Sends Responses
polled.
Both Commands and
Combined Combines both roles. Used in peer-to-peer balanced links.
Responses

Transfer Modes
Mode Full Name Who Initiates Used For
Only Primary (secondaries
NRM Normal Response Mode Multi-point terminal networks
polled)
Asynchronous Response Secondary (when channel
ARM Unbalanced point-to-point
Mode idle)
Asynchronous Balanced
ABM Either combined station Balanced P2P -- used by PPP, LAPB
Mode

HDLC Frame Types

Frame Type Identifier Sequence Nos Purpose
I-frame
Bit 0 = 0 N(S) + N(R) Carries user data. N(R) piggybacks ACK.
(Information)
S-frame
Bits 0-1 = 10 N(R) only Flow/error control: RR, RNR, REJ, SREJ
(Supervisory)
U-frame
Bits 0-1 = 11 None Link management: set mode, disconnect, UA
(Unnumbered)

HDLC Frame Format: [ Flag | Address | Control | Data | FCS | Flag ]

Flag (1B): 01111110 -- start/end delimiter; bit stuffing prevents this in data
Address: Identifies secondary station in unbalanced mode
Control: Frame type (I/S/U) + sequence numbers N(S), N(R) + P/F bit
Data: User payload (I-frames only; absent in S/U frames)

Page 28 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

FCS (2-4B): CRC-16 or CRC-32 over Address+Control+Data

3.9.2 PPP — Point-to-Point Protocol

What is PPP and where is it used?
PPP (RFC 1661) is the standard DLL protocol for serial point-to-point links.

Used for: Home user dialling into ISP over modem

Two routers connected by a leased serial line
DSL customers (PPPoE -- PPP over Ethernet)

Key design choices vs HDLC:

NO flow control at DLL (left to TCP) | YES multi-protocol support (Protocol field)
NO error correction (FCS detection only) | YES link negotiation via LCP
| YES authentication: PAP or CHAP

PPP Sub-protocols
Sub-
Full Name Purpose
protocol
Link Control Negotiates link parameters: frame size, compression, auth method, loop
LCP
Protocol detection
Network Control Family: IPCP (IPv4), IPv6CP, IPXCP. Assigns IP addresses per NL
NCP
Protocol protocol.
Password Auth
PAP Simple plaintext: client sends username+password. Weaker.
Protocol
Challenge Challenge-response with MD5. Password never sent over the link.
CHAP
Handshake Auth Stronger.

PPP Frame: [ 0x7E | 0xFF | 0x03 | Protocol 2B | Data 0-1500B | FCS | 0x7E ]
Flag (0x7E): Start/end delimiter. Byte stuffing: 0x7E in data --> 0x7D 0x5E
Address (0xFF): Always broadcast -- PPP is point-to-point, addressing unnecessary
Control (0x03): Unnumbered info -- no sequence numbers at DLL
Protocol (2B): 0x0021=IPv4, 0x0057=IPv6, 0xC021=LCP, 0x8021=IPCP
Data (0-1500B): Network Layer packet. MRU negotiated by LCP (default 1500B)
FCS (2-4B): CRC-16 or CRC-32 -- detection only

PPP Connection Phases: Dead --> Establish --> Authenticate --> Network --> Open -->
Terminate
Dead: No physical connection.
Establish: LCP negotiates frame size, auth method, compression.
Authenticate: Optional. PAP or CHAP verifies the user.
Network: NCP(s) configure NL protocols. IPCP assigns IP addresses.
Open: Data flows. LCP monitors with Echo-Request/Echo-Reply.

Page 29 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Terminate: Either side sends LCP Terminate-Request to close gracefully.

3.9.3 HDLC vs PPP

Feature HDLC PPP
Orientation Bit-oriented Byte-oriented (derived from HDLC)
Topology P2P and multi-point Point-to-point only
Addressing Full for multi-point Always 0xFF (redundant on P2P)
Flow control Yes -- sliding window N(R)/N(S) None at DLL
Error correction Yes -- GBN or SR Detection only via FCS
Multi-protocol No Yes -- Protocol field
Link negotiation None LCP negotiates all parameters
Authentication None PAP or CHAP
Dial-up, DSL PPPoE, leased WAN
Applications X.25, ISDN, LAPB, LAPD
serial

Page 30 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Unit 3 — Complete Summary and Key Formulas

The Complete DLL Engine: Raw Input --> Framing --> Error Control --> ARQ Flow Control --> Output

Topic Summary Table

Section Core Topics Key Terms
3.1 DLL
Framing, MAC addressing, error detect/correct, flow control, Frame, FCS, ACK, NAK, LLC,
Functio
channel access MAC
ns
3.2 LLC LLC=medium-independent (framing, flow, multiplex). OUI, NIC, 802.2, 802.3,
& MAC MAC=medium-specific (access, addr, delimiting) FF:FF:FF:FF:FF:FF
3.3
4 framing methods. ARQ protocols: Stop-Wait, Go-Back-N, Bit stuffing, ARQ, window N, a =
Framing
Selective Repeat. Sliding window. prop/tx
& ARQ
3.4
Error Parity (single-bit detect). Checksum (one's complement). CRC CRC-32, FCS, Hamming(7,4),
Detectio (strongest). Hamming (FEC correct). syndrome
n
3.5
Pure ALOHA 18.4%, Slotted ALOHA 36.8%, CSMA variants
Channe G load, S throughput, 2t vs t
(1-persistent, non, p)
l Alloc
3.6
CSMA/CD+backoff (802.3), Token Bus (802.4), Token Ring JAM, SFD, IFG, preamble,
Etherne
(802.5), Ethernet frame 64-1518B backoff
t
3.7
FHSS (79ch, 1600 hops/s), DSSS (11-chip Barker), FHSS, DSSS, DIFS, SIFS,
Wireles
CSMA/CA, RTS/CTS, Bluetooth piconet RTS/CTS
s
3.8 VC phases: setup/transfer/teardown. X.25 (64kbps). Frame VCI, VPI, CBR, VBR, ABR,

Page 31 of 32
Computer Networks | Unit 3: Data Link Layer | Student Study Notes

Section Core Topics Key Terms

VC/FR/
Relay (45Mbps). ATM (53B cell, QoS). PVC, SVC
ATM
3.9
HDLC: Primary/Secondary/Combined, NRM/ARM/ABM, I/S/U I-frame, S-frame, ABM, LCP,
HDLC &
frames. PPP: LCP, NCP, PAP, CHAP. IPCP, CHAP
PPP

Key Formulas
Pure ALOHA: S = G x e^(-2G) --> S_max ~18.4% at G = 0.5
Slotted ALOHA: S = G x e^(-G) --> S_max ~36.8% at G = 1.0
CRC remainder: R = (M x 2^r) mod G(x) [XOR polynomial division]
Stop-and-Wait: eta = 1 / (1 + 2a) [a = [Link] / [Link]]
Go-Back-N: eta = N / (1 + 2a) when N < (2a + 1)
100% efficiency: N >= (2a + 1) [window fills the pipe]
Hamming parity bits: 2^r >= m + r + 1 [m = data bits, r = parity bits]
Ethernet min frame: 2 x tau x B = 512 bits = 64 bytes [tau = one-way delay]

— End of Unit 3: Data Link Layer —

Computer Networks | BCA / [Link] | Student Handout Notes

Page 32 of 32