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 #

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

1void Router::add_route( const uint32_t route_prefix,
2                        const uint8_t prefix_length,
3                        const optional<Address> next_hop,
4                        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 归零的数据包直接丢弃。

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

1struct Entry
2{
3    uint32_t route_prefix;
4    uint8_t prefix_length;
5    std::optional<Address> next_hop;
6    size_t interface_num;
7};
8
9std::vector<Entry> routing_table_ {};

 1void Router::add_route( const uint32_t route_prefix,
 2                        const uint8_t prefix_length,
 3                        const optional<Address> next_hop,
 4                        const size_t interface_num )
 5{
 6  // cerr << "DEBUG: adding route " << Address::from_ipv4_numeric( route_prefix ).ip() << "/"
 7  //      << static_cast<int>( prefix_length ) << " => " << ( next_hop.has_value() ? next_hop->ip() : "(direct)" )
 8  //      << " on interface " << interface_num << "\n";
 9
10  routing_table_.push_back( Entry { route_prefix, prefix_length, next_hop, interface_num } );
11}

 1void Router::route()
 2{
 3  for ( auto& interface : interfaces_ ) {
 4    auto& datagrams_received = interface->datagrams_received();
 5    while ( !datagrams_received.empty() ) {
 6      auto dgram = move( datagrams_received.front() );
 7      datagrams_received.pop();
 8
 9      if ( dgram.header.ttl <= 1 ) {
10        // TTL (will be) expired, drop the datagram
11        continue;
12      }
13      dgram.header.ttl--;
14      dgram.header.compute_checksum();
15
16      const uint32_t dest_ip = dgram.header.dst;
17      int best_prefix_len = -1;
18      optional<Address> best_next_hop = nullopt;
19      size_t best_interface_num = 0;
20      for ( auto& entry : routing_table_ ) {
21        const uint32_t mask = entry.prefix_length == 0 ? 0 : 0xffffffff << ( 32 - entry.prefix_length );
22        if ( ( dest_ip & mask ) == ( entry.route_prefix & mask ) ) {
23          if ( static_cast<int>( entry.prefix_length ) > best_prefix_len ) {
24            best_prefix_len = entry.prefix_length;
25            best_next_hop = entry.next_hop;
26            best_interface_num = entry.interface_num;
27          }
28        }
29      }
30      if ( best_prefix_len == -1 ) {
31        // No matching route, drop the datagram
32        continue;
33      }
34      Address next_hop = best_next_hop.has_value() ? *best_next_hop : Address::from_ipv4_numeric( dest_ip );
35      interfaces_[best_interface_num]->send_datagram( dgram, next_hop );
36    }
37  }
38}

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