CS144

• 2019 Fall：https://kangyupl.gitee.io/cs144.github.io/
• 2020 Fall：https://github.com/lawliet9712/Stanford-CS144-2021
• 【推荐】2021 Fall：https://github.com/Kiprey/sponge

前前后后弄了半个月，终于啃完 CS144 了，感谢 K大博客，大概弄懂了 80% 吧

我的笔记: https://blog.csdn.net/Miracle_ps/article/details/131364792

Linux 环境

• Mac VirtualBox 安装 Ubuntu desktop 版：https://www.zhihu.com/tardis/zm/art/109808506
• 安装 ubuntu server 版：https://blog.csdn.net/weixin_46658699/article/details/114693006
• VirtualBox 增强工具（方便双向复制）：https://blog.csdn.net/zhu_1997/article/details/117814728
• SSH 连接 VirtualBox Ubuntu 虚拟机：https://www.cnblogs.com/linxiaoxu/p/16260601.html
• Ubuntu18.04 升级 gcc：https://blog.csdn.net/weixin_44128857/article/details/108554751
• Sponge 仓库 2021：https://gitee.com/ericps/cs144-2021

Lab0: ByteStream

• webget: 利用已有 API 获取网页
• byte_stream: 实现一个有序字节流类（in-order byte stream），使之支持读写、容量控制。可以使用 std::dueue （双端开口）作为「可靠」字节流的底层。这个字节流类似于一个带容量的队列，从一头读，从另一头写。当流中的数据达到容量上限时，便无法再写入新的数据。特别的，写操作被分为了peek和pop两步。peek为从头部开始读取指定数量的字节，pop为弹出指定数量的字节。
• string_view: https://blog.csdn.net/danshiming/article/details/122573151

Lab1: StreamReassembler

• git 拉取远程所有分支到本地：for i in git branch -r; do git checkout basename $i && git pull --all; done
• git 合并分支：参考
• 内含 ByteStream 没有默认的构造函数为啥可以直接定义，这里面没有设置 ByteStream 的 capacity？
• 不可靠的流失传输中每条数据可能 reorder、duplicate 等等，TCP 的功能就是使用不可靠的数据包提供可靠的字节流服务，因此需要实现「流重组器」来应对收到的乱序或者重复数据的情况，每条流带有一个 stream_index（类型是uint64_t，理解为不会 wrap），按照顺序重组字节流并送入指定的 ByteStream 中
• 实现使用 std::map<size_t, std::string> 存放那些还未重组的数据，维护下图中的 first_unassembled 即可，收到一个子串就会调用 push_substring，根据 map 中的内容重组 ByteStream，整个思路就是比较 stream_idx，找到比 stream_idx 小的第一个位置以及比 stream_idx 大的第一个位置（二分查找）

Lab2: TCPReceiver

• make 出错：安装 libpcap-dev 库

• 三个索引：

  • (relative) seqno：从 ISN 开始，包含 SYN 和 FIN，32 位循环计数（这也是 TCP Header 的一个字段）
  • absolute seqno：从 0 开始，包含 SYN 和 FIN，64 位非循环计数（为什么不会循环，pdf 给出了说明：Transmitting at 100 gigabits/sec, it would take almost 50 years to reach 2^64 bytes. By contrast, it takes only a third of a second to reach 2^32 bytes.）
  • stream_index：从 0 起步，排除 SYN 和 FIN，64 位非循环计数

• 首先理解 wrapping_intergers 转换过程

  • absolute seqno 转 seqno 比较简单：absolute seq 转 32 位之后直接和 isn 相加即可，溢出自动处理
  • seqno 转 absolute seqno 需要思考一下：需要利用上一次收到的 checkpoint 参考

• 实现 TCPReceiver

  • segment_received()：该函数将会在每次获取到 TCP 报文被调用，完成两个功能
    • 如果接受到 SYN 包就设置 ISN 编号（SYN 和 FIN 包仍然可以携带用户数据并一同传输。同时，同一个数据包下既可以设置 SYN 标志也可以设置 FIN 标志。why ??? 有点不太理解）
    • 将收到的数据直接丢进 stream reassembler，并在接收到 FIN 包时终止数据传输
  • ackno() 返回接收方下一次期望接收到的字节索引，根据 ByteStream 已写字节数得到 absolute seqno （注意如果是 FIN 需要 ++），然后转换成 seqno 即可
  • window_size() 返回接受窗口的大小，也就是 capacity - ByteStream 的 BUFFER_SIZE，可以用于「流量控制」

