第二次寒假作业_简陋路由实现
第二次寒假作业_简陋路由实现
内容概要
| 这个作业属于哪个课程 | 2022面向对象程序设计 |
|---|---|
| 这个作业要求在哪里 | 第二次寒假作业 |
| 这个作业的目标 | 完成一个简单的路由程序 |
| 作业正文 | 如下 |
| 其他参考文献 | 无 |
前言
这次作业真的是一路磕磕绊绊完成的。一边研究(附上详细内容)，一边研究 Git 怎么用，还要学习计算机网络的一些基本知识。本来还想着用 C++ 来写这个作业的。最后研究半天还是没有搞懂面向对象的精髓所在，甚至不确定要把什么抽象成类。
最终，这份作业还是用的认识了一学期的老朋友 C 语言来完成的。没有用上复杂的数据结构设计，用的是单链表来管理路由规则。如果有时间的话，可以好好考虑一下其他更高效的数据结构。
这个是本次作业的 Github 仓库
如果有看到不完善的地方，欢迎来骂！??
前置知识
五元组
由 5 个基本元素组成，源IP地址，源端口，目的IP地址，目的端口和传输层协议。e.g.
| 源 IP 地址 | 源端口 | 目的 IP 地址 | 目的端口 | 传输层协议类型 |
|---|---|---|---|---|
| 192.168.1.1 | 10000 | 121.14.88.76 | 80 | TCP |
规则集
规则集是匹配规则的集合，以五元组的形式给出范围。e.g.
| 源 IP 地址 | 目的 IP 地址 | 源端口[范围] | 目的端口[范围] | 协议号[范围] | |
|---|---|---|---|---|---|
| 178.139.217.251/32 | 126.0.44.183/32 | 0 : 65535 | 1526 : 1526 | 0x06/0xFF | 暂时不考虑 |
/数字 表示这个 IP 地址的掩码位。
参考资料 CIDR地址块及其子网划分（内含原始IP地址分类及其子网划分的介绍）
注意 该程序中不考虑规则优先级，默认规则集中的规则按从高到底排列，即数据包在规则集中找到的第一个匹配的规则即是它的最佳匹配
数据集
数据集是数据包的集合。e.g.
| 源 IP 地址 | 目的 IP 地址 | 源端口 | 目的端口 | 协议号 |
|---|---|---|---|---|
| 2995509645 | 269990131 | 0 | 0 | 255 |
路由
用于转发数据包，实现网络互联。
根据上面提到的数据包的基本信息（如原地址、目标地址、端口、协议等等）匹配路由表，按规则来决定转发策略的过程。
程序设计思路
前期规划
预计目标
? 用 C++ 实现 完全没有用到 C++ 的特性...
? 算法优化 可以说是完全没有，这个版本是暴力算法实现的
? 配置 VS Code 实现多文件编译支持 具体过程参见
? 实现程序内部计算运行时间
? 调试模式支持
模块化设计
- 文件 IO
规则匹配算法优化路由表数据结构优化输出结果和样例的对比模块(用的 VS Code 自带文件比较)- IP类型转换模块 （在 core.h 里面了）
天呐，大部分都没有实现。??
最终实现
核心逻辑其实没啥东西，感觉最后代码里有一半写的是调试信息这种东西...
基本运行流程
graph LR id1(程序开始) --> id2[(读入匹配规则)] subgraph simple-router id2 --单链表存储--> id3[(读入数据)] id3 --> id4(匹配规则) id4 --> id5(写入文件) id5-->id6(释放链表) end id6 --> id7(程序结束)程序结构
main 主程序
config 配置信息
fileIO 文件 IO
core 程序核心
基本数据结构
下面是 core.h 文件中所有关于数据结构定义的代码
typedef struct
{
unsigned int start; // 开始
unsigned int end; // 结束
} RANGE; // 范围结构体
// Rule structures
typedef struct
{
unsigned int id;// 规则的唯一ID, 用作判断优先级
RANGE S_ip; // 原地址范围
RANGE D_ip; // 目标地址范围
RANGE S_port; // 源端口范围
RANGE D_port; // 目标端口范围
RANGE proto; // 协议号范围
} RULEItem; // 规则内容
typedef struct Rnode
{
RULEItem item; // 规则内容
struct Rnode *next; // 规则下一个节点的指针
} RULENode; // 规则节点
typedef RULENode * RULEList; // 规则链表
// Data structures
typedef struct
{
unsigned int S_ip; // 原地址
unsigned int D_ip; // 目标地址
unsigned int S_port; // 源端口
unsigned int D_port; // 目标端口
unsigned int proto; //协议号
} DATA; // 数据结构体
这个作业中的程序有两个主要的数据结构，规则RULE 和 数据DATA
其中 规则RULE 的存储用到了单链表，数据DATA 则是一个普通的结构体。
此外，我还将频繁用到的 范围 这个概念抽象成了 RANGE 以便后续结构体的调用。
关于 规则RULE 的链表结构
这里有两方面考虑。
一方面，根据程序目标要求，链表作为线性表，其内部节点的存储是有顺序的。在匹配第一条之后就不用再往后继续匹配了，直接输出结果就好。这样可以稍微节省一点时间。
另一方面考虑是，采用链表他有一个动态内存分配特性，如果用数组的话因为栈内存比较小，万一遇到大量的规则会爆内存。 (写到这里仔细想了一下，用 malloc 好像是可以规避这个问题的诶...)
我抽象出了这样的结构用来实现规则的单链表存储，以便于后续的检索。
classDiagram direction LR class 规则 Node0{ RULEItem 规则内容 .指针(规则Node ~1~) } class 规则 Node1{ RULEItem 规则内容 .指针(规则Node ~2~) } 规则 Node0--o规则 Node1 : 指向下一条规则 规则 Node1--o 下一条规则 : 指向下一条规则关于 数据DATA
我根据 前置知识 中的需要设置了包含有以下成员的结构体。
- 原地址
- 目标地址
- 源端口
- 目标端口
- 协议号
（具体参见上面的源代码）
主程序
main.c 运行流程如下。
graph LR id1(程序开始) --> id2[(读入匹配规则)] subgraph simple-router id2 --单链表存储--> id3[(读入数据)] id3 --> id4(匹配规则) id4 --> id5(写入文件) id5-->id6(释放链表) end id6 --> id7(程序结束)配置文件
config.h 中主要定义了程序
- 报错信息返回值
- 提示信息返回值
- 程序主要参数(详细见下)
// 报错信息返回值 略
// 提示信息返回值 略
#ifndef CONFIG____
#define CONFIG____
#define PROGRAM_NAME "simple-router" // 程序名字
#define DEBUG_RULE_DIR "debug-rule" // 调试调用的规则文件
#define DEBUG_DATA_DIR "debug-data" // 调试调用的数据文件
#define RESULTFILE_NAME "ans" // 输出结果的文件名
#define MAX_RULE 1000 // 最大支持规则数量
#define MAX_DATA 10000 // 最大支持数据包数量
#define DEBUGGING_MODE 0 // 调试模式开关
#endif
文件IO
简单的文件读入，没有什么好讲的。
程序核心
程序核心就一个核心函数 int MatchRule(DATA *input, RULEList rList)，写在 core.c 里面了。其他的函数就是一些基本的数据处理。
因为这个程序也就是暴力算法，没啥技术含量。
MatchRule 的伪代码如下。
int MatchRule(数据包信息, 规则链表头)
{
结果 = -1;
while (是否到链表末尾)
{
if (是否匹配规则)
{
结果 = 规则 id;
结束循环;
}
更新链表为下一个节点;
}
return 结果;
}
没啥好说的，完全是暴力算法。
首先从 data 文件中读入一条数据包信息，
依次将 源/目标 IP 地址，源/目标 端口，协议号与内存中的 规则 进行逐条匹配。
匹配成功 返回 规则id
匹配失败 返回 -1
其余详细代码参见 Github 仓库。
性能测试
使用作业中提供的 测试数据 (大约 1k 条规则以及 1w 个数据包)
PS D:\Projects\simple-router-repo\build> .\simple-router.exe .\debug-rule .\debug-data
INFO: Start to read rule.
INFO: Start to match.
INFO: Read 9191 data in total, matched 9191/9191
=================
TIME (in cpu clock):
Read rule: 4
Match data: 35
我的笔记本的 CLOCKS_PER_SECOND 为 1000。
经过换算，大概就是在 40ms 左右能够完成路由工作。
如果打开编译器的 O3 优化 再进行编译，程序性能还能够有一定的提升。
PS D:\Projects\simple-router-repo\build> .\simple-router-O3.exe .\debug-rule .\debug-data
INFO: Start to read rule.
INFO: Start to match.
INFO: Read 9191 data in total, matched 9191/9191
=================
TIME (in cpu clock):
Read rule: 4
Match data: 26
程序性能提升了 25%，使用测试集文件可以做到 30ms 完成。
优化方案
IP 地址类型转换优化
因为 规则文件 和 数据包文件 中的 IP 地址的格式不一致需要格式转换。
正好，int 类型的变量正好 4 bytes 用来存放 ipv4 的地址刚刚好。
因此，把所有的 IP 地址转换成 二进制数字 来比较会方便很多。
所有涉及到转换的函数，全部使用位运算，可以节省下不少的时间。
unsigned int ConvertIPToInt(char ip[])
{
unsigned int IPDecimal[4] = {0};
unsigned int resultIP = 0;
for (int i = 0; i < 4; i++)
{
resultIP += IPDecimal[i] << ((4 - i - 1) * 8);
}
return resultIP;
}
核心代码其实也就一句，按照 8 的倍数去操作十进制IP地址，直接加到结果变量上就可以了。
非常好用，用了都说好！
数据结构优化（未实现）
使用单链表虽然可以满足这个程序的需要，但是经过仔细分析后我发现。
因为，你不知道能够正确匹配数据包的规则具体在链表中的哪个位置，那么你就需要遍历一整个链表，才能够确认这个数据包分发的规则。因此这个暴力算法的时间复杂度很不稳定。
最好情况下 \(\Omega(1)\)
最差情况下 \(O(n)\) (\(n\)为规则数)
对于路由来说，一个数据包分发的时间是不稳定的。这显然是一种非常不理想的情况。
那么有没有其他的数据结构能够优化算法呢？
有！字典树（trie）可以实现非常稳定的检索速度。
顾名思义，字典树是将 26 个字母作为一层索引。假设说要在字典树中查找一个 \(n\) 位的单词，只要按字母一个一个去找。最多只需要 \(n\) 步就可以匹配到你需要的单词。
字典树显著的特点就是，字典树的检索时间是固定（线性）的。检索字典树的时间取决于你分层的层数 \(n\)。
在最好和最坏情况下 \(\Theta(1)\)
这样的特性能够极大地提升路由的检索速度，程序性能也能够大幅提升。
倘若推广到路由表上，或许可以对规则数据建立一个索引，分段索引规则表。比如说 8 位分一段，将一个 IP 地址分成四层。（和哈希表结合好不好更好一点）
然而，有舍才有得。这样高效的性能是用占用更大的内存空间和前期整理规则缓存的时间换来的。
不仅如此，使用这种数据结构就意味着失去了链表线性的特点。
我们不能够在匹配到第一个规则时就直接转发。而是要在整个树中匹配到所有符合的规则，并记录下来。在其中找到优先级最高的一项进行转发。
此外，我们还需要在规则中添加一个新的成员作为判断规则优先级的依据，用以选择所有匹配的规则中优先级最高的进行分发操作。
但即便如此，字典树也能节省下大量的时间。尤其是在处理更大量的路由表的时候，字典树的先天优势就会更加显著。
参考资料 哈希表和字典树的笔记 - CS50 (harvard.edu)
多线程匹配
如果能够用到上述说的字典树，也许就可以用到多线程去检索路由表。这样肯定是更快的。
但是我不会 ??
遗憾和缺陷
-
配置文件是硬编码在源代码中的，如要修改需要重新编译
-
没有使用 C++ 的新特性来完成程序
-
暴力算法实现，无优化
踩坑记录
include 自定义头文件报错
写头文件的时候记得用上 ifdef
否则后边其他文件里面引用的时候，会交叉引用。导致重复定义结构体，编译器报错。
参考资料 《C Primer Plus》
拆分仓库
整个程序本来是在 Github 上的一个私有仓库里面写的。
我本来是想保留原有的 commit，所以没有直接新建一个文件夹，想着能不能直接拆分仓库。
结果，仓库拆分，分支合并什么的搞得乱七八糟。
我也迷迷糊糊的，最后还是稀里糊涂拆出来了。
主要参考了下面的这个文档。
参考文档 Git 仓库拆拆拆 - SegmentFault 思否