介绍

CS 144: Introduction to Computer Networking, 2023 Spring. 是一门讲 TCP/IP 入门的课程，用 C++ 完成 TCP 栈的各个组件，最后组装起来在真实环境测试。

11 月底愉快地完成了 CS 106L 后开始做 CS 144，耗时大约 3 周，其实和想象中的耗时差不多。 据 wakatime 统计的 codetime 是 65 h，加上阅读 handouts / labs 的时间应该有 100 h +。

如果 CS 106L 可以给满分 10 分的话，那么 CS 144 只能给到 8 分，理由有：

1. 新版 minnow 相对于 2020 libsponge 原版删了 TCPConnection，课程难度直接下降一个星级。TCP benchmark 也全没了。
2. 有几个 lab 没有发挥的空间，也有很多细节没讲到，甚至被删掉，下面会具体讲讲。
3. 课程老师有点大病，12 月 16 号左右把仓库 made private 同时关闭了 https://cs144.github.io 课程主页。之前听说他不允许公布个人解法我还能理解，made private 简直莫名其妙。

Labs

Lab 0 ByteStream

实现一个简单的 byte 流，主要实现 Writer::push( string data ) 和 Reader::pop( uint64_t len ) 方法。

这里的 Reader 和 Go 的 read(T& obj, size_t len) 接口不太一样，是根据 peek() 返回的字符串数量来 pop，所以设计的时候 peek 为了效率必须返回 string_view，这里也是一个设计限制了。

因为刚接触 C++ 不多，所以我尝试写了各种实现，他们的速度对比如下：

1. string impl: ByteStream throughput: 3.95 Gbit/s
2. vector<char> impl: ByteStream throughput: 3.90 Gbit/s
3. queue<char> impl: ByteStream throughput: 0.67 Gbit/s
4. char* impl: ByteStream throughput: 3.00 Gbit/s
5. queue<string> impl: ByteStream throughput: 30.00 Gbit/s

上面的排序也是我的实现顺序。

queue<char> 慢的原因是不支持迭代，每次 peek 只能得到一个 char。 我这里写的 char* 实现略显巧妙，思路是初始化 3 * capacity 的大小，然后用几个变量操作滑动窗口。 写 char* 实现时 sanitizer 一直报内存泄漏，花了好多时间解决。以后再也不想要手操指针了 qwq。

一开始思维定势在了 char 数组类结构，最优也就 4 Gbit/s，后来查了查才得到一些启发用 string 数组类结构。 更新思路后速度一下子提到了 10+ Gbit/s。

然后在正确思路上进行优化，以下是我的几点优化方法：

1. queue.pop() 相比 vector.erase(vector.begin()) 可以提升 2 Gbit/s
2. 用 string + move 可以提升 3 Gbit/s
3. 用 front_view 相比 string.erase 可以提升 6 Gbit/s

最终可以达到 32 Gbit/s。

Lab 1 Reassembler

被 overlapping 概念坑了，codetime 6 h 才完成。

实现一个 随机 流重组器。

TCP 流一般是提前分割好然后发送的，也就是说 substring index 是不会重叠的。 但是重组器实现为了 robustness 会实现为重组任何子字符串，也就是强调 随机 这一概念。 这里 lab 也没讲清楚，搞得我以为 overlapping 是指某个包重发导致的。

做了很多 test fit 后我才发现我混淆了概念，然后真正的 solution 两个钟就写好了…而且 10 Gbit/s +。

具体实现就不细讲了，就一个简单的算法。

Lab 2 Receiver

第一部分是 ISN wrapper 挺简单的。

第二部分是 Receiver 也挺简单的。

Lab 3 Sender

算是最难的一部分，讲义里面很多细节没讲到，codetime 13 h 才做完。

建议参照 2020 的讲义来做，里面提到了 test workflow 之类的东西，对 分析 Sender 的工作流程 很重要。

有以下几个概念是讲义里面没具体讲的：

1. 没讲清为什么要在 window size != 0 时增加累计重发次数并 back off RTO
2. 原文说在 push 的时候对 window size 0 特殊处理，也没讲清楚，和上一条是关联的
3. window size 的概念，没讲为什么每次 receive 就需要执行无条件更新

我先对上面这些概念进行解释：

1. 当且仅当网络繁忙时才进行 RTO back off，而 window size = 0 时代表 receiver 忙于处理数据
2. 当且仅当发送队列没有任何 byte 并且 window size = 0 时才需要假装 window size = 1，旨在发送一条 不为空 的消息促使 receiver 回复 ack
3. 无条件更新 window size 是一个提前设计好的行为，因为课程作者认为 window size 表明的就是 Sender 的发送队列容量，不给你有别的想法

这个 lab 还有一些过度设计的行为和 test case，下面也讲讲。

window size 那里我认为 ackno + window size - pushed byte count 可以得到精确值。 我第一次做的时候是这么写的，但是卡在了 send_extra 一些莫名其妙的测试上。 继续写的话应该可以过测试，但是代码太丑了就重写了。

还有就是 tick 那里旨在计时第一个发出的包然后重发。 其实只要在 tick 时判断一下有没有 outstanding segment 再增加计时，收到 ack new receipt of data 再重置， 就可以保证计时是精确的。 事实上我就是这么实现的可以通过 tick 所有测试。

总而言之，Sender 这块的讲义里面没讲明白原理和细节，只讲流程，莫名其妙，根本没有发挥空间。

Lab 4 Network Interface

实现 ARP 请求和回复、IPv4 包封装和帧交换，简单。

ARP 的设计那里，我对课程作者的要求写法存疑，代码测试要求每次 ARP Request/Response 都带上自己的 Hardware address / ip address 其实可以没必要。

有一点坑的是 2023 的讲义里删了很多东西，我是配合 2020 的讲义看的。

Lab 5 Router

实现 Route table 和最长前缀匹配，不涉及路由算法 bellman-ford、BGP、OSPF 之类的，简单。

课程里没讲要更新 checksum，简直狗屎，就看着它莫名其妙的错误信息发呆。后来我看其他人代码才知道。

Lab 6 All together

用课程给的 endtoend 程序启动 server 和 client。

原理大概类似于 frp 吧，tun 我也不懂。网络栈还是博大精深的，课程的 TCP 只是其中一点点。

末尾

总体上来说，如果能走在正确的路径上，那么课程是比较轻松的，也具有很大的教学意义。 并没有特别批判的意思，课程就如开头所说 8 / 10 分。

https://github.com/iyume/Stanford-CS144（直接 public，无所谓了）