[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

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

	# 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
		if NumDups == 3 then

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

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

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

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

	# 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