Lab3: TCPSender

• TCPSender 需要将 ByteStream 中的数据以 TCP 报文形式持续发送给 receiver（利用写好的 TCPSegment 这个类填充其中的头部字段以及 payload 信息）

• 需要处理 TCPReceiver 传入的 ackno 和 window size，以追踪接收者当前的接收状态，以及检测丢包情况

• 若经过一个超时时间后仍然没有接收到 TCPReceiver 发送的针对某个数据包的 ack 包，则重传对应的原始数据包，主要这里的检测主要是通过 tick 函数实现，不需要使用 timer 相关的系统调用，tick 函数的入参就是上一次调用到现在的时间（ms），因此需要维护一次 全局计时器变量 timecount，另外采用“指数退避”的思想，每次超时之后 timeout *= 2，另外需要维护一个全局的重传次数 retans_count，如果某个报文连续重传次数达到 8 次需要发送 RST 报文终止连接（当然这个是在 Lab4 中实现的）

• 注意！！！remote_window_size 应该初始化为 1，否则如果「初始」就丢包的话 remote_window_size = 0 不会退避 timeout，另外接收方的 Windows size 为 0，发送方也将按照接收方 window size 为 1 的情况进行处理，持续发包。为了 keep alive

  • 退避的前提的是 window_size > 0，接收方可以接收数据但是网络拥塞了导致还没有收到数据，超时一次超时时长会乘2 （实行网络拥塞控制）

• 维护一个已经发送但未被确认的 segment 队列 std::queue<std::pair<size_t, TCPSegment>>， 如果 ack_receiver 是收到 ackno 以及 window_size 之后需要检查 queue 以及移除并 reset timer 相关变量

  • 相当于采取累计确认方式通过维护缓存队列重传
  • 根据 ackno --> abs_seq，如果 abs_seq > _next_seqno 直接丢弃并返回，否则从头遍历 queue 移除那些已经确认的 segment

Lab4: TCPConnection

• TCPConnection 需要将 TCPSender 和 TCPReceiver 结合，实现成一个 TCP 终端，同时收发数据。

• 接受数据端：

  • 如果收到 RST 直接关闭连接，否则交给 TCPReceiver 处理，对其中各个字段解析

  • 收到 ACK 需要向当前自己的 TCPConnection 的 TCPSender 对端的 ackno 和 window_size 信息

    这一步相当重要，因为数据包在网络中以乱序形式发送，因此远程发送给本地的 ackno 存在滞后性。将远程的 ackno 和 window size 附加至发送数据中可以降低这种滞后性，提高 TCP 效率。

• 发送数据端：

  • 当 TCPSender 从 ByteStream 读取数据组成一个 TCPSegment 放入待发送的队列时，TCPConnection 从其中取出并将其发送（push 到 _segment_out 队列即可）
  • 在发送当前数据包之前，TCPConnection 会获取当前它自己的 TCPReceiver 的 ackno 和 window size（用来表示自己下一次期望接收到 seqno 以及自己的 window_size），将其放置进待发送 TCPSegment 中，并设置其 ACK 标志。

• TCPConnection 需要检测时间的流逝。它存在一个 tick 函数，该函数将会被操作系统持续调用。当 TCPConnection 的 tick 函数被调用后，它需要

  • 告诉 TCPSender 时间的流逝，让其重新发送丢失的数据包
  • 如果 sender 的「连续重传次数」超过 TCPConfig::MAX RETX ATTEMPTS，发送一个 RST 包终止连接
  • 考虑 TIME_WAIT 状态

• 关闭连接

  • 接收方收到 RST 标志或者发送方发送 RST 标志后，设置当前 TCPConnection 的输入输出字节流的状态为错误状态，并立即停止退出。这种属于暴力退出（unclear shutdown），可能会导致尚未传输完成的数据丢失（例如仍然在网络中运输的数据包在接收方收到RST标志后被丢弃）。
  • 若想让双方都在数据流收发完整后退出（clear shutdonw），考虑四次挥手，参考 K 大的博客

Lab5: NetworkInterface

• ARP 协议：根据 IP 地址获取 Mac 地址，实现简单的 ARP 协议

