Computer Networks · Module II

Data Link Layer & Error Control

Comprehensive reference guide covering all 5 lecture topics — error detection, correction, ARQ protocols, MAC, Ethernet, and IEEE standards. Click any flashcard to reveal the answer.

Unit 1 · L6

Data Link Layer — Services & Sublayers

Theory

🔑 One-Line Definition

Layer 2 of OSI. Sits between Physical (L1) and Network (L3). Packages raw bits into frames, adds addressing, does error detection, and controls medium access.

Two Sublayers (IEEE 802)

LLC — Logical Link Control (Upper)

Protocol Multiplexing — identifies which upper-layer protocol (IP, ARP) a frame belongs to using Service Access Points (SAPs)
Error Detection & Correction — CRC, ARQ, checksums; requests retransmission if corrupted
Flow Control — Stop-and-Wait & Sliding Window to prevent fast sender overwhelming slow receiver
Framing & Synchronization — marks start/end of frames so receiver knows boundaries

MAC — Media Access Control (Lower)

Physical Addressing — assigns 48-bit MAC addresses (e.g., 00:1A:2B:3C:4D:5E)
Channel Access Control — CSMA/CD, CSMA/CA, Token Passing to prevent collisions
Framing — converts data into frames (header + payload + trailer with CRC)
Error Detection at Frame Level — basic CRC at hardware level, quickly discards corrupted frames

5 Main Services of the Data Link Layer

Service	What it does	Technique
1. Framing	Divides bit stream into structured frames with clear boundaries	Character Count, Bit Stuffing, Char Stuffing
2. Physical Addressing	Adds source & destination MAC address to every frame	48-bit MAC address
3. Flow Control	Prevents sender overwhelming receiver with different speeds	Stop-and-Wait, Sliding Window
4. Error Control	Detects / corrects frame corruption during transmission	Parity, CRC, Hamming; ARQ
5. Access Control	Determines who may use shared medium at any given time	CSMA/CD, CSMA/CA, Token Passing, FDMA/TDMA/CDMA

Framing Methods
Character Count — first field specifies number of characters. Problem: if count field corrupted, all boundaries lost.
Character Stuffing — special chars DLE STX (start) and DLE ETX (end). If DLE appears in data, escape it by inserting DLE before it. 

          Data: A DLE B  →  Frame: DLE STX A DLE DLE B DLE ETX
Bit Stuffing (HDLC) — frames delimited by flag 01111110. After 5 consecutive 1s in data, sender inserts a 0. Receiver removes it.

            Data: 01111110 11111011111110 01111110

            Sent: 01111110 111110 11111100 01111110
          

Unit 2 · L6

Error Types & Causes

Theory

Causes of Errors

Cause	Description	Effect
Thermal Noise	Random electron motion due to heat	Continuous background hiss
Impulse Noise	Sudden disturbance — lightning, switching devices	Short but corrupts multiple bits
Cross Talk	Signal from one channel bleeds into another	Common in twisted-pair telephone lines
Attenuation	Signal weakens over long distances	Receiver misinterprets bits
Jitter	Small variations in signal arrival time	VoIP / video quality degradation

Types of Errors

Single-Bit Error
Only one bit flipped per data unit
Rare in modern high-speed networks
Easier to detect with parity bits
Example

            Sent: 1001101  →  Received: 1001111
Bit 5 flipped: 0 → 1
          

Burst Error
Two or more consecutive bits altered
Much more common — channel disturbances hit groups of bits
Length = first corrupted bit to last (bits in between may be fine)
Requires stronger methods like CRC
Example

            Sent: 1101001111  →  Received: 1100010111
Bits 3–7 corrupted (burst length = 5)
          

Key Terms

Dataword = original data before encoding (e.g., 1101)
Codeword = dataword + redundant bits (e.g., 11011)

Unit 3 · L6

Error Detection Methods — VRC, LRC, Checksum, CRC

Calculation

① VRC — Vertical Redundancy Check (Parity Bit)

Add one extra bit to each data unit so the total number of 1s is even (even parity) or odd (odd parity).

Sender Steps

Count the number of 1s in the data unit.
Even parity: parity bit = 0 if count is already even; = 1 if odd. (Odd parity: reverse.)
Transmit data + parity bit.

Receiver Steps

