CS144-check6

总览

上个lab中我们实现了网卡的逻辑，现在我们要开始实现路由了。

路由有多个网口，连接多个network interface（在上一个lab中我们实现的）。在本次实验中，我们不需要考虑路由表的产生逻辑（例如 OSPF，BGP，RIP，SDN Controller等），我们只需要根据手动添加的路由规则，进行目的IP的最长前缀匹配，再将其转交给对应的interface即可。

并且，我们的匹配规则只有唯一的匹配域。也就是说，我们在匹配时只需要关心目的ip，根据最长前缀进行匹配。如图

最长前缀匹配算法 LPM

在具体目标之前，我们先考虑一下如何进行针对ipv4（uint32）的最长前缀匹配。

我们的每条匹配规则需要显式地指定前缀和长度。

思考：可以不指定长度吗？

如果不指定长度，对于32位整数来说我们无法区分192.168.0.0和192.168.*.*，势必会引入更复杂的编码

在这里介绍两种简单常用的LPM算法，分别为哈希和字典树（trie）

Hash

DPDK（Data Plane Development Kit）的hash采用了一种24bit hashtable+多个8bit hashtable的解决方案。对于有效前缀长度小于24的规则则扩展到24位并添加到多个24bit hashtable的条目中。（例如有效前缀长度长度为22，则需要添加$2^(24-22) = 4$个表项）。对于长度大于24bit的规则，则使用一个24bit表项指向空闲的8bit表项。也就是说，对于前24位相同而后8位不同的规则，可以共用同一个8bit hashtable。这样的设计兼顾了查找速度（两次hash），内存用量和可用性。

但是，维护这样的表似乎同样有些复杂，有没有更简单的hash方法呢，当然有，我们可以针对长度为1-32的逻辑各建立一个hash表，进行pipeline式地匹配，也就是查找匹配32位的hash表，失配则匹配31位的hash表……这样的流水匹配虽然有些笨拙，但是完成本实验是完全足够的。

Trie

那么，有没有优雅一点的数据结构呢？我们隆重介绍————字典树（trie）

Trie是进行字符串前缀检索的常用数据结构。例如我们想检索《中华人民共和国行政区划代码》（GB/T 2260），对省/市/县/乡进行前缀匹配，一个常用的结构就是字典树Trie。

更好的是，对于二进制的01串，Trie就更加合适了。因为每个节点最多有两个子节点0/1，这样一切都容易了起来。

所以，当一个目的ip需要被匹配时，我们只需要在树上往下走，走到走不了为止，此时最近匹配的含有路由规则的节点就是应该执行的行为。

失配的节点不一定含有路由规则，所以路由规则在最近的匹配节点里。例如
rule1 : 192.1.*.*
rule3 : 192.*.*.*
dst ip : 192.0.1.1
那么会在Trie的第16bit(16层)处失配，但是deep = 15的节点是不包含任何转发规则的，需要执行的转发规则在deep = 8处的节点里。

那么，在了解匹配算法之后，我们来看本次实验的目标

目标

在这个lab中，你将实现一个路由器类，它可以：

• 跟踪路由表（转发规则或路由列表），
• 转发它接收到的每个数据报：
  • 到正确的下一跳
  • 通过正确的外部网络接口。
    你的实现将被添加到 router.hh 和 router.cc 的框架文件中。在你开始编码之前，请查阅 router.hh 中新路由器类的文档。
    这里是你将实现的两种方法，以及我们在每种方法中的期望：

void add_route(uint32_t route_prefix, uint8_t prefix_length, optional<Address> next_hop, size_t interface_num);
这种方法向路由表中添加一条路由。你将想在 Router 类中添加一个数据结构作为私有成员来存储这些信息。这个方法需要做的就是保存以后使用的路由。

