[ee122] pseudo-code for TCP congestion control

[vern at cs.berkeley.edu]

A number of students asked for pseudo-code for how a TCP sender executes
the congestion control and retransmission algorithms, so I've put together
the appended.  If you have questions about it, I encourage you to send them
to the mailing list, as likely others will be wondering the same things.
(Also, it's possible there are some bugs in this, as it's something I've
newly written - if you spot something that doesn't look right, please feel
free to point that out as well.)

		Vern


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

	# We do not cut CWND all the way down to the beginning of
	# a Slow Start.  Instead, we just halve it and will proceed
	# in Congestion Avoidance.
	CWND <- SSTHRESH

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