2021 CS144 实验笔记

计算机网络一直是自己的薄弱项，因为感觉知识都是死记硬背，背完就忘。那就索性学一下 CS144，顺带梳理一下整个的网络流程。这篇笔记不光记录实验过程，也会记录相关的网络笔记。

整个项目编码耗时 51 小时 21 分钟。

整个实验的的顺序是自顶向下，正好对应《计算机网络 自顶向下》这本书。

如果要答案源码，直接私信或发邮件。

网络分层

按照五层网络模型，网络分层如下：

应用层

比如 HTTP，FTP 这类基于 TCP 等传输层协议构建的应用。数据叫 message。

传输层

负责应用程序之间传输报文，比如 TCP，UDP。数据叫 segment。

网络层

负责主机之间传输报文，如 IP 协议。数据叫 datagram。

链路层

负责将一个主机的报文传输到另一个主机。比如 WiFi 协议，以太网。数据叫 frame。

物理层

负责数据一个 bit 一个 bit 的传输，比如网线。

实验准备

环境搭建

这个实验是在虚拟机进行，我们不可能使用 vim 敲代码，更不可能在虚拟机里面装一个图形化界面，然后套娃开发。

这里给出两种方法：

VS Code 远程开发

使用 VS Code 的远程开发，通过 ssh 连接进入虚拟机，然后直接远程开发。适合懂得 C++ 语法的人操作，毕竟没有代码提示。

CLion 远程开发

因为本人对 C++ 语法不熟悉，如果没有 ide 辅助，估计一行代码都写不出来了，所以这里我使用的是 Clion。

方法也很简单，在自己电脑里面创建 CS144 项目，然后用 Clion 打开。在 clion 的 Preference->Toolchains 里面添加 Remote Host，然后在 Deployment 中添加目录映射（如果不映射，Clion 会自动映射到虚拟机里面的 tmp 目录下，不方便手动 make 运行测试用例）。

具体大家可以百度。

调试技巧

解决 Debug 时莫名其妙跳过断点以及 Optimized Out

在 Lab 4 之前，我都是将就着调试，但是到了 Lab 4 真顶不住了。出现这个问题主要就是编译器已经对代码进行了优化，我们设置为不要优化即可。

找到项目目录下的 etc/cflags.cmake ，第 18 行，将
set (CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb3 -Og") 改为 set (CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb3 -O0")。

调试 lab 4 txrx.sh 的小技巧

在 Lab 4 的测试用例中，fsm 开头的测试用例我们能直接进行跑，并且进行 debug，但是有相当大的一部分实验是通过 txrx.sh 脚本跑，这里给大家一点调试方案。

• 把代码中所有的 std::cout 的调试信息输出全部换成 cerr，因为 ctest 中是不会显示标准输出的内容。
• ctest 单独运行一个测试脚本的命令如下： ctest --output-on-failure -V -R 't_icS_16_1'，-V 用于输出日志。同时使用 tshark 进行监听。tshark 是监听 tun144 还是 tun145 看具体的测试用例，你稍微看下 shell 脚本就知道了（不懂 shell 也没事，看名字就能猜到，因为我也是不会 shell 的）。

Lab 0 Networking Warmup

Lab 0 中主要是学习应用层的东西，不难，大多数人在日常中已经接触过了。

实验细节

第一部分是让我们利用系统的 tcp 实现一个 webget，这个没啥难点，调用 C++ 的包即可。

第二部分是让我们实现一个 ByteStream，这个代码注释也挺详细的，总之不难。

补充

常见应用层协议

FTP：

用于文件传输，基于 TCP。

SMTP，IMAP，POP3：

用于收发邮件，基于 TCP。

HTTP：

用于网页浏览，基于 TCP。

DNS：

用于域名解析，普通查询采用 UDP。父级 DNS 向子级 DNS 同步时，采用 TCP。

DHCP：

动态主机配置协议，基于 UDP。新主机加入网络时，以 0.0.0.0 为地址，向 255.255.255.255 广播地址发送 UDP 包，UDP 里面封装了 BOOTP 协议。这一步称为 DHCP Discover，内容如下：

此时网络里面的 DHCP Server 收到请求时，其提供地址，这一步叫 DHCP offer。因为新主机还是没有 IP 地址，DHCP offer 也是发往广播地址的，内容如下：

