13. Transport Layer Protocol - Reliable Data Transfer

TCP Segments

TCP will divide each message into segments - the sequence number for each segment is the index of the first data byte in the segment. In practice, a random sequence number is used for the initial segment’s sequence number.

The receiver’s ACK message contains the index of the largest byte received: the segment’s sequence number plus the number of data bytes.

TCP uses a single retransmission timer.

Simplified TCP sender (without refinements below):

next_sequence_number = initial_sequence_number
send_base = initial_sequence_number
while True:
  if # data received from upper layer:
    segment = create_tcp_segment(next_sequence_number)
    if timer is None: # no unacknowledged segments in the window
      timer = start_timer()
    send_packet(segment)
    next_sequence_number += len(segment.data)

  elif # timer expired:
    # re-send the segment with the oldest sequence number 
    segment = unacknowledged_packets_in_window()[0]
    send_packet(segment)
    timer = start_timer()

  elif # ack received:
    ack = get_sequence_number()
    if ack > send_base:
      send_base = ack # cumulative ACK
      if len(unacknowledged_packets_in_window()) != 0:
        timer = start_timer()

Some refinements:

• When the timer expires, double the timeout interval: timeout_interval *= 2
  • The expiration may be an indication of congestion
  • Typical initial value is one second
• When the timer is restarted, reset the timeout interval to its initial value
• Timer restarts occur when an ACK arrives or data is received from the upper layer AND there are currently no unacknowledged segments
• Fast retransmit: If the sender receives three ACKs with the same segment number, retransmit it before the timeout
• ACKs coming back may also be a signal that the network is not too congested

Events on the receiver side:

• In order segment with expected sequence number arrives:
  • Wait 500 ms; if no segment comes within this time, send an ACK
• Above, but there is already another segment with pending ACK:
  • Immediately send an ACK, acknowledging the arrival of both packets
• Out-of-order segment with higher-than-expected sequence number:
  • Immediately send a duplicate ACK with the sequence number of the next expected byte
• Arrival of segment that partially/completely fills a gap:
  • If the segment fills in the start of the gap, immediately send an ACK

TCP is a mixture of the go-back-N and selective repeat strategies:

• It uses cumulative ACK, similar to GBN
• Out-of-order segments are often buffered, similar to SR
• When there is a timeout, the sender retransmits only the smallest unacknowledged packet, unlike GBN

Setting the Timeout Value

The timeout value should be longer than the round-trip time, so the first step is to find this value.

The SampleRTT will be the time from segment transmission to ACK, with the condition that retransmissions should not be used - the ACK for the first transmission could arrive after the sender retransmits, giving a wrong value.

The RTT varies over time, so several samples are required. This is done using exponential weighted moving average, which puts more weights on more recent samples:

$EstimatedRTT = (1 - \alpha) \cdot EstimatedRTT + \alpha \cdot SampleRTT$, where $\alpha$ is typically a value such as $0.125$.

An estimate of the variability is also required:

$DevRTT = (1 - \beta) \cdot DevRTT + \beta \cdot |SampleRTT - EstimatedRTT|$, where $\beta$ is typically a value such as $0.25$.

With these two values, the timeout interval can be calculated:

$TimeoutInterval = EstimatedRTT + 4 \cdot DevRTT$