这个 Lab 相比前面的 Lab4 就要简单很多啦

Lab5 介绍

Lab5 的任务是实现网络接口 Network Interface（也被称为适配器），具体来说，就是实现 ARP 协议。

下面是官方的解释图，一张图概况了 7 个 Lab 的是做了什么工作。这个 Network Interface 就是用于负责网络层和数据链路层之间的数据交换。

TCP 报文的数据传输方式

TCP报文有三种方式可被传送至远程服务器，分别是：

• TCP-in-UDP-in-IP：用户应用提供 TCP 包，之后可以使用 Linux 提供的接口，让内核来负责构造 UDP 报头、IP 报头以及以太网报头，并将构造出的数据包发送至下一个层。因为这一切都是内核完成的任务，因此内核可以确保每个套接字都具有本地地址与端口，以及远程地址与端口的唯一组合，同时能保证不同进程之前的隔离。

• TCP-in-IP：通常，TCP 数据包是直接放进 IP 包作为其 payload，这也因此被称为 TCP/IP。但用户层如果想直接操作构造 IP 报文的话，需要使用到 Linux 提供的 TUN 虚拟网络设备来作为中转。当用户将 IP 报文发送给 TUN 设备后，剩余的以太网报头构造、发送以太网帧等等的操作均会由内核自动进行，无需用户干预。

  这一个正是之前 Lab4 中 CS144 所使用的机制，感兴趣可以仔细读读代码，目前我也不太明白。

• TCP-in-IP-in-Ethernet：上面两种方式仍然依赖 Linux 内核来实现的协议栈操作。每次用户向 TUN 设备写入 IP 数据报时，Linux 内核都必须构造一个适当的链路层（以太网）帧，并将 IP 数据报作为其 payload。因此 Linux 必须找出下一跳的以太网目的地址，给出下一跳的 IP 地址。如果 Linux 无法得知该映射关系，则将会发出广播探测请求以查找到下一跳的地址等信息。而这种功能是由网络接口 network interface （也被称为适配器，两者等价）所实现，它将会把待出口的 IP 报文转换成链路层（以太网）帧或者反之亦然，之后将链路层帧发送给 TAP 虚拟网络设备，剩下的发送操作将会由它来代为完成。
  

  比较熟悉的网络接口分别是 eth0, eth1, whan0 等等。

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

在本实验中，我们将会完成一个这样的网络接口实现。

地址解析协议 ARP

在编写代码前，我们需要简单的了解一下 ARP 协议。

主机或路由器不具有链路层地址，而是它们的适配器（即网络接口）具有链路层地址。链路层地址通常称为 MAC 地址。当某个适配器要向某些目的适配器发送一个帧时，发送适配器将目的适配器的 MAC 地址插入至该帧中，并将该帧发送到局域网上。一块适配器可能因为广播操作，接收到了一个并非向它寻址的帧，因此当适配器接收到一个帧时，将检查并丢弃帧的目的MAC地址不与自己MAC地址匹配的以太网帧。

为什么适配器除了有网络层地址（IP地址）以外，还会有链路层地址（MAC地址）呢？有两个原因：

• 局域网是为了任意网络层协议而设计，并非只用于 IP 和因特网。
• 如果适配器使用 IP地址而不使用 MAC 地址，那么每次适配器移动或重启时，均需重新配置地址。

由于适配器同时拥有网络层和链路层地址，因此需要相互转化。而这种转换的任务就由 地址解析协议 来完成。ARP 类似于 DNS 服务，但不同的是，DNS 为任何地方的主机来解析主机名，但 ARP 只能为在同一个子网上的主机和路由器接口解析 IP 地址。

每台主机或路由器在其内存中保存了一张 ARP 表，该表包含了 IP 地址到 MAC 地址的映射关系，同时还包含了一个寿命值（TTL），用以表示从表中删除每个映射的时间，例如：

若 ARP 表中已经存放了目标 IP 地址的 MAC 地址映射，那么适配器将会很容易的找出目标 MAC 地址并构造一个以太网帧。但如果找不到，那么发送方将会构造一个 ARP 分组的特殊分组。

ARP 分组中的字段包括发送和接收 IP 地址以及 MAC 地址，同时 ARP 查询分组和响应分组都具有相同的格式。ARP 查询分组的目的是询问子网上所有其他主机和路由器，以确定对应于要解析的 IP 地址的那个 MAC 地址。

