cs144-sp23, Lab Checkpoint 3: the TCP sender

记录 cs144 Spring-23 Lab3: the TCP sender 的思路与实践难点。前面一些内容看起来像翻译，但其实也是做一遍逻辑梳理，之后落实思路会更清晰一些。

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

1. 内容简述

Lab3 将实现 TCP 中的 TCPSender，其需要完成的功能有：

跟踪 Receiver 的 TCPReceiverMessage 信息，通过将 ByteStream 的数据以 TCP Segments 的格式不断发送，尽可能地填满 window，直到 window 满了或者 ByteStream 中没有任何东西可以发送。
跟踪那些已经发送但还没有被接收的 segments，通常将这些数据被称为 “outstanding segments”。
若是这些 segments 在足够长的时间后没有没接收，则重传这些 segments 数据。

这些功能实现了 “automatic repeat request (ARQ)” 机制， TCPSender 的任务就是确保 TCPReceiver 能收到每个字节至少一次。

2. TCPSender 如何监测丢包

TCPSender 会跟踪那些 outstanding segments 的状态，周期性调用 tick 函数以指示这些 segments 自发出以来所经过的时间。 TCPSender 会在内部的存储空间存储 TCPSenderMessages 的信息并遍历这个集合，找出那些 已发出但经过时间太久但还未被接收 的 segments 进行 数据超时重传，直到所有的 seqno 都被接收。

那么如何界定 已发出但经过时间太久 这个定义就尤为重要，太长的等待时间会增加通信延时，而太短的等待时间则会浪费网络存储空间以及增大开销。需要注意如下几点：

tick 函数每隔几毫秒需要调用一次，记录自上一次调用以来经过的时间，并以此记录 TCPSender 存在的总时长。 time 以及 clock 这类与操作系统和 CPU 相关的函数不允许调用，否则会导致 TCP 工作异常。
retransmission timeout (RTO) 在 TCPSender 初始化时会初始化 _initial_retransmission_timeout，该值始终不变而 RTO 会不断改变（可能为初值的两倍，或者等于初值）以记录 outstanding segments 在超时重传前所经过的时间。
重传定时器 timer 以 tick 为时间单位， timer 会在某个时间启动，在经过 RTO 时间后失效。
包含数据的 segment 被传输后 timer 会被启动，直到经过 RTO 毫秒后 timer 会失效。
当所有的 outstanding 数据都被接收后，服务于重传机制的 timer 将会被停止。
以下信息与 tick 函数的实现密切相关

若是 tick 被调用而 timer 已经失效了：
1. 将时间最早的未被接收的 segment 进行重传（seqno 最小的那个）。
2. 若此时 window size 非零：
  - 跟踪记录连续 重传的数量，并在每次重传后进行累加， TCPConnection 会使用这个信息用以判断 TCP 连接的可靠性，太多连续的重传意味着 TCP 连接不稳定需要终止。
  - 设置 RTO 值为原来的两倍。 “exponential backoff” 以降低较差网络的重传速度，避免加深网络的拥堵。
3. 重置 timer 并启动，使其在 RTO 毫秒之后失效（需要考虑 RTO 已经翻倍）。
以下信息与 receive 函数的实现密切相关

当接收方给发送方传输了 ackno 表示成功接收了新的数据（这个 ackno 比之前任何一个的 absolute seqno 都要大）:
1. 需要将 RTO 设置为其初始值。
2. 如果发送方仍有 outstanding 的数据， timer 需要重启并将会在 RTO 毫秒后失效。
3. 重置前述的 连续重传数量 为 0。

3. TCP Sender 实现

space structure, HangX-Ma

需要实现以下 5 个接口并增添自己所需的变量以及 helper functions。上图是 Sender 端所看到的内存结构以及 seqno 的分布。

push: 不断读取新的字节，并组装生成 TCPSenderMessage。需要使满足 window 尺寸的 TCPSenderMessage 尽可能大，但上限是 TCPConfig::MAX PAYLOAD SIZE (1452 bytes)。 TCPSenderMessage::sequence length() 会用以计量该 segment 占用的 seqno 的尺寸， SYN 和 FIN 都需要计算在内。
```
 /* Push bytes from the outbound stream */
 void push(Reader &outbound_stream);
```
这里也是需要注意 window size 最小应当为 1。另外我们需要两个布尔变量来记录是否需要给传输的 TCPSenderMessage 增加 SYN 标志或者 FIN 标志。我们以如下顺序对 msg 进行组装： SYN， payload， FIN。需要注意的是， FIN 标志设定有一定的条件限制：
- FIN 之前没设定过；
- Reader 已经没有数据了；
- 塞完 SYN 和 payload 之后我们的 window size 还能容纳一个 FIN 的位置如果本次 FIN 没有传输，就下次传输，不会有什么影响。
另外，只有在 outstanding segments 清空后我们才需要在传输新的 TCPSenderMessage 时重置 timer，否则 timer 将在很大程度上失去其基本作用。每次传输都需要更新 outstanding segments 集合以及发送的 seqno 数量， next_seqno 等信息。

cs144 指导书特地说明了 window size 为零的情况，仅适用于 push() 函数。这时 TCPSender 仍需要发送一个独立的字节，虽然会被 TCPReceiver 拒绝接收但 TCPReceiver 会返回一个 TCPReceiverMessage 数据，这个信息可以告知 TCPSender window 中是否有新用于传输的空间。否则 TCPSender 将无法确定何时发送新的 segment。

