Stanford CS144 Lab 6

building an IP router

August 28, 2025

#Cs144 #C++

Checkpoint 6 是最后一个需要在实验框架中填充代码的 checkpoint。我们将在 NetworkInterface 的基础上实现一个 IP router。如同现实世界的 router 一样，这个 router 包含若干个 interfaces，按照路由表将 IP 包路由到不同的 interface。遗憾的是，这里不涉及路由表生成的算法。我们只需遵照路由表完成转发。

3 Implementing the Router #

实验框架给出的添加路由的方法签名是这样的：

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

route_prefix 是将路由前缀用 32 位无符号整数表达的形式，prefix_length 相当于子网掩码。例如 route_prefix 为 $305070080$，prefix_length 为 $16$ 的时候，就是一条向 18.47.0.0/16 的路由。

所有路由表采用最大前缀匹配 (longest-prefix-match)：在所有匹配的路由表条目中，选择 prefix_length 最大的那个。一旦成功匹配，则调用 interface_num 对应的 NetworkInterface，将数据包转发到对应的 next_hop。特别地，假如 next_hop 为 None，则转发到数据包头的目标地址。

此外还需要注意转发时要给数据包的 TTL 减去 1，对于 TTL 归零的数据包直接丢弃。

顺着这个函数签名，我添加了如下私有成员用于表示路由表：

struct Entry
{
    uint32_t route_prefix;
    uint8_t prefix_length;
    std::optional<Address> next_hop;
    size_t interface_num;
};

std::vector<Entry> routing_table_ {};

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";

  routing_table_.push_back( Entry { route_prefix, prefix_length, next_hop, interface_num } );
}

void Router::route()
{
  for ( auto& interface : interfaces_ ) {
    auto& datagrams_received = interface->datagrams_received();
    while ( !datagrams_received.empty() ) {
      auto dgram = move( datagrams_received.front() );
      datagrams_received.pop();

      if ( dgram.header.ttl <= 1 ) {
        // TTL (will be) expired, drop the datagram
        continue;
      }
      dgram.header.ttl--;
      dgram.header.compute_checksum();

      const uint32_t dest_ip = dgram.header.dst;
      int best_prefix_len = -1;
      optional<Address> best_next_hop = nullopt;
      size_t best_interface_num = 0;
      for ( auto& entry : routing_table_ ) {
        const uint32_t mask = entry.prefix_length == 0 ? 0 : 0xffffffff << ( 32 - entry.prefix_length );
        if ( ( dest_ip & mask ) == ( entry.route_prefix & mask ) ) {
          if ( static_cast<int>( entry.prefix_length ) > best_prefix_len ) {
            best_prefix_len = entry.prefix_length;
            best_next_hop = entry.next_hop;
            best_interface_num = entry.interface_num;
          }
        }
      }
      if ( best_prefix_len == -1 ) {
        // No matching route, drop the datagram
        continue;
      }
      Address next_hop = best_next_hop.has_value() ? *best_next_hop : Address::from_ipv4_numeric( dest_ip );
      interfaces_[best_interface_num]->send_datagram( dgram, next_hop );
    }
  }
}

代码量很小，唯一需要注意的就是操作 TTL 之后，不要忘了重新计算 checksum。