首页 > 其他分享 >【斯坦福CS144】Lab5

【斯坦福CS144】Lab5

时间:2024-10-09 20:46:50浏览次数:8  
标签:tgt ip CS144 斯坦福 len prefix Lab5 interface route

一、实验目的

在现有的NetworkInterface基础上实现一个IP路由器。

二、实验内容

在本实验中,你将在现有的NetworkInterface基础上实现一个IP路由器,从而结束本课程。路由器有几个网络接口,可以在其中任何一个接口上接收互联网数据报。路由器的工作是根据路由表转发它得到的数据报:一个规则列表,它告诉路由器,对于任何给定的数据报:

发送到哪个接口;

下一跳的IP地址 ;

你的工作是实现一个路由器,它可以为任何给定的数据报计算出这两件事。(你不需要实现设置路由表的算法,例如RIP、OSPF、BGP或SDN控制器,只需要实现跟随路由表的算法)。

你对路由器的实现将使用带有新的Router类的Sponge库,以及在模拟网络中检查你的路由器功能的测试。本实验建立在你在上一个实验中对NetworkInterface的实现之上,但不使用你在之前实验中实现的TCP栈。IP路由器不需要知道任何关于TCP、ARP或以太网的信息(仅限IP)。我们希望你的实现将需要大约25-30行的代码。

三、实验过程

在minnow目录下输入git merge origin/check5-startercode获取Lab5

用文本编辑器打开./src/router.hh

修改代码

用文本编辑器打开./src/router.cc

修改代码

在build目录下输入make进行编译

输入make check5进行测试

测试成功,实验结束

四、实验体会

1.本实验中的 Router 实现比较简单,只需实现一下 IP 最长匹配并将数据包转发即可。

2.需要注意的是,联系计算机网络理论课和实验所学习的内容,在实际网络中,路由表会根据网络拓扑和路由策略进行配置,以确保数据包能够正确地转发到目标。路由表中的路由条目根据目标网络地址的前缀匹配来确定数据包的转发规则。当无法找到匹配的路由条目时,数据包将根据默认路由进行转发,或者如果没有默认路由,则会被丢弃。

五、代码附录

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.
class AsyncNetworkInterface : public NetworkInterface
{
  std::queue<InternetDatagram> datagrams_in_ {};

public:
  using NetworkInterface::NetworkInterface;

  // Construct from a 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
  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
  std::optional<InternetDatagram> maybe_receive()
  {
    if ( datagrams_in_.empty() ) {
      return {};
    }

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

// 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_ {};

//   struct Route_entry//route_entry_
//   {
//     uint32_t route_prefix{};
//     uint8_t prefix_length{};
//     std::optional<Address> next_hop;
//     size_t interface_num{};
//   };
//   //static typedef struct route_entry_ Route_entry;
//   std::vector<Route_entry> route_table_{};
class Router
{
  // The router's collection of network interfaces
  std::vector<AsyncNetworkInterface> interfaces_ {};
  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_ {};

  //std::vector<Route_entry>::iterator longest_prefix_match_( uint32_t dst_ip );

  //static int match_length_( uint32_t src_ip, uint32_t tgt_ip, uint8_t tgt_len );
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
  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.
  void route();

  std::vector<Route_entry>::iterator longest_prefix_match_( uint32_t dst_ip );
  int match_length_( uint32_t src_ip, uint32_t tgt_ip, uint8_t tgt_len );
  // std::vector<Route_entry>::iterator longest_prefix_match_( uint32_t dst_ip );
  // int match_length_( uint32_t src_ip, uint32_t tgt_ip, uint8_t tgt_len );
};

router.cc

#include "router.hh"

#include <iostream>
#include <limits>
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.
// 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";

//   // (void)route_prefix;
//   // (void)prefix_length;
//   // (void)next_hop;
//   // (void)interface_num;

//   route_table_.emplace_back(route_prefix, prefix_length, next_hop, interface_num);
//   return;
// }

// void Router::route()
// {
//   for ( auto& current_interface : interfaces_ ) {
//     auto received_dgram = current_interface.maybe_receive();
//     if ( received_dgram.has_value() ) {
//       auto& dgram = received_dgram.value();
//       if ( dgram.header.ttl > 1 ) {
//         dgram.header.ttl--;
//         // NOTE: important!!!
//         dgram.header.compute_checksum();
//         auto dst_ip = dgram.header.dst;
//         auto it = longest_prefix_match_( dst_ip );
//         if ( it != route_table_.end() ) {
//           auto& target_interface = interface( it->interface_num );
//           target_interface.send_datagram( dgram, it->next_hop.value_or( Address::from_ipv4_numeric( dst_ip ) ) );
//         }
//       }
//     }
//   }
// }

// std::vector<Router::Route_entry>::iterator Router::longest_prefix_match_( uint32_t dst_ip )
// {
//   auto res = route_table_.end();
//   int max_length = 0;
//   for ( auto it = route_table_.begin(); it != route_table_.end(); ++it ) {
//     int len = match_length_( dst_ip, it->route_prefix, it->prefix_length );
//     if ( len > max_length ) {
//       max_length = len;
//       res = it;
//     }
//   }
//   return res;
// }

// int Router::match_length_( uint32_t src_ip, uint32_t tgt_ip, uint8_t tgt_len )
// {
//   if ( tgt_len == 0 ) {
//     return 0;
//   }

//   if ( tgt_len > 32 ) {
//     return -1;
//   }

//   // tgt_len < 32
//   uint8_t const len = 32U - tgt_len;
//   src_ip = src_ip >> len;
//   tgt_ip = tgt_ip >> len;
//   return src_ip == tgt_ip ? tgt_len : -1;
// }

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_table_.emplace_back( route_prefix, prefix_length, next_hop, interface_num );
}

void Router::route()
{
  for (uint32_t i=0; i<interfaces_.size();i++) {
    auto received_dgram = interface(i).maybe_receive();
    if ( received_dgram.has_value() ) {
      auto dgram = received_dgram.value();
      if ( dgram.header.ttl > 1 ) {
        dgram.header.ttl--;
        dgram.header.compute_checksum();
        auto dst_ip = dgram.header.dst;
        auto it = longest_prefix_match_( dst_ip );
        if ( it != route_table_.end() ) {
          //这里的bug
          interface( it->interface_num ).send_datagram( dgram, it->next_hop.value_or( Address::from_ipv4_numeric( dst_ip ) ) );
        }
      }
    }
  }
}

std::vector<Router::Route_entry>::iterator Router::longest_prefix_match_( uint32_t dst_ip )
{
  auto res = route_table_.end();
  int max_length = -1;
  for ( auto it = route_table_.begin(); it != route_table_.end(); ++it ) {
    int len = match_length_( dst_ip, it->route_prefix, it->prefix_length );
    if ( len > max_length ) {
      max_length = len;
      res = it;
    }
  }
  return res;
}

int Router::match_length_( uint32_t src_ip, uint32_t tgt_ip, uint8_t tgt_len )
{
  if ( tgt_len == 0 ) {
    return 0;
  }

  if ( tgt_len > 32 ) {
    return -1;
  }

  // tgt_len < 32
  uint8_t len = 32U - tgt_len;
  src_ip = src_ip >> len;
  tgt_ip = tgt_ip >> len;
  return src_ip == tgt_ip ? tgt_len : -1;
}

标签:tgt,ip,CS144,斯坦福,len,prefix,Lab5,interface,route
From: https://blog.csdn.net/qq_37293468/article/details/142796323

相关文章

