cs144-sp23, Lab Checkpoint 2: the TCP receiver

记录 cs144 Spring-23 Lab2: the TCP receiver 的思路与实践难点。

CS144 Spring 2023 实验仓库 CS144/minnow，备份为 HangX-Ma/minnow 进行版本回退即可。
CS144 Spring 2023 Lab2 项目指导书 - Lab Checkpoint 2: the TCP receiver。
具体的项目实现在个人的 Github。

1. 内容简述

Lab2 将实现 TCP 协议的具体细节， TCPReceiver，以处理传入的字符流数据。如果还记得 Lab1 中的实验框图， TCPReceiver 是 Reassembler 和 ByteStream 的上层封装，它通过 receive() 函数从 peer 端接收数据，经过 Reassembler 处理写入 ByteStream 缓存，应用层就可以通过 TCPSocket 读取数据。

在接收 peer 端数据的同时， TCPReceiver 通过 send() 函数承担着告知 peer 一些重要信息的职责，这些信息包括这两个部分：

Acknowledgment: first_unassembled_index 又称 ackno，是 TCPReceiver 从 peer 发送端希望收到的 第一个字节的索引号。
Flow Control: window size，是输出到 ByteStream 的剩余空间，限制了 TCPSender 发送数据的 index 的实际范围。通过这个 window， TCPReceiver 能够 对输入的数据流量进行控制，限制发送端的数据直到接收端准备好继续接收。

通常将 ackno 称作 window 的索引左边界（Smallest Index），将 ackno + window size 称作 window 的索引右边界（Largest Index）。

2. 64-bit 索引与 32-bit 序列号的转换

TCP segment, wikipedia

Reassembler 重组 substrings 时每一个字节的索引号都是 64-bit，并且其首位 index 始终是从零开始。这是一组在当前技术条件下永远不可能溢出的数据流索引号组。但是在 TCP segment 的头部数据中，这一组 sequence number 又被称为 seqno 是 32-bit 的，这组索引号与前述的数据流索引号在长度上不匹配。 32-bit 的数据可以在 100 gigabits/sec 的传输速率下在 1/3 秒内传输完，因而其可能溢出。这种不匹配引入了一些复杂性：

TCP 的数据流长度是不固定的，但数据段的头部 seqno 仅有 32 位， 4 GiB 大小。当 seqno 到达 \(2^{32} - 1\) 大小后， seqno 会置零。
TCP seqno 的起始位置是任意的， ISN （Initial Sequence Number）可以是 32-bit 中的任意值，避免数据混淆和提高协议的鲁棒性。那么 ISN 就代表了当前数据流的 “零点（zero point）”，或称其为 SYN （beginning of stream）。
有 SYN （beginning of stream）自然也有 FIN （end of stream），它们不属于数据流中的任意字节，仅作为数据流的起始和末尾的两个标识符存在，但他们分别占有一个 seqno。

Sequence Numbers, Absolute Sequence Numbers, Stream Indices

cs144 区分了三种类型的索引值，并给出了一个 “cat” 数据的例子。 seqno， absolute seqno，以及 stream index，这些索引需要我们实现相互之间的转换，并保持转换前后不同数据的这三类索引值之间的关系一致。

wrap 是将 absolute seqno 转换为 seqno， 64-bit 数据本就是 32-bit 数据的倍数，进行 absolute seqno 截断直接和 zero_point 加和就是 wrap 后的结果。

uint32_t 数据类型自动将溢出部分进行了 wrap 操作。
```
  static Wrap32 wrap(uint64_t n, Wrap32 zero_point);
```
unwrap 麻烦一些，但指导书表明 10 行也能搞定。给了 absolute seqno 中的 checkpoint 以及 seqno 中的 zero_point， checkpoint 是 \([SYN,FIN] \in {64 bit}\) 之间的任意一个值。在指导书中有这么一句：

“Given a sequence number (the Wrap32), the Initial Sequence Number (zero point), and an absolute checkpoint sequence number, find the corresponding absolute sequence number that is closest to the checkpoint.”

