Chapter 3 - Data Link Layer#2

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).