Chapter 3 - Data Link Layer#1

What is the overall goal of the Data Link Layer (L2)?

Provide reliable, efficient data transfer of frames between adjacent stations over a physical link, using the L1 bit-stream service.

What does L1 provide to L2? What are its deficiencies?

L1 provides an unreliable bit pipe (no sequence errors, but bit flips, insertions, and losses possible). It has finite propagation speed and limited data rate.

What are the four main L2 functions?

(1) Data transmission through Framing,

(2) Error detection/correction,

(3) Flow control,

(4) Configuration management.

Name the three L2 service classes.

• Unconfirmed connectionless – no ACK, no flow control; used in LANs with low error rates

• Confirmed connectionless – each frame ACKed individually; used on high-error channels (e.g. wireless)

• Connection-oriented – connection setup → data transfer (with ACK, flow control) → disconnect

Why are L2 ACKs not strictly required?

Higher layers (L4) can also do error correction. But retransmitting an entire L4 message due to one faulty L2 frame wastes time → L2 ACKs are an optimization.

What is the purpose of framing at L2?

Structure the raw L1 bit stream into delimited units (frames) so error correction and flow control can be applied per frame.

What are the four framing methods?What does each one do?

• Character-oriented – control characters mark boundaries (DLE, STX, ETX)

• Count-oriented – frame contains a length count field

• Bit-oriented – special flag bit pattern (e.g. 01111110) marks boundaries → requires bit stuffing

• Invalid L1 characters – use encoding-specific invalid symbols as delimiters

What is character stuffing and when is it used?

Used in character-oriented protocols.

Sender prepends DLE(Data Link Escape) before any control character in user data.

Receiver only interprets control characters preceded by DLE. If user data contains DLE itself, an extra DLE is inserted before it.

What is bit stuffing and when is it used?

Used in bit-oriented protocols (e.g. HDLC). Sender inserts a 0 after every five consecutive 1s in user data. Receiver removes 0 after five 1s. Prevents the flag pattern 01111110 from appearing in data.

What is the problem with count-oriented framing?

A transmission error in the length count field desynchronizes sender and receiver — it's unclear where the next frame starts.

What is the problem with the "idle time" framing approach?

L1 may not have a reliable notion of time; inefficient if idle periods are required between frames.

What causes transmission errors?

Thermal noise, impulse disruptions (~10 ms, from lightning/power lines), crosstalk, echo, interference, signal distortion. Errors typically occur in bursts.

What is the Hamming distance between two code words?

The number of bit positions in which they differ (computed via XOR, count the 1s).

What is the Hamming distance of a code?

The minimum Hamming distance between any two valid code words in the code.

For detection off bit errors, what Hamming distance d is required

d ≥ f + 1

For correction off bit errors, what Hamming distance d is required?

d ≥ 2f + 1 (received word is "closer" to the original than to any other valid word)

Lower bound for check bits r to correct 1-bit errors in m data bits?

(m + r + 1) ≤ 2^r. Example: m=8 → r=4; m=1000 → r=10

What is a parity bit and what can it detect?

A single redundant bit making the total number of 1s even (or odd). Detects all single-bit errors (d=2, detects f=1). Cannot correct errors.

What is CRC (Cyclic Redundancy Check)?

Error detection method treating bit strings as polynomials. Sender appends remainder R(x) of B(x)·x^r / G(x) to the message. Receiver divides received word by G(x); zero remainder → no error detected.

What are the CRC sender steps?

1. Append r zeros to block B → B_E (= x^r · B(x))

2. Divide B_E(x) by G(x) (mod 2) → quotient Q(x) + remainder R(x)

3. Transmit B_E − R(x) (i.e. B with R replacing the appended zeros)

What does G(x) require for CRC?

Degree r < degree of B(x); highest and lowest order bit must be 1.

What errors does CRC-CCITT (x^16 + x^12 + x^5 + 1) detect?

All single/double bit errors, all odd-bit errors, all burst errors ≤ 16 bits, 99.99% of burst errors > 16 bits.

Why is error correction less common than detection at L2?

Correction requires high redundancy per block. For the same overhead, error detection + retransmission is usually more efficient given typical error distributions