ch03 - Data Link Layer

What is the overall goal of the Data Link Layer (L2)?How does it do it?

Provides reliable and efficient data transfer between adjacent stations through framing.
This is done over a physical link using the L1 Bitstream.

What does L1 provide to L2? What are its deficiencies and possible errors?

L1 provides raw bit transmission with no error-free garantee, limited data rate and propagation speed.
The errors are not sequence errors, they are bit insertion/losses/flips.

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.
L4 Messages are a large number of L2 Frames. If there is one error in these frames, the whole message has to be retransmitted→ loss of time and efficiency

What is the purpose of framing at L2?

Structure the raw L1 bit stream into delimited units (frames)

→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

Why is flow control needed?

The sender can transmit faster than the receiver can process frames → receiver loses frames even on an error-free channel.

Protocol 1 (Utopia) – assumptions and problem?

Assumes error-free channel, infinite receiver buffer and processing speed. In reality: sender floods receiver

Protocol 2 (Stop-and-Wait) – principle and problem?

Sender transmits one frame and waits forACK before sending next. Solves buffer overflow. Problem: locks up on frame orACK loss.

Protocol 3a (Stop-and-Wait ARQ) – what does ARQ add?

Automatic Repeat reQuest: sender sets a timer; if no ACK received within timeout, retransmit. Problem: lost ACK causes duplicate frames at receiver

Protocol 3b – what do sequence numbers solve?

Duplicate detection. Receiver uses SeqNo to identify retransmissions. For Stop-and-Wait: only 2 sequence numbers needed (0 and 1).

Protocol 3c – what does NAK add

Active error control: receiver immediately sends NAK on corrupted frame, instead of waiting for sender timeout → faster retransmission.

Why is Stop-and-Wait inefficient on high-delay links?

Channel utilization U ≈ T_it / (T_it + 2T_p). Example: 50 kbps satellite, RTT=500ms, 1000-bit frame → U < 4%.

What is the sliding window mechanism?

Sender can have multiple unACKed frames "in flight" simultaneously (up to window size k)→ fills the pipe on high-latency links instead of waiting idle.

Define S-Window and R-Window.

• S-Window (sender): set of SeqNos sent but not yet ACKed

• R-Window (receiver): set of SeqNos the receiver is willing to accept

What do LB and UB mean in a sliding window?

LB (Lower Bound):

sender = oldest unACKed SeqNo;

receiver = next expected SeqNo

UB (Upper Bound):

sender = next SeqNo to send;

receiver = highest SeqNo accepted + 1

Channel utilization formula with sliding window (window size k)?

U = k / (1 + 2·T_p/T_it) if k < 1 + 2T_p/T_it, else U = 1

What is piggybacking?

ACK is embedded in a data frame going the other direction (full-duplex), reducing the number of separate ACK frames. Frame format: Frame(SeqNo, ACK-SeqNo, …Data…).

Go-Back-N – principle and properties?

On error, receiver discards all subsequent frames until the faulty one is correctly received. Sender retransmits from the faulty frame onwards. Simple (no out-of-order buffering), but poor throughput.

Selective Repeat – principle and properties?

Receiver buffers correctly received frames that follow a faulty one. Sender only retransmits the faulty frame. More complex (buffering required), higher throughput

Maximum window size for Go-Back-N vs. Selective Repeat?

Go-Back-N: window size ≤ 2^n − 1 (SeqNo range = 2^n)

Selective Repeat: window size ≤ 2^n / 2 = 2^(n−1) (half the SeqNo range)

Why must the SeqNo space be at least twice the window size?

To distinguish new frames from retransmissions when all ACKs are lost. If window = half the SeqNo range, no ambiguity is possible.

What is HDLC?

High-Level Data Link Control. Bit-oriented, full-duplex L2 protocol. Uses bit stuffing (insert 0 after five 1s). Frame: 01111110 | Address | Control | Data | FCS | 01111110 . FCS = CRC variant.

What are the three HDLC frame types?

1. I-frame (Information): data transfer; carries SeqNo and piggybacked ACK

2. S-frame (Supervisory): flow/error control (RR, REJ, RNR, SREJ)

3. U-frame (Unnumbered): connection management (SABM, DISC, UA, FRMR)

What do the four HDLC supervisory frame types do?

• RR (00): Receive Ready = ACK, ready for more

• REJ (01): Reject = NAK, Go-Back-N retransmit from NEXT

• RNR (10): Receive Not Ready = ACK but stop sending (temporary problem)

• SREJ (11): Selective Reject = retransmit only specific frame

What is SABM and DISC in HDLC?

SABM (Set Asynchronous Balanced Mode): establishes peer-to-peer connection, resets SeqNos to 0. DISC (Disconnect): terminates connection.

SLIP – protocol and limitations?

Serial Line IP. Frames IP packets with flag byte 0xC0 at end; character stuffing if 0xC0 in data. Limitations: no error detection, no authentication, IP only, no dynamic address assignment, no standard.

PPP – three phases and what each does?

1. LCP (Link Control Protocol): establish/test/release L2 connection, negotiate options, authenticate

2. NCP (Network Control Protocol): configure L3 (e.g. assign IP address dynamically)

3. Data transfer: carry L3 packets (IP, etc.)

PPP frame format fields?

Flag (01111110) | Address (11111111) | Control (00000011) | Protocol (1–2B) | Payload | Checksum (CRC) | Flag

PPP vs. SLIP – key improvements?

PPP adds: error detection, multi-protocol support (not just IP), dynamic IP addressing, authentication, standardized (RFC 1661).