GATE/Computer Networks/Data Link Layer — Framing, Error Control & MAC
Sign in to track
Hard20 min readComputer Networks

Data Link Layer — Framing, Error Control & MAC

The Data Link layer handles framing, error detection/correction, and media access control. GATE heavily tests sliding window protocols, CRC, and CSMA/CD.

Key Points

  • ·Framing: character stuffing or bit stuffing to delineate frames
  • ·Error detection: parity, CRC (Cyclic Redundancy Check) — can detect burst errors
  • ·Error correction: Hamming code — can correct 1-bit errors, detect 2-bit errors
  • ·Stop-and-Wait: send one frame, wait for ACK; efficiency = 1/(1 + 2a) where a = Tp/Tf
  • ·Go-Back-N (GBN): window size ≤ 2^n − 1; retransmit all from error onward
  • ·Selective Repeat (SR): window size ≤ 2^(n-1); retransmit only errored frame
  • ·CSMA/CD: Carrier Sense Multiple Access / Collision Detection — Ethernet
  • ·CSMA/CA: Collision Avoidance — 802.11 Wi-Fi (cannot detect collisions on wireless)
  • ·ALOHA: pure ALOHA 18.4% max efficiency; slotted ALOHA 36.8% max efficiency

Why Data Link Layer?

Analogy: The Data Link layer is like a local delivery service operating within one city. The Network layer (IP) plans the cross-country route, but the Data Link layer handles the last mile — from one node to the adjacent node.

Error Detection

Parity Bit

Add 1 bit so total 1s in data is even (even parity) or odd (odd parity).
Detects single-bit errors. Cannot correct.

Example: 1010110 → count of 1s = 4 (even)
Even parity bit = 0 → 10101100 sent
If received as 10001100 → count of 1s = 3 (odd) → ERROR detected!

CRC (Cyclic Redundancy Check)

Analogy: Divide a big number by a "magic number" (generator). Send the remainder with the message. Receiver divides again — if remainder is non-zero, there was an error.

Steps:
1. Append r zeros to message (r = degree of generator polynomial)
2. Divide (modulo-2 XOR division) by generator
3. Append remainder to original message (not the zero-appended version)
4. Receiver divides full received message by generator — remainder = 0 means no error

CRC detects ALL single-bit errors, ALL burst errors ≤ degree of generator.

Hamming Code

For m data bits, need r parity bits where: 2^r ≥ m + r + 1
Parity bits placed at positions 1, 2, 4, 8, 16... (powers of 2)

Can CORRECT 1-bit errors, DETECT 2-bit errors.

Sliding Window Protocols — The Key GATE Topic

The Problem: In Stop-and-Wait, the sender waits for ACK before sending the next frame. On long-distance links (satellite), the round-trip delay wastes time.

Solution: Send multiple frames without waiting!

Key Parameters

Tf = Transmission time = L/B  (L = frame length in bits, B = bandwidth in bps)
Tp = Propagation delay = d/v  (d = distance, v = signal speed ~3×10^8 m/s)
a  = Tp/Tf  (bandwidth-delay ratio)

Round trip for one frame = Tf + 2Tp = Tf(1 + 2a)

Stop-and-Wait

Send one frame → wait for ACK → send next frame.
Window size = 1

Efficiency η = Tf / (Tf + 2Tp) = 1 / (1 + 2a)

Example: a = 10 → η = 1/21 = 4.7% efficiency!
The link is idle 95% of the time waiting for ACK.

Go-Back-N (GBN)

Send up to W frames without waiting for ACK.
On error: retransmit ALL frames from the errored one onward.

Max window size W = 2^n - 1  (n = sequence number bits)
  (Must be < 2^n to distinguish old/new frames)

Efficiency:
  If W ≥ 1+2a:  η = 1
  If W < 1+2a:  η = W / (1+2a)

Selective Repeat (SR)

Send up to W frames. On error: retransmit ONLY the errored frame.
Receiver buffers out-of-order frames.

Max window size W = 2^(n-1)  (HALF of GBN — because receiver buffers matter)
  If SR used 2^n-1 like GBN, receiver could mistake old frames for new.

