CS 372 Lecture #19 The Transport Layer:
• Pipeline error recovery • Stop and wait
• Selective Repeat
Note: Many of the lecture slides are based on presentations that accompany Computer Networking: A Top Down Approach, 6th edition,
by Jim Kurose & Keith Ross, Addison-Wesley, 2013.
v
Or•egon State University
TCP sender events #1
Data comes down from application layer:
oCreate segments with sequence numbers
o sequence # is byte-stream number of first data byte
in segment (or based on that number)
oStart countdown timer (if not already running for a previous segment)
oSend segments
oWait for Ack or timeout
TCP sender events #2
If countdown timer expires:
• Retransmit segment that caused timeout • Restart timer
If ACK received:
• Check to see if ACK includes previously unACK’ed segments – update what is known to be ACK’ed
– restart timer if there are outstanding segments
Note: ACK’s are cumulative. The ACK # is always the next expected byte number. This implies that all previous bytes have been accounted for.
Pipeline retransmission scenarios #1
•
l
Seq:::92 8 b
, Ytes data
timeout
timeout
next seq# = 146 (cumulative)
time
segment error
next seq# = 146 (cumulative)
time
segment lost
Host A
Host B
Error: no ACK sent
Host A
Host B
X
loss
Pipeline retransmission scenarios #2
time
ACK lost (A)
next seq# = 120
time
ACK lost (B)
Host A
Host B
Host A
Host B
••••
ll
~
,,..cv:– AC¥:–\’l
~c’l-l-
~\’V
l
G ;’ ~
tes data
timeout
timeout
X
loss
X
loss
Duplicate
discarded
Pipeline retransmission scenarios #3
Seq=92 timeout
Seq=92 timeout
Seq=92 timeout
next seq#
= 120
time
next seq#
= 136 time
Host A
Host B
Host A
Host B
Duplicate
discarded
ACK delayed (A)
0, 16 b
tes data
ACK delayed (B)
Selective Repeat protocol
oSender can have up to “window size” un-ACK’ed packets in pipeline
oReceiver ACKs individual packets
oSender maintains timer for each un-ACK’ed packet
oWhen timer expires, retransmit only the un-ACK’ed packet
Selective Repeat protocol example
kt O :sent lo1 2 314
pktl :sent lo1 2 314
pkt2 :sent lo1 2 314
pkt3 :sent, lo1 2 314
5 6 7 s9 ———….._,~ pktO rcvd, delivered, ACKO sent 011 2 3 415 6 7 8 9
5 6 7 s 9 ——–_,,.C,~ pktl rcvd, delivered, ACKl sent o112 3 4 516 7 s9
pkt3 rcvd , buf fered, ACK3 sent o11?73 4 5I6 7 s9
ACKO rcvd, pkt4 sent
011 2 3 415 6 7 8 9- 7—7′.’.__–a.pkt4 rcvd~ buffered ACK4 sent
ACKl rcvd, pkt5 sent
o1I2 3 4 516 7 s9—/L–..,l__…_pktS rcvd~ buffered ACKS sent
o1ll?J3 4 516 7 s9 o11?73 4 516 1 s9
pkt2 rcvd, pkt 2,pkt 3,pkt 4,pkt5 delivered, ACK2 sent
012345167891
pkt2 TIMEOUT, pkt2 resent
0 1I2 3 4 5I6 7 8 9 – 7 :…_—–:,L._,.L-a.
ACK3 rcvd, nothing sent o1!2 3 4 5l67 s9
TCP Fast Retransmit #1
oSuppose that the packet with sequence #0 gets lost
o Q: When will the packet with sequence #0 get retransmitted?
o A: typically at t1 . We think it is lost when the timer expires
oCan we do better?? o Why wait till timeout?
o We already know the packet is
Remember: lost.
• Sequence# is the number (in the data
stream) of the first byte of the sent segment
• ACK# is the number of the next byte
expected by the receiver.
client
Timer is set at t0
server
Uence #Q
ence #.
Timer expires
at t1
TCP Fast Retransmit #2
Host A
Host B
X
If we receive
many duplicate ACKs for sequence #x2 …
seq # x1 seq # x2
triple duplicate ACKs
… it means packet with sequence #x2 is lost.
Fast retransmit => better performance
seq # x3 seq # x4 seq # x5
ACK x2 ACK x2
time
timeout
TCP Fast Retransmit (recap)
oReceipt of duplicate ACKs indicate loss of segments
oSender usually pipelines segments
oIf segment is lost, there will likely be many duplicate ACKs.
This is how TCP works:
• If sender receives 3 ACKs for the same data, it supposes that segment after ACK’ed data was lost
• fast retransmit:
• resend segment before timer expires
• better performance
Summary Lecture #19
oTCP
ocumulative ACKS
ocount-down timer
ohandling segment errors, segment loss ohandling lost ACK, delayed ACK
oRetransmission protocols oSelective-Repeat ofast retransmission