Data Communication · Lecture 12

Data Link Layer II

Flow and error control: Stop-and-Wait, Go-Back-N and Selective Repeat ARQ, piggybacking, HDLC and PPP

Md Mahbub E Noor · Assistant Professor, Department of CSE, University of Barishal

Course: Data Communication · 2nd Year, 2nd Semester

Reliable links: today's goals

Explain flow control and error control at the data link layer
Trace Stop-and-Wait ARQ through lost frames and lost ACKs
Calculate link utilisation and the window size a link needs
Trace Go-Back-N and Selective Repeat; state their window limits
Describe piggybacking, HDLC frames and PPP framing and phases

Lecture 11 gave us

frames, and codes that tell the receiver when a frame is damaged.

Today

make delivery reliable: acknowledge, time out, resend, and never overwhelm the receiver.

Reading: Forouzan (5th ed.) Sections 11.1–11.4 and 23.2 (Go-Back-N, Selective Repeat)

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

2 / 38

Flow control and error control

Together they are called data link control (DLC)
Flow control: a fast sender must not overwhelm a slow receiver
Error control: damaged frames are discarded; lost ones must be resent
Data link error control is ARQ: automatic repeat request
Both need feedback from the receiver: ACKs (and sometimes NAKs)

Flow control

How much may the sender send before it must wait for an acknowledgement? Protects the receiver's buffer.

Error control

Detect lost or damaged frames and resend them: automatic repeat request (ARQ).

Tool	Job
ACK (acknowledgement)	“received correctly; I expect frame n next”
NAK (negative ACK)	“frame n is missing or damaged”
Timer	no ACK in time → resend
Sequence numbers	tell new frames from duplicates
Window	how many frames may be unacknowledged

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

3 / 38

Five protocols, from simplest to smartest

Protocol	Channel	Flow control	Error control	Windows (send / receive)
Simplest	noiseless	none	none	–
Stop-and-Wait	noiseless	wait for ACK	none	1 / 1
Stop-and-Wait ARQ	noisy	wait for ACK	timer, resend 1 frame	1 / 1
Go-Back-N ARQ	noisy	window	resend from the lost frame on	2^m − 1 / 1
Selective Repeat ARQ	noisy	window	resend only the lost frame	2^m−1 / 2^m−1

A noiseless channel is an ideal one: no frame is lost, duplicated or corrupted. Real links are noisy, so real protocols use ARQ. m = number of bits in the sequence-number field.

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

4 / 38

On a perfect channel: Simplest and Stop-and-Wait

Simplest: send whenever there is data; no ACK, no flow control
Assumes the receiver can process every frame immediately
Stop-and-Wait: send one frame, then stop until its ACK arrives
The ACK is the receiver's permission to send the next one
Flow control only: on a perfect channel, nothing is lost

Simplest

Sender

Receiver

Stop-and-Wait

Sender

Receiver

ACK

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

5 / 38

Stop-and-Wait ARQ

Real (noisy) channel: frames and ACKs can be lost or damaged
Sender keeps a copy of the frame and starts a timer
Time-out before the ACK? Resend the copy
Frames are numbered 0, 1, 0, 1 … so duplicates can be recognised
ACK n means “I expect frame n next”

What can go wrong	Fix in Stop-and-Wait ARQ
frame lost or damaged (receiver silent)	sender keeps a copy and a timer; on time-out it resends
ACK lost: the frame arrives twice	sequence number on each frame; the receiver discards the duplicate
ACK delayed: which frame is it for?	ACK number = number of the next frame expected

Sequence numbers

modulo 2 (m = 1)

0, 1, 0, 1 …

Receiver gets frame 0 correctly

it now expects frame 1

sends ACK 1

A damaged frame is discarded silently: the receiver sends nothing, and the timer does the rest.

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

6 / 38

Stop-and-Wait ARQ in action

Frame 0 is sent and acknowledged (ACK 1)
Frame 1 is lost: no ACK; the timer expires; frame 1 is resent
Frame 0 arrives, but its ACK is lost
Sender cannot tell which was lost: it resends frame 0
Receiver expects 1, sees 0: a duplicate. Discard it, send ACK 1 again

Sender

Receiver

Frame 0

ACK 1

Frame 1

ACK 0

Frame 0

ACK 1

Frame 0

ACK 1

time-out

duplicate: discard, re-ACK

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

7 / 38

Checkpoint 1 · 3 minutes

