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 编译优化的的结果如下：

可以看到此时通过对控制流和指令排布调度等方面的优化，查找的处理速度提高了一个数量级。