[ee122] corrected pseudo-code for TCP congestion control (fix for FastRetransmit)
Vern Paxson
vern at icir.org
Mon Nov 5 23:37:07 PST 2007
Initialization:
# Congestion window. Actual window used by sender is minimum of
# this and the "offered window" specified by the receiver in each
# acknowledgment (or data packet, for that matter) they send to us.
CWND <- MSS
# Slow-Start threshold. If CWND is less than or equal to this value,
# then we operate in Slow Start. If CWND is larger than this value,
# then we operate in Congestion Avoidance, i.e., linear increase.
SSTHRESH <- Infinity
# The following variable holds the value of the highest sequence
# number we've sent.
MaxSent <- 0
# The following variable holds the highest sequence number that the
# receiver has acknowledged.
MaxAcked <- 0
# Count of how many duplicate acks ("dups") we've received.
NuMDups <- 0
# Now that we've initialized, we send as much data as allowed,
# which will be limited by CWND to a single full-sized (MSS) packet.
SendPackets(1, CWND)
Upon receiving an ACK for sequence AckSeq:
if AckSeq == MaxAcked && offered window hasn't changed then
++NumDups
if NumDups == 3 then
FastRetransmit()
return
# Not a duplicate ack.
NumDups <- 0
update offered window
if AckSeq > MaxAcked then
# This acknowledges new data.
MaxAcked <- AckSeq
free up memory buffering data up to MaxAcked
# Update the operation of the retransmission timer.
if this ack gives us a new RTT measurement
update our RTT estimators
recompute RTO based on new estimates
restart retransmission timeout
# Update congestion control window.
if CWND <= SSTHRESH then
# We are in Slow Start. Note, some TCPs use
# a test of CWND < SSTHRESH instead of <=.
CWND += MSS # increase by one packet per ack
else
# We are in Congestion Avoidance - linear increase.
# Here we use the form that makes a small update
# for each incoming ack, and is not quite linear.
CWND += MSS * MSS / CWND
# Send any new data allowed by changes from this ack to either
# the offered window, CWND, or MaxAcked.
Window <- Min(offered window, CWND)
if MaxAcked + Window > MaxSent then
# Send all data between MaxAcked+Window and what we've
# sent so far.
SendPackets(MaxSent, MaxAcked + Window - MaxSent)
Upon a retransmission timeout:
SSTHRESH <- CWND / 2 # multiplicative decrease
# Begin Slow Start.
CWND <- MSS
# Exponentially back off retransmission timer.
RTO <- RTO * 2
# Make no assumptions about the past. In particular,
# do *not* presume that any packets sent past this one
# have made it to the receiver. If we left MaxSent alone,
# then upon receiving an acknowledgment for the packet
# we're about to send, we often wouldn't be able to send any
# additional data since CWND wouldn't extend us past the
# old value of MaxSent.
MaxSent <- MaxAcked
NumDups <- 0
# Retransmit a single packet, namely the first one for which
# we haven't received an ack.
SendPackets(MaxAcked, MSS)
function SendPackets(StartingSeqNum, Size)
# Note, in this example we always send full-sized packets.
FinalSeq <- StartingSeqNum + Size - 1
while StartingSeqNum < FinalSeq do
transmit an MSS-sized packet with sequence number StartingSeqNum
StartingSeqNum += MSS
if FinalSeq > MaxSent then
MaxSent <- FinalSeq
function FastRetransmit()
# Multiplicative decrease.
SSTHRESH <- CWND / 2
# Cut CWND all the way down to begin Slow Start. However,
# we won't actually slow-start unless only a single packet
# (or in some cases a few) was lost and the next ack we
# receive is for all of the outstanding data.
#
# FYI, a refinement to FastRetransmit, termed "Fast Recovery",
# doesn't cut CWND in this fashion. By keeping CWND larger
# (which it does in a somewhat peculiar fashion), it lets
# us continue to transmit data when more duplicate ACKs arrive,
# and to wind up right at the correct rate (i.e., SSTHRESH)
# when all the lost data has been retransmitted.
CWND <- MSS
# Note that unlike how we handled a retransmission timeout,
# here we do *not* alter MaxSent. This means that if we
# receive an ack for just the packet we're retransmitting,
# instead of an ack further along that includes some of the
# packets we sent earlier, then we might not be able to send
# anything new in response to that ack. Basically, we're
# betting here that only a single packet has been lost, and
# once we retransmit it the receiver will send us an ack
# all the way up to MaxSent. If that's not the case, then
# we will stall until RTO goes off for a timeout retranmissions.
# Retransmit a single packet - the one called for by the dups.
SendPackets(MaxAcked, MSS)
More information about the ee122
mailing list