网络里面可能存在多个 DHCP Server，故新主机可能同时收到多个 DHCP Offer，新主机会选择最先到达的那个，并会向网络发送一个 DHCP Request 广播数据包，告诉所有 DHCP Server 它将接受哪一台服务器提供的 IP 地址，无关的 DHCP Server 会撤销它们提供的 IP 地址，以便提供给下一个 IP 租用请求者。DHCP Request 内容如下：

DHCP Server 接收到客户机的 DHCP request 之后，会通过广播返回给新主机一个 DHCP ACK 消息包，表示确认。DHCP ACK 内容如下：

可以注意到，所有的请求均是通过广播地址发送的。

Lab 1 Stitching Substrings Into a Byte Stream

Lab1 到 Lab4 主要实现传输层的 TCP 协议。

Lab 1 需要将不按顺序的数据转换为顺序的 Byte Steam，主要用于解决 TCP 接收乱序包的问题。这个实验选用合适的数据结构是关键。这里我使用的是 std::deque ，因为它既能够和队列一样从两端插入，删除数据，又具有和数组一样的随机访问能力。

用了两个 deque，分别是 std::deque<char> buf_ 和 std::deque<bool> bitmap_ 。buf_ 存储着 char，bitmap_ 则标记该位置是否存在 char。

注意理解 capacity，我的理解就是 capacity = unassembled bytes + output ByteStream 中未被取走的部分。

有一点要注意：如果 push_substring() 数据有一部分因为放不下被舍弃掉的话，那么及时传进来 eof 也是无效的，不过并不代表放弃整个 substring，在 capacity 容量里面的字符串还是需要保存。

Lab 2 the TCP Receiver

这一节实验一开始让我们先实现 WrappingInt32 里面 buffer index 和 tcp sequence number 之间的转换，建议开始搞之前，把负数的二进制表示，32 位无符号整形，C++ 从 long 转为 int 等等搞清楚，不然莫名其妙的溢出会让人摸不到头脑。

这里主要讲讲 unwrap() 里面的一个细节：

uint64_t unwrap(WrappingInt32 n, WrappingInt32 isn, uint64_t checkpoint) {
    WrappingInt32 c = wrap(checkpoint, isn);
    int32_t offset = n.raw_value() - c.raw_value();
    int64_t ans = checkpoint + offset;
    return ans >= 0 ? ans : ans + (1ul << 32);
}

可以看到我 ans 用的是有符号的 int64_t，那是因为 ans 可能为负数（比如 isn 为 5，然后 n 从 isn 开始绕了一圈后 seqno 是 4，那么计算出来的 offset 为 -1，而假设此时的 checkpoint 还没有更新，等于 0，使得 ans = -1），显然 buffer index 不可能为负数（因为其要求从 0 开始），所以当小于零时人为加上 $2^{32}$ 就行了。

关于写 receiver 我给几点建议，大家仅供参考：

• 关于计算 ackno 的值，大家没必要在内部维护一个 ackno 的变量。可以直接通过 stream_out().bytes_written() 进行计算，不过注意的是，记得 +1，因为 SYN 占用一个序号。如果输出流已经结束，则要再 +1，因为 FIN 也占用一个序号。
• 在 _reassembler.push_substring() 时我们需要计算 buffer index，这里我推荐使用 int64_t 来处理 buffer index，因为支持负数的话，好处理很多。比如当计算出来的 buffer index < 0 时，直接抛弃即可，这说明了传入的 seqno 小于当前的 isn。
• 注意通过 unwrap 计算而来的 buffer index 需要 -1，因为你需要去掉 SYN 占得那一个坑位。而如果当前这个 TCPSegment 正好是 SYN 包，那么则不需要 -1。可能说起来有些拗口，等你测试用例报错时就明白了。

Lab 3 the TCP Sender

这一节实验难度相比于上一节一下子提升了很多，有很多的琐碎地方。我第一次写的时候是面向测试用例编程，后面实在改不动了，拆东墙补西墙。然后直接重构，就光速 PASS 了。最好写之前自己内心就要有一个总体的方案，不然代码就会很乱。

这里我简单的介绍下思路和注意点，当然不可能把代码放出来。

我自己定义了如下变量，大家经供参考：

// 每一个 TCPSegment 发送后，就放在这里进行追踪，只有当对应的 TCPSegment 被 ack 后，才从这里移除。
std::queue<TCPSegment> segments_wait_{};
// 标记 TCP 是否建立了 SYN
bool has_SYN_ = false;
// 标记 TCP 是否已经结束
bool has_FIN_ = false;
// 最近一次接收的（最新的）ack number
uint64_t receive_ackno{0};
// 接收的 window size
uint16_t window_size_ = 0;
uint64_t bytes_in_flight_ = 0;
unsigned int consecutive_retransmissions_ = 0;
// 是否开启超时重传计时器
bool timer_running_ = false;
// 相比于上一次接收 tick()，现在已经过去了多久
size_t pass_time_ = 0;
unsigned int retransmission_timeout_ = 0;

