（计算机科学与技术专业论文）ip报文分类算法评测系统的研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要+ 随着各种网络应用的发展，未来i p 网络必须为用户提供更多的服务类型和更好的服务 质量，要求网络互连关键设备路由器提供额外的以报文分类为基础的一些网络关键技术来 实现区分服务。从现有的研究来看，高速多维分类算法仍然存在的一些不足已经成为路由 器新的瓶颈。 由于i p 报文分类问题本身的复杂性以及其应用环境的多样性，现有的算法很难满足不 同环境下不同的性能和其他应用需求。因此需要建立评价体系和完备的模拟平台，对现有 算法进行模拟和评估，确定不同环境下适用的不同算法，以及各个算法所适用的环境，从 而有助于网络设备如路由器和防火墙的开发研制，并可以对高速核心路由器等特定应用条 件下i p 报文分类算法的研究提供建议和参考。 本文通过分析报文分类技术的特点以及在不同应用领域中人们所关注的性能表现，确 定了对报文分类算法进行全面性能评价的度量参数，提出了一个较为完善的评价体系。通 过全面考虑报文分类技术在网络中的应用环境以及所需测量参数的主要影响因素，本文建 立了i p 报文分类算法评测系统的通用模型，并力图将i p 报文分类算法性能评价工作标准 化、规格化。在此基础上，我们以美国斯坦福大学的报文分类与查找模拟器p a l a c ( p a c k e t l o o k u pa n dc l a s s i f i c a t i o ns i m u l a t e r ) 为基础，结合报文分类算法的现状和发展趋势， 对p a l a c 模拟器进行了改进和完善，例如：新增了规则数据库生成模块；新增了支持硬件 算法接口模块：对输出统计模块、控制平台模块进行了完善和改进；完备了对模拟结果的 统计输出。通过这些改进和完善，我们建立了一个完善的模拟和测试系统，该平台能够为 各类算法的模拟提供方便的功能接口，并能对算法在不同模拟环境中的性能进行测试。本 文中运用该模拟测试平台对一些典型的报文分类算法进行了模拟和测试，并用我们提出的 评价体系对它们进行了比较和评价，指出其优缺点和适用范围，从而为路由器相关算法模 块的开发研究以及i p 报文分类算法本身的进一步研究提供参考和支持。 关键字：区分服务，l p 报文分类算法，评价体系，模拟评测系统 t 本课题得到9 7 3 国家重点基础研究发展计划新一代联网络路由与交换理论( 2 0 0 3 c b 3 1 4 8 0 2 ) 支持 国防科学技术大学研究生院学位论文 a b s t r a c t w h i l et h ec u r r e n ti n t e m e to f f e r sb e s t e f f o r ts e r v i c e 、f u t u r ei pn e t w o r k sw i i lp r o v i d e e n h a n c e ds e r v i c e st oi t su s e r s s u c hs e r v i c e sm a yi n c l u d ed i f f e r e n t i a t e ds e r v i c e s f i n eg r a i n q u a l i t yo fs e r v i c e ，e t c 趟l s u c he n h a n c e m e n t sn e e dp a c k e tc l a s s i f i c a t i o n i - i o w e v e r ，p a c k e t c l a s s i f i c a t i o no nm u l t i p l ef i e l d si sad i f f i c u l tp r o b l e m h e n c e ，c u f r e n ta l g o r i t h m sa r eh a r d l ya b l e t om e e tt h er e q u i r m e n t so fv a r i e da p p l i c a t i o n sa n de v i r o n m e n t s s ot h ee v a l u a t i o ns y s t e m sa n d t h ef u n c t i o n a ls i m u l a t o r sa r en e e d e dt oh e l pt h er e s e a r c h e r ss i m u l a t i n ga n de v a l u a t i n gc u r r e n t a l g o r i t h m sa n dn e wo n e s ，w “ht h ev a l u a t i o ns y s t e m sa n dt h es i m u l a t o r st h e yc a nf i n do u tt h e b e t t e ra l g o r i t h m sf o rt h es p e c i f i e ds i t u a t i o n o rc a nt e s tt h e i rs t a t e o f - t h e a ni d e a so ft h en e w a l g o r i t h m s 灿s ot h ed e v e l o p e r so ft h en e t , y o r ke q u b m e r i t sr e l a t e dt op a c k e td a s s i f i c a t i o nc a l l f i n dv a l u a b l ea d v i c e sf r o mt h ee v a l u a t i o n s a f t e ra n a l y z i n gt h ec h a r a c t e r i s t i co ft h ep a c k e tc l a s s i f i c a t i o np r o b l e ma n ds t u d y i n gt h e p e r f o r m a n c e sw h i c hr e s e a r c h e r sa n dd e v e l o p e r sa r ei n t e r e s t e d ，w ed e f i n es e v e r a lm e t r i c st oh e l p e v a l u a t et h ep a c k e tc l a s s i f i c a t i o no naf i n es c a l e b a s e do nt h ec o n s i d e r a t i o no r lt h em e t r i c sa n d p a c k e tc l a s s i f i c a t i o ne n v i r o n m e n t s ，w ep r o p o s eag e n e r a lp e r f o r m a n c ee v a l u a t i o ns y s t e mm o d e l o fp a c k e te l a s s i f i c a t i o na n dt r yt os t a n d a r d i z et h em e t h o do fp e r f o r m a n c ee v a l u a t i o n a c c o r d i n g t oo u rt h e o r ya n a l y z i n go nt h ea l g o r i t h m sa n dt h ee v a l u a t i o ns y s t e mm o d e l ，q u a n t i t yo f i m p r o v e m e n t sa r ed o n eo nt h ep a c k e tl o o k u pa n dc l a s s i f i c a t i o ns i m u l a t o r ( p a l a c 、1 1 1 e s e i m p r o v e m e n t si n v o l v en e wf i l t e r s g e n e r a t i o nm o d u l e ，n e wh a r d w a r ea l g o r i t h ms u p p o r t i v e i n t e r f a c e ，t h er e f i n e m e n to nt h es t a t i s t i c sc o l l e c t i o na n dq u e r y ( s t a t ) m o d u l ea n dt h ec o n s o l e t h i sp e r f o r m a n c ee v a l u a t i o ns y s t e mp r o v i d e sab e t t e rt o o lt oe v a l u a t ec l a s s i f i c a t i o na l g o r i t h m s a tt h ee n do ft h i sp a p e r , s o m et y p i c a lc l a s s i f i c a t i o na l g o r i t h mi s t e s t e dw i t ht h ee v a l u a t i o n s y s t e m ，a n ds o m ec o n c l u s i o n sa r ed r a w e d t h i sm a yp r o v i d es o m ea d v i c e sf o rt h ef u t u r er e s e a r c h o np a c k e tc l a s s i f i c a t i o n k e y w o r d ：d i f f e r e n t i a t e ds e r v i c e 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 ，e v a l u a t i o ns y s t e m ， s i m u l a t i o ns y s t e m 1 i 国防科学技术大学研究生院学位论文 图表目录 图2 1 流识别路由器中报文处理路径。5 图2 - 2i p 报文分类的多个分类字段实例。5 图2 3 最坏情况下的分类器结构 8 k 6 表1 1 规则库示例7 图2 - 4s w i t c hp o i n t e r 添加方法8 图2 5g r i d o f - t r i e 数据结构及查询实例8 图2 - 6 二维规则在二维空间的分布图9 图2 7a q t 数据结构及查询实例1 0 图2 - 8f i s t r e e 数据结构查询实例1 1 图2 9 各元组对应h a s h 表构造示例1 3 图2 1 0 与规则库中两个字段联系的两个t r i e 树实例1 4 图2 1 1 在2 维空间建立的h i c u t s 树结构实例1 5 图2 1 2r f c 中的报文流1 6 图2 1 3h y p e r c u t s 决策树实例1 7 表2 - 2 报文分类算法时空复杂度比较1 8 图2 1 4 二维规则f 与空间区域a 的相互关系2 0 表3 - 1 评价体系包含的度量参数2 5 图3 - 1 报文分类算法测试系统基本模型2 7 图3 2 表示分类算法规模扩展性的测试数据n t 图2 9 图3 3i p 报文分类算法评测系统的通用模型3 0 图4 1p a l a c 系统结构模块结构示意图3 1 图4 2p a l a c 输入输出示意图3 2 图4 3p 觚a c 个功能模块的结构关系3 3 图4 - 4p a l a c 获取规则库信息图示3 4 表4 - 1 部分指定规则分配比例3 6 表4 2 协议字段与端口字段的相关性3 6 图4 5 规则库生成模块添加入p a l a c 3 7 图4 6f g e n 模块生成数据库的伪代码3 7 表4 3p a l a c 原有输出统计信息3 8 国防科学技术大学研究生院学位论文 图4 7p a l a c 的控制平台一3 9 图4 8 改进后的p a i _ , a c 控制平台4 0 图4 - 9p a l a c 原有算法仓库模块接口层次4 1 图4 1 0 改进后的p a l a c 算法仓库接口层次4 1 图4 1 1 通用t c a m 框架结构4 2 图4 1 24 k 7 2 的t c a m 的功能接口实现数据结构4 4 表4 4t c a m 类提供的功能接口4 4 表4 5 添加的功能接口函数4 5 图4 1 3 范围前缀转换算法的伪代码4 5 表5 1 实现算法简介5 0 图5 - 1g r i do ft r i e 算法类图5 0 图5 2 a q t 算法类图5 1 图5 3r f c 缩减树及各阶段索引表的存储分配5 2 图5 - 4r f c 算法类图5 3 表5 2t c a m 度量值测试结果5 5 表5 3g r i d o f - t r i e 度量值测试结果5 5 表5 4 a q t 度量值测试结果5 5 表5 5 三种算法基准性能相对评价计分- 5 6 表5 - 6t c a m 算法时间性能测试5 7 图5 - 4t c a m 算法n - t 曲线图5 7 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：! 里捏塞佥娄簋鎏迁型丕缠煎珏壅皇塞理 学位论文作者签名： 而彦 日期：卯，年上月学日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：! 里塑塞佥娄簋洼迁型歪缠的盟窒兰塞理 学位论文作者签名： 作者指导教师签名： 日期：? _ 彳寸q 年2 月步日 日期：砌年z 月扣勃 国防科学技术大学研究生院学位论文 第一章绪论 i n t e r n e t 的飞速发展给高速网络的使用带来了巨大的挑战和许多亟待解决的复杂问 题。物理链路速度飞快增长，目前，主流的骨干路由器如c i s e o 的1 2 4 x x 系列、j u n i p e r 的m 1 6 0 等路由器已支持o c 一1 9 2 接口。根据研究机构d a t a q u e s t 调查报告预测 1 ，到2 0 0 4 年，1 4 核心路由器间的链路速度将达到o c 一7 6 8 ( 4 0g b p s ) ，2 1 的边缘路由器间链路速度 将达到o c 1 9 2 ( 1 0o b p s ) 。要适应这种飞速增长，就要求作为连接链路结点的路由器性能 的提高，以期在单位时间内能够处理更多数目的报文。 另一方面，传统的i n t e r n e t 只是提供尽力传输( b e s t e f f o r t ) 的转发机制，采用先 到先服务( f i r s t c o m e f i r s t - s e r v e d ) 的方式对目的地相同的报文进行相同的处理，根 据报文的目的i p 地址决定下一跳的端口地址。随着各种网络应用的发展，未来i p 网络必 须为用户提供更多的服务类型和更好的服务质量，要求路由器提供额外的处理机笨g 来实现 区分服务e 2 ，防火墙访问控制( f i r e w a l l ) 3 、虚拟专用网( v p n ，v i r t u a lp r i r a t e n e t w o r k ) 、基于策略的路由( p o l i c y b a s e dr o u t i n g ) 4 、q o s ( q u a l i t yo fs e r v i c e ) 调 度、网络入侵检测监控( n e t w o r ki n t r u s i o nd e t e c t i o n ) 、网络地址转换( n e t w o r ka d d r e s s t r a n s l a t i o n ) 、拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 、流量记账( t r a f f i cb i l l i n g ) 5 、 资源预留( r s v p ，r e s o u r c er e s e r v a t i o ns e t u pp r o t o c 0 1 ) 、负载平衡( l o a db a l a n c i n g ) 等一些网络关键技术都是以报文分类为基础的。报文分类技术通常是基于多个字段信息对 报文进行处理，相对于报文转发就需要更多的操作。 综合上面两个方面，要适应链路速度的高速增长，实现对报文的线速转发，报文分类 技术要求在报文处理复杂度增加的同时增加单位时间内处理报文的数目。从现有的研究来 看，高速多维分类算法仍然存在一些不足，已经成为路由器新的瓶颈，因此对高效的报文 分类算法的研究很有必要。 1 1 研究背景 传统的i n t e r n e t 提供尽力传输( b e s t e f f o r t ) 的转发机制，采用先到先服务 ( f i r s t c o m e f i r s t s e r v e d ) 的方式对目的地相同的报文进行相同的处理。未柬i p 网络 必须为用户提供更多的服务类型和更好的服务质量，要求路由器提供额外的处理机制来实 现区分服务，其中报文分类、流标识是其中关注的重点之一。同时报文分类在网络技术领 域具有广泛的应用，许多网络关键技术，如区分服务、防火墙访问控制、基于策略的路出、 虚拟专用网、q o s 调度、网络入侵监测监控、网络地址转换、捌塞控制、流量记账、资源 预留、负载平衡、收集统计数据等都是以报文分类为基础的。从现有的研究来看，高速多 搪l “ 国防科学技术大学研究生院学位论文 维报文分类算法仍然存在很多困难，已成为路由器的新的瓶颈，因此吸引了很多研究人员 的注意。 由于i p 报文分类问题本身的复杂性以及应用环境的多样性，目前还没有提出在各种 情况下都满足不同需求的理想算法。从报文分类技术的应用环境来说，不同的应用对i p 报文分类算法的要求各有侧重。如v p n 的一种实现技术称为路由过滤技术，在这种机制中， i s p 在路由器中根据报文头的源、目的地址字段将不同的用户群划分为不同的通信域，每 个通信域构成一个v p n s ，为这些v p n s 进行通讯域划分的就是一个在源i p 地址和目的i p 地址这两个维度上进行分类的二维i p 报文分类器：而基于安全存取列表控制的防火墙对 报文进行分类过滤处理包括报文的源地址、目的地址，所用的源、目的端口号，传输层的 协议，还包括特定的网络服务协议等多个字段。另外，在异构网络中合成对延迟敏感的应 用数据如声音等时，对于报文分类的速度要求非常严格；而流量记账等网络管理应用的实 时性要求则相对较弱。从网络设备的角度来看，因特网提供新的有差别的网络新业务时， i s p 核心路由器、i s p 边缘路由器、食业内联网路由器、防火墙、工作站和服务器等对各 种新业务的支持是不一样的，它们分类器数据库的大小和特征也是不一样的。从路由器所 处的位置来看，骨干网核心路由器相对于边缘路由器而言要求更高的报文分类速度；从路 由器中分类规则数据库的规模来看，i s p 的访问控制列表( a c l ，a c c e s sc o n t r o lh i s t ) 数据库要比企业内部互联网的a c l 大得多，所需的报文分类算法要能够高效的运行在上千 甚至上万条规则的数据库上。另外，不同规则数据库的结构和特点也各不相同，导致其上 报文分类转发的复杂度各异，这对于大多数依据规则库本身的特点和冗余构建数据结构的 i p 报文分类算法的性能也有很大影响。 $ u m e e ts i n g h 等将其提出的报文分类算法h y p e r c u t s 与k f c 、h i c u t s 、a b v 分别在核 心路由器、边缘路由器和防火墙中的规则数据库中作了模拟测试 6 ，表现出不同的空间 和时间性能，但是模拟测试仅限于少数几类规则数据库和算法，并且也只是对模拟结果做 了简单的空间和时间方面的性能比较。而在此之前，研究人员在提出自己的算法时都只是 与少数相关的算法在单一的规则数据库上作一些简单的时间空间分析。目前该领域研究人 员只是侧重于证明所提出算法在某一方面的性能优势，并没有系统全面地将各类规则数据 库、各种算法及报文流这几类因素的变化综合考虑，分析比较每个因素的变化对于各个方 面的性能( 包括搜索时问、耗费空间、是否可动态更新、预处理时间、更新时间等) 影响。 而这项工作对于分析各种算法的适用环境以及在各种环境下的优势性能、了解掌握各种算 法的优点和存在问题的具体方面具有很重要的意义。而令人信服的报文分类算法性能评价 结果应该是以一个完善可靠的模拟测试环境和评价体系为基础的。报文分类算法的模拟测 试环境和评价体系具有很大的实际应用价值：在进一步设计研究高性能的分类算法过程 中，研究人员需要将新算法与其他算法进行评价，以确定设计思路的f 确性和价值；而报 国防科学技术大学研究生院学能论文 文分类产品供应商则需要通过与其他竞争产品之间的性能比较声明来推销自己的产品：对 于报文分类产品用户，例如路由器制造商，他们在路由器的开发研制过程中能够通过在统 一的标准上评价各个分类产品性能来选择所需的分类部件。 很多应用和数据处理设备研究领域中都开发了相应的基准测试环境，例如计算机系统 结构领域中使用标准的基准测试环境来评估微处理器的性能。虽然这些基准测试环境对于 是否能够精确区分系统结构的改善、制作结构的进步及编译优化所产生的影响还有待讨 论，但是它们最大的好处在于提供了一个供比较的统一环境。然而对于报文分类算法和产 品的性能评价仍然没有标准的评价工具或技术。 1 2 课题研究的工作重点和创新点 本文针对报文分类技术性能评价领域存在的问题和需要进行研究，主要包括以下几个 方面的工作： 1 对现有i p 报义分类算法进行了深入研究 从算法所依赖的主要数据结构及其核心思想的角度出发，对已有的典型报文分类 算法进行深入的分类研究。通过分析和比较，预测了未来高性能i p 报文分类算法的研 究和发展趋势，并提出了我们进一步对算法本身进行研究和设计的几个思路。 2 提出i p 报文分类算法的评价体系，建立评测系统模型 通过分析报文分类技术的特点及在不同应用领域中人们所关注的性能表现，我们 确定了对报文分类算法进行全面性能评价的度量参数，提出了一个较为完善的评价体 系。在全面考虑报文分类技术在网络中的应用环境，以及影响所需要测量的度量参数 的主要因素后，我们建立了i p 报文分类算法评测系统的通用模型，将i p 报文分类算 法性能评价工作标准化、规格化。 3 i p 报文分类算法模拟测试系统的实现 主要是以美国斯坦福大学的报文分类与查找模拟器p a l a c 为基础，根据所提出的 评价体系及报文分类算法的现状和发展趋势，添加了规则数据库生成模块、支持硬件 算法接口模块，并对输出统计模块、控制平台模块进行了完善和改进，建立了一个能 够提供完善的模拟环境和统计结果输出并且对各类算法的模拟都能够提供方便功能接 口的报文分类算法模拟测试系统。 4 典型报文分类算法的实现和模拟评测 针对我们实现的分类算法模拟测试系统，选取了一些典型的报文分类算法进行实 现模拟，基于模拟结果使用第三章提出的评价体系对它们进行了比较评价并给出相应 的评价结论。 第3 血 国防科学技术大学研究生院学位论文 1 3 论文组织结构 本文共分为六章。 第一章：绪论，主要介绍课题的背景、研究现状、本课题的研究内容与目标以及论文 的组织情况。 第二章：介绍了i p 报文分类问题的概念并已有的典型报文分类算法进行了深入的分 类研究。 第三章：深入讨论研究i p 报文分类算法评测系统的特点、结构，建立起评测系统通 用模型 第四章：介绍i p 报文分类算法评测系统模拟测试平台的实现，着重介绍了规则生成 模块、支持硬件算法接口模块，并对输出统计模瑰、控制平台模块的添加和完善工作。 第五章：针对所提出的评价系统，选取了一些典型的报文分类算法进行实现，使用模 拟测试平台进行测试评价，给出评价结果。 第六章：对全文进行了总结，并指出下一步的工作方向。 笫4m 国防科学技术火学研究生院学位论文 第二章相关工作研究 2 1 1 报文分类在网络中的位置 2 1i p 报文分类问题描述 分类处理一般处于通信子网的结点或路由器中，路由器分为识别流与非识别流的路由 器。识别流的路由器跟踪流的传输并对在同一个流的报文进行相似的处理，非识别流的路 由器( 也称报文一报文路由器) 则单独处理每个进入的报文。 在流识别路由器中报文的处理路径如图2 - 1 所示： 决 舞翌跳地址对报文进行分类鞭捂撮文对应的将报文交换到输 及输出端口得到相应操作“操作提供服务出端口 路曲查找报文分类 鬟特殊处理 交换调度 线卡交换系统 2 1 2 报文分类简介 图2 ：1 流识别路由器中报文处理路径 出 i p 报文分类技术为在路由器等设备中把到达的报文归类为不同的数据流提供了支持 机制：它用不同的规则来标识各个数据流，每条规则根据对报文头部各字段的分析指出该 数据流中的报文应当执行的相应操作，如拒绝某指定源地址发来的所有报文。这些规则的 集合我们称为分类器( c l a s s i f i e r ) 。图2 - 2 所示为对报文进行分类时需要分析的各个字 段的实例。 有赦萱荷 射麟1 6 6 靖口舭层目1 6 嗍6 。 第4 挈议 第3 号嚣地址第3 层嚣地址第3 肭8 6 议 第翎4 8 眦6 址第2 屡目4 8 b 的地址 1 j 一一一一一一一 图2 2i p 报文分类的多个分类字段实例 通常情况下，分类器数据库中的规则包含两种类型的字段源、目的i p 地址对用 来确定网络路径；传输层字段( 源、目的端口号和协议类型) 表示网络应用程序特征。目 前比较常见的分类组合是：源、目的i p 地址的二维分类和源、目的i p 地址、协议类型、 源、目的端口号的五维分类。 在使用了i p 报文分类算法的网络设备中，由于需要对每一个通过浚设备的i p 报文进 第5 血 国防科学技术人学研究生院学位论文 行处理，而i p 分类算法由于“多域”特征导致了此类算法的时间和空间复杂度较高，以 二维规则分类器为例，一条2 维规则可表示为二维欧几里得空间上的一个矩形，一个报文 头表示为该空间上的一个点，对报文的分类问题等价于在这样的一个空间内定位报文头所 代表的点属于哪些矩形( 高维情况为超立方体) ，由于现实规则库中的规则之间相互重叠， 使得问题的复杂性大大增加。图2 3 表示了最坏情况下一个二维规则分类器中规则相互重 叠的情况。因此分类算法的优劣对提供这些服务的网络设备( 如路由器) 的整体性能有决 定性影响。 2 1 3 报文分类定义 图2 - 3 最坏情况下的分类器结构 8 分类器中的每条规则由d 部分组成，r i 表示规则r 的第i 部分，它表示的是该条规 则对报文头第i 个字段的约束条件。当满足下列条件时我们说一个报文p 与一条规则r 匹 配：1 对于任意的i ，p 的第i 个字段满足r i 所表示的规则；2 当有l 条或多条规则满 足条件l 时，其中优先级最高的即为与该报文匹配的规则。与一条规则匹配的所有报文将 被执行同样的操作，用标识符c l a s s l d 来唯一表示。 i p 分类问题是最佳过滤规则匹配问题的一个实例，其核心是高效的查找算法。一般来 说，一个好的查找算法需要满足以下几个条件：查询速度快，占用内存少，能够运用于实 际中大容量的分类器，具备快速更新能力，对于分类字段的数目具有可伸缩性。 2 2 1 分类器实例 22 典型f p 报文分类算法比较研究 为对各类算法的查找过程进行具体况明，我们以一个包含有8 条两个字段规则的数据 库为例。 国防科学技术人学研究生院学位论文 表1 - 1 规则库示例 r u l e f i e l d 只p l d 、r “l ef 把l d ，f i e l d ， r n 0 0 * 0 0 +1 0 + 1 + r d r ， 0 0 +0 1 + r s 1 1 +1 0 + r 0 + +1 0 r 6 1 + 4 o + + r 3 0 4 + r 1 1 + 2 2 2 基于t r i e 树的算法 基于t r i e 树的算法是建立层次式的r a d i xt r i e 9 结构，查询时一旦在一个维度上得 到匹配结点，便开始在与该结点连接的另一个独立的t r i e 树上开始查询。这类算法在最 坏情况下需要的访存次数为用于分类的字段中比特位的数目。一般说来，基于t r i e 树的 机制对于一维查询比较有效，而在多维查找中会耗费大量的内存空间。主要算法包括 g r i d - o f - t r i e s 9 ，f i s t r e e 1 1 ，a r e a b a s e dq u a dt r e e 1 和e g t p c i 6 。 ( 1 ) g r i d o f - t r i e s g r i d - o f - t r i e s 是在h i e r a r c h i c a lt r i e s 和s e t p r u n i n gt r i e s 1 2 的基础上加以改 进提出的一种较为高效的适用于2 维的报文分类算法。 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 对一维空间上的r a d i xt r i e 数据结构进行简单扩展，采用递归 的方法构造而成。首先以规则集合c = ) 中所有规则的第1 个字段的前缀集合为基础构造 一个一维t r i e 树f 卜t r i e 。对于每一个表示某一前缀的结点p ，递归的构造一个( d 一1 ) 维的h i e r a r c h i c a lt r i e st 。，它是以规则集合 r r 1 = p ) 为基础构造的。结点p 和l 之 间用n e x t t r i e 指针连接。h i e r a r c h i c a lt r ie s 的空间复杂度是线性的，因为每条规则实 际只存储了一次。但是在进行查询匹配的时候，如果在t 。上没有后续维空间上匹配的规则， 则需要在上一维t r i e 树中进行回溯继续查找，使得其最坏情况下的时间复杂度过大。为 了解决这个问题，提出了s e tp r u n i n gt r i e 。 s e t _ p r u n i n g t r i e s e t p r u n i n gt r i e 通过复制规则来避免回溯，对于到达的报文在f i t r i e 中得到最长 匹配前缀，沿着它的n e x tp o i n t e r 向下查询，所有在该维上属于该最长匹配的前缀的规 则都会在后续t r i e 树的相应结点上复制，以保证每一个可能的匹配规则在这次遍历中可 以遇到。显然，这样避免了四溯造成的时闻浪费，但耗费空问也由于规则的频繁复制而大 大增大。 那么如何结合h i e r a r c h i c a l i r i e s 的空间优势和s e tp r u n i n gt r i e 中避免回溯的机 制呢，g r i d - o f - t r i e 引入了s w i t c hp o i n t e r 来达到这个目的。 国防科学技术人学研究生院学位论文 g r d o f - n i e g r i d o f t r i e 以一个两层h i e r a r e h i c a lt r i e s 树为基本的数据结构，对于收到的报 文( ，i ，2 ) ，在第一层t r i e 树中查找匹配，1 的最长前缀结点，然后跟踪它的n e x t p o i n t e r ， 查找f 2 一t r i e s 树中与f 2 的最佳匹配。为了减少空间存储要求使得一条规则在其中只占据 一个结点并且无需回溯查找，g r i d o f t i r e s 算法利用了预计算并在某些结点上保存一个 交换指针( s w i t c hp o i n t e r ) 使得查询时间为o q 矿) ( w 为字段的宽度) 。下面我们结合具 体的查询实例来进一步说明算法原理及s w it c hp o i n t e r 的使用。 r 图2 4s w i t c hp o i n t e r 添加方法 。i tj i n tc 。r 矿x h il “i 。r 一+ 徽矧娑 图2 5g r i d o f - t r i e 数据结构及查询实例 图2 - 4 根据表l 中的各条规则建立起二层的t r i e 树结构，并通过预计算在各个第二层 t r i e 树的结点之间添加了s w i t c hp o i n t e r 。图2 - 5 为报文( 0 0 ，1 0 ) 到达时所经过的 第一层t r i e 树t 上的路径及两个第二层t r i e 树t ( p ) 和t ( p ) ，分别为t 中两个表示前 缀p 和p ( 0 0 * g uo $ ) 的结点的n e x tp o i n t e r 所指向。t ( p ) 和t ( p ) 的结点之间存在 一个标记为“l ”的s w i t c hp o i n t e r 是满足下面的条件的：p 是p 的最长前缀，t ( p ) 中 的某个结点u ( 图例中为根结点) 没有标记为1 的予结点，若该结点所对应的前缀为s ， 第8 虬 国防科学技术大学研究生院学位论文 则t ( p ) 中没有表示前缀s l 的结点，而t ( p ) 中存在表示前缀s l 的结点v ，这时，u 和v 之间就可以用一条标记为“1 ”的s w i t c hp o i n t e r 来指向。报文( 0 0 ，i 0 ) 到达t ( p ) 的根结点时查找标记为l 的路径失败，便可以沿着根结点的s w i t c hp i n t e r 跳到t ( p ) 继续查找而无需在第一层t r i e 树t 中回溯。 s w i t c hp o i n t e r 的引入消除了单纯的层次t r i e 树中存在的回溯需求，只需要经历一 条路径就能够找到最佳匹配规则，并且不用复制规则，在时间和空间上都有较好的性能。 但由于其初始数据结构的建立需要大量的预计算，在插入或删除规则时都有可能需要建立 或删除n e x t p o i n t e r 和s w i t c hp o i n t e r 以及f 2 一t r i e s ，不利于数据库规则的快速更新。 g r i d - o f t r i e 适用于二维规则的报文分类，如目的地址一源地址对，并不具备处理分 类维数扩展方面的灵活性。大型核心路由器中常常包含有大量用于处理v p n 及多播转发的 目的地址一源地址过滤器，在处理这些二维分类问题时g r i d o f t r i e 是一个相当高效的分 类算法。 ( 2 ) a r e a - b a s e dq u a d t r e e ( a q t ) 这种算法也是使用递归空间分解进行报文分类的算法思想的在二维空间上的一个实 例。这种思想基于用几何的观点对二维规则进行解释：每条二维规则看作为欧几里得空间 中的一个矩形区域，每个报文可看作是该空间中的一个确定的点。 具体的分解过程可以用q u a d t r e e 来表示，q u a d t r e e 是一个用于表示对空间进行二元分 解的4 向分支树。树中的每个节点v 代表分解过程中的一个方形区域，它的四个子节点对 应于将结点v 所表示的二维空间划分成的大小相等的四个象限空间。如图2 - 6 中的正方形 被划分为的四个子正方形，分别用图2 7 中的四个子结点v 1 ，v 2 ，v 3 ，v 4 来表示，如果一 条规则至少跨越了了该空间的一个维范围，则将该规则分配给该结点，已经分配过的规则 不再参与分配。对每个结点分别进行再分解，直到每个象限中只含有一条规则。 其巾发生重叠的部分，h 显示优先 绒较高的规则( 即山现在规则列表 中较前位置的规则) ，图中r 3 的一 i 部分被r 2 ，r 1 和r 0 覆盖，r 7 的左部 被r 3 和r 4 覆盖。 图2 - 6 二维规则在二维空间的分布图 第9 虹 国防科学技术火学研究生院学位论文 具体实现的时候同时对两个维度进行处理：在进行查询时，算法每次处理两个比特位 ( 每一维上顺次选一个) ，在每个结点上进行两次一维查找得到落入其范围的子结点。如 图7 对于到达的报文( o o 丰，1 0 ) 根据每一维的第一位进入0 l 子象限结点，该结点不存 在分支节点，即可得到尺，为最佳匹配规则。 r o ( r l 图2 7a q t 数据结构及查询实例 报义( 0 0 ，1 0 ) 的查询路线 a q t 提供一种非常有效的更新机制，对于n 条规则的二维分类器，只需要( 口：万) 的 更新时间，a 是一个可调的整数参数。 可以看出，a q t 树的最大高度等于参与分类的字段的宽度，比起g r i d o f t r i e 对每个 字段都要建立一层t r i e 树的层次结构，前者的查询速度要高于后者。 ( 3 ) f a ti n v e r t e ds e g m e n tt r e e ( f i s - t r e e l f i s t r e e 数据结构是根据规则在一个坐标轴上的投影所形成的分段集合建立的。其叶 结点表示各个分段的端点将坐标轴划分成的各个基本问隔，如图8 中的 0 0 0 ，0 0 1 、 0 1 0 ， 0 1 1 等。f i s t r e e 的任一内部结点表示其子结点表示范围的合集，并且每个结点v 都保存 有指向起父结点p a r e n t ( v ) 的指针。每个结点v 包含一个规则的规范集合( c a n o n i c a ls e t ) s ，设该结点表示的范围为i ( v ) ，若存在规则r ，使得i ( v ) r 但i ( p a r e n t ( v ) ) 旺r ，则r s 。 具体在解决二维分类问题时，首先根据所有规则在x 轴上的投影分段集合建立f i s t r e e ( x f i st r e e ) ，再根据每个结点所存储的各个规则规范集合在y 轴上投影的分段集合建 立相应的f i s t r e e ( y - f i st r e e ) 。 查询过程分两个阶段，如图2 - 8 所示。首先从x f i st r e e 的根节点出发到达表示包含 报文的基本间隔的叶结点，然后沿指向父结点的指针倒退查询，在每个结点对其相应的 y - f i st r e e 进行查询，找