Check your understanding

Q1

Stop-and-Wait ARQ: the receiver has just accepted frame 1. Which ACK does it send, and why?

Q2

Frame 0's ACK is lost. What does the sender do, and how does the receiver recognise the duplicate?

Q3

A 2 Mbps link carries 4,000-bit frames; one-way propagation is 4 ms. What fraction of the time is Stop-and-Wait sending?

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

8 / 38

Why Stop-and-Wait wastes a fast link

Rate 1 Mbps; a bit takes 20 ms to go and come back
Bandwidth-delay product = bits the link can hold during one round trip
Stop-and-Wait sends 1,000 bits per round trip: 5% utilisation
Letting 15 frames be in flight: 75%
Fast or long links (satellite, fibre) need many frames in flight: pipelining

One round trip could carry 20 frames of 1,000 bits; Stop-and-Wait sends one

Bandwidth-delay product

1 Mbps × 20 ms

20,000 bits

Stop-and-Wait

1,000 / 20,000

Up to 15 frames in flight

15,000 / 20,000

75%

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

9 / 38

Link utilisation: the general formula

T_t = L / R (transmission time); T_p = propagation time
One cycle = T_t + 2T_p; a window of W frames fills W·T_t of it
Stop-and-Wait (W = 1): U = 1 / (1 + 2a)
The longer or faster the link, the larger a, and the bigger W must be
W needs enough sequence numbers: the window-size rules come later

a = T_p / T_t

U = W / (1 + 2a), at most 1

Full use: W ≥ 1 + 2a

Worked: a GEO satellite link · R = 1 Mbps, L = 8,000 bits, T_p = 270 ms

T_t and a

8,000 / 10⁶ = 8 ms; 270 / 8

a = 33.75

Stop-and-Wait

1 / 68.5

1.46%

Window for 100%

1 + 2a = 68.5

W = 69

Sequence bits

GBN: 2⁷ − 1 = 127 · SR: 2⁷ = 128

m = 7 · m = 8

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

10 / 38

Try it: fill the pipe with a window

Interactive

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

11 / 38

Sliding windows and sequence numbers

Pipelining needs many numbered frames in flight
With an m-bit field, numbers run 0 … 2^m − 1, then repeat
The send window covers frames sent but not yet ACKed, plus those it may still send
S_f: first outstanding · S_n: next to send · S_size: window size
An ACK slides the window forward; the sender may then send more

m = 3: sequence numbers repeat modulo 8

S_f = 2 (first outstanding)

· S_n = 5 (next to send)

· S_size = 5

acknowledged

sent, no ACK yet

may send

ACK 4 arrives → frames 2 and 3 confirmed → the window slides two places

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

12 / 38

Go-Back-N ARQ

Up to S_size frames may be outstanding; S_size ≤ 2^m − 1
Receiver window = 1: frames must arrive in order; others are discarded
ACKs are cumulative: ACK n confirms all frames before n
On time-out the sender goes back and resends every outstanding frame
Simple receiver (no buffering); wasteful when errors are frequent

Sender

one timer, for the oldest outstanding frame (S_f)

Receiver

receive window of size 1: accepts only R_n; anything else is discarded

Cumulative ACK

ACK 5 confirms

every frame before 5

Time-out

resend

S_f … S_n − 1

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

13 / 38

Go-Back-N in action

Left: ACK 2 is lost, but ACK 3 confirms frames 0–2: no harm done
Right: frame 1 is lost; frames 2 and 3 arrive but are out of order
Receiver discards them (window size 1)
Time-out: sender goes back and resends 1, 2 and 3
Two good frames were sent twice: the cost of a simple receiver

ACK 2 lost

Sender

Receiver

ACK 1

ACK 2

ACK 3

ACK 4

Frame 1 lost

Sender

Receiver

ACK 1

ACK 2

ACK 4

time-out

Grey = arrived but discarded (out of order) · dashed = resent

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

14 / 38

Go-Back-N: why S_size < 2^m

Worst case: a full window arrives, but every ACK is lost
Receiver has moved on; sender times out and resends its oldest frame
If the window used all 2^m numbers, the old frame's number is exactly the one the receiver expects next
So the send window must be at most 2^m − 1
m = 3 → window ≤ 7; m = 4 → ≤ 15

m = 2, window 3: safe

sender: sent, all ACKs lost, then resends 0

receiver now expects

Resent 0 ≠ expected 3: recognised as a duplicate ✓