  • 【斯坦福CS144】Lab2
    一、实验目的实现一个TCPReceiver,用以接收传入的TCPsegment并将其转换成用户可读的数据流。二、实验内容1.接收TCPsegment;2.重新组装字节流(包括EOF);3.确定应该发回给发送者的信号,以进行数据确认和流量控制。三、实验过程输入gitmergeorigin/check2-startercode......
  • 斯坦福:合成LLM持续预训练语料
    ......
  • 斯坦福大学2014机器学习教程中文笔记目录
    http://www.ai-start.com/ml2014/第一周一、引言(Introduction)1.1欢迎1.2机器学习是什么?1.3监督学习1.4无监督学习二、单变量线性回归(LinearRegressionwithOneVariable)2.1模型表示2.2代价函数2.3代价函数的直观理解I2.4代价函数的直观理解II2.5梯......
  • 探索人工智能的未来:埃里克·施密特2024斯坦福大学分享四
    一、语言模型的经济影响关于语言模型的经济影响,我想先谈谈市场的影响。我们看到一些服务领域的变化速度比预期的要慢,比如CHEG和其他相关服务的表现。对此,您是否认为学术界应该获得人工智能补贴?还是说,他们应该与大公司合作?我个人非常努力地推动为大学争取数据中心。如果......
  • 斯坦福大学深度解析:机器学习优化算法全攻略
    在全球人工智能研究的浪潮中,斯坦福大学以其卓越的学术成就和前沿的研究成果,一直站在该领域的前沿。今天,我们将深入探讨斯坦福大学关于机器学习优化算法的精华讲义,这份讲义不仅包含了丰富的理论知识,还有图解和Pytorch实现代码,是学习和实践机器学习优化算法的宝贵资源。↓↓↓......
  • 卷积神经网络--卷积层(斯坦福李飞飞学习笔记)
    卷积核对于图像分类任务,常见的卷积核(kernel)大小可以是3x3、5x5个像素点注意一下词汇的辨析:kernel是二维的,也就是每一层的卷积核大小;filter表示的是三维的,所以可以看到ppt里面的filter展示的是5*5*3,因为kernel的大小是5*5,同时放入的图像是RGB类型,总共3个像素层,所以三维的filt......
  • 【Linux详解】冯诺依曼架构 | 操作系统设计 | 斯坦福经典项目Pintos
    目录一.冯诺依曼体系结构(VonNeumannArchitecture)注意事项存储器的意义:缓冲数据流动示例二.操作系统(OperatingSystem)操作系统的概念操作系统的定位与目的操作系统的管理系统调用和库函数操作系统的管理:sum三.系统调用实现示例:Pintos项目Step1:进入ex......
  • GitHub星标破千!斯坦福大学的284个机器学习小抄(漫画中文版)
    说到人工智能必然要了解机器学习,从信息化软件,到电子商务,然后到高速发展互联网时代,到至今的云计算、大数据等,渗透到我们的生活、工作之中,在互联网的驱动下,人们更清晰的认识和使用数据,不仅仅是数据统计、分析,我们还强调数据挖掘、预测。机器学习就是对计算机一部分数据进行学习,......
  • 和斯坦福博士写代码的第 8个月
    不知不觉,和斯坦福博士在一起合作了8个月,记得在 和斯坦福博士写代码的一个月 这篇文章中,我谈了自己和他们合作第一个月的感受,今天再来聊聊和他们合作了8个月后最大的2个感受。语言是文化侵略的最好武器语言是文化侵略的最好武器在这8个月的合作中,感受最深的是语言是文化侵......
  • 斯坦福大学Mobile ALOHA——一款革命性的家政机器人
    https://www.bilibili.com/video/BV1nT421e7Cy/?spm_id_from=333.999.0.0随着社会老龄化问题的加剧,家政机器人成为了解决日常生活辅助需求的新方向。欢迎来了解MobileAloha家政机器人的技术原理和潜力——它将把你的家务活变成轻而易举的事。推动这款机器人功能的技术特点包......