CS144 Lab Checkpoint 6: building an IP router

Overview

在上次实验实现的网络接口上实现IP路由器。路由器有多个网络接口，可以在其中任何一个接口上接收 Internet 数据报。路由器的工作是根据路由表转发它收到的数据报：对于任何给定的数据报，路由表都是告诉路由器的规则列表。

需要实现的基本功能：

• 发送的网络接口；
• 下一跳的IP地址。

您的路由器实现将使用带有新 Router 类的 Minnow 库，并进行测试以检查路由器在模拟网络中的功能。检查点 6 建立在您从检查点 5 实现的 NetworkInterface 的基础上，但不使用您之前实现的 TCP堆栈。IP 路由器不必了解任何有关 TCP、ARP或以太网（仅 IP）的信息。

Implenting the Router

Router 类：

跟踪路由表（转发规则或路由的列表），并且
转发收到的每个数据报：

• 到正确的下一跳
• 在正确的传出网络接口上。

void add_route(uint32_t route_prefix, uint8_t prefix_length, optional next_hop, size_t interface_num);

函数功能：

• 此方法将路由添加到路由表。您需要在 Router 类中添加一个数据结构作为私有成员来存储此信息。此方法需要做的就是保存路由以供以后使用。

void route();

此方法需要将每个传入的数据报路由到下一跳，通过适当的接口。它需要实现 IP 路由器的“最长前缀匹配”逻辑，以找到最佳路由。这意味着：

• 路由器搜索路由表以查找与数据报的目标地址匹配的路由。“匹配”是指目标地址的最高有效前缀长度位与路由前缀的最高有效前缀长度位相同。
• 在匹配的路由中，路由器选择前缀长度值最大的路由。这是最长前缀匹配路由。
• 如果没有匹配的路由，路由器将丢弃数据报。
• 路由器减少数据报的 TTL（生存时间）。如果 TTL 已经为零，或者在减少后达到零，则路由器应丢弃数据报。
• 否则，路由器将修改后的数据报通过适当的接口( interface(interface num)->send datagram() ) 发送到适当的下一跳。

为了实现最大前缀匹配，我用智能指针维护了一个前缀树（Trie），其基本原理网上教程很多，大概做法就是用0，1表示这一位的两个子节点，然后查找的时候，不断更新前缀匹配的路由项，最后匹配到的就是最大前缀匹配。值得注意的是，假如用原始指针，又不去析构的话，是会报内存泄漏警告（cmake规定警告都变为error）。

class Router
{
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( std::shared_ptr<NetworkInterface> interface )
  {
    _interfaces.push_back( notnull( "add_interface", std::move( interface ) ) );
    return _interfaces.size() - 1;
  }

  // Access an interface by index
  std::shared_ptr<NetworkInterface> interface( const size_t N ) { return _interfaces.at( N ); }

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

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

private:
  // The router's collection of network interfaces
  std::vector<std::shared_ptr<NetworkInterface>> _interfaces {};
  
  class RouteEntry {
    public:
        uint32_t route_prefix;
        uint8_t prefix_length;
        optional<Address> next_hop;
        size_t interface_num;
    
        RouteEntry(uint32_t route_prefix_param, uint8_t prefix_length_param, optional<Address> next_hop_param, size_t interface_num_param)
            : route_prefix(route_prefix_param),
              prefix_length(prefix_length_param),
              next_hop(next_hop_param),
              interface_num(interface_num_param) {}
  };


  class TrieNode {
    public:
        array<unique_ptr<TrieNode>, 2> children;  // 左、右子节点
        optional<RouteEntry> route = nullopt;     // 存储路由信息
    
        TrieNode() : children{} {}  // 初始化 children
    };
    
    // Trie 树的根节点
    unique_ptr<TrieNode> root = nullptr;
    
