Stanford CS144 Lab Assignment 学习笔记

文章最后更新时间为：2021 年 09 月 01 日 21:20:11

由于暑假没啥事干(其实还要打 gal)，并下个学期马上就要学计算机网络了，所以提前学习一下 Stanford 的 CS144

一些准备工作

课程选用的是 CS144 Fall2019，一开始是打算用 Fall 2020，但是发现 20 的课程里视频比较多（要登录 Stanford 才能观看），并且19的课程网上教程多一些，所以最终还是选择了19的课程。快逃！好吧，根据我一段时间的学习，发现在 Fall2020 里完善了一些内容，所以改为使用 Fall2020 了，下面是一些链接：

1. CS144公开视频课
2. CS144 Fall2020 Course Page
3. CS144 Fall2020 Sponge 备份
4. huangrt01's CS144 学习笔记
5. 康宇PL's Stanford CS144 Lab Assignment 学习笔记
6. ViXbob's libsponge

说在前面

以下所有代码/言论均有时效性，即我写文章时的代码和我写文章时的心态，如果对最新版本有兴趣可以去 GitHub 上看。

Lab0

1 配置GNU/Linux环境

ViXbob 在 MacOS 上使用 Parallels Desktop 配置虚拟机，然后 ssh 回去敲一些命令，因为用 iTerm 复制粘贴啥的一些快捷键会更舒服一点。再用 VSCode 的 remote 模式来编辑代码。感觉很爽！可惜的是 Parallels Desktop 不能把虚拟机弄成服务器的形式挂在后台。

2 Networking by hand

2.1 Fetch a Web page

telnet cs144.keithw.org http

用 telnet 链接 cs144.keithw.org 协议是 http ，这里我理解是 http 一般默认的端口号是 80 ，所以这个命令相当于

telnet cs144.keithw.org 80

PS：操作下来感觉没区别，具体代考证

GET /hello HTTP/1.1

Host: cs144.keithw.org

在命令行里输入这两行，相当于浏览器访问时的 header，然后在输入回车告知服务器输入完毕，接着就会收到服务器的 response：

HTTP/1.1 200 OK
Date: Sun, 15 Aug 2021 04:37:58 GMT
Server: Apache
Last-Modified: Thu, 13 Dec 2018 15:45:29 GMT
ETag: "e-57ce93446cb64"
Accept-Ranges: bytes
Content-Length: 14
Content-Type: text/plain

Hello, CS144!

Assignment 只需要把 \hello 换成 \lab0\sunetid 即可，response 为：

HTTP/1.1 200 OK
Date: Sun, 15 Aug 2021 05:11:29 GMT
Server: Apache
X-You-Said-Your-SunetID-Was: vixbob
X-Your-Code-Is: 670279
Content-length: 110
Vary: Accept-Encoding
Content-Type: text/plain

Hello! You told us that your SUNet ID was "vixbob". Please see the HTTP headers (above) for your secret code.

2.3 Listening and connecting

netcat -v -l -p 9090 用 netcat 监听 9090 端口，然后在局域网中用 telnet 再和 127.0.0.1:9090 建立连接后就可以通信了。

3 Writing a network program using an OS stream socket

Stream Socket : A bidirectional in-order byte stream between two programs, one running on your computer, and the other on a different computer across the Internet.

3.1 Let's get started --- fetching and building the starter code

注意记得把 g++ 和 gcc 的版本更新到 8.0 以上，并且把 g++-xxx 链接到 g++ 上（gcc 同理）。

3.3 Reading the Sponge documentation

读文档对我这种没有什么基础的人来说还挺费劲的，不过也学到一些：

FileDescriptor: 在 Unix 内核的系统中，程序每打开或者创建一个文件，内核就会向进程返回一个文件描述符（通常为正整数）用来索引、指向这个文件。FileDescriptor 则封装了文件的读写等操作。

Socket: 我粗浅的认为套接字就是两个程序通信的管道，一个程序写，另一个程序就可读。当然，两个程序可以在本地（LOCAL），也可以在不同的地方（即通过网络通信）。而 Socket 则封装了若干函数，这个地方要注意一下 shutdown 函数：

1. shutdown(SHUT_RD) 关闭当前 Socket 的读入，但是还是可以向 connect 的另一端写入数据。
2. shutdown(SHUT_WR) 关闭当前 Socket 的写入，但是还是可以读入 connect 的另一端写入的数据。
3. shutdown(SHUT_RDWR) 关闭读写。

