cs144-sp23, Lab Checkpoint 4: down the stack (the network interface)

记录 cs144 Spring-23 Lab4: down the stack (the network interface) 的思路与实践难点。与以往实验不同的是， spring 2023 版本没有要求实现 TCP Connection 部分（将 TCPReceiver 和 TCPSender 结合起来）。

CS144 Spring 2023 实验仓库 CS144/minnow，备份为 HangX-Ma/minnow 进行版本回退即可。
CS144 Spring 2023 Lab4 项目指导书 - Lab Checkpoint 4: down the stack (the network interface)。
具体的项目实现在个人的 Github。

1. 内容简述

network interface structure

Lab4 要求实现网络接口部分，打通网络数据报（Internet datagrams）和链路层的以太网帧（link-layer Ethernet frames）之间的桥梁。之前的实验实现了 TCP segments 在使用 TCP 协议的设备之间的传输，而 TCP 报文是如何传递的？ TCP报文有三种方式可被传送至远程服务器：

TCP-in-UDP-in-IP： TCP 报文会被置于用户的数据报的 payload 中，在用户空间下这是最简单的实现方式： Linux 提供接口（如 UDPSocket），而用户侧仅需要提供 payload，目标地址， Linux 内核会负责将 UDP 报部， IP 报头，以太网报头组装起来，将这个网络包发向下一个 hop。 Linux 内核会保证每个 socket 会有独立的本地与远端地址以及端口号，并且保证这些数据在应用层的相互隔离。
TCP-in-IP： 一般情况下， TCP 报文会直接放在 Internet datagrams 中，这通常被成为 “TCP/IP”。 Linux 会提供一个 TUN 设备接口，需要应用层提供整个 Internet datagram，而 Linux 内核则会处理剩下的部分。但此时应用层需要自己构建整个 IP 报头以及 payload 部分。
TCP-in-IP-in-Ethernet： 以上的方法依赖Linux内核来实现的协议栈操作，每次用户向 TUN 设备写入 IP datagrams 时， Linux 都需要构建正确的带有 IP datagrams 的以太网帧作为 payload。这意味着 Linux 需要知悉下一个 hop 的以太网目的地址，给出其 IP 地址。否则 Linux 会以广播的形式请求这些信息。

这些功能是由 Network Interface 实现的，该组件能将 IP 数据报转义成以太网帧等等，之后会传入 TAP 设备（类似 TUN 设备但更底层），实现对 link-layer 的数据帧的传输。

网络接口的大部分工作是， 为每个下一跳 IP 地址查找(和缓存)以太网地址。而这种协议被称为 地址解析协议 ARP （Address Resolution Protocol）。

Address Resolution Protocol - wiki

2. Network Interface 实现

2.1 默认接口

在 Lab4 的 Network Interface 中我们需要实现以下几个部分，维护一个 IP 地址到 Ethernet 地址的映射表。这个映射类似缓存，能提高网络栈的传输效率。

send datagram： 该方法被 TCPConnection 或者 router 所调用，这个接口就是将待发送的 Internet(IP) datagrams 转义为以太网帧并最终发送出去。
- 如果以太网目的地址是已知的就直接发送，创建以太网帧（type = EthernetHeader::TYPE IPv4），将 payload 设置为串行的数据报文，并设置源地址和目标地址。
- 如果以太网目的地址未知，广播下一跳的以太网地址的 ARP 请求，并将 IP 报文放入队列中待 ARP 回复收到后能将其发送出去。
  
  需要间隔 5 秒再发送相同的 ARP 请求，并且只有在收到目的以太网地址后再将数据报放入队列中。若没有收到目的以太网地址，我们需要将 dgrams 以及其对应的 Address 都暂存在列表中，以供之后收到 ARP reply 后再进行发送，否则这部分数据就会丢失了。
```
 void send_datagram(const InternetDatagram &dgram, const Address &next_hop);
```
recv frame： 该方法接收来自网络的以太网帧，但需要忽略任何目的地址非网络接口部分的帧（广播地址或者存储在 _ethernet_address 中的接口自身的以太网地址）。
- 若为 IPv4 帧就将其以 InternetDatagramF 进行解析，若成功的就将结果的 InternetDatagramF 返回给调用者。
- 若为 ARP 帧就将其以 ARPMessage 进行解析，若成功则缓存发送方 IP 地址与以太网帧的映射 30 秒。若这个 ARP 请求是询问我们的 IP 地址，就回复正确的 ARP 答复。
  
  根据 FAQs 中的答疑，我们需要自行创建一个用以存储映射的 arp_table_。