路由的各部分是什么意思？
一条路由是一个“匹配-动作”规则：它告诉路由器，如果一个数据报是为了一个特定的网络（一个IP地址范围），并且如果这条路由被选为最具体的匹配路由，那么路由器应该将数据报转发到特定的下一跳和特定的接口。
“匹配”：数据报是不是要去这个网络？路由前缀和前缀长度一起指定了可能包括数据报目的地的一系列IP地址（一个网络）。路由前缀是一个32位数值IP地址。前缀长度是0到32（包括）之间的一个数字；它告诉路由器路由前缀的多少最重要的位是重要的。例如，要表示一个到网络“18.47.0.0/16”的路由（这匹配任何前两个字节是18和47的32位IP地址），路由前缀将是305070080（18×224 + 47×216），前缀长度将是16。任何目的地为“18.47.x.y”的数据报都将匹配。
“动作”：如果路由匹配并被选择，该做什么。如果路由器直接连接到目的设备，下一跳将是一个空的可选项。在这种情况下，下一跳是数据报的目的地址。但如果路由器通过某其他路由器连接到目的设备，下一跳将包含沿路径下一个路由器的IP地址。接口编号给出了应该用来将数据报发送到下一跳的路由器的网络接口的索引。你可以通过 interface(interface_num) 方法访问这个接口。

void route();
这里是关键所在。这个方法需要将每个进来的数据报路由到下一跳，通过适当的接口输出。它需要实现 IP 路由器的“最长前缀匹配”逻辑来找到最佳的路由。这意味着：

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

互联网设计中有一种美丽（或至少是一个成功的抽象）：路由器从不考虑 TCP、ARP 或以太网帧。路由器甚至不知道链路层是什么样的。路由器只考虑互联网数据报，并且只通过网络接口抽象与链路层交互。当涉及到诸如“链路层地址是如何解析的？”、“链路层是否有自己与 IP 不同的地址方案？”、“链路层帧的格式是什么？”或“数据报的有效载荷是什么意思？”等问题时，路由器就不关心了。

Q & A

• 什么数据结构应该用来记录路由表？

  这取决于你！但请不要太复杂。对于每个数据报需要 O(N) 的工作量是完全可以接受的，其中 N 是路由表中的条目数。如果你想做一些更高效的事情，我们鼓励你先实现一个工作版本，然后再优化，并且仔细记录和注释你选择实现的任何内容。

• 如何将以 Address 对象形式出现的 IP 地址转换为我可以写入 ARP 消息的原始 32 位整数？

  使用 Address::ipv4_numeric() 方法。

• 如何将以原始 32 位整数形式出现的 IP 地址转换为 Address 对象？

  使用 Address::from_ipv4_numeric() 方法。

• 如何比较一个 32 位 IP 地址的最重要的 N 位（其中 0 ≤ N ≤ 32）与另一个 32 位 IP 地址的最重要的 N 位？

  这可能是这个作业中最“棘手”的部分——得到正确的逻辑。编写一个小的 C++ 测试程序（一个简短的独立程序）或在 Minnow 中添加一个测试来验证你对相关 C++ 操作符的理解并仔细检查你的逻辑可能是值得的。
  记住，在 C 和 C++ 中，将一个 32 位整数移位 32 位可能会产生未定义行为。测试会在你的代码下运行检测器来尝试检测这一点。你可以通过在 minnow 目录下运行 ./build/tests/router 直接运行路由器测试。

• 如果路由器没有到目的地的路由，或者如果 TTL 变为零，它不应该向数据报的来源发送 ICMP 错误消息吗？

  在现实生活中，是的，这会很有帮助。但在这个实验室中不是必需的——丢弃数据报就足够了。（即使在现实世界中，也不是每个路由器在这些情况下都会向来源发送 ICMP 消息。）

实现

在理解了Trie的逻辑之后，这里0-1Trie的实现是简单的

struct TrieNode
{
  TrieNode() : interface_num(std::nullopt),next_hop(std::nullopt),left(nullptr),right(nullptr) {};

  std::optional<size_t> interface_num;
  std::optional<Address> next_hop;
  std::unique_ptr<TrieNode> left;
  std::unique_ptr<TrieNode> right;
};

插入时根据前缀长度进行插入到指定深度

for ( auto i = 1; i <= prefix_length; i++ ) {
    auto bit = route_prefix & ( 1 << ( 32 - i ) );
    if (bit){
      if (cur->right == nullptr){
        cur->right = make_unique<TrieNode>();
      }
      cur = cur->right.get();
    } else {
      if (cur->left == nullptr){
        cur->left = make_unique<TrieNode>();
      }
      cur = cur->left.get();
    }
    if ( i == prefix_length ){
      cur->interface_num = interface_num;
      if ( next_hop.has_value() )
        cur->next_hop = next_hop;
    }
  }