Count 1s in received data + parity bit.
If parity rule violated → error detected; otherwise → assume no error.

        Even Parity Example: Data: 10110010 → four 1s (even) → parity bit = 0

        Transmitted: 10110010 0

✓ Strengths
Very simple & cheap
Detects odd number of bit errors (1, 3, 5…)
Common in low-cost serial links

✗ Weaknesses
Fails on even number of flips (2 bits cancel out)
Not reliable for burst errors

② LRC — Longitudinal Redundancy Check (2D Parity)

Arrange data as a block of rows. Compute parity for each column → the column parities form an extra LRC row appended after the data.

Example — 4×8 block, even parity
D1 = 11001010
D2 = 01011011
D3 = 11110000
D4 = 00011101


        Column parity row (LRC) = 01111000

        Transmit D1, D2, D3, D4 + LRC row.
      

✓ Strengths
Detects most burst errors & multiple errors affecting columns/rows
Can locate and correct a single-bit error (row ∩ column)

✗ Weaknesses
More overhead than VRC
Cannot correct arbitrary multi-bit errors
Some pathological patterns escape detection

③ Checksum (Ones'-Complement Sum)

Divide data into fixed-length words (16-bit in practice). Sum them using ones'-complement arithmetic. Complement the sum → this is the checksum sent with data.

Sender (16-bit words)

Break data into 16-bit words.
Add all words in binary. If carry beyond 16 bits, wrap it around (add carry to LSB).
Take bitwise NOT of final sum → Checksum.
Transmit data + checksum.

Receiver

Sum all received 16-bit words including checksum using ones'-complement.
If result = all 1s (0xFFFF) → no error. Otherwise → error detected.

        8-bit Demo:

        W1 = 01010101, W2 = 01100110

        Sum = 10111011  →  Checksum = 01000100 (bitwise NOT)

        Receiver Sum: W1 + W2 + Checksum = 11111111 ✓

Note on Carries

If adding two 16-bit words gives a 17-bit result, wrap the carry (add it back into the LSB) before complementing. This is specific to ones'-complement arithmetic used in IP/TCP/UDP headers.

④ CRC — Cyclic Redundancy Check (Polynomial Division)

Treat the bit sequence as a binary polynomial. Divide by a fixed generator polynomial G (known to both sides). Remainder = CRC bits. Receiver divides received frame by same G; zero remainder = no error.

Key Facts
Generator of degree r yields r CRC bits.
Detects all burst errors of length ≤ r.
Detects all single-bit errors (if G has ≥ 2 nonzero terms).
Implemented efficiently in hardware via linear-feedback shift registers (LFSRs).
Used in: Ethernet, HDLC, PPP, USB, storage devices.

Sender Steps

Let M = message bits. Choose generator G of degree r.
Multiply M by x^r → append r zeros to M.
Divide M·x^r by G using mod-2 (XOR) division.
Let R = remainder (r bits). Transmit T = M followed by R.

Receiver Steps

Receive T' (may be corrupted).
Divide T' by G using mod-2 division.
If remainder = 0 → assume no error. If ≠ 0 → error detected.

        Worked Example: M = 1101011011 (10 bits), G = 10011 (degree 4, so r = 4)

        Step 1: Append 4 zeros → 11010110110000

        Step 2: XOR-divide by 10011 → remainder R = 1110

        Step 3: Transmitted frame T = 11010110111110

        Receiver divides 11010110111110 by 10011 → remainder = 0000 ✓

Transmitted Frame T = M + R = 14 bits

At a Glance Comparison

Method	Detects Single-bit?	Detects Burst?	Corrects?	Used In
VRC (Parity)	✅ (odd count)	❌	❌	Serial links, RAM
LRC (2D Parity)	✅	Partial	Single-bit only	Legacy protocols
Checksum	✅	Partial	❌	IP, TCP, UDP
CRC	✅	✅ (≤ r bits)	❌ (detect only)	Ethernet, USB, HDLC

Unit 4 · L6

Error Correction — Hamming Code & Single-Bit Correction

Calculation

Two Approaches to Error Correction

FEC — Forward Error Correction
Sender adds redundant bits to let receiver self-correct without retransmission
Examples: Hamming code, Reed-Solomon
Used in: real-time video, satellite, memory
Drawback: bandwidth overhead

ARQ — Automatic Repeat Request
Receiver detects error and asks sender to retransmit
Examples: Stop-and-Wait, Go-Back-N, Selective Repeat
Used in: TCP, file transfers
Drawback: latency from retransmission

Hamming Code — Key Principles

Developed by Richard W. Hamming (1950). Can detect and correct single-bit errors and detect (not correct) double-bit errors.

Step 1 — How many parity bits do I need?

2^r ≥ m + r + 1 where m = data bits, r = parity bits needed

Example: m = 4 data bits
Try r = 2: 2² = 4, need 4+2+1 = 7 → 4 ≥ 7? FALSE
Try r = 3: 2³ = 8, need 4+3+1 = 8 → 8 ≥ 8? TRUE ✓
So 3 parity bits, total codeword = 4+3 = 7 bits

Step 2 — Parity Bit Positions

Parity bits go at positions that are powers of 2: positions 1, 2, 4, 8, 16, …

Step 3 — Which bits does each parity bit cover? (Check-Skip Method)

Parity Bit	Position	Pattern	Covers positions
P1	1	Check 1, skip 1	1, 3, 5, 7, 9, 11…
P2	2	Check 2, skip 2	2, 3, 6, 7, 10, 11…
P4	4	Check 4, skip 4	4, 5, 6, 7, 12, 13…
P8	8	Check 8, skip 8	8, 9, 10, 11, 12, 13, 14, 15…

Full Worked Example — Encode 1011

Data bits: D1=1, D2=0, D3=1, D4=1. Need 3 parity bits → 7-bit codeword.

Positions: 1(P1) 2(P2) 3(D1) 4(P4) 5(D2) 6(D3) 7(D4) · Codeword = 0110011

Parity Calculations (Even Parity)
P1 covers pos 1,3,5,7 → values: P1,1,0,1 → sum of known = 1+0+1=2 (even) → P1 = 0
P2 covers pos 2,3,6,7 → values: P2,1,1,1 → sum of known = 1+1+1=3 (odd) → P2 = 1
P4 covers pos 4,5,6,7 → values: P4,0,1,1 → sum of known = 0+1+1=2 (even) → P4 = 0

        Final codeword: 0 1 1 0 0 1 1

Error Detection & Correction

Suppose bit 5 flips during transmission → received: 0 1 1 0 1 1 1

Recalculate parities at receiver

        P1 (1,3,5,7): 0+1+1+1 = 3 (odd) → Error! → P1 bit = 1

        P2 (2,3,6,7): 1+1+1+1 = 4 (even) → OK → P2 bit = 0

        P4 (4,5,6,7): 0+1+1+1 = 3 (odd) → Error! → P4 bit = 1

        Error location = P4 P2 P1 in binary = 1 0 1 = 5

        Flip bit 5 → corrected codeword: 0 1 1 0 0 1 1 ✓

        Extract data bits (3,5,6,7): 1 0 1 1 = original 1011 recovered!

Summary

Detection: Parity checks identify whether an error exists.
Location: The combination of failed parity bits (in binary) gives the position.
Correction: Flip the bit at that position — original data restored.

Unit 5 · L7

Error Recovery Protocols — ARQ

Protocol

Concept

Automatic Repeat Request: receiver detects errors in frames & requests retransmission. Uses ACK (positive) and NAK (negative) acknowledgments, plus timeouts.

① Stop-and-Wait

Window=1. Send → Wait → Send.

Simplest ARQ
Simple to implement
Slow on high-latency links

② Go-Back-N

Window=N. Error → re-tx bad + all after.

Receiver discards out-of-order
Higher throughput than S&W
Wastes bandwidth on errors

③ Selective Repeat

Window=N. Retransmit ONLY bad frame.

Receiver buffers out-of-order
Most efficient
Complex receiver (buffers)

Comparison Table

Feature	Stop-and-Wait	Go-Back-N	Selective Repeat
Window Size (Sender)	1	N	N
Window Size (Receiver)	1	1	N
On Error: Retransmit	That frame only	Error frame + all after	Error frame only
Buffering?	No	No (discards)	Yes (out-of-order)
Efficiency	Lowest	Medium	Highest

Stop-and-Wait Visual

Go-Back-N Visual (N=4)

Unit 6 · L8

Multiple Access Protocols

Protocol

① TDMA (Time Division)

Discrete time slots; one exclusive slot per frame.

Predictable, orderly, easy to manage
GSM cellular — frame = 4.615 ms, 8 time slots
Wasted bandwidth if device is idle

② CDMA (Code Division)

All users share same freq; unique spreading codes.

3G (WCDMA) — phones share band, split by codes
High spectral efficiency; robust against fading
Complex encoding; needs precise power control

③ FDD (Frequency Division Duplex)

Uplink and downlink on separate frequency bands.

3G/4G — uplink 1920–1980 MHz, downlink 2110–2170 MHz
Simultaneous two-way communication
Needs wider spectrum allocation

④ CSMA/CA (Avoidance)

Used in Wi-Fi (802.11). Sense → Wait → RTS/CTS.

Works where detection is impractical (wireless)
Sense idle → optionally send RTS → receive CTS
Overhead from backoff + control frames

⑤ CSMA/CD (Detection)

Used in wired Ethernet (802.3). Sense → Send → Listen.

Fast resolution for wired collisions
Listen before sending → monitor for collision → stop + jam signal → backoff
Inefficient under high load

Quick Reference Comparison

Protocol	Medium	Collision?	Key Mechanism	Real-World Use
TDMA	Wireless/Wired	None (time)	Fixed time slots	GSM (2G)
FDD	Wireless	None (freq)	Separate uplink/downlink bands	3G, 4G LTE
CDMA	Wireless	None (code)	Unique spreading codes	3G (WCDMA)
CSMA/CA	Wireless	Avoided	Listen before send + RTS/CTS backoff	Wi-Fi (802.11)
CSMA/CD	Wired	Detected	Listen while send + jam + backoff	Ethernet (802.3)

Unit 7 · L9

MAC Addressing & Ethernet

Network Hardware

MAC Address (Physical Address)

Unique 48-bit (6-byte) hardware address assigned to every NIC.
Written in hexadecimal: 00:1A:2B:3C:4D:5E
First 24 bits = OUI — identifies manufacturer
Last 24 bits = unique identifier assigned by manufacturer
Operates at Layer 2; used only within a local network segment.

00:1A:2B : 3C:4D:5E
(OUI - Manufacturer) : (NIC Specific)

UNICAST

AA:BB:CC:DD:EE:01
1 to 1

MULTICAST

01:00:5E:xx:xx:xx
1 to Group

BROADCAST

FF:FF:FF:FF:FF:FF
1 to ALL in LAN

Ethernet Frame Structure (IEEE 802.3)

Min Frame: 64 bytes (excluding preamble)

Max Frame: 1518 bytes (Standard Ethernet MTU)

Why minimum 64 bytes?

In CSMA/CD, a device must detect a collision before finishing transmission. The minimum frame size ensures the frame is still on the wire when a collision signal returns.

Ethernet Standards

Standard	Speed	Medium	Distance
10BASE-T	10 Mbps	Copper TP	100 m
100BASE-TX	100 Mbps	Copper TP	100 m
1000BASE-T	1 Gbps	Copper TP	100 m
10GBASE-T	10 Gbps	Copper TP	100 m
10GBASE-SR	10 Gbps	Multimode Fiber	300 m
40GBASE-LR	40 Gbps	Single-mode Fiber	10 km

Ethernet Operation

Traditional (CSMA/CD)

Carrier Sense: listen before transmit
Multiple Access: transmit if idle
Collision Detection: stop + jam signal + random backoff

Modern (Switched)

Each device on a dedicated switch port
Full-Duplex: simultaneous send and receive
No collisions; CSMA/CD is no longer needed

Unit 8 · L9

Polling & Controlled Access

Theory

Eliminates collisions by centrally managing who transmits. Used in industrial networks and mainframe terminals. Only the polled device may transmit.

Select (Primary → Secondary)

Primary has data for a specific secondary. Asks: "I have data for you, ready?" Secondary ACKs, then data flows.

Poll (Primary ← Secondary)

Primary asks each secondary: "Do you have anything to send?" If yes, secondary sends. If no, secondary sends NAK.

Types of Polling

Type	Description	Efficiency
Roll Call	Master polls EVERY device in a fixed sequence.	Simple but wastes time on idle
Hub / Selective	Master only polls devices likely to have data.	More efficient; reduces wait
Interrupt	Devices raise a request flag; master responds.	Most efficient; no unnecessary poll

✓ Advantages
No collisions — only one device transmits at a time
Simplified error handling (master controls access)
Predictable behavior & Fairness

✗ Disadvantages
Polling overhead consumes bandwidth
Delay — devices must wait for their turn
Single point of failure (Master)

Unit 9 · L10

IEEE 802 Standards

Reference

Standard	Name	Freq / Speed	Access Method
802.3	Ethernet	N/A	CSMA/CD
802.11a/g	Wi-Fi	2.4 / 5 GHz (54 Mbps)	CSMA/CA
802.11n	Wi-Fi 4	Dual Band (600 Mbps)	CSMA/CA
802.11ac	Wi-Fi 5	5 GHz (3.5 Gbps)	CSMA/CA (MU-MIMO)
802.11ax	Wi-Fi 6	2.4/5/6 GHz (9.6 Gbps)	OFDMA
802.15.1	Bluetooth	2.4 GHz (1-3 Mbps)	FHSS (Piconets)

      Note: 802.1 covers Bridging, 802.2 covers LLC. Modern Bluetooth (5.x) reaches 50 Mbps.
    

Unit 10 · Review

Flashcard Bank

Tap to flip

What are the 2 sublayers of the Data Link Layer?

LLC (Logical Link Control) — upper sublayer; handles protocol mux, error/flow control.
MAC (Media Access Control) — lower sublayer; handles physical addressing & channel access.

What is a Burst Error?

Two or more consecutive bits altered in a data unit. Much more common than single-bit errors. Requires CRC to detect.

VRC parity bit rule for even parity?

Count the 1s in the data. If count is even → parity bit = 0. If count is odd → parity bit = 1. Total 1s should be even.

What is the Hamming Code formula?

2^r ≥ m + r + 1
r = parity bits, m = data bits.

Where are parity bits placed in Hamming Code?

At positions that are powers of 2: positions 1, 2, 4, 8, 16, … All other positions hold data bits.

What does P1 (position 1) check in Hamming?

Check-Skip Method: Check 1, skip 1 → covers positions 1, 3, 5, 7, 9, 11… (all odd positions)

How does Hamming Code locate an error?

The binary number formed by failing parity checks (P4 P2 P1) gives the bit position. Flip that bit to correct.

CRC: What happens at the receiver?

Divide received frame by same generator G using mod-2 division. Remainder 0 = assume no error.

Go-Back-N vs Selective Repeat?

GBN: retransmit bad + all after. SR: retransmit ONLY bad frame. SR requires buffering out-of-order.

CSMA/CA vs CSMA/CD — where used?

CD → wired Ethernet (802.3). CA → wireless Wi-Fi (802.11). Wireless can't detect collisions while sending.

MAC address format & size?

48-bit (6-byte) hex. First 24 bits = OUI (manufacturer). Broadcast = FF:FF:FF:FF:FF:FF.

Ethernet frame: what is the FCS field?

Frame Check Sequence — 4 bytes. Contains CRC-32 checksum for hardware-level error detection.

Ethernet min frame size and why?

64 bytes. Ensures collision signal returns before transmission finishes in CSMA/CD.

What is Bit Stuffing?

Used in HDLC. After 5 consecutive 1s in data, sender inserts a 0 to avoid mimicry of flag (01111110).

What is CDMA?

Code Division Multiple Access. All share freq/time; split by unique spreading codes. Signal-to-Noise.

What is Polling?

Centralized access where master asks slaves for data. No collisions. Roll Call vs Hub vs Interrupt.

IEEE 802.11 uses which MAC protocol?

CSMA/CA (Avoidance). Hidden nodes solved by RTS/CTS.

Bluetooth frequency technique?

FHSS — Frequency Hopping Spread Spectrum. Hops between 79 channels at 2.4 GHz, 1600 times/sec.

LRC can correct which error?

Single-bit errors only. Intersection of bad row/column.

Checksum sender: final step?

Take the bitwise NOT (ones' complement) of the sum.

What is FEC?

Forward Error Correction. Sender adds redundancy for self-correction. Satellite, real-time, memory.

Hidden node problem in Wi-Fi?

A & C out of range of each other but in range of AP B. Both send simultaneously → collision. RTS/CTS.