CS144 Lab 3

Lab Checkpoint 3: the TCP sender

Checkpoint3 spec

In Checkpoint0, we implemented a flow-controlled byte stream(ByteStream).

In Checkpoint1 and 2, we implement a Reassembler and TCPReceiver to translate from segments carried in unreliable datagrams to an incoming byte stream.

In Checkpoint3, we'll implement the sender side of the TCP connection. The TCPSender translates from an outbound byte stream to segments that will become the payloads of unreliable datagrams.

The TCP Sender

In this lab, you will 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.

TCPSender is responsible for:

1. Keep track of the receiver's window.
2. Keep sending segments until either the window is full or the outbound ByteStream has nothing more to send.
3. Keep track of which segments have been sent but not yet acknowledged("outstanding" segments) by the receiver.
4. Re-send outstanding segments if enough time passes since they were sent, and they haven't been acknowledged yet.

How does the TCPSender know if a segment was lost?

Periodically, the owner of the TCPSender will call the tick method. The TCPSender is responsible for looking through its collection of outstanding TCPSenderMessages and deciding if the oldest-sent segment has been outstanding for too long without acknowledgement.

To be specific:

1. The TCPSender stores the initial value of RTO(retransmission timeout).

2. You will implement the retransmission timer: an alarm that can be started at a certain time, and the alarm expires once the RTO has elapsed. Every time a segment containing data is sent, if the timer is not running, start it running. When all outstanding data has been acknowledged, stop the retransmission timer.

3. When tick is called and the retransmission timer has expired:

   • Retransmit the earliest(lowest sequence number) segment that hasn't been fully acknowledged by the TCP receiver. You should store the outstanding segments in some internal data structure.

   • If the window size is nonzero:

     (a). Keep track of and update the number of consecutive retransmissions.

     (b). Double the value of RTO.

   • Reset the retransmission timer and start it.

4. When the receiver gives the sender a new ack message:

   • Set the RTO back to its initial value.
   • If the sender has any outstanding data, restart the retransmission timer.
   • Reset the consecutive retransmissions back to zero.

以上就是TCPSender的retransmission logic，详细见cs144官方spec。

简单总结一下就是TCPSender会在内部存储outstanding segments。TCPSender的owner会周期性地调用tick函数查看retransmission timer是否expired，如果是则retransmit最早的outstanding segment，double RTO防止网络堵塞加剧retranmission的负担(exponential backoff)，并重启retransmission timer。当TCPSender接收到新的acknowledgement的时候，重设RTO为最初值并重启retransmission timer(如果还有outstanding segments)。

Implement the TCP sender

You should implement the interface that your TCPSender provides:

• void push( const TransmitFunction& transmit );

Read from the outbound byte stream and send as many TCPSenderMessages as possible, as long as there are new bytes to be read and space available in the window.

Make sure that every TCPSenderMessage you send fits fully inside the receiver’s window. Make each individual message as big as possible, but no bigger than the value given by TCPConfig::MAX PAYLOAD SIZE.

What should my TCPSender assume as the receiver’s window size before the receive method informs it otherwise?

One.

What if the window size is zero?

If the receiver has announced a window size of zero, the push method should pretend like the window size is one. The sender might end up sending a single byte that gets rejected by the receiver, but this can also provoke the receiver into sending a new acknowledgment segment where it reveals that more space has opened up in its window.

This is the only special-case behavior your implementation should have for the case of a zero-size window. The TCPSender shouldn’t actually remember a false window size of 1. The special case is only within the push method. Also, N.B. that even if the window size is one (or 20, or 200), the window might still be full. A “full” window is not the same as a “zero-size” window.

• void receive( const TCPReceiverMessage& msg );

A message is received from the receiver, conveying the new left (= ackno) and right (= ackno + window size) edges of the window. The TCPSender should look through its collection of outstanding segments and remove any that have now been fully acknowledged (the ackno is greater than all of the sequence numbers in the segment).

• void tick( uint64 t ms since last tick, const TransmitFunction& transmit );

The sender may need to retransmit an outstanding segment.

• TCPSenderMessage make_empty_message() const;

The TCPSender should generate and send a zero-length message with the sequence number set correctly.

Note: a segment like this one, which occupies no sequence numbers, doesn’t need to be kept track of as “outstanding” and won’t ever be retransmitted.

我的实现思路

前言：认真读spec！至少将spec的第二板块读3遍再开始coding：

2 Checkpoint 3: The TCP Sender