m = 2, window 4: broken

sender: sent, all ACKs lost, then resends 0

receiver now expects

Resent old 0 = expected new 0: accepted by mistake ✗

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

15 / 38

Try it: the window-size trap

Interactive

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

16 / 38

Checkpoint 2 · 3 minutes

Check your understanding

Q1

m = 4. What is the largest send window for Go-Back-N? For Selective Repeat?

Q2

Go-Back-N, window 5: frames 0–4 are sent and frame 2 is lost; the rest arrive. Which frames does the sender resend after the time-out?

Q3

A link has a = 12. What window gives full utilisation, and how many sequence bits does Go-Back-N need?

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

17 / 38

Selective Repeat ARQ

Receiver keeps a window too, and stores out-of-order frames
Missing frame? Receiver sends a NAK for it
Sender resends only that frame (NAK or its own timer)
Frames are delivered to the network layer in order, once the gap is filled
Both windows ≤ 2^m−1; more buffers and logic at the receiver

Sender

a timer for each outstanding frame

Receiver

window of size 2^m−1: frame 3 is stored while 2 is missing

delivered / acknowledged

sent / stored

window

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

18 / 38

Selective Repeat in action

Frame 1 is lost; frames 2 and 3 arrive and are stored
Frame 2's arrival reveals the gap: NAK 1 (only once)
Sender resends only frame 1
Now 1, 2, 3 are delivered together; one ACK 4 confirms all three
Compare Go-Back-N: 3 frames resent instead of 1

Sender

Receiver

ACK 1

NAK 1

ACK 4

F2 stored

F3 stored

deliver 1, 2, 3

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

19 / 38

Selective Repeat: why the window is ≤ 2^m−1

Same worst case: the frames arrive, every ACK is lost
The receiver's window has slid forward by a whole window
If the two windows overlap, an old number falls inside the new window
No overlap needs send + receive window ≤ 2^m, so each ≤ 2^m−1
m = 3 → 4 (Go-Back-N could use 7)

m = 2, window 2: safe

sender: sent, all ACKs lost, then resends 0

receiver now expects

Receiver window {2, 3} does not contain 0: duplicate ✓

m = 2, window 3: broken

sender: sent, all ACKs lost, then resends 0

receiver now expects

Receiver window {3, 0, 1} contains 0: old frame accepted ✗

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

20 / 38

Try it: Stop-and-Wait, Go-Back-N and Selective Repeat

Interactive

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

21 / 38

Stop-and-Wait, Go-Back-N and Selective Repeat compared

	Stop-and-Wait ARQ	Go-Back-N	Selective Repeat
Frames in flight	1	up to 2^m − 1	up to 2^m−1
Receiver window	1	1	2^m−1 (buffers)
After a loss, resend	that frame	it and all after it	only that frame
Timers	1	1	one per frame
Lab run: 10 frames, frame 3 lost, m = 3	11 sent · 80 time units	W = 7: 17 sent · 36	W = 4: 11 sent · 30
Best for	short links	few errors	long or noisy links

Lab run: propagation = 3 frame times, link otherwise idle. Go-Back-N's bigger window loses to Selective Repeat once a frame is lost: 7 frames go twice.

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

22 / 38

Piggybacking

Real links carry data in both directions
Each data frame carries an ACK field for the other direction
So B's next data frame acknowledges A's frames: no separate ACK frame
No data to send? Wait briefly, then send an ACK frame on its own
In HDLC the N(R) field of an I-frame is the piggybacked ACK

Top: 3 frames · Bottom: piggybacking, 2 frames

data →

← ACK

← data

data →

← data

+ ACK

Advantage	Disadvantage
fewer frames, better use of the channel	more complex sender and receiver
less header overhead	an ACK held back too long triggers a time-out

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

23 / 38

HDLC: High-level Data Link Control

A bit-oriented protocol (flag 01111110, bit stuffing: Lecture 11)
Point-to-point and multipoint links
Implements the ARQ ideas of today: Go-Back-N and Selective Repeat
NRM: one primary, many secondaries that speak only when polled
ABM: point-to-point, both stations are equal (combined)

NRM: normal response mode

Primary

Secondary

ABM: asynchronous balanced mode

Combined

Primary sends commands; secondaries only respond. A combined station does both.

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

24 / 38

HDLC frames

