TCP

The transmission control protocol (TCP) delivers a reliable, in-order byte stream.

• Reliability means that TCP resends lost packets (recursively) until it gives up and shuts down the connection.
• In-order means that TCP only hands out consecutive chunks of data to application.
• Byte stream assumes that there's an incoming stream of data, and attempts to deliver it to the app

Content

What does TCP use:

• checksums
• sequence numbers are byte offsets
• sender and receiver maintains a sliding window
• receiver sends cumulative acknowledgements (like GBN), sender maintains a single retransmission timer, for one packet.
• receivers buffer out-of-sequence packets (like SR)
• it also uses fast transmit, timeout estimation algorithms, etc.

TCP Header format from RFC9293:

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          Source Port          |       Destination Port        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Sequence Number                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Acknowledgment Number                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Data |       |C|E|U|A|P|R|S|F|                               |
| Offset| Rsrvd |W|C|R|C|S|S|Y|I|            Window             |
|       |       |R|E|G|K|H|T|N|N|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           Checksum            |         Urgent Pointer        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                           [Options]                           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               :
:                             Data                              :
:                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	  Note that one tick mark represents one bit position.

The header is made up of:

• source port + destination port (used to mux and demux)
• sequence number (byte offsets, instead of packet id, because TCP is a byte stream)
• acknowledgment (cumulative like GBN) (gives seqno just beyond highest seqno received in order)
• HdrLen (is the number of 4 byte words in the header), 0 (this is reserved for future use and it should be zero), Flags, Advertised window
• Checksum (computed over pseudo-header and data), urgent pointer (not commonly used)
• options (variable)
• Data

Segment

TCP "stream of bytes" service is provided using "TCP segments", which are sent when 1) the segment is full (max segment size), or 2) when the segment is not full, but times out.

Clarifying some terms:

• TCP segment is the unit of data that encapsulates a chunk of data and the TCP header ($\geq$ 20 bytes long). They are no more than Maximum Segment Size (MSS), which refers to the maximum amount of data that can be included in a TCP segment, excluding the TCP header. E.g., up to 1460 consecutive bytes from the stream
• TCP packet is the entire TCP header and data, also referred to as the TCP segment.
• • An IP packet is no bigger than the Maximum Transmission Unit (MTU). E.g., up to 1500 bytes with Ethernet

$MSS = MTU - (\text{IP header}) - (\text{TCP header})$

Sequence numbers

The sequence number is the starting byte offset of data carried in a segment. What is the value of the sequence number?

• $\text{Sequence number} = \text{1st byte in the segment} = \text{ISN} + k$, where ISN is the initial sequence number and $k$ is the starting byte offset of the data carried in this segment.
• Then its the TCP data followed by the TCP HDR.

ACKs always come with a sequence number:

• $\text{ACK Sequence number is the next expected byte} = \text{seqno} + \text{length(data)}$

Suppose the sender sends packet. Data starts with sequence number $X$, and packet contains $B$ bytes $[X, X+1, X+2, \dots, X + B-1]$ Upon receipt of packet, receiver sends an ACK.

• If all data prior to $X$ already received: ACK acknowledges $X+B$ (because that is next expected byte).
• If highest in-order byte received is $Y$ s.t. $(Y+1) < X$, ACK acknowledges Y+1, even if it has been ACKed before.

Example of a typical operation (Note: the seqno of the next packet is the same as the last ACK field; i.e., ACK is beyond the highest seqno already receieved in order).

• sender: seqno=X, length=B
• receiver: ACK=X+B
• sender: seqno=X+B, length=B
• receiever: ACK=X+2B

What happens when there is a loss when using cumulative ACKs:

