1

Error and Flow Control

Required reading:
Garcia 5.2

CSE 3213, Fall 2010

Instructor: N. Vlajic
 Error Control 2

Error Control (1) Forward Error Correction (FEC)

Approaches (2) Error Detection + Automatic Retrans. Req. (ARQ)
• not enough redundant info to enable error correction
case (a) receiver detects no errors
ƒ an ACK packet is sent back to sender
case (b) receiver detects errors
ƒ no ACK sent back to sender
ƒ sender retransmits frame after a ‘time-out’

error detected !!!

= round-trip time
 Error Control (cont.) 3

Challenges of • send one frame at the time, wait for ACK

ARQ-based ƒ easy to implement, but inefficient in terms of channel
Error Control usage

• send multiple frames at once

ƒ better channel usage, but more complex to implement -
sender must keep (all) sent but unACKed frame(s) in a
buffer, as such frame(s) may have to be retransmitted

frame
frame
ACK

frame ACK
buffer of
frame finite size

How many frames should be sent

at any point in time?
How should frames be released from
the sending buffer?
 Error and Flow Control 4

Flow Control – set of procedures used to restrict the amount of data that
sender can send while waiting for acknowledgment
• two main strategies
(1) Stop-and-Wait: sender waits until it receives ACK
before sending next frame
(2) Sliding Window: sender can send W frames before
waiting for ACKs

Error + Flow Control (1) Stop-and-Wait ARQ

Techniques (2) Go-Back-N ARQ
(3) Selective Repeat ARQ

Error Detection + ARQ (error detection with retransmissions)

must be combined with methods that intelligently limit
the number of ‘outstanding’ (unACKed) frames.
Fewer unACKed frames ⇒ fewer packets buffered at sender and receiver.
 5

(1) Stop-and-Wait ARQ

 Stop-and-Wait ARQ 6

Stop-and-Wait ARQ – simplest flow and error control mechanism

• sender sends an information frame to receiver
• sender, then, stops and waits for an ACK
• if no ACK arrives within time-out, sender will
resend the frame, and again stop and wait
ƒ time-out period > roundtrip time
• abnormalities (and how to fix them)
ƒ lost acknowledgment
ƒ delayed acknowledgment

error detected !!!

= round-trip time
 Stop-and-Wait ARQ (cont.) 7

Lost Acknowledgment • frame received correctly, but ACK undergoes

errors / loss
ƒ after time-out period, sender resends frame
ƒ receiver receives the same frame twice

• frames must be numbered so that receiver

can recognize and discard duplicate frames
ƒ sequence # are included in packet header

0
frame frame 0
ACK ACK
1
frame frame 1
ACK ACK
2
frame frame 2
ACK ACK
retransmitted 2 Receiver has already
frame frame 2
frame How will receiver know received frame 2 –
that this is NOT it resends an ACK and
a new packet?! discards the duplicate.

without packet numbering with packet numbering

 Stop-and-Wait ARQ (cont.) 8

Delayed Acknowledgment • ACKs can be delayed due to problems with

(Premature Timeout) links or network congestion
ƒ time-out expires early, sender resends frame
ƒ when delayed ACK arrives, sender assumes
that given ACK is for the last frame sent
• ACKs must be numbered to prevent gaps
in delivered packet sequence

0 0
frame 0 frame 0
0
ACK ACK 1
receiver sees this as 0 0
ACK for 2nd frame-0 frame 0 frame 0
and sends frame-1 1 ACK 1 ACK 1 0

receiver sees this as frame-1 not

delivered !!! cannot send
ACK for frame-1 2
frame-2
and sends frame-2

without ACK numbering with ACK numbering

How large should the packet / ACK sequence be? Only 1-bit long !!!
 Stop-and-Wait ARQ (cont.) 9

[Link]
 Stop-and-Wait ARQ (cont.) 10

Stop-and-Wait • t0 = basic Stop-and-Wait delay – from time when frame

