高性能包分类算法研究

论文摘要

Internet发展到今天,连接到Internet的主机数量正在以前所未有的速度增长从而使得网络的流量逐年成倍地增长。这无疑对Internet服务质量提出了新的挑战,随着光纤技术和密集波分复用技术(DWDM)的发展,网络链路传输速率问题已基本解决,此时,作为网络核心器件——路由器的性能已成为网络性能的新瓶颈。而路由器所具有的包括路由选择、区分服务、QoS、流量费等在内的多项功能都是以数据包分类技术为支撑地。本文首先对目前常见的十余种典型的基于软件实现的包分类算法进行了系统、详细的研究,并对各种算法的查找时间和空间需求进行了比较,分析总结出当前数据包分类领域面临的问题。研究发现现有的包分类算法均只对特定形式的分类规则表现出良好的性能。目前还没有一种算法能在所有方面都较理想地满足高速(大于100Gbps)应用的需要。随后本文针对多维包分类问题,提出了一种能灵活的适应各种多维规则的包分类算法,本文称之为域分多维包分类算法。研究过程中取得的主要研究成果有:1.根据多维规则的各个域的表现形式不同将其分段处理。具体的做法是:将规则分为最长前缀表示段、精确值表示段、剩余部分段三部分,分别加以处理。如此处理显然能使算法更很好地适应各种形式的规则集;2.通过对规则表示形式的研究,本文统一将规则中除前缀式和精确值形式之外的部分转化为任意位掩码形式予以处理,并针对任意位掩码形式表示的规则,提出了一种新的分类算法——状态转移树算法(时间复杂度O(m),空间复杂度O(m),m为规则长度);3.对Tuple space search算法作了改进,将查找速度由O(n)提高到O(logn),n为不同前缀的个数;4.针对本文提出的分段策略,设计出并行执行方案,进一步提高了速度;文章分析得出本算法的时间复杂度为O(log n)空间复杂度为O(N),n为不同前缀个数,N为规则数。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 研究背景
• 1.2 包分类问题的研究现状
• 1.3 本文主要工作
• 第二章 包分类问题概述
• 2.1 包分类问题的提出
• 2.2 包分类问题的定义
• 2.3 包分类算法的性能评价
• 2.4 包分类问题的难点
• 2.5 本章小结
• 第三章 典型算法描述
• 3.1 概述
• 3.2 基于Trie算法
• 3.2.1 Hierarchical Trie算法
• 3.2.2 Set-Pruning Trie算法
• 3.2.3 Grid-of-Tries算法
• 3.3 2D分类算法
• 3.4 Bit Vector算法
• 3.5 HiCuts算法
• 3.6 RFC算法
• 3.7 Tuple space search
• 3.8 基于平面划分的四叉树算法
• 3.9 基于FIS树的算法
• 3.10 交叉相乘法
• 3.11 位并行包分类算法
• 3.12 本章小结
• 第四章 域分多维包分类算法
• 4.1 算法的顺序实现思想
• 4.2 前缀匹配段
• 4.2.1 Tuple space search算法改进
• 4.2.2 算法描述与性能分析
• 4.3 精确匹配段
• 4.4 任意位掩码匹配段
• 4.4.1 Aho-Corasick算法
• 4.4.2 状态转移树算法设计思想
• 4.4.3 预处理
• 4.4.4 查找
• 4.4.5 本算法的进一步说明
• 4.4.6 时间复杂性分析
• 4.4.7 空间复杂性分析
• 4.5 域分包分类算法的时间复杂度和空间复杂度分析
• 4.6 本算法的并行实现思想
• 4.7 实验验证
• 4.8 本章小结
• 第五章 结束语
• 致谢
• 参考文献
• 在校期间研究成果