CS 144 Lab Six -- building an IP router

---

对应课程视频: 【计算机网络】 斯坦福大学CS144课程

Lab Six 对应的PDF: Lab Checkpoint 5: building an IP router

---

引言

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

• 发送到哪个接口；
• 下一跳的IP地址 ；

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

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

图1：路由器包含多个网络接口，可以在其中任何一个接口上接收IP数据报。路由器将接收到的任何数据报转发到相应出站接口上的下一跳，路由表告诉路由器如何做出这个决定。

---

路由器的实现

AsyncNetworkInterface:

• 它是对 NetworkInterface 类的包装，用于使主机端接口变成异步的。
• 在原始的 NetworkInterface 类的基础上，AsyncNetworkInterface 将接收到的数据报保存在队列中，而不是立即返回给调用者，以便稍后检索。
• 同时，AsyncNetworkInterface 在其他方面与底层的 NetworkInterface 实现完全相同。

class AsyncNetworkInterface : public NetworkInterface {std::queue<InternetDatagram> _datagrams_out{};public:using NetworkInterface::NetworkInterface;//! Construct from a NetworkInterfaceAsyncNetworkInterface(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 framevoid recv_frame(const EthernetFrame &frame) {auto optional_dgram = NetworkInterface::recv_frame(frame);// 只会将IPV4数据报放入数据报接收队列中if (optional_dgram.has_value()) {_datagrams_out.push(std::move(optional_dgram.value()));}};//! Access queue of Internet datagrams that have been receivedstd::queue<InternetDatagram> &datagrams_out() { return _datagrams_out; }
};

这里的 Router 实现比较简单，只需实现一下 IP 最长匹配并将数据包转发即可：

Router.hh:

//! \brief 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{};//! Send a single datagram from the appropriate outbound interface to the next hop,//! as specified by the route with the longest prefix_length that matches the//! datagram's destination address.// 路由一个IP数据报void route_one_datagram(InternetDatagram &dgram);// 路由表条目struct RouterTableEntry {// 路由前缀const uint32_t route_prefix;// 前缀长度const uint8_t prefix_length;// 下一跳的IP地址const std::optional<Address> next_hop;// 对应哪一个网络接口const size_t interface_idx;};// 路由表std::vector<RouterTableEntry> _router_table{};public://! Add an interface to the router//! \param[in] 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(const size_t N) { return _interfaces.at(N); }//! Add a route (a forwarding rule)// 增加路由条目void add_route(const uint32_t route_prefix,const uint8_t prefix_length,const std::optional<Address> next_hop,const size_t interface_num);//! Route packets between the interfacesvoid route();
};

Router.cc:

• 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() << "/" << int(prefix_length)<< " => " << (next_hop.has_value() ? next_hop->ip() : "(direct)") << " on interface " << interface_num << "\n";_router_table.push_back({route_prefix, prefix_length, next_hop, interface_num});
}

• route_one_datagram： 根据路由表完成当前IP数据报的路由工作

//! \param[in] dgram The datagram to be routed
// 根据路由表进行路由
void Router::route_one_datagram(InternetDatagram &dgram) {// 获取目的ip地址const uint32_t dst_ip_addr = dgram.header().dst;auto max_matched_entry = _router_table.end();// 开始查询for (auto router_entry_iter = _router_table.begin(); router_entry_iter != _router_table.end();router_entry_iter++) {// 如果前缀匹配匹配长度为 0，或者前缀匹配相同if (router_entry_iter->prefix_length == 0 ||(router_entry_iter->route_prefix ^ dst_ip_addr) >> (32 - router_entry_iter->prefix_length) == 0) {// 如果条件符合，则更新最匹配的条目if (max_matched_entry == _router_table.end() ||max_matched_entry->prefix_length < router_entry_iter->prefix_length)max_matched_entry = router_entry_iter;}}// 将数据包 TTL 减去1// 如果存在最匹配的，并且数据包仍然存活，则将其转发if (max_matched_entry != _router_table.end() && dgram.header().ttl-- > 1) {// 获取下一条IP地址const optional<Address> next_hop = max_matched_entry->next_hop;// 获取对应的网络接口AsyncNetworkInterface &interface = _interfaces[max_matched_entry->interface_idx];// 目标主机是否位于与路由器相同的网络中。// 在这种情况下，下一跳字段可能为空，因为目标主机可以直接通过局域网访问，无需经过路由器。if (next_hop.has_value())// 交给NetworkInterface,将这个数据报发送出去interface.send_datagram(dgram, next_hop.value());else// 目的主机与路由器位于相同的网络中interface.send_datagram(dgram, Address::from_ipv4_numeric(dst_ip_addr));}// 其他情况下则丢弃该数据包
}

上面的代码中，next_hop.has_value() 为 false 表示没有下一跳（next hop）地址，即无法找到用于转发数据包的下一跳。这可能发生在以下情况下：

1. 直接连接目标主机： 路由表中可能存在直接连接目标主机的路由条目，也就是目标主机位于与路由器相同的网络中。在这种情况下，下一跳字段可能为空，因为目标主机可以直接通过局域网访问，无需经过路由器。

2. 默认路由： 路由表中通常会包含默认路由（default route），也称为默认网关（default gateway）。默认路由是指当没有更精确的路由匹配时，所有未知目标IP地址的数据包将会通过默认路由进行转发。在这种情况下，下一跳字段可能为空，因为默认路由指定了一个特定的网络接口，将数据包发送到该接口，由默认网关负责将数据包转发到外部网络。

需要注意的是，在实际网络中，路由表会根据网络拓扑和路由策略进行配置，以确保数据包能够正确地转发到目标。路由表中的路由条目根据目标网络地址的前缀匹配来确定数据包的转发规则。当无法找到匹配的路由条目时，数据包将根据默认路由进行转发，或者如果没有默认路由，则会被丢弃。

---

• Route: AsyncNetworkInterface会将接收到的IP数据报暂存在队列中，由Route方法负责从队列取出并进行路由

void Router::route() {// Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.// 依次遍历当前路由器内部每个网络接口,依次取出每个AsyncNetworkInterface的待传输队列datagrams_outfor (auto &interface : _interfaces) {auto &queue = interface.datagrams_out();// 如果待路由队列不为空,则依次取出进行路由while (not queue.empty()) {route_one_datagram(queue.front());queue.pop();}}
}

---

测试

这是 CS144 的测试网络拓扑：

测试结果:

---