CS144 lab5~6

最后两个lab了，虽然很多大佬都说剩下的两个lab比起TCP的实现，“简直太简单了”，但是我认为做这两个之前需要补充一些额外的网络知识，不然直接上手去做的话，难度也是不小的。我举一个简单的例子，lab6中有一个函数需要我们实现：add_route()，这个函数的4个参数分别是 route_prefix，prefix_length，next_hop，interface_num，如果不了解IP地址和子网掩码的概念，可能连前2个参数为什么这么起名都理解不了，更别提写lab了。

这里建议可以阅读《网络是如何连接的》第二、三章的内容。

CS144 lab5：ARP协议

这个lab要求实现ARP协议，ARP协议（Address Resolution Protocol）可以将IP地址解析为MAC地址。在数据包发送前，主机需要知道目标主机的MAC地址才能发送数据包。ARP协议通过广播询问网络上其他主机的MAC地址，从而获取目标主机的MAC地址。

0.概述与思路

一个以太网帧：

A端点接到了一个B端点发来的以太网帧后做的事：

分析mac头部的协议，判断以太类型是 IP协议 or ARP协议

IP协议：按照IP协议提取报文即可。（推到队列稍后检索什么意思，后需要做的事是下一个lab的内容）

ARP协议：(本 lab 要实现的)

1. 先缓存B端点的 ip_addr : MAC_addr
2. 判断这是一个ARP request 还是 ARP reply：
   • ARP request：满足你，给B端点返回一个ARP reply，告诉B端点A的mac地址。
   • ARP reply：说明B端点回复了自己的MAC地址，查看A端点是否有需要发送给B端点的以太网帧，有的话就包装为以太网帧（填上B的MAC地址）发送。（之前无法发送是因为没有B端点的MAC地址，所以程序中要设计一个map，key是ip地址，value一个waiting_list，waiting_list中是需要发送给这个ip的报文）
   • 关于上一点map的详细说明：如果A端点给B端点要发送一个以太网帧，现在已知了A的ip和mac、B的ip，接下来只需要知道B的mac就可以成功发送。
     1. 若B的ip:mac已经缓存在A的arp_cache中，则查询缓存即可得到，然后可以顺利发送
     2. 若B的mac没有缓存，就需要先把这个ip：datagram 放入waiting_list中，然后向同一以太网中所有设备发送ARP request广播，等待ARP reply到达后，再把waiting_list中的datagram取出来发送。（在ARP relpy到达前可能还有发送到B的若干以太网帧，所以需要缓存）

1.关于需要注意的时间问题

ARP协议的实现中，有两处需要注意的时间问题。

1. ARP的缓存要要超时机制

   //caching_time超过30秒要从 _cahce中清除
   std::map<uint32_t, EthernetAddressEntry> _cache{};
   struct EthernetAddressEntry {
         size_t caching_time;
         EthernetAddress MAC_address;
   };
   
   

2. 发送 APR request 前要检查 time_since_last_ARP_request_send，如果小于5s，就不发送。

   std::map<uint32_t, WaitingList> _queue_map{};
   struct WaitingList {
         size_t time_since_last_ARP_request_send = 0;
         std::queue<InternetDatagram> waiting_datagram{};
    };
   

CS144 LAB6 IP Router

0.概述

lab6要求实现一个“路由器”。

回顾一下，lab5已经实现了一个网络接口，这个接口具有接收和发送以太帧的功能：

1. 接收以太帧：接收到以太帧后，如果该帧是ARP协议，则根据ARP request 或者ARP reply进行不同的动作；如果是IP协议，无动作（这正是留给lab6做的）。
2. 发送以太帧：将IP包添加MAC头后，发送出去。

所以lab6的路由器最重要的功能就是路由匹配：接收到IP协议的以太帧后，丢掉旧的MAC头部，取出其中的IP包，对IP包进行路由匹配，然后调用网络接口的发送方法，装上新的MAC头后发送。

其中路由匹配的含义是：根据IP包要发送的目标IP地址，对比路由表中的各项，从而查询得到下一跳路由器的IP地址。

1.查询路由表的过程：

路由器匹配时会忽略主机号，只匹配网络号，一个路由表如下所示：（这里是为了和lab中的路由表对应，实际不止这么多项）

lab中已经给出了add_route()函数的4个参数分别是 route_prefix，prefix_length，next_hop，interface_num，含义分别是 目的网络地址、子网掩码中连续1的长度、下一跳IP、接口号，含义分别是：

• route_prefix：直译为“路由前缀”，含义是IP地址的网络号，用来标识一个网络，之所以用“前缀”，是因为IP地址分为网络号和主机号，网络号处于IP地址的前缀部分。
• prefix_length：前缀长度，是指子网掩码中，连续1的长度，之所以叫前缀长度，是因为 （IP & 子网掩码 = 网络号），
• next_hop：下一跳的IP地址，是我们要查询的内容。
• interface_num：接口号，一个路由器可以有n个接口，每个接口可以发往不同IP地址，而是我们想查询的内容。

匹配时需要将目的IP地址和表中的子网掩码按位与，得到的结果与目的网络号比较，若一致则匹配成功，另外lab doc中讲到：If the router is directly attached to the network in question, the next hop will be an empty optional ,In that case, the next hop is the datagram’s destination address. .所以如果 next_hop 为空，说明目的IP就和本router直接相连，选择目的IP直接发送就好~

int match_index = -1;
//遍历路由表
for (size_t i = 0; i < _routing_table.size(); i++) {
    auto mask = numeric_limits<int>::min()>>(_routing_table[i] - 1);
    if ((dst_ip_addr & mask) == _routing_table[i]._route_prefix) {
    	//匹配成功
        match_index = i;
	} 
}

if(match_index == -1) {
    //发送ICMP，但是lab6不要求
}

//路由匹配完成：得到了下一跳的 IP地址 和 接口号
auto next_hop = _routing_table[match_index]._next_hop;
auto interface_num = _routing_table[match_index]._interface_num;

if (next_hop.has_value()) {
    _interfaces[interface_num].send_datagram(dgram, next_hop.value());
} else {
    //
    _interfaces[interface_num].send_datagram(dgram, Address::from_ipv4_numeric(dst_ip_addr));
}

2.TTL到底是秒数还是跳数？

在几乎所有的TTL中文资料中，都会讲到每经过一个路由器，TTL就会减1，所以TTL的含义是路由器的跳数，当减为0时，这个包会被抛弃，但是TTL是time to live，怎么和跳数联系到一起呢？为此，我查阅了RFC791，里面讲到：

也就是说，TTL的定义的确是秒，每经过一个路由器，处理时间小于1秒，也会按照1s计算，那处理时间是2s、3s是不是就要-2、-3了呢？是的，从TCP协议规定来看，作者是想要-2、-3的，但是从编码实现角度考虑，需要计算每个包在router之间传输的时间，个人猜测，很可能是牺牲了这部分时间精度，选择粗暴地每次都减1，以换来编码实现的简化。

维基百科中也提到了，实际的实现中都是每次减1，所以为了照顾这种实现，TCP协议在IPv6中已经将TTL改名为hop limit，哈哈哈，感觉还是很有意思的，协议的制定者为了协议的实现者而妥协，很有趣，不是么~

3.结尾

历时4周吧，终于写完了CS144，除了lab4花费一周时间，其余lab均花费约半周的时间，这种沉浸式体验的感觉还是很好的，吃饭，走路的时候脑子里都在想着这些lab，实在是太爽了，截止到目前为止，已经完成了CSAPP、MIT6.S081、CS144的所有lab，下一门向CMU15-445进发~