# CS144-2021

**Repository Path**: ericps/cs144-2021

## Basic Information

- **Project Name**: CS144-2021
- **Description**: CS144 源码记录
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: mysol
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 1
- **Created**: 2023-06-19
- **Last Updated**: 2023-11-11

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 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大博客](https://kiprey.github.io/tags/CS144/)，大概弄懂了 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 合并分支：[参考](https://git-scm.com/book/zh/v2/Git-%E5%88%86%E6%94%AF-%E5%88%86%E6%94%AF%E7%9A%84%E6%96%B0%E5%BB%BA%E4%B8%8E%E5%90%88%E5%B9%B6)
- 内含 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 大的第一个位置（二分查找）

![reassembled](https://p6-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/1ca0780f1be94436a074a7f85d48194d~tplv-k3u1fbpfcp-zoom-in-crop-mark:1512:0:0:0.awebp?)



### 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 [参考](https://zhuanlan.zhihu.com/p/464281077)
- 实现 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

![system](https://gitee.com/dying1122/cs144-lab/raw/master/assets/1683900423271.png)

### 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

  ![](https://kiprey.github.io/2021/11/cs144-lab7/image-20211118211047223.png)



### 参考
- **重点理解 CS144Socket 的角色**：https://github.com/Kiprey/Kiprey.github.io/issues/74#issuecomment-1751716850
- https://csdiy.wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C/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](https://web.stanford.edu/class/cs144/vm_howto).

## 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](https://web.stanford.edu/class/cs144/vm_howto) 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](https://www.kernel.org/doc/Documentation/networking/tuntap.txt) 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](https://en.wikipedia.org/wiki/AddressSanitizer) and
  [UBSan](https://developers.redhat.com/blog/2014/10/16/gcc-undefined-behavior-sanitizer-ubsan/)
- `RelTSan` - release build with
  [ThreadSan](https://developer.mozilla.org/en-US/docs/Mozilla/Projects/Thread_Sanitizer)
- `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