（信号与信息处理专业论文）ip路由查表与报文分类算法研究.pdf

摘要 摘要 互联网( i n t e r n e t ) 是当今最广泛使用的网络，而路由器是构架互连网的核心设备。 路由器运行路由协议维护网络的正常通讯，当前最广泛使用的路由协议是i p ( i n t e r n e t p r o t o c 0 1 ) 协议，数据帧封装在i p 报文中。路由器最基本的功能包括：寻径和转发。 寻径即判定到达目的地的最佳路径，依靠路由选择算法来实现，并将收集到的信息填 入路由表中。当报文到达时，路由器根据报文的目的1 p 地址在路由表中查找，判断接 下去该分组将发送到哪一个站点，并把分组直接送到相应的端口上，完成报文转发操 作。 网络的快速发展对路由器的性能提出更高的要求。首先，由于w d m 和d w d m 光纤传输技术飞速发展，在物理层上传输速度已经高达4 0 g b s 的速率。链路速率的提 高要求路由器必须支持更高的路由查表速度。因此，如何实现高速路由查表仍是一个 挑战性的任务；其次，网络支持业务类型的增加，要求路由器必须有能力支持q o s 、 网络入侵检测、传输测量与记帐、负载平衡、拥塞控制等一系列功能。这些功能的实 现都要求路由器支持报文分类技术，即能够基于报文头的某些协议字段( 也可以是报 文的内容) 对报文进行分类。因此报文分类将是下一代路由器中许多网络技术的基础。 报文分类速度的快慢、功能的强弱都将直接影响到这些网络技术的性能。 本文致力于路由查表算法和报文分类算法研究。在分析总结已有算法和所面临挑 战的基础上，提出了一些新的算法，并对它们的性能进行了深入的讨论。本文的主要 研究内容如下： 路由查表：报文转发是路由器需要完成的主要功能之一。路由器以报文的目的i p 地址作为索引，查找转发表，得到报文对应的下一跳输出端口，这个过程被称为i p 路由查表( 1 pr o u t i n gl o o k u p ) 。c i d r 技术的出现，使路由查表必须使用最长前缀匹 配算法，增加了其实现的复杂度。 本文介绍了基于最长前缀匹配的路由查表算法，以及算法性能衡量的标准。在此 基础上，总结了几种组织路由表的数据结构，以及基于t c a m 的路由查表解决方案的 实现结构、相关算法等一系列问题。最后，本文提出了两种新的路由查表算法： ( 1 ) 基于快速搜索树的路由查表算法。 该算法根据路由表中前缀的分布特点，将路由集合分割成几个子集，然后分别针 对每个子集建立搜索树来实现路由查表。借助哈希压缩索引表降低了搜索树的深度， 加快了搜索树的查找速度。而b l o o mf i l t e r s 的应用，使几乎平均一次搜索树的查找操 作就可以完成一次路由查表。该算法可以满足高速链路的处理速度要求，支持达1 0 6 数 量级的路由表项，适于硬件流水线方式实现，具有很高的实用价值； 摘要 ( 2 ) a d p c a m 算法 路由器中高速i p 查表引擎一般使用t c a m 实现。然而，由于功耗较大限制了其 应用的范围。非对称前缀分布算法( a d p c a m ) 是一个新颖的降低t c a m 功耗的解决 方案。该算法在保证t c a m 有较高利用率的前提下，有效的降低了功率消耗，并将其 限制在可预知的范围内。这种算法支持路由表的快速更新。仿真和应用证明了该算法 的可行性和实用性。 报文分类：随着因特网的发展，对于业务质量( q u a l i t yo fs e r v i c e ，q o s ) 的需求 不断提高，导致越来越多的网络设备逐渐或部分采用基于流的报文处理方法。 本文系统的阐述了报文分类的相关知识，总结了报文分类算法的发展和应用。对 几种具有代表性的算法进行了详细分析。同时，本文提出三种新的报文分类算法： ( 1 ) 规则分割一快速搜索树算法( f c f s t ) 。 该算法是一种新的多维报文分类算法。算法利用哈希压缩索引表，将分类规则集 合分割成多个子集，并针对每个子集建立快速搜索树，而这些规模相对小的本地搜索 树更利于实现快速建立、查找和优化。本文在搜索树建立、优化以及规则分割等问题 上也提出了独到的解决方法。该算法查找速度快，支持分类规则数据库大，可扩展性 好，适于硬件流水线方式实现，具有很高的实用价值； ( 2 ) 基于多域t r i e 的报文分类算法( m f t - t c a m ) 。 该算法试图通过建立一种新的数据结构来解决基于t c a m 的报文分类算法存在 的范围匹配问题。本文首先提出一种多域t i l e ( m f t ：m u l t i f i e l d t i l e ) 的数据结构， 它是按照规则中的多个域构建的层次结构。m f t - t c a m 算法利用m f t 结构在t c a m 中组织分类规则，并将大多数范围信息存放在r a m 中，极大地提高了t c a m 的利用 率。在查找时，最多需要两次t c a m 访问操作，可以保证分类速度满足高速链路的要 求。该算法具有很高的实用价值； ( 3 ) 基于d 1 e f t 算法的硬件哈希表。 本文提出一种基于d - l e f t 算法和片内c a m 的硬件哈希表解决方案，可以通过一 次查表操作获得结果，解决了一般哈希表存在的最坏访问时间的问题。利用片内c a m 使哈希表的加入失败概率降到可以忽略的程度，同时提高了存储器的利用率。在实现 方面，可以按照设计需要折衷考虑存储器利用率、加入失败概率、占用片内c a m 资 源多少以及硬件实现复杂度等因素，具有很好的灵活性和可扩展性。将之应用到基于 哈希表的硬件报文分类算法中，可以有效的提高其处理性能。 关键词：路由器，路由查表，报文分类，q o s ，t c a m 摘要 a b s tr a c t t h ei n t e r n e ti s c o m p r i s e d o fam e s ho fr o n t e r si n t e r c o n n e c t e d b y l i n k s c o m m u n i c a t i o na m o n gn o d e so nt h ei n t e r n e t ( r o u t e r sa n de n d - h o s t s ) t a k e sp l a c eu s i n gt h e i n t e r a c tp r o t o c o l ，c o m m o n l yk n o w na si p i pd a t a g r a m s ( p a c k e t s ) t r a v e lo v e rl i n k sf r o m o n er o u t e rt ot h en e x t0 1 3 , t h e i rw a yt o w a r d st h e i rf i n a ld e s t i n a t i o n e a c hr o u t e rp e r f o r m sa f o r w a r d i n gd e c i s i o no ni n c o m i n gp a c k e t st od e t e r m i n et h ep a c k e t sn e x t h o pr o u t e r t h e c a p a b i l i t yt of o r w a r dp a c k e t si sar e q u i r e m e n tf o re v e r yi pm u t e r w i t ht h er a p i dg r o w t ho fi n t e m e t ，r o u t e r sh a v ef a i l e dt ok e 印u p 州t i lt h i sp a c eb e c a u s e t h e ym u s tp e r f o r me x p e n s i v ep e r - p a c k e tp r o c e s s i n go p e r a t i o n s o w i n gt oa d v a n c e si n o p t i c a lt e c h n o l o g i e s ，s u c ha sw 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 ，t h ed a t ar a t e so fl i n k sh a v e i n c r e a s e dr a p i d l yo v e rt h ey e a r s b e s i d e si n c r e a s e dp a c k e ta r r i v a lr a t e sb e c a u s eo fh i g h e r s p e e dl i n k s ，t h ec o m p l e x i t yo ft h ef o r w a r d i n gl o o k u pm e c h a n i s ma n dt h el a r g es i z eo f f o r w a r d i n gt a b l e sh a v em a d er o u t i n gl o o k u p sab o t t l e n e c ki nt h er o n t e r st h a tf o r mt h ec o r e o f t h ei n t e r n e t a d d i t i o n a l l y ，a ni pr o u t e rm a ya l s oc h o o s et op e r f o r ms p e c i a lp r o c e s s i n go n i n c o m i n gp a c k e t s e x a m p l e so fs p e c i a lp r o c e s s i n gi n c l u d ef i l t e r i n gp a c k e t sf o rs e c u r i t y r e a s o n s ，d e l i v e r i n gp a c k e t sa c c o r d i n gt oap r e - a g r e e dd e l a yg u a r a n t e e ，t r e a t i n gh i g hp r i o r i t y p a c k e t sp r e f e r e n t i a l l y ，a n dm a i n t a i n i n gs t a t i s t i c so nt h en u m b e ro fp a c k e t ss e n tb yd i f f e r e n t n e t w o r k s s u c hs p e c i a lp r o c e s s i n gr e q u i r e sc l a s s i f y i n gi n c o m i n gp a c k e t si n t oo n eo fs e v e r a l f l o w s a l lp a c k e t so faf l o wo b e yap r e d e f i n e dr u l ea n da r ep r o c e s s e di nas i m i l a r1 t i a n n e r f o rt h i s ，r o u t e r sn e e dt oh a v et h ec a p a b i l i t yt od i s t i n g u i s ha n di s o l a t et r a f f i cb e l o n g i n gt o d i f f e r e n tf l o w s t h e a b i l i t yt oc l a s s i f ye a c hi n c o m i n gp a c k e tt od e t e r m i n et h e f l o wi t b e l o n g st oi sc a l l e dp a c k e tc l a s s i f i c a t i o n t h ew o r kp r e s e n t e di nt h i st h e s i sf o c u s e so nt h ea l g o r i t h m sf o rr o u t i n gl o o k u p sa n d p a c k e tc l a s s i f i c a t i o n t h ed e t a i l e di n t r o d u c t i o ni sa sf o l l o w s ： i pr o u t i n gl o o k u p s ：f o r w a r d i n gp a c k e t si so n eo ft h em a i nf u n c t i o n st h a tr o u t e r n e e da c c o m p l i s h t h ea r r i v i n gp a c k e ti sl o o k e du pi nt h et r a n s f e rt a b l ew i t hd e s t i n a t i o ni p a d d r e s ss e r v i n ga si n d e x t h e ni ti ss e n tt ot h ec o r r e s p o n d i n go u t p u tp o r t t h i sp r o c e d u r ei s c a l l e dr o u t i n gl o o k u p s ，t h en e e dt op e r f o r ml o n g e s tp r e f i xm a t c h i n gh a sm a d er o u t i n g l o o k u p sm o r ec o m p l i c a t e dn o wt h a nt h e yw e r eb e f o r et h ea d o p t i o no fc i d rw h e no n l yo n e e x a c tm a t c hs e a r c ho p e r a t i o nw a sr e q u i r e d f i r s t l y ，t h et h e s i sc o n c i s e l yi n t r o d u c e st h ed e v e l o p m e n ta n de v a l u a t i o ns t a n d a r do f 摘要 r o u t el o o k u p sa l g o r i t h m ，a n dt h ed a t as t r u c t u r eu s e dt oo r g a n i z et h er o u t i n gt a b l e ，a n ds oo n t h e r o u t i n gl o o k u ps c h e m e sb a s e dt c a ma r es u m m a r i z e di nd e t a i l a n df i n a l l y ，t w on e w a l g o r i t h m sa r ep r o p o s e d ： ( 1 ) ar o u t i n gl o o k u pa l g o r i t h mb a s e do nf a s ts e a r c ht r e e s t h ea l g o r i t h ms p l i t st h er o u t er u l e si n t os e v e r a ls u b s e t sa c c o r d i n gt ot h ep r e f i xl e n g t h d i s t r i b u t i o n sa n dc o n s t r u c t sf a s ts e a r c ht r e e sf o re a c hs u b s e t u s i n gt h eh a s hc o m p r e s s i o n i n d e xt a b l e sa n db l o o mf i l t e r st h es p e e do fl o o k u pi si m p r o v e dd r a m a t i c a l l y t h i ss c h e m e c a nb ee a s i l yi m p l e m e n t e di nh a r d w a r eu s i n gap i p e l i n ef a s h i o na n dt h er e s u l t so ft h e e x p e r i m e n t a la n da p p l i c a t i o ns h o wt h a ti ti sp r a c t i c a la n de f f i c i e n t ( 2 ) a d p c a ma l g o r i t h m t c a m sa r eb e c o m i n gv e r yp o p u l a rf o rd e s i g n i n gh i 曲- t h r o u g h p u tf o r w a r d i n ge n g i n e s o nr o u t e r sf o rt h ea d v a n t a g e so ff a s tl o o k u pa n de a s ym a n a g e m e n t h o w e v e r , am a j o r d r a w b a c ko ft c a m si st h e i rh i 曲p o w e rc o n s u m p t i o na n dh i g hd i s s i p a t i o nd u et ot h e i r i n h e r e n tp a r a l l e ls t r u c t u r e w ep r o p o s ea p o w e r e f f i c i e n tt c a m s a r c h i t e c t u r ef o ri p l o o k u p c a l l e da s y m m e t r yd i s t r i b u t eo fp r e f i x e si np a g e t c a m s ( a d p c a m ) ，w h i c ho f f e r s s i g n i f i c a n tp o w e rs a v i n g sw i t i lah i g hu t i l i z a t i o na n di ss u i t a b l ef o rt h ei n c r e m e n t a lu p d a t i n g t h a tt h em o d e mi pr o u t e r sn e e d t h ep r o p o s e da r c h i t e c t u r ei ss i m p l et oi m p l e m e n tu s i n g c o m m o d i t yt c a m s ，a n dc a np r o v i d et h ec o n f i r m a b l ew o r s t c a s ep o w e rc o n s u m p t i o n g u a r a n t e e t h es i m u l a t i o nr e s u l t so nr e a ld a t af r o mt h ei n t e m e ts h o w st h ep e r f o r m a n c e b e n e f i t sa c h i e v a b l eu s i n gt h ea p p r o a c h p a c k e tc l a s s i f i c a t i o n ：i no r d e rt op r o v i d ed i f f e r e n t i a t e ds e r v i c e s ，r o u t e r sr e q u i r e a d d i t i o n a lm e c h a n i s m s t h e s em e c h a n i s m s - - - a d m i s s i o nc o n t r o l ，c o n d i t i o n i n g ( m e t e r i n g ， m a r k i n g ，s h a p i n g , a n dp o l i c i n g ) ，r e s o u r c er e s e r v a t i o n ( o p t i o n a l ) ，q u e u em a n a g e m e n ta n d f a i rs c h e d u l i n g ( s u c ha sw e i g h t e df a i rq u e u e i n g ) 叫e q u i r e ，f i r s to fa l l ，t h ec a p a b i l i t yt o d i s t i n g u i s ha n di s o l a t et r a f f i cb e l o n g i n gt od i f f e r e n tu s e r sb a s e do ns e r v i c ea g r e e m e n t s n e g o t i a t e db e t w e e nt h ei s p a n di t sc u s t o m e r t h i sh a sl e dt od e m a n df o rp a c k e t c l a s s i f i c a t i o ni nr o t i t e r s t h et h e s i sp r o v i d e sas e r i e so fi s s u e sc o r r e s p o n d i n ga b o u tp a c k e tc l a s s i f i c a t i o n s y s t e m a t i c a l l y ，i n c l u d i n gt h ef o r m a ld e f i n i t i o n ，t h em e t r i c so fp e r f o r m a n c ee v a l u a t i o n ，t h e m o d e lo fa n a l y s i sa n dt e s t i n g ，a n ds oo n a n ds e v e r a lt y p i c a lp 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 es u m m a r i z e ds y s t e m a t i c a l l y a n df i n a l l y ，t h r e en e wa l g o r i t h m sa r ep r o p o s e d ： ( 1 ) r c - f s ta l g o r i t h m o u rr e s e a r c hp r e s e n t san e wc l a s s i f i c a t i o na l g o r i t h mc a l l e dr c - f s t ( r u l e s c u t t i n g s f a s ts e a r c ht r e e s ) w h i c hs p l i t st h es e to ff i l e rr o l e si n t os e v e r a ls u b s e t sb yt h e 摘要 h a s h - c o m p r e s s i o ni n d e xt a b l eb u i l tb a s e do nt h ef i r s t8 - b i tp r e f i xo fi pa n dc o n s t r u c t sf a s t s e a r c ht r e e sf o re a c hs u b s e t t h e s es e a r c ht r e e sw i t hs m a l l e r s i z e df i l t e r sc a l lb em o r e q u i c k l yc o n s t r u c t e d ，o p t i m i z e da n du p d a t e d ，s ot h er a t eo fs e a r c hi sc o r r e s p o n d i n g l y i m p r o v e d f u r t h e r m o r e ，s o m en o v e lm e t h o d sf o r t h eb u i l d i n go fs e a r c ht r e e sa n dt h e p a r t i t i o no ff i l t e r sa r ed e s c r i b e d r c - f s tc a np r o v i d ea no r d e ro fm a g n i t u d ei m p r o v e m e n t o v e re x i s t i n gc l a s s i f i c a t i o na l g o r i t h m sa n db ee a s i l yi m p l e m e n t e di nh a r d w a r ea tl i n es p e e d s u s i n gap i p e l i n ef a s h i o n ( 2 ) m f t t c a ma l g o r i t h m i ng e n e r a l ，h a r d w a r eb a s e ds o l u t i o n ，t c a m ，i sn e c e s s a r yt ok e e pu p 、i t l lg i g a b i tl i n e r a t ep r o c e s s i n g o n eo ft h em o s tc r i t i c a lr e s o u r c em a n a g e m e n ti s s u e su s i n gt c a mf o r p a c k e tc l a s s i f i c a t i o ni sh o w t oe f f e c t i v e l ys u p p o r tr a n g em a t c h i n g t h et r a d i t i o n a la p p r o a c h h a sb e e nd e e m e di n e f f i c i e n tb e c a u s er a n g e sh a v et ob eb r o k e ni n t op r e f i x e sb e f o r es t o r e di n t c a m ，r e s u l t i n gi nl a r g ee x p a n s i o n w ep r o p o s ean o v e ls c h e m em f t - t c a m ，w h i c h a r r a n g e sr u l e si nt c a mb a s e do nm u l t i f i e l dt r i e ( m f nd a t as t r u c t u r e ss c h e m ec a l l m o r ee f f i c i e n t l yi m p l e m e n tr a n g e sm a t c h i n gu s i n gt c a m 、i 也m g hs p e e da n dr e a s o n a b l e s t o r a g e ( 3 ) h a r d w a r eh a s ht a b l eb a s e do nd - l e f ta l g o r i t h m h a s ht a b l e ，、i t l li t sl o w e rc o s ta n db e a e rs c a l a b i l i t y ，i sw i d e l yu s e di nm a n yr o u t i n g a n dp 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 o u rr e s e a r c hp r e s e n t sa na p p r o a c hf o ro b t a i n i n g l l i 曲一p e r f o r m a n c eh a r d w a r eh a s ht a b l eb a s e do nd - l e f ta l g o f i t h ma n do n - c h i pc a m u s i n g d - l e f ta l g o r i t h m , t h es e a r c h i n gr e s u l to fh a s ht a b l ec a nb ea c h i e v e dv i aar a mb u s ta c c e s s b e n e f i t i n gf r o mf a s t e ro n - c h i pc a m ，t h ef a i l u r ep r o b a b i l i t yo fi n s e r to p e r a t i o nd e c r e a s et o u l t r al o wl e v e l ，a tt h es a m et i m e ，t h ea v a i l a b i l i t yr a t i oo fm e m o r yi si m p r o v e dd r a m a t i c a l l y t h er e s u l t so ft h ee x p e r i m e n t a la n d 印p l i c a t i o ns h o wt h a ti ti sp r a c t i c a la n de f f i c i e n t t h e p a c k e tc l a s s i f i c a t i o ni m p l e m e n t e du s i n gt h em e t h o di ss u i tt ot r a f f i cm e t e r i n g k e yw o r d s ：r o u t e r , r o u t i n gl o o k u p ，p a c k e tc l a s s i f i c a t i o n ，q o s ，t c a m 独创性( 或创新性) 声明 本人卢l 蚰所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所失，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 也含j 他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教阿机构的学位或址书而使用过的材料。与我一同工作的刷志列本研究所做的任 贞献均已证沦文中作了明确的浇 埘并表示了酣意。 l # 学位论文与资料若有刁j 实之 本人签钙：捌鼬耻一 处，本人承担一切相关责任。 i q 期： 主! ! 堇- 堂：主墨 关于论义使用授权的说明 学化沦文作者完全了解北京l | | | j i 乜人学有关保留和使用学位沦文的规定，扭： 究乍仡校攻读学位期问沦文：j ：作的知识产权单位属北京邮电大学。学校有权保 1 7 “ 向l 到家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 恻；学校可以公前i 学位论文的全 ； f f 或部分内密，可以允许采用影印、缩印或其它 复制于段保存、汀：编学位沦文。( 保密的学位论文在解密后遵守此规定) 俅拌j 论文注释：本学位论文属下保密在一年解密后适用本授权+ 岛。非保密论 丈注释：本学位论文不属于保密范旧适用本授权：件。 小人掺名：盔塑鳢 阿期： 皇! ! ：坐主卫一 导| j i | j 签名 季叶一 隅了矿幻吲卜 北京邮电大学博士研究生学位论文 第一章绪论 互联网( i n t e m e t ) 是当今最广泛使用的网络，而路由器是构架互连网的核心设备。 整个互联网由许多子网络通过路由器连接起来的网状结构，各子网络又由许多主机组 成。子网内部的主机通信，由链路协议直接进行；子网之间的主机通信，要通过路由 器来完成。路由器是多个子网的成员，通信起点主机发出数据帧被路由器接收后，路 由器确定下一跳输出端口，发给下一台路由器，这台路由器又转发给另外一台路由器， 用这样一跳接一跳的方式，直到通信终点的另一台主机收到这个数据帧。 路由器运行路由协议维护网络的正常通讯，最广泛使用的路由协议是i p ( i n t e r a c t p r o t o c 0 1 ) 协议，数据帧封装在i p 报文中。路由协议能够根据网络拓扑结构，为经过 路由器的每个数据帧寻找一条最佳传输路径。路由器通过路由协议交换网络的拓扑结 构信息，依照拓扑结构动态生成路由表。 路由动作包括两项基本内容：寻径和转发。寻径即判定到达目的地的最佳路径， 由路由选择算法来实现。由于涉及到不同的路由选择协议和路由选择算法，要相对复 杂一些。为了判定最佳路径，路由选择算法必须启动并维护包含路由信息的路由表， 其中路由信息依赖于所用的路由选择算法而不尽相同。路由选择算法将收集到的不同 信息填入路由表中，根据路由表可将目的网络与下一跳( n e x t - h o p ) 的关系告诉路由 器。路由器间互通信息进行路由更新，维护路由表使之正确反映网络的拓扑变化，并 由路由器根据量度来决定最佳路径。这就是路由选择协议( r o u t i n gp r o t o c 0 1 ) ，例如路 由信息协议( r i p ) 、开放式最短路径优先协议( o s p f ) 和边界网关协议( b g p ) 等。 转发即沿路由选择协议确定的最佳路径传送信息分组。当报文到达时，路由器根 据报文的目的i p 地址在路由表中查找，判断接下去该将分组发送到哪一个站点( 路由 器或主机) ，根据路由表查找匹配结果将分组发送到下一个站点，如果目的网络直接 与路由器相连，路由器就把分组直接送到相应的端口上。这就是路由转发协议( r o u t e d p r o t o c 0 1 ) 。路由转发协议和路由选择协议是相互配合又相互独立的概念，前者使用后 者维护的路由表，同时后者要利用前者提供的功能来发布路由协议数据分组。 链路速率的迅猛增长，对路由查表速率的要求越来越高。w d m 和d w d m 光纤传 输技术飞速发展，在物理层上传输速度已经高达4 0 g b s ( o c 7 6 8 ) 的速率，而4 0 g b s 传输接口将成为未来城域核心和骨干网中最重要的传输接口之一。为满足线速处理， 这样的链路要求在8 n s 的时间内完成一次查表( 最短报文按照4 0 字节考虑) 。如果路 由器支持多个这样的链路，要求的查表速率也会成倍增加。因此，如何实现高速路由 查表仍是一个很具挑战性的任务。另一方面，路由设备容量的增加也导致大的功率消 第1 页 北京邮电大学博士研究生学位论文 耗。同时，功耗增加必须使用更多的散热设备，这样就降低了接口板上接口的密度。 因此如何设计合理的路由查表算法减少功耗也是一个需要解决的问题。 寻径和转发是路由器必须具备的基本功能。但是随着网络所支持的业务的增加， 要求下一代路由器必须有能力支持q o s 、网络入侵检测、传输测量与记帐、负载平衡、 拥塞控制等一系列功能。因此必须采用一定的机制来实现这些功能。虽然实现这些功 能的技术可能不尽相同，但它们都有一个共同的要求，即路由器应能够基于报文头的 某些协议字段( 也可以是报文的内容) 对报文进行分类称为报文分类技术。因此 报文分类将是下一代路由器中许多网络技术的基础，它涉及到网络的控制、性能、安 全、管理等多方面的内容。报文分类速度的快慢、功能的强弱都将直接影响到这些网 络技术的性能。 相对于路由查表仅仅使用i p 报文的目的坪地址，报文分类要求使用多个协议字 段，如：源、目的i p 地址，协议类型，源、目的端口范围等，而且报文分类也要满足 线速处理。所以报文分类要比路由查表复杂的多，而且也成为路由器处理新的瓶颈。 随着网络的发展，一方面为满足未来高速网络的需求，要求报文分类的速度越来越快， 另一方面网络支持的业务的增加要求路由器根据更多的报文协议字段以及更负责、更 灵活的分类组合对报文进行分类( 这将导致分类速度更慢) 。这种矛盾使报文分类成 为当今网络技术研究的热点。 根据上面的讨论，本文的致力于分析与解决下一代路由器所面临的两个问题：路 由查表和报文分类。与之相对应，本文介绍了两种类型的算法：( 1 ) i p 路由查表算法； ( 2 ) 报文分类算法。 本章后续内容组织如下：第1 1 节将先介绍路由器以及路由查表算法。第1 2 节介 绍流识别路由器的结构以及报文分类算法。最后是本文的创新点和论文结构。 第2 页 北京邮电大学博士研究生学位论文 1 1 路由器与路由查表 本节首先介绍了路由器所包含的基本功能，回顾了路由器体系结构的演进过程， 接下来介绍了c i d r 与最长前缀匹配查表，在最后一小节中，分析了路由器在进一步 发展过程中将会遇到的一些主要问题以及对应的一些解决方法，并提出了本文的研究 方向。 1 1 1 路由器的基本功能 路由器是构架因特网的核心设备之一，从因特网出现之初到现在，路由器经历了 数十年的发展，系统容量不断增加，体系结构也发生了多次变化，但其基本功能并没 有发生太大的变化。路由器的基本组成模块框图如1 1 所示。 输出 图1 - 1 路由器功能模块图 下面我们依次介绍路由器中的各个基本功能模块。 路由查表1 1 路由器的主要任务是完成报文转发，即根据报头中的目的i p 地址，将到达输入端 口的i p 报文转发到正确的输出端口。为此，在路由器中通常需要运行路由协议软件， 通过路由协议软件，以及用户的手工配置，在路由器中生成一个路由转发表，该转发 表中包含不同目的i p 地址对应的下一跳输出端口信息。i p 路由查表即根据报文的目 的口地址，查找路由器中的转发表，得到报文的下一跳输出端口的过程，简称路由查 第3 页 北京邮电人学博士研究生学位论文 表。 随着因特网的发展，在1 9 9 3 年，基于c i d r ( 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 ) 【2 ，3 】 的地址分配和路由方案被采纳。c i d r 一方面有效抑制了转发表大小的指数增长趋势， 提高了i p 地址的利用率，但同时也增加了路由查表实现的复杂度。此时的转发表中包 含一系列的i p 前缀( i pp r e f i x ) ，每个前缀对应一定的前缀长度和下一跳输出端口，对 于一个目的i p 地址，它可能与多个前缀同时匹配，此时需要按照匹配的最长前缀对应 的输出端口进行报文转发，这样的查表过程称为最长前缀匹配( l o n g e s tp r e f i x m a t c h i n g ) 查表。 路由查表将是本文详细讨论的问题之一。 报文处理 报文处理即按照协议的要求，对报文的内容进行相应的修改。例如对于i p 协议， 需要修改的内容通常包括：报头中的r r l 域，如果需要对报文进行拆分，则需要修改 报头中的d f 、m f 、c h e c k s u m 、f r a g m e n to f f s 武域。对于m p l s ，可能的报文处理操 作包括标签( l a b e l ) 的替换，标签堆栈的压栈以及弹出等等。 交换 交换功能主要存在于包含多个输入输出端口，尤其是包含多块接口板的路由器 中。交换功能的主要任务是：根据路由查表得到的报文的下一跳输出端口，将报文传 送到相应的输出端口或者接口板。交换功能通常可以采用总线、交换芯片、交换背板、 或者专用的交换板实现。 _ 缓冲与队列调度 为了容纳交换阵输出端口报文的突发性，降低因此而产生的报文丢弃概率，通常 需要在交换阵输出端口之后设置一定容量的报文缓冲，报文缓冲通常包含一定的报文 丢弃策略。 队列调度功能主要用来保证不同优先级的报文能够按照对应的优先级进行转发， 以及同一优先级报文转发的公平性。 网络设备管理 网络设备管理完成路由器的管理功能，通常包括路由器的配置管理、故障管理、 性能管理、安全管理和计费管理5 个管理功能域。管理功能通常通过特定的管理接口 实施，如通过网络进行的s n m p ( s 如n p l en e t w o r km a n a g e m e n tp r o t o c 0 1 ) 网管接口， 通过控制台实现的c l i ( c o m m a n dl i n ei n t e r f a c e ) 管理接口等等，此外，由于客户端 i n t e m e t e x p l o r e 非常普及，因此，基于h t t p 协议的网络管理接口也为众多用户所青睐。 一