CODEWITHSUNDEEP
network-programmingtcp
N. McA.
N. McA.

Reputation: 4946

TCP versions and AIMD

When we talk about TCP we often talk about Additive Increase Multiplicative Decrease.

In particular we suggest that we decrease the Congestion Window Size by a factor of 2 on packet loss. However am I right in thinking that there are in fact multiple approaches?

In TCP-Tahoe we actually don't do AIMD at all. When we time-out or a triple dup-ack occurs, the CWND is set to 1, and slow-start begins again (Note this is not a multiplicative decrease).

In TCP-Reno, we set CWND := CWND/2 on a triple dup-ack, and CWND := 1 on a timeout. (Note only the first instance is a multiplicative decrease)

This division of CWND by two is part of a process referred to as fast-recovery, this is where (and only where) AIMD is implemented.

Is the above correct? Could you therefore identify whether a TCP version was Tahoe or Reno from the sawtooth? Would it be correct to state that Tahoe does not do AIMD?

Upvotes: 2

Views: 2932

Answers (1)

Jalal Mostafa
Jalal Mostafa

Reputation: 1024

What you've said is correct, let me reexplain it with details:

Slow Start

Any TCP congestion control algorithm starts from congestion window size cwnd = 1 MSS (Maximum Segment Size as congestion window size is scaled by bytes) then it starts an additive increase according to the number of received acknowledgements until it reaches the slow start threshold value ssthresh that's the intial advertised window size.

So, let's suppose ssthresh = 8. TCP starts sending the first segment according to cwnd = 1 if an acknowledgement is received cwnd is additively increased by the number of acknowledgements received according to the formula cwnd = cwnd + MSS (this means that the congestion window size is increased by 1 segment).

when cwnd >= ssthresh then each time an ACK is received, increment cwnd as follows: cwnd = cwnd + MSS(MSS/ cwnd) (don't forget that cwnd is in bytes). So cwnd is increased by one segment (=MSS bytes) only if all segments have been acknowledged, e.g.:

let's suppose last cwnd was 8.

cwnd = 8 + 1 * ( 1 / 8) and this is repeated 8 times (because all segments have been acknowledged). So after adding 1 / 8 to cwnd 8 times, the result is 1 MSS added to the last known cwnd which is 8 i.e. new cwnd is 9. Figure 1 - Slow Start

Slow Start Algorithm

If cwnd < ssthresh then
    Each time an Ack is received:
    cwnd = cwnd + MSS
else /* cwnd >= ssthresh */
    Each time an Ack is received :
    cwnd = cwnd + MSS. MSS / cwnd
endif

Response to Congestion

There is 2 ways to detect loss:

  1. TCP retransmission timer has a timeout
  2. Receipt of duplicate ACK

TCP Reno

  • Case 1: Timer Timeout

    Reno drops to cwnd to 1 then reinitialize a slow start with ssthresh = last_cwnd / 2.

  • Case 2: 3 Duplicate Acknowledgemnts Reno do:

    1. sshresh = cwnd /2
    2. cwnd = cwnd / 2
    3. Enters Fast Retransmission state: retransmits the missing packet that was signaled by three duplicate ACKs, and waits for an acknowledgment of the entire transmit window before returning to congestion avoidance.

TCP Tahoe

For both cases, Tahoe always drops cwnd to 1 then reinitialize a slow start with ssthresh = last_cwnd / 2.

Could you therefore identify whether a TCP version was Tahoe or Reno from the sawtooth?

TCP congestion algorithms are always implement in the OS level. Windows and Linux implements the following algorithms (according to this paper): Figure 2 - Congestion Algorithms on Windows and Linux

Would it be correct to state that Tahoe does not do AIMD?

Tahoe only implements Additive Increase and doesn't implement Multiplicative Decrease. Reno implements them both.

Upvotes: 5

Related Questions