1.0 Starting a TCP connection

  • TCP connection begins with a client (caller) doing an active open to a server. This server does a passive open.
  • TCP connections are established using a three-way handshake shown below:

  • Segment 1: Sets SYN bit to 1 & sends an initial seq # (x). Note: In Kurose it is called client_isn.
  • Segment 2: Sets SYN and ACK flags to 1, acknowledges clients seq. # (x) by setting AckNum = x + 1. It also states its own sequence #. Sometimes it is known as a “SYNACK” segment.
  • Segment 3: Sets ACK bit to 1 with AckNum = y + 1. SYN = 0.
  • Note 1: For each segment transmitted a timer is started. If the expected response to the transmitted segment is not received then it is retransmitted
  • Question 1: Why is there a 3 way handshake and not a 2 way handshake?
  • Question 2: Why do both parties choose intial sequence numbers?

2.0Terminating a TCP connection

See Kurose’s book, p. 249-253.

3.0 TCP Roundtrip and Timeout

  • TCP guarantees reliable delivery of data. In order to do this it retransmits each segment if an ACK is not received in a specified amount of time.
  • TCP sets a timeout as a function of the RTT (round trip time) between the two ends of the connection.
  • How to determine RTT? This is a tricky question. As it turns out, it needs an adaptive retransmission mechanism.

Read all of section 3.5.3 from your textbook for information on roundtrip and timeout.

4.0 Congestion Control

  • Was introduced into the Internet in the late 1980’s by Van Jacobson, about 8 years after the protocol stack went operational.
  • Prior to this the Internet was suffering from congestion collapse, i.e., hosts sent their data into the Internet as fast as the advertised window would allow, congestion would occur at some router and packets would be dropped. The hosts would time out and resend their packets resulting in even more congestion.

In TCP’s congestion control mechanism works because each source knows how many packets (say x) it can safely have in the Internet (by determining available capacity). Once a source has x packets/segments in transit, the arrival of an ACK lets it know that one (or more) of its packets/segments has been absorbed by the receiving process and that it may put new packets into the network with fear of adding to the congestion. Determining available capacity is extremely hard. Of course, if there were only one sender and receiver (or a fixed number of senders and receivers) the task becomes a lot easier. Unfortunately, the net is a very dynamic medium, so the number of senders and receivers change continuously and therefore the available bandwidth varies as well. Therefore TCP senders need to be able to regulate the number of packets/segments it has in transit. In the following sections we discuss three mechanisms that when viewed together give us the TCP congestion control mechanism.

4.1 AIMD (Additive Increase, Multiplicative Decrease)

TCP maintains a new state variable for each connection (receiving and sending ends), called CongestionWindow (CW), which is used by the source to limit how much data (in bytes) it is allowed to have in transit at a given time. The number of bytes of unacknowledged data is the minimum of the congestion window and the advertised window. Note in our lecture of 17th October, we defined several terms that we reintroduce here

  • LastByteSent (LBS)
  • LastByteAcked (LBA)
  • AdvertisedWindow (AW)
  • EffectiveWindow (EW) – the effective window limits how much data it can send.

The effective window is calculated as follows:

MaxWindow (MW) = MIN(CW, AW).

EW = MW – (LBS – LBA).

The above formulae show that the TCP source cannot send at a rate that is faster than the slowest component will allow. The problem is how to determine CongestionWindow (CW)? Remember in our previous lectures (of 17 October) we defined AdvertisedWindow (AW) and said that the receiver transmitted this to the sender. If we look at the TCP header (page 231 Kurose) we see that there is no way to define CW and thus some other mechanism is needed.

The answer is for the source to determine that the network is congested and that packets/segments are being dropped. It is important to note that the main reason packets are dropped is due to congestion since it is rare for losses to occur due to errors in transmission. Upon detection of congestion, a timeout occurs and the parameter CongestionWindow is reduced to ½ its previous value. This is what is referred to as “multiplicative decrease,” in the heading of this section.