当发送适配器需要查询目的适配器的 MAC 地址时，发送适配器会设置分组的目的地址为 MAC 广播地址（FF-FF-FF-FF-FF-FF），这样做的目的是为了让所有子网上的其他适配器都接收到。当其他适配器接收到了该 ARP 查询分组后，只有 IP 匹配的适配器才会返回一个 ARP 响应分组，之后发送适配器便可更新自己的 ARP 表，并开始发送 IP 报文。

查询ARP报文是在广播帧中发送，而响应ARP报文只在一个标准帧中发送。同时 ARP 表是自动建立的，无需人为设置。若主机与子网断开连接，那么该节点留在其他节点的 ARP 表中对应的条目也会被自动删除。

与之相对的，ARP欺骗攻击可以利用 ARP 协议不提供对网络上的 ARP 回复进行身份验证 这样的一个缺陷，来轻易执行中间人攻击或者 DOS 攻击。

其他详细信息可以看看 RFC826 规范。

以太网帧结构

在本实验中，发送的以太网帧是 Ethernet Type Ⅱ Frame，它的 header 为 14 字节。

其中当 EtherType 为 0x800 时，表示这是 IPv4 数据报；为 0x806 时，表示这是 ARP 数据报。

代码实现

在本实验中 ARP 条目默认过期时间为 30s，ARP 请求相应默认等待时间为 5s

在本实验中，为了简单起见，如果 ARP 请求超时（超过 5s 没有回复），不需要重发甚至发回一个 “host unreachable” 的 ICMP 报文。

具体实现思路见代码注释，还是写得比较详细了

network_interface.hh

#ifndef SPONGE_LIBSPONGE_NETWORK_INTERFACE_HH
#define SPONGE_LIBSPONGE_NETWORK_INTERFACE_HH

#include "address.hh"
#include "ethernet_frame.hh"
#include "ethernet_header.hh"
#include "tcp_over_ip.hh"
#include "tun.hh"

#include <cstddef>
#include <cstdint>
#include <list>
#include <optional>
#include <queue>
#include <unordered_map>

//! brief A "network interface" that connects IP (the internet layer, or network layer)
//! with Ethernet (the network access layer, or link layer).

//! This module is the lowest layer of a TCP/IP stack
//! (connecting IP with the lower-layer network protocol,
//! e.g. Ethernet). But the same module is also used repeatedly
//! as part of a router: a router generally has many network
//! interfaces, and the router's job is to route Internet datagrams
//! between the different interfaces.

//! The network interface translates datagrams (coming from the
//! "customer," e.g. a TCP/IP stack or router) into Ethernet
//! frames. To fill in the Ethernet destination address, it looks up
//! the Ethernet address of the next IP hop of each datagram, making
//! requests with the [Address Resolution Protocol](ref rfc::rfc826).
//! In the opposite direction, the network interface accepts Ethernet
//! frames, checks if they are intended for it, and if so, processes
//! the the payload depending on its type. If it's an IPv4 datagram,
//! the network interface passes it up the stack. If it's an ARP
//! request or reply, the network interface processes the frame
//! and learns or replies as necessary.
class NetworkInterface {
  private:
    //! ARP 条目
    struct ARPEntry {
      EthernetAddress eth_addr;
      size_t ttl;
    };

    //! Ethernet (known as hardware, network-access-layer, or link-layer) address of the interface
    EthernetAddress _ethernet_address;

    //! IP (known as internet-layer or network-layer) address of the interface
    Address _ip_address;

    //! outbound queue of Ethernet frames that the NetworkInterface wants sent
    std::queue<EthernetFrame> _frames_out{};

    //! ARP 表
    std::unordered_map<uint32_t, ARPEntry> _arp_table{};

    //! 正在查询的 ARP 报文。如果发送了 ARP 请求后，在过期时间内没有返回响应，则丢弃等待的 IP 报文
    std::unordered_map<uint32_t, size_t> _waiting_arp_response_ip_addr{};

    //! 等待 ARP 报文返回的待处理 IP 报文，每一个 IP 地址映射到一个 IP 报文等待发送列表
    std::unordered_map<uint32_t, std::list<std::pair<Address, InternetDatagram> > > _waiting_internet_datagrams{};

    //! brief 发送以太网帧
    void _send(const EthernetAddress &dst, const uint16_t type, BufferList &&payload);

  public:
    //! ARP 条目默认过期时间为 30s
    static constexpr uint32_t ARP_ENTRY_TTL_MS = 30 * 1000;