我的代码实现如下：

uint64_t TCPSender::bytes_in_flight() const { return bytes_in_flight_; }

void TCPSender::fill_window() {
    if (has_FIN_) {
        return;
    }

    TCPSegment tcpSegment;
    if (!has_SYN_) {
        // 建立初次连接，开始三次握手
        // ....
          has_SYN_ = true;
        return;
    }

    // 注意实验说明里面的，如果接收的 window_size 为 0，那我们要把它当做 1.
    uint16_t tmp_window_size = window_size_ == 0 ? 1 : window_size_;

    if (_stream.eof() && (receive_ackno + tmp_window_size > _next_seqno)) {
        // 发送 FIN
          // ....
        has_FIN_ = true;
        return;
    }

    // 注意此处使用 while，循环发送，直到 window size 被填满或 _stream 没数据为止
    while (!_stream.buffer_empty()) {
        if (_next_seqno > receive_ackno + tmp_window_size - 1) {
            break;
        }

        size_t max_length = ...; // 根据边界计算能发送的最大 max_length
        if (max_length == 0) {
            break;
        }

        tcpSegment.payload() = _stream.read(max_length);
        // 如果发送当前的数据后，且仍有空间携带 FIN，那么直接带上 FIN。 piggyback data in FIN
        if (_stream.eof() && tcpSegment.length_in_sequence_space() < tmp_window_size) {
            // ...
        }
        send_tcp_segment(tcpSegment);
    }
}

//! \param ackno The remote receiver's ackno (acknowledgment number)
//! \param window_size The remote receiver's advertised window size
void TCPSender::ack_received(const WrappingInt32 ackno, const uint16_t window_size) {
    uint64_t abs_ack = unwrap(ackno, _isn, _next_seqno);

    if (abs_ack > _next_seqno) {
        return;
    }

    if (abs_ack >= receive_ackno) {
        receive_ackno = abs_ack;
        window_size_ = window_size;
    }

    while (!segments_wait_.empty()) {
        // 弹出 ack 确认过的 TCPSegment
        // ...

        // 重置超时重传的相关信息
        retransmission_timeout_ = _initial_retransmission_timeout;
        consecutive_retransmissions_ = 0;
        pass_time_ = 0;
    }

    if (segments_wait_.empty()) {
        timer_running_ = false;
    } else {
        timer_running_ = true;
    }
}

//! \param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void TCPSender::tick(const size_t ms_since_last_tick) {
    if (!timer_running_) {
        return;
    }

    pass_time_ += ms_since_last_tick;
    if (pass_time_ >= retransmission_timeout_ && !segments_wait_.empty()) {
        // 超时重传
          // ...
        pass_time_ = 0;

        // 此处需要考虑如果是 SYN 包的超时重传，因为 SYN 包你没有接收到过 window size，但是你仍然需要 时间x2
        if (window_size_ > 0 || tcpSegment.header().syn) {
            consecutive_retransmissions_++;
            retransmission_timeout_ *= 2;
        }
    }
}

unsigned int TCPSender::consecutive_retransmissions() const { return consecutive_retransmissions_; }

