基于变步长Trie树的数据包分类技术的研究与实现

摘要

数据包分类技术是网络管理的基础技术，尤其在网络访问控制以及面向网络业务的Qos控制中发挥着至关重要的作用。
　　目前已有的数据包分类算法面向静态规则算法，其研究目标主要集中在加快数据包匹配的速度上。而面向统一威胁管理目标的网络安全系统则大部分由多个部件联动形成，访问控制规则分发多以自动联动的模式工作，规则动态更新的数量和频率比以前有了极大的提高,更新的速度对于网络安全防护系统的性能有着重要的影响。
　　本文首先从分析访问控制列表出发，研究规则库特征，根据访问控制规则的分布特点，提出基于变步长trie树的数据包分类算法。该算法使用变步长trie树结构，根据规则集合中的源地址域，选择合适的渐变步长，建立查找树。由于采用变步长trie树结构，大大减少了查询过程中的访存操作。在此基础上，结合线性链表，散列表以及二叉查找树结构，可快速构建基于变步长trie树的复合式查找树结构。使得该算法在保持较高的数据包分类速度的同时，可以快速添加和删除访问控制规则，达到动态更新规则库的目的。最后，本文将详细介绍采用该算法的基于专用Linux系统平台的数据包分类系统，该系统运行稳定，并取得了较好的应用效果。
　　与同类算法的量化测试评估实验表明，本文提出的算法具有明显的性能提升，尤其在平均访存次数和规则构建速度上具有明显的优势，其中：在内存占用处于可接受范围内的情况下，该算法比预处理时间最优的EGT-PC算法减少了60％时间耗费。平均访问次数则与该项指标较优的Hicuts算法以及RFC算法持平。而最坏访存次数在5000条规则以下的规则集评测中，比EGT-PC算法减少了50%，在10000条规则以上的规则集评测中，与Hicuts算法接近。此外，采用该算法的数据包分类系统，作为网络安全防护体系中的联动部件，在实际应用中表现良好。

目录

基于变步长Trie树的数据包分类技术的研究与实现

RESEARCH AND IMPLEMENTATION OF PACKET CLASSIFICATION TECHNIQUE BASED ON VARIED STEP TRIE

摘要

Abstract

第1章 绪论

1.1 课题来源

1.2 课题背景和研究意义

1.3 国内外研究现状

1.4 课题研究的主要内容

1.4.1 访问控制列表特征的研究

1.4.2 动态数据包分类算法的研究

1.5 论文主要内容和组织结构

第2章 数据包分类技术分析

2.1 数据包分类问题的描述

2.1.1 数据包分类问题的基本定义

2.1.2 数据包分类问题的解决思路

2.1.3 数据包分类问题的评价标准

2.1.4 数据包分类代表性算法介绍

2.2 数据包分类系统概要设计

2.2.1 设计思路

2.2.2 技术难点

2.3 本章小结

第3章 基于变步长Trie树的动态数据包分类算法

3.1 访问控制列表及其特征的研究

3.1.1 访问控制列表介绍

3.1.2 规则域分布特征研究

3.2 基于trie树结构的Cstrie算法

3.2.1 基于trie树算法特征分析

3.2.2 使用通配符方式处理带掩码规则

3.2.3 基于变步长trie树的Cstrie算法特征

3.2.4 Cstrie算法设计思路

3.2.5 建立Cstrie算法的变步长trie树

3.2.6 数据包查询过程

3.2.7 规则插入过程

3.2.8 规则删除过程

3.3 主要数据结构设计

3.4 本章小结

第4章 动态数据包分类Cstrie算法评测分析

4.1 数据包分类算法评测平台

4.2 数据包分类算法评测工具

4.3 数据包分类算法评测结果

4.3.1 算法预处理时间评测

4.3.2 算法内存占用评测

4.3.3 算法平均访存次数评测

4.3.4 算法最坏访存次数评测

4.3.5 数据包分类算法评测结论

4.4 本章小结

第5章 数据包分类系统的实现与运行效果

5.1 数据包分类系统总体设计

5.2 数据包分类系统——UPCS的实现

5.2.1 采用LFS技术构建Linux操作系统

5.2.2 访问控制规则XML文件解析端实现

5.2.3 基于Netfilter框架的Linux内核模块编写

5.2.4 Linux内核网络协议栈部分的修改

5.3 数据包分类系统运行效果

5.4 本章小结

结 论

参考文献

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

哈尔滨工业大学硕士学位涉密论文管理

致谢