cs144笔记
cs144 Lab 0到Lab 7所有笔记。
Lab 0
构造一个字节流。我是用一个数组实现的，需要用到模运算。
Lab 1
接收方把接收到的子串，重新组装（reassemble）为原序列，也就是按顺序排列的序列。主要还是算法的问题，不涉及网络。
Lab 1的主要工作就是处理接收到的子串。绿色部分是reassembler已经处理好按顺序的序列，但还没有被上层读取，所以要保存起来，占用窗口空间。如果新来的子串中包括first unreassembled，就往后添加为绿色部分。并且继续往后看，如果有红色部分和刚刚标记为绿色的部分是相接的，就继续往后走。如果新来的子串在first unreassembled以后，就标记为红色的。如果大于first unacceptable，就不用添加。其实就是接收窗口。
Lab 2
实现TCPReceiver。需要处理序号格式的转换。接收数据时，除了一些特殊情况，往reassembler里面写数据就行了。
Lab 3
实现TCPSender。需要注意的有以下几点：
- 窗口管理。需要在发送方维护一个表示接收方可接收数据窗口大小的变量
_acceptable_win，初始化为1。但是这个和接收方发过来的window size不一样，具体为：这样做是因为可能接收方发送数据时，发送方发到的介于1和2之间的数据接收方还没收到。每次发送新数据时，需要将1
2
3
4
5
6
7|<--------------------window_size-------------------->|
|XXXXXXXXX|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|
1 2
1: receive_absolute_ackno，接收方发送过来的ACK
2: _next_seqno，发送方下一个未发送的数据
window_size，接收方发送过来的窗口大小
window_size - (_next_seqno - receive_absolute_ackno)是发送方可发送的窗口大小_acceptable_win_acceptable_win减去对应的数据大小。重传数据时不用，因为那是介于1到2之间的部分。 - 接收与发送。需要维护一个表示发送方已发送但未收到
ACK的包的集合_segments_outstanding，也就是上面1到2之间的数据。每次接收到包时，查看接收方发过来的ACK和window_size，更新_segments_outstanding和_acceptable_win。然后调用fill_window()，也就是尽可能多选数据，然后发送。同样也需要更新_acceptable_win和_segments_outstanding。fill_window()也可以由上层应用调用。 - 超时重传。以上的接收与发送是正常情况下的。如果发送方发送了一个包后，经过了指定时间
RTO还没收到一个有效的ACK，发送方就需要重新传送_segments_outstanding中最早的一个包。时间信息由tick()提供。还需要自己实现一个计时器。此计时器记录的是最早发送的未收到ACK的包（不管是新数据还是重传数据）的已发送时间。发送新数据时，如果计时器已经在计时，则不管，接着计时；如果未开始计时，则打开，重置计时器为0。重传包时，都要重置计时器为0（此时计时器必然打开，因为是否重传需要依靠计时器是否打开和经过的时间来判断）。如果正常接收到了有效ACK，重置为0。如果调用tick()时发现计时器大于RTO了，说明在这RTO时间段内没有接收到ACK，触发重传。此时也要把计时器重置为0，重复以上步骤。 RTO加倍。有时候由于网络拥塞，包往返时间是要增加的。所以每次超时重传时，都要把RTO加倍，直到某个界限。恢复为初始值的条件是发送一个包后在RTO时间内接收到一个有效ACK，这说明网络恢复正常了。但有一种情况超时重传时不用加倍：接收方发送过来的window_size为0。这表明接收方的上层应用由于某种原因（比如繁忙）还没有取出接收方接收到的数据，并不是由于网络拥塞导致的超时。所以此时不用加倍，但是要设置_acceptable_win为1，虽然可能接收方还是无法接收，但是发送方能够通过接收方返回来的数据掌握窗口大小变化的情况。
几个要注意的点：
- 在这里实现的时候，
SYN是需要单独发送的，也就是SYN包里面没有数据，但是FIN是可以附在有数据的包上的。 SYN和FIN都占用一个seqno，但都不占用包的数据载荷。- 计时器是通过两个变量一起实现的。一个指示计时器是否打开，一个表示计时器经过的时间。
tick()函数由上层调用，参数为距离上次调用tick()经过的时间，也就是提供了时间信息。
Lab 4
一个TCP通信是点对点的，双方各有一个接收和发送通道。而这一次的Lab就是把之前的TCPReceiver和TCPSender融合起来。最主要的函数是segment_received()，此函数把接收到的网络包分别给TCPReceiver和TCPSender：TCPReceiver接收对面的数据，按顺序排好，给上层的是字节流；如果有包中有ACK，把ACK和WIN交给TCPSender，调整发送窗口，并尽可能地发送数据。如果包中没有ACK，则说明这是对面的第一个SYN包，这里又分为两种情况，就不细讲了。最后真正发送时，因为是从TCPSender那里获取要发送的包，需要加上TCPReceiver给出的ACK（如果有的话）和WIN再发送。
下面主要讲一下建立连接和断开连接两个阶段，倒不是讲怎么实现的，而是为什么这么实现。实现的时候也还好，有些就是直接把之前写的堆在一起就能实现功能了，很奇妙，比如建立连接阶段。
1 | 建立连接 断开连接 |
要确保每个包都被送达，如果是SYN，FIN或者是有数据的包，重传机制可以确保包被送达。所以需要特别关注的是最后单独的ACK。用Lab里的话就是：TCP doesn’t deliver acks reliably (it doesn’t ack acks)
- 建立连接：前两个
SYN和SYN+ACK重传机制可以保证被送达，那么就只剩下了A发送的最后一个ACK，此ACK是对B的SYN的答复。一种思路是让B再给A答复对于此ACK的ACK，但此时又要保证B的最后一个ACK被送达。这样就会循环下去，也就是造成了两军问题。所以，TCP在这给出的思路是不管了，认为被送达，和断开连接时给出的等待一段时间不同。我认为TCP这样设计是因为断开连接时如果直接断开，不管了，认为被送达，万一没送达对面重传了就出错了，但刚刚建立连接时一般不会马上断开，如果B的SYN+ACK重传了，A还可以答复。而且如果未送达，A在B重传前发送了字节流，如果这个包能送达，则里面的ACK也能够确认B的SYN。 - 断开连接：B会对A的
FIN答复ACK以及FIN+ACK，A最后的ACK确保了B的答复A是收到的。而A对于B的FIN的答复，并不能确保B收到，因为B收到答复后，确认了自己的FIN和对A的FIN的ACK被收到就直接关闭了。而A要等待一段时间，防止A对FIN的答复B没收到，进而重传FIN时A已关闭。如果过一段时间后B还没有重传，则A认为自己的ACK发送成功，就关闭了。
别的几点：
- 本次Lab涉及到
RST，有两种情况会发出RST，发送和接收到RST时要断开连接。 - 我的实现里面最后B发送的
ACK和FIN+ACK应该总是分开的，不会出现压缩成一个FIN+ACK的情况。但压缩成一个FIN+ACK从原理上来讲也是可以的，能够保证正常通信，此时各个包的情况就和建立连接阶段类似。但在实际情况中一般B对应服务端，可能在A要断开时还有数据要发送，所以分开发的情况更常见一点。 - 最后修改了
webget.cc，修改前是正常的，修改后就不能正常获取到网页了，我也不知道是什么原因，有点遗憾。☹
Lab 5
本次实验还是比较简单的，主要是实现ARP协议。当在ip头填好ip后，就可以根据路由表决定下一跳了（在Lab 6中实现）。有了下一跳地址，就可以在以太网层发帧（frame）了。以太网帧的头部分别为：目标以太网地址、源以太网地址、帧类型。常见的帧类型为ARP、IPv4这些，意思就是这个以太网帧的内容是ARP、IPv4等。此时若不知道目标以太网地址，就需要ARP协议。A需要发的数据的下一跳是B的ip，此时已知B的ip，需要知道B的以太网地址，就广播（目标以太网地址为FF:FF:FF:FF:FF:FF）一个ARP报文。此时不管是B还是另一个C收到此ARP消息后，都把A的ip和MAC地址对缓存一定的时间，然后C对此报文的操作就结束了。B回复给A它的MAC地址。A收到后会记录ip和MAC映射，然后把之前的数据发送出去。需要注意的是A发送ARP广播之前需要记录要发送的数据以及下一跳（B的ip地址），以方便最后和B返回的消息对比。我一开始直接用数据里ip头的ip地址和B返回的消息对比，这是不对的，因为B的ip是下一跳，而ip头里面的是最终地址，不一样的。
TAP
但这次Lab的最大收获不是这些。因为这次Lab又要修改webget.cc，以实现TAP层面上的调用。这里先说一下TAP和TUN，这两个都是虚拟网络设备。在真实物理设备中，要用网卡发送数据时只需要提供要发送的数据，然后调用socket接口，系统会完成tcp到ip到以太网帧的包装，然后通过网卡发送。如果人为地提供ip层的数据，然后往TUN设备里面写，系统会根据ip决定下一跳，有时会发出ARP广播，然后构造以太网帧，最后通过物理网卡发送。如果人为地提供以太网帧（也就是说已经知道下一跳的ip地址，可能会发送ARP查询，此Lab就是在做这个事情），然后往TAP里面写，就能通过虚拟网卡发送出去了。但我这次改了以后还是不行，我看了下测试代码，以下代码构造了TAP：
1 | tap.sh |
我改好后抓包，发现是先用系统调用产生一个TAP设备。然后模拟一个本地的设备，ip为169.254.10.9，发送数据给下一跳tap10（此时没有经过路由，因为已经构造到了以太网层，而且每一次的下一跳地址都是tap10，是在代码里写死了的，都不经过路由）：
1 | //! \param[in] seg the TCPSegment to send |
也就是169.254.10.1（以太网层面上，ip头里面还是真正的最后目的ip）。因为刚开始本地设备不知道tap10的MAC地址，所以会发出ARP查询，tap10也做了响应。然后本地设备给tap10发送了数据包（此时也没有查路由表），也就是TCP连接的第一个SYN，tap10收到了，之后就没有响动了。然后本地设备由于没有接收到响应，继续重传。然后就没有了。所以我猜测是因为tap10收到数据包后不知道下一跳，所以不往外发。为了验证这一猜想，我用route查看路由表：
1 | Kernel IP routing table |
可以看出，发往169.254.10.0/24的数据包转交给tap10，但这是发往169.254.10.0/24的情况。现在的情况是没有经过路由，直接发送给tap10后确实没有设置下一跳了。所以，可以再添加一个设备（可以是物理设备），此设备有两张网卡，一张可以正常上网，另一张直接和169.254.10.1连接，然后设置测试ip或者默认ip的Gateway为此能上网的网卡的网关，Iface（Iface: Interface to which packets for this route will be sent，也就是此路由的数据包将发送到的接口）为能上网的网卡，169.254.10.1/24路由到tap10。这样应该就可以了（其实添加一张网卡，然后设置两个ip应该也可以，意思都差不多），就像这里的默认路由一样，通过eth0发送到我的主机（我是用WSL2做实验的）。但这样很麻烦，所以我想到了echo 1 > /proc/sys/net/ipv4/ip_forward，也就是让数据包在网卡之间转发。在这里和这里找到了方法。在项目根目录下的tap.sh/start_tap()后面添加：
1 | iptables -A FORWARD -i tap10 -o eth0 -j ACCEPT |
意思就是让tap10接收到的数据包用eth0转发出去。但是我直接写在tap.sh里面不起作用，所以直接在命令行里面运行就行了。之后用sudo iptables -L -v -n查看：
1 | Chain FORWARD (policy ACCEPT 0 packets, 0 bytes) |
用sudo iptables -t nat -L -v -n查看nat表：
1 | Chain POSTROUTING (policy ACCEPT 0 packets, 0 bytes) |
添加上去了，然后再运行make check_webget，就终于正常了！！！
用sudo tcpdump -i any -w /tmp/packets.tap抓包，发现确实，每次都是本地设备先发送给tap10，然后eth0再转发，接收的时候一样，eth0先接收一次，然后tap10再发送给本地设备。就是经常会重传，应该是重传时间设置得太短了。
同样的道理，Lab 4运行前两条命令，最后那一句已经写过了。把tap10改为tun144，因为发出请求的是169.254.144.9，属于tun144，然后Lab 4的webget.cc也通过了。我抓包tun144，发现有这么一句tcpdump: listening on tun144, link-type RAW (Raw IP)。抓到的包不管是发送还是接收，和169.254.144.9直接相关的都是没有以太网层的数据。但抓包eth0，一切正常，也就是用WSL2的网卡发给主机和WSL2连接的网卡时有以太网帧。所以，可以得出结论：TUN层面的数据包转发，第一次原本的数据只包装到ip层，然后加上以太网层，转发的网卡拿到后，再发送出去。
我看网上说的数据包转发：所谓转发即当主机拥有多于一块的网卡时，其中一块收到数据包，根据数据包的目的ip地址将数据包发往本机另一块网卡，该网卡根据路由表继续发送数据包。这通常是路由器所要实现的功能。确实是这样子的，不经过路由直接发送给tap10，tap10接收到数据后，要用eth0转发出去，eth0查路由表的时候，测试的ip符合默认路由，由eth0发送。而外界的数据包发送到eth0做了NAT转换后（应该是要做的），目的地址变成了169.254.10.9，查路由表，符合169.254.10.0/24，用tap10发送出去。
TAP的构造和各级序列化&解析
在libsponge/tcp_helpers/tcp_sponge_socket.cc中构造FullStackSocket()的时候会传递TapFD("tap10")，这个参数最终会在libsponge/util/tun.cc中使用系统调用构造一个TAP设备。此TAP设备读写的操作在libsponge/tcp_helpers/tuntap_adapter.cc中。读数据时先把数据解析成以太网帧，然后解析以太网帧的数据部分（除了头部的部分）为ip包，然后解析ip包的数据部分为tcp包，最终返回tcp包。写的时候也是，接收到的是tcp包，序列化为ip包数据部分，加上ip头，然后用网卡发送的时候再序列化整个ip包为以太网帧的数据部分，加上以太网头，最终发送时序列化整个以太网帧。
我也看了看各级是怎么进行序列化和解析的。先从最上面开始，TCPSegment有TCPHeader和数据部分（真正要发送的数据）。序列化TCPSegment时，TCPHeader单独序列化（方法其实很简单：把头部要发送的不同长度的数据按顺序添加成一个字符串），然后加上数据部分，形成一个大的字符串形式的数据（实际实现中使用的是自定义的BufferList）。IPv4Datagram同理，IPv4Header单独序列化，然后添加TCPSegment的序列化结果（IPv4Datagram._payload）。EthernetFrame同理，EthernetHeader单独序列化，然后添加IPv4Datagram（InternetDatagram）的序列化结果（IPv4Datagram._payload）。接收到的数据（_tap.read()）是字符串，EthernetFrame按顺序把EthernetHeader中不同长度的数据读出来后，这部分字符串就丢弃了。剩下的就是InternetDatagram整个部分。读出IPv4Header后，剩下的是TCPSegment。读出TCPHeader后，剩下的是对面发送来的数据了。
Lab 6
这次是要实现一个路由器的功能。路由器可以有好多网卡，每当一个网卡收到数据包而不是ARP之类的包时，就需要转发此数据包。转发是根据路由表来转发的。路由表有四个关键参数：网络前缀、子网掩码、下一跳和网卡。找到与ip包中目的地址最长匹配的网络，就用对应网卡发送到下一跳。不考虑NAT转换，假设本设备的一个网卡是A，下一跳ip不能够到达目的地址，则下一跳是路由器，对应的网卡是B，则匹配完成后是使用网卡A发送数据包到网卡B。如果下一跳ip直接到达目的地址了，也就是A和目的地址的一个网卡是直接相连的，则匹配完成后会发现下一跳为空（是这么设置，插入的）。此时需要做的是把ip包中目的地址作为下一跳，通过A发送出去（也只能这么做，路由表又不记录要发给这个网络里面的哪一个设备，只能自己填写）。注意，路由表中记录的和网卡发送数据时接收的下一跳地址是下一跳的ip地址，如果arp表中有对应的MAC地址，则直接构造以太网帧发送，否则使用arp协议找到MAC地址然后再发送。
虽然此次Lab没有用到之前TCP的代码，但是用到了Lab 5的网卡的代码的。也就是说，路由器是在以太网层之上的，接收和发送都要用到网卡，在接收和发送之前查路由表，确定下一跳地址。
Lab 7
这次不需要写代码，合并到Lab 7的分支后，直接测试，我用我的WSL2和Azure相互测试，是可以的。然后测试1M文件的发送接收，出问题了，时间很长。然后我用小一点的文件比如100K，是可以的，应该是底层的算法速度太慢，但我不打算改了，整体方向对了就可以了。
然后看了下Lab 7实验提供合在一起的代码，还是比较简单的。构造了服务端和客户端，每个都配一个路由器，有两张网卡，一边连的是服务端/客户端，一边连的是因特网。发往因特网时，用系统调用UDP发送整个以太网帧到实验提供的网站，在他们那做一个中转，然后发给对面。lab7.cc里面的规则是对于服务端/客户端和路由器之间的规则，有些就是路由。比如路由器因特网端的网卡接收到数据以后（其实是UDP接收到以后发送因特网端网卡的），从因特网端的网卡拿出数据后做路由，然后用本地连接的网卡发送给服务端/客户端，反之亦然。这和上个Lab中讲到的是一样的。服务端/客户端代码中TCP的规则还是在libsponge/tcp_helpers/tcp_sponge_socket.cc中。
总结
- 我写前几个Lab的记录的时候，感觉都很短，所以打算放一起写了。但是到后面越写越长。里面有些词用得不规范，比如包、数据包、以太网层，但也不想改了，知道意思就行了。
- 实验整体设计还是可以的，但有些地方，就比如Lab 4，实验说明里面写得也不细致，好多corner case都是看测试代码才知道的，属于面对测试用例编程。
- 我不知道TUN和TAP那里Lab本来是怎么设计的，是打算怎么发出数据。而且我在网上搜，别人好像没有这个问题。反正把我折腾了好久，才能够正常运行的。
- 断断续续搞得有半年，但中间好多时候都是有事啊这那的没弄，实际集中精力做的时间并不是很多。确实学到了很多。