说明我们实际要转换的是一个 Wrap32 类型的数据，这个数据源就是 this->raw_data_，属于 seqno。
```
  uint64_t unwrap(Wrap32 zero_point, uint64_t checkpoint) const;
```
对于 checkpoint 的作用指导书也说的很明确， seqno 中 17 可能对应着 absolute seqno 的 17，也可能是 \(17 + 2^{32}\) 等等。我们确定变量 seqno_offset = this->raw_data_ - zero_point.raw_data_，写过 Lab0 和 Lab1 应该都清楚， checkpoint 是 first_unassembled_index，它应当比传入的 seqno_offset 的值要小，若 checkpoint >= seqno_offset，我们就需要找到具体偏移了几个 \(2^{32}\)，那最终的 absolute seqno = seqno_offset + UINT32_SIZE_num * UINT32_SIZE。

3. TCP Receiver 实现

cs144 提供了 TCPSenderMessage 和 TCPReceiverMessage, 前者用于 receive 后者用于 send。

receive： 该部分有两个要求
- 在必要时，也就是 message 中包含 SYN 时，需要保存这个 SYN 的 seqno。
- 将 payload 部分的数据推送给 Reassembler， FIN 作为标识符控制 push 过程的终止。
```
 void receive(TCPSenderMessage message, Reassembler &reassembler, Writer &inbound_stream);
```
可以明确的是，在 TCPReceiver 还没有接收到 SYN 时，所有的数据都不应当被送入 Reassembler，因为此时的数据传输还没有开始，所以我们需要有一个标志位表明数据开始传输。

另外传输的时候使用的是 stream_index，而我们得到的是 seqno，首先需要将 seqno 转为 absolute seqno，我们已经写好了 unwarp 函数，需要提供 checkpoint。 checkpoint 是 first_unassembled_index，也就是下一个需要被 buffer 存储的字节。在 Lab0 中我们完成的 Writer 类有一个 bytes_pushed() 函数， bytes_pushed() + 1 = checkpoint。

absolute_seqno 转换为 stream_index 时需要考虑当前的 message 是否有 SYN 部分。我们给 unwrap 提供的 zero_point 是以 SYN 对应的 seqno，若 SYN 在当前的 message 中不存在，则 zero_point 应当为当前 payload 的第一个字节。所以有如下转换满足：
```
 uint64_t stream_index = abs_seqno - 1 + message.SYN;
```
之后我们只需要提供 inbound_stream.insert() 所需要的各个变量即可。
send： 这里只需要注意只有 ackno 是 optional 属性， window_size 是每次都要发送的。如果已经收到 FIN 那段 message，满足 inbound_stream.is_closed() == true 那我们需要增加 FIN 部分的长度。但也别忘了传输开始后， SYN 也是占有一个 seqno 位置的。
```
 TCPReceiverMessage send(const Writer &inbound_stream) const;
```

4. 测试结果

cs144@cs144-ubuntu22:~/cs144-sp23/minnow$ cmake --build build --target check2
Test project /home/cs144/cs144-sp23/minnow/build
      Start  1: compile with bug-checkers
 1/29 Test  #1: compile with bug-checkers ........   Passed   20.37 sec
 ...
      Start 21: recv_connect
20/29 Test #21: recv_connect .....................   Passed    0.09 sec
      Start 22: recv_transmit
21/29 Test #22: recv_transmit ....................   Passed    0.75 sec
      Start 23: recv_window
22/29 Test #23: recv_window ......................   Passed    0.09 sec
      Start 24: recv_reorder
23/29 Test #24: recv_reorder .....................   Passed    0.09 sec
      Start 25: recv_reorder_more
24/29 Test #25: recv_reorder_more ................   Passed    1.86 sec
      Start 26: recv_close
25/29 Test #26: recv_close .......................   Passed    0.09 sec
      Start 27: recv_special
26/29 Test #27: recv_special .....................   Passed    0.10 sec
      Start 28: compile with optimization
27/29 Test #28: compile with optimization ........   Passed   18.11 sec
      Start 29: byte_stream_speed_test
             ByteStream throughput: 0.63 Gbit/s
28/29 Test #29: byte_stream_speed_test ...........   Passed    0.71 sec
      Start 30: reassembler_speed_test
             Reassembler throughput: 1.33 Gbit/s
29/29 Test #30: reassembler_speed_test ...........   Passed    1.23 sec

100% tests passed, 0 tests failed out of 29

Total Test time (real) =  47.45 sec
Built target check2

Website

Transmission Control Protocol - wikipedia

PREVIOUS私有化 Git Pages 源码仓库

NEXTcs144-sp23, Lab Checkpoint 3: the TCP sender