CS144-5

幻雪2023-12-152023-12-16

CS144-5

前言
cmake --build build --target check4如下就可以开始代码了

</div>
这一次是要实现一个路由表的功能，你需要去做一个存储路由的功能。

我使用的结构体加vector的组合来实现这一部分，当然你可以自己想一个合适的，我选择这种组合的原因是，用map来实现的话那么用什么来映射呢，又如何知道哪一个是最优的匹配路径，只能通过遍历，然后再通过算法去实现查询，我目前的思路是这样的，所以选择能支持快速增删的简单结构

其中实现的重点在于寻求最优匹配，这一部分涉及到网络掩码的内容，如果不懂这一部分的友友，可以去b站搜搜看，大概的意思就是多少位是一样的，剩下的这可变化的区域作为子网段，掩码的作用就是规定了这个范围，同时也告诉我们匹配的长度，用于后续求最优的依据。

实验开始
我阅读完文档可以罗列出的思路是这样的

</div>
实现完代码后的思路是这样的

</div>
以上就是我整体的思路

难的是匹配路由表的函数，这个函数是需要通过提供的匹配长度，然后推算出当前是否是匹配的路由，后面我们可以通过这个匹配长度来判断是否是最优的

判断最优的过程是找到优的就复制，这和新手村求一组数max是一样的，很简单。

然后就是如何匹配，我们知道ip也是0和1的世界，所以我们匹配0和1的时候只要与一下不就可以了？思路是不是一下子就出来了。

那就去实现吧，我代码放在文末

router.cc

#include "router.hh"

#include <iostream>
#include <limits>
#include<iostream>

using namespace std;

// route_prefix: The "up-to-32-bit" IPv4 address prefix to match the datagram's destination address against
// prefix_length: For this route to be applicable, how many high-order (most-significant) bits of
//    the route_prefix will need to match the corresponding bits of the datagram's destination address?
// next_hop: The IP address of the next hop. Will be empty if the network is directly attached to the router (in
//    which case, the next hop address should be the datagram's final destination).
// interface_num: The index of the interface to send the datagram out on.

// route_prefix: 要与数据报目的地址匹配的“最多32位”的IPv4地址前缀
// prefix_length: 此路由适用所需的条件，即数据报目的地址的高阶（最重要）位中有多少位需要与路由前缀对应的位匹配？
// next_hop: 下一跳的IP地址。如果网络直接连接到路由器，则为空（在这种情况下，下一跳地址应该是数据报的最终目的地）。
// interface_num: 发送数据报的接口索引。

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_Message route_message;
  route_message.interface_num=interface_num;
  route_message.next_hop=next_hop;
  route_message.prefix_length=prefix_length;
  route_message.route_prefix=route_prefix;
//存储路由信息
  route_map.push_back(route_message);
  (void)route_prefix;
  (void)prefix_length;
  (void)next_hop;
  (void)interface_num;
}

bool ip_matches_route(uint32_t ip_address, uint32_t route_prefix, uint8_t prefix_length) {
if(prefix_length>32){
  return false;
}
uint32_t subnet_mask = prefix_length == 0 ? 0 : 0xFFFFFFFF << (32 - prefix_length);
uint32_t masked_ip = ip_address & subnet_mask;
uint32_t masked_route_prefix = route_prefix & subnet_mask;
return masked_ip == masked_route_prefix;
}

void Router::route() {
//当前是否有接口传输数据
for(auto &it:interfaces_){
  auto datagram=it.maybe_receive();
  if(!datagram.has_value()){
    continue;
  }
  auto& dgram=datagram.value();
  //是否已经有已经不存在的路由
  if(dgram.header.ttl<=1){
    continue;
  }
  //否者计算校验和，更新ttl
  dgram.header.ttl--;
  dgram.header.compute_checksum();
  //是否找得到匹配一个段?
  //获取ip地址
  uint32_t IP=dgram.header.dst;
  //设置最匹配地址
  Route_Message bestMatchRoute{};
  bool hasBestMatch = false; // 新增变量来跟踪是否找到有效匹配
  size_t i=0;
  while(i<route_map.size()){
    // cout<<"发送之前"<<endl;
    // cout<<"bestMatchRoute.prefix_length:"<<to_string(bestMatchRoute.prefix_length)<<endl;
    // cout<<"route_map[i].prefix_length:"<<to_string(route_map[i].prefix_length)<<endl;
    // cout<<"hasBestMatch:"<<hasBestMatch<<endl;
    // cout<<"IP:"<<IP<<endl;
    

    if(!ip_matches_route(IP,route_map[i].route_prefix,route_map[i].prefix_length)){
      i++;
      continue;
    }
    //当前的是否需要更新，如果没有赋值先赋值，如果已经初始化了就看看是不是需要更新
    if(hasBestMatch&&bestMatchRoute.prefix_length>=route_map[i].prefix_length){
      i++;
      continue;
    }
    
    bestMatchRoute=route_map[i];
    hasBestMatch=true;
    i++;
  }
  //有合适下一跳？
  if(!hasBestMatch){
  continue;
  }
auto &async_NetworkInterface=interface(bestMatchRoute.interface_num);
async_NetworkInterface.send_datagram(dgram, 
            bestMatchRoute.next_hop.value_or(Address::from_ipv4_numeric(IP)));
    // cout<<"发送之后"<<endl;
    // cout<<"bestMatchRoute.prefix_length:"<<to_string(bestMatchRoute.prefix_length)<<endl;
    // cout<<"route_map[i].prefix_length:"<<to_string(route_map[i].prefix_length)<<endl;
    // cout<<"hasBestMatch:"<<hasBestMatch<<endl;
}
}