TCPSocket: 两个程序建立的通信的链接的协议为 TCP 协议，即 Socket(AF_INET, SOCK_STREAM)，AF_INET 表示网络连接（IP 协议），SOCK_STREAM 表示稳定的数据传输。（SOCK_STREAM provides sequenced, reliable, two-way, connection-based byte streams. An out-of-band data transmission mechanism may be supported）

3.4 Writing webget

利用 TCPSocket 与 Host 建立连接，然后发送请求头即可。

void get_URL(const string &host, const string &path) {
    TCPSocket socket1;
    socket1.connect(Address(host, "http"));
    socket1.write("GET " + path + " HTTP/1.1\r\nHost: " + host + "\r\n\r\n\r\n");
    socket1.shutdown(SHUT_WR);
    while(!socket1.eof())
        std::cout << socket1.read();
    socket1.close();
}

注意：认真读 lab0 的文档，请求头里的每一行的换行必须是 \r\n 不能是 \n，发完请求后需要 shutdown(SHUT_WR) 不然服务端等待你后续的请求。然后就是必须读到 eof 后才结束，不然可能会读入的不完整。（例子暂时还没想到）

4 An in-memory reliable byte stream

利用内存做数据缓冲区，并维护数据流。方案：

1. 利用 std::deque<char> 来维护缓冲区。
2. 利用 std::string 和双指针来维护缓冲区。

这两个方案我都实现了，在我这是 std::string 更快，代码如下：

1. byte_stream.hh
2. byte_stream.cc

DUMMY_CODE 是为了让编译时不报有变量没有用的 Warning ，EOF 的判断要写入端和读入端，两端均结束才算达到 EOF。

Update: 2021.08.24

上面的测试出了点问题，我测试的时候没有用的是 Debug 模式，实际上应该开 Release 模式。并且用 std::string 也不符合有内存限制的初衷，下面是 std::deque 的代码实现：

1. byte_stream.hh
2. byte_stream.cc

测试结果：

Lab1

3 Putting substrings in sequence

要求实现一个 stream reassembler 将无序 byte stream 的碎片重新排序组合成正确的 byte stream 并写入 ByteStream 对象 _output 中。

注意：

1.每个碎片由开头位置，长度，字符串内容组成。

2.碎片会重叠，但是不会有冲突。

3.一个字节没有被写入 _output 当且仅当它前面的那个字符没有被写入 _output。换而言之如果一个标号为 index 的字节存在，并且 [0, index - 1] 的字符存在那么它就必须被写入 _output 中。（0 号字符一存在就要被写入 _output 中）

4.会存在字符串内容为空的带有 EOF 标志的碎片。

我对于 stream reassembler 的理解一开始有很大的偏差，我认为 _ouput 可以存储 capacity 个字节，并且 stream reassembler 本身也可以存储 capacity 个字节，但这样的理解是有问题的。实际上我们可以将整个 stream reassembler 看成一个可以无序写入的 byte stream （用 c++ 的理解就是继承），那么一切就说得通了，其实也就是说这个 byte stream 中的内存内被重新利用当且它被 read 段读取了，这里有一张图也许可以帮大家更好的理解：

关于实现：

1.可以用 set 去维护未被占用的连续内存（若干个不相交的线段）。

2.然后用 map + list 维护对于每个开头最长的连续线段（Segment），然后贪心地从 0 开始往后覆盖即可。

代码如下：

1. stream_reassembler.hh
2. stream_reassembler.cc

测试结果：

Lab2

3.1 Translating between 64-bit indexes and 32-bit seqnos

SYN 表示字符串的起始，FIN 则表示结束。

Absolute Sequence Numbers：为正常字符串下标，即从 $0$ 开始依次加一。(SYN 和 FIN 都要占据一个位置，SYN 在 $0$，FIN 在最后一个字符后面一个)

Sequence Numbers：用 ISN 表示 SYN 的位置（在实际应用中 ISN 为一个32位的随机正整数），而对于某个字符串的字符，如果它的 Absolute Sequence Number 为 $x$，那么它的 Sequence Number 为 $(\text{ISN} + x)\mod {2^{32}}$。

Stream Indices：则是 Absolute Sequence Numbers 去掉 SYN 和 FIN。

下面是一个 cat 这个字符串的栗子（ISN 为 $2^{32}-2$）：

