这个 Lab6 就更 easy 啦

Lab6 介绍

在这个实验中，我们将完成一个简易路由器，其功能是：对于给定的数据包，确认发送接口以及下一跳的 IP 地址。为了简化实验难度，该实验中无需处理任何复杂路由协议，实验代码推荐只需 25-30 行。

这个 Lab 不需要依赖之前 Lab0-4 实现的 TCP 协议，只需要实现两个接口。

添加一条路由规则

void add_route(const uint32_t route_prefix,
               const uint8_t prefix_length,
               const optional<Address> next_hop,
               const size_t interface_num);

很简单，直接存入路由表即可。路由表使用 std::vector 存储上面的所有内容。

文档中说了，对于每一个数据报，路由的时间复杂度是 $\mathcal O(N)$ 是完全可以接受的。

⚠ 注意：如果路由器直接连接到当前网络上，那么下一跳（next_hop）将是一个空的可选项（empty optional）。在这种情况下，下一跳就是数据报的目标地址。但是，如果路由器是通过其他路由器连接到当前网络的，那么下一跳将包含沿路径的下一个路由器的 IP 地址。interface num 给出了路由器的 NetworkInterface 的索引，用于将数据报发送到下一跳。可以使用 interface(interface num)方法访问此接口。

路由一个数据报

void route_one_datagram(InternetDatagram &dgram);

在互联网的设计中存在一种美感（或者至少是成功的抽象）：路由器从不考虑 TCP、ARP 或以太网帧。路由器甚至不知道链路层的样子。路由器只考虑互联网数据报，并且只通过 NetworkInterface 抽象与链路层进行交互。当涉及到问题，比如“链路层地址是如何解析的？”或者“链路层是否具有与IP不同的自己的寻址方案？”或者“链路层帧的格式是什么？”或者“数据报的有效负载的含义是什么？”时，路由器根本不关心。

路由仅需要知道目的 IP 地址和路由表，通过最长前缀匹配（longest-prefix match）来决定下一跳的 NetworkInterface。

路由规则的前缀长度可以是闭区间的 [0, 32] 之间，路由其会搜寻路由表的所有规则，在所有匹配规则中选择前缀最长的那一条。

然后令数据报的 TTL 减 1，然后把数据报送到下一跳。如果数据报的 TTL <= 1 则直接丢弃。和之前一样，我们同样不需要在丢弃报文后发回 ICMP 报文，因为即使是在真实网络世界，也不是每一个 router 都会在丢弃数据报后发回 ICMP 报文。

代码实现

右移位的坑点

在代码实现的时候注意一个右移位的坑点：根据 CSAPP，在 32 位整数下，右移量只取低 5 位（即 mod 32），因此右移 32 位等价于右移 0 位，在路由匹配时需要特判右移 32 位的情况

下面是在 Debug 过程中的实验测试记录，

以上代码在最新版本的 g++ 13.2.0 编译器上的结果，可以发现右移 32 位并不会让原数变为 0。

router.hh

#ifndef SPONGE_LIBSPONGE_ROUTER_HH
#define SPONGE_LIBSPONGE_ROUTER_HH

#include "network_interface.hh"
#include "address.hh"


#include <cstdint>
#include <optional>
#include <queue>
#include <vector>

//! \brief A wrapper for NetworkInterface that makes the host-side
//! interface asynchronous: instead of returning received datagrams
//! immediately (from the `recv_frame` method), it stores them for
//! later retrieval. Otherwise, behaves identically to the underlying
//! implementation of NetworkInterface.
class AsyncNetworkInterface : public NetworkInterface {
    std::queue<InternetDatagram> _datagrams_out{};

  public:
    using NetworkInterface::NetworkInterface;

    //! Construct from a NetworkInterface
    AsyncNetworkInterface(NetworkInterface &&interface) : NetworkInterface(interface) {}

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

    //! - If type is IPv4, pushes to the `datagrams_out` queue for later retrieval by the owner.
    //! - 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 "target" fields.
    //!
    //! \param[in] frame the incoming Ethernet frame
    void recv_frame(const EthernetFrame &frame) {
        auto optional_dgram = NetworkInterface::recv_frame(frame);
        if (optional_dgram.has_value()) {
            _datagrams_out.push(std::move(optional_dgram.value()));
        }
    };

    //! Access queue of Internet datagrams that have been received
    std::queue<InternetDatagram> &datagrams_out() { return _datagrams_out; }
};

//! \brief A router that has multiple network interfaces and
//! performs longest-prefix-match routing between them.
class Router {
    //! The router's collection of network interfaces
    std::vector<AsyncNetworkInterface> _interfaces{};

    //! 路由表条目
    struct RouteEntry {
        uint32_t route_prefix;
        uint8_t prefix_length;
        std::optional<Address> next_hop;
        size_t interface_num;