Flag 01111110 at both ends
Address: the secondary station's address
Control (1 or 2 bytes): frame type, sequence and ACK numbers
Information: data from the network layer (or management data)
FCS: frame check sequence, a 2- or 4-byte CRC (Lecture 11)

Flag

Address

Control

Information

FCS

Flag

Frame	Carries	Control starts with
I-frame	user data + flow/error control (piggybacked ACK)	`0`
S-frame	flow and error control only (ACK, NAK); no data	`10`
U-frame	link management: connect, disconnect …	`11`

Back-to-back frames may share a flag: one frame's ending flag is the next frame's starting flag.

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

25 / 38

The HDLC control field

First bit(s) give the type: 0 I-frame, 10 S-frame, 11 U-frame
N(S): this frame's sequence number
N(R): the ACK number (piggybacked in I-frames)
P/F: poll (primary → secondary) or final (the reply)
S-frames: RR, RNR, REJ, SREJ; U-frames: SABM, UA, DISC …

I-frame

N(S) ·3

P/F

N(R) ·3

S-frame

1 0

code ·2

P/F

N(R) ·3

U-frame

1 1

code ·2

P/F

code ·3

·n = number of bits

S code	Name	Meaning
`00`	RR	receive ready: ACK up to N(R) − 1
`10`	RNR	ACK, but stop: receiver busy
`01`	REJ	NAK for Go-Back-N: resend from N(R)
`11`	SREJ	NAK for Selective Repeat: resend N(R) only

Decode 0 011 0 101

I-frame · N(S) = 3 · P/F = 0 · N(R) = 5

“my frame 3; I expect your 5”

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

26 / 38

Try it: build an HDLC control field

Interactive

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

27 / 38

HDLC in action (Example 11.6)

Left: B's I-frame 0 carries N(R) = 2: “got your 0 and 1”
A has no more data, so it sends an S-frame: RR 3
Right: frame 1 is lost; frame 2 is discarded
A sends REJ 1 (Go-Back-N NAK); B resends 1 and 2; A sends RR 3
Before data: SABM → UA; after: DISC → UA (U-frames)

No error: piggybacking

Node A

Node B

I 0,0

I 1,0

I 0,2

I 1,2

I 2,2

RR 3

Frame 1 lost: REJ

Node B

Node A

I 0

I 1

I 2

REJ 1

I 1

I 2

RR 3

Labels: I N(S),N(R) · grey = discarded · dashed = resent

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

28 / 38

PPP: the Point-to-Point Protocol

The common protocol for point-to-point links (dial-up, DSL via PPPoE, router links)
Byte-oriented, with an HDLC-like frame
Address FF and control 03 are constants: no stations, no numbering
Protocol field says what the payload is (IP, LCP, PAP …)
Errors are only detected (FCS); recovery is left to upper layers

Flag

Addr

Ctrl

Protocol

1–2 B

Payload

≤ 1500 B

FCS

2–4 B

Flag

PPP provides	PPP does not provide
frame format and byte stuffing	flow control
link set-up and option negotiation (LCP)	error recovery: a bad frame is silently dropped
authentication (PAP, CHAP)	sequence numbers
many network protocols; address assignment (NCP)

Old-slide fix: control = 00000011 = 03 (5th ed.). The old slide's 11000000 is the same byte written in transmission order (LSB first).

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

29 / 38

PPP byte stuffing

PPP's flag is a whole byte: 7E = 01111110
A data byte equal to 7E or 7D (escape) must be escaped
Escape byte 7D = 01111101
Real PPP also changes the escaped byte: XOR with 20
Receiver: drop 7D, XOR the next byte with 20

Payload bytes (hex)

Forouzan's rule: insert escape 7D (01111101) before 7E or 7D

Real PPP (RFC 1662): 7D, then the byte XOR 20

7E ⊕ 20

0111 1110 ⊕ 0010 0000

7D ⊕ 20

0111 1101 ⊕ 0010 0000

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

30 / 38

Try it: PPP byte stuffing

Interactive

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

31 / 38

PPP transition phases

Dead: no carrier
Establish: LCP negotiates options
Authenticate (optional): PAP or CHAP
Network: an NCP (e.g. IPCP) configures the network layer
Open: data flows · Terminate: LCP closes the link

Dead

Establish

Authenticate

Network

Open

Terminate

carrier

LCP OK

auth OK

NCP done

carrier lost

auth failed

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

32 / 38

PPP's helpers: LCP, PAP, CHAP and NCP

