「一个人的桃花源」

文章最后更新时间为: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 9090netcat 监听 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 是为了让编译时不报有变量没有用的 WarningEOF 的判断要写入端和读入端,两端均结束才算达到 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$ 开始依次加一。(SYNFIN 都要占据一个位置,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 去掉 SYNFIN

下面是一个 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 时要考虑 SYNFIN

代码如下:

  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 只限制字符串长度并不包括 SYNFIN,但是 window_size 包括 SYNFIN
  • 发出的 segment 要在满足 acknowindow_size 的要求
  • 新的 segment 只会在 fill_window 中生成!

ack_received 流程:

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

    • 重置 RTOconsecutive_retransmissions
    • 更新 outstanding segments 集合

      • 如果更新完后不存在 outstanding segment 那么停止 timer
      • 否则用重置后的 RTO 重置 timer
    • 更新 acknowindow_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 后,去看了看 huangrt01commit 记录才稍微明白了一点为什么 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_streamtcp_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 状态和 senderreceiver 之间的对应(均可以在 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_finishfalse ,那么我们我们这一端的 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 的底层实现有关吧,通过观察 dequeinserterase 的复杂度,可以粗浅地猜测底层应该是一个类似于链表的东西,所以一个链表的节点只存一个 char 就有点不太聪明的亚子。然后参考了网友的一些做法后,我魔改了一下 BufferList (注意使用 move 去避免 string 的复制,并且 bufferremove_prefix 复杂度是 $O(1)$,因为它的实现其实就是一个指针的移动)。代码如下:

  1. byte_stream.hh
  2. byte_stream.cc

魔改后的性能:

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

吐槽时间

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

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

建议 CS144 Fall 2021 合并一下 Fall 2019Fall 2020 (((

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

要好好学 modern c++

标签: Standford, CS144, 计算机网络, Lab Assignment, TCP/IP

已有 12 条评论

  1. 蹲一下,听说是门好课,手写tcp的lab远近闻名><

    1. 顺带一提友链的第二条失效了23333

  2. dayu
    1. 嗯哼?
      之前确实有用GitHub Action测试的想法,但是没有去学x

      1. dayu
        1. 恩恩,确实是这样。而且我这份代码在我实体机 Ubuntu 20.04 上也跑不过,并且似乎我在网上找的好几份代码也都是同样的测试点过不了(也包括你的x),目前还不知道是啥原因,等中秋我在调试一下。

  3. mucz

    感谢!deque<Buffer>比Bufferlist要快很多!

  4. Aubbish

    Mark了,课和您的笔记都很好,这手modern C++用的可以

  5. rmJay

    大佬,请问Lab 0的make check_webget你执行成功了吗?我不但执行失败了,连make check_lab0都失败了

  6. [...]ViXbob的博客[...]

  7. [...]ViXbob的博客[...]

  8. [...]ViXbob 的博客[...]

添加新评论

Hitokoto

分类

归档

友情链接

其它