```
 std::optional<InternetDatagram> recv_frame(const EthernetFrame &frame);
```
maybe send： 该方法在必要时发送 EthernetFrame。
```
 std::optional<EthernetFrame> maybe_send();
```
tick： 记录时间，以使得任何已经过期的 IP 地址到 Ethernet 地址的映射失效。
```
 void tick(size_t ms_since_last_tick);
```

FAQs and special cases 中的信息都很有帮助，可以当作一种提供解题思路的 Hints。

2.2 额外说明

Ethernet Frames

EthernetFrame 是我们需要传输给 TAP 设备的数据，根据已有信息，我们只需要将组装好的 EthernetFrame 用 queue 数据结构封装即可。

// outbound Ethernet frames which will be sent by the Network Interface
std::queue<EthernetFrame> outbound_frames_ {};

ARP Table

从以上接口的描述可以看出，我们需要建立一个存储 ARP 映射的 arp_table_， IP-To-Ethernet。根据 wiki 关于 ARP 原理章节的阐述，这个表中的 ARP 数据需要有一个变量存储 EthernetFrame 表示映射目标，以及 ttl (time-to-live) 表示该条 ARP 信息的生命周期（默认是 30s）。另外，在 FAQs 中有这么一句：

Q: How do I convert an IP address that comes in the form of an Address object, into a raw 32-bit integer that I can write into the ARP message?
A: Use the Address::ipv4 numeric() method.

这说明 ARP 的映射应当是 uint32_t 类型到 arp_t 类型，我们可以用一个 unordered_map 数据结构存储映射信息。除此之外我们还注意到，同一个 ARP 的 ARP 请求的间隔需要 5s，那么除了映射信息外，我们还需要一个 list 结构用以存储绑定 InternetDatagram 和 Address 的等待列表 arp_datagrams_waiting_list_。另外，为了记录 ARP 请求的声明周期，我们还需要一个 unordered_map 数据结构存储 numeric IP 与该条 ARP 请求的声明周期的映射 arp_requests_lifetime_。

这里使用 list 数据结构是头文件中已经包含了相关的库文件，另外这部分信息具有时效的不确定性，我们并不清楚 ARP 请求究竟哪一个会在下一刻返回，所以在这部分信息我们需要逐个遍历，将已经获取目标以太网地址的数据包组装后放入发送队列中，并从 list 中移除。故而使用 list 数据结构能够利用链表插入/移除数据的快速性的优势，而不用考虑查询带来的负面影响。

这样关于 ARP Table 的数据结构就可以按如下格式创建。需要注意的是 TTL 的时间单位是 ‘毫秒’，而我们设定的边界值都是以 ‘秒’ 为单位。

// ARP will be stored for 30s at most, which can reduce the length of ARP table,
// increasing the enquiry speed. What's more, 
const size_t ARP_DEFAULT_TTL = 30 * 1000;
const size_t ARP_REQUEST_DEFAULT_TTL = 5 * 1000;
typedef struct arp {
    EthernetAddress eth_addr; // mac address
    size_t ttl; // time to live
} arp_t;
std::unordered_map<uint32_t/* ipv4 numeric */, arp_t> arp_table_ {};
std::list<std::pair<Address, InternetDatagram>> arp_requests_waiting_list_ {};

内存泄漏

在遍历 ARP Table 的时候我用了迭代器，但是调用了 erase 函数之后又用了 iter++ 去获取下一个 ARP 项，这产生了矛盾，当前的迭代器的内存空间已经被释放了。因而使用 erase 函数需要注意使用 iter = xxx.erase(iter); 来更新迭代器的内容。

3. 测试结果

cs144@cs144-ubuntu22:~/minnow$ cmake --build build --target check4
[1/1] cd /home/cs144/minnow/build && /usr/bin/ctest --output-on-failure --stop-on-failure --timeout 12 -R '^net_interface'
Test project /home/cs144/minnow/build
    Start  1: compile with bug-checkers
1/2 Test  #1: compile with bug-checkers ........   Passed   20.14 sec
    Start 35: net_interface
2/2 Test #35: net_interface ....................   Passed    0.15 sec

100% tests passed, 0 tests failed out of 2

Total Test time (real) =  20.29 sec

PREVIOUScs144-sp23, Lab Checkpoint 3: the TCP sender

NEXTcs144-sp23, Lab Checkpoint 5: building an IP router