Program Structure and Design

这次实验比较简单，主要是需要设计一个高效的路由表，这里我选择设计的路由表类型是：

1
std::array<std::map<uint32_t, std::pair<std::optional<Address>, size_t>>, 33> _routing_table {};

这个结构的含义如下：

  • 第一层Array用于表示前缀的长度，这样方便从长到短匹配
  • 第二层里面是一个map，记录了从ip前缀到下一跳地址以及出口号的映射关系
  • 最后存的是一个pair，记录了下一跳、出口地址

然后我封装了一个最长前缀匹配的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::pair<std::optional<Address>, size_t> Router::get_address( const uint32_t ip ) const
{
  for ( int idx = 32; idx >= 0; --idx ) {
    uint32_t mask;
    if ( idx == 0 )
      mask = 0;
    else
      mask = 0xFFFFFFFF << ( 32 - idx );
    uint32_t masked_ip = ip & mask;
    auto it = _routing_table[idx].find( masked_ip );
    if ( it != _routing_table[idx].end() ) {
      return it->second;
    }
  }
  return make_pair( std::nullopt, std::numeric_limits<size_t>::max() );
}

这里的思路就是首先根据前缀的长度去创建一个mask然后按位与上当前的ip就可以获得这个长度的前缀，需要注意的是，如果前缀长度为0直接左移是未定义行为，会报错，所以需要特殊处理一下，最后顺次进去匹配看有没有匹配上的就行了

最后这个发送也非常简单，按照手册实现就行了，首先检查ttl是否还有空余，没有直接丢包，然后去查表，查到下一跳和出口号用对应的api发包就行了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void Router::route()
{
  // Your code here.
  for ( auto& interface : _interfaces ) {
    auto& datagrams = interface->datagrams_received();
    while ( !datagrams.empty() ) {
      auto datagram = std::move( datagrams.front() );
      datagrams.pop();
      auto& header = datagram.header;
      if (header.ttl <= 1) {
        // it the ttl is less than 1 then drop the datagram
        continue;
      }
      header.ttl--;
      header.compute_checksum();
      auto [next_hop, interface_num] = get_address( header.dst );
      if ( interface_num == std::numeric_limits<size_t>::max() ) {
        // drop this datagram because of no route found
        cerr << "No route found for " << Address::from_ipv4_numeric( header.dst ).ip() << "\n";
        continue;
      }
      // now send the datagram
      if ( next_hop.has_value() ) {
        cerr << "Sending datagram to " << Address::from_ipv4_numeric( header.dst ).ip() << " via "
             << next_hop.value().ip() << " on interface " << interface_num << "\n";
        _interfaces[interface_num]->send_datagram( datagram, next_hop.value() );
      } else {
        cerr << "Sending datagram to " << Address::from_ipv4_numeric( header.dst ).ip() << " directly on interface "
             << interface_num << "\n";
        _interfaces[interface_num]->send_datagram( datagram, Address::from_ipv4_numeric( header.dst ) );
      }
    }
  }
}

Implementation Challenges.

在实现过程中，我遇到了如下问题：

  • 左移了0，为定义行为爆了RE
  • 忘了重新计算checksum，导致报错包损坏
  • ttl是uint8_t 我开始是直接减一再去判断的，这样在0的时候会溢出，导致变成 255 最后这个包就不会丢弃了
    别的这次实验还算顺利，只测了三发就过关了

Remaining Bugs.

None

Experimental results and performance.

测试结果如下：