CS 144 Checkpoint 3 - TCP Sender

“This week, you’ll implement the “sender” part of TCP, responsible for reading from a ByteStream (created and written to by some sender-side application), and turning the stream into a sequence of outgoing TCP segments. On the remote side, a TCP receiver1 transforms those segments (those that arrive—they might not all make it) back into the original byte stream, and sends acknowledgments and window advertisements back to the sender.”

I find this checkpoint the most difficult one so far. The specification is not clear on details, so it is required to go though all test cases to confirm edge case behaviours, which makes the debugging process daunting and discouraging. I aim to provide a more detailed description and clarification in this post.

We are tasked to implement the TCPSender class with the following interface:

class TCPSender
{
public:
  /* Construct TCP sender with given default Retransmission Timeout and possible ISN */
  TCPSender( ByteStream&& input, Wrap32 isn, uint64_t initial_RTO_ms );

  /* Generate an empty TCPSenderMessage */
  [[nodiscard]] TCPSenderMessage make_empty_message() const;

  /* Receive and process a TCPReceiverMessage from the peer's receiver */
  void receive( const TCPReceiverMessage& msg );

  /* Type of the `transmit` function that the push and tick methods can use to send messages */
  using TransmitFunction = std::function<void( const TCPSenderMessage& )>;

  /* Push bytes from the outbound stream */
  void push( const TransmitFunction& transmit );

  /* Time has passed by the given # of milliseconds since the last time the tick() method was called */
  void tick( uint64_t ms_since_last_tick, const TransmitFunction& transmit );

  [[nodiscard]] uint64_t sequence_numbers_in_flight() const; // How many sequence numbers are outstanding?
  [[nodiscard]] uint64_t consecutive_retransmissions() const; // How many consecutive *re*transmissions have happened?
};

States to track

• ByteStream input_: The input stream we will read from. It is given through the constructor.
• const Wrap32 isn_: The initial sequence number (ISN), also given through the constructor.
• Wrap32 seqno_: The next sequence number. We use and update it when we send new messages. Its initial value should be set to isn_.
• std::optional<Wrap32> ackno_: The largest acknowledgment number we have received so far. It is set to std::nullopt initially since we haven’t received any ackno yet. It is used to maintain the RTO as stated in the spec.
• bool SYNed_: A flag to indicate if we have sent a SYN message. It is set to false initially.
• bool FINed_: A flag to indicate if we have sent a FIN message. It is set to false initially. We need to track the finish state separatly from reader().is_finished() since the event of the stream finishing and the event of sending a FIN message might not happen at the same time. We might not have enough space in the window to send a FIN message when the stream finished, we need to send it next time.
• uint64_t initial_RTO_ms_: The initial value of the retransmission timeout (RTO). It is given through the constructor.
• uint64_t current_RTO_ms_: The current value of the retransmission timeout (RTO). It is set to initial_RTO_ms_ initially. It is used by the retransmission timer, and updated according to the spec.
• uint64_t consecutive_retransmissions_: The count of consecutive retransmissions. It is set to 0 initially, and updated according to the spec.
• uint64_t current_time_ms_: The current time in milliseconds. It is set to 0 initially, and updated by the TCPSender::tick function. It’s used for the retransmission timer.
• uint16_t window_size_: The current window size of the receiver. It is set to 1 initially. It is updated everytime we receive an ACK message.
• uint16_t window_available_: The available space in the window. It is set to 1 initially.
• uint64_t sequence_numbers_in_flight_: The count of sequence numbers in flight. It is set to 0 initially. It should satisfy the invariant that the sum of message.sequence_length() for each message in outstanding_messages_ should be equal to sequence_numbers_in_flight_.
• std::deque<TCPSenderMessage> outstanding_messages_: The list of messages that are in flight. It is empty initially. We add messages to this list when we send them, and remove them when we receive an ACK for them.
• RetransmissionTimer timer_: The retransmission timer.

Window Management

Note that we not only need to keep track of the window size of the client returned from TCPReceiverMessage::window_size, we also need to track which part of the window is “available”. We might fill the window partially in a single TCPSender::push call, maybe because we exhaust the ByteStream (temporarily). The next time when TCPSender::push is called, we should remember that we have already filled part of the window, and we should not fill it again with different data.

If we decide to always fill the window from begin to end, which is not something unreasonable to do, we can keep track of the “available window” information with a single uint16_t variable window_available_. Assume the window is [ackno, ackno + window_size), then we say the interval [ackno + window_size - window_available, ackno + window_size) is available to be filled.

We can maintain the window_available_ variable in each TCPSender::receive call. The next unfilled byte’s index is seqno_, the end of client’s window is message.ackno + message.window_size. It’s not hard to see the available size is the difference between the two, if it is non-negative.

Retransmission Timer

We are suggested to design a separate class RetransmissionTimer to keep track of retransmissions. It is not complicated, but for the sake of completeness, I will include my interface here.

class RetransmissionTimer
{
  bool running_ {};
  uint64_t expiry_time_ms_ {};

public:
  /* Start the timer, if already started, do nothing. */
  void start( uint64_t current_time_ms, uint64_t timeout_ms );

  /* Stop and reset the timer. */
  void reset();

  /* Check whether the timer has expired. Return false if it is not started. */
  [[nodiscard]] bool expired( uint64_t current_time_ms ) const;
};

TCPSender::make_empty_message

An “empty message” is a message with zero size, i.e. it does not take up any sequence number. Therefore it should contain no SYN flag, no data, and no FIN flag. Its sequence number should be the next available sequence number seqno_, but it should not increment seqno_ since it does not really use it. It should also flag the RST flag if needed, the RST flag does not take up any sequence number.

TCPSender::receive

When we receive a new TCPReceiverMessage, we first need to handle all the special cases:

1. What if the RST flag is set in the message? We should set_error on the underlying ByteStream.
2. What if the ackno of the message is empty? It means that the receiver hasn’t received our SYN message yet. We should update the window_size_ and window_available_ variables, and return immediately.
3. What if the ackno returned is impossible? An ackno is impossible if it is greater than or equal to the seqno_, because we havn’t even send the message yet. We should ignore this message.

Now we are ready to handle the normal case. We should first update the window_size_ and window_available_ as described. Then we should handle the case when the receiver gives an ackno that acknowledges the successful receipt of new data mentioned in the spec. Finally, we should look through the outstanding_messages_ and remove the messages that are acknowledged by the receiver.

TCPSender::push

Note that the size of the window might be much larger than the size of each individual message. Thus one call to the TCPSender::push function might end up transmitting multiple messages to fill as much of the window as possible. We should keep trying to send messages as long as 1. we still have available space in the window, and 2. we still haven’t sent the FIN message.

For every message we send, we should:

1. Add the SYN tag if it is the first message (tracked with the SYNed_ flag),.
2. Add the RST tag if the underlying ByteStream has an error.
3. Add the FIN tag if it the underlying ByteStream is finished.
4. Push the right amount of data.
5. Check the FIN tag again. If we haven’t sent the FIN message, but we just finished the stream, and we still have space in the window, we should send the FIN tag with the message.
6. If the message is empty, then we have nothing to send, we can stop here.
7. We assign and maintain the seqno_.
8. We transmit the message and add it as an outstanding message.

If you have passed all the test cases, feel free to try the checkpoint 4 directly! It does not require any modifications to the TCPSender class.

Here is the full TCP RFC for your reference: RFC 793.

This concludes Checkpoint 3.