Same efficiency formula as GBN but can use bigger W for same n.

Comparison Table:

Protocol Window size On error Buffer needed
Stop-and-Wait 1 Retransmit 1 frame 1
Go-Back-N 2^n - 1 Retransmit ALL from error 1 (no receiver buffering)
Selective Repeat 2^(n-1) Retransmit ONLY errored Both sides need W buffer

Worked Example:

n = 3 bits, so sequence numbers 0-7
GBN max window = 2^3 - 1 = 7
SR max window  = 2^(3-1) = 4

Bandwidth = 1 Mbps, frame size = 1000 bits, distance = 500km, speed = 2×10^8 m/s
Tf = 1000 / 10^6 = 1ms
Tp = 500000 / 2×10^8 = 2.5ms
a = Tp/Tf = 2.5

1+2a = 1+5 = 6
GBN efficiency = 7/6 → capped at 1 = 100%  (W=7 ≥ 1+2a=6 so η=1)
Stop-and-Wait = 1/6 = 16.7%

CSMA/CD — Ethernet (Wired)

Analogy: Multiple people trying to talk in a room. Listen first (CS), if quiet then speak (MA). If two speak at once (Collision Detected), both stop, wait random time, try again.

Algorithm:
1. Sense the carrier (listen to wire)
2. If busy → wait; if idle → transmit
3. While transmitting → keep listening for collision
4. Collision detected → send JAM signal (tell everyone), stop
5. Wait random backoff: k × slot_time, k random from {0, 1, ..., 2^i-1}
   (Binary Exponential Backoff — i increases with each collision)

Minimum frame size in Ethernet:
  Must transmit long enough to detect a collision before transmission ends.
  Min frame = 2 × Tp × B
  For 10Mbps Ethernet, 200m: min frame = 64 bytes

CSMA/CA (Wi-Fi 802.11): Cannot detect collisions on wireless (cannot transmit and receive simultaneously). Uses random backoff BEFORE transmission (collision avoidance, not detection).

ALOHA Protocols

Pure ALOHA: transmit whenever you want
  Collision if any two transmissions overlap
  Vulnerable period = 2 × frame time
  Max throughput = 1/(2e) ≈ 18.4% at offered load G = 0.5

Slotted ALOHA: transmit only at slot boundaries
  Vulnerable period = 1 × frame time (half of pure ALOHA)
  Max throughput = 1/e ≈ 36.8% at offered load G = 1.0

Quick Check

Q1. GBN with 4-bit sequence numbers. What is the maximum window size? Answer: 2^4 - 1 = 15 frames

Q2. Efficiency of Stop-and-Wait if Tp = 5ms, Tf = 1ms?

a = Tp/Tf = 5
η = 1/(1+2×5) = 1/11 ≈ 9.1%

Q3. Why is SR window size half of GBN? Answer: With SR, the receiver buffers frames and sends selective ACKs. If window = 2^n - 1 like GBN, the receiver could confuse new incoming frames for retransmissions of old ones (sequence numbers overlap). Half the sequence space prevents this ambiguity.

Key Formulas

  • Stop-and-Wait efficiency: η = 1/(1 + 2a), a = Tp/Tf
  • Sliding window efficiency: η = W/(1+2a) if W < 1+2a, else η = 1
  • GBN max window: 2^n − 1 (n = sequence number bits)
  • SR max window: 2^(n-1)
  • Slotted ALOHA max: 1/e ≈ 36.8% at G=1; Pure ALOHA 1/(2e) ≈ 18.4% at G=0.5

GATE Exam Tips

  • ★GBN window = 2^n - 1, SR window = 2^(n-1) — GATE always tests why SR is exactly half.
  • ★Efficiency formula W/(1+2a) — always check if W ≥ 1+2a first (if so, efficiency = 1).
  • ★Minimum Ethernet frame size ensures collision is detected before sender finishes transmitting.
  • ★Slotted ALOHA is exactly 2× better than Pure ALOHA in max throughput.

Finished reading this topic?

Mark it complete to track your study progress.

Sign in to track