这个lab的整体实现难度不难，很大一部分原因是因为spec讲解得非常清晰。就我自己实现起来比lab2还要轻松一些。主要难度在于细节点和corner case非常多，因此需要大量的时间面向test来debug。我自己debug花的时间比coding的时间还要长。

接下来进入正题：

TCP Sender的实现可以分成3大部分，难度我认为也是逐级递增的：

1. Retransmission (retransmission timer + tick)
2. Window (sender's window + receiver's window)
3. Push + Receive

• Retransmission

Retransmission的逻辑其实是TCP Sender的一大重难点，但这部分(retransmission timer + tick)在spec中讲解得非常详细。并且，在这个lab中要求我们实现的Retransmission逻辑其实是真实的TCP协议的Retransmission逻辑的简化版本，真实的TCP协议的Retransmission包含更多细节(如3次duplicate ACK的应对, congestion control…)。因此这部分实现起来比较轻松。

这里再放一下我总结的Retransmission logic，如果spec读起来有点费解的话可以参考：

TCPSender会在内部存储outstanding segments。TCPSender的owner会周期性地调用tick函数查看retransmission timer是否expired，如果是则retransmit最早的outstanding segment，double RTO防止网络堵塞加剧retranmission的负担(exponential backoff)，并重启retransmission timer。当TCPSender接收到新的acknowledgement的时候，重设RTO为最初值并重启retransmission timer(如果还有outstanding segments)。

我建议单独创建一个Retransmission timer类，与TCPSender类区分开来，结构更清晰。

• Window

这部分在spec中讲解得比较模糊，需要自行理解与实现！

在spec中反复提到的window，其实指的是TCPSender接收到的acknowledge message中包含的Receiver's window。回顾Checkpoint1，我们画过一张Receiver's window:

但spec中没有提到，需要我们自己理解的是，TCPSender的window与TCPReceiver的window是不同的，为了区分这两端的window，我在TCPSender端维护了一个sender's window，用来与上面的receiver's window进行区分，如下图：

希望这张图能帮助你理解Sender's window和Receiver’s window的区别与联系。其中绿色区域代表的是Receiver已经acknowledge的bytes范围，红色区域代表的是outstanding segments，蓝色区域是push方法允许transmit的bytes范围，也就是Sender's window。

TCPSender需要一种数据结构来存储outstanding segments，以便在传输过程中丢失时可以retransmit。由Retransmission logic可知我们每次retransmit的是earliest outstanding segment，也就是seqno最小的segment，所以思考可以用什么数据结构来存储outstanding segments？

联系Checkpoint1，最容易想到的就是用map，这样每次retransmit只要移除map的第一个元素就可以了。

• Push + Receive

这也是这个lab最tricky的部分，尤其是push的实现，细节点很多。主要的实现逻辑在spec中已经说明得比较详细，我在此提示一些注意点：

1. void push( const TransmitFunction& transmit );

   The TCPSender is asked to fill the window from the outbound byte stream: it reads from the stream and sends as many TCPSenderMessages as possible, as long as there are new bytes to be read and space available in the window.

   好好理解上面加粗的这段话，什么叫做只要outbound stream中还有可读取的new bytes和window(Sender's window)还有空间就不停地send segments?

2. 当receive方法接收到一个message告知自己Receiver's window size = 0时，push需要将其作为special case处理，详细见spec。

3. 在debug时尤其注意SYN和FIN flag带来的各种corner case。这部分我们在Checkpoint2中已经有一定的应对经验，但在这个lab中处理起来会更麻烦一点。

4. 在push和receive中，需要时刻注意Sender's window的变化。

TCP Sender Finish!

All tests in check3 pass!

恭喜！到这里你已经实现了一个完整可运行的TCP协议了！

Hands-on activity

恭喜！到这里你应该已经实现了一个完整可运行的TCP协议了！

在这一部分，我们要实际验证这个TCP协议栈确实能work，我们要：

1. 尝试让你的TCP协议与Linux的TCP协议对话
2. 尝试在你的TCP协议与Linux的TCP协议之间传送文件
3. 与其他同学的TCP协议通话（要用到CS144内部网络，我们做不了）
4. 在你的TCP协议栈之上重新实现Web fetcher

我这里就只展示最后一条：

webget revisited

在lab0中，我们在Linux的TCP协议之上，实现了一个使用TCP Socket传输http协议信息，来获取网页的Web fetcher(get_URL)。

如今，尝试换成在我们自己实现的完整TCP协议栈之上，改写这个Web fetcher（只需要将Linux的TCPSocket换成我们自己的CS144TCPSocket）。

Our own TCP implementation works! 😊