[THUSC 2019] PCAP 文件解析与读写

所有题目中，网络流量都将以 PCAP 文件格式保存，具体格式说明可参见《学习手册》。本题需要对 PCAP 文件进行基本的读写与解析。 在本题中，你需要完成的任务是依次遍历输入文件中时间乱序的流量片段，在对它们进行一些操作后，组装为 PCAP 格式写入输出。关于文件的读写方式，可以参照《学习手册》。 需要进行的操作为：只保留长度**不大于** $1000$ 的片段（只考虑完整的以太网帧长度，不包括 PCAP 格式的片段头），并按照时间升序排序这些片段（即首先比较秒，而后比较微秒），保证没有两个片段的时间是相同的。需要注意，你的输出文件需要是一个合法的 PCAP 文件。为了测试文件格式的合法性，你可以使用 Wireshark 等工具打开你的输出文件进行检查。 与手册中指示的不同的是，本题中，你应该直接完整复制每个流量片段的头，包括时间戳字段。 ## Input 输入包含不超过 $n$ 个流量片段，总大小不超过 $m$ 字节。 ## Output 你的输出将与答案文件进行**逐字节**对比。请不要输出任何多余信息，以免导致不必要的失分。 [samples] ## Background 说明：请从题目附件下载试题题面所提及的《学习手册》。自本题起的五题，为 THUSC 2019 第三试《网络流量分析与处理》的五小题。原试题共六小题，其中最后一题为反馈，不再收入。 --- 芃芃是华清大学计算机系的一名学生，马上读大二上学期。由于他精通 OI，觉得这个学期的唯一一门专业课《数据结构》实在是太简单了。在学长杰哥的盛情推荐下，他提前选了大三的专业课《计算机网络原理》。然而，这门课程的大作业是自己动手实现一个软件路由器，这可难倒了没有工程经验的芃芃。为了不让杰哥失望，他决定在暑假里就提前完成这个任务。 本题一共分为 6 个小题，难度递增。你将与芃芃一起学习网络的基本原理、网络设备的工作方式，并亲手实现一个个功能，最终完成一个简化版的路由器软件。麻雀虽小，五脏俱全，它将能对多种基本的网络协议进行处理，并担任起路由器最根本的使命——转发。 在本题**所有的小题**中，我们都有以下的约定： * 你的计算机上有 16 个网络接口，编号从 1 到 16。 * 你的计算机上默认的路由表为空，并且只能从 RIP 报文获得路由表的更新。 * 每个接口对应**一个** IP 地址 `10.2.n.1/24`，其中 $n$ 代表接口编号，范围是 1 到 16。 * 每个接口对应一个 MAC 地址 `98:01:29:00:00:xx`，其中 `xx` 是接口编号的 16 进制表示，范围是 $01_{16}$ 到 $10_{16}$。 * 所有的流量片段，包括读取和写入的，都是以太网帧（包括帧头和帧尾的校验），包含完整的协议格式。 * 除特殊说明外，输入的 PCAP 文件中的流量片段都是按照时间顺序排列的（时间戳单调递增），只需要进行依次处理即可。 如果你不能理解上述的约定，请参见《学习手册》网络基础相关部分。 ## Note **【子任务】** | 测试点 | $n$ | $m$ | |:--:|:--:|:--:| | 1 | $=10^2$ | $=5\times 10^4$ | | 2 | $=10^2$ | $=1.5\times 10^5$ | | 3 | $=10^3$ | $=1.5\times 10^6$ | | 4 | $=10^4$ | $=1.5\times 10^7$ | | 5 | $=10^5$ | $=1.5\times 10^8$ | **【样例 1】** 见题目附件 `1.in/ans`。 **【样例解释 1】** 你可以用你电脑上安装的 Wireshark 软件打开样例数据的输入和输出。 用 Wireshark 打开样例输入文件，应该可以看到，界面上部记录了这个 PCAP 文件中记录的所有以太网帧，界面中部显示的是当前这个以太网帧的解析，下部则是它的十六进制数据。对于这个软件的详细使用方法，除了部分题目给出的提示外，不会提供更多帮助，请选手自行熟悉并摸索。 样例输入文件记录了两个以太网帧，都是从 `10.2.254.100` 发往 `10.2.12.82` 地址的 ARP 请求，它们区别在于 ARP 请求后多余的数据长度不同。由于第一个帧的长度不大于 1000 ，第二个帧的长度大于 1000，按照题目意思，只有第一个帧需要输出，排序后输出到了样例输出文件中，你可以同样地用 Wireshark 打开样例输出文件来验证这一点。