void TCPSender::send_empty_segment() {// 没写，测试用例没有测试到，等下一个实验补上}

void TCPSender::send_tcp_segment(TCPSegment &tcpSegment) {
    tcpSegment.header().seqno = wrap(_next_seqno, _isn);
    _next_seqno += tcpSegment.length_in_sequence_space();
    _segments_out.push(tcpSegment);
    segments_wait_.push(tcpSegment);
    bytes_in_flight_ += tcpSegment.length_in_sequence_space();
    if (!timer_running_) {
        timer_running_ = true;
        pass_time_ = 0;
    }
}

Lab 4 the TCP connection

Lab 4 相比之前确实很难，网上很多人说做 lab 4 时会发现自己之前写的代码有很多 bug，然后要去改之前的代码，或者修改之前代码结构。还有些人说有些测试用例是访问国外的网站，国内网络不行，所以即使出现 timeout 也就不管了。

这里我说说我的感受：

• 难度确实大，但是没有那么离谱，我做花了大约 4 天吧。
• 我就改了之前的一行 bug，并没有其他地方需要修改。
• 测试用例那个 169 开头的 IP 并不是国外的，而是它在你自己机子上面模拟的一个本地 ip，所以如果出现 timeout，并不是访问超时，而是你的 tcp 没有正常关闭，建议使用 tshark 抓包分析下。

关于代码的实现，我的操作是通过各种 if-else 操作，确定当前的状态，然后根据状态机的图，从哪切换到哪里，确定好路径。不过代码并不完美，比如我无法通过状态区分 CLOSE_WAIT 和 FIN_WAIT_2 的区别。

放出来一段 segment_received 的代码仅供参考：

void TCPConnection::segment_received(const TCPSegment &seg) {
    if (!is_active_) {
        return;
    }

    time_since_last_segment_received_ = 0;

    if (seg.header().rst) {
        immediate_shutdown(false);
        return;
    }

    // closed
    if (_sender.next_seqno_absolute() == 0) {
        // passive open
        if (seg.header().syn) {
            // todo Don't have ack no, so sender don't need ack
            _receiver.segment_received(seg);
            connect();
            log_print("closed -> syn-rcvd");
        }
        return;
    }

    // syn-sent
    if (_sender.next_seqno_absolute() == _sender.bytes_in_flight() && !_receiver.ackno().has_value()) {
        if (seg.header().syn && seg.header().ack) {
            // active open
            _sender.ack_received(seg.header().ackno, seg.header().win);
            _receiver.segment_received(seg);
            // send ack
            _sender.send_empty_segment();
            send_internet();
            // become established
            log_print("syn-sent -> established");
        } else if (seg.header().syn && !seg.header().ack) {
            // simultaneous open
            _receiver.segment_received(seg);
            // already send syn, need a ack
            _sender.send_empty_segment();
            send_internet();
            // become syn_rcvd
            log_print("syn-sent -> syn_rcvd");
        }
        return;
    }

    // syn-rcvd
    if (_receiver.ackno().has_value() && !_receiver.stream_out().input_ended() &&
        _sender.next_seqno_absolute() == _sender.bytes_in_flight()) {
        // receive ack
        // todo need ack
        _receiver.segment_received(seg);
        _sender.ack_received(seg.header().ackno, seg.header().win);
        log_print("syn-rcvd -> established");
        return;
    }

    // established, aka stream ongoing
    if (_sender.next_seqno_absolute() > _sender.bytes_in_flight() && !_sender.stream_in().eof()) {
        _sender.ack_received(seg.header().ackno, seg.header().win);
        _receiver.segment_received(seg);
        if (seg.length_in_sequence_space() > 0) {
            _sender.send_empty_segment();
        }
        _sender.fill_window();
        send_internet();
        if (seg.header().fin) {
            log_print("established -> close wait");
        }
        return;
    }

    // close wait
    if (!_sender.stream_in().eof() && _receiver.stream_out().input_ended()) {
        _sender.ack_received(seg.header().ackno, seg.header().win);
        _receiver.segment_received(seg);
        // try to send remain data
        _sender.fill_window();
        send_internet();
        log_print("close wait -> (send remain data) or (last ack)");
        return;
    }

    // FIN_WAIT_1
    if (_sender.stream_in().eof() && _sender.next_seqno_absolute() == _sender.stream_in().bytes_written() + 2 &&
        _sender.bytes_in_flight() > 0 && !_receiver.stream_out().input_ended()) {
        if (seg.header().fin && seg.header().ack) {
            _sender.ack_received(seg.header().ackno, seg.header().win);
            _receiver.segment_received(seg);
            _sender.send_empty_segment();
            send_internet();
            log_print("fin_wait_1 -> time_wait");
        } else if (seg.header().fin && !seg.header().ack) {
            _sender.ack_received(seg.header().ackno, seg.header().win);
            _receiver.segment_received(seg);
            _sender.send_empty_segment();
            send_internet();
            log_print("fin_wait_1 -> closing");
        } else if (!seg.header().fin && seg.header().ack) {
            _sender.ack_received(seg.header().ackno, seg.header().win);
            _receiver.segment_received(seg);
            send_internet();
            log_print("fin_wait_1 -> fin_wait_2");
        }

        return;
    }

    // CLOSING
    if (_sender.stream_in().eof() && _sender.next_seqno_absolute() == _sender.stream_in().bytes_written() + 2 &&
        _sender.bytes_in_flight() > 0 && _receiver.stream_out().input_ended()) {
        _sender.ack_received(seg.header().ackno, seg.header().win);
        _receiver.segment_received(seg);
        send_internet();
        log_print("closing -> time_wait");
        return;
    }

    // FIN_WAIT_2
    if (_sender.stream_in().eof() && _sender.next_seqno_absolute() == _sender.stream_in().bytes_written() + 2 &&
        _sender.bytes_in_flight() == 0 && !_receiver.stream_out().input_ended()) {
        _sender.ack_received(seg.header().ackno, seg.header().win);
        _receiver.segment_received(seg);
        _sender.send_empty_segment();
        send_internet();
        log_print("fin_wait_2 -> time_wait");
        return;
    }

    // TIME_WAIT
    if (_sender.stream_in().eof() && _sender.next_seqno_absolute() == _sender.stream_in().bytes_written() + 2 &&
        _sender.bytes_in_flight() == 0 && _receiver.stream_out().input_ended()) {
        if (seg.header().fin) {
            _sender.ack_received(seg.header().ackno, seg.header().win);
            _receiver.segment_received(seg);
            _sender.send_empty_segment();
            send_internet();
            log_print("time_wait -> time_wait (Still reply FIN)");
        }

        return;
    }
        // 有些状态没有预判到，这里统一处理下。
    _sender.ack_received(seg.header().ackno, seg.header().win);
    _receiver.segment_received(seg);
    _sender.fill_window();
    send_internet();
}

结果并不是那么完美，有一个没过，报错 Not Run。

31/162 Test  #31: t_webget .........................***Not Run   0.00 sec

反正我也是纳闷了，不知道为什么会 Not Run，但是想着 TCP 大部分都过了，那就这样算了吧，不想耗费过多的时间在这上面。

本来是想把代码贴出来的，后来想想算了，一是没有完美通关，二是感觉写的不好，有些地方也是稀里糊涂莫名其妙的过了。

八股补充

TCP

TCP Header

TCP Header 不含 IP 地址，那是 IP 层的事情。

源 IP、源端口、目标 IP、目标端口构成了 TCP 连接的「四元组」。一个四元组可以唯一标识一个连接。

常见的 flag 有：

• SYN（Synchronize）：用于发起连接数据包同步双方的初始序列号
• ACK（Acknowledge）：确认数据包
• RST（Reset）：这个标记用来强制断开连接，通常是之前建立的连接已经不在了、包不合法、或者实在无能为力处理
• FIN（Finish）：通知对方我发完了所有数据，准备断开连接，后面我不会再发数据包给你了。
• PSH（Push）：告知对方这些数据包收到以后应该马上交给上层应用，不能缓存起来

MTU，MSS

MTU 在 IP 层，其能携带的最大容量是 1500 bytes。下图为一个 frame 的结构。

MSS 为 TCP 最大分片大小：

MSS = MTU – IP header头大小 – TCP 头大小。这样一个 MSS 能够正好装进 MTU，使得 IP 层不需要分片。
MSS = 1500 – 20 -20 = 1460。

状态机

• 被动关闭方收到 FIN 时进入 CLOSE_WAIT 状态，此时其需要将自己缓冲区里面所有的数据发出去，发完后调用 Close 并发送 FIN，同时进入 LAST_ACK 状态，等待对方回复自己的 FIN。如果收到 ACK 就立刻关闭。
• CLOSING 出现在 TCP 同时关闭的情况下，双方同时收到对方的 FIN 包。

TIME-WAIT 2MSL的意义

MSL（Maximum Segment Lifetime），它是任何报文段被丢弃前在网络内的最长时间，建议一个 MSL 为 2 分钟。一来一回要乘以二。

这么设计为了解决如下两个原因：

1. 当我发送ACK回复对方的FIN时，这个ACK可能丢了。对方会重发FIN，如果我自己直接关了，那就回复不了了。对方就会一直处于LAST-ACK状态。重发ACK用以回复FIN后要重置计时器。
2. 使本连接持续的时间内所产生的所有报文段都从网络中消失，使下一个新的连接中不会出现这种旧的连接请求报文段。

这种2MSL等待的另一个结果是这个TCP连接在2MSL等待期间，该连接接口（客户的IP地址和端口号，服务器的IP地址和端口号）不能再被使用。这个连接只能在2MSL结束后才能再被使用。

可以通过地址重用来解决，SO_REUSEADDR 参数。

快速重传

当发送端收到 3 个或以上重复 ACK，说明之前发的包可能丢了，马上进行重传，不用等到超时再重传。

Nagle 算法

Nagle 算法要求，当一个 TCP 连接中有在传数据（已经发出但还未确认的数据）时，小于 MSS 的报文段就不能被发送，直到所有的在传数据都收到了 ACK。同时收到 ACK 后，TCP 还不会马上就发送数据，会收集小包合并一起发送。这也是会产生粘包的一个原因。

UDP

UDP Header

ICMP

ICMP 基于 IP 协议传输，但是他不和传输层一样可以用于传输数据。我觉得它处于链路层和传输层之间。

ICMP 报文有很多的类型，不同的类型有不同的代码。主要分为主动探查的查询报文和异常报告的差错报文。

PING 是 ICMP 主动查询报文。

差错报文是数据在路途中出问题，人家返回来的 ICMP。比如你 TTL 为 0 时，人家就会回你一个信息（Traceroute 就是采用这种方式）。

Lab 5 the network interface

Lab 5 实现的是链路层的东西。链路层的通讯是根据 MAC 地址进行通讯，与 IP 无关，交换机会通过 frame 头上的 MAC 地址，将 frame 转发到对应的机器上。当一个主机发送 frame 时，如果只知道对方的 IP 地址，则先需要发送 ARP 请求到广播地址，然后获取到目标机器的 MAC 地址，并将其放入自己的缓存表里，之后发送消息时就可以在 frame header 带上 MAC 地址了。

NetworkInterface 模拟的是一台机器 frame 的收发。

send_datagram

1. 检查本机是否缓存了目标 IP 的 ARP，如果不存在或者 ARP 信息过期，将该请求放到等待队列里面，并发送 ARP 请求。当 ARP 请求收到回复后，再将等待队列里面的信息发出。
2. 否则在 header 里面添加目标的 MAC 地址直接发送即可。

recv_frame

负责接收来自网络的 frame。

1. 如果 frame 目标 MAC 不是本机 MAC，直接忽略。但是你不能忽略 dst 为广播 MAC 的 frame，因为那个可能是 ARP 请求。
2. 如果是 IPv4 协议，解析后返回给上层应用。
3. 如果是 ARP 协议，则根据是 OPCODE_REQUEST 还是 OPCODE_REPLY 做出相应的处理即可。

注意点：

• 发送 IP 报文时，如果当前没有目标主机的 ARP 信息，那么先发送 ARP 请求，得到 ARP 回复后，再把该 IP 报文发送（这意味着你不能丢弃 IP 报文，需要拿一个 queue 存储）。
• 发送 ARP Request 时，frame 的 dst 是广播 mac 地址，但是 ARPMessage 里面的 target_ethernet_address 应该为空。target_ethernet_address 只用于 ARP Reply。
• ARP 请求 5s 内不能重复发送，可以用一个 map 记录下上一次发送时间。

Lab 6

Lab 6 是实现一个路由转发，比较简单。

自己创建一个结构体 Table 和 std::vector<Table> route_table_{} 用于保存 add_route() 加进来的路由。

转发路由时采用最长匹配规则。匹配方法基于 prefix_length 生成一个 mask（mask 就是我们常说的子网掩码），然后通过 (dst & mask) == route_prefix 运算进行匹配即可。Mask 的生成方式通过 0xFFFFFFFF 位移得到，mask = 0xFFFFFFFF << (32-prefix_length)。

注意存在 prefix_length 为 0 的情况，此时会位移 32 位，超出 int 最大的合法范围，这里建议做个单独处理，令 prefix_length 为 0 的 mask 为 0 即可。

最后转发时注意判断 next_hop 是否存在值。如果存在值代表是发到下一个路由，不存在值时发送到 direct 连接的设备上，代码如下：

if (route_table_[target_interface].next_hop_.has_value()) {
  interface(target_interface).send_datagram(dgram, route_table_[target_interface].next_hop_.value());
} else {
  interface(target_interface).send_datagram(dgram, Address::from_ipv4_numeric(dgram.header().dst));
}

别忘 TTL – 1。

Lab 7

把玩自己的玩具，但是我的 client 和 server 一直连不上。看了下 cs144.keithw.org 这个域名是架在 Google 上的，猜测是被墙了无法通讯，便作罢了。

总结

自此，将手上所有堆积网课全部完结，在这半年的时间里完成了：

1. MIT 6.824
2. MIT 6.s081
3. Talent Plan TinyKV
4. CMU 15-445
5. CS144

平均下来差不多是一个月一门课，有空可以去刷一下 vldb-2021-labs 和 tinysql ，不过目测没时间了，要找工作和写毕业论文了。