    // 插入路由信息
    void insert_route(uint32_t route_prefix, uint8_t prefix_length,
                      optional<Address> next_hop, size_t interface_num) {
        // 初始化根节点
        if (!root) {
            root = make_unique<TrieNode>();
        }
    
        TrieNode *node = root.get();
        uint32_t mask = 0x80000000;  // 从最高位开始
    
        for (int i = 0; i < prefix_length; ++i) {
            bool bit = (route_prefix & (mask >> i)) != 0;
            if (!node->children[bit]) {
                node->children[bit] = make_unique<TrieNode>();
            }
            node = node->children[bit].get();
        }
    
        // 在叶子节点存储路由信息
        node->route = RouteEntry(route_prefix, prefix_length, next_hop, interface_num);

        std::cerr << "[DEBUG] Inserted route: "
              << Address::from_ipv4_numeric(route_prefix).ip() << "/"
              << static_cast<int>(prefix_length)
              << " -> " << (next_hop ? next_hop->ip() : "DIRECT")
              << " (interface " << interface_num << ")" << std::endl;
    }
    
    // 查找目标 IP 地址的最佳匹配路由
      optional<RouteEntry> lookup(uint32_t destination) {
      if (!root) return nullopt;
  
      TrieNode *node = root.get();
      optional<RouteEntry> matched_route = nullopt;
      uint32_t mask = 0x80000000; // 最高位掩码
  
      for (int i = 0; i < 32; ++i) {
          bool bit = (destination & mask) != 0; // 注意：使用 mask 而非 mask >> i
          mask >>= 1; // 右移掩码，处理下一低位
  
          // 如果当前节点有路由条目，更新最佳匹配
          if (node->route.has_value()) {
              matched_route = node->route;
          }
  
          // 检查子节点是否存在
          if (!node->children[bit]) {
              break;
          }
          node = node->children[bit].get();
      }
  
      // 循环结束后再次检查最后一个节点的路由
      if (node->route.has_value()) {
          matched_route = node->route;
      }
  
      if (matched_route) {
        std::cerr << "[DEBUG] Matched route: "
                  << Address::from_ipv4_numeric(matched_route->route_prefix).ip()
                  << "/" << static_cast<int>(matched_route->prefix_length)
                  << " -> " << (matched_route->next_hop ? matched_route->next_hop->ip() : "DIRECT")
                  << " (interface " << matched_route->interface_num << ")"
                  << std::endl;
      } else {
        std::cerr << "[ERROR] No match for destination: "
                  << Address::from_ipv4_numeric(destination).ip() << std::endl;
      }
      return matched_route;
  }
    
    // 清理整棵 Trie 树
    void cleanup_trie() {
        root.reset();  // 清理 root，会递归释放所有节点
    }

  optional<RouteEntry> lookup_route(uint32_t destination) {
    return lookup(destination);
  }

  // Debug 
};

实现前缀树后，后面的两个主要函数就没有实现难度了，其中route()函数就是遍历该路由器上所有的网络接口，然后将未发送的数据报都发送出去。

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() << "/"
       << static_cast<int>( prefix_length ) << " => " << ( next_hop.has_value() ? next_hop->ip() : "(direct)" )
       << " on interface " << interface_num << "\n";

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

// Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
void Router::route()
{
  for (auto& interface : _interfaces) {
    while (!interface->datagrams_received().empty()) {
        InternetDatagram datagram = interface->datagrams_received().front();
        interface->datagrams_received().pop();

        auto route = lookup_route(datagram.header.dst);
        if (!route.has_value()) {
            cerr << "No route for " << Address::from_ipv4_numeric(datagram.header.dst).ip() << endl;
            continue;
        }

        // 处理TTL
        datagram.header.ttl--;
        if (datagram.header.ttl <= 0) {
            cerr << "TTL expired for " << Address::from_ipv4_numeric(datagram.header.dst).ip() << endl;
            continue;
        }

        // 确定下一跳
        const Address next_hop = route->next_hop.value_or(
            Address::from_ipv4_numeric(datagram.header.dst)
        );

        // 发送数据包
        _interfaces[route->interface_num]->send_datagram(datagram, next_hop);
    }
  }
}

Test

至此完成CS 144的全部实验。