• sender sends packet with 100B and seqnos: 100, 200, 300, ...
• assume the 5th packet (500) was lost, but no other,
• the stream of ACKs will be 200, 300, 400, 500(rcv'd seqno:600), 500(rcv'd seqno:700), 500 (rcv'd seqno:800), ...

Therefore, having Duplicate ACKs is a sign of an isolated loss. The lack of ACK progress (as we are stuck on 500) means that 500 has not been delivered. Alternatively, a stream of incrementing ACKs means that some packets are being delivered.

When we receive duplicate ACKs, we know there is missing data, so we would trigger early retransmission upon receiving $k$ duplicate ACKs. This is called fast retransmit. ^i1j32e

• TCP uses $k=3$.
• This method of retransmitting upon duplicate ACKs is faster than waiting for a timeout.

Retransmission timeout

Sender maintains a single retransmission timer. If the sender hasn't received an ACK by timeout, we must retransmit the first packet in the window.

How do we pick a timeout value?

• It can't be too long, or the connection has low throughput and is therefore inefficient.
• It can't be too short, or else we could be redundantly retransmitting a packet that was just delayed, leading to duplicate packets.
• The solution: make the timeout proportional to RTT. However, how do we estimate RTT?

Estimating RTT

RTT is estimated by the weighted exponential average of RTT samples. This is because RTT fluctuates a lot, which is why it must be smoothed.

$\text{EstimatedRTT} = (1-\alpha) \cdot \text{EstimatedRTT} + \alpha \cdot \text{SampleRTT}$

Need to differentiate between the real ACK and the ACK of the retransmitted packet.

• When calculating the RTT, how do we know whether this represents the time between retransmission or the time between the original transmission.
• do we even consider retransmission?

We actually want to throw it away- don't use SampleRTT from retransmissions.

• once retransmitted, ignore that segment in the future.

There are two algorithms to estimate the time out value: Karn/Partidge Algorithm Algorithm and Kacobson/Karels Algorithm

Karn/Partridge Algorithm

Compute EstimatedRTT using $\alpha = 0.125$.

Timeout value (RTO) is $\text{RTO} = 2 \times \text{EstimatedRTT}$

• Employs exponential backoff: Every time RTO timer expires, set RTO $\leftarrow$ 2 $\cdot$ RTO (Up to maximum $\geq$ 60 sec).
• Every time new measurement comes in (= successful original transmission), collapse RTO back to $2 \times \text{EstimatedRTT}$

This strategy is sensitive to RTT variations.

Kacobson/Karels Algorithm

Problem to solve: need to better capture variability in RTT.

• It's solution is to directly measure deviation

$\text{Deviation} = | \text{SampleRTT} - \text{EstimatedRTT} |$

DevRTT is the exponential average of Deviation $\text{DevRTT} = (1 - \beta) \times \text{DevRTT} + \beta\times | \text{SampleRTT} - \text{EstimatedRTT} |$

$\text{RTO} = \text{EstimatedRTT} + 4 \times \text{DevRTT}$

Connection Establishment

Recall that Initial Sequence Number (ISN) is the very first byte. We use a number instead of ISN = 0 because of some practical issues:

• IP + port number should be able to uniquely identify a connection.
• Eventually, as these port #'s get used again, there's a small chance an old packet is still in flight.
• Also, others might try to spoof your connection

Hosts exchange ISNs when establishing connection- a three way handshake. These steps are done with every single TCP connection:

• Host A sends a SYN (open; "synchronize sequence numbers") to host B
• Host B returns a SYN acknowledgement (SYN ACK)
• Host A sends an ACK to acknowledge the SYN ACK-
• Data is now sent...

In the header there's a Flag. It can be SYN, ACK, FIN, RST.

In A's initial SYN packet, A tells B to open a connection. What's in it?

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
|    A's port    |    B's port     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
|    A's Initial Sequence Number   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
|               N/A                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
|  5  |  0  | SYN |  Advertised W  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
|    Checksum    |  Urgent Pointer |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• A's port | B's port
• A's initial sequence number
• acknowledgement=N/A
• hdrlen=5 | 0 | flags=SYN | Advertised window
• Checksum | Urgent pointer

In B's SYN-ACK packet, B tells it accepts and is ready to accept next packet. It contains the following:

• B's port | A's port
• B's initial sequence number
• ACK=A's ISN + 1
• hdrlen=5 | 0 | flags=SYN|ACK | Advertised window
• Checksum | Urgent pointer

A's ACK to SYN-ACK. A tells B to open a connection.

• A's port | B's port
• A's initial sequence number + 1
• acknowledgement=B's ISN + 1
• hdrlen=5 | 0 | flags=ACK | Advertised window
• Checksum | Urgent pointer

The sequence looks like this:

Think about this: Should B's initial sequence number = A's initial sequence number

• no

What if the SYN packet gets lost?

• It can be lost due to network or server busy. So eventually, no SYN-ACK arrives, which means the sender retransmits the SYN on timeout.

How should the TCP sender set the timer?

• Consider that the sender has no idea how far away the receiver is, and its hard to guess a reasonable length of time.
• SHOULD (RFCs 1122 & 2988) uses a default of 3 seconds (while others use 6 seconds).

Example: SYN loss during web downloads:

• when the user clicks on the hypertext link, the browser creates a socket and does a "connect," which triggers the OS to transmit a SYN.
• If the SYN is lost: 3-6 seconds of delay, which can be very long. The user may become impatient and can retry
• User triggers an "abort" of the "connect", and the browser creates a new socket and another "connect." This can be effective in some cases.

Connection Teardown

In normal termination the connection ends one side at a time:

• A sends a Finish (FIN) to close and receive remaining bytes. The FIN occupies one byte in the sequence space.
• Other host ACKs the byte to confirm, which closes A's side of the connection, but not B (now the connection is half closed).
• B will close when it likewise sends a FIN. Which A then ACKs, which then closes B's side of the connection.
  • If B's FIN is not ACK'd, then it will retransmit the FIN.

Another style is normal termination, both together. It's the same as before but B sets FIN+ACK together. B then has to wait for A to ACK and then it is considered complete.

Abrupt termination is when A sends a RESET (RST) to B. E.g., application process on A crashed. That's it.

• B does not ack the RST
• Thus, RST is not delivered reliably and any data in flight is lost
• But, if B sends anything more, will elicit another RST.

TCP state transitions can be modeled with a state diagram.