    //! ARP 请求相应默认等待时间为 5s
    static constexpr uint32_t ARP_RESPONSE_TTL_MS = 5 * 1000; 

    //! brief Construct a network interface with given Ethernet (network-access-layer) and IP (internet-layer) addresses
    NetworkInterface(const EthernetAddress ðernet_address, const Address &ip_address);

    //! brief Access queue of Ethernet frames awaiting transmission
    std::queue<EthernetFrame> &frames_out() { return _frames_out; }

    //! brief Sends an IPv4 datagram, encapsulated in an Ethernet frame (if it knows the Ethernet destination address).

    //! Will need to use [ARP](ref rfc::rfc826) to look up the Ethernet destination address for the next hop
    //! ("Sending" is accomplished by pushing the frame onto the frames_out queue.)
    void send_datagram(const InternetDatagram &dgram, const Address &next_hop);

    //! brief Receives an Ethernet frame and responds appropriately.

    //! If type is IPv4, returns the datagram.
    //! If type is ARP request, learn a mapping from the "sender" fields, and send an ARP reply.
    //! If type is ARP reply, learn a mapping from the "sender" fields.
    std::optional<InternetDatagram> recv_frame(const EthernetFrame &frame);

    //! brief Called periodically when time elapses
    void tick(const size_t ms_since_last_tick);
};

#endif  // SPONGE_LIBSPONGE_NETWORK_INTERFACE_HH

network_interface.cc

#include "network_interface.hh"

#include "arp_message.hh"
#include "ethernet_frame.hh"

#include <iostream>

// Dummy implementation of a network interface
// Translates from {IP datagram, next hop address} to link-layer frame, and from link-layer frame to IP datagram

// For Lab 5, please replace with a real implementation that passes the
// automated checks run by `make check_lab5`.

// You will need to add private members to the class declaration in `network_interface.hh`

template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {}

using namespace std;

//! param[in] ethernet_address Ethernet (what ARP calls "hardware") address of the interface
//! param[in] ip_address IP (what ARP calls "protocol") address of the interface
NetworkInterface::NetworkInterface(const EthernetAddress ðernet_address, const Address &ip_address)
    : _ethernet_address(ethernet_address), _ip_address(ip_address) {
    cerr << "DEBUG: Network interface has Ethernet address " << to_string(_ethernet_address) << " and IP address "
         << ip_address.ip() << "n";
}

void NetworkInterface::_send(const EthernetAddress &dst, const uint16_t type, BufferList &&payload) {
    EthernetFrame eth_frame;
    eth_frame.header().src = _ethernet_address;
    eth_frame.header().dst = dst;
    eth_frame.header().type = type;
    eth_frame.payload() = std::move(payload);
    _frames_out.push(std::move(eth_frame));
}

//! param[in] dgram the IPv4 datagram to be sent
//! param[in] next_hop the IP address of the interface to send it to (typically a router or default gateway, but may also be another host if directly connected to the same network as the destination)
//! (Note: the Address type can be converted to a uint32_t (raw 32-bit IP address) with the Address::ipv4_numeric() method.)
void NetworkInterface::send_datagram(const InternetDatagram &dgram, const Address &next_hop) {
    // convert IP address of next hop to raw 32-bit representation (used in ARP header)
    const uint32_t next_hop_ip = next_hop.ipv4_numeric();

    auto it = _arp_table.find(next_hop_ip);
    if (it != _arp_table.end()) {
        // ARP 表命中，则直接发送 IP 数据报
        _send(it->second.eth_addr, EthernetHeader::TYPE_IPv4, dgram.serialize());
    } else {
        // ARP 表不命中，且最近没有对该 IP 发送过 ARP 查询数据报，则发送查询报文
        if (_waiting_arp_response_ip_addr.find(next_hop_ip) == _waiting_arp_response_ip_addr.end()) {
            ARPMessage arp_msg;
            arp_msg.opcode = ARPMessage::OPCODE_REQUEST;
            arp_msg.sender_ethernet_address = _ethernet_address;
            arp_msg.target_ethernet_address = {};
            arp_msg.sender_ip_address = _ip_address.ipv4_numeric();
            arp_msg.target_ip_address = next_hop_ip;

            _send(ETHERNET_BROADCAST, EthernetHeader::TYPE_ARP, arp_msg.serialize());

            // 加入等待回复 ARP 报文的记录表中
            _waiting_arp_response_ip_addr[next_hop_ip] = ARP_RESPONSE_TTL_MS;
        }
        // 加入 IP 报文等待发送列表
        _waiting_internet_datagrams[next_hop_ip].emplace_back(next_hop, dgram);
    }

}