router.hh

#pragma once

#include "network_interface.hh"

#include <optional>
#include <queue>

// A wrapper for NetworkInterface that makes the host-side
// interface asynchronous: instead of returning received datagrams
// immediately (from the `recv_frame` method), it stores them for
// later retrieval. Otherwise, behaves identically to the underlying
// implementation of NetworkInterface.

// 对NetworkInterface的包装，使得主机侧的接口变为异步：不是立即返回收到的数据报
//（来自`recv_frame`方法），而是将它们存储起来以供稍后检索。除此之外，
// 其行为与底层实现的NetworkInterface相同。

class AsyncNetworkInterface : public NetworkInterface
{
  std::queue<InternetDatagram> datagrams_in_ {};

public:
  using NetworkInterface::NetworkInterface;

  // Construct from a NetworkInterface
  // 从NetworkInterface构造
  explicit AsyncNetworkInterface( NetworkInterface&& interface ) : NetworkInterface( interface ) {}

  // \brief Receives and Ethernet frame and responds appropriately.

  // - If type is IPv4, pushes to the `datagrams_out` queue for later retrieval by the owner.
  // - If type is ARP request, learn a mapping from the "sender" fields, and send an ARP reply.
  // - If type is ARP reply, learn a mapping from the "target" fields.
  //
  // \param[in] frame the incoming Ethernet frame

    // \brief 接收Ethernet帧并做出相应的响应。

  // - 如果类型是IPv4，则将其推入`datagrams_out`队列，以供所有者稍后检索。
  // - 如果类型是ARP请求，则学习“发送者”字段中的映射，并发送ARP回复。
  // - 如果类型是ARP回复，则学习“目标”字段中的映射。
  //
  // \param[in] frame 进来的Ethernet帧

  void recv_frame( const EthernetFrame& frame )
  {
    auto optional_dgram = NetworkInterface::recv_frame( frame );
    if ( optional_dgram.has_value() ) {
      datagrams_in_.push( std::move( optional_dgram.value() ) );
    }
  };

  // Access queue of Internet datagrams that have been received
  // 访问已收到的Internet数据报队列

  std::optional<InternetDatagram> maybe_receive()
  {
    if ( datagrams_in_.empty() ) {
      return {};
    }

    InternetDatagram datagram = std::move( datagrams_in_.front() );
    datagrams_in_.pop();
    return datagram;
  }
};

//构建路由信息
struct Route_Message{
  uint32_t route_prefix{};
  uint8_t prefix_length{};
  std::optional<Address> next_hop{};
  size_t interface_num{};
};


// A router that has multiple network interfaces and
// performs longest-prefix-match routing between them.
// 一个拥有多个网络接口并在它们之间进行最长前缀匹配路由的路由器。
class Router
{
  // The router's collection of network interfaces
    // 路由器的网络接口集合
  std::vector<AsyncNetworkInterface> interfaces_ {};
   //构建路由映射
  std::vector<Route_Message> route_map {};

public:
  //设置辅助函数

  

  // Add an interface to the router
  // interface: an already-constructed network interface
  // returns the index of the interface after it has been added to the router

  // 向路由器添加一个接口
  // interface: 一个已经构造好的网络接口
  // 返回添加到路由器后的接口索引 
  size_t add_interface( AsyncNetworkInterface&& interface )
  {
    interfaces_.push_back( std::move( interface ) );
    return interfaces_.size() - 1;
  }

  // Access an interface by index
  // 通过索引访问接口
  AsyncNetworkInterface& interface( size_t N ) { return interfaces_.at( N ); }

  // Add a route (a forwarding rule)
  // 添加一条路由（一条转发规则）
  void add_route( uint32_t route_prefix,
                  uint8_t prefix_length,
                  std::optional<Address> next_hop,
                  size_t interface_num );

  // Route packets between the interfaces. For each interface, use the
  // maybe_receive() method to consume every incoming datagram and
  // send it on one of interfaces to the correct next hop. The router
  // chooses the outbound interface and next-hop as specified by the
  // route with the longest prefix_length that matches the datagram's
  // destination address.

  // 在接口之间路由数据报。对于每个接口，使用
  // maybe_receive() 方法消费每个进入的数据报，
  // 并根据路由选择正确的下一跳发送到其中一个接口。路由器
  // 根据与数据报目的地址匹配最长前缀长度的路由规则指定出站接口和下一跳。
  void route();
};