（计算机应用技术专业论文）ip包分类算法研究.pdf

分类号 密级公开 重庆邮电大学硕士学位论文 论文题目i p 包分类算法研究 英文题目r e s e a r c ho ni pp 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 硕士研究生金磊 指导教师巫垩垩丝丝 学科专业进关扭应田拉本 论文提交日期2 q q 2 生且 论文答辩日期2 q 皿生且2 且 论文评阅人 答辩委员会主席李祖枢教授重庆大学 2 0 0 7 年5 月3 0 日 重庆邮电大学硕士论文 摘要 网络新业务的不断出现，对网络传输速度提出了越来越高的要求。为适应这 些新变化，i s p ( i n t e r a c ts e r v i c ep r o v i d e r ) 一方面必须升级因特网骨干网络的速 度，一方面必须筹划新的有差别的网络服务，以满足不同用户的需要。由于光纤 技术和d w d m ( d e n s e w a v e l e n g t h - d i v i s i o nm u l t i p l e x i n g ) 技术的发展使得链路的 速率不再成为瓶颈，而路由器作为连接链路的节点，其性能会成为主要瓶颈。 高速路由器要求包分类装置具有线速度的吞吐能力，使得包分类的设计具有 很高的难度，成为路由器处理流程中最大的瓶颈之一，并且随着口网络应用领域 的不断扩展，要求包分类算法对规则维数、规则数量和每维的宽度可扩展能力强， 这也加剧了包分类算法设计的难度，成为扩宽1 1 ( i n t 豇 n c t p r o t o c 0 1 ) 网络应用的 障碍。 口包分类是路由器根据口包的多个域，从分类器数据库中匹配每个输入包， 确定包转发规则的技术。分类器为实现因特网新业务提供了统一的方式，包分类 是因特网提供一切有差别服务和其他新业务的基础，高速包分类问题是具有重要 现实意义和理论价值的研究课题。 路由器不仅要完成按照口包头目的地址转发口包的任务，同时也要满足能区 分不同的数据流的任务。一维p 包分类用于处理前一个任务，多维包分类用于 处理后一个任务。口包分类算法根据口包头地源地址、p 目的地址、源端口号、 目的端口和协议五个域进行分类，把不同的包归为不同的流，以便为不同的流提 供有差别的服务。 本文首先介绍了口包分类算法的应用背景，然后给出了m 包分类问题的详 尽数学描述。对现有的各种口包分类算法进行了详细的分析，并对各种算法的查 找性能和存储空间需求进行了分析比较。在此基础上，针对a q t ( a r e a - b a s e dq u a d t r e e ) 算法提出了改进算法。为了使原有a q t 算法能够应用于五维的口包分类， 使用无冲突哈希函数处理源端口号、目的端口和协议域，提出了一种新的口包分 类算法n c h a q t ( n o n - c o l l i s i o nh a s ha r e a - b a s e dq i i a dt r e e ) 。详细地给出了该算 法的基本思想、预处理过程、包匹配过程，并对规则优先权给出了明确的定义。 经理论分析与仿真实验证明，该算法是一个综合性能较高的算法。 关键词：m 包分类，无冲突哈希，规则库，匹配，复杂度 重庆邮电大学硕士论文 a b s t r a c t w i t ht h ed e v e l o p m e n to f n e wn e t w o r kt t a 伍c ，i ti su r g e n tt oa c c e l e r a t et h es p e e do f t h et r a n s m i s s i o no ft h en e t w o r k i no r d e rt oa d a p tt ot h en e ws i t u a t i o n , i n t e r n e t s e r v i c ep m “d e r so s p ) n e e d sn o to n l yt oi m p r o v et h es p e e do ft h eb a c k b o n en e t w o r k , b u ta l s op r o v i d e sn 绷d i f f e r e n t i a t e dn e t w o r ks e r v i c e st h a tc a l lm e e td e m a n d so f t h e d i f f e r e n tc l i e n t s t h el i n ks p e e dh a s n tb e e np e r f o r m a n c eb o t t l e n e c kb a u s eo f i m p r o v i n gi nf i b e ro p t i c sa n dd e n s ew a v e l e n g t h - d i v i s i o nm u l t i p l e x i n g ( d w d m ) ，b u t i n t e r n e tp r o t o c o l ( 口) t o u t e r sc a l lb em a i np e r f o r m a n c eb o t t l e n e c kb e c a u s eo fr e q u i r i n g m a n yc o m p l e xo p e r a t i o n ss u c ha sf a s tp a c k e tc l a s s i f i c a t i o n m 曲- s p e e dr o u t e rr e q u i r e st h ep a c k e tc l a s s i f i c a t i o ne q u i p m e n tt op 麒瑚sp a c k e t s i nw i r e - s p e e d t h u s ，i ti sv e r yh a r dt od e s i g n 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 sa n di th a s b e c o m eab i gb o t t l e n e c ko ft h ea c t i o n si nm u t e r s w i t ht h ei n c r e a s i n gd e v e l o p m e n to f t h en e t w o r ka p p l i c a t i o n ，i pp 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 sm u s th a v es t r o n gs c a l a b l e a b i l i t i e si nt h ea s p e c t so ft h en u m b e ro fd i m e n s i o n ，q u a n t i t ya n dw i d t ho fe a c h d i m e n s i o n t h u s ，i tm a k e sd e s i g no 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 mm o r ed i f f i c u l t i th a s b e c 咄t h eo b s t a b l eo f i pn e t w o r ke x t e n s i o n p a c k e tc l a s s i f i c a t i o ni sat e c h n i q u et om a t c he a c hi n c o m i n gp a c k e ta tam u t e r a g a i n s tad a t a b a s eo fc l a s s i f i e ra n ds p e c i f yf o r w a r d i n gr u l e sf o rt h ep a c k e t s t h e c l a s s i f i e r si u oap o w e r f u la n du n i f o r mw a yt oi m p l e m e n tn e wn e t w o r ks e r v i c e s t h e s t u d yo ni pp 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 sp r a c t i c a ls i g n i f i c a n c ea n dt h e o r yv a l u e r o u t e rm u s tn o to n l yf o r w a r dt h ei pp a c k e ta c c o r d i n gt ot h ed e s t i n a t i o ni pa d i 出e s s b u ta l s od i f f e r e n t i a t et h ed i f f e r e n td a t af l o w o n ed i m e n s i o n a li pp a c k e tc l a s s i f i c a t i o n a l g o r i t h m sa r eu s e dt os l o v et h ef o r m e rt a s ka n dm u l t i p l ed i m e n s i o n a li pp 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 m sa ”u s e dt os i e v et h et h el a t t e rt a s k g e n e r a l l ys p e a k i n g , i n o r d e rt op r o v i d ed i f f e r e n t $ e r v i c ef o rd i f f e r e n tf l o w , i pp 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 s c l a s s i f yt h e d i f f e 佗n tp a c k e t si n t od i f f e r e n tf l o wa c c o r d i n gt ot h es o u r c ei pa d d r e s s d e s t i n a t i o ni pa d d r e 豁，s o i l r c ep o r t ，d e s t i n a t i o np o r ta n dp r o t o c o lf i e l d i nt h i sp a p e r , f i r s t ，t h eb a c k g r o u n d o fi pp a c k e tc l a s s i f i c a t i o n a l g o r i t h m sa g e i n t r o d u c e d t h e n , p a c k e tc l a s s i f i c a t i o np r o b l e m sa r ed e s c r i b e di nm a t he x p r e s s i o n i p 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 sa n a l y z e di nd e t a i la n dc o m p a r e dt h es e a r c ht i m ea n d m e m o r yc o s ti nd i f f e r e n ta l g o r i t h m s i no r d e rt oe x t e n dt h eo r i g i n a la r e a - b a s e dq u a d t r e e ( a q t ) a l g o r i t h mi n t o f i v ed i m e s i o n a lp 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 , t h e 重庆邮电大学硕士论文摘要 n o n - c o l l i s i o nh a s hf u n c t i o ni su s e dt oc a 3 l p ew i t h 自d u g c ep o r t d e s t i n a t i o np o r ta n d p r o t o c o l f i e l d an o v e li pp a c k e tc l a s s i f i c a t i o n a l g o r i t h mn o n c o l l i s i o n h a s h a r e a - b a s e dq u a dt r e e ( n c h a q t ) i sp r o p o s e d t h eb a s i ci d e a s ，t h ep r o c e s so f p r c p r o c e s s i n ga n dp a c k e tm a t c h 黜a n a l y z e di n d e t a i l s a n d , t h ep r i o r i t yo fr u l si s c l e a r l yd c 丘n c d f r o mt h et h e o r e t i ca n a l y s i sa n ds i m u l a t i o ne x p e r i m e n t s i ti sag o o d m g o f i t h mw i t hh i g hc o m p r e h e n s i v ep e r f o r m a n c e k e yw o r d s ：i pp a c k e tc l a s s i f i c a t i o n , n o n - c o l l i s i o nh a s h , r u l ed a t a b a $ e ，m a t c h , c o m p l e x i t y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 入已经发表或撰写过的研究成果，也不包含为获得重废虹直太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：徐磊签字日期：咯妇弓j 日 学位论文版权使用授权书 本学位论文作者完全了解 重庆邮电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重废邮电太堂 可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：畚磊 签字日期：二物d 7 年乡月弓7 日 z?l莎 仙 ： 九刚 年 龟7叫叩 签 期 师 日 导 字签 重庆邮电大学硕士论文第一章绪论 1 1 研究背景 第一章绪论 随着计算机网络各种业务的不断发展，网络的传输速度也相应地越来越快。 t c p i p ( t r a n s p o r tc o n t r o lp r o t o c o l i n t e m e tp r o t o c 0 1 ) 协议已经成为整个网络的基 础性协议。其中，m 协议工作在网络层，主要负责根据包的地址来找到下一跳 地址，将包往相应的链路上转发；t c p 协议工作在传输层，主要建立稳定的连接， 支持端到端的可靠传输。但是，由于传统的i n t o r n o t 是基于不能提供任何服务质量 保证的尽力传送( b e s te f f o r t ) 模型，它只根据数据包的目的地址决定下一跳地址， 而且对于到来的数据包采取先到先服务的方式，并不区分数据包的优先级，其q o s ( q u a l i t y o f s e r v i c e ) 无法得到保证。为了满足q o s 要求，在路由器上必须运行效 率较高的口包分类算法，对不同的包先进行分类，然后对同一类的包产生相同的 动作【1 1 。 由于光纤技术和d w d m ( d e n s e w a v e l e n g t h - d i v i s i o nm u l t i p l e x i n g ) 技术的发 展，通讯链路传输速率目前可以完全满足日益增长的新的业务的需要，对从而使 高速网络在链路上的瓶颈已经消除。但在路由器方面，由于要适应新的应用，必 须要运行m 包分类算法。即当输入的口包到了路由器，都要根据输入包头中的目 的口地址、源疋地址、目的端口、源端口和协议这五个域，在路由器规则库里查 找相应的规则，然后按照规则对输入包做相应的动作1 2 1 。 因此，网络中路由器的性能已经成为制约网络传输速率的关键。在一维口包 分类方面，也是在路由查找上，要求路由器要具有高速的路由查找算法，能够快 速地对每个输入包执行最长前缀匹配( l o n g e s tp r e f i xm a t c h i n g ，l p m ) ，以发现其 下一跳( n e x th o p ) 地址。在多维口包分类方面，为了提供多种网络服务，路由 器需要将到达的包归类为不同的数据流，根据不同的数据流来决定相应的动作 【朋。路由器的这两方面功能都是以口包分类( i pp a c k e tc l a s s i f i c a t i o n ) 技术为基础 的。路由查找是通过查找口数据包包头中的目的地址来决定其下一跳地址，它是 一维坤包分类中最典型的形式，也是多维口包分类的基础。而通常的口包分类 是查找p 包头中的多个域，以决定其归属于哪个数据流，它属于多维的口包分类 【4 1 。 网络业务的不断增长要求提高路由器的转发速率，由于路由器承担了碑包分 重庆邮电大学硕士论文 第一章绪论 类任务，为了要达到高的转发速率，必要使用转发速率较快的口包分类算法。而 口包分类具有允许范围匹配、前缀匹配和多维等特性决定了口包分类算法的复杂 性。口包分类算法的设计不但要满足较高的速率，同时要求占用较少的内存资源， 而且当规则库更新时，更新代价要尽可能小【5 1 因此，研究新一代的高速口包分 类算法已成为刻不容缓的任务【6 j 。 1 2 论文的内容和结构 1 2 1 论文内容 本文对当前一维和二维以上m 包分类算法进行了分析、对比和研究，结合无 冲突哈希函数和a q t ( a r e a - b a s e dq u a dt r e e ) 算法提出了一种新的p 包分类算 法。论文的主要内容包括： ( 1 )对p 包分类问题进行了总体概述。 ( 2 )介绍了口包分类问题的研究状况，对一维m 包分类算法，即路由查 找算法和二维以上m 包分类算法进行了全面的综合分析比较。 ( 3 ) 基于a q t 算法，同时构造无冲突的哈希函数，提出了一种新的五维 p 分类算法n c h a q t ( n o n c o l f i s i o nh a s ha r e a - b a s e dq u a at r e e ) ，它在功能上增 强了原始的a q t 算法，使原始a q t 二维分类算法能适用于五维分类。最后通过 理论分析与仿真实验，证明了它是一个综合性能较高的m 包分类算法。 ( 4 ) 总结了n c s a q t 算法的特点和应用环境，并对今后的研究工作做了 进一步的展望。 1 2 2 论文的组织结构 第一章：绪论 介绍p 包分类算法的应用背景和论文研究的主要工作。 第二章：p 包分类问题概述 概述了口包分类的理论基础、衡量标准、性能要求、分类算法的设计原则和 思路。 第三章：m 包分类算法的研究现状口包分类 对当前一维和多维口包分类算法进行了比较和分析，总结了当前研究中的不 足。 2 重庆邮电大学硕士论文第一章绪论 第四章：基于a q t 算法的n c h a q t 分类算法 详细描述了提出的基于a q t 算法与无冲突哈希函数的p 包分类算法的基本 思想、预处理过程、包匹配过程，最后给出了算法的性能分析和仿真结果。 第五章：结论与研究展望 对论文提出算法的总结，以及对后续研究工作的展望。 重庆邮电大学硕士论文第二章口包分类问题概述 第二章i p 包分类问题概述 各种业务的不断发展，使路由器逐渐成为网络性能的瓶颈。这就更要寻求一 种高效的m 包分类算法，来缓解路由器的处理速度不能与链路的速度相匹配的矛 盾。在一维的包分类方面，即路由查找方面，理想的算法要能够快速地根据每 个包的目的口地址对每个输入包执行规则匹配，以发现其下一跳地址。在二维以 上的多维包分类方面，都要根据输入包头中的目的口地址、源口地址、目的 端口、源端口和协议这五个域查找规则库，找出代价最小的一条规则，对这五个 域所确定的数据流进行相应的动作。 2 ii p 包分类的数学模型 这一部分定义了一些口包分类中必要的术语，建立了口包分类的数学模型。 2 i ii p 包分类的相关术语 定义1 ：地址d 是一个长度为矽b i t s 的比特串( 一般为二值比特串，各比特取 0 和1 两个值，也可以为三值比特串，每个比特还可取值“”) 。【7 】 定义2 ：前缀p 是长度介于0 到矽问的一个比特串，l e n g t h 门，表示前缀p 的 以比特数为单位的长度。 定义3 ：如果d 开始的l e n g t h ( p ) 个比特与p 相同，就称前缀p 与地址d 匹配。 定义4 ：包头日是有k 个域的实体，包头的各个域分别表示成 日【l 】，h e 2 9 - 9 h k 】，其中每个域都是比特串。 定义5 ：一条过滤规则，具有k 个域。与过滤规则的一个域相关联的有一个 匹配方式，它可以是下面三种匹配方式中的任何一个：精确匹配( 既tr n a t c h ) ， 前缀匹配( p r e f i xm a t c h ) 或范围匹配( r a n g em a t c h ) 。 定义6 ：域砸，通过一个数值来指定，如果包头日的域h f q 与过滤规则f 的 域f f i l 满足月阿= ，阿，那么就称h f q 与印，精确匹配。 定义7 ：域f f i j 通过一个前缀来指定，如果包头日的域h ：i j 与过滤规则，用 前缀表示的域f q 匹配，那么就称h f i l 与f f i j 前缀匹配。 定义8 ：域即，通过一个范围指定，也即f i 】= v a l l 。v a l 2 ，如果包头日的域 月阿与过滤规则f 的域，阿满足v a l l s 日【f 】v a l 2 ，那么就称h i j 与，阿围匹配。 4 重庆邮电大学硕士论文第二章口包分类问题概述 定义9 ：称f 过滤规则与包头日匹配，当且仅当对目的每个域+ v b i 都与f 相 应的域，w 匹配。砸7 与f 阿的匹配方式由f f i 的形式指定，可为上述三种匹配方 式中的任何一种【引。 2 1 2i p 包分类问题的定义 定义1 0 ：具有条过滤规则的过滤规则库，给定一个包头日，在，k 中 可能有不止一条过滤规则与h 匹配。约定，与每条过滤规则，有一个相关联的代 价函数c o s t ，过滤规则f 的代价记为c o s t c f ) 。定义最佳过滤规则匹配为在凡。中 查找满足下列条件的过滤规则f b 。： 一_ 厂蛐是日的一个匹配过滤规则； 一一在，k 中不存在其它的过滤规则f ，使f 与日匹配且满足 c o s t 伊fc o s t f f 训 2 2i p 包分类的性能评价指标 ( 1 )时间复杂度低 时间复杂度有三种评价指标： 最坏情况：在最坏情况下，对一个数据包进行m 分类所需的时间。 平均情况：在随机情况下，对一个数据包进行口分类的平均时间。 统计情况：在符合某种预先指定的数据包或过滤规则分布下，对一个数据 包进行p 分类的平均时间。 ( 2 )空间复杂度低：在查找过程中，一个算法所需要占用的内存不仅仅指 容纳过滤规则数据库本身所需要的，还指算法为了保证高速度的查找建立的各种 数据结构所消耗的内存。 ( 3 )更新复杂度低 更新的方式有3 种： 完全更新：指数据结构的建立是完全按过滤规则库的所有内容进行重新建 立。 增量更新：在已建成的查找数据结构中，根据增加或删除的过滤规则进行 数据结构的增减。 重组更新：随着过滤规则的不断增加或删除，可能造成查找数据结构效率 降低，因此在适当时候需要对数据结构进行重组使其恢复原来的效率。 目前大多数解决方案都比较重视空间复杂度和时间复杂度，由于这两个因素 重庆邮电大学硕士论文第二章口包分类问题概述 互相制约，因此解决方案是在二者间进行折衷唧。 ( 4 )可扩展性好 可扩展性包括以下3 个方面的内容： 在分类器的规则个数上具有可扩展性，指分类器的规则个数n 可以很大， 而不是限定在固定的规则数目上。 在分类的维数上具有可扩展性，指可以包含任意多个分类的字段，而不是 限定在固定的某几个字段上。 在分类的层次上具有可扩展性，指分类可包含多层次的分类，理想的算法 应该是能够容许匹配任意层内的字段，包括数据链路层、网络层、传输层，在一 些特殊的情况下可能要包括应用层的内容。 ( 5 )最坏情况下的性能良好 一个分类算法的好坏，除了给出平均性能的分析外，还应该给出在最怀情况 下的性能分析。平均的性能分析有时不能完全真实反映分类的性能，最近的研究 表明7 5 的数据包要比典型的5 5 2 b 的t c p 数据包要小。而且近半的数据包是4 0 4 4 b 的长度，主要由t c p 确认和t c p 控制组成。由于分类算法在执行过程中不能 用缓冲来消减数据包的变化，即使数据包的大小都是4 4 b ，分类算法也必须以线速 处理数据包。这就意味着算法应能够提供最坏情况下数据包最小的执行时间【l0 1 。 对于m 包分类算法而言，一般期望时间复杂度、空间复杂度和更新复杂度越 小越好，并具有良好的可扩展性，不仅平均性能好，而且在最坏情况下的性能也 良好。但在许多情况下，p 包分类算法无法满足全部指标达到最优，而是要根据 算法的使用场合加以折裂“】。 2 3i p 包分类算法的工作原理 包分类技术是路由器根据输入口数据包包头的一个或多个域，在分类器 ( c l a s s i f i e r ) 数据库中进行匹配，以确定数据包转发规则，对不同的数据包施以不 同操作的技术【1 2 】。i p 包分类过程基本原理如图2 1 所示： 6 重庆邮电大学硕士论文第二章包分类问题概述 萼亟 分类器数据库 属性行动 敷据包 图2 1 口包分类基本原理图 分类器数据库( 也叫做策略数据库、流表或简单地叫做规则数据库，不同文 献有不同的称谓) 指定了数据包转发规则或对数据包欲进行的操作，它由n 条分 类规则( 或称过滤器、过滤规则) 组成，每条分类规则由属性和行为( a c t i o n ) 组 成，其中： ( 1 ) 属性由k 个分量组成，第i 个分量也称为属性的第i 个域，记为c 【i 】。如 果对于任意的i ，数据包p 的头部第i 个域都满足属性域c e i l ，那么就说该数据包 p 和一个特定规则匹配，从而可以确定这条规则相应的行为。 ( 2 ) 行为指定对该数据包欲进行的操作。根据因特网业务的不同，对数据包 所采取的操作也不同，例如，对于路由转发，行为是输出端口号或下一跳地址 ( n e x t h o p ) ：对于防火墙数据包过滤，行为是允许和拒绝等等。 一般来说，k 个域的口包分类问题也称为k 维p 包分类。口数据包包头的k 个域可以为网络层的头、传输层的头或应用层的头，分别对应0 s 删网络体系 结构的第3 层、第4 层、第7 层。因此，这种根据第3 层信息、第4 层信息或第7 层信息来进行口包分类也被称为第3 层交换、第4 层交换、第7 层交换【1 3 】。 通常的m 包分类是指根据网络层及网络层以上的各层信息进行数据包的转 发。路由器根据包头信息和给定的规则数据库将数据包分为若干数据流( f l o w ) ， 并对不同的数据流施以不同的操作级别i l ”。因此，一般情况下的口包分类是多维 的p 包分类，它属于第4 层交换。在本文中，如未加说明，p 包分类是指多维 的包分类，如使用口源地址、口目的地址、协议域、源端口号和目的端口号的 五维m 包分类。 路由查找的基本概念是第3 层交换，它是一维口包分类中最典型的形式【”l 。 路由查找只需要通过查找口数据包网络层目的地址来决定下一跳地址，根据网络 层的地址前缀信息对输入数据包进行转发。在路由查找问题中，路由转发表的表 7 重庆邮电大学硕士论文第二章m 包分类问题概述 项是一个组对 ：路由前缀是网络层的p 地址或地址前缀，它 相当于分类器数据库中的属性；下一跳对应输出的端口号或下一跳地址，它相当 于分类器数据库中的行为。因此，路由查找问题实际上是一类特殊的口包分类问 题，它是包分类问题在一维上的实现，即规则只是简单的一个前缀表项【l “。 对于p 包分类问题，一个简单的解决方案就是将其分解为若干子问题，然后 将各子问题的结果进行一定的相“与”操作，得出原问题的结果。因此很多口包 分类算法就是通过降维，把k 维包分类逐步分解为k 个一维包分类，将问题简单 化，最终实现多维的口包分类，如位并行包分类算法、g r i d - o f - t r i e s 算法等。因此 路由查找问题也是口包分类的基础【1 7 1 0 2 4 一维口包分类算法 一维坤包分类素算法也叫p 包路由查找算法，它是m 包分类算法的最简单 的形式，即只针对包头的目的口地址域查找路由表，与多维数据包分类相比， p 路由查找最显著的特点是它使用最长前缀匹配( l p m ) 进行查找【1 8 】。 2 4 1 最长前缀匹配 在i m e m e t 的发展初期，i p v 4 地址采用的是基于类的地址结构。整个地址 空间分为5 类：为单播地址设计的a 、b 、c 类；为组播设计的d 类；为今后使用 而保留的e 类地址，各个类之间由地址的前几个比特来区分【1 9 】。 基于类的地址结构降低了路由表查找的复杂程度。在基于类的地址结构体系 下，可以通过目的口地址前几个比特位的值来获得该地址所对应的类，从而知道 匹配地址前缀的长度，因此地址前缀查找比较简单：路由表中的所有前缀可以根 据3 类不同的前缀长度而分为3 个查找相对独立的前缀表，地址前缀的查找已经 转化为在相应前缀表中精确查找关键字的操作，此时查找操作完全可以使用例如 基于二分法或者基于h a s h 哈希表的传统的查找算法【2 0 】。 随着网络的不断发展，i p v 4 地址结构产生了两个问题：地址分配的不灵活， 导致地址空间的大量消耗以及路由表规模的不断增大。为此，i e t f 为i n t a n e t 提 出了另一种称为无类域问路由( c l a s s l e s si n t e r - d o m a i nr o u t i n g ，c i d r ) 的地址结 构。c d r 摒弃了传统基于类的地址分配方式，规定可以使用任意长度的网络地址 部分，因此产生了路由地址前缀的概念【2 ”。 c d r 的使用提高了地址空间的利用率，但它也带来了新的问题，路由器进行 路由查找时，必须找到最长匹配前缀路由，这大大增加了路由查找的复杂性。在 重庆邮电大学硕士论文第二章包分类问题概述 c i d r 地址结构下，地址前缀表中前缀表项的长度是任意的，类的概念不在存在， 所以往往不能从目的地址的前几个比特推断出该地址所对应地址的长度来，从而 地址查找操作不再能简单的转化为关键字的精确匹配查找。因此，在c d r 地址结 构下，地址前缀查找不仅需要与前缀的比特位进行匹配查找，而且还需要考虑地 址前缀的长度，这就最长前缀匹配( l p m ) 问题【2 ”。 m 路由查找时，必须进行最长前缀匹配：当目的地址匹配多个路由表项时， 优先级由路由表项的前缀长度决定，长度越长，优先级越高。表2 1 的例子说明了 最长前缀匹配的问题，当目的地址为l o 1 0 1 2 1 时，它与前缀1 0 8 和1 0 1 0 1 2 2 3 匹配，按最长前缀匹配原则，它的下一跳地址应该时n h 4 而不是n h i | 2 ”。 表2 i 最长前缀匹配例子 前缀 下一跳地址( n e x t h o p ) 1 0 ，8n h l 1 0 2 1 2 b ，1 7n i l 2 1 0 1 1 力珥 n i l 3 1 0 1 0 1 2 ，2 3n h 4 2 4 2 范围匹配转化为前缀匹配 口包分类算法可以分为精确匹配、前缀匹配和范围匹配【2 4 1 。当前大多数算法 都是针对前缀匹配而提出的，但当所给出的匹配规则库的规则是以范围形式给出 时，这个时候若还想利用现有的基于前缀匹配的算法，就必须先要进行范围到前 缀的转化。由已有的数学知识得知，任何一个范围匹配都可以转换成为前缀匹配。 对于在范围i l ，“j 之间有个点的范围匹配问题，可以转换成最多2 n 个前缀匹配， 每个前缀的长度最多为l o g u i z 5 】。 9 重庆邮电大学硕士论文第二章口包分类问题概述 表2 2 范围表示转换为掩码 【4 ，7 1 【3 , 8 】 【1 , 1 4 】 0 1 ” 0 0 1l ，o l ”，1 0 0 0 0 0 0 1 ，0 0 1 , o l ，1 0 ，1 1 0 , 1 1 1 0 表2 2 为将范围转换成前缀的结果( 假设最长前缀w = 4 ) 。 2 4 3 一维包分类算法分类 由上节所述，m 路由查找难点在于要实现最长前缀匹配【2 6 1 ，也就是在查找过 程中，不仅需要与地址前缀的比特值进行匹配查找【2 ”，而且还需要考虑地址前缀 的长度，因此各种路由查找算法都可以归结为这两个方面的匹配查找过程【2 引。 ( 1 ) 基于地址前缀值的路由查找算法 基于地址前缀值路由查找算法的特点是通过对整个地址前缀空间进行地址关 键字穷举来消除地址前缀长度对查找的影响。线性匹配查找算法是基于地址前缀 值查找中最简单直观的地址前缀查找方法。地址区域二分法也是基于地址前缀值 的查找算法，但是出于它采用了二分查找，所以在算法性能上有了很大的提高。 基于t c a m 的硬件实现方法从本质上来说也属于地址前缀值的查找算法。 ( 2 ) 基于地址前缀长度的路由查找算法 另一个查找方法是基于地址前缀长度的路由查找算法，这类算法的出发点就 是在前缀长度空间内进行查找，与基于地址前缀值查找算法类似，查找过程可以 使用线性遍历法，也可以使用二分遍历法。二进制t r i e 树查找算法就是基于地址 前缀长度的线性遍历法，因为对于查找的第i 步来说匹配的是长度为i 的地址前缀。 多分支t r i e 查找算法也是基于在地址前缀长度空间内的线性遍历法，但是由于它 采用大于l 的步宽，所遍历的地址长度数目变少了，查找性能得到了提高。前缀 长度二分查找算法由于可以在前缀空间进行二分查找，所以算法的复杂度来看它 的性能更好。 2 5 多维i p 包分类算法 越来越多的网络新应用要求路由器提供q o s 功能，即针对不同的数据流提供 i o 重庆邮电大学硕士论文第二章口包分类问题概述 有差别的服务。这就要求路由器在转发口包的时候，不仅需要查询口包头的目的 口地址，而且需要查询口包头的更多的域。二维以上口包分类算法通常是查找五 个域：目的p 地址、源口地址、目的端口、源端口和协议，找出相应的匹配规则 3 0 1 。 现有的数据包分类算法主要有四类：l 、基本数据结构算法，其中代表性的算 法有：线性查找、分层查找树、网格树1 6 垮。2 、基于计算几何算法，包括c r o s s - - p r o d u c t i n g 1 卅基于区间划分的a q t 算法【3 3 1 。3 、启发式算法，包括递归数据包分 类算法【3 4 】、智能分层查找树3 5 1 、元组空间查找p 6 3 7 1 ；4 、基于硬件实现算法，典 型算法是基于t c a m 的算法【”1 ( 1 ) 基本数据结构算法 最简单的基于线性结构的分类算法是顺序查找方法，它将所有的匹配规则按 优先级顺序存储在线性链表上，对输入的口数据包依次顺序查找，算法虽然非常 简单，但时间复杂度太高。其中，基于t r i e s 树结构算法是一种常用算法。如 c n i d - o f - t i r e s 树、层次t r i e s 树、多比特t r i e s 树。它们的主要特点是通过构造一级或 多级t r i e s 树，并用t r i e s 树特性来优化【3 卿。如g r i d - o f - t i r e s 树通过建立交换指针来 加速查找：而多比特t r i e s 树以增加空间为代价来加快查找。 ( 2 ) 基于几何空间 基于几何空间的数据包分类算法也很常见，如c r o s s p r o d u c t 、a q t 等算法。 它们的主要特点是针对规则的前缀分布，按照0 l 序列的排列不同，将规则分为不 同的等价类。 ( 3 ) 基于启发的算法 如t u p l es p a c es e a r c h 、h i c u t s 等。它们的主要特点是利用规则的某些特性来 构造查找数据结构，从而形成查找入口，加快查找速度。如t u p l es p a c es e a r c h 算 法利用规则的前缀长度形成元组空间，这些元组空间的不同元组的个数很有限， 因此按照不同元组来查找规则，可以获得较快的查找速度。h i c u t s 算法是按照某 些启发的规则来对各个域实施划分，每次划分都尽量使规则均匀地落入子节点中， 这样就可以使这个划分树的深度较小，从而加快了查找速度。 ( 4 ) 基于硬件的算法 具有最快的分类时间，但需要增加一个容量为d n w ( w 为每一维的长度) 的 t c a m 存储器，由于这种存储器价格高，耗电量大，不能直接支持范围匹配，因 而对规则数量、规则维数和每维宽度的可扩展性均较差，只能用于较小的数据包 分类问题。 重庆邮电大学硕士论文第三章口包分类问题的研究现状 第三章i p 包分类问题的研究现状 3 1 一维口包分类算法研究现状 一维包分类算法根据口包头的目的口地址进行包的分类，研究人员提出了多 种一维的分类算法，用以提高包转发速率帅1 。 3 i 1 基本二叉键树 这里的查找键树又称t i l e 树，用二进制键树结构来表示地址前缀是一个常用的 方法。键树采用一种基于树的数据结构，通过前缀中每一位比特的值来决定树的 分支。图3 1 就是用二进制键树结构( 树中每一个内部节点最多包含两个子节点) 来表示的地址前缀表【4 ”。 在键树中，处于第l 层的节点代表了一类地址前l 个比特均相同的地址空间， 并且这前l 个比特串就是由从根节点到这个节点路径上的l 个比特组成。例如， 图3 1 中处于第三层的节点c 就代表了所有前3 个比特为0 1 1 的地址簇，而且比特 串0 1 l 就是根节点到节点c 路径上的比特按照遍历顺序所构成的。图中带阴影的节 点表示该节点对应着一个地址前缀，因此这些节点中包含了与该地址前缀相关的 转发信息。阴影节点既可以是叶子节点( 如节点b ) ，也可以是中间节点( 如节点 a ) 。二进制键树查找过程非常简单，可直接根据目的地址比特位搜索键树。搜索 时，把到目前为止匹配上的最长前缀记录下来，直到搜索结束，此时记录的最长 前缀即为最长前缀匹配。查找过程算法的复杂度为0f 删，存储空间复杂度为d ( n w ) 。 重庆邮电大学硕士论文第三章m 包分类问题的研究现状 3 1 2 路径压缩键树 图3 1 二进制键树结构 二叉键树经常包含一系列没有分枝的节点，可以通过在每个节点中增加s k i p 计数来去掉没有分枝的节点，使用s k i p 计数的技术也称为路径压缩( p a t h c o m p r e s s i o n ) ，m o m n 使用路径压缩技术建立了数据库索引系统，他称路径压缩 为p a t r i c i a ( p r a c t i c a la l g o r i t h mt or e t r i e v ei n f o r m a t i o nc o d e d i na l p h a n u m e r i c ) ， p a t r i c i a 因此得名。 路径压缩的思想最初在被称为p a t r i c i a 的算法中提出但该算法不支持最长 前缀的查找。s i d o w c r 对该算法进行改进，使之能够适应最长前缀的查找，并且在 b s d ( b e r k e l e ys o t s a r cd i s t r i b u t i o n ) u n i x 中加以实现。 路径压缩算法的时间复杂性与二进制键树的时间复杂度相同，但一般来说它 更快些。当二进制键树中的前缀分布相对比较稀疏时，路径压缩算法能够获得较 好的压缩效果，但是随着地址前缀数量的增加，二进制键树的前缀分布变得相对 聚集时，此时用路径压缩算法就不能获得更好的效果。 3 1 3 级压缩键树 n i l s s o n 和k a r l s s o n 使用级压缩( l e v e lc o m p r e s s i o n ，l c ) 改进路径压缩键树。 只要键树节点下面t 级没有叶节点，就将该部分键树压缩为一个大小为2 的数组， 用t 位作为指向节点指针数组的索引。当t 值很大时插入和删除代价大。和 p a t r i c i a 一样，级压缩键树未改善最坏时间复杂度，但一般来说更快。