C语言实现基于高效率IP路由查找的内容
基于高效率 IP 路由查找的内容
实验内容
实验内容一
实现最基本的前缀树查找
实验内容二
调研并实现某种 IP 前缀查找方案
测试与验证
-
基于 forwarding-table.txt 数据集(Network, Prefix Length, Port)
-
本实验只考虑静态数据集，不考虑表的添加或更新
-
以前缀树查找结果为基准，检查所实现的 IP 前缀查找是否正确
- 可以将 forwarding-table.txt 中的 IP 地址作为查找的输入
-
对比基本前缀树和所实现 IP 前缀查找的性能
- 内存开销、平均单次查找时间
设计思路
最基本的前缀树查找
RouterEntry* line_parser (char * line) 函数
负责将 txt 文件中读取的每一行字符串，转换成路由表项，返回 RouterEntry*，每一个路由表项结构包括三个变量，分别是网络号，掩码长度以及转发端口号。
int net_parser(char * s) 函数
负责将网络号从字符串类型，转换成一个 int 类型。
TreeNode * init_tree() 函数
初始化树结构，即建立一个树的根节点，并返回根节点。
int add_node (RouterEntry* entry) 函数
结果验证
基本前缀树实验结果
实验结果如下：
上图可知，实现基本前缀树所消耗的内存为 65863400 字节。所需要的查找时间（除去从 txt 中解析字符串的时间）为 118ns。
Leaf Pushing 实验结果
实验结果如下：
上图可知，实现基本前缀树所消耗的内存为 39518040 字节。所需要的查找时间（除去从 txt 中解析字符串的时间）为 117ns。
两者对比发现 Leaf Pushing 在存在很多路由表项插入的情况下，内存消耗减少 40%。但是时间减小的并不明显。这是因为存在很多路由表项来构建前缀树时，前缀树趋于完全，因此可以减少查询的次数不多。相较于通过算法进行改进，通过编译优化进行速度提升效果更高。
Leaf Pushing 开启 O2 编译优化的的结果如下：
可以看到此时通过对控制流和指令排布调度等方面的优化，查找的处理速度提高了一个数量级。