CS144 Lab 2

Lab Checkpoint 2: the TCP receiver

Checkpoint2 spec

The TCP Receiver

In this lab, we implement the TCP Receiver. The TCPReceiver receives messages from the peer’s sender (via the receive() method) and turns them into calls to a Reassembler, which eventually writes to the incoming ByteStream. Applications read from this ByteStream.

Meanwhile, the TCPReceiver also generates messages that go back to the peer’s sender, via the send() method. These “receiver messages” tell the sender:

1. the index of the “first unassembled” byte, which is called the “acknowledgment number” or “ackno.” This is the first byte that the receiver needs from the sender.
2. the available capacity in the output ByteStream. This is called the “window size”.

Together, the ackno and window size describe describes the receiver’s window: a range of indexes that the TCP sender is allowed to send.

Translating between 64-bit indexes and 32-bit seqnos

In the TCP headers, space is precious, so each byte’s index in the stream is represented not with a 64-bit index but with a 32-bit “sequence number,” or “seqno.”

在这一部分，我们需要实现一个Wrap32类中的wrap和unwrap方法来实现64位的absolute sequence number和32位的sequence number之间的转换。

其中，wrap方法负责将一个64位的absolute sequence number转换为一个32位的sequence number，比较简单，只需要一行代码。

unwrap方法负责将一个32位的sequence number转换为64位的absolute sequence number。这里稍微麻烦一点的地方在于一个32位的sequence number理论上可以转换为无穷多个以$2^{32}$为间隔的absolute sequence number，需要通过给定的checkpoint来定位我们需要的absolute sequence number。

因此，我们的问题是：

如何找到最接近checkpoint的absolute sequence number?

首先我们要获得这个32位的sequence number与ISN的offset，这个offset将会是最小可能的absolute sequence number，然后每增加$2^{32}$就又会得到一个可能的absolute sequence number。

我第一个想到的方法是用一个while循环，每次循环增加$2^{32}$，直到找到那个刚好小于checkpoint和刚好大于checkpoint的两个相邻的absolute sequence number，比较并返回那个更接近checkpoint的值。但是这样的话如果checkpoint很大循环次数将会很多很浪费时间，实测这样实现的话test会超时，需要更换思路。

其实解决方案很简单，思考如何根据checkpoint直接定位到相邻可能的absolute sequence number？

最后要注意，测试前可能需要将debug行注释掉否则可能会超时（至少我的情况是这样）。

Implementing the TCP receiver

在这一部分，我们需要实现TCPReceiver类，这个类需要一个receive方法来接收TCPSenderMessages,并将其中的payload交给Reasssembler;还需要一个send方法来acknowledge收到的message，发送TCPReceiverMessages。

为什么在Reassembler前面需要一个TCPReceiver类，不能直接将接收到的segment交给Reassembler？

由TCPSenderMessage类:

struct TCPSenderMessage
{
  Wrap32 seqno { 0 };

  bool SYN {};
  std::string payload {};
  bool FIN {};

  bool RST {};

  // How many sequence numbers does this segment use?
  size_t sequence_length() const { return SYN + payload.size() + FIN; }
};

可以看出TCP segment不仅仅包含data(payload)，还有seqno和SYN,FIN,RST flag。

TCPReceiver的receive方法需要负责：

一句话概括：分析接收到的TCP segment(TCPSenderMessage)后，将payload交由Reassembler处理。

具体来说：

1. 根据RST flag判断是否有error。

2. 根据SYN和FIN flag判断是byte stream的起始segment还是终止segment：如果是起始segment，那么TCPReceiver需要记录下ISN(Initial Sequence Number)，并且通知Reassembler我们已经接收到byte stream的起始segment（这是为了让Reassembler从index 1开始接收substring，因为index 0需要保留给SYN flag）；如果是终止segment，TCPReceiver需要先在自己内部记录下来已经接收到了FIN flag，等到所有存储在Reassembler中的substrings全部push到byte stream之后（也就是当ByteStream的写入端关闭之后），再通知Reassembler我们已经接收到byte stream的终止segment（这是因为当接收到完整的byte stream之后，最后send方法发送的ackno需要包含最后的FIN flag）。

   需要注意，虽然SYN和FIN flag本身不属于payload，也不需要push入byte stream，但是他们各需要占据一个sequence number，也就是Reassembler的index 0和最后一个index。需要思考需要怎样修改我们之前在Checkpoint1中实现的Reassembler中的next_byte_index方法。

3. 根据记录下的ISN作为zero point和Reassembler在等待的next byte作为checkpoint，运用我们之前实现的Wrap32类将segment中32位的seqno转化为Reassembler中从0开始的64位的index(absolute sequence number)，并将转化后的index作为first_index，message的payload作为data，交给Reassembler处理。

TCPReceiver的send方法需要负责：

一句话概括：根据接收到的TCP segment，发送TCPReceiverMessage来告知TCP的发送端我们已经已接收到这个segment。

struct TCPReceiverMessage
{
  std::optional<Wrap32> ackno {};
  uint16_t window_size {};
  bool RST {};
};

具体来说：

1. 如果byte stream有error，设置RST flag为true。
2. 设置ackno为Reassembler正在等待的next byte对应的sequence number（用到Wrap32类将64位的next_byte_index(absolute sequence number)转化为32位的sequence number）。
3. 设置window_size为Reassembler和ByteStream的available capacity，用来通知TCP的发送端进行flow control。

补充：

以上的步骤都是笔者自己的实现思路，其中对SYN和FIN的处理有些messy，特别是考虑SYN和FIN的sequence number后我修改了Reassembler获取next_byte_index的方式。并且我用到了Reassembler中的一些private成员变量和函数，因此在Reassembler中将TCPReceiver声明为了友元，破坏了一定的封装性。但无伤大雅，最终能work，读者可梳理思路自行寻求更优的实现。

根据cs1441官方的spec，TCPReceiver的代码量只在15行左右，但要完全考虑到tests中的所有case实现起来还是有些tricky，笔者实现过程中遇到问题的test包括recv_connect, recv_close, recv_special，供读者参考。

Finish!

All tests in check2 pass!