查找

for ( auto i = 1; i <= 32; i++ ) {
  auto bit = ip & ( 1 << ( 32 - i ) );
  cur = bit ? cur->right.get() : cur->left.get();
  if ( cur == nullptr ) {
    break;
  }
  if ( cur->interface_num.has_value() ) {
    infce = cur->interface_num;
    addr = cur->next_hop;
  }
}

这里值得注意的一点是，TTL是报文在网络中的存活时间，所以我们在转发时也需要ttl自减，并且因为ttl发生了变化，我们需要重新计算校验值。

其他部分的逻辑是简单的，我们只需要从每个网卡的receive队列中抽出并进行匹配即可。完整代码如下

class Router
{
  ......
  std::queue<InternetDatagram> datagram_buffer_ {};

  bool match( InternetDatagram& d );

  struct TrieNode
  {
    TrieNode() : interface_num(std::nullopt),next_hop(std::nullopt),left(nullptr),right(nullptr) {};

    std::optional<size_t> interface_num;
    std::optional<Address> next_hop;
    std::unique_ptr<TrieNode> left;
    std::unique_ptr<TrieNode> right;
  };

  std::unique_ptr<TrieNode> root_ {nullptr};
};

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

  auto cur = root_.get();
  if ( prefix_length == 0 ) {
    if (!root_){
      root_ = make_unique<TrieNode>();
    }
    root_->interface_num = interface_num;
    if ( next_hop.has_value() )
      root_->next_hop = next_hop;
    return;
  }
  for ( auto i = 1; i <= prefix_length; i++ ) {
    auto bit = route_prefix & ( 1 << ( 32 - i ) );
    if (bit){
      if (cur->right == nullptr){
        cur->right = make_unique<TrieNode>();
      }
      cur = cur->right.get();
    } else {
      if (cur->left == nullptr){
        cur->left = make_unique<TrieNode>();
      }
      cur = cur->left.get();
    }
    if ( i == prefix_length ){
      cur->interface_num = interface_num;
      if ( next_hop.has_value() )
        cur->next_hop = next_hop;
    }
  }
}

// Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
void Router::route()
{ 
  for ( auto& i : _interfaces ) {
    while ( !i->datagrams_received().empty() ) {
      datagram_buffer_.push( i->datagrams_received().front() );
      i->datagrams_received().pop();
    }
  }
  queue<InternetDatagram> datagram_buffer_copy;
  while ( !datagram_buffer_.empty() ) {
    InternetDatagram& d = datagram_buffer_.front();
    if (d.header.ttl == 0){
      datagram_buffer_.pop();
      continue;
    }
    if ( !match( d ) ) {
      d.header.ttl--;
      datagram_buffer_copy.push( d );
    }
    datagram_buffer_.pop();
  }
  datagram_buffer_ = move(datagram_buffer_copy);
}

bool Router::match( InternetDatagram& d )
{ 
  auto ip = d.header.dst;
  auto cur = root_.get();
  optional<size_t> infce;
  optional<Address> addr; 
  if (root_->interface_num.has_value()) {
    infce = root_->interface_num;
    addr = root_->next_hop;
  }
  for ( auto i = 1; i <= 32; i++ ) {
    auto bit = ip & ( 1 << ( 32 - i ) );
    cur = bit ? cur->right.get() : cur->left.get();
    if ( cur == nullptr ) {
      break;
    }
    if ( cur->interface_num.has_value() ) {
      infce = cur->interface_num;
      addr = cur->next_hop;
    }
  }
  if (!infce.has_value()){
    return false;
  }
  d.header.ttl--;
  if( d.header.ttl == 0 ){
    return true;
  }
  d.header.compute_checksum();
  if (addr.has_value()){
    interface(infce.value())->send_datagram( d, addr.value() );
  }
  else {
    interface(infce.value())->send_datagram( d, Address::from_ipv4_numeric( d.header.dst ));
  }
  return true;
}