学位论文 > 优秀研究生学位论文题录展示

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

作　者: 尹青
导　师: 迟乐军
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: 数据包分类访问控制列表变步长trie树动态更新
分类号: TP393.07
类　型: 硕士论文
年　份: 2008年
下　载: 16次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  4-5
Abstract  5-9
第1章绪论  9-14
  1.1 课题来源  9
  1.2 课题背景和研究意义  9-10
  1.3 国内外研究现状  10-11
  1.4 课题研究的主要内容  11-12
    1.4.1 访问控制列表特征的研究  12
    1.4.2 动态数据包分类算法的研究  12
  1.5 论文主要内容和组织结构  12-14
第2章数据包分类技术分析  14-27
  2.1 数据包分类问题的描述  14-23
    2.1.1 数据包分类问题的基本定义  14-15
    2.1.2 数据包分类问题的解决思路  15-16
    2.1.3 数据包分类问题的评价标准  16
    2.1.4 数据包分类代表性算法介绍  16-23
  2.2 数据包分类系统概要设计  23-26
    2.2.1 设计思路  23-25
    2.2.2 技术难点  25-26
  2.3 本章小结  26-27
第3章基于变步长Trie树的动态数据包分类算法  27-41
  3.1 访问控制列表及其特征的研究  27-29
    3.1.1 访问控制列表介绍  27-28
    3.1.2 规则域分布特征研究  28-29
  3.2 基于trie树结构的Cstrie算法  29-38
    3.2.1 基于trie树算法特征分析  29-30
    3.2.2 使用通配符方式处理带掩码规则  30-31
    3.2.3 基于变步长trie树的Cstrie算法特征  31
    3.2.4 Cstrie算法设计思路  31-32
    3.2.5 建立Cstrie算法的变步长trie树  32-34
    3.2.6 数据包查询过程  34-36
    3.2.7 规则插入过程  36-37
    3.2.8 规则删除过程  37-38
  3.3 主要数据结构设计  38-40
  3.4 本章小结  40-41
第4章动态数据包分类Cstrie算法评测分析  41-50
  4.1 数据包分类算法评测平台  41
  4.2 数据包分类算法评测工具  41-42
  4.3 数据包分类算法评测结果  42-49
    4.3.1 算法预处理时间评测  42-43
    4.3.2 算法内存占用评测  43-45
    4.3.3 算法平均访存次数评测  45-46
    4.3.4 算法最坏访存次数评测  46-47
    4.3.5 数据包分类算法评测结论  47-49
  4.4 本章小结  49-50
第5章数据包分类系统的实现与运行效果  50-61
  5.1 数据包分类系统总体设计  50-52
  5.2 数据包分类系统——UPCS的实现  52-59
    5.2.1 采用LFS技术构建Linux操作系统  52-54
    5.2.2 访问控制规则XML文件解析端实现  54-56
    5.2.3 基于Netfilter框架的Linux内核模块编写  56-57
    5.2.4 Linux内核网络协议栈部分的修改  57-59
  5.3 数据包分类系统运行效果  59-60
  5.4 本章小结  60-61
结论  61-62
参考文献  62-67
致谢  67

相似论文

地域特征与旧城更新设计初探,TU984.114
普适计算中动态更新及其形式化研究,TP338
云计算环境下可证明数据持有技术研究,TN918.2
基于统计学方法的击键动态认证技术的研究,TP393.08
滇中云南松林火烧五年后植物群落动态及其演替趋势,S718.5
基于覆盖粗糙集模型下的近似集动态更新方法研究,TP18
基于SSH和JBPM的西南交大网络教育学院综合管理信息系统的设计与实现,TP311.52
城市土地集约利用评价系统应用研究,F301
船舶作业分配计划系统的设计与实现,TP311.52
一种改进的XML数据管理方案,TP311.13
HIC：一种混合完整性控制的设计与实现,TP309
Java程序动态更新的研究,TP311.10
基于NDIS中间层的Windows平台下包分类算法的研究,TP393.08
对象文件系统访问控制列表机制的设计与实现,TP393.08
基于DSL的动态更新策略描述与实现,TP311.52
基于OSGi的两阶段动态软件更新,TP311.53
IPv6环境下基于DNS自动更新的域名访问控制系统,TP393.09
模块化业务动态更新平台的设计与实现,TP311.52
汽车总装线MES技术的研究,TP311.52
Linux操作系统访问控制安全研究与实现,TP309