然后我们要是实现的为，将一个 Sequence Number 转为 Absolute Sequence Number。当然，直接转换是做不到的，对于 $x$ 来说，$x + a\times 2^{32}$ 在模意义下是相同的，所以我们要有一个基准值，我们要求离基准值最近的 $x+a\times 2^{32}$。那么只需要比较 $x+2^{32}, x-2^{32},x$ 谁离基准值在模意义下的值最近即可。关于实现其实比较 tricky（用了一点 unsigned int 的性质），可以看一下具体代码：

1. wrapping_integers.hh
2. wrapping_integers.cc

所以说为什么要 wrap integers 呢？

3.2 Implementing the TCP receiver

注意：

1. 按照 tests 来看，如果没有出现 SYN，那么在 SYN 出现之前的 stream segments 忽略。太贴心了
2. 计算 acknowledgment number 时要考虑 SYN 和 FIN。

代码如下：

1. tcp_receiver.hh
2. tcp_receiver.cc

测试：

Lab3

Lab3 Assigment 里描述的实现方法有部分不是线性的，可能需要将几部分拼起来才是一个完整的功能描述。并且里面大部分描述的小细节都很重要，看漏了可能会很难受。

3.1 How does the TCPSender know if a segment was lost?

1. TCPSender 内部不涉及任何时间函数的调用，仅当 tick 被调用时会有时间流逝。
2. retransmission timer 有三种状态：停止运行、运行但时间没有完全流逝、运行并且时间流逝。timer 的初始状态是停止运行的。每当 outstanding segments 都消失时，timer 要被停止。每当有 segment 被发送时，要将停止的 timer 重新运行。

3.2 Implementing the TCP sender

tick 流程：

• 使 timer 流逝一段时间。

• 如果存在 outstanding segment 并且 timer 正在运行并且时间完全流逝

  • 重新发送最靠前的 outstanding segment
  • 如果 window size > 0，那么 consecutive_retransmissions 加一，并且 RTO 加倍
  • 将 timer 的时间设置为加倍后的 RTO

fill_window 要注意的细节：

• MAX_PAYLOAD_SIZE 只限制字符串长度并不包括 SYN 和 FIN，但是 window_size 包括 SYN 和 FIN
• 发出的 segment 要在满足 ackno 和 window_size 的要求
• 新的 segment 只会在 fill_window 中生成！

ack_received 流程：

• 如果新的 ackno 大于旧的 ackno （大小在 absolute sequence number 下比较）

  • 重置 RTO 和 consecutive_retransmissions

  • 更新 outstanding segments 集合

    • 如果更新完后不存在 outstanding segment 那么停止 timer
    • 否则用重置后的 RTO 重置 timer
  • 更新 ackno 和 window_size
• 执行 fill_window

代码如下：

1. tcp_sender.hh
2. tcp_sender.cc

测试结果：

vixbob@ubuntu:~/sponge/build$ sudo make check_lab3
[100%] Testing the TCP sender...
Test project /home/vixbob/sponge/build
      Start  1: t_wrapping_ints_cmp
 1/33 Test  #1: t_wrapping_ints_cmp ..............   Passed    0.00 sec
      Start  2: t_wrapping_ints_unwrap
 2/33 Test  #2: t_wrapping_ints_unwrap ...........   Passed    0.00 sec
      Start  3: t_wrapping_ints_wrap
 3/33 Test  #3: t_wrapping_ints_wrap .............   Passed    0.00 sec
      Start  4: t_wrapping_ints_roundtrip
 4/33 Test  #4: t_wrapping_ints_roundtrip ........   Passed    0.13 sec
      Start  5: t_recv_connect
 5/33 Test  #5: t_recv_connect ...................   Passed    0.00 sec
      Start  6: t_recv_transmit
 6/33 Test  #6: t_recv_transmit ..................   Passed    0.04 sec
      Start  7: t_recv_window
 7/33 Test  #7: t_recv_window ....................   Passed    0.00 sec
      Start  8: t_recv_reorder
 8/33 Test  #8: t_recv_reorder ...................   Passed    0.00 sec
      Start  9: t_recv_close
 9/33 Test  #9: t_recv_close .....................   Passed    0.00 sec
      Start 10: t_recv_special
10/33 Test #10: t_recv_special ...................   Passed    0.00 sec
      Start 11: t_send_connect
11/33 Test #11: t_send_connect ...................   Passed    0.00 sec
      Start 12: t_send_transmit
12/33 Test #12: t_send_transmit ..................   Passed    0.03 sec
      Start 13: t_send_retx
