（计算机科学与技术专业论文）高速ip路由查找与报文分类算法研究.pdf

里堕型兰垫查奎兰竺壅竺堕鲎竺笙苎 摘要 自1 9 9 7 年以来，i n t e r n e t 的网络流量、带宽以及物理链路速率约每6 个月增长一倍， 这使得报文的到达速率激增。但由于路由器需要对每个报文进行费时的处理，因此路由器 性能的增长速度难以达到与之相当的水平。此外，i n t e r n e t 网络规模的高速增长要求i p 路由查找算法能够处理大容量的路由表。而未来i p v 6 的应用要求i p 路由查找算法能够以 良好的性能处理1 2 8 位的i p v 6 地址和对海量路由表进行查找。 另一方面，i n t e l e t 需要根据不同用户的不同需求以及对服务质量的不同期望，提供多 种区分服务。包括：防火墙访问控制、虚拟专用网、基于策略的路由、q o s 调度、网络入 侵检测、网络地址转换、拥塞控制、流量记账、资源预留、负载平衡，以及基于内容的转 发等。而上述服务中的大部分都以报文分类作为其基础。但是高速多维报文分类本身是一 个公认的难以解决的问题，而且报文速率的快速增长给报文分类算法带来了巨大的压力。 由于i p 路由查找算法和i p 报文分类算法处于网络中的关键位置，不仅提供了对互连 网络的基础支持，而且其对i m e m e t 的性能和功能有着重要的影响，所以需要高速的i p 路 由查找和报文分类算法以适应互联网的发展。因此本文对i p 路由查找和报文分类算法进行 了深入研究，并针对不同的应用背景和需求提出了四个高性能算法。 本文首先对现有的典型i p 路由查找和报文分类算法进行了综述和分类比较，根据它们 的空间几何意义提出了i p 路由查找与报文分类模型m d c m ，并进一步提出了一些重要的 结论、方法和原则以指导算法的设计。其中基于最大最小熵原理和对前缀h a s h 结果分布 相似性的实验，提出了选择1 p 路由查找所用h a s h 函数的最大熵判定法。 本文提出了高速硬件i p v 4 路由查找算法c a t 。该算法突破了现有算法以存储空间和路 由更新性能为代价换取查找性能的一般模式，充分运用了a m d a l l l 定律、m d c m 信息约束 以及c a m 和t c 脚的器件特性，查找速度快，所需存储空间小。算法使用1 0 n s 的c a m 和t c a m 时即可满足4 0 g b p s 链路的的线速转发要求。c a t 算法是一种高度并行化的硬件 算法，易于流水实现，支持增量更新。由于其具有良好的可扩展性和并行性，容易通过扩 展满足对更大容量的路由表和更高速度网络单元的线速转发要求。 软件实现的i p 高速路由查找具有广泛的应用背景，本文提出了一个高速动态软件i p 路由查找算法l p em h 。该算法基于有限前缀扩展和多h a s h 函数技术实现，具有良好的 时空性能，支持动态更新。而且l p em h 算法能够根据报文流的变化动态地调整算法的搜 索过程。实验结果表明该算法能够满足o c 一1 9 2 等高速接口的线速转发要求。 高速i p v 6 路由查找需要解决两个难点：1 2 8 位的i p v 6 地址需要更多的访存时间，而海 第1 页 国防科学技术大学研究生院学位论文 量路由表使得算法很难进行高性能搜索和更新。因此本文提出一个i p v 6 路由查找算法r r b t r e e ，该算法首先将前缀转化为范围表示以避免进行费时的最长前缀匹配，并很好地利 用了b 树和层次式的范围比较方法以减少对存储空间的需求。理论分析和模拟结果表明该 算法能够以很好的性能支持海量i p v 6 路由表的查找。 针对多维高速硬件分类环境，本文提出了基于多维子空间切割的高速i p 报文分类算法 m s d c 。该算法根据报文分类问题的空间本质，采用间接的方法对报文进行分类。该算法 所需的存储空间小，分类速度快，支持动态更新。使用1 0 n s 的存储器件能够满足4 0 g b p s 链路的线速报文分类要求。同时该算法具有强表述能力，规则的各个域可采用前缀、范围、 关系式等多种方法来表示。 为了有效地进行研究，本文还以美国斯坦福大学高性能网络组开发的报文查找与分类 模拟器p a l a c 为基础建立了一个完善的模拟环境。根据本文算法的模拟所提出的需求以 及i p 路由查找算法和报文分类算法的发展趋势，增加并完善其中的多个模块，从而能够有 效地对各种i p 路由查找和报文分类算法进行模拟和评估。 关键词：4 ，i p v 6 ，高速路由查找，高速多维报文分类，a m d a h l 定律 第页 国防科学技术大学研究生院学位论文 a b s t r a c t s m c e1 9 9 7 ，m e 廿a 伍c ，b a l l d w i d t l la n dl i n ks p e e do ft h ci n t e m e th a v ed o u b l e de v e r ys i x m o n m s ，w h j c hh a s1 e a dt 0 打e m e n d o u si n c r e a s eo fp a c k e ta 玎i v a lr a t e h o w e v e r ，r o u t e r sa r en o t a b l et ok e 印u p 丽t l lt h i sp a c en o wb e c a u s em e ym u s te x e c u t ee x p e n s i v cp e r _ p a c k e tp r o c e s s i n g o p e r a t i o n s b e s i d e s ，i pr o u t m gl o o k u pa l g o r i t t l l l l sm u s tb ea b l et o1 0 0 k u pl a r g er o u t et a b l e sa st 1 1 e i n t e m e ts c a l e sr 叩i d l y a n dd u et o 也ep o p u l a r i z a t i o no f i p v 6i nt h e 如t u r e ，i pr o u t i n gl o o k u p a l g 嘶m m ss h 伽1 dh a v ee v e nb e n e rp e r f b r i l l a l l c eo ns e a r c l l i n g 也eh u g ei p v 6r o u t et a b l e sa n d p m c e s s i n gt h e1 2 8 一b i ti p v 6a d d r e s s e s 0 n 恤eo t h c rh a n d ，t l l ei m e m e tn e e d st op r o v i d ev a r i o u sd i f r e r e n t i a t e ds e r v i c e st od i 仃b r e n t u s e r sb a s c do n 也e i rd i 丘 e r e n tr e q i l i r e m e m sa n de x p e c t 砒i o n so fq u a l i t y t h e s es e r v i c e si n c l u d e f i r e 、v a l l ，v i r t l l a lp r i v a t en e t w o r l ( ，p o l i c y - b a s e dr o 谢r 培，q o sc o n 协o l ，n e t 、v o r ki n t m s i o nd e t e c t i o n ， n e t w o r ka d d r c s s 订a n s l a d o n ， c o n g e s t i o nc o m m l ， 订缅c b i l l i i l g ，r e s o u r c er e s e r v a t i o n ， 1 0 a d b a l a n c 访g ，锄dc o n t e n t - b a s e df o r w 盯d i i l g ，c t c a n dm o s to ft h es e r v i c e sa r eb a s e do np a c k e t c l a s s i f i c a t i o n h o 、v e v p e r f b 姗【i n gc l a s s i f i c a t i o nq u i c l 【l y o nm u l t i p l ef i e l d si sh o 、v 1 1t ob e d i 伍c l l l t ，a i l dt 1 1 ef 瓠ti n c r e a s eo fp a c k c 吨a r r i v a lr a t ea l s op u tg r e a tp r e s s u r eo n 也ep a c k c t c l a s s m c a t i o na l g 耐m m s a s m ei pr o u 廿n gl o o k u pa n dp 砌【e tc l a s s i f i c a t i o na l g o r i m m sa r ea tt h ek e yp o s i t i o no ft l l e n e t w o r k s ，m e yn o to i l l yp r o v i d e 也eb a s i cs u p p o n sf o r t l l ei m c m e t ，b u ta l s oh a v e s o n g i i l n u e n c e so ni t sp e r f b r i n a n c ea n dm n c d o n a l i t i e s h e n c eh i g hs p e e di pm u t i n gl o o k u pa n dp a c k e t c l a s s i f i c a t i o na l g o r i m m sa r ei l e e d e dt om e e tt h et e n d e n c yo fm e1 m e m e t t h e r e f b r e ，m i st l l e s i s g o e sd e e pi m o 1 er e s e a r c ho fi pr o u 廿n gl o o k u pa n dp a c k e tc l a s s i f i c a _ d o na l g o r i m m s ，a n d p r o p o s e sf o u rh 蟾hs p e e da l g o r i t l l i i l sf o rd i 邱e r e n t 印p l i c a t i o n sa n dr e q u i r e m e n t s f i r s t l y ，a r e r t h es 山v e ya i l d 伽( o n o m yo ft 1 1 ec u r r e m 母p i c a la l g o r i t h r n s ，t h i s 也e s i sm n g s f o n a r da i li pr o m i l l g1 0 0 k u pa n dc l a s s m c a t i o nm o d e l ，m d c m ，b a s e do nt h e i rs p a t i a lg e o m e 时 e s s e n c e a n dt 1 1 e ns o m ei m p o r t a mc o n c l u s i o n s ，m e t l l o d sa 1 1 dp r i n c i p l e sa r eb r o u g h to u tt og u i d e t 1 1 ea l g o r i t h m sd e s i g n p a r t i c u l a r l y ，b a s e do nt h em a x i m a i m i n i m a le n 仃o p y 血e o r ya i l dm e e x p e r i m e n t sf o r 山es i m i l a r i 哆o fp r e f - e s h a s hd i s t r i b u t i o n ，血em a ) 【i m a l 咖p yc r i t e r i o n m e m o di sp u tf o n a r dt oc h o o s et h eh a s hf 血c d o l l sf b ri pm u t i n gl o o k u pa l g o i i t h m s 1 1 1 i sm e s i sa l s op r o p o s e sah i g hs p e e dh a r d w a r ei p v 4r o u t i n gl o o k u pa l g o r i t l l i nc a t t h i s a l g 撕b r e a k st 啪u 出血eg e n e r i cd e s i 9 1 1p a t t e m ，w i l i c hg e t sb e t t e rs e a r c hp e r f b n t l a l l c ea tt h e c o s to fs t o m g ea n du p d a t ep e r f o m l a n c e t h ec a ra l g o r i t l l ms e a r c h e sf 酞t e ra n dn e e d s1 e s s m e m o r yb yu t i l i 五n ga m 出1 1 1 1 sl a w ，t h ei n f o 肌a t i o nc o n s 拄a i n so ft h em d c mm o d e l ，a n dt h e f e a t u r e so ft 1 1 eg r o u pa s s o c i a t e dc a ma 1 1 dt c a m u s i n g10 n sc a ma n dt c a m ，i tc a ns a t i s 母 m en e e do fm el i n es p e e df o n a r d i n gf o rm e4 0 g b p sl i l l l ( a 1 s oc a ti sah i g h l yp 啪1 l e l i z e d h a r d w a r ea l g o r i t l l i n ，a n di se a s yt ob ep i p e l i n e d t h ec a ta l g o r i t h ms u p p o r t sf h s ti n c r e m e n t a l 第l i i 页 国防科学技术大学研究生院学位论文 u p d a t e b e c a u s eo f i t sg o o ds c a l a b i l i t ya 1 1 dp a m l l e l i s m ，i tc a nb ee a s i l ye x t e n d e dt om e e t 血el i l l e s p e e df o r w a r d i n gr e q u i r e m e mo fm el a 喀e rf o r w 盯幽唱t a b l e sa 1 1 dm ef a s t e rn e t 、o r k 砌t a sh i g hs p e e ds o f 咐a r ei pr o l n i n gl o o k u pc a nb eu s e di nb m a da p p l i c a t i o n s ，t l l i st l l e s i s p r o p o s e sad y n a m i ch i 曲s p e e ds o 矗w a r ei pm u t i i 塔1 0 0 k u pa l g o r m l ml p 删h ，w l l i c hi sb a s e d o n1 i 商t e ( 1p r e f i xe x p a n s i o na n dm u l t i p l oh a s h 如1 c t 主o n st e c q u e s t h el p e ha l g o r i t l l m g a i n sl l i 曲s p a t i o t e m p o m lp e r f o r 玎 1 a n c ea i l ds u p p o n si n c r e m e n t a lu p d a t e m o r ci 1 1 1 p o r t a n t ly ，i t c a l la d j u s ti t ss e a r c m n gs e q u e n c et oa d 印tt h ec h a n g eo ft h ep a c k e tn o w t h ee x p e r i m e n t i n d i c a t e s 廿1 a tm i sa l g o r i t l l mc a l ls a t i s 母t l l en e e do f t h e1 i n es p e e df o r w a r d i n gf o rh i g hs p e e dl 址， s u c ha so c 1 9 2 f a s ti p v 6r o u t i n g1 0 0 k u pn e e d st os o l v et 、od i 珩c u 】tp r o b l e m s ：m e1 2 8 - b “a d d r e s sn e e d s m o r em e m o r ) ra c c e s s e s ，a n dt h eh u g er o u t et a _ b l e sm a k e “d i 街c u l tt op e r f b 肌h i 曲s p e e d s e a r c l l i n ga n du p d a t i n g t h e r e f o r e ，出i st h e s i sp r o p o s e sa ni p v 6r 伽t i n gl o o k u pa l g o r i t l l mr r b t r e e i tc o i e r tt l l ep r e f i x e st or a n g e s 协a v o i de x p e n s i v el o n g e s tp r e f i x e sm a t c h ，a n dt h e n t a k e sg o o du s eo f 也ebt r e ea 1 1 d 也eh i e r a r c l l i c a lr a n g ec o m p a r i n gm e t h o dt or e d e u c em em e m o r y u s a g e n em e o r ya 1 1 由s i s 趾dt 1 1 es i m l l l a t i o nr e s u l t si n d i c a t et h a t 也er rb t r e ea l g o r i t mc a i l p e 血珊m g hp e r f b m a l l c er o u t i n gl o o k u pf o rh u g ei p v 6r o u t et a b l e s a i n l i n ga tt h eh i g hs p e c dm 瑚矗一d i m e n s i o nh 缸d w 越ec l a s s 证i c a t i o ne n v h o 衄e n t ，t h i st h e s i s p r o p o s e st h em s d ca l g o r i m mb a s e do n 廿1 et e c h j l i q u eo fm u l t i p l es u b d i m e n s i o nc u t t i n g a c c o r d i n gt ot 1 1 es p a t i a lg e o m e t 拶e s s e n c eo f 廿1 ec l a s s i f i c a t i o np f o b l e m ，t 1 1 i sa 1 9 0 r i t l l mc l a s s i f i e s t h ep a c k e t s 、v i t lt 1 1 ei n d i r e c tm e t b o d i tr e q u i r e ss m a l ls t o r a g e ，c a ns u p p o r tf 如tp a c k e t c l a s s i f i c a 石o na n di n c r e m e n t a lu p d a t e w i m1 0 n sm e i r l o r y ，i tc a na l s om e e tt h er e q u i r e m e mo f m e l i n es p e e dc l a s s m c a t i o nf o rt h e4 0 g b p sl i n k f u 曲e n n o r e ，i t1 1 a s1 1 i 曲n e x i b i l 时f o rs p e c m c a t i o n o fm l e s ，a n de a c hf i e l do f t h em l e sc a nb ee x p r e s s e da sp 蹦仅e s ，r a n g e s ，r e l a t i o n s h i pe x p r e s s i o n ， e 位 m o r e o v e r ，t om a k e 吐l er e s e a r c hc a r r i e do mm o r ee 仔b c t i v e l y ，m i st h e s i sm a l 【e sq u a n t n y i m p r o v e m e n to nt h ep a c k e tl o o k u pa 1 】dc l a s s m c a t i o ns i i u l a t o rp a j l a c ，w h i c hi sd e v e l o p e db y h i g hp e r f b m a n c en e t w o r k i n gg r o u po fs t a n f o r du 1 l i v e r s 咄u s a a c c o r d i n gt ot h es i m u l a t i n g d e m a n d sf r o mt 1 1 er e s e a r c h e s ，t h ed e v e l o p m e mt e n d e n c yo fm ei pr o m i n gl o o k u pa n dp a c k e t c l a s s i f i c a t i o na l g o r i m m s ，s o m en e wm o d u l e sa r ea p p e n d e da n ds o m eo l dm o d u l e sa r ei m p r o v e d t h u saw e l l - b u i l ts i m u l a t o ri sg o tt oe n a b l ee 疏c t i v es i n l u l a t i o na i l de v a l u a t i o no fv a r i o u sk i t l d s o f i pm u t i i l g1 0 0 k u pa n dp a c k c tc l a s s i 丘c a t i o na l g o r i t h m s k e y w o r d s ： v 4 ，6 ，瑚g hs p e e dr 0 u 恤gl o o k u p ，h i g hs p dm u l 6 _ d i m 姐s i o n p a c k e tc l a s s i 矗c a t j o n a m d a h l sl a w 第1 v 页 国防科学技术大学研究生院学位论文 图1 1 图1 2 图1 3 图l 4 图1 5 图1 6 图1 7 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 1 图2 1 2 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图4 1 图4 2 图4 - 3 图4 4 图5 1 图5 2 图5 3 图5 4 图6 1 图6 2 图6 3 图7 1 图7 2 图7 - 3 图目录 i n t e m e t 性能发展趋势2 i n t e m e t 网络带宽和流量增长趋势2 路由表容量变化趋势3 i p 路由系统示例及i p 路由更新与查找在其中所处位置示意图7 报文分类在网络单元中的一种典型处理过程1 0 i p 报文分类的多个分类字段实例1 l 最坏情况下的分类器结构一1 4 一个r a d i xt r i e 树l8 可变步距多分支t r i e 树18 2 4 - 8d i r 算法原理示意图2 0 t c a m 最长前缀匹配原理示意图2 0 s w i t c hp o i n t e r 添加方法一2 4 g r i d - o f i t r i e 数据结构以及查询实例2 4 规则在二维空间的分布图以及a q t 数据结构及查询实例2 5 f l s t r e e 数据结构查询实例2 6 h i c u t s 树结构实例2 7 h y p e 圮u t s 决策树实例2 8 r f c 中的搜索过程2 8 a b v 结构示例一3 1 i p 路由查找问题在一维空间中的示意图3 4 表2 2 中的伪规则在- 维空间中的图像3 5 二维空间中f a t 对象图例3 6 二维空间中的虚拟优先级平面示例4 2 i p 路由查找问题中的虚拟优先级平而4 2 不同长度前缀在不同路由表中所占比例的最小、平均和最大值一4 5 分类器大小的分布4 8 c a t 算法中一个c a m 单元的内容5 7 c a t 算法原理结构图5 8 c a t 算法引入t c a m 后的算法结构图5 9 c a t 算法的可扩展性和并行性6 3 l p em hb s 算法数据结构及其关系图一6 7 l p em hb s 算法各个h a s h 表单元数据结构图6 7 l p em he s 算法中h a s h 表a 和b l 各单元的内容7 4 l p em hh w 算法结构7 8 新插入的前缀与旧有前缀之间的关系8 0 表3 1 中各路由端点插入阶为5 的b 树后的宏观数据结构一蛇 r r b 1 k e 算法结点内部构建分段范围比较树内部结构和信息压缩原理示意8 4 m s d c 算法原理实例图( 1 ) 示例规则r 1 山在二维空间中的图像8 9 m s d c 算法原理实例图( 2 ) 示例规则r 1 r 4 被进行多维子空间切割后的图像9 0 m s d c 算法的直观解释9 1 第v 页 国防科学技术大学研究生院学位论文 图7 4m s d c 算法硬件原理图及实例图9 3 图7 5m s d c 算法与其它算法的最差情况分类时间实验结果曲线1 0 0 图7 6m s d c 算法与其它算法耗费空间实验结果曲线1 0 1 图a 1报文分类算法测试系统基本结构1 1 8 图a 。2i p 路由和报文分类算法评测系统的通用结构，1 1 8 图a 3p a l a c 模块结构示意图1 1 9 图a 4p a l a c 输入输出示意图1 2 0 图a 5p a l a c 个功能模块的结构关系1 2 0 图a 6p a l a c 获取规则库信息图示1 2 1 图a 7 规则库生成模块添加入p a l a c 12 3 图a 8p a l a c 的控带0 平台1 2 5 图a 9 改进后的p a l a c 控制平台1 2 5 图a 1 0p a l a c 原有算法模拟支持库模块接口层次1 2 6 图a 1 1 改进后的p a l a c 算法模拟支持库接口层次】2 6 图a 1 2 通用t c a m 框架结构1 2 7 第v i 贞 国防科学技术大学研究生院学位论文 表目录 表1 1图1 4 中路由器l 的路由表示例8 表2 1 几种典型i p 路由查找算法时空复杂度比较2 2 表2 - 2 示例规则集2 2 表2 3t u p l es p a c es e a r c h 算法主要数据结构示例3 0 表2 4 几种典型报文分类算法时空复杂度比较31 表3 1 一个伪路由表实例3 4 表3 2 实验中得到的不同长度前缀所占百分比的最大值一4 5 表3 3多个h a s h 函数的映射结果及其熵4 6 表3 4 前缀投影结果比例相似性4 8 表3 5 基本算法设计方法一51 表3 6 本文算法针对m d c m 模型的各个要素所应用的约束、特征、方法和原则5 5 表4 1c a t 算法h a s h 函数和其它参数的选取6 0 表4 2c a t 算法实验结果6 l 表4 3c a t 算法与其他硬件算法的比较6 2 表5 1 l p em hb s 算法各个h a s h 表不同级中的单元内容及其含义6 8 表5 2l p em hb s 算法更新性能测试数据一7 2 表5 3l p em hb s 算法搜索性能测试结果7 2 表5 4l p em he s 算法中平均代价c o s t 的系数求取7 5 表5 5l p em he s 算法更新性能测试数据7 6 表5 6l p em he s 算法搜索性能与b s 算法相比测试数据( b 6 4 k ) 7 7 表5 7l p em he s 算法与其他软件实现算法的定性比较7 7 表5 8l p em h 算法性能实测结果，数据来源同前7 7 表6 1 r rb t r e e 算法对真实小容量i p v 6 的性能( m = 3 2 ，三= 3 2 ，肛1 2 8 ) 8 6 表6 2r r b 1 r e e 算法对大容量i p 、r 6 路由表的性能( 聊= 3 2 ，三= 3 2 ，阡。1 2 8 ) 8 7 表7 1m s d c 算法的几个搜索过程实例9 4 表7 2m s d c 算法模拟测试结果：各种情况下候选规则集合的大小9 8 表7 3m s d c 算法模拟测试结果：各种情况下更新时所需要的访存次数9 9 表7 4m s d c 算法对大容量分类器的模拟测试结果( s 。= 2 ) 1o o 表7 5m s d c 算法与其它算法的分类时间和空间模拟比较1 0 0 表a 1 评价体系包含的度量指标1 1 7 表a - 2 部分指定规则分配比例1 2 3 表a 3 协议字段与端口字段的相关性1 2 3 表a 4p a l a c 原有输出统计信息1 2 4 表a 5 控制平台各个参数的含义1 2 5 表a 6 法模拟支持库模块的对外接口及其含义1 2 6 表a 7t c a m 类提供的功能接口1 2 8 表a 8 添加的功能接口函数1 2 8 第v i 页 独创性声明 本人声明所呈交的学位论文是裁本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：壶垫! ! 整直查热生堂塞佥娄差蓬珏塞 学位论文作者签名 攀 日期：2 。s 年9 月2 莎日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：矗望! 里坠直查塑量亟塞佥麦篡造盈窒 日期：，。a f 年夕月6 日 日期：么印产年7 月彰日 ， 国防科学技术大学研究生院学位论文 第一章绪论 我们正迈入一个以网络为主要技术支持的信息时代，i n t e m e t 正在越来越多地融 入到社会的各个方面，日益成为世界各国商业、科研、教育、文化交流、新闻传播、 意识形态等领域的重要工具和手段。而我们的生活方式也在互联网的影响下发生着 巨大的变化，互联网已成为人类生活中不可或缺的重要元素。 i n t e m e t 由相互连接在一起的路由器网络构成其主要组成部分。目前i n t e m e t 上的 结点间主要使用i p 协议进行通讯，而路由器的核心功能是在路由表中为从不同链路 接收到的i p 报文寻找最佳路由，并按照最佳路由所指定的路径将报文转发到下一台 路由器，如此不断重复该过程，直到报文最终到达其目的地。为i p 报文在路由器等 网络结点上的路由表中查找最佳路由的算法，称为i p 路由查找算法。 上述过程仅对接收到的报文进行简单转发而不做其它处理，因此被称为尽力传 输，这是i p 路由器应具备的最基本和最核心的能力【1 】，其目的是为了保证互联互通。 但实际上一台路由器也可以对某些特定的报文进行额外的处理，以提供高品质的服 务和完善的q o s 及安全保证。例如出于安全考虑对报文进行过滤，i s p ( i n t e m e t s e r v e i c ep r o v i d e r ，i n e r n e t 服务提供商) 统计用户流量进行记帐，i s p 根据与用户的协 议对某些报文提供延迟、带宽、流量等保证，以及其它多样化的区分服务等。这些 额外的处理要求路由器等网络结点根据预先定义的规则，按照报文头的一个或多个 字段将到达的报文区分为不同类别，并对相同类别的报文流执行由规则指定的相同 操作。这种根据规则对i p 报文进行分类的算法，称为i p 报文分类算法。 i p 路由查找算法和i p 报文分类算法由于其所处的位置十分关键，因而其性能对 i n t e r n e t 的整体性能和功能有着重要影响，而i n t e m e t 的高速发展也对i p 路由查找算 法和i p 报文分类算法提出了更高的要求。本文对i p 路由查找算法和i p 报文分类算 法进行了深入研究，提出了一系列新的算法以满足这些要求。 1 1 1 应用需求 1 1 立题背景 随着i n t e m e t 网络的高速发展，i n t e r n e t 的规模、带宽和链路速度等在以指数级增 长。如图1 1 和图1 2 【2 1 所示，kgc o f h n a n 等人在2 0 0 1 年撰文指出刚l ，i n t e n e t 中 也存在类似m o o r e 定律的指数增长情况，并将在此后的1 0 年间保持这一增长趋势。 第l 页 国防科学技术大学研究生院学位论文 童烹寰攀_ 薯_ _ _ ：_ _ _ 拳_ _ - _ 攀一= 烹_ _ _ 烹寰篡学紫一 墓辆稚 薹。 a o i l ：i i | i 娃g 粒e 孵6 蕺j _ 量 薹鞠丽丽蔬i 薪丽丽虿墨_ 一_ - _ _ 墨瑟两蒜丽丽丽嚣蕊西一 鍪f 每m 赫h 确fp e r f b r 嘲a n 棚( i i a r 。 _ 霉 m o i ! i ；l h 釜黼两囔晦5 、| 懒 篓黝m m 醐j c a t i i i s 孙i t s 棚o l 函b 耐o r e1 9 9 5 。”誊期m 硼甜螬囊i 。嚣 i 鼬埔翻刚c a 鳓泌静h i 棚o n 盯谳h l ；w d 喊i薹强2 m o n 秘麟雾i 誊i 囊 。 黧焖a x i m 狙m 獭两馘l m n k ；叠蜘吐砸酾峨誊蓦_i 臻胂o n t 麟纛鬻；霪羹一蠢： 曩黼i i l 嘲t 嵫l 麟口f 自i 汹1 9 6 虢1 9 8 2 一 ： u u 窖豢蜘o n t 麟i 霹誊鬻i 篓i 雾 誊旗骥嘲t 鼢拜黼鑫晒瓣酗1 9 黪- ，9 9 7 一薰j 篡“ t 9 稃同纳攀冀；j 纛誊蒸鬻黧熏曩 篓阳酶 ：f 瓣t 黼獭c 喜汹“1 9 9 z 一2 爱鹫m 彻t 噍蠹鎏羔簿i 薹。麓i 差i ；麟f 黪】皇tf 汹瞒谴i _ i i 碡h 锕蔽s 船嘲丽鹾1 9 9 7 2 2m 钢l 聪i 誊 蠹囊? 、i 一 薰l 谚i 秘曛! ! 熟i t e 孵唧s p 睁a 船曝锣7 囊 6 m 卿峨一。纂黧i ”? * 一* 囊一j 舞、 图1 1i n t e r n e t 性能发展趋势 图1 2i n t e r n e t 网络带宽和流量增长趋势 根据研究机构d a t a q u e s t 在2 0 0 0 年的调查和预测【”j ，到2 0 0 4 年，1 4 核心路由 器间的链路速度将达到4 0g b p s ( o c - 7 6 8 接口) ，2 l 的边缘路由器间链路速度将达 到1 0g b p s ( o c 一1 9 2 接口) 。而目前的实际应用情况虽然还没有达到这一预测，但是主流 的骨干网路由器，如c i s c o 的1 2 4 x x 系列、j u n i p e r 的m 1 6 0 、n e c 的n e cc x 5 2 2 0 等路由器，已支持o c 1 9 2 接口( 1 0 g b p s ) 。而为了在未来保持与i n t e r n e t 网络流量和 带宽的同步增长，骨干网路由器必将支持0 c 一7 6 8 或更高速率的接口。 链路速度的飞速增长使得单位时间内到达路由器的报文数目急剧增加，