Efficiency is transmitted into channel until time when ACK arrives
back to receiver, and another frame can be sent
nf n ACK
t 0 = 2 ⋅ t prop + 2 ⋅ t proc + t frame + t ACK = 2 ⋅ t prop + 2 ⋅ t proc + +
R R
• Reff = effective transmission (data) rate:

number of info bits delivered to destination nf − nheader

R eff = =
total time required to deliver info bits t0

t0 = total time to transmit 1 frame

A
nf bits tproc

nACK bits
B
frame
tprop tproc tack tprop
tf time
first frame bit end of ACK
arrives at end of frame first ACK bit is received
receiver is received arrives at
receiver
 Stop-and-Wait ARQ (cont.) 11

• ηSW = transmission efficiency:

efficiency ratio of actual and effective
transmission (data) rate - ideally, ηSW ≈ 1
ƒ where do we lose channel efficiency, and how can ηSW → 1
be achieved ?!
should be
as small
nf − nheader nheader
1− as possible
R t0 nf
ηSW = eff = =
R R n ACK 2(t + t )R
1+ + prop proc
nf nf

nheader
(1) - loss in efficiency due to (need for) header
nf
n ACK
(2) - loss in efficiency due to (need for) ACKs
nf

(3) 2(t prop + t proc )R - bandwidth-delay product

ƒ max number of bits in transit at any given time

ƒ in Stop-and-Wait ARQ delay-bandwidth product is a measure

of lost opportunity in terms of transmitted bits
 Stop-and-Wait ARQ (cont.) 12

Bandwidth-delay product = 2*(tprop + tproc)*R =

= capacity of the transmission pipe from the sender to the receiver and back.
 Stop-and-Wait ARQ (cont.) 13

frame size in comparison max number of bits in transit –

to bandwidth-delay product ‘the pipe is full’

tprop + tproc > tframe tprop + tproc < tframe

Stop-and-Wait ARQ becomes inadequate when data is fragmented

into small frames, such that nf / R = tframe is small relative to tprop .
 Stop-and-Wait ARQ (cont.) 14

Example [ impact of delay-bandwidth product ]

nf = 1250 bytes = 10000 bits n ACK nheader

⇒ = = 0.02
nACK = nheader = 25 bytes = 200 bits nf nf

nheader
1−
R eff nf 0.98
ηSW = = =
R n ACK 2 ⋅ (t prop + t proc )R 2 ⋅ (t prop + t proc )R
1+ + 1.02 +
nf nf nf

200 km 2000 km 20000 km 200000 km

Efficiency
(tprop = 1 ms) (tprop = 10 ms) (tprop = 100 ms) (tprop = 1 sec)
103 104 105 106
1 Mbps
88% 49% 9% 1%
106 107 108 109
1 Gbps
1% 0.1% 0.01% 0.001%

Stop-and-Wait does NOT work well for very high speeds or long propagation delays.
 Stop-and-Wait ARQ (cont.) 15

Stop-and-Wait • Pf = probability that transmitted frame has errors and