One frame format, many jobs: the protocol field says which
LCP sets up, tests and closes the link
PAP and CHAP authenticate the user
NCPs (IPCP for IP) prepare a network protocol
Example (Ex. 11.7): LCP ×2 → PAP ×2 → IPCP ×2 → IP data → LCP terminate

Protocol field	Payload carries
`C021`	LCP: link set-up, options, termination
`C023`	PAP: user name and password
`C223`	CHAP: challenge and response
`8021`	IPCP (an NCP): configure IP
`0021`	an IP datagram: user data

PAP

2 steps: send ID + password; accept or reject. Password crosses the link in clear.

CHAP

3 steps: challenge → result of f(challenge, password) → accept or reject. Password never sent.

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

33 / 38

Try it yourself: ARQ Lab

1 · Sliding windows: lose frames or ACKs; compare S&W, GBN, SR
2 · Link efficiency: utilisation, window size and sequence bits
3 · Window-size trap: watch a too-big window fail
4 · HDLC & PPP: build control fields; stuff PPP bytes

Scan to open the lab on your phone

Open the lab ↗

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

34 / 38

See it in action: recovering lost frames

Watch Stop-and-Wait time out and resend
See Go-Back-N go back, and Selective Repeat resend one frame
See an ACK ride on a data frame
When a “Pause & predict” card appears, answer before the video moves on

Click the video to play or pause · Press → for full screen

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

35 / 38

Checkpoint 3 · 3 minutes

Check your understanding

Q1

Decode the HDLC control field 10 01 0 011 (as on the slides). What is the receiver asking for?

Q2

Byte-stuff the PPP payload 7E 41 7D: (a) by Forouzan's rule, (b) by RFC 1662.

Q3

Selective Repeat, m = 3: frames 0–3 are sent and frame 2 is lost. What does the receiver deliver, store and send?

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

37 / 38

Key takeaways

Flow control protects the receiver; error control (ARQ) resends what is lost
Stop-and-Wait ARQ: copy, timer, numbers 0/1; U = 1/(1 + 2a)
Go-Back-N: window ≤ 2^m − 1, receiver window 1, resend from the loss
Selective Repeat: windows ≤ 2^m−1, NAK, resend only the lost frame
Piggybacking puts ACKs in data frames; HDLC (I/S/U frames) and PPP use these ideas

Next lecture

Lecture 13 · Multiple Access

Sharing one medium: random access (ALOHA, CSMA, CSMA/CD, CSMA/CA), controlled access and channelization.

Reading: Forouzan, Chapter 12 · Practise in the ARQ Lab

Md Mahbub E Noor

Lecture 12: Data Link Layer II

University of Barishal

38 / 38

Data Link Layer II

Reliable links: today's goals

Flow control and error control

Flow control

Error control

Five protocols, from simplest to smartest

On a perfect channel: Simplest and Stop-and-Wait

Simplest

Stop-and-Wait

Stop-and-Wait ARQ

Stop-and-Wait ARQ in action

Check your understanding

Q1

Q2

Q3

Why Stop-and-Wait wastes a fast link

Link utilisation: the general formula

Try it: fill the pipe with a window

Sliding windows and sequence numbers

Go-Back-N ARQ

Sender

Receiver

Go-Back-N in action

Go-Back-N: why Ssize < 2m

m = 2, window 3: safe

m = 2, window 4: broken

Try it: the window-size trap

Check your understanding

Q1

Q2

Q3

Selective Repeat ARQ

Sender

Receiver

Selective Repeat in action

Selective Repeat: why the window is ≤ 2m−1

m = 2, window 2: safe

m = 2, window 3: broken

Try it: Stop-and-Wait, Go-Back-N and Selective Repeat

Stop-and-Wait, Go-Back-N and Selective Repeat compared

Piggybacking

HDLC: High-level Data Link Control

HDLC frames

The HDLC control field

Try it: build an HDLC control field

HDLC in action (Example 11.6)

PPP: the Point-to-Point Protocol

PPP byte stuffing

Try it: PPP byte stuffing

PPP transition phases

PPP's helpers: LCP, PAP, CHAP and NCP

PAP

CHAP

Try it yourself: ARQ Lab

See it in action: recovering lost frames

Check your understanding

Q1

Q2

Q3

Key takeaways

Lecture 13 · Multiple Access

Go-Back-N: why S_size < 2^m

Selective Repeat: why the window is ≤ 2^m−1