（计算机软件与理论专业论文）基于网络处理器的包分类引擎设计与实现.pdf

硕士学位论文 摘要 网络规模和性能的迅速增长，要求当前和未来的网络设备具备线速和智能处 理能力的同时，又需要高灵活性。通用c p u 和专用集成电路( a s i c ) 已不能同时满 足这些要求。网络处理器通过良好的体系结构设计和专门针对网络处理部件的优 化，为上层提供了一个可编程控制的环境，很好地解决了硬件加速和软件可扩展 的折衷问题。网络处理器被认为是推动下一代网络发展的核心设备。 同时，网络信息安全的发展要求路由器等设备能够支持基于策略的路由、防 火墙、入侵检测等功能，实现这些功能的关键是包分类技术。包分类算法作为包 分类技术的核心，其性能对网络的时延和吞吐量有决定性的影响。 本文以网络处理器为硬件核心，结合提出的并行包分类算法，设计和实现了 一个包分类引擎系统。主要工作包括： l 、在a b v 算法基础上，提出了基于分类域聚集的a 2 b v 包分类算法。该算 法通过对现有策略库的统计分析，结合a b v 算法的并行思想，在对分类规则进 行维数压缩后，再“聚集”规则位图，使并行分类查找由原来的五维压缩为三维。 从而降低了a b v 算法的空间复杂度，提高了查找速度，同时更适合用网络处理 器来实现。 2 、以i x p 2 4 0 0 为硬件核心，运用a 2 b v 算法设计和实现了一个高速包分类引 擎系统。文章分析了i x p 2 4 0 0 的硬件体系架构，基于i n t e li x a 框架提出了实现 包分类引擎系统的软件架构和硬件架构，并给出了软件架构中各功能模块的详细 设计及性能分析。同时根据a 2 b v 算法的并行性要求，对i x p 2 4 0 0 的微引擎和存 储资源分配作了合理的规划。 3 、针对a 2 b v 算法实现过程中产生的存储器访问延迟进行了优化。通过对 i x p 2 4 0 0 中指令流水线和存储器访问指令的分析，在存储器访问的延迟内插入其 它并行微码指令，填补了工作线程在这段时间内的闲置，减少了微引擎中空闲时 钟周期数，进一步提高了整个系统的功能。 关键宇：网络处理器；a 2 b v 算法：i x p2 4 0 0 ；包分类引擎 基于网络处趣器的包分类引擎设计与实现 t h ei n c r e a s i n go fn e t w o r ks c a l ea n dp e r f o r m a n c er e q u i r e st h a tt h en e t w o r kd e v i c e s o fn o wa n df u t u r ec a l lw o r k 采l i n e s p e e da n di n t e l l i g e n t l ya sw e l la sh i 醢f l e x i b i l i t y t h eg e n e r a lc p ua n dt h ea s i cc a n tm e e tw i t hb o t ho ft h en e e d w i t ht h ew e l ld e s i g n o fa r c h i t e c t u r ea n ds p e c i a lo p t i m i z a t i o nt ot h ep r o c e s s i n gu n i t ，n e t w o r kp r o c e s s o rc a n p r o v i d eap r o g r a m m a b l ee n v i r o n m e n tf o rt h eu p p e rp l a n e ，w h i c hp r o v i d e sag o o d s o l u t i o nt ot h ep r o b l e mo fs o f t w a r ee x p a n d a b i l i t ya n dh a r d w a r ea c c e l e r a t i o n n e t w o r k p r o c e s s o ri sr e g a r d e da st h ec o r ed e v i c ep r o m o t i n gt h ed e v e l o p m e n to fn e x tg e n e r a t i o n n e t w o r k s i m u l t a n e o u s l y , t h ed e v e l o p m e n to fn e t w o r ki n f o r m a t i o ns e c u r i t yd e m a n d st h a t t h er o u t e r sc a ns u p p o r tf u n c t i o n s ，s u c ha sp o l i c y - b a s e dr o u t i n g ，f i r e w a l la n di n t r u s i o n d e t e c t i o n t h ek e yo fi m p l e m e n t i n gt h e s ef u n c t i o n si st h et e c h n o l o g yo fp a c k e t c l a s s i f i c a t i o n ，a st h ec o r eo fp a c k e tc l a s s i f i c a t i o nt e c h n o l o g y , t h ep e r f o r m a n c eo f 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 mh a sac r u c i a li n f l u e n c eo nt h et i m ed e l a ya n dt h r o u g h p u t o ft h en e t w o r k t h i sp a p e rd e s i g n sa n di m p l e m e n t s 繇e n g i n es y s t e mo fp a c k e tc l a s s i f i c a t i o n a p p l y i n gt h ep a r a l l e lc l a s s i f y i n ga l g o r i t h m ，i nw h i c hn e t w o r kp r o c e s s o ri st h eh a r d w a r e c o r e t h em a j o rw o r ki n c l u d e ： 1 、a p p l y i n gt h ea g g r e g a t i o nt ot h ef i e l d so ft h er u l e s ，aa 2 b va l g o r i t h mi s p r e s e n t e db a s e do nt h ea b va l g o r i t h m a f t e rs t a t i s t i ca n da n a l y s i st ot h ep r e s e n tr u l e l i b r a r i e s ，a 2 b va l g o r i t h mr e d u c e st h er u l ef i e l d sf r o mf i v et ot h r e e ，w i t h o u tl o s i n gt h e p a r a l l e l i s mo ft h ea b va l g o r i t h m 。a 。b va l g o r i t h mh a sal o w e rs p a c ec o m p l e x i t yi n c o m p a r i s o nt oa b va l g o r i t h m ，w h i l ei ti sm o r ep r a c t i c a lb e i n gc a r r i e do u to nn e t w o r k p r o c e s s o r 2 a p p l y i n ga 2 b va l g o r i t h m ，ah i g hs p e e dp a c k e tc l a s s i f i c a t i o ne n g i n e i s p r e s e n t e db a s e do ni x p 2 4 0 0 ，a f t e ra n a l y z i n gt h eh a r d w a r ea r c h i t e c t u r eo fi x p 2 4 0 0 ，w e d e s i g nt h es o f t w a r ea r c h i t e c t u r ea n dh a r d w a r ea r c h i t e e t u r eo fa l lp a c k e tc l a s s i f i c a t i o n e n g i n eu n d e rt h ei n t e li x af l a m e ，a l s og i v i n gt h ed e t a i l e dd e s i g no ff u n c t i o nb l o c k s a n di ta l s om a k e sar e a s o n a b l ea s s i g n m e n ta m o n gt h em i c r o e n g i n e sa n dm e m o r y 3 a c c o r d i n gt ot h em e m o r ya c c e s sd e l a yc a u s e db yt h ei m p l e m e n to f t h ea 2 b v a l g o r i t h m ，a no p t i m i z a t i o ni sp r e s e n t e d a f t e ra n a l y z i n gt h em e m o r ya c c e s si n s t r u c t i o n a n di t sp i p e l i n e ，w er u no t h e r sm i c r o c o d e sp a r a l l e ld u r i n gt h i sd e l a y , t h i sl e a d st ot h e i d i ec y c l ed e c r e a s eo fm i c r oe n g i n e 琰士学位论文 k e yw o r d s ：n e t w o r kp r o c e s s o r ；a 2 b va l g o r i t h m ；i x p 2 4 0 0 ；p a c k e tc l a s s i f i c a t i o n e n g i n e i l l - 基于网络处理器的包分类引擎设计与实现 插图索引 图2 1 包分类器结构4 图2 2r f c 算法的4 阶段缩减树1 0 图2 3 网络处理器的体系结构1 3 图3 1 位并行算法示例图，1 7 图3 2 简单的t r i e 树结构1 8 图3 4 位并行算法的硬件实现2 2 图3 5 集聚域的结构映射2 5 图4 1i n t e li x a 可移植性架构2 9 图4 2i n t e li x p 2 4 0 0 体系结构3 0 图4 3 线程状态转换图31 图4 4 基于网络处理器的包分类系统3 2 图4 5 位并行算法的并行映射3 3 图4 6 位并行算法的流水线映射3 4 图4 7 分类引擎系统结构3 5 图4 8i x p 2 4 0 0 的微引擎分配3 5 图4 9 接收数据状态的转换3 7 图4 1 0n i e 节点数据结构3 9 图4 1 1n e x th o pd a t a b a s e 结构4 0 图4 1 2 单线程的s r a m 访问指令4 3 图4 1 3 多线程的s r a m 访问指令4 4 图4 1 4 执行线程中的队列阻塞4 4 图4 1 5 插入指令后线程的并发运行4 5 图5 1i n t e li x a 3 5 组件图5 1 图5 2i o 仿真5 3 图5 3 时钟频率参数配置一5 3 图5 4 内存参数配置5 4 图5 5p o si p 流仿真一5 4 硕士学位论文 附表索弓 表2 1 简单的二维分类器 表2 2 网络处理器与通用c p u 及a s i c 的结构比较 表3 it r i e 规则示例表 表3 _ 3 常见协议类型号的对应映射 表3 4 常见端口号的对应映射 表3 5 压缩前的5 维分类器 表3 6 压缩后的3 维分类器 表4 1 系统存储资源分配表 表4 2 接收重组状态信息格式 表4 3 接收数据状态跳转表 表4 4 策略表字段的定义 表4 5n e x th o pi n f o r m a t i o n 字段的定义一 表4 6 队列描述的字段定义 表4 7q u e u e 的数据结构 表4 8q u e u e 传输信息结构 表4 9 队列描述符结构 表5 1 包接收模块中的存储器访问 表5 2 包分类模块中的存储器访问 表5 3 队列管理模块中的存储器访问 表5 4 发送模块中的存储器访问 表5 5 存储器总线状况 9 1 4 1 9 2 4 2 5 2 6 2 6 3 6 3 8 3 8 3 9 4 0 4 1 ：4 2 4 2 4 3 4 9 5 0 5 0 5 1 5 5 湖南大学 学位论文原刨性声瞬 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特剐加以标注弓i 用的内容外，本论文不包含任何 葵拖个人藏集体已经发表或撰写静残巢俸鑫。对本文鼹研究傲爨重要贡献 的个人蚕匠集体，均已在文中以盟确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：似日期：f 年3 月刀e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查酒和借阕。本人授权潮南大学可以将本学位论文静全部躐部分内容编入 蠢关数据露进行检紫，可以采用影零、绽霹或握糕等复制手段保存程汇缡 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不傈密口。 ( 涛奁以上猩盛方框凌t t “4 ”) 作者签名：t 医排 日期：莎卯厶年；月? 日 导师签名：积嗍跏年弓月彳日 硕士学位论文 1 1 研究目的及意义 第1 章绪论 本课题受湖南省自然科学基金项目：高速网络环境下入侵检测技术研究资助。 随着网络技术的发展和应用范围的扩大，人们越来越依赖于网络进行信息的 处理。信息基础设施已成为国民经济的一个重要支撑点【lj ，作为信息基础设施的 一个重要组成部分，信息安全关系到国家的存亡，经济的发展，社会的稳定。目 前，保障信息安全的主要手段是基于策略的路由【2 1 、防火墙【3 1 、入侵检测【”、虚拟 专用网( v p n ) t 3 1 等技术。 高速网络技术如a t m 、千兆以太网等的迅速发展，网络流量高速增长，各种 宽带接入手段层出不穷【5 】。如何实现高速网络环境下的实时信息安全检测，已经 成为目前所面临的问题【6 l 。目前主干网络上的安全产品其性能指标与实际要求相 差较远【7 1 ，其数据处理速率和灵活性远远不能满足网络的高速发展，当网络流量 达到千兆或更高些时，这些产品的性能均大大下降，丢包率很高。 为了提高信息检测系统的处理速率，适应网络的高速发展，达到在高速网络 环境下近似实时的检测，就必须采用新的硬件体系结构，结合高效的包分类算法， 从网络底层实现信息分类检测。 基于策略的路由、防火墙、入侵检测等都属于数据包分类任务，这些任务的 实现主要由分类引擎来完成，分类引擎系统的核心是网络处理芯片和数据包分类 算法，处理芯片的使用决定了包分类算法的选择。网络处理器作为一种新兴的处 理芯片，其专门为网络处理而进行优化设计的硬件结构1 8 j 提供了高速强大的网络 处理平台，适应了网络处理宽带化的趋势；完全可编程的网络处理模式提供了灵 活多样的网络处理功能，满足了网络业务综合化的要求1 9 】。其高并行性和完全可 编程能力使得网络处理器被认为是推动下一代网络发展的核心设备。而并行包分 类算法因其内在的并行性，非常适合采用硬件并行运行来获得更好的算法性能【9 】。 本项目研究正是基于上述特点，将网络处理器技术和并行包分类算法结合起来， 设计和实现了一个包分类引擎系统。基于网络处理器的包分类擎的设计与实现， 为高速网络下信息安全的实时检测，促进新一代信息安全检测技术研究的深入， 将产生良好的社会与经济效益。 基于网络箍攥器魍急势粪； 擎设计与实瑷 1 2 研究内容 数据包分类是实现基于策略的路由、防火墙和入侵检测等功能的核心。包分 豢技术主要包括：镪分类算法、硬俘平台、包分类功麓摸块设计数及各模块豹洼 熊评铡。高速隧终下包分类技术魏磷突主要有爨下几个方蘑： 1 何种硬件平台适合数据包的快速分类。目前高速网络数据的传输速率非 常大，新的网络业务不断出现，网络信息的安全要求逐渐提高。同时， 基于市场对网络产品的快速反应，所以选择的邋种硬件平台在功熊、灵 活性、拜发艘本班及枣场存涵嬲等方委有一个较麓熬综合性能； 2 谤释毽分类算法适合所途硬佟平台。包分类楚蘩予策略静路由、陡火麓 和入侵检测等技术的基础，熊功能直接影响整个网络的整体性能，所以 该算法应适合所选硬件平台的体系结构。 3 数据包分类在硬件平台上的映射方式。针对同一硬件平台可以有不同的 算法欧瓣，不弱懿映射其分炎牲髓结果会不一撵。所选浃射方法戍考虑 实舔静应溺繇凌，在综台毪怒上耱涛蹩数据惫耱线速筵理要求。 4 包分类流程的安排和系统资源的规划。嵌入式系统的硬件资源非常有限， 如何有效划分和安排包分类的各个功能模块，并对系统资源作合理的规 划，这将对嵌入式系统的资源利用和提高系统性能有很大影响。 零文分辑了现蠢包分类算法稠i x p 2 4 0 0 瘸络处理器麓硬磐钵系结构，缝合两 雾靛特点，稿建了一个萋予i x p 2 4 0 0 溺络处理器匏毽分类弓l 擎结毒毒，实珉了一个 能满足o c 4 8 逮率下包线速转发功能的分类引擎系统，并利用i n t e l 提供的 d e v e l o p e rw o r k b e n c h 集成环境对系统进行了仿真测试和分析。 1 + 3 本文主要工侔 本文根据现今商速网络下数据流纛的增长，以及网络信息安全对网络设备的 需求，分析了现有网络数据包分类算法的特点；针对新兴的网络处理器平台，提 出了一种适合网络处理器实现的并行靓分类算法。基于i x p 2 4 0 0 设计l 一个包分 炎零l 擎，并绘出了锫模块豹详缨设计。然后对分类弓i 擎中戆关键技术进行了谯纯， 簸落逶过费卖绘密系统设诗戆萑篷测试结莱帮努辑。爨钵工作蟊下： 1 分析了网络处理器的体系结构及其在网络数嘏处理方面的优越穗。对 i n t e li x a 架构中i x p 2 4 0 0 网络处理器的软件模块和硬件模块作了详细的 描述，并就其高并行性和可编程特点进行了深入了解。 2 + 分析了现鸯数据包分类算法熬特点。针对网络处理器的并行体系黎构提 硕士学位论文 出了a 2 b v 包分类算法。a 2 b v 算法以a b v 算法为出发点，通过对现有 策略库的统计分析，采用对分类域聚集的方法，减少了分类的维数。从 而降低了算法的空间复杂度，减少了算法执行时间；同时也节省了网络 处理器的硬件处理资源。 3 应用a 2 b v 算法，基于i x p 2 4 0 0 网络处理器提出了实现包分类功能的软 件架构和硬件架构，并对软件架构的各个模块作了详细设计。同时对i x p 2 4 0 0 的存储资源分配作了合理规划。 4 根据算法运行时产生的存储器访问延迟，采用微码指令插入技术，填补 了存储器访问延迟期间执行线程的空转。有效地解决了因存储器访问延 迟而产生的微引擎性能下降问题。 5 利用i n t e l 提供的i x as d k 集成开发环境，完成了上述工作及系统功能的 仿真和测试分析。 1 4 本文组织结构 全文共分5 章，各部分的内容组织如下： 第1 章概述了本文的研究目的、意义和内容，介绍了本文所做的研究工作。 第2 章详细介绍了相关的背景知识及研究现状，包括网络数据包分类的定 义、分类器和分类规则的原理、典型的包分类算法以及包分类算法的性能评价标 准；最后分析了网络处理器的技术原理及其在网络数据处理方面的性能优势。 第3 章分析了位并行包分类算法的原理及特点。并针对其不足，采用对包分 类规则维数的压缩，提出了一种新的基于网络处理器的包分类算法。 第4 章运用改进后的包分类算法设计了一个基于i x p 2 4 0 0 处理器的包分类 引擎系统，详细描述了系统的模块设计及实现；分析了微引擎的外存储器访问过 程，并就产生的访问延迟提出了优化方案。 第5 章对各模块的性能进行了评估，利用i n t e l 提供的d e v e l o p e r w o r k b e n c h 仿真环境对系统进行了功能仿真并给出了仿真结果和分析。最后总结全文。 基丁网络处理器的包分类引擎设计与实现 2 1 数据包分类原理 2 1 1 包分类的定义 第2 章相关研究 数据包分类就是根据数据包奉身携带的信息或与数据包有关的信息( 主要足 指i p 包头和传输层头部携带的信息) 索引预先设置的分类器，查找匹配的规则来 达剑区分数据包的目的 1 0 1 1 1 1 1 2 1 ( 如图2 1 所示) 。数据包分类的结果决定了这个数 据包属于哪一个数据流以及此数据包应得到什么样的服务等级，然后包转发引擎 根据分类的结果采用相应的处理来满足用户的需求，这些处理可能包括丢弃未授 权的分组、进行特殊的排队和调度处理或者作为路由选择的依据等。其数学模型 描述1 1 3 1 如下： 假定一个分类器c ( 它是规则的集合，也称为策略数据库、流分类器) 含有 n 个规则r j ，( 1 j n ) ，壶u 果对报文头的k 个字段进行分类，这里的规则r j 由 3 部分组成： 1 一个关于每个报文头k 个字段的正则表达式r 【i ，1 i k ，通常用具 体的值、范围表达式或者是前缀表达式表示。 2一个整数，p r i ( r ) ，表示这个规则在分类器中的优先级，用来当一个报文 同时匹配多个规则时来决定哪个规则优先。 3 一个行为a ( r j ) ，表示当这个规则被匹配后应对报文所做的操作。 对于一个进入路由器的报文p ，假设考虑报文头的k 个字段( p i , p 2 ，p k ) ， 则k 维报文分类是指在所有匹配( p i , p 2 ，p k ) 的规则r j 中找一个具有最高优先 权的规则r 。即p r i ( r 。) p r i ( r j ) ，j m ，1 j n ，且满足p i 匹配r j i 】，1 i k 。我们称r 。是报文p 的最佳匹配规则。数据包分类的流程如图2 1 所示。 i p 包1 i p 包1 1 图21 包分类器结构 图21 包分类器结构 硕士学位论文 糯有的蹋络大都憝熬予“b e s te f f o r t ”服务匏。扶i n t e r n e t 发展趋势来看，来 来的i p 网络必须为用户提供更多的服务类溅和更好的服务质摄，能够给网络信息 提供熙大的安全保障。遮魑服务包括区分服务、基于策略的路由、服务质量( q o s l 、 流量计费、防火墙、入侵检测、虚拟专用网( v p n ) 等等。所钶这些服务都需要将 弱这熬数据包舞类爻不溺麴数摇滚，禳攘不嚣戆鼗莛滚采决是该数器包我遗一步 处毽。如是否转发、内哪墨转发数据包，怒否对数据包内餐进季亍检测等一系捌阏 题。像们都是以包分类( p a c k e tc l a s s i f i c a t i o n ) 技术i l l 】为基础的。由于在i n t e r n e t 上 路由器传送处理的数据甑绝大部分都是i p 包，因此，包分类技术也称为i p 分凝 ( i pc l a s s i f i c a t i o n ) 技本。 l p 查找主要是基予臻囊戆壹援，遂豢只是遴遘查我l p 魏头孛熬基懿建缝壤 来决定下一跳( n e x t h o p ) 的地址。丽i p 分黉遥常是查找i p 包头中的多个域，戳此 决定熬归属哪个数据流，这是它和i p 查找的本质区别。 i p 分类问题是最佳过滤规则匹配问题的一个实例。理论上讲共有7 个域可被 选择成为过滤规则的域：源、目的i p ，源、目的端日，t o s 域，协议类型和协议 蠢卷。实际主，逶遂绞诗e 鞑】发凌过滤蔑剿黪不是踺菠有熬躐簿惑兴趣，2 。1 。2 节绘 出了贸际串常见分类域瀚使用情况。 2 1 2 分类器和分类规则 分类器是分类褒萸l l 露分类策略熬集合。一般情提下，分类器孛匏一条戴粼钱 表一耱照务流，在数摇叙转发过程串接受捆网豹鼹务。分类勰刘是分类算法簸瑷 数据包的依据。一条分类规则可以看成怒一个过滤器( f i l t e r ) 和一种处理行为 ( a c t i o n ) 的组合。因此，旗于目的地址的i p 路由可以看作是分类的一个特例( 熙 对目的i p 地址进行匹配) 。路由表就是一个分类器，路由袭中的每一条路由表颂 就是一条分类援刘，藤遴避埝出端日转发分缀就是分类中的楚溪霞走。通常分类 囊粼过滤器涉及簧数攘镪包头豹一个或多个字段，如源p 撼疆( 3 2 b i t s ) 、雷豹i p 地址( 3 2 b i t s ) 、源端口( 1 6 b i t s ) 、目的端口( 1 6 b i t s ) ，协议( s b i t s ) ，t o s ( s b i t s ) 等字 段。分桊后的处理行为包括数据包的调度策略、带宽管理策略、路由选择策略、 内容枪测等。此外处理行为中还必须包括一个优先级标识符，以此来解决一个数 据惫簿会多个分类援则豹愤瀑，即分类筑粼瓣稳互重叠。邋耱愤猛一般采焉缀剿 铙先级獯撵来簿决【并】。磁究表臻矧，分类嚣遥常具有懿下死令特点： 1 现有分类器大多不包含数目巨大的分类规则。但随稽业务量的增大，网 络安全性的增强，分类器的规则将会越来越多。在大多数网络里，分淡 规则的配置是由网络操作员手工进行的； 2 。遴零分类规则涉及刭斡傣患域有刚络震源、基鲍圭| 蔓撼，传辕层源、毽黥 基于网络处理器的包分类引擎设计与实现 端口号，服务类型( t o s ) 域，协议域和传输层协议标志域等。目前研究表 明：有1 7 的规则只对一个域进行说明，有2 3 的规则对三个域进行说 明，其余6 0 的规则对四个域进行说明； 3 传输层协议域的取值只限于一个较小的范围：传输控制协议( t c p ) 、用户 数据包协议( u d p ) 、i n t e r n e t 控制消息协议( i c m p ) ，i n t e r n e t 组管理协议 ( i g m p l 、内部网关路由协议( i g r p ) 和通配符”； 4 分类器中分类规则的表示方式不仅仅局限于精确匹配( 如源端口为8 0 ) ， 还存在有大量的区间表述( 如源端口号为2 0 3 0 ) 、前缀表述( 源i p 地址为 1 9 2 1 6 8 4 1 等： 5 同一分类器中的不同分类规则可能存在不同程度的重叠现象，如部分重 叠、完全包含等。 从上面的结论可以看出，现有分类算法处理的维数基本少于5 维，这是因为 维数越多，分类处理就越复杂，对硬件平台的要求也就越高。但网络应用的发展 需要对更多的维数进行查找匹配。本文设计选用5 个参数作为过滤规则的域，即： 源，目的i p ，源目的端口以及协议类型。 2 1 3 数据包分类技术的划分 依据不同的划分标准【l4 1 ，我们可以大致把包分类技术划分为以下三种： 1 根据分类规则涉及的分类域的个数，数据包分类可以划分为多维分类和单 维分类。在多维分类中分类规则过滤器涉及到数据包包头( 包括网络层头和传输层 头部等) 的多个字段。目前多维分类的分类规则一般涉及5 个域：源i p 地址( 3 2 b i t s ) 、目的i p 地址( 3 2b i t s ) ，源端口( 1 6b i t s ) 、目的端口( 1 6b i t s ) 以及协议类型( 8 b i t s ) ， 共1 0 4b i t s 。单维分类中，分类规则过滤器则只涉及数据包的一个域。路由表可 以看成单维分类的一个特例。 2 根据分类功能在协议栈中所处位置的不同，数据包分类可以分为传输层分 类、网络层分类和链路层分类等，在入侵检测等功能中还需要对应用层进行分类。 根据这种划分标准区分的分类技术只涉及到协议栈中某一层的信息，如网络层分 类技术的分类规则可能涉及到源i p 地址、目的i p 地址等，但是不会涉及到运输 层的有关信息( 如运输层协议端口号等) 。按层次划分的分类技术常常结合起来使 用，以达到较好的区分分组的效果。 3 根据分类器中分类规则是否重叠可以把分类技术划分为重叠分类和非重 叠分类。非重叠分类的分类规则两两互不相交，在非重叠分类中不会出现一个分 组经过分类器后匹配多条分类规则的情况。而在重叠分类中因为分类规则可以任 意重叠，所以可能会出现一个分组经过分类器后匹配多条分类规则的情况。而分 硕士学位论文 类规则的重叠是十分普遍的现象，因此分类算法应该解决规则重叠问题。现在算 法一般采用规则优先级来解决这个问题，从而实现一个分组最终匹配唯一的一条 分类规则。 2 1 4 数据包分类的要求 网络中的数据包分类是一项极其复杂的处理任务，可能会成为包路由中的“瓶 颈”。主要是因为具体的应用环境【1 6 1 复杂，要考虑的问题特别多。主要有： 1 网络资源的限制：网络连接的方式各种各样，访问速度从住宅用户的t 1 到网络i s p 边界的o c 1 2 ，o c 4 8 或更高，范围变化非常大。这就要求数据包的分 类方案能够在每个包的分类时间和资源需求之间进行调节，达到要求的访问速度 并最小化资源的使用数量。 2 策略库的规则数量：数据包分类问题因不同的应用场合，规则数量差别巨 大。目前，典型的防火墙可能规定几百条过滤器规则【l ”，而一个骨干路由器可能 有几十万条规则，这些数字还可能由于增强服务和路由器吞吐量扩大到上百万条。 3 分类域的个数：在不同的数据包分类应用中，用于分类的i p 包头域的数 量是不同的。传统的路由器只使用目的地址一个域，新一代的路出器为了提供防 火墙、入侵检测等其它的复杂应用可能使用更多的域。 4 规则的形式：传统路由器规则使用目的i p 地址的前缀形式，由于网络地 址的划分更灵活，目前网络地址更多的是使用范围来表示。数据包的分类算法应 该能提供对范围的访问。 5 过则集滤规的更新：由路由或策略的改变引起的规则更新数量相对于整个 规则库来说往往是很少的，为每一个更新重建全部数据结构是不允许的，这就需 要算法能够支持渐增式更新 6 分类算法的性能：分类算法是分类技术的核心部分，不同的分类算法支持 的分类速度和分类器大小不同，同时需要的存储空间和处理速度也存在很大差异。 所谓分类算法就是实现数据包分类信息域和分类器某一条规则相匹配的一种方 法，一般包含分类器的预处理过程和分组的查找过程两部分。预处理过程就是将 分类规则所对应的数据进行处理，然后按照一定的结构存放。查找过程则对处理 后的结构进行操作，区分到达的分组数据。一般来说，分类算法的性能包括查找 时间、存储空间、预处理时间、规则更新时间等【l 引。一般来说不能同时满足这几 个性能指标。在选择分类算法时必须根据系统性能的总体要求对这几个指标做折 衷处理。 基于网络处理器的包分类引擎设计与实现 2 2 数据包分类算法 2 2 1 常见数据包分类算法 所谓分类算法就是实现数据包分类信息域和分类器某一条规则相匹配的一种 方法，其主要应用在路由器、交换机等包交换设备中。路由器通过查找数据包头 部中目的i p 地址来决定其下一跳信息【39 1 ，查找参数只需一个域。而包分类则往 往需要对包头中的多个域进行查找。因此，i p 地址查找是包分类中的一个特例。 i p 地址查找的关键字是前缀( 代表一组i p 地址集合) ，查找的目的是找到最长匹 配前缀 2 6 】( 即最佳匹配规则) 。包分类中，其查找的对象不仅是前缀，还可能是 一个任意的范围，如端口号为【2 0 ，3 0 】。这就使得查找更为复杂，文献 2 l 】给出了 如何将范围查找转换为前缀匹配问题，使得任意范围查找问题都可以用前缀匹配 算法来解决，这使得包分类更现实。数据包分类算法1 2 1 1 主要有以下几大类： 1 、简单包分类算法 地址索引和线性查找是两种非常简单的i p 地址查找算法。 地址索引查找算法采用创建一个跟地址空间相同大小的数组，为每个1 p 地址 分配一索引号，使索引号与数组元素形成一一对应。算法的空间复杂度为0 ( 2 ”) ( w 为地址的宽度) 。例如对源、目的i p ，源、目的端口和协议类型这5 个域进行分类 的话，所需地址空间为2 10 4 b i t 。虽然该分类算法仅需一次内存访问，但所需地址 空间不现实。 线性查找算法则采用把所有前缀而不是i p 地址线性存入数组。当执行查找 时，先把数据包的i p 地址逐个与数组中的前缀进行匹配，直到匹配完数组中所有 的前缀，匹配过程中的最长前缀就是我们所要的最终结果。算法的空间复杂度为 o ( n ) ，一次查找需0 ( n ) 内存访问，n 为分类器中规则的条数。尽管线性查找算法 所需的最少内存为0 ( n ) ，但o ( n ) 次的内存访问却是我们无法容忍的。 2 、并行包分类算法 包分类是对路由器中i p 地址查找问题的扩展，它不仅对一个域进行查找，也 可能针对多个域。因此，我们很自然地想到先并行地对每个域进行查找j 然后再 对各域的查找结果做“与”操作从而得到查找的最终结果。其算法思想如下。 s t e o l 把规则库中所有规则的每一个维分别映射到一坐标轴上，则每个坐标 轴上最多可得到2 n + 1 个不相交的区间。 例如：表2 1 是一个2 维分类器，现分别对它的两个域f i e l d l 和f i e l d 2 进行 映射。从域f i e l d l 我们可得到的映射区间有【0 0 0 0 ，0 1 0 0 ) ， 0 1 0 0 ，0 1 1 0 ) ， 0 1 1 0 ， 1 0 0 0 ) ， 1 0 0 0 ，1 0 0 1 ) ， 1 0 0 1 ，1 1 1 0 ) 和 1 1 1 0 ，1 1 1 1 】，域f i e l d 2 映射的区间 硕士学位论文 有 0 0 0 0 ，0 1 0 0 ) ，【0 1 0 0 ，0 1 1 1 ) ，f 0 1 1 1 ，1 0 0 0 ) ，【1 0 0 0 ，1 1 1 0 ) 和 1 1 1 0 ，1 1 1 1 】。 表2 1 简单的 二维分类器 f i e l d lf i e l d 2r u l e 【0 0 0 0 ，0 1 0 0 ) 0 0 0 0 ，0 1 0 0 ) r 1 【0 0 0 0 ，0 1 0 0 )【0 1 0 0 ，o l11 ) r 7 【0 0 0 0 ，0 10 0 ) 0 111 ，1 0 0 0 ) r 4 0 0 0 0 ，0 1 0 0 ) 【1 0 0 0 ，1 1 1o ) r 7 【0 0 0 0 ，0 1 0 0 )【1 1 1 0 ，1 1 1 1 】 r 3 【1 1 1 0 ，1 1 1 1 】【0 0 0 0 ，0 10 0 ) r 7 【1 1 1 0 ，1 1 1 l 】【0 1 0 0 ，0 1 1 1 ) r 7 【1 1 1 0 ，1 1 1 1 】【0 111 ，1 0 0 0 ) r 4 【1 1 1 0 ，1 1 1 1 】【1 0 0 0 ，111 0 ) r 7 【1 1 1 0 ，1 1 1 1 】【1 1 1 0 ，1 1 1 1 】 r 6 泌给这些区间的每个结果( e a c h p r o d u c t ) 分配一最佳匹配规则。 最差情况下，这一步将为每个d 维分类器产生n 4 个条目( e n t r y ) ，因此这种情 况下条目的数量是比较大的。c r o s s p r o d u c t i n g 算法中就是使用该数据结构。 s t e p 3 对每一维执行范围查找，把各维的查找结果相“与”，并把“与”操作 结果作为表的索引。 典型的并行包分类算法要有位并行算法【9 1 ，r f c 算法u o ，以及 c r o s s - p r o d u e t i n g 算法，算法的空间复杂度为o ( n 4 ) ，只适合小规模的分类器。 我们知道，在对存储空间要求不高的情况下，索引技术通常可以减少内存的 时间，而且它易于实现。因此，我们可以使用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 ) 【1 0 】算法是一种多维i p 分类快速查找算 法。其主要思想是将i p 分类问题看成一个将包头中的s 比特数据到t 比特的 e l a s s i d 的一个映射( t = l o g n 且t s ，n 是过滤规则的总数) 。如果预先计算出 包头中的这s 位共2 3 种不同情况中每种情况所对应的c l a s s l d 值，那么每一个包 只需要一次查表，但是这样会消耗极大的空间。r f c 的思想是通过多步或者说是 多个阶段( p h a s e ) 完成这个映射过程。每个阶段的结果将一个较大的集合映射成 一个较小的集合，称其为一次缩减( r e d u c t i o n ) 。 基于网络处理器的包分类引擎设计与实现 图2 2 中建立了一种4 阶段的缩减树，对i p 包查找的过程如下： 图2 2r f c 算法的4 阶段缩减树 ( 1 ) 在第一阶段( p h a s eo ) ，包头中的k 个域被分成若干个块( c h u n k s ) ，每一 块被用来作为并行查找的索引；( 2 ) 在后面的几个阶段，每次查找内存的索引值 都是由前几个阶段的查找的结果通过特定的方式合并而成的；( 3 ) 在最后一个阶 段，查找的结果得到一个确定的值，这个值就是该包对应的c l a s s i d 。 r f c 算法的性能受到两个参数的影响： 1 ) 选取的阶段( p h a s e ) 数目p ； 2 ) 在给定p 的情况下，“缩减”树的形状，也就是后面的阶段的索引值从前 面哪几个阶段的查找结果进行合并。 在p 和缩减树固定的情况下，随着过滤规则树n 的增加，消耗的内存量也增 加。对于同样的过滤规则数据库，一般而言p 越大消耗的空间越少，但是查找时 间增多。r f c 查找的时间复杂性是0 ( 1 ) ，但是消耗内存非常大，有时候甚至是 不切实际的。 3 、串行包分类算法 并行包分类算法采用对所有的规则域进行并行查找。串行包分类算法则先对 某一维进行查找，然后基于该维查找结果再执行下一维的查找，直到所有的维数 查找完了以后我们才能得到结果。典型的串行包分类算法有g r i do ft r i e s 1 4 】和 f a s t i n v e r t d s e g m e n t 树( f i s 树) 【2 2 1 。 g r i do f t r i e s 【1 4 】主要是针对二维情况下的i p 分类问题提出的有效解决方案。 如果将数据结构中的tr i e 树【2 3 1 从一维扩展到二维，就形成g r i do f t r i e s 树 g r i do f t r i e s 算