C语言实现基于高效率IP路由查找的内容

野性酷女 2024-04-06 10:24 28阅读 0赞

## 基于高效率 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)` 函数 #####

### 结果验证 ###

#### 基本前缀树实验结果 ####

实验结果如下：

![在这里插入图片描述][c4bc58195919474d946dda8e8fe4cf26.png]

上图可知，实现基本前缀树所消耗的内存为 65863400 字节。所需要的查找时间（除去从 txt 中解析字符串的时间）为 118ns。

#### Leaf Pushing 实验结果 ####

实验结果如下：

![在这里插入图片描述][6f9f8dbfa3134dcaa3d7f96b89ffc233.png]

上图可知，实现基本前缀树所消耗的内存为 39518040 字节。所需要的查找时间（除去从 txt 中解析字符串的时间）为 117ns。

两者对比发现 Leaf Pushing 在存在很多路由表项插入的情况下，内存消耗减少 40%。但是时间减小的并不明显。这是因为存在很多路由表项来构建前缀树时，前缀树趋于完全，因此可以减少查询的次数不多。相较于通过算法进行改进，通过编译优化进行速度提升效果更高。

Leaf Pushing 开启 O2 编译优化的的结果如下：

![在这里插入图片描述][730a133559b24b718af0c02acf915d16.png]

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

[c4bc58195919474d946dda8e8fe4cf26.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/983a6f09ce764fbebdd3809eddad8242.png
[6f9f8dbfa3134dcaa3d7f96b89ffc233.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/ff2841d4c36f4876ae44a2fdef41c68e.png
[730a133559b24b718af0c02acf915d16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/657913e6417442518a704af12234e5d3.png