（计算机软件与理论专业论文）高速路由中的多维快速包分类算法的改进与应用.pdf

南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机软件与理论 研究方向：数据仓库与决策支持系统 作者：李伟伟 指导教师：郑彦 删删i j | f 舢洲舢删 y 17 5 5 4 2 。 题目：高速路由中的多维快速包分类算法的改进与应用 英文题目：t h e a p p l i c a t i o na n dr e s e a r c ho fm u l t i d i m e n s i o n a lf a s tp a c k e t c l a s s i f i c a t i o na l g o r i t h mu s e di nh i g h - s p e e dr o u t i n g 主题词：包分类；高速路由；访问控制列表 k e w o r d s ：p a c k e tc l a s s i f i c a t i o na l g o r i t h m ；h i g h s p e e dr o u t i n g ； a c e s sc o n t r o ll i s t 一r r ： ， 南京邮电大学硕士研究生学位论文 摘 摘要 随着i n t e r n e t 的发展和新技术的不断出现，各种网络应用的数据流迅猛增长，传统 路由器的“尽力 服务方式已经不能满足要求，这要求网络设备提供更高的带宽和数据分 类能力。这一切都对网络中间设备路由器提出了新的要求，如资源预留、服务质量、 防火墙、基于策略的区分服务，虚拟专用网( v p n ) 、流量计费等这些“差别服务”机制。 而所有这些“差别”服务机制都需要路由器对i p 包进行分类，根据数据包头部的内容把 数据包归类为某个流的过程称为数据包分类。数据包分类系统要求对输入的任何网络信息 包与数据库中的规则相匹配。根据匹配的结果，按照符合最高优先级的规则来处理输入的 信息包。 本文选题来自于网络中使用的边界网关设备中的访问控制列表中的包分类算法的研 究项目。访问控制列表( a c c e s sc o n t r o ll i s t s ) 是c i s c oi o s 所提供的一种访问控制技 术。 本文在原来几种主要包分类算法以及其优缺点的分析的基础上，通过对现有算法分 析，提出了一种适应于包分类算法动态更新的多维高速数据包分类算法。该算法在原有算 法的基础上，通过增加新增表的方式达到实现动态更新的目的。新增表的数据结构是根据 实际使用情况，通过设计和优化从而达到空间和时间的平衡。本算法同现存的路由器上应 用的r f c 算法相比，在支持动态添加删除条目的基础上同时具有较好的时间和空间复杂度， 通过仿真比较证明试验和理论分析吻合，达到了预期的效果。 关键字：包分类；网络路由器；r f c 算法 南京邮电大学硕上研究生学位论文 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t , v a r i o u sn e tt r a f f i c sa r ee m e r g i n g ，a n dt h eo r i g i n a l b e s te f f o r t s e r v i c ei sn o ta d a p t i v e i nt h a te a s e , t h en e t w o r ke q u i p m e n td e m a n d sm o r eh i g h e r b a n d w i d t ha n da b i l i t yo fp a c k e tc l a s s i f y a l lo fa b o v es h o wn e wr e q u i r e m e n t st ot h ek e r n e l e q u i p m e n to fi n t e r n e t - b a c k b o n er o u t e r s e r v i c ep r o v i d e r sw o u l dl i k er o u t e r st op r o v i d e s e r v i c e d i f f e r e n t i a t i o n ”，s u c ha sr e s o u r c er e s e r v a t i o n , q o s ，f i r e w a u ，p o l i c y - b a s e dr o u t i n g , v i r t u a lp r i v a t e n e t w o r k sa n dt r a f f i cb i l l i n g a l lt h e s ef u n c t i o n sd e m a n dt h er o u t e r sw i t hap a c k e tc l a s s i f i c a t i o n c a p a b i l i t y , w h i c hc a l ld i s t i n g u i s ht r a f f i c sb a s e dt h eh e a do ft h ep a c k e t i pp a c k e tc l a s s i f i c a t i o ni s at e c h n i q u et om a t c he a c hi n c o m i n gi pp a c k e ta g a i n s tad a t a b a s eo ff i l t e r s ( o rr u l e s ) a c c o r d i n g o n e - d o m a i no rm u l t i - d o m a i ni nt h eh e a do ft h ep a c k e t ，a n df o r w a r d i n gt h ep a c k e ta c c o r d i n gt o t h eh i g h e s tp r i o r i t yf i l t e r t h es u b j e c to f t h i sa r t i c l ec o m e sf r o mt h ea c c e s sc o n t r o ll i s tu s e di n t h eb o u n d a r yg a t e w a y 。 a c li saa c c e s sc o n t r o lt e c h n o l o g yp r o v i d e db yac i s c oi o s b a s e do ns o m er e p r e s e n t a t i v ec l a s s i f i c a t i o na l g o r i t h m s ，d i s c u s st h e i rt i m ea n ds p a c er e q u e s t a c c o r d i n gt oa n a l y s i so nt h ep a r a l l e la b i l i t yo fn e t w o r kp r o c e s s o ra n dc l a s se q u i v a l e n tu s e di n t h ea l g o r i t h mo fr f c ，ah i g h - s p e e dp a c k e tc l a s s i f i c a t i o nw h i c hs u p p o r td y n a m i cr e f r e s ha n di s f l e x i b l ea n ds c a l a b l ei sp r e s e n t e d b a s e d0 1 1t h eo r i g i n a la l g o r i t h ma n da c t u a lu s a g e ，t h e a l g o r i t h mg a l lu p d a t ed y n a m i c a l l yb ya d d i n gn e w st a b l e s t h ed e s i g na n do p t i m i z a t i o nc a n b a l a n c eb e t w e e ns p a c ee f f i c i e n c ya n dt i m ee f f i c i e n c y c o m p a r i n gt ot h ea l g o r i t h mo fr f cu s e di n t h ea d v a n c e dr o u t e r , t h ea l g o r i t h mp r o v i d e sb e t t e rt i m ea n ds p a c ec o m p l e x i t y , s u p p o r t sd y n a m i c u p d a t e ；a n dt h el o o k u pt i m ei si n d e p e n d e n to ft h es i z eo ft h ed a t a b a s eo fr u l e s f i n a l l y , t h e p e r f o r m a n c eo ft h en e wa l g o r i t h mi st e s t e da n dt h er e s u l t ss h o ww e l la n dm e e tt h et h e o r yr e s u l t r e q u i r e m e n t k e yw o r d s ：p a c k e tc l a s s i f i c a t i o na l g o r i t h m ；r o u t e ri nn e t w o r k ； r e c u r s i v ef l o wc l a s s i f i c a t i o n i i 南京邮电大学硕士研究生学位论文 目录 目录 摘要i a b s t r a c t i i 目j i 乏i 】：i 第一章绪论1 1 1 研究的目的和意义l 1 2 研究现状2 1 3 论文的主要工作2 1 3 论文结构3 第二章包分类算法综述4 2 1 包分类算法4 2 1 1 包分类定义4 2 1 2 前缀匹配5 2 1 3 包分类算法的性能评估指标5 2 1 4 常用包分类算法的介绍和优缺点6 2 2 网络处理器16 2 2 1 网络处理器的概述1 6 2 2 2 网络处理器在分布式路由器中的使用1 6 2 3 访问控制列表1 8 2 3 1a c l 基本概念。1 8 2 3 2a c l 工作原理。1 8 2 3 3a c l 的分类1 9 2 3 4a c l 的应用。2 0 第三章包分类算法的改进和实现2 2 3 1 算法在路由a c l 功能中的应用2 2 3 2 算法的改进思想2 4 3 3 改进算法逻辑流程2 5 3 3 1 增加条目的动态更新。2 5 i i l 南京邮电大学硕上研究生学位论文目录 3 3 2 删除条目的动态更新2 6 3 3 3 查找条目2 6 3 4 算法的内存结构2 9 3 5 主要数据结构设计。3 1 第四章改进算法的仿真和测试3 6 4 1 网络流和规则库的选择和设计3 6 4 2 仿真环境3 7 4 2 1 硬件环境3 7 4 2 2 软件环境3 7 4 2 3 测试环境3 7 4 3 仿真配置3 8 4 4 仿真结果和分析4 2 第五章总结和展望4 5 5 1 对本文工作的总结4 5 5 2 对进一步研究的展望4 5 j g c 谢4 7 参考文献4 8 图表清单5 0 攻读学位期间发表的学术论文5 2 i v 南京邮电人学硕士研究生学位论文第一章绪论 1 1 研究的目的和意义 第一章绪论 近年来，随着因特网的快速发展和网络用户数骤增，导致网络拥塞，报文丢失，传统 的网络设备对于每个i p 包都“尽力服务”已经不再满足网络用户的需求。网络应用的多样 化成为了网络发展的一种趋势。尤其是随着宽带多媒体业务日益普及，用户对因特网的要 求也不再仅仅满足于简单的文件传输。话音、文本、图像、视频等多媒体在网络中的应用 日益广泛，对网络安全的要求也是越来越高，这就要求网络提供更加安全、快速和多样化 的服务。为了适用网络发展的需求，网络服务供应商i s p ( i n t e m e ts e r v i c ep r o v i d e r ) 必须 努力提高网络骨干网的速度以及筹划新的差异性服务，前者由于光纤技术和高密度波分多 工技术( d e n s ew a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ，d w d m ) 的发展，使得链路的速率已经 不再成为瓶颈。另外的一个难点一路由器，却大有可能成为网络性能的主要瓶颈。这主要 是由于路由器对输入输出报文需要执行众多的操作，包括十分复杂的分类行为，以支撑各 式各样的差别服务，包括访问控制列表( a c c e s sc o n t r o ll i s t ，a c l ) 、策略路由( p o l i c yb a s e d r o u t i n g ，p b r ) 、网络地址翻译( n e t w o r ka d d r e s st r a n s l a t e ，n a t ) 、负载均衡( l o a db a l a n c e ， l b ) 、流量计费( t r a f f i cb i l l i n g ，t b ) 等。这些要求直接促成了网络包分类的发展和应用。 路由器，网关和终端设备等，它们之间通过协议实现通信，主要功能是路由和转发。 路由是指通过抽取数据报文的头信息，判断到达目的地的最佳路径，由路由选择算法来实 现。转发则是沿着路由选择确定的最佳路径进行报文的发送。传统的路由器采用尽力而为 的方式，不区分的对待所有的数据报文，所以无法满足网络发展及i s p 的需求。而流分类 技术是在传统路由器基本功能上的拓展，它通过抽取报文头中的不同域的信息，根据规则 库中一定的规则，采取不同的处理方式。对流入的所有p 包，路由器根据i p 包的不同属 性进行分类，这些属性包括源地址、目的地址、源端口号、目的端口号等，描述p 包的属 主、所承载的应用类型等，路由器对每个分类后的i p 包分配一个“流标记”。这样，所有 通过路由器的i p 包将被分成不同的流，同一个流的所有i p 包具有相同的属性。路由器对 不同流的口包采取不同的处理策略，而属于同一个流的所有i p 包则使用相同的处理策略。 显而易见，流分类技术是在路由器上实现差别服务的基础，其技术的发展及方案的应用将 直接影响到整个路由器的性能。 南京邮电大学硕上研究生学位论文 第一章绪论 1 2 研究现状 流分类问题的研究始于9 0 年代中后期，经过短短近十年的研究，基于不同思想和不 同数据结构的算法及改进优化已近二十余种。最初的流分类问题研究主要是基于i p 路由查 找，后来随着网络应用要求的不断提高，基于差分服务、网络安全等各方面的报文分类研 究逐步展开。这个研究领域主要有两大学派：以g e o r g ev a r g h e s e 教授及其弟子s r i n i v a s a n 为主，偏向于尝试数据结构以及h a s h 函数解决方案的圣路易斯大学( w a s h i n g t o nu n i v e r s i t y i i ls t l o u i s ) 学派，其主要合作伙伴是b e l l 实验室和微软研究院：另一学派是以n i c k m e k e o w n 教授及其弟子p a k a jg u p t a 为主，重点研究多维数据报文分类及基于t c a m 算法设计的的 斯坦福大学学派，其主要的合作伙伴是c i s c o 公司。国内从事这一领域的研究的主要有：清 华网络和协议测试实验室、中科大信息网络实验室、北京邮电大学程控交换技术与通讯网 国家重点实验室等。目前具有代表性的流分类算法有：递归流分类算法、交叉乘积算法、聚 合比特向量算法、网格查找树算法、二维组空间查找等。 自从1 9 9 9 年g u p t a 和m c k c o w n 提出了r f c 算澍2 】之后，流分类领域有很多的学者对 r f c 算法的应用和改进提出了自己的研究成果，比如g u p t a 在其r f c 提出的文章当中就 提出了利用邻接规则压缩规则库的思想，s p i t z n a g e l 提出了对交叉乘积表采用比特向量压 缩的方法，并进一步提出了改进的措施，但是并没有对算法的数据设计实现。d ul i u ，b e i h u a 等提出了对交叉乘积表位图压缩算法的实现方案，并对算法在网络处理器上的实现作了积 极的探索。k o u n a v i s 等人对网络中规则库的分布规律作了总结，并提出了在网络处理器上 利用软件硬件分别实现m 查询和剩余域查询两个阶段实现方案，并对这种两阶段实现方案 进行了详细地分析。 1 3 论文的主要工作 本文通过对几种主要算法的分析，提出了一种支持动态更新的包分类算法。 ( 1 ) 首先，通过增加一个可支持动态更新的表，来弥补r f c 不可支持动态更新的不足， 因为新增表格是对原a c l 的补充，所以我们规定新增表具有高于r f c 表格的优先 级。在匹配的过程中，优先匹配，达到一个对原表的补充的目的。 ( 2 ) 其次，通过分析，我们是在新增表结构实现源i p 地址的一维包分类的前缀匹配，根 据实际使用的包的特点，首先h a s h 与或计算得到k e y 的值，然后再做树结果的 搜索匹配，减少了树的深度，加快了搜索的速度。对冲突采用按照索引号的顺序插 2 南京邮电大学硕士研究生学位论文 第一章绪论 入，查找方便。 ( 3 ) 最后，对删除条目的更新处理，在上层人机命令脚本的部分，直接删除，保证下次 启动的时候不再加载。对下层驱动微码部分，采用了新增表直接删除，对r f c 表则 采用删除标志位的方式，将结果匹配串和删除标记位相与，得到真正匹配的字符串， 找到匹配的条目。 。 对算法在网络处理器上进行了软件设计仿真，仿真结果显示，本算法能够可以实现动 态的更新，并且有较好的空间和时间复杂度。 1 3 论文结构 本文的内容由以下章节组成： 第l 章，绪论，论述论文的选题背景、研究现状、主要应用以及论文的主要工作。 第2 章，流分类算法综述与网络中分布式路由器的介绍。流分类综述部分主要介绍了 流分类算法的定义，常用的匹配方式，匹配字段，衡量标准，设计原则并对常用的流分类 算法作了介绍总结。分布式路由器简介部分主要对算法实现的硬件平台及软件开发架构作 了简要介绍。 第3 章，r f c 算法的改进，对包分类算法的动态更新改进措施进行了功能分析，数据 结构设计，流程规划，代码实现。 第4 章，改进算法的仿真和测试，给出了仿真环境配置情况，给出了仿真结果并进行 了分析。 第5 章，对本文算法改进工作的总结，以及对后期算法的发展做了展望。 南京邮电大学硕士研究生学位论文第- 二章包分类算综述 2 1 包分类算法 2 1 1 包分类定义 第二章包分类算法综述 包分类技术是很多网络业务所使用的关键技术，包括服务质量、安全、监控、计费和 多媒体通信等，为了将口包分成不同的流，网络设备根据口包的多个域作为键值，对定 义的一套规则做搜索匹配。规则集是指网络服务提供商在网络设备中设置一组用于m 报文 匹配的规则的集合，每条规则有多个域的值来描述其属性，规则的每个域和口包的相应域 对应，一个m 包和某个规则相匹配就是指i p 包的所有域的值都符合规则对相应域的值的 描述。 简单将包分类定义【3 1 如下：包分类就是将包头中的相关域与路由器中预设的规则集进 行比较以决定数据包所属数据流的过程用数学语言描述，规则集包含n 条规则，每条规 则包含d 个域，其中第i 个域( 用f 【i 】表示) 与数据包头的第i 个域( 用p 【i 】表示) 相对应 对于一个到达的数据包，如果存在一条规则r 对任意的i 满足f i 】匹配p i 】，那么数据 包与该条规则匹配。 流分类模型见图2 1 所示： 图2 1 流分类模型 4 南京邮电大学硕上研究生学位论文 第二章包分类算综述 2 1 2 前缀匹配 在包分类的过程中，包分类的规则库的域的值常见有三种描述的方式，一是精确匹配， 输入的i p 包头的每个域的值k e y 恰好等于对应一个规则的对应域的值v a l ；二是前缀匹配 1 1 ，即有前缀的方式来描述，如( v a l ，m a s k ) 格式来表示，砌是规则库的域的值，m a s k 是规则库域值的掩码，只有属于i p 包的对应的域值满足( k e y & m a s k = v a l & m a s k ) 时才匹配； 三是范围匹配，报头每个域的值都是在某一个规则的制定的范围内。例如： 1 , 4 4 ，【5 5 1 0 3 】 盘簟 守。 当前大多都是针对前缀匹配而提出的，但当所给出的匹配规则库的规则是范围形式 时，这个时候若还想利用现有的基于前缀匹配的算法，就必须先要进行范围前缀的转化。 由已有的数学知识得知，任何一个范围匹配都可以转换成为前缀对于在范围 1 ，u 】之间有n 个点的范围匹配问题，可以转换成最多2 n 个前缀每个前缀的长度最多为l o gu 1 5 。 r a n g e c o n s t i t u e n tp r e f i x e s 【4 ，7 】 o l 3 ，8 】0 0 1 1 ，0 1 料，1 0 0 0 1 ，1 4 】0 0 0 1 ，0 0 1 幸，0 1 料，l o ，1 1 0 牛，1 1 1 0 将范围转换成前缀的结果( 假设最长前缀w = 4 ) 。 2 1 3 包分类算法的性能评估指标 对包分类算法的性能评估主要从以下几个方面： ( 1 ) 分类速度，即分类处理一个包所需要的时间。分类速度除了与算法本身直接有关外， 还受诸如分类规则个数、分类域的多少以及分类规则给定方式的影响。分类速度与 这些因数的相互影响关系有时决定着该算法的可用范围。 ( 2 ) 空间复杂度，即算法运行所需要的存储空间大小以及与上述影响分类速度的诸多因 素间的依赖关系。算法的实际应用实现往往是时间复杂度和空间复杂度的平衡折衷。 ( 3 ) 对规则的适应性，包括对规则个数、规则在空间中的分布、域的多少以及规则定义 方式的适应性； ( 4 ) 预处理时间，预处理时间是指包分类算法建立初始的数据结构所需要的时间。对于 静态算法，增加或者是删除一条规则，那么整个数据结构都需要重建。对于动态更 新的算法，其数据结构是动态的，只需要插入删除条目即可。 5 南京邮电大学硕士研究生学位论文第二章包分类算综述 ( 5 ) 更新速度，在包分类算法的问题当中，不同的应用场景对于更新速度的要求也是各 不相同。 目前，大部分的包分类算法都是比较注重分类的查找速度和存储空间的复杂度。但是 随着计算机硬件技术的发展，在设备上可以使用大容量的存储器，存储的空间因素的制约 越来越小。一些网络技术的发展和应用，对规则查找速度和动态更新的要求越来越多。在 算法的实现过程中，不可能做到每个指标都是最好的，所以，我们在设计算法的时间的过 程中，要根据实际的使用情况，对各个因素的侧重度，将各个指标的实现程度做到最适用 的组合。 2 1 4 常用包分类算法的介绍和优缺点 比较典型的流分类算法可以分为四类：以穷尽搜索为主要思想的线性查找和t c a m 算 法【4 】【6 】：以决策树为主要思想的h i e r a r c h i c a lt r i e s 7 ，s e t - p r u n i n gt r i e s ，g r i d o f - t r i e s ，h i c u t s ( h i e r a r c h i c a li n t e l l i g e n tc u t t i n g s ) ，h y p e r c u t s 算法等；以划分元组空间为主要思想的元组 空间算法( t u p l es p a c es e a r c h ，t s s ) 【8 1 ；以对数据处理过程分解为并行过程成为主要思想 r f c 算法等。对与典型的包分类算法的比较，我们主要从空间复杂度，时间复杂度，更新 复杂度三个角度来分析。 典型算法的空间时间复杂度比较5 】【1 9 1 如表2 1 t 2 】所示。 表2 1 主要包分类算法的复杂度比较 a l g o r i t h m w o r s t - c a s et i m ec o m p l e x i t y w o r s t - c a s es t o r a g ec o m p l e x i t y l i n e a rs e a r c hnn t e r n a r yc a m l n h i e r a r c h i c a lt r i e sw dn d w s e t - p r u n i n gt r i e s d wn d g r i d o f - t r i e sw ( d 1 )n ( 1 w h i c u t sdn d t u p l es p a c es e a r c h nn i 江cdn d 2 1 4 1 穷尽搜索算法 ( 1 ) 线性查找算法 线性查找算法很简单，它将规则按优先级的顺序线性排列。当数据包到来时，将其头 部信息与规则顺次比较，直到找到匹配规则。该方法的空间复杂度和时间复杂度都是o ( n ) ， 6 童室堂皇盔堂堡主塑窒竺堂篁丝壅茎三雯鱼坌耋簦堡垄 更新即为类似数组的插入删除操作。随着规则库的增大，查找时间会增长较快。其优点： 查找方便，存储器空间使用的效率比较高。其缺点：该算法只适合应用在具有小型分类规 则库的环境中，对应大型的规则库查找速度低下且可扩展性较差。 ( 2 ) t c m a t c a m ( t e r n a r yc a m ，b i t m a p i n t e r s e c t i o n ) 是内容可寻址寄存器的简称，是常见的硬 件方案，采用并行处理的方式，理想情况下一个周期可以完成数据包流分类的比较。其内 部硬件逻辑可以将一条关键字同多条记录进行比较，然后将比较的结果进行优先级编码， 并输出位移的匹配记录的地址。三态的c a m 支持三种状态的比较，分别为“0 ”，“1 ”，“x 即具有掩码比较的功能，便于实现数据包分类中常用的m 前缀匹配等功能。其优点：复杂 度最小。其缺点：由于t c a m 功耗大，内存密度小，价格昂贵，条目数量扩展需要改变硬 件，它能够处理的分类规则也十分有限，因此也不是一种理想的解决方案。 2 1 4 2 决策树搜索算法 ( 1 ) h i e r a r c h i c a lt r i e s 算法 h i e r a r c h i c a lt r i e s 算法是指先在预处理阶段根据规则集构建一个分层二叉树，在i p 包 进来的时候，搜索匹配过程沿着树结构查找，直到找到匹配的规则或者搜索结束为止。 创建搜索树过程：假设规则库有j 个域，分别记做f j ，域的宽度记做w j ，则很容易根 据规则库的第一个域r l 建立一个至多m 层的二叉树，树根的左分支包含域值m s b 为0 的规则，右分支包含域值m s b 是1 的规则。依次类推，从m s b 到l s b 的比特顺序，依 照所有规则的第一个域的m b i t 的值建立二叉树记做f 1 t r i e 。显而易见，f 1 t r i e 中的节点包 含规则集中所有与域r 1 有关的规则域值。固定类型的规则域值所在的分支跨越f 1 t r i e 的 所有层，到达底层节点就结束或者是指向下一个域的二叉树。对于范围类型的规则域值必 须先转化为前缀的形式，而前缀类型的规则域值所在的分支并不跨越f 1 t r i e 的所有层，可 能到某一个中间的节点就结束或者是指向下一个域的二叉树。f 1 t r i e 创建成功之后，如果 规则没有下一个域要创建下一层二叉树，那么分层数的终结点就是f 1 t r i e 的结束节点。如 果还有下一个域的二叉树要创建，那么从f 1 t r i e 的每个结束节点出发，它们的下一级指针 均指向下一个域的跟节点，在每个根节点上建立第二层的二叉树f 2 t r i e ，依次类推，直到 建立总共d 层二叉树为止，并在节点中存入对应的规则号。 搜索过程：首先必须分层遍历，在某个层次找到p 的最佳匹配前缀m ，沿着该节点的 下一层次查找树指针继续遍历下一维查找树，记录下这条路径上所有匹配规则。然后回溯 7 南京邮电大学硕士研究生学位论文第二章包分类算综述 最佳匹配前缀m 的最小祖先( m 的最长匹配前缀) 进行再次遍历，直到m 的所有祖先都遍 历完为止，所有路径上的规则库即为该实例的匹配情况 r m ) ，规则的选取可以根据实际的 优先级或者特定域决定。 其中最佳匹配前缀及最小祖先是指： 最佳匹配前缀：即某一层次二义树中匹配的深度最深的结点，i 最小祖先：假设n 和n ，均是树t 中的两个结点，当且仅当n 是n 的最佳匹配前缀 时，我们称n 是n 的最小祖先。 如表2 - 2 1 8 】所示的规则集： 表2 2 规则集 r u l e sf 1f 2 r 10 0 0 0 r 20 木木0 l 木 r 3 1 木木0 幸宰 r 40 0 0 宰3 | r 5 0 木木1 木宰 r 6 木木木 1 木木 1 根据域f l ，创建f 1 t r i e ，如图2 2 所示： 2 创建f 2 t r i e ，如图2 3 所示： f 1 t r i e 图2 3f 2 - t r i e 8 f 2 t r i e 南京邮电大学硕士研究生学位论文第二章包分类算综述 3 查找( 0 0 0 ，0 1 0 ) ，过程如图2 - 4 所示： f 2 t r i e 图2 4 查找( 0 0 0 ，0 1 0 ) 过程图 ( 2 ) s e t p r u n i n gt r i e s 算法 s e t - p r u n i n gt r i e s 算法是对h i e r a r c h i c a lt r i e s 算法的改进，使通过对多层查找树中某些节 点进行复制，避免查找中的回溯。 创建查找树如图2 5 所示，查找过程不必回溯。 t r i e 图2 5s e t p r u n i n gt r i e s 查找树 ( 3 ) g r i d o f t r i e s 算法 g r i d o f t r i e s 算法是对s e t p r u n i n gt r i e s 算法算法的进一步改进，重复的节点只 保留一棵子树，使用指针引用。即避免了重复的存储，也避免了回溯。创建树如图2 - 6 所 示： 9 南京邮电大学硕士研究生学位论文第二章包分类算综述 f 2 t r i e 刚 回 图2 6g r i d o f - t r i e s 查找树 其优点：比较适合于二维前缀匹配，查找速度快，空间要求小；交换指针的引入消除 了分层查找树存在的回溯要求，只需经过一条路径就可以匹配到整个规则库。其缺点：由 于交换指针的引入同时也导致网格查找树生成时大量的预处理计算：在规则库更新时，树结 构以及交换指针的更新，影响预处理及更新速度。并且扩展到多维匹配后，会导致整个网 格查找树实现较为困难，整个树结构也会异常复杂，规则库更新需要大量时间。 ( 4 ) h i c u t s 算法 h i c u t s ( h i e r a r c h i c a li n t e l l i g e n tc u t t i n g s ) 算法，是由是由学者g u p t a 和m c k e o w n 提出的， 其基本思想是在预处理的时候构建一棵基于规则的决策树，决策树的内部节点包含的适当 的分类导向信息( c ，k ，1 1 其中c 表示包含的子空问的个数，k 表示分割根据的维，1 1 表示 空间被分成的分数即其孩子节点的个数) ，但是不储存任何规则，其叶节点储存一个小型 的规则集，当包到来的时候，就遍历决策树找一个叶子节点，找到叶子节点后，线性查找 这个叶子节点储存的小型规则集，这个小型规则集的数目小于一个常数，该常数称为b i n t h 。 决策树的外形特征，如高度、每个节点的度等，都是在预处理的时候根据规则集的特征决 定的。 根据表2 的规则集，并且限定b i n t h = 2 ，构造的决策树如图2 7 所示。该树代表完整的 二维空间，其大小为2 8 * 2 8 h i c u t s 算法根据x 维将空间四等分，根结点的四个子节点代表这四个子空间，这四个 子节点包含的规则集的数目，如果大于b i n t h 则还要对这个子节点进行分割。示例中除了 的二个节点之外，其他节点包含的规则数目都小于等于b i n t h ，我们对第二个节点进行分割。 第二个节点的空间大小为2 2 2 8 ，根据y 维将这个子空间分成2 个子节点，每个节点包 1 0 南京邮电大学硕士研究生学位论文第二章包分类算综述 含两条规则，规则数目小于b i n t h ，决策树构造过程结束。过程如图2 7 所示： o o o 0 0 l 0 1 0 0 1 1 l o o 1 0 1 1 1 0 l l l r lr 4 r 5 r 2 r 6 r 3 0 0 00 0 10 1 00 l l 1 0 01 0 l1 1 0l l lf 2 图2 7h i c u t s 决策查找树 其优点：h i c u t s 算法对内存空间需求较低，规则库的更新也比较容易，可以支持范围 匹配，在规则空间均匀分布的情况下，h i c u t s 有很好的性能。其缺点：由于构造h i c u t s 树时是依次对每一维进行空间划分，考虑这样的情况：在一个d 维的分类规则集中，大部分 规则只通过某一维来区分，而其他维的值相似或相同。这时，h i c u t s 树的深度和结点会大 大增加，预处理时间和占用的内存空间都会成倍增大，算法的性能受到很大影响。 2 1 4 3 元组空间搜索算法 t s s 元组空间搜索算法是基于前缀匹配的搜索，其出发点是利用实际规则库的特性来 提高搜索的速度。根据实际使用的统计发现，在实际使用的规则库中，存在大量具有不同 长度的前缀，但是前缀长度的取值范围都是在( o 3 2 位) 之间，因此各个字段的前缀长度 的组合的数目也就非常的有限。根据这个特点，t s s 算法对规则库中的不同的前缀长度的 组合作为一个元组，定义一个t u p l e ，也就是将规则库中的规则按照每个域的不同的长度 组成元组来归类。因为在一个元组中的规则的各个字段具有固定的前缀长度，所以按照关 键字用h a s h 表来组织，用关键字来搜索，可以非常迅速的找到匹配的规则。这样通过规则 库的不同元组空间的分类，将大的规则库分成小的规则库来查找，大大提高了搜索的效率。 当分组到达的时候，首先根据数据包的前缀长度找到可能匹配该数据包规则的元组。如果 存在这样的元组，则利用从数据包头中各个域中提取的适当的比特位，通过h a s h 运算来进 行查找，并从搜索到的匹配项中确定最佳的匹配。 表2 2 规则库对应元组规则对应表和元组的h a s h 表如表2 3 所示： 南京邮电大学硕上研究生学位论文第二章包分类算综述 表2 3 组规则对应表和元组的h a s h 表 规则元组 r 1 ( 0 0 ，0 0 ) ( 2 ，2 ) r 2 ( 0 枣木，0 1 木) ( 1 ，2 ) r 3 ( 1 枣木j0 枣木) ( i ，i ) r 4 ( 0 0 ，0 术木) ( 2 ，i ) r 5 ( 0 木木ji 阜木)( 1 ，1 ) r 6 ( i 【木木，1 掌，| )( 0 ，i ) 元组的规则对应表 h a s h 表的元组项 对应规则集合 ( 0 ，1 ) r 6 ( 1 ，1 )r 3 r 5 ( 1 ，2 )r 2 ( 2 ，1 ) r q ( 2 ，2 ) r 1 元组的h a s h 表 其优点：t s s 算法的最大优点是支持规则动态更新。在多维平均情况下，元组空间查 找算法有较好的性能，因为这时元组数量不多。其缺点：由于哈希表的使用，使得该算法 的时间不太好估计。在最坏的情况下，元组的数量可能很多，达到o ( w d ) 。同时，元组空 间查找算法只支持前缀形式，对于一般形式的规则，它的空间复杂度可能会增加，因为一 条范围规则可能展开为o ( w ) 个前缀规则。 2 1 4 4 分解搜索算法 r f c ( r e c u r s i v ef l o wc l a s s i f i c a t i o n ) 8 1 【9 】【1 0 1 流分类算法和h i c u t s 算法复杂度相同，但 是在分包效率上r f c 具有明显的优势，其速度最快、支持范围匹配、扩展性好，较其他集 中算法，具有明显的优越性，也是我们快速路由中最广泛使用的包分类算法。 r f c 算法( r e c u r s i v ef l o wc l a s s i f i c a t i o n ) 是一种多维的p 分类快速查找算法，其主 要思想是把多字段分类问题看作为分组头控制字段取值空间( s ) 到类标识( c l a s si d ) 空间( t ) 的映射问题( t = l o g n ，n 为规则数，且t 3 e q l d组合为( 3 ，3 ) e q i d 8 = 3 木5 + 3 = 1 8 = l ( c b m = 0 1 0 0 1 ) ，按照规则i d 越小优先级越高的规则，匹配的规则是r l ， 检查匹配正确。 匹配规则规 则，d 越小优先 级越商的原则 翩c 撕 诅、 oj i4 1 0 0 雠l3 2 i l z ，m ；0 ，tj 0 i l 0 n 期1 ， ， vm m l 2 2 聃h 远埘 # n 口 4 l 图2 8r f c 算法的缩减过程以及查找过程 其优点：r f c 算法是一个通用性强、速度快的多维数据包分类算法，对规则的维数和 宽度可扩张性较强，分类查找性能不受规则数量和规则特征的影响。其缺点：算法所需要 的存储空间在某些情况下会急剧膨胀，例如：