13/33 Test #13: t_send_retx ......................   Passed    0.00 sec
      Start 14: t_send_window
14/33 Test #14: t_send_window ....................   Passed    0.01 sec
      Start 15: t_send_ack
15/33 Test #15: t_send_ack .......................   Passed    0.00 sec
      Start 16: t_send_close
16/33 Test #16: t_send_close .....................   Passed    0.00 sec
      Start 17: t_send_extra
17/33 Test #17: t_send_extra .....................   Passed    0.00 sec
      Start 18: t_strm_reassem_single
18/33 Test #18: t_strm_reassem_single ............   Passed    0.00 sec
      Start 19: t_strm_reassem_seq
19/33 Test #19: t_strm_reassem_seq ...............   Passed    0.00 sec
      Start 20: t_strm_reassem_dup
20/33 Test #20: t_strm_reassem_dup ...............   Passed    0.00 sec
      Start 21: t_strm_reassem_holes
21/33 Test #21: t_strm_reassem_holes .............   Passed    0.00 sec
      Start 22: t_strm_reassem_many
22/33 Test #22: t_strm_reassem_many ..............   Passed    0.04 sec
      Start 23: t_strm_reassem_overlapping
23/33 Test #23: t_strm_reassem_overlapping .......   Passed    0.00 sec
      Start 24: t_strm_reassem_win
24/33 Test #24: t_strm_reassem_win ...............   Passed    0.04 sec
      Start 25: t_strm_reassem_cap
25/33 Test #25: t_strm_reassem_cap ...............   Passed    0.07 sec
      Start 26: t_byte_stream_construction
26/33 Test #26: t_byte_stream_construction .......   Passed    0.00 sec
      Start 27: t_byte_stream_one_write
27/33 Test #27: t_byte_stream_one_write ..........   Passed    0.00 sec
      Start 28: t_byte_stream_two_writes
28/33 Test #28: t_byte_stream_two_writes .........   Passed    0.00 sec
      Start 29: t_byte_stream_capacity
29/33 Test #29: t_byte_stream_capacity ...........   Passed    0.33 sec
      Start 30: t_byte_stream_many_writes
30/33 Test #30: t_byte_stream_many_writes ........   Passed    0.00 sec
      Start 53: t_address_dt
31/33 Test #53: t_address_dt .....................   Passed    0.01 sec
      Start 54: t_parser_dt
32/33 Test #54: t_parser_dt ......................   Passed    0.00 sec
      Start 55: t_socket_dt
33/33 Test #55: t_socket_dt ......................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 33

Total Test time (real) =   0.76 sec
[100%] Built target check_lab3
vixbob@ubuntu:~/sponge/build$

做完了 Lab3 后，去看了看 huangrt01 的 commit 记录才稍微明白了一点为什么 Standford 助教说一个 git 仓库是你完成这个 Lab 的最好证明。在我现有的认知里，我只是单纯的把 github 当成一个代码仓库，而实际上它是记录你完成整个工程最好的工具，每个单元测试的通过，代码细微的变化全部都记录下来了，这种感觉很奇妙！以后可以好好利用起来！

而且 sponge 库里的一些实现以及对 modern c++ 的运用也比较有趣，后面有时间可能也会研究研究~

Lab4

写在前面

只能说被 Lab4 折磨了，真是一段非常狗血的经历。最初我选择了 Fall2019 的课程，却因 Lab1 中对 reassembler 的解释不够清楚（在 Fall2020 添加了一张很清楚的图）转到了 Fall2020 的课程；但是在后面的 Lab 里 Fall2020 删掉了几个很关键的内容导致难度直线上升，因为如果不说清楚的话，你只能自己 Debug 找问题，并且关键在于这些问题并不会在单元测试中暴露，而是会在与系统真实通信中大面积爆发（而这种测试点说实话不是很好调试，而且我至今还没太弄懂 txrx.sh 的机制）。然后我按照 Fall2019 Lab 的描述重构了一部分代码之后迅速就过掉了.... 我TM直接蚌埠住了

后来又按照 TCPFSM 的状态转移图以及 TA 写的 tcp_state 重构了 tcp_connection.*, tcp_sender.*, tcp_receiver.* ，感觉也算是把思路理的比较清晰了。