Efficiency in need to be retransmitted
Channel with ƒ (1-Pf) – probability of successful transmission
and including
Errors 1
ƒ – average # of (re)transmission until first correct arrival
1- Pf
1
ƒ total delay per frame: t 0 ⋅ (average # of retrans.) = t 0 ⋅
1- Pf

n f − nheader
t0 nheader
1−
R eff_error (1- Pf ) nf
ηSW_error = = = (1- Pf ) ⋅ (∗)
R R n ACK 2(t + t )R
1+ + prop proc
nf nf

ηSW_error = (1- Pf ) ⋅η0

Pf increases ⇒ ηSW decreases

 Stop-and-Wait ARQ (cont.) 16

successful
average # of transmissions in error
before a successful transmission transmission
time-out time-out time-out t0

Probability that i transmission are needed to deliver frame successfully

( i-1 transmission in error and the ith transmission is error free ):

P[ # of trans. in error = i-1 ] = (1-Pf) Pfi-1

∞ ∞
E[# of transmissi ons in error] = ∑ (i - 1) ⋅ P[n trans in error = i - 1] = ∑ (i - 1) ⋅ (1− Pf )Pfi−1 =
i=1 i=1
∞ ∞
= (1− Pf ) ⋅ ∑ (i - 1) ⋅ P f
i−1
= (1− Pf ) ⋅ ∑ n ⋅ Pfn =
i=1 n =1
∞
1
= (1− Pf ) ⋅ Pf ⋅ ∑ n ⋅ Pfn−1 = (1− Pf ) ⋅ Pf ⋅ =
n =1 (1− Pf )2
Pf
=
1− Pf
Total average Pf 1
delay per frame: t 0 + time - out ⋅ E[# of transmiss in error] = t 0 + time - out ⋅ ≈ t0
1- Pf 1- Pf
 Stop-and-Wait ARQ (cont.) 17

Piggybacking • Stop-and-Wait discussed so far was ‘unidirectional’

• in ‘bidirectional’ communications, both parties send &
acknowledge data, i.e. both parties implement flow control
• piggybacking method: outstanding ACKs are placed in
the header of information frames
• piggybacking can save bandwidth since the overhead from
a data frame and an ACK frame (addresses, CRC, etc) can
be combined into just one frame

S(0) S(0)

0 R(0)
S(1) R(0) S(1)
0
1 R(1)
S(2) R(1) S(2)
1

without piggybacking with piggybacking

 18

(2) Go-Back-N ARQ

 Go-Back-N ARQ 19

Go-Back-N ARQ – overcomes inefficiency of Stop-and-Wait ARQ –

sender continues sending enough frames to keep
channel busy while waiting for ACKs
• a window of Ws outstanding frames is allowed
• m-bit sequence numbers are used for both - frames
and ACKs, and Ws = 2m-1

Go-Back-4: 4 frames are outstanding; so go back 4

fr fr fr fr fr fr fr fr fr fr fr fr fr fr Time
0 1 2 3 4 5 6 3 4 5 6 7 8 9
A

B
A A A out of sequence A A A A A A
C C C frames C C C C C C
K K K K K K K K K
1 2 3 4 5 6 7 8 9

Rnext 0 1 2 3 3 4 5 6 7 8 9

Assume: Ws= 4
1) sender sends frames one by one
2) frame 3 undergoes transmission error – receiver ignores frame 3 and all subsequent frames
3) sender eventually reaches max number of outstanding frames, and takes following action:
ƒ go back N=Ws frames and retransmit all frames from 3 onwards
 Go-Back-N ARQ (cont.) 20

Sender Sliding Window • all frames are stored in a buffer, outstanding

frames are enclosed in a window
ƒ frames to the left of the window are already
ACKed and can be purged
before ACKs for frames 0 and 1 arrive
ƒ frames to the right of the window cannot be sent
until the window slides over them
ƒ whenever a new ACK arrives, the window slides
after ACKs for frames 0 and 1 arrive to include new unsent frames
and window slides
ƒ once the window gets full (max # of outstanding
frames is reached), entire window gets resent
Receiver Sliding Window
• the size of receiver window is always 1
ƒ receiver is always looking for a specific frame
to arrive in a specific order
ƒ any frame arriving out of order is discarded
and needs to be resent

The complexity of the receiver in Go-Back-N is the same as that of Stop-and-Wait!!!

Only the complexity of the transmitter increases.
 Go-Back-N ARQ (cont.) 21

Problems with • Go-Back-N works correctly (retransmission of

Go-Back-N damaged frames gets triggered) as long as the
sender has an unlimited supply of packets that
(Go-Back-N
need to be transmitted
with Timeout)
ƒ but, in case when packets arrive sporadically, there
may not be Ws-1 subsequent transmissions ⇒ window
will not be exhausted, retransmissions will not be
triggered
ƒ this problem can be resolved by modifying Go-Back-N
such that:
1) set a timer for each sent frame
2) resend all outstanding frames either when window
gets full or when the timer of first frame expires

Window size

5 6 7 0 1 2 3 4 5 6 7 0 1 2 3

ž ¢¤
 Go-Back-N ARQ (cont.) 22

