Reliable Transport via TCP

computer systems › 6.033 system design

Reliable transport

Reading: rtp guide

  1. Best-effort networks do not provide reliability.
  2. TCP provides reliability and congestion control on the best-effort network.
  3. The goal of reliable transport protocol is exactly-once, in-order delivery.

This guide uses layered model (two-layer version, app + transport) as examples.

  1. packet structure: header + data (+ trailer) -> in-order

    • metadata: source addr, dest addr, sequence number

  2. two machanisms -> reliability

    • acknowledgements: Every time the receiver receives a packet, it will send a small packet — an “ACK” — back to the sender.
    • sliding-window protocol: as the communication occurs, the sender’s window slides across the stream of packets it has to send.
      • guarantee: no more than W packets in its window at a time
    • terms: waterfall diagram, outstanding packet, window (the collection of outstanding packets), window size, cumulative ACKs (an ACK for packet k means the receiver has received all packets up to and including k)

  3. Error cases

    • packet loss: retransmissions, the sender will retransmit a lost packet if it doesn’t receive an ACK for it after a certain amount of time
    • ACK loss
      • The sender will retransmit the packet 2. The receiver has received two copies of packet 2. It will ACK both of them.
      • Receiver should not deliver both packet 2 so it keeps track of the received packets but that have not sent to the application yet in its buffer.
    • terms: retransmission timeout (RTO)

  4. Real world:

    • set RTO: RTO in the guide is assumed larger than a round-trip-time.
    • set W: many sender and receivers on the internet; the amount of data changes. Find an optimal W.

  5. Reliable transport protocol

    At the sender:

    • The sender will keep a list of all of its outstanding packets. We’ll call that list outstanding_packets; initially it is empty.
    • If len(outstanding_packets) < W, transmit the next packet (call it packet k). Store packet k and the current time in outstanding_packets.
    • When an ACK for packet k is received, remove packet k from outstanding_packets, as well as any packets with sequence number less than k.
    • Periodically check the packets in outstanding_packets; if any were received more than RTO seconds ago, re-transmit them.

    At the receiver:

    • Send an ACK for every received packet. If the sequence number of this ACK is k, that indicates that all packets up to and including packet k have been received.
    • Save delivered packets — ignoring duplicates — in a local buffer.
    • Keep track of the next packet the receiving application expects. After each reception, deliver as many in-order packets as possible.

Some thinking

  1. A receiver knows the packes out-of-order when the receiving sequence number is not sequential.
  2. In ACK lost case:
    • The sender can not tell the difference between ack 2 lost and one where packet 3 itself is lost. Senders consider a packet has been lost when it did not receive corresponding ack signal. In this case, sender hasn’t received ack3 therefore it’s either the packet 3 was lost or the ack2 was lost.
    • Why the receiver need to send an ACK for the second copy of packet 2? Though the receiver has received the copy of packet 2, it needs to ack the sender that it is indeed received. However, it can just discard packet 2 in the second time.
    • If the ACK for packet 3 had arrived before the sender’s retransmission of packet 2, could the sender have avoided that retransmission? (I.e., is there a way for the sender to tell that packet 2 had actually been received?) No, the sender will still retransmit packet 2. The sender should be aware of the packets that have been successfully received.

tcpdump

1
2
tcpdump -r tcpdump.dat > /tmp/outfile.pcap
mv /tmp/outfile.pcap outfile.txt

example:

A packet sent from willow to maple:

00:34:41.474225 IP willow.csail.mit.edu.39675 > maple.csail.mit.edu.5001: Flags [.], seq 1473:2921, ack 1, win 115, options [nop,nop,TS val 282136474 ecr 282202089], length 1448

Maple receives the packet and sends ack to willow:

00:34:41.482047 IP maple.csail.mit.edu.5001 > willow.csail.mit.edu.39675: Flags [.], ack 2921, win 159, options [nop,nop,TS val 282202095 ecr 282136474], length 0

How to read the log: timestamp, IP, source addr > dest addr, length is for seq in sender.

Definition in TCP differs from the guide:

  • The ACK reflects the next byte that the receiver expects.
  • There is one sequence number per byte of data.