• 维护 ARP 条目哈希表，每个条目 TTL 为 30s，到期之后删除

• send_datagram(dgram, next_hop) 时如果 ARP 表中没有 IP 地址对应的表项就广播发送（构造 ARPMessage 以及 Ethernet Frame TYPE_ARP），如果有的话就直接构造 Ethernet Frame TYPE_IPv4 将 dgram 发送

• recv_frame(dgram) 首先判断是不是 frame 的 目的地址是不是 自己的Mac/广播地址，不是直接 丢弃

  • TYPE_IPv4：收到 IP 数据包直接转发丢给上层

    为啥 recv_frame 为什么还可以收到 IPv4 的数据包呢？因为 ARP 数据包加上 Ethernet Frame Header 之后变成以太网帧在数据链路层传输，Frame 类型有很多，包括 IPv4、IPv6、ARP 等等，如果是 IPv4 数据包仅仅只需要转发给 caller 即可，因为作为数据链路层不需要管 TCP 状态、IP 字段等等其他信息

  • TYPE_ARP：收到 ARP 包分为请求和应答两种情况处理

    • 请求：将自己的 Mac 封装之后发送，并且更新 ARP 表项
    • 应答：更新 ARP 表项，并且检查 IP 请求列表，如果相符就 send_dgram，并删除对应的表项

• tick(ms_since_last_tick) 删除过期的 ARP 表项以及 已经发送 dgram 表项

Lab6: Router

• router：实现简单的路由表，转发数据包，维护路由表（哈希表），最长匹配原则

• add_route(route_prefix, prefix_length, next_hop, interface_num)：添加一条路由表项

• route_one_datagram(dgram)：查询路由表，如果存在匹配项切 TTL > 1 就转发给下一跳/直连，并将 TTL 减一，其余情况全部丢弃

Lab7

• 将之前所有内容合为一个 app

  

参考

• 重点理解 CS144Socket 的角色：https://github.com/Kiprey/Kiprey.github.io/issues/74#issuecomment-1751716850
• https://csdiy.wiki/计算机网络/CS144/
• K大博客：https://kiprey.github.io/tags/CS144/
• 掘金博客： https://juejin.cn/user/822883244836461
• CS144-2019翻译：http://doraemonzzz.com/tags/CS144/
• CS144-2019：https://blog.csdn.net/kangyupl/article/details/108589594
• https://zhuanlan.zhihu.com/p/464281077
• https://gitee.com/dying1122/cs144-lab

------------------分割线，以下是原文------------------

For build prereqs, see the CS144 VM setup instructions.

Sponge quickstart

To set up your build directory:

$ mkdir -p <path/to/sponge>/build
$ cd <path/to/sponge>/build
$ cmake ..

Note: all further commands listed below should be run from the build dir.

To build:

$ make

You can use the -j switch to build in parallel, e.g.,

$ make -j$(nproc)

To test (after building; make sure you've got the build prereqs installed!)

$ make check_labN *(replacing N with a checkpoint number)*

The first time you run make check_lab..., it will run sudo to configure two TUN devices for use during testing.

build options

You can specify a different compiler when you run cmake:

$ CC=clang CXX=clang++ cmake ..

You can also specify CLANG_TIDY= or CLANG_FORMAT= (see "other useful targets", below).

Sponge's build system supports several different build targets. By default, cmake chooses the Release target, which enables the usual optimizations. The Debug target enables debugging and reduces the level of optimization. To choose the Debug target:

$ cmake .. -DCMAKE_BUILD_TYPE=Debug

The following targets are supported:

• Release - optimizations
• Debug - debug symbols and -Og
• RelASan - release build with ASan and UBSan
• RelTSan - release build with ThreadSan
• DebugASan - debug build with ASan and UBSan
• DebugTSan - debug build with ThreadSan

Of course, you can combine all of the above, e.g.,

$ CLANG_TIDY=clang-tidy-6.0 CXX=clang++-6.0 .. -DCMAKE_BUILD_TYPE=Debug

Note: if you want to change CC, CXX, CLANG_TIDY, or CLANG_FORMAT, you need to remove build/CMakeCache.txt and re-run cmake. (This isn't necessary for CMAKE_BUILD_TYPE.)

other useful targets

To generate documentation (you'll need doxygen; output will be in build/doc/):

$ make doc

To format (you'll need clang-format):

$ make format

To see all available targets,

$ make help