Example [ lost frame in Go-Back-N with time-out ]

Note:
• ACKs number always defines the number of the next expected frame !!!
• in Go-Back-N, receiver does not have to acknowledge each frame received –
it can send one cumulative ACK for several frames
 Go-Back-N ARQ (cont.) 23

Sequence Numbers • m bits allotted within a header for seq. numbers

and Window Size ⇒ 2m possible sequence numbers
ƒ how big should the sender window be!?
ƒ W > 2m cannot be accepted – multiple frames with
same seq. # in the window ⇒ ambiguous ACKs
ƒ W = 2m can still cause some ambiguity – see below
ƒ W = 2m – 1 acceptable !!!

ACK1

ACK1

ACK2

ACK2

ACK3

ACK3

ACK0

ACK3

ACK1

window size 2m = 4 window size 2m-1 = 3

 Go-Back-N ARQ (cont.) 24

Go-Back-N • completely efficient if Ws is large enough to keep channel busy,

and if channel is error free
Efficiency time

time

• in case of error-prone channel, with Pf frame loss probability,

time to deliver a frame is:
ƒ t frame - if 1st transmission succeeds – prob. (1-Pf)
average # of 1
frame/window ƒ t frame + ⋅ Ws ⋅ t frame - if 1st transmission does NOT succeeds –
(re)transmission 1 − Pf
prob. Pf
until a successful
transmission
• total average time required to transmit a frame:
⎛ 1 ⎞ P
t GBN = (1 − Pf ) ⋅ t frame + Pf ⋅ ⎜⎜ t frame + ⋅ Ws ⎟⎟ = t frame + f ⋅ Ws ⋅ t frame
⎝ 1 − Pf ⎠ 1 − Pf

• transmission efficiency
n f − nheader n
1− header
ηGBN =
t GBN
=
nf
(1− Pf ) (∗∗)
R 1+ (Ws − 1)Pf
 Go-Back-N ARQ (cont.) 25

What is total average time required to transmit a frame, assuming Pf?

successful successful
transmission transmission
WS WS

0 1 2 3 4 5 6 7 8 9 1011 0 1 2 3 4 5 6 7 R R R R R R R R 8 9 10 11

tframe ACK keeps window ‘sliding’ tframe

1st attempt successful: t GBN = t frame

2nd attempt successful: t GBN = t frame + WS ⋅ t frame

