P10348 [THUSC 2019] RIP 路由协议实现

支持了链路层和网络层的协议以后，路由器立刻了收到无数的数据包。虽然芃芃被大量的数据淹没，不过镇定的他还是记起来教材上写的话：网络设备能够处理的报文有两种，分别是控制报文和数据报文。对于路由器来说，数据报文就是需要转发的内容；而控制报文则是用来管理它的转发流向（路由表）的。为了和其他真实的路由器进行交互，你需要实现简单的路由协议 RIP；而在建立了转发表之后，需要开始进行“抛热土豆”，正确地将其他主机的流量送到对应的下一台路由器。

你需要根据《学习手册》中的相关知识，处理下列两类报文： 一类是 RIP 路由协议的控制报文，它被封装在 UDP 协议数据报中。你将只会收到 `RIP Response` 报文，且目标 IP 地址是 `224.0.0.9`，目标 MAC 地址为 `01:00:5E:00:00:09`，用于指示路由表的更新，你需要根据源 IP 地址来判断它与你拥有的哪一个 IP 在同一个子网中，从而得知路由表中对应的出端口编号。对于收到的每一条路由信息，你需要根据给定的规则（见《学习手册》）恰当维护自身的路由表，记录对于可达的每一个网络前缀的下一跳信息（包括 IP 和 MAC）。对于控制报文，总是无需进行回复。 另一类是数据报文，它将被封装在 IP 分组中，你需要对**目标 IP 地址非本机所拥有**的分组进行转发。如果路由表中能够查询到目标 IP 地址对应的下一跳，则你应当构造一个合法的 IP 分组，填写正确的源、目标信息，并更新相关字段（如 TTL、校验和）；如果无法查询到路由信息，则你应当构造一个正确的 `ICMP Destination Network Unreachable` 报文返回给源主机；如果分组的 TTL 减小到 0，则你应当构造一个正确的 `ICMP Time Exceeded` 报文返回给源主机，这两种错误信息都需要按照《学习手册》的要求填入相应的负载，从接收者 MAC 地址中推断出源地址 IP ，并且以太网帧中（接收者的 MAC 地址，发送者的 MAC 地址）为输入数据中对应数据报文的（发送者的 MAC 地址，接收者的 MAC 地址）；如果同时出现无法查询到路由信息并且 TTL 减到 0 的情况，应当构造一个 `ICMP Destination Network Unreachable`。无论何种情况，对于一个目标 IP 地址不属于本机的数据报文，你实现的路由器**总会产生**一个发出的以太网帧。 由于转发报文需要填写下一跳的 MAC 地址，而我们不提供主动的 ARP 查询接口；在本小题中，你需要并仅从 RIP 报文的**以太网帧头**中获得相应目的路由器的 MAC 地址，以**转发前最后一次获得到的为准** 。 我们保证，在此问题给出的正常流量片段（也就是通过了校验的片段）中，包含且只包含上述两类报文；并且对于所有需要转发的包，你都能通过上述方法从 RIP 报文中获得对应目的路由器的 MAC 地址。和上题类似，Wireshark 会显示 UDP 校验值错误，忽略即可。

输入包含不超过 $n$ 个流量片段，总大小不超过 $m$ 字节。根据输入，你需要构造的路由表的项目不超过 $k$ 条，需要查询路由表进行转发的报文占总报文的数量约为 $p_{query}\%$。

你的输出将与答案文件进行**逐字节**对比。请不要输出任何多余信息，以免导致不必要的失分。

**【子任务】** | 测试点 | $n$ | $m$ | $k$ | $p_{query}$ | | :--: | :--: | :--: | :--: | :--: | | 1 | $=10^2$ | $=1.5\times 10^5$ | $=10$ | $=50\%$ | | 2 | $=10^3$ | $=1.5\times 10^6$ | $=10^2$ | $=50\%$ | | 3 | $=10^3$ | $=1.5\times 10^6$ | $=10^2$ | $=95\%$ | | 4 | $=10^4$ | $=1.5\times 10^7$ | $=10^3$ | $=50\%$ | | 5 | $=10^4$ | $=1.5\times 10^7$ | $=10^3$ | $=95\%$ | | 6 | $=10^5$ | $=2\times 10^7$ | $=10^4$ | $=95\%$ | | 7 | $=10^5$ | $=2\times 10^7$ | $=10^4$ | $=95\%$ | | 8 | $=10^6$ | $=2\times 10^8$ | $=10^5$ | $=95\%$ | | 9 | $=10^6$ | $=2\times 10^8$ | $=10^5$ | $=95\%$ | | 10 | $=10^6$ | $=2\times 10^8$ | $=10^5$ | $=95\%$ | **【样例 1】** 见题目附件 `1.in/ans`。 **【样例解释 1】** 样例输入有十个以太网帧，包括八个 RIP 包和两个需要转发的 IP 包。 对于前四个 RIP Response，可以得到如下的路由表： 收到第一个 Response 后： ``` 104.0.0.0/6 via 10.2.7.2 if 7 metric 7 13.115.192.0/18 via 10.2.7.2 if 7 metric 9 224.0.0.0/3 via 10.2.7.2 if 7 metric 15 ``` 收到第二个 Response 后： ``` 104.0.0.0/6 via 10.2.7.2 if 7 metric 7 13.115.192.0/18 via 10.2.7.2 if 7 metric 9 ``` 收到第三个 Response 后： ``` 104.0.0.0/6 via 10.2.7.2 if 7 metric 7 13.115.192.0/18 via 10.2.7.2 if 7 metric 9 88.128.0.0/10 via 10.2.6.2 if 6 metric 13 ``` 收到第四个 Response 后： ``` 104.0.0.0/6 via 10.2.7.2 if 7 metric 7 88.128.0.0/10 via 10.2.6.2 if 6 metric 13 ``` 接着是两个 UDP 包，对于 `77.147.142.166` 这个地址，在路由表中没有对应的项，于是回应了 `ICMP Destination unreachable` 。对于 `107.28.70.129` 地址，它在 `104.0.0.0/6` 范围中，于是 TTL 减一并且转发到 `10.2.7.2` ，它的 MAC 地址可以从第一个 `RIP Response` 得到。 收到第五个 Response 后： ``` 104.0.0.0/6 via 10.2.7.2 if 7 metric 7 88.128.0.0/10 via 10.2.6.2 if 6 metric 13 130.127.0.0/17 via 10.2.4.2 if 4 metric 3 ``` 收到第六个 Response 后： ``` 130.127.0.0/17 via 10.2.4.2 if 4 metric 3 ``` 收到第七个 Response 后： ``` 130.127.0.0/17 via 10.2.4.2 if 4 metric 3 160.245.176.0/20 via 10.2.5.2 if 5 metric 9 ``` 收到第八个 Response 后： ``` 130.127.0.0/17 via 10.2.4.2 if 4 metric 3 160.245.176.0/20 via 10.2.5.2 if 5 metric 9 90.32.0.0/15 via 10.2.5.2 if 5 metric 8 ``` **【提示】** 由于每个数据报文的转发都需要查询路由表，因此需要用高效的数据结构存储路由表中的关键信息，同时也要注意空间的使用效率。关于算法的高效实现，你可以参考《学习手册》附带的相关论文和资料。 在转发 IP 分组时，分组头内很少的字段会被修改。因此 IP 校验值也未必需要重新计算，很多情况下可以只进行最小限度的改动。但如果你想进行任何形式的简化，务必保证你的操作与我们叙述的操作是**完全等价**的。直观的想法往往会遗漏一些边界情况，请一定注意。