CS144-check6

overview

虽然一共有8个lab，但本质上这就是最后一个了：第八个lab是检查你的实现是否正确，并在真实的网络环境下运行。check6需要我们实现路由：将同一个路由器的不同网络接口收到的报文分发到正确的网络接口。确定网络接口使用了Longest-prefix match。

具体的，我们需要记录一张路由表，并根据匹配+动作的路由规则正确处理。

简单得出乎意料，并不需要实现路由选择算法之流。

implement

member

class Router
{
...
private:
  // The router's collection of network interfaces
  std::vector<std::shared_ptr<NetworkInterface>> _interfaces {};

  // the routing table
  struct route_entry{
    uint32_t route_prefix;
    uint8_t prefix_length;
    std::optional<Address> next_hop;
    size_t interface_num;
  };
  std::vector<route_entry> route_table {};
};

实现非常简单，因为只需要记录路由表。

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

  route_entry re;
  re.route_prefix = route_prefix;
  re.prefix_length = prefix_length;
  re.next_hop = next_hop;
  re.interface_num = interface_num;
  route_table.push_back(re);
}

将传入的参数记录在表中就行。

route

// Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
void Router::route()
{
  for(size_t i = 0; i < _interfaces.size(); i++) {
    // for each datagram
    while(!((interface(i)->datagrams_received()).empty())) {

      InternetDatagram dgram = interface(i)->datagrams_received().front();
      
      // search the routing table and match
      uint32_t dst = dgram.header.dst;
      uint32_t longest_length = 0;
      route_entry *longest_prefix_match = nullptr;
      auto it = route_table.begin();
      for(; it != route_table.end(); it++) {
        route_entry e = *it;

        // search the match
        if(e.prefix_length == 0) {
          if(longest_length == 0)
            longest_prefix_match = &(*it);
          continue;
        }

        uint32_t prefix1 = (dst >> (32 - e.prefix_length)) << (32 - e.prefix_length);
        uint32_t prefix2 = (e.route_prefix >> (32 - e.prefix_length)) << (32 - e.prefix_length);
        
        if(prefix1 == prefix2) {
          // among the match, choose the longest-prefix-match route
          if(e.prefix_length > longest_length) {
            longest_length = e.prefix_length;
            longest_prefix_match = &(*it);
          }
        }
      }

      // if not found, drop the datagram
      if(longest_prefix_match == nullptr) {
        interface(i)->datagrams_received().pop();
        continue;
      }
        

      // decrement TTL
      if(dgram.header.ttl == 0 || dgram.header.ttl == 1) {
        interface(i)->datagrams_received().pop();
        continue;
      }  
      dgram.header.ttl -= 1;
      dgram.header.compute_checksum();

      // send modified datagram to appropriate interface
      if(longest_prefix_match->next_hop.has_value())
        interface(longest_prefix_match->interface_num)->send_datagram(dgram, (longest_prefix_match->next_hop).value());
      else 
        interface(longest_prefix_match->interface_num)->send_datagram(dgram, Address::from_ipv4_numeric(dgram.header.dst));
      interface(i)->datagrams_received().pop();
    }
    
  }
}

大部分看文档实现就行，通关到这里实现这个真的非常简单。位操作别出问题，不确定的话可以输出debug infomation看看。注意，prefix_length为0的情况：一是在位操作前要特殊处理（试图对无符号32位整数位移32位是未定义操作UB），二是prefix_length为0的表项可以匹配到任何IP地址，而不是不匹配！