最后魔改了一下 BufferList 来实现 byte_stream ，tcp_benchmark 表现大幅度提升。并且原生的 tcp_benchmark 好像测试的不太全面，里面在 inbound 端的读入都是整个 Buffer 一并读入并且 BufferSize 也比较小（64KB），这就导致了一些本来不太对的写法速度奇快..... 有点离谱，虽然我目前还不是非常了解在真实通信中到底 Buffer 的大小，一次读入的大小一般是多少，一次写入的大小是多少，所以似乎也不能一棒子打死那些在极端情况下不太行的实现方法，但是我不敢苟同。

The TCP connection & wire up all the parts

主要的问题在于 segment_received 函数和 clean shutdown 的判断，先给出下面三张图：

State of TCPReceiver：

State of TCPSender：

State of TCPConnection(TCP FSM)：

然后这里给出 FSM 状态和 sender，receiver 之间的对应（均可以在 tcp_state.cc 中查到）：

FSM_LISTEN = SENDER_CLOSED && RECEIVER_LISTEN

FSM_SYN_SENT = SENDER_SYN_SENT && RECEIVER_LISTEN

FSM_TIME_WAIT = SENDER_FIN_ACKED && RECEIVER_FIN_RECV

segment_received 函数：

• 如果 FSM 处于LISTEN 状态时，只接收带有 SYN 的报文段，并且如果收到 SYN 要更新 receiver 和发送 ack segment，即 _receiver.segment_received + _sender.fill_window
• 如果收到 RST，直接 unclean shutdown

• 此外

  • 更新 receiver 状态（_receiver.segment_received）
  • 如果数据带有 ack 则要更新 sender 状态（_sender.ack_received）
  • 如果上述两个操作完了均没有发送任何报文段，并且更新状态时出现错误，我们需要发送带有 ack 的空报文段，并且 seqno 要设置正确
  • 并且主要到这里有个小细节，如果 FSM 处于 SYN_SENT 状态，那么只允许接受带有正确 ack 的报文段

clean shutdown 的判断：

其实这个也没啥好说的，因为 LAB 文档里已经写得很清楚了x

• 如果 inbound stream 不处于 EOF 状态并且 receiver 处于 FIN_RECV，将 _linger_after_streams_finish 设为 false （说明 FSM 处于 TIME_WAIT 后，我们不需要等待）

• 如果 FSM 处于 TIME_WAIT

  • 如果 _linger_after_streams_finish 为 false ，那么我们我们这一端的 TCP 连接可以 clean shutdown
  • 或者距离上一次收到报文段的时间不小于 $10$ 倍的 _cfg.rt_timeout 那么我们也可以 clean shutdown

代码：

1. tcp_receiver.hh
2. tcp_receiver.cc
3. tcp_sender.hh
4. tcp_sender.cc
5. tcp_connection.hh
6. tcp_connection.cc

测试结果：

tcp_benchmark：

性能优化

首先我们用 gprof 分析一下 tcp_benchmark，先将 ../etc/cflags.cmake 中的 -g 改为 -Og -pg，然后执行以下命令：

sudo cmake .. -DCMAKE_BUILD_TYPE=Release
sudo make -j8
./apps/tcp_benchmark
gprog ./apps/tcp_benchmark > prof
vim prof

对于我的程序来说单看用时看不出来什么，因为是系统函数的调用：

我们要看一下函数调用关系图，然后锁定了两个函数：

可以初步判断是我们的 byte_stream 实现的不太优秀，但说实话也不能具体地分析为啥 std::deque<char> 就不优秀，可能还是和 deque 的底层实现有关吧，通过观察 deque 的 insert，erase 的复杂度，可以粗浅地猜测底层应该是一个类似于链表的东西，所以一个链表的节点只存一个 char 就有点不太聪明的亚子。然后参考了网友的一些做法后，我魔改了一下 BufferList （注意使用 move 去避免 string 的复制，并且 buffer 的 remove_prefix 复杂度是 $O(1)$，因为它的实现其实就是一个指针的移动）。代码如下：

1. byte_stream.hh
2. byte_stream.cc

魔改后的性能：

就在我的这个测评环境下提升了大概 $35\%$ 吧。

吐槽时间

为啥 stream_reassembler 要按有交区间来实现啊，明明在真实通信中都是不交的线段....

为啥要有 Sequnce Number 这种封装啊，只是单纯的让 header 更小一点？

建议 CS144 Fall 2021 合并一下 Fall 2019 和 Fall 2020 （（（

中途有一次用想用 string_view 来实现 byte_stream 结果萎了，出现了奇奇怪怪的内存泄露问题，到现在还不知道为啥...

要好好学 modern c++！