        RouteEntry() = default;
        RouteEntry(const uint32_t _route_prefix, const uint8_t _prefix_length, \
        const std::optional<Address> &_next_hop, const size_t _interface_num) :
            route_prefix(_route_prefix),
            prefix_length(_prefix_length),
            next_hop(_next_hop),
            interface_num(_interface_num)
            {}
    };

    //! 路由表
    std::vector<RouteEntry> _route_table{};

    //! Send a single datagram from the appropriate outbound interface to the next hop,
    //! as specified by the route with the longest prefix_length that matches the
    //! datagram's destination address.
    void route_one_datagram(InternetDatagram &dgram);

  public:
    //! Add an interface to the router
    //! \param[in] interface an already-constructed network interface
    //! \returns The index of the interface after it has been added to the router
    size_t add_interface(AsyncNetworkInterface &&interface) {
        _interfaces.push_back(std::move(interface));
        return _interfaces.size() - 1;
    }

    //! Access an interface by index
    AsyncNetworkInterface &interface(const size_t N) { return _interfaces.at(N); }

    //! Add a route (a forwarding rule)
    void add_route(const uint32_t route_prefix,
                   const uint8_t prefix_length,
                   const std::optional<Address> next_hop,
                   const size_t interface_num);

    //! Route packets between the interfaces
    void route();
};

#endif  // SPONGE_LIBSPONGE_ROUTER_HH

router.cc

#include "router.hh"

#include <iostream>

using namespace std;

// Dummy implementation of an IP router

// Given an incoming Internet datagram, the router decides
// (1) which interface to send it out on, and
// (2) what next hop address to send it to.

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

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

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

//! \param[in] route_prefix The "up-to-32-bit" IPv4 address prefix to match the datagram's destination address against
//! \param[in] prefix_length For this route to be applicable, how many high-order (most-significant) bits of the route_prefix will need to match the corresponding bits of the datagram's destination address?
//! \param[in] next_hop The IP address of the next hop. Will be empty if the network is directly attached to the router (in which case, the next hop address should be the datagram's final destination).
//! \param[in] interface_num The index of the interface to send the datagram out on.
void Router::add_route(const uint32_t route_prefix,
                       const uint8_t prefix_length,
                       const optional<Address> next_hop,
                       const size_t interface_num) {
    cerr << "DEBUG: adding route " << Address::from_ipv4_numeric(route_prefix).ip() << "/" << int(prefix_length)
         << " => " << (next_hop.has_value() ? next_hop->ip() : "(direct)") << " on interface " << interface_num << "\n";

    // Your code here.
    _route_table.emplace_back(route_prefix, prefix_length, next_hop, interface_num);
}

//! \param[in] dgram The datagram to be routed
void Router::route_one_datagram(InternetDatagram &dgram) {
    // Your code here.
    // 取出 IP 字段，在路由表中进行最长前缀匹配
    auto ip = dgram.header().dst;
    auto best_match_it = _route_table.end();
    for (auto it = _route_table.begin(); it != _route_table.end(); it = std::next(it)) {
        // 前缀匹配成功
        //! NOTE: 根据 CSAPP，在 32 位整数下，右移量只取低 5 位（即 mod 32），因此右移 32 位等价于右移 0 位，因此这里需要特判右移 32 位的情况 
        // cerr << "DEBUG route table: " << ((it->route_prefix ^ ip) >> (32 - it->prefix_length)) << '\n';
        if (it->prefix_length == 0 ||  (it->route_prefix ^ ip) >> (32 - it->prefix_length) == 0) {
            if (best_match_it == _route_table.end() || it->prefix_length > best_match_it->prefix_length) {
                best_match_it = it;
            }
        }
    }
    // 匹配到路由规则并且 TTL 大于 1
    if (best_match_it != _route_table.end() && dgram.header().ttl > 1) {
        --dgram.header().ttl;
        auto &next_interface = interface(best_match_it->interface_num);
        // 如果路由器直接连接到相关网络，则下一跳就是目的 IP 地址，否则为下一跳路由器的 IP 地址
        if (best_match_it->next_hop.has_value()) {
            next_interface.send_datagram(dgram, best_match_it->next_hop.value());
        } else {
            next_interface.send_datagram(dgram, Address::from_ipv4_numeric(ip));
        }
    }
    // 其余情况数据报则直接丢弃，也不作 ICMP 回复
}

void Router::route() {
    // Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
    for (auto &interface : _interfaces) {
        auto &queue = interface.datagrams_out();
        while (not queue.empty()) {
            route_one_datagram(queue.front());
            queue.pop();
        }
    }
}

测试

下面是测试时使用的网络拓扑结构图，

Lab6 单独测试结果如下，

ohhhhh，通过所有测试用例啦 🎉。

References

CS144 计算机网络 Lab6