//! param[in] frame the incoming Ethernet frame
optional<InternetDatagram> NetworkInterface::recv_frame(const EthernetFrame &frame) {
    // 如果不是广播帧或者 MAC 地址不是本机，则直接过滤
    if (frame.header().dst != ETHERNET_BROADCAST && frame.header().dst != _ethernet_address) {
        return nullopt;
    }
    // 如果是 IPv4 数据报，则把解析后把数据返回
    if (frame.header().type == EthernetHeader::TYPE_IPv4) {
        InternetDatagram ret;
        // 解析成功则返回
        if (ret.parse(frame.payload()) == ParseResult::NoError) return ret;
        return nullopt;
    }
    // 如果是 ARP 数据报，则尝试从中学习到 IP-MAC 映射关系（我们可以同时从 ARP 请求和响应包中获取到新的 ARP 表项）
    if (frame.header().type == EthernetHeader::TYPE_ARP) {
        ARPMessage arp_msg;
        if (arp_msg.parse(frame.payload()) != ParseResult::NoError) return nullopt;

        const uint32_t my_ip = _ip_address.ipv4_numeric();
        const uint32_t src_ip = arp_msg.sender_ip_address;
        // 如果是发给本机的 ARP 请求
        if (arp_msg.opcode == ARPMessage::OPCODE_REQUEST && arp_msg.target_ip_address == my_ip) {
            ARPMessage arp_reply;

            arp_reply.opcode = ARPMessage::OPCODE_REPLY;
            arp_reply.sender_ethernet_address = _ethernet_address;
            arp_reply.target_ethernet_address = arp_msg.sender_ethernet_address;
            arp_reply.sender_ip_address = my_ip;
            arp_reply.target_ip_address = src_ip;

            _send(arp_msg.sender_ethernet_address, EthernetHeader::TYPE_ARP, arp_reply.serialize());
        }
        // 从 ARP 报文中学习新的 ARP 表项（即使不是发给我的也可以学，比如广播但目标 IP 不是本机）
        _arp_table[src_ip] = {arp_msg.sender_ethernet_address,  ARP_ENTRY_TTL_MS};

        // 如果该 IP 地址有等待发送的数据报，则全部发送出去
        auto it = _waiting_internet_datagrams.find(src_ip);
        if (it != _waiting_internet_datagrams.end()) {
            for (const auto &[next_hop, dgram] : it->second) {
                // send_datagram(dgram, next_hop);
                _send(arp_msg.sender_ethernet_address, EthernetHeader::TYPE_IPv4, dgram.serialize());
            }
            _waiting_internet_datagrams.erase(it);
        }
    }
    return nullopt;
}

//! param[in] ms_since_last_tick the number of milliseconds since the last call to this method
void NetworkInterface::tick(const size_t ms_since_last_tick) {
    // 删除 ARP 表中过期条目
    for (auto it = _arp_table.begin(); it != _arp_table.end(); ) {
        if (it->second.ttl <= ms_since_last_tick) {
            it = _arp_table.erase(it);
        } else {
            it->second.ttl -= ms_since_last_tick;
            it = std::next(it);
        }
    }
    // 删除等待 ARP 报文回复超时的记录，不作重发处理
    for (auto it = _waiting_arp_response_ip_addr.begin(); it != _waiting_arp_response_ip_addr.end(); ) {
        if (it->second <= ms_since_last_tick) {
            // 如果还有等待发往该未回复的 IP 地址的数据报，则直接丢弃
            auto it2 = _waiting_internet_datagrams.find(it->first);
            if (it2 != _waiting_internet_datagrams.end())
                _waiting_internet_datagrams.erase(it2);

            it = _waiting_arp_response_ip_addr.erase(it);
        } else {
            it->second -= ms_since_last_tick;
            it = std::next(it);
        }
    }
}

测试

webget.cc 需要将 CS144TCPSocket 替换成 FullStackSocket，然后依然能正常运行

仅测试 webget 和 ARP 协议，

完整测试 make check，由于 router_test 肯定是没有实现的，应该是下一个 Lab 的任务，其它的测试都通过啦

References

CS144 计算机网络 Lab5

RFC 826 —— An Ethernet Address Resolution Protocol

Ethernet frame