maybe_send: 必要时发送 TCPSenderMessage 或者为空。
```
 std::optional<TCPSenderMessage> maybe_send();
```
我们需要额外创建一个队列变量 segments_out_ 来管理需要发送的 segments，使用队列可以保证传输的先后顺序。仅在这个队列的元素数量不为零且收到 SYN 信号才返回队列头部的那个数据，并将其从队列头部移除。
receive: 接收的 window 范围是 \([ackno, ackno + window size]\)。 TCPSender 需要遍历 outstanding segments 集合将其中已经被 ACK 的部分移除（ackno 比 segments 中所有的 seqno 都要大的那些 segments）。
```
 /* Receive an act on a TCPReceiverMessage from the peer's receiver */
 void receive(const TCPReceiverMessage &msg);
```
我们只需要按照 2.TCPSender 如何监测丢包中的最后一条逻辑写代码就行。

这里需要注意，接收的 TCPReceiveMessage 中的 ackno 可能为空，这时候不能直接返回，有可能是我们传输了一个 empty message 去获取 window size 而返回的一个包。因此，我们需要更新 window_size_ 变量，除此之外就什么都不做了。

或者收到的这个 ackno 比我们当前保存的 next_seqno 都要大，这可能是一个错误信息需要丢弃这段数据。
tick: 计时单位，得到与上次该函数被调用的时间间隔。
```
 /* 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);
```
除了要创建一个 timer_ 变量存储时间外，在 tick 中还需要做 2.TCPSender 如何监测丢包中的几件事：
1. 若 outstanding segments 存在且 timer 失效，重传时间最早的那个 segments。
2. window size 非零时累加连续重传数量，并进行 “exponential backoff”。
3. 重置 timer 的值为 0，为下一次重传准备。
send_empty_message: 长度为零并且 seqno 正确的 TCPSenderMessage，在 TCPReceiver 希望通过 TCPReceiverMessage 获取一些特定信息的时候特别有用，这个和 push 中的那个想法很类似。
```
 /* Generate an empty TCPSenderMessage */
 TCPSenderMessage send_empty_message() const;
```
这种长度为 0 的 segments 不需要被监测并纳入 outstanding segments 用以重传。我们只需要返回一个仅有 ackno 被赋值为下一个需要接收的字节的 seqno 的 TCPSenderMessage。

FAQs and special cases 中的信息都很有帮助，可以当作一种提供解题思路的 Hints。

Helper Functions

简化 seqno 与 abs_seqno 转换，使用如下两个 helper functions 即可满足需求。之后在给 TCPSenderMessage 中的 ackno 赋值就很方便了。

uint64_t get_next_abs_seqno_() const { return next_abs_seqno_; };
Wrap32 get_next_seqno() const { return isn_ + next_abs_seqno_; };

4. 坑点记录

4.1 The test “Retx SYN twice at the right times, then ack” failed.

这个问题是初始化 window size 不正确导致的，在文档里的 FAQs 部分有这么一段：

Q: What should my TCPSender assume as the receiver’s window size before I’ve gotten an ACK from the receiver?
A: One.

当时我将 window_size_ 初始化为 0，结果在调用 tick 函数后 window_size_ > 0 这条条件判断语句永远不满足， RTO_timeout_ 永远无法进行翻倍。正确的做法是将 window size 初始化为 1。

4.2 The test “Retx SYN until too many retransmissions” failed.

RTO_timeout 翻倍，但我以为是初始值翻倍就直接设定成了 RTO_timeout = 2 * initial_RTO_ms_，实际上指导书就是说 Double the value of RTO 并且说明是 exponential backoff （给的提示很明显）。

5. 测试结果

...
      Start 28: send_connect
27/36 Test #28: send_connect .....................   Passed    0.09 sec
      Start 29: send_transmit
28/36 Test #29: send_transmit ....................   Passed    1.11 sec
      Start 30: send_retx
29/36 Test #30: send_retx ........................   Passed    0.08 sec
      Start 31: send_window
30/36 Test #31: send_window ......................   Passed    0.35 sec
      Start 32: send_ack
31/36 Test #32: send_ack .........................   Passed    0.08 sec
      Start 33: send_close
32/36 Test #33: send_close .......................   Passed    0.09 sec
      Start 34: send_extra
33/36 Test #34: send_extra .......................   Passed    0.16 sec
      Start 36: compile with optimization
34/36 Test #36: compile with optimization ........   Passed   18.01 sec
      Start 37: byte_stream_speed_test
             ByteStream throughput: 1.02 Gbit/s
35/36 Test #37: byte_stream_speed_test ...........   Passed    0.45 sec
      Start 38: reassembler_speed_test
             Reassembler throughput: 1.83 Gbit/s
36/36 Test #38: reassembler_speed_test ...........   Passed    0.85 sec

100% tests passed, 0 tests failed out of 36

Total Test time (real) = 170.63 sec
Built target check3

PREVIOUScs144-sp23, Lab Checkpoint 2: the TCP receiver

NEXTcs144-sp23, Lab Checkpoint 4: down the stack (the network interface)