average case: t GBN = t frame + E[# of transmissions in error] ⋅ WS ⋅ t frame

Pf
E[# of transmissions in error] =
1 − Pf

n f − nheader n
1− header
t GBN = t frame +
Pf
1 − Pf
WS ⋅ t frame ⇒ ηGBN =
t GBN
=
nf
(1− Pf )
R 1+ (Ws − 1)Pf
 Go-Back-N ARQ (cont.) 26

Example [ Stop-and-Wait vs. Go-Back-N ]

nf = 1250 bytes = 10000 bits

nACK = nheader = 25 bytes = 200 bits

Compare S&W with GBN efficiency for random bit errors with pb = 0, 10-6, 10-5, 10-4 and
bandwidth-delay product R*2*(tprop+tproc) = 1 Mbps * 100 ms = 100000 bits = 10 frames →
use Ws = 11.
11

Efficiency pb=0 pb=10-6 pb=10-5 pb=10-4

S&W 8.9% 8.8% 8.0% 3.3%
GBN 98% 88.2% 45.4% 4.9%

• Go-Back-N provides significant improvement over Stop-and-Wait for large delay-

bandwidth product
• Go-Back-N becomes inefficient as error rate increases
 27

(3) Selective Repeat ARQ

 Selective Repeat ARQ 28

Selective Repeat ARQ • Go-Back-N is NOT suitable for ‘noisy links’ – in

case of a lost/damaged frame a whole window
of frames need to be resent
ƒ excessive retransmissions use up the bandwidth
and slow down transmission

• Selective Repeat ARQ overcomes the limitations

of Go-Back-N by adding 2 new features
(1) receiver window > 1 frame, so that out-of-order
but error-free frames can be accepted
(2) retransmission mechanism is modified – only
individual frames are retransmitted

• Selective Repeat ARQ is used in TCP !!!

Window size Window size

already ACKed usable not yet sent out of order buffered acceptable
sent, not yet ACKed not usable but already ACKed (within window)
expected, not yet received not usable

sender window of size WS receiver window of size WR

 Selective Repeat ARQ (cont.) 29

Selective Repeat ARQ Operation

Receiver:
• window advances whenever next
in-order frame arrives
Rnext • out-of-order frames are accepted only
Rnext + WS -1 if their sequence numbers satisfy
Rnext < Rframe < Rnext + Ws

• a negative ACK (NAK) with sequence

number Rnext is sent whenever an
out-of-sequence frame is observed

Sender:
• window advances whenever an ACK
arrives
• if a timer expires, the corresponding
frame is resent, and the timer is reset
• whenever a NAK arrives, Rnext frame
is resent
 Selective Repeat ARQ (cont.) 30

Window Sizes • m bits allotted within a header for sequence numbers

(WS and WR) ⇒ 2m possible sequence numbers
ƒ how big should the windows be!?
ƒ WS and WR = 2m-1 cannot be accepted due to possible
ambiguity as shown below
ƒ W = 2m/2 = 2m-1 acceptable !!!

ACK1

ACK1

ACK2

ACK2

ACK3

window size 2m-1 = 2

window size 2m-1 = 3
 Selective Repeat ARQ (cont.) 31

Selective Repeat • completely efficient if Ws is large enough to keep

Efficiency channel busy, and if channel is error free
ƒ of course, sequence number space must be 2X sequence
sequence number space of Go-Back-N

• in case of error-prone channel, total average time

required to transmit a frame:
t frame nf
t SR = =
1− Pf R ⋅ (1− Pf )

• transmission efficiency

n f − nheader

ηSR
R
= eff =
t SR ⎛ n
= ⎜⎜1− header
⎞
⎟⎟ ⋅ (1− Pf ) (∗∗∗)
R R ⎝ nf ⎠
 Selective Repeat ARQ (cont.) 32

What is total average time required to transmit a frame, assuming Pf?

successful
successful transmission
transmission
on NAK or time-out

0 1 2 3 4 5 6 7 8 9 1011 0 1 2 3 4 5 R 6 7 8 9 101112
tframe
NAK 0

1st attempt successful: t SR = t frame

2nd attempt successful: t SR = t frame + t frame

average case: t SR = t frame + E[# of transmissions in error] ⋅ t frame

Pf
1 − Pf

nf − nheader
t SR = t frame +
Pf
1− Pf
⋅ t frame =
1 nf
⋅
1− Pf R
⇒ ηSR =
t SR ⎛ n
= ⎜⎜1− header
⎞
⎟⎟(1− Pf )
R ⎝ nf ⎠
Stop-and-Wait vs. Go-Back-N vs. Selective Repeat 33

Performance • assume nACK and nheader are negligible relative to nf, and
Comparison
2(t prop + t proc )R WS is for 1 less than the
= L = Ws − 1 number of frames currently in transit
nf
size of the “pipe” in
multiples of frames

• efficiencies of three ARQ techniques are

1
ηSW = ⋅ (1- Pf )
1+ L
1
ηGBN = (1− Pf ) ηSW < ηGBN < ηSR
1+ LPf

ηSR = (1− Pf )

• for 0 < Pf < 1, Selective Repeat provides best performance

• for Pf → 0 Go-Back-N as good as Selective Repeat

 34

ARQ Efficiency Com parison

Selective
1.5 Repeat
Go Back N 10
Efficiency

0.5 Stop and Wait

100
0 Go Back N 100
-9-9 10
10 -8-8 10
-7-7 10
-6-6 10
-5-5 10
-4-4 10
-3-3 -2
10-2 -1
10-1

- LOG(p)
p Stop and Wait
10

Delay-Bandwidth product = 10, 100