Let us make this more concrete (Kurose p. 263) – consider a case where loss and packet transmission delays are negligible. Therefore, given the above formulae, the sender is able to put CongestionWindow (CW) bytes of data into the connection and after 1 RTT it receives an ACK for the data – therefore as a good approximation, the throughput (rate at which bytes are sent) is CW /RTT bytes/sec. Therefore, by changing CW the throughput can be changed.

In order to continue this discussion we now need the concept of a duplicate ACK (duplicate acknowledgement, p. 244 Kurose). If a sender sends three (say) segments to a receiver and the first and third segment arrives but the second doesn’t then TCP detects a gap in the data stream. However, TCP doesn’t use negative acknowledgements, it continues to send acknowledgements indicating that it is expecting the second segment (remember, the first and third arrived safely). These ACKs are known as duplicate ACKs. In the case of TCP, the sender waits for three duplicate acknowledgements (known as a triple duplicate ACK) before it assumes that the segment is lost and that it needs to retransmit that segment. Loss of segments is used as an indication of congestion.

Consider a case where CW is 16 segments (although it is expressed in terms of bytes). If a loss is detected (triple duplicate ACK), then CW is set to 8 segments. Further losses would lead to values of 4, 2 and finally 1 segment. Note that CW is never let to fall below the size of a single segment that is also known as the Maximum Segment Size (MSS) (defined briefly on page 231 of Kurose).

TCP also needs to be able to increase the window size if the congestion in the network decreases. According to Kurose (p. 264) the increase is more cautious in that TCP increases CW by one segment (one MSS) every RTT provided no loss has occurred. This is known as the “additive increase” part of TCP’s congestion control mechanism. However, what really happens is every time an ACK arrives, CW is changed as follows:

Increment = MSS x (MSS/CW)

CW Increment + CW.

We see that CW is increased by a fraction of MSS every time an ACK is received, rather than one segment (one MSS) every RTT as indicated by Kurose.

It is only after considering additive increase and multiplicative decrease (AIMD) that we see why TCP needs very accurate timeouts. Since section 3.5.3 of Kurose deals with RTT and timeouts we won’t repeat it here.

For a graph of how the overall AIMD process might look like, see page 265 of Kurose.

4.2 Slow Start

On initializing a connection, TCP doesn’t know anything about congestion on the network and an additive increase might not make best use of the available capacity. Therefore, TCP uses something that is known as “slow start.” The source sets CW to one segment (MSS) and sends one segment. When the ACK arrives CW = CW + 1 (i.e, CW is incremented by one) and two segments are sent. When the two ACK s arrive back CW is incremented by two, i.e., CW = 4 and four segments are sent. Thus we see that every RTT the number of packets it sends is doubled.

“Slow start,” might seem to be a misnomer but it needs to be seen in terms of the original behavior of TCP where the sender sent as many segments as AdvertisedWindow (AW) allowed. Even if bandwidth in a network is very high, the combined data of many TCP connections (behaving as described above) might overwhelm the network or the routers in the network. Slow start was introduced to space packets so that such bursty traffic is avoided.

The slow start mechanism is always used in the beginning of a TCP connection and is also used when flow control in TCP (lecture of 17th October) causes the sender to be blocked (p. 248 Kurose). Under these circumstances, the sender will receive an ACK that will open up the entire advertised window (AW). Under such circumstances it makes sense to not send AW (bytes) worth of data all at once but to use the slow start mechanism. What happens is that CW grows exponentially until it reaches ½ the value it was before the timeout event. At this point it goes into additive increase mode (i.e., linear increase). There is a little bookkeeping since TCP needs to keep a record of the congestion window before the time out occurred, i.e., it creates a temporary variable called CongestionThreshold (CT) and sets it equal to CW/2 when timeout occurs.

A good example of how the congestion window varies is shown in page 267 of the textbook (figure 3.51). Especially pay attention to the graphs for TCP Reno (black) and note that we are using the variable CongestionThreshold while Kurose uses the term Threshold. Read the paragraphs on page 267 from the top till the sentence that ends as, “… which will support who knows what kinds of services.”

5. Macroscopic description of TCP throughput

Read page 267-268 of Kurose.

6. TCP delay modeling

Read section 3.72 of textbook.