（计算机应用技术专业论文）ngi高性能路由器转发处理算法与实现.pdf

i 【! i ：论文n g i 高性能路由器转发处理算法与实现 摘要 本文研究n g i ( n e x tg e n e r a t i o ni n t e r n e t ) 高性能路由器的转发处理关键技术路 由查找技术和流转发交换技术。通过对已有路由查找算法的分析得出两点结论。结论 一是已有路由查找算法不能适应n g i 高性能路由器的线速率转发；二是适应n g i 高性 能路由器线速率转发的路由查找算法应基于分部搜索和t c a m 技术。两点结论成为本 文主要研究工作的基础。 综合基于前缀长度二分搜索的路由查找算法和基于n i e 的路由查找算法的优点， 提出了“基于t r i e 二分搜索的路由查找算法( b s t r i e ，b i n a r y s e a r c ho n t r i e ) ”。不同于 r a d i xt r i e 算法的逐一比特进行比较和对前缀长度进行二分搜索的路由查找，b s t r i e 采 用二分法将i p 目的地址与t r i e 进行匹配，并用部分i p 目的地址做索引避免了使用h a s h 函数。对b s t r i ei p v 4 实现方案和b s t r i ei p v 6 实现方案进行了讨论。其路由查找速度和 转发表表项更新速度可适应o c 一4 8 ( 25 g b p s ) 端1 2 1 的线速率转发。 提出了“基于前缀范围二分搜索的路由查找算法( b s p r ， b i n a r y s e a r c h o np r e f i x r a n g e ) ”并给出了两组实现方案。第一组方案采用了比较器并在各步t c a m 存储完整 的转发表。包括b s p ri p v 4 路由查找流水线，b s p ri p v 6 路由查找流水线，和b s p r i p v 4 i p v 6 双协议栈路由查找流水线。通过转发表的减半存储( h a l f - s t o r e d ) ，第二组方 案避免了比较器的使用并减少了t c a m 的容量需求。由此产生了h s b s p ri p v 4 路由 查找流水线，h s b s p r i p v 6 路由查找流水线，和h s b s p r i p v 4 i p v 6 双协议栈路由查找 流水线。 提出了“基于前缀范围四分搜索的路由查找算法( q s p r ，q u a t e r n a r y s e a r c h o i l p r e f i xr a n g e ) ”，实现了两组硬件路由查找流水线。将q s p r 与前缀扩展技术相结合， 实现了q s p e ( q u a t e r n a r y s e a r c h o np r e f i x e x p a n s i o n ) i p v 4 路由查找流水线，q s p ei p v 6 路由查找流水线，和b s p ei p v 4 i p v 6 双协议栈路由查找流水线。混合采用q s p r 和 b s p r 技术，构建了q b s p r ( q u a t e r n a r y b i n a r y s e a r c h o np r e f i xr a n g e ) i p v 4 路由查找 流水线，q b s p ri p v 6 路由查找流水线，和q b s p ri p v 4 l p v 6 双协议栈路由查找流水线。 与已有的对前缀长度进行二分搜索和采用单步t c a m 的路由查找算法不同，本文 提出的b s p r 路由查找算法和q s p r 路由查找算法对前缀范围分别进行二分搜索和四分 搜索，并采用多步t c a m 组建路由查找流水线。突出特点是转发表无需排序、表项更 新快、查找速率高且连续性好。每2 个时钟周期即可完成一次i p v 6 路由查找或一一次转 发表表项更新，每项表项更新只对流水线路由查找流程中断一次。满足i p v 4 、i p v 6 及 i p v 4 i p v 6 双协议栈核心路由器o c 。7 6 8 ( 4 0 g h p s ) 端口的线速率转发。 提n 了“虚分组”概念和“虚分组交换( v p s ， v i r t u a l p a c k e ts w i t c h i n g ) ”机制。通 摘监 博t 论文 过剥传统i p 分缎的改进，v p s 在支持零散分组的逐一分组转发的基础上，特别适应对 t c p 流和u d p 流( 如实时视频数据流和实时音频数据流) 的高速交换。 关键词：新一代i n t e r n e t ，i p v 6 路由查找，四分搜索，快速表项更新，虚分组交换 f o l k - 论文n g i 岛性能路由器转发处理算法与实现 a b s t r a c t t h e f o r w a r d i n gp r o c e s sk e yt e c h n o l o g i e s ，i pr o u t i n gl o o k u pa n df l o wf o r w a r d i n g s w i t c h i n g ， w h i c ha r eu s e di nn g i ( n e x tg e n e r a t i o n i n t e r n e t ) h i g h p e r f o r m a n c er o u t e r sa r es t u d i e di nt h i s p a p e r , t h e r e a r et w oc o n c l u s i o n se x t r a c t e df r o mt h e r e l a t i v e p r e v i o u sr o u t i n gl o o k u p a l g o r i t h m sb ya n a l y z i n g t h e i rp e r f o r m a n c e t h ef i r s to n ei st h a tn oe x i s t e n ta l g o r i t h m ss u i tn g i h i g h p e r f o r m a n c er o u t e r st of o r w a r di p v 6p a c k e t sa tw i r es p e e d t h es e c o n do n ei st h a tt h e n g i h i g h p e r f o r m a n c er o u t e r s r o u t i n gl o o k u p ss h o u l db em u l t i p a r t i t ea n dt e a m - b a s e d t h e t w oc o n c l u s i o n sa r et h eb a s i c p r i n c i p l e so f t h em a i nr e s e a c hw o r ki nt h i sp a p e r a l g o r i t h mb a s e do nb i n a r y - s e a r c ho nt r i e ( b s t r i e ) i n t e g r a t i n gt h ea d v a n t a g e so ft h e a l g o r i t h m sb a s e do np r e f i x l e n g t hb i n a r y - s e a r c ha n d t h a tb a s e do nt r i ei sr e s e a r c h e d d i f f e r e n t f r o mt h e b i t b y - b i tm a t c h i n ga l g o r i t h m sb a s do nr a d i xt r i e ，o rt h ea l g o r i t h m sb a s e do n p r e f i x l e n g t hb i n a r y - s e a r c h ，i t m a k e st h ei pd e s t i n a t i o na d d r e s sm a t c ht h et r i e u s i n g b i n a r y s e a r c hm e t h o d a n di tu s e sp a r t so ft h ed e s t i n a t i o ni pa d d r e s sa si n d e xt oa v o i dh a s h f u n c t i o n si t s i m p l e m e n t a t i o ns c h e m ef o ri p v 4a n df o ri p v 6i sd i s c u s s e d i t sr o u t i n gl o o k u p s p e e da n d t h ee n t r yu p d a t e s p e e do ff o r w a r d i n gt a b l e sa r es u i t a b l ef o ro c 4 8 ( 2 5 g b p s ) p o r t s a l g o r i t h m b a s e do n p r e f i x r a n g eb i n a r y s e a r c h ( b s p r ) a n d i t st w o g r o u p s o f i m p l e m e n t a t i o ns c h e m e sa r eg i v e n t h ef i r s tg r o u pc o n s i s t so fb s p r - b a s e dt c a mi p v 4 r o u t i n gl o o k u pp i p e l i n e ，b s p r b a s e dt c a m i p v 6r o u t i n gl o o k u pp i p e l i n e ，a n db s p r b a s e d 7 f c a mi p v 4 i p v 6d u a l s t a c k r o u t i n gl o o k u pp i p e l i n et h e yu s ec o m p a r a t o r sa n ds t o r eh o l e f o r w a r d i n gt a b l ei ne a c hs t e po ft c a m b ys t o r i n gh a l fo ft h ef o r w a r d i n gt a b l e ，c o m p a r a t o r s a r ea v o i d e da n dt c a mc o s ti sr e d u c e d h s b s p r - b a s e dt c a mi p v 4r o u t i n gl o o k u pp i p e l i n e ， h s b s p r b a s e dt c a mi p v 6r o u t i n gl o o k u pp i p e l i n e ，a n dh s b s p r b a s e dt c a mi p v 4 i p v 6 d u a l s t a c kr o u t i n gl o o k u p p i p e l i n ea r ep r o p o s e dt oc o m p o s e t h es e c o n dg r o u p a l g o r i t h m b a s e do np r e f i x - r a n g e q u a t e r n a r y s e a r c h i s p r o v i d e d v i ap r e f i x e x p a n s i o n ， q s p e b a s e dt c a mi p v 4r o u t i n gl o o k u pp i p e l i n e ，q s p e - b a s e dt c a m i p v 6r o u t i n gl o o k u p p i p e l i n e ，a n dq s p e b a s e dt c a m i p v 4 t p v 6d u a l s t a c kr o u t i n gl o o k u pp i p e l i n ea r ec r e a t e d w i t hb s p r f o l l o w i n gq s p r ，q b s p r - b a s e d t c a mi p v 4 r o u t i n gl o o k u pp i p e l i n e ， q b s p r b a s e dt c a m i p v 6r o u t i n gl o o k u pp i p e i i n e ，a n dq b s p r b a s e dt c a mi p v 4 i p v 6 1 t i a b s t r a cr 博十论文 d u a l s t a c kr o u t i n gl o o k u pp i p e l i n ea r ec o n s t r u c t e d d i f f e r e n tf r o mt h o s ea l g o r i t h m sb a s e do np r e f i x l e n g t ho rs i n g l es t a g et c a m ，t h et w o r o u t i n gl o o k u pa l g o r i t h m s ，b s p ra n dq s p r a r eb a s e do i lp r e f i x r a n g ea n di m p l e m e n t e db y m u l t i s t e pt c a mp i p e l i n i n g e n t r ys o r t i n gi sn o tn e e d e da n ym o r ei ns p i t eo f t c a m s u s i n g o n ei p v 6l o o k u po ro n ei p v 6f o r w a d i n gt a b l ee n t r yu p d a t i n gc a r lb ec o m p l e t e dw i t h i no n e 2 - c l o c k c y c l e t h el o o k u pp i p e l i n i n gi si n t e r r u p t e do n l yo n c ep e re n t r yu p d a t i n g t h e ya c h i e v e o c 一7 6 8 ( 4 0 g b p s ) i n t e r f a c e s w i r e s p e e df o r w a r d i n ga n ds a t i s f yi p v 4c o r er o u t e r s ，i p v 6c o r e r o u t e r sa n di p v 4 i p v 6d u a l s t a c kc o r er o u t e r s v i r t u a l - p a c k e tc o n c e p ta n dl d r t u a l - p a c k e ts w i t c h i n g ( v p s ) m e c h a n i s ma r ep r o p o s e d b y a d d i n ga d j a c e n ti n d i c a t o r st ot h et r a n d i t i o n a li pp a c k e t ，v p ss u p p o r t sn o to n l yt h es p o r a d i c p a c k e t sf o r w a r d i n gb u ta l s oh i g h s p e e ds w i t c h i n go fu d p o rt c p p a c k e t sf l o w s ，s u c ha st h e t r a n s m i s s i o no fr e a l t i m ea u d i oa n dv i d e o k e y w o r d s ：n e x tg e n e r a t i o ni n t e r n e t ，i p v 6r o u t i n gl o o k u p ，q u a t e r n a r y - s e a r c h ，f a s te n t r e y u p d a t e ，v i r t u a l p a c k e ts w i t c h i n g v 博l 论文 n g i 高性能路由器转发处理算法，实现 缩写词 a a s i c b b s t r i e b s p r c c i d r c p u c a m c a o 0 p t d d r a m f f p g a g g b p s h h s b s p r i i p v 6 i p v 4 i s p l l p m m m p p s m f m p l s n 英文全称 注释表 中文全称 a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t 专用集成电路 b i n a r y - s e a r c ho n t r i e b i n a r ys e a r c ho np r e f i x r a n g e 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 e n t r a lp r o c e s s i n gu n i t c o n t e n ta d d r e s s a b l em e m o r y c h a i n - a n c e s t o ro r d e r i n gc o n s t r a i n t o p t i m a la l g o r i t h m 基于t r i e 二分搜索 基于前缀范围二分搜索 无类域问路由 中央处理单元 内容地址关联存储器 同枝繁衍排序约束最优算法 d y n a m i cr a n d o m a c c e s sm e m o r y 动态随机存取存储器 f i e l d p r o g r a m m a b l eg a t ea r r a y s现场可编程门阵列 g i g a b i tp e rs e c o n d吉l l 特( 1 0 9 比特) 每秒 h a l f - s t o r e db i n a r ys e a r c ho n 基于前缀范围半存储二分搜索 p r e f i x r a n g e i n t e r n e tp r o t o c o lv e r s i o n6 i n t e m e tp r o t o c o lv e r s i o n4 i n t e m e ts e r v i c ep r o v i d e r 第6 版本因特网协议 第4 版本因特网协议 因特网服务供应商 l o n g e s tp r e f i xm a t c h最长前缀匹配 m i l l i o np a c k e t sp e rs e c o n d m a t c h f l a g m u l t i p r o t o c o ll a b e ls w i t c h i n g 百万分组每秒 匹配标志 多协议标签交换 沣释表博士论文 n g i n h p p p l 0 一o p t p c b q q o s q s p r q b s p r q s p e s s r a m t t 比特 t c a m v v p v p f v p d v s r x i v n e x tg e n e r a t i o ni n t e r n e t n e x t h o p p o i n t e r p r e f i x l e n g t ho r d e r i n gc o n s t r a i n t o p t i m a la l g o r i t h m p r i n t e dc i r c u i tb o a r d q u a l i t yo f s e r v i c e q u a t e r n a r ys e a r c h o n p r e f i x r a n g e q u a t e r n a r y - b i n a r y s e a r c h 0 1 3 p r e f i x r a n g e q u a t e r n a r ys e a r c h w i t h p r e f i x e x p a n s i o n 新一代因特网 下一跳指示 前缀长度排序约束最优算法 印刷电路板 服务质量 基于前缀范围四分搜索 基于前缀范围四一二分搜索 前缀扩展四分搜索 s t a t i cr a n d o ma c c e s sm e m o r y动态随机存取存储器 t e m b i t太( 1 0 佗，兆兆) 比特 t e r n a r yc o n t e n t a d d r e s s a b l em e m o r y三态内容地址关联存储器 v i r t u a lp a c k e t v i r t u a l p a c k e tf l o w v i r t u a l p a c k e td e n s i t y v i r t u a l p a c k e ts w i t c h i n g r o u t e r 虚分组 虚分组流 虚分组密度 虚分组交换路由器 博卜论文n g i 高性能路由器转发处理算法j 实现 1 绪论 1 1 新一代i n t e r n e t ( n g i ) 的发展 随着i n t e m e t 规模的急剧膨胀【】、信息量的加大以及i n t e r n e t 上新应用的不断出现， 2 0 多年前提出的i p v 4 网际互联版本在许多方面已不适应。首先是地址限制，其次是日 益复杂的应用业务如流式视频和音频业务等对网络性能提出新的需求，人们对i p 协议的 地址空间、性能以及安全性等方面提出了更高的要求，使i p v 4 的局限性越发显现出来， 迫切需要发展新一代i n t e r n e t ( n g i ，n e x tg e n e r a t i o ni n t e r n e t ) 。i p v 6 正是为满足这些新的 需求而提出来的。 i p v 6 是i p v 4 的换代技术，是n g i 的基础。采用i p v 6 技术可以解决i p v 4 的地址空 间不足、地址层次少、可聚合性差、不能有效支持实时宽带业务、网络可扩展性差、对 新业务支持弱和安全性能差等一系列问题。在全球i n t e r n e t 技术研发力量的共同努力下， i p v 6 协议体系和技术已趋成熟，i p v 6 作为i p v 4 唯一替代者的地位已经得到国际认可。据 估计，2 0 0 3 年i p v 6 网络已开始进入规模化实施阶段，之后i p v 4 和i p v 6 将在一段时间 保持共存，期间i p v 6 将逐步取代i p v 4 ，并最终完全过渡到i p v 6 。 i p 协议是i n t e m e t 的灵魂 4 5 1 ，目前使用的i p v 4i n t e r n e t 技术诞生在美国，i n t e m e t 基础设备( 如路由器、服务器等) 的标准、软件及硬件关键技术，基本上由美国掌握。 网络资源也是如此。我国在i p v 4 时代获得的i p 地址数只有9 0 0 万( 而美国斯坦福大学 是1 7 0 0 万，i b m 公司则更达到3 3 0 0 万) ，经过近十年来i n t e m e t 应用的高速发展，中国 面临着日益严重的i p 地址短缺问题，i p v 6 技术无疑为我国i n t e m e t 提供了历史性的发展 机遇。在i p v 6 技术已成为新一代i n t e m e t 技术标准的情况下，世界各国对i p v 6 技术的研 究卜分重视。1 9 9 2 年，美国政府主导进行了“新一代i n t e r n e t 计划”的研究；1 9 9 6 年，美 国国家科学基金会又设立了“新一代i n t e r n e t ( n g i ) ”研究计划，这些研究计划中均包括 对i p v 6 技术及应用的研究。美国多所大学和研究机构联合起来，共同构造了一个名为 “6 b o n e ”的i p v 6 试验网络。随后，英国、德国、法国、日本、加拿大等5 3 个国都纷纷斥 巨资投入到对i p v 6 技术的研究和应用开发。 由于历史原因，我们在i p v 4 的技术研究、标准制订、产品开发等诸多方面远远落后 于美国，但i p v 6 作为新兴技术为中国的i n t e r n e t 事业提供了一个缩小差距的良机。i p v 6 使我国可以和世界重新站在同一起跑线上，对n g i 技术的研究，将使中国在新一代国际 i n t e r n e t 的开发与应用中处于有利地位。由于路由器是保障i n t e r n e t 中众多子网互联的重 要组成单元，所以开发n g i 高性能路由器技术具有十分重要的学术意义和重大的应用价 值。 绪论博士论文 t 2 转发处理技术研究的重点 路由器工作杰网络层，是i n t e m e t 剐络互联的圭要设餐，负责连接甭同豹子嗣，其 主要功能是根据网终拓抒选择最佳路由，耙孰辘人链路接收到髂分组转发到桐应的输出 链路。接入网审的鼹由器可以把家庭用户或者小的企业用户接入到i n t e m e t 业务供应商 ( 1 s p , i n t e r a c ts e r v i c e p r o v i d e r ) ；边缘路由器位于昔干网蚋边缘，茳聚校园或者公到中土平 台计葬机的业务量；置于嬲中的核心路出嚣则不壹接与终端用户相连，露是通过长距离 链路连接i s p 和企、啦网。 现代路由器由输入输出线# 单元、转发处理单元、交换咧络单元及主控单元四大部 分组成1 6 4j 。其中的转发处理单元主要功能是，接收输人输地线卡盥元传柬的口报文并 提取出报头信息，然后进行路出查找、报头处理以及q o s ( q u a l i t yo fs e r v i c ) ：g t ：l i 文分类 处理等。最厉将报文送入交换单元进行变换。其中高性能路由鹰找技术和漉转发交换技 术是转发处理的关键技术。路由查找可善作一维报文分类问题查找算法对报文分类算 法”“j 的研究具有一定促进作用。路出查找包括单播路由查找、组播路由查找和任播路 由奁找( i p v 6 ) 。而单播路由查找算法及其实现技术足组播路由查找、任捅路由查找和高 速流转发的基础，也是转发处理技术研究的重点。 1 3i p v 6 路田查找面临的问题 高性能i p v 6 核心路由器和高速链路是构建新一代i n t e m e t 的关键。目前 o c - 1 9 2 ( 1 0 g b p s ) 链路已投入应用，o c 7 6 8 ( 4 0 0 b p s ) 也在行发与成熟之中。而端阳速率 与之捐适应的i p v 6 协议栈高速路由器的发展刚受到报文转发处理速度的制约。影响转发 处理速度的一个重要因素是路出转发表的奁表速度难以适应币断增氏的链路速度。 转发表查表是对每个到达的诤报文根据箕目的i p 地址确定其应转发的输出端口号 和下一目t 地址。为撬高i p v 4 地址空间的剥弼率，减缓潞由袭中袭项的增长速度，i n t e m e t 工作纽i e t f 在1 9 9 3 年提岛了“无娄域问路由”( c i d 兄c l a s s l e s sl i n e r - d o m a i nr o u t i n g ) # 技术，地址前缀长度可为不超过i p v 4 遗址宽度的任意长度。变长地址前缀箭采用使得i p 蝗址的层次性分配成为可能，提高了地址有效利用率，僵在路自转发表查表时就有可靛 找口多个匹配的表礤，因此需要在所有匹配韵表项中选择地址前缀长凄最大静表项洚为 照终的盎表结果，卵进行最长前缀艇配( l p m ，l o n g e s tp r e f i xm a t z h ) 。 网络规模的不辑增长和服务质量酋需求促使i _ 】a t e m e t 向鞋i p v 6 网络互联弱议为基础 的新一代! n l e r n e i 过渡。i p v 6 与i p v 4 榴毙，在避鼓格式上发生_ ，键大改变，墙垃长度癌 厦袭的3 2 位变脏了1 2 8 位，在地址分配 ：也进行了改进 2 5 2 ”。尽管i p v 6 冬地址缡掏每 i p v 4 相比有许多币闻之处，坦整个地址空闻还嫠屡次性链构+ 仍然存在类 | x 手i p v 4c i d r 地址结构下蚋路由台并，i p v 6 赂出奎找同样是l p m 同题，焉睦i p v 6 地址室震弱增搬使 博l 沦文n g i 高性能路由姑转发处理算法与实现 得最长前缀匹配问题变得更加突出。随着链路速度的提高和i p v 6 的应用，l p m 日益成为 实现i p v 6 高速路由查表以确保线速率转发的瓶颈。 近年来人们提出了许多针对i p v 4 的路由查找算、法【3 0 “1 ，但转发表更新速度低且不 适应i p v 6 转发。比如，即使采用搜索次数较少的对前缀长度的二分搜索算法，一次i p v 4 路由查找需要5 步搜索，一次i p v 6 路由查找需要多达7 步搜索，且因存在回溯问题难以硬 件实现。目前，既支持i p v 4 又支持i p v 6 的高速速路由查找技术大多采用基于三态地址 关联存储器( t c a m ，t e r n a r yc o n t e n ta d d r e s s a b l em e m o r y ) 的解决方案 4 2 - 4 8 】。其特征是 采用单t c a m 存储体存储前缀，将前缀对应的输出端口号和下一跳地址存储在静态随机 存取存储器( s r a m ，s t a t i cr a n d o ma c c e s sm e m o r y ) 中。查表时将目的i p 地址送入 t c a m ，t c a m 将匹配项的最低地址输出( 优先编码) 作为后续查表索引，据此从s r a m 中读出相应的输出端口号和下一跳地址，即为最长前缀匹配结果。查表以并行方式进行， 因而理想状况下查找速率较高。但表项更新会中断查表流程，特别是t c a m 仅简单地将 地址最低的匹配表项的存储地址作为结果( 索引) 输出，要保障最长前缀匹配，表项的 存储必须按前缀长度相对地址降序排列，因而一个表项插入有时需要数十个维序操作， 不仅影响了表项及时更新，也使查表连续性能大幅下降，进而带来路由器丢分组率和缓 存容量需求的增加。已有研究通过减少按序插入表项所需的表项移动次数来提高表项更 新速度“，虽对路由更新的平均效率有所提高，但预处理操作复杂，最差情况下更新开 销大。也有文献研究免排序的t c a m 结构【i ，但至今未能在大容量t c a m 上成功应用。 制约路由器性能的因素主要有三个：路由查找、分组交换和输出调度。随着研究的 不断发展，已经提出一些性能良好的分组交换和输出调度解决方案【4 。因此，研究路由 查找算法从而提高路由查找速度成为进一步提高路由器性能的关键。 1 _ 3 1i p v 4 的地址结构和基于类的路由查找 i p v 4 为目前i n t e r n e t 上广泛使用的协议，它的地址长度为3 2 比特，分为网络号( n e t i d ) 和主机号( h o s t i d ) 两个部分，用( n e t i d ，h o s t i d ) 表示。i p 协议最初提出的时候采用的 是基于类的地址结构，它把i p 地址分为5 类：a 、b 、c 类用于单播业务，d 类用于组 播业务，e 类保留给其它应用。地址所属的类别通过i p 地址的最高几位来区分。各类单 播地址的n e t i d 和h o s t i d 比特数都不同，因此不同地址类型的网络能容纳的主机数也不 相同，如表1 3 1 1 所示。 网络路径是用地址前缀表示的，在这种情况下，地址前缀就只有3 种，长度分别为8 ， 1 6 , d 2 4 比特，分别对应于到a 类网络、b 类网络和c 类网络的路径。路由器根据分组目的 地址的前3 比特就可以知道地址的类别，然后取出其前若干( 8 ，1 6 或2 4 ) 比特，到相应 的前缀集合中进行完全匹配查找就可以了。所以在引入c i d r 之前，只有3 种不同长度的 地址前缀而且可以很容易地确定一个地址属于哪类前缀，则在查找分组的下一中继点 绪论 博士论文 时不需要进行最长前缀匹配搜索 基于类的路由查找在 早期的i n t e r n e t 中应用情况 良好。但随着i n t e m e t 的发 展，这种地址分配方式存 在的问题逐渐暴露出来。 很多中小企业和组织都需 要几百到几千个i p 地址， 例如某个公司需要1 2 0 0 个 i p 地址，这时就需要为它 路由查找要简单得多。 襄1 3 1 1 基于类的地址划分 类高位n e t i dh o s t i d地址范围 1 78 3 1 ao 0 0 0 o - 1 2 72 5 5 2 5 52 5 5 比特比特 2 1 51 6 3 1 b1 01 2 8 0 0 0 - - - 1 9 1 2 5 5 2 5 5 2 5 5 比特比特 3 2 32 4 3 1 c1 1 0 1 9 2 0 0 0 - - 2 2 3 2 5 5 2 5 5 2 5 5 比特比特 d ( 组播) 1 1 1 02 2 4 0 0 0 - 2 3 9 2 5 5 2 5 5 2 5 5 e ( 保留) 1 1 1 i o2 4 00 0 0 2 5 5 2 5 52 5 52 5 5 分配5 个c 类网络，但5 个c 类网络总共有1 2 8 0 个i p 地址，剩余的8 0 个地址不能被分配给其 它公司，就只能被浪费了。更严重的情况是如果需要5 0 0 0 0 个i p 地址，最好是分配一个b 类网络，这时被浪费的地址就有1 5 5 3 6 之多。一般来说用户希望自己的i p 地址是相互邻近 的，而且这些网络在物理位置上也大多是邻近的，所以在路由表中应该只为这些网络设 立一个路由表项。但是在原来的地址分配方案中，寻址是按照既定大小的子网进行的， 必须为这个公司的网络在路由表中设置5 个表项。从以上的描述中可以看出原来的地址分 配方案存在以下两个问题： ( 1 ) i p 地址的浪费。随着i n t e r n e t 的不断增长，3 2 位的i p v 4 地址本来就显得比较紧张， 不能高效率地使用这些珍贵的资源，i p 地址就会很快用尽，以后的用户就不可能连接到 i n t e r n e t 上，这是网络发展所不能允许的。更为严重的是，实际分配情况表明用户对c 类 网络的需要量特别大，尽管c 类网络的总量也是最多的，但仍然不能满足实际需要；而a ， b 两类网络很少需要，特别是a 类网络，分配出的数量就更少。这样很可能造成如下的情 况：虽然仍然有很多地址没有分配( 这些地址属于a 类或b 类子网) ，但是已经不能满足 用户对i p 地址的需要了。如果不改变原有的地址分配方案，这种情况会更早地出现。 ( 2 ) 会造成路由表的严重膨胀。骨干路由器需要知道整个网络的完整路径信息，近 年来，越来越多的网络连接至u i n t e m e t 上，造成路由表的指数级膨胀。1 9 9 0 年1 2 月主干路 由器中有2 1 9 0 条路径，1 9 9 2 年1 2 月增加n 8 5 0 0 ，到1 9 9 5 年1 2 月路径数已经超过3 万条。不 幸的是，简单地增加路由器的存储器，扩大路由表容量是不能解决路由查找问题的。路 径越多，路由器的控制c p u ( 路由处理器) 计算路由表、应付网络拓扑结构变化就越为 困难。路由器通常通过缓存最近用到的路由表项来提高分组转发性能，路径增多，使得 缓存常用路径的作法变得意义不大，这就降低了路由器的转发性能。所以，如果允许路 由表中的条目无限制地增长，核心路由器最终必定不得不丢弃某些路径，使得i n t e r a c t 上 的某些网段不可达。 博【论文 n g i 商性能路由器转发处理臂：法_ 实现 1 3 2 无类域问路由( c i d r ) 及l p m 问题 为减缓骨干路由表的增长速度，提高i p 地址空间的利用率，i n t e r n e t 工作组i e t f 在 1 9 9 3 年提出了无类域间路由( c i d r ) 技术，在分配地址时网络号( n e t i d ) 不再限制为7 、1 4 或者2 1 比特，可以为任意长度。c i d r 的网络号用i p 前缀( p r e f i x ) 表示，前缀的有效长 度可以从0 到3 2 比特( 实际中i p v 4 最短的前缀长度为8 比特) 。i p 前缀的表示方法为 p r e f i x l e n g t h ，其中p r e f i x 为前缀或者网络号，l e n g t h 为前缀的长度，例如，2 0 2 1 9 6 6 4 0 2 4 为2 4 l p , 特网络前缀。采用c i d r 技术后，如果一个机构需要申请3 0 0 个i p 地址，可阻为 该机构分配2 3 比特的网络前缀，从而使i p 地址的分配更为有效。 采用t c i d r 以后，每收到一个i p 分组，路由器根据i p 分组的目的地址查找路由表， 将i p 分组的目的i p 地址与每个转发表表项的掩码相与，如果结果与该表项的网络地址相 等，则找到了一个匹配的表项。由于路由表中对网络地址进行了聚合，就有可能找到多 个匹配的表项。所以，需要在所有匹配的表项 中选择前缀长度最长的表项作为最终的查找结 果，这就是最长前缀匹配( l p m ) 问题。例如， 某路由器有表1 3 2 1 所示的三个表项，如果有 一个分组的目的地址为2 0 2 1 9 65 1 2 3 ，则该地 址与表项1 h 3 都匹配，由于表项3 为最长匹配， 因此分组被转发：至l j h 3 。 表1 3 2 1 路由转发表 表项编号前缀下一跳地址 12 0 2 1 9 6 0 0 2 2h 1 22 0 2 1 10 0 2 2h 2 32 0 2 1 9 6 5 1 0 2 4h 3 图1 3 2 1 给出了骨干网路由器a a d s 5 0 1 上路由表前缀长度分布情况。其分布有3 个特 点： i p v 4 路由前缀长度至少为8 ；i p v 4 路由前缀并不是按其长度平均分布，大部分 的前缀分布在前缀长度为1 6 2 4 比特之间，路由表前缀长度 为1 6 2 4 的前缀占总数的 9 89 ，仅前缀长度为2 4 的前缀 就占5 0 左右。i p v 4 前缀长度 为8 1 5 比特和2 5 3 2 比特的 前缀所占比例很小。 1 3 3i p v 6 的路由查找 图1 3 21a a d s 上转发表前缀长度分布情况( 2 0 0 2 3 1 0 ) i p v 6 与i p v 4 * h 比，在地址格式上发生了很大变化，地址长度由原来的3 2 比特变成了 1 2 8 比特，相应地，i p v 6 在整个地址分配上也进行了一定的改进。尽管i p v 6 的地址结构与 i p v 4 相比有很多不同之处，但是从根本上来说，整个地址空间仍然是层次性结构，仍然 采用类似于i p v 4c i d r 地址结构下的路由合并，因此新一代网络协议并没有改变路由查找 绪论 博+ 论文 l p m t 筝j 本质特点，而且其多达1 2 8l l 特的地址使i p v 6 的路由查找面临更大的困难。 1 4 路由查找算法的研究 1 4 1 路由查找算法的性能评价标准 ( 1 ) 路由查找速度 查找速度是决定路由查找算法性能及路由器转发处理能力的最主要因素。物理链路 速率的提高要求路由查找速度也相应提高。在给定链路速率下，要求的查找速度一般有 两种计算方式；种是按昭, , i m e m e t 最短分组长度和最坏情况下的查找速度来计算。在i p v 4 为基础的i n t e r n e t 的流量中，仅t c p 回应报文( 2 0 字节的i p 头+ 2 0 字节t c p 头，计4 0 字 节) 就占4 0 左右 5 1 5 4 1 ，因此对第一种情况的速度一般要求按分组长度4 0 字节计算，对 o c l 9 2 ( 1 0 g b p s ，g i g a b i tp e rs e c o n d ) 链路来说最坏情况下的查找速度需要达n 3 1 2 5 m p p s ( m i l l i o np a c k e t sp e rs e c o n d ) ；对i p v 6 路由查找则常以4 8