（计算机科学与技术专业论文）网络处理器原型系统路由查找算法的研究.pdf

国防科技大学研究生院学位论文 摘要 本文的研究课题来源于8 6 3 计划项目“网络处理器芯片的设计与原型”，重点论述 了网络处理器中一项关键技术：路由查找算法及其相关技术。 根据摩尔定律，随着光纤通信的发展，存储器的访问速度跟不上光纤传输速度的增 长。而网络处理器中的路由查找，报文分类等功能都需要进行查表操作，需要访问存储 器，其性能都受到存储器访问时间的限制。因此，研究路由查找算法从而提高路由查找 速度成为进一步提高网络处理器性能的关键。 本文首先详细分析了现有的高速路由查找算法以及这些算法的优缺点，并讨论了各 种路由查找算法的的硬件实现的方案。 传统的路由查找算法一般分两步实现最长前缀匹配：首先找出和目的地址匹配的所 有前缀，然后从这些前缀中选出最长匹配的条目，因此，需要不断访存取出前缀值和目 的地址匹配。本文采用了一种与传统的路由查找算法不同的思路：在一系列前缀匹配中， 只有和最长前缀的那次匹配才是必要的，因此，路由查找只需要确定匹配目的地址前缀 的最长长度。 根据这一思路，本文提出了一种基于长度标记的位图映射b m t l f ( b i tm a pt d e b a s e do i ll e n g t hf l a g ) 路由查找算法。b m t l f 路由查找算设置了一个长度标记l f ( 1 e n g t h f l a g ) ，记录上一个结点中最长匹配前缀的长度，避免内部节点的前缀值匹配；采用简单 的标志位，表示在相应长度上存在一个前缀匹配，只要在路由搜索终止结点中检查一次 这些标志位，就可以确定最长匹配前缀。 本文用软件模拟了b m t l f 路由查找算法，对算法的性能进行了评测。从模拟的结 果来看，b m t l f 路由查找算法在存储空间利用率上有明显的优势，路由查找速度也有 一定程度的提高。和多比特t r i e 树相比，b m t l f 路由查找算法的存储复杂度从 d ( 2 k n t v k ) 降低到o ( v ) v k ) ，虽然采用压缩路由表的方法，但是没有增加更新操作复 杂度，同时避免了多比特t i l e 树存在的前缀更新扩散问题。 本文在网络处理器原型系统上设计了一种实现b m t l f 路由查找算法的硬件流水处 理引擎方案。本文针对在使用t c a m 时更新路由表需要进行复杂耗时的排序，以及 t c a m 功耗高的问题，提出了一种路由表免排序和降低t c a m 功耗的方案。本文针对 存储碎片影响路由查找速度的问题，提出了一种可编程指针的存储管理算法，减少了存 储碎片的产生。 主题词：路由查找，最长前缀匹配，位图映射，t c m 第i 页 国防科技大学研究生院学位论文 a b s t r a c t t h i st h e s i ss t u d i e sr o u t i n gl o o k u pa l g o r i t h m s ，o n eo ft h ek e yt e c h n o l o g i e so ft h e n e t w o r kp r o c e s s o r t h es t u d yi so n ep a r to ft h e8 6 3p r o j e c t s ”t h ed e s i g na n dp r o t o t y p eo fa n e t w o r kp r o c e s s o rc h i p ” w i t ht h ed e v e l o p m e n to fo p t i c a lf i b e rc o m m u n i c a t i o n s ，o n eo ft h em a i no b s t a c l e s r e s t r i c t i n gt h ep e r f o r m a n c eo f n e t w o r kp r o c e s s o r si st h a tt h eg r o w t hr a t eo f s p e e do f a c c e s s i n g m e m o r i e sc o u l dn o tk e e pp a c ew i t ht h a to fl i n ks p e e da c c o r d i n gm o o r e sl a w r o u t i n gl o o k u p a n dp a c k e tc l a s s i f i c a t i o nf u n c t i o n so fn e t w o r kp r o c e s s o r sl i e c da c c e s s i n gm e m o r y t h e i r p e r f o r m a n c e sa r es u b j e c tt or e s t r i c t i o n so fm e m o r i e s a c c e s st i m e t h e r e f o r e ，t h es t u d yo f r o u t i n gl o o k u pa l g o r i t h mt oi m p r o v es p e e do fr o u t i n gl o o k u pi st h ek e y t of u r t h e re n h a n c e p e r f o r m a n c eo f n e t w o r kp r o c e s s o r s t h et h e s i sp r e s e n t sad e t a i l e da n a l y s i so ft h ee x i s t i n gh i g h - s p e e dr o u t i n ga l g o r i t h m sa n d p o i n t so u tt h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e s ea l g o r i t h m sa n dd i s c u s s e st h eh a r d w r e i m p l e m e n t a t i o no f t h e s ea l g o r i t h m s t r a d i t i o n a lr o u t i n gl o o k u pa l g o r i t h m sg e n e r a l l yf i n d st h el o n g e s tm a t c h i n gp r e f l xi nt w o s t e p ：a tf i r s ti ti d e n t i f i e sa l lp r e f i x st h a tm a t c h i n gt h ei pa d d r e s sa n dt h e ns e l e c t st h el o n g e s t l e n g t hi nt h e s ep r e f i x s t h e r e f o r ei tn e e d st oa c c e s sm e m o r yt og e tp r e f i xv a l u ef o rm a t c h i n g t h ei pa d d r e s s t h i st h e s i sa d o p t sad i f f e r e n tt h i n k i n gf r o mt h et r a d i t i o n a lr o u t el o o k u p a l g o r i t h m a m o n g i na l l p r e f i x sm a t c h e d ，o n l y t h el o n g e s tp r e f i x m a t c h i n g i s n e c e s s a r y t h e r e f o r e ，w eo n l yn e e d s t od e t e r m i n et h el e n g t ho f l o n g e s t m a t c h i n gp r e f i x a c c o r d i n gt ot h et h o u g h t , t h i st h e s i sp r o p o s e sar o u t i n gl o o k u pa l g o r i t h mo fb i tm a pt r i e o nl e n g t hf l a g ( b m t l f ) t h eb m t l fr o u t i n gl o o k u pa l g o r i t h mb u l i d sa nl e n g t hf l a gt h a t r e c o r d i n gt h el e n g t ho ft h el o n g e s tm a t c h i n gp r e f i xl e n g t hi nn o d ef o ra v o i d i n gp r e f i xv a l u e m a t c h i n gi ni n t c m a ln o d e t h eb m t l fr o u t i n gl o o k u pa l g o r i t h mu s e ss o m es i m p l ef l a gb i t s w h i c hm e a n sap r e f i xm a t c h i n gi nac o r r e s p o n d i n gl e n g t ha n dc h e c kt h e s eb i t st od e t e r m i n e t h el o n g e s tm a t c h i n gp r e f i xo n l yi nr o u t i n gs e a r c ht e r m i n a t i n gn o d e s t h i st h e s i ss i m u l a t e sb m t l fr o u t i n ga l g o r i t h mi ns o r w a r ea n dt h ep e r f o r m a n c eo ft h e b m t l f r o u t i n ga l g o r i t h mi se v a l u a t e d a sf o rr e s u l t s ，b m t l fr o u t i n gl o o k u pa l g o r i t h mh a s o b v i o u sa d v a n t a g e si nt h em e m o r yu t i l i z a t i o na n di n c r e a s e ss p e e do fr o u t i n gl o o k u pt oa c e r t a i ne x t e n t c o m p a r i n gt om u l t i b i tt i l e ，t h eb m t l fr o u t el o o k u pa l g o r i t h mt od e c r e a s e s t h ec o m p l e x i t yo f s t o r a g e , a c c e s st i m ef r o m 0 ( 2 n m k ) t o o ( n w k ) a l t h o u g ht h eb m t l f r o u t el o o k u pa l g o r i t h mu s e st h er o u t i n gt a b l ec o m p r e s s i o nm e t h o d s ，b u ti th a sn oi n c r e a s i n gi n t h ec o m p l e x i t yo fr o u t i n gu p d a t eo p e r a t i o n a tt h es a m et i m e ，i ta v o i d st h ep r o l i f e r a t i o no f p r e f i x e su p d a t e t h i st h e s i sa l s oi m p l e m e n t e st h eb m t l fr o u t i n gl o o k u pa l g o r i t h mi nt h ep r o t o t y p e n e t w o r kp r o c e s s o r a sf o rt h ep r o b l e m so fr e a r r a n g i n gd u r i n gr o u t i n gt a b l eu p d a t i n ga n dh i g h 第i i 页 国防科技大学研究生院学位论文 p o w e rc o n s u m i n gw h e nu s i n gt c a m s ，t h i st h e s i sp r e s e n t sa l li m p l e m e n t a t i o ns c h e m eo f o r d e r i n g - f r e ea n dl o w - p o w e rt c a m an e wm e m o r ym a n a g e m e n ta l g o r i t h mw h i c hi sv e r y s i m p l et oo p e r a t eb yu s i n gp r o g r a m m a b l ep o i n t e ri sp u tf o r w a r d 。t h ea l g o r i t h mc a l lc a n e f f e c t i v e l yr e d u c et h es t o r a g ed e b r i s k e yw o r d s ：r o u t i n gl o o k u p ，l o n g e s tp r e f i xm a t c h i n g , b i tm a p ，t c a m 第i i i 页 国防科技大学研究生院学位论文 表目录 表1 1路由表示例3 表1 2各种线路速率下的查找速度5 表2 1t b l 2 4 表项结构。1 4 表2 2各种路由查找数据结构的性能比较1 7 表3 1实验所用路由表3 l 表3 2不同步长下的实验数据3 2 表3 3不同步长和不同比特初始阵列搭配下的结点数量3 3 表3 4不同路由表下的结点数量3 4 表3 5b m r l f 算法平均路由查找和插入时间3 5 表4 1实验平台内部主要模块4 l 第1 i i 页 国防科技大学研究生院学位论文 图目录 图1 1 图1 2 图1 3 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 有类地址结构2 m a b 、e s t 路由表前缀长度分布情况3 1 9 9 5 2 0 0 5 年骨干网路由表大小增长曲线6 二进制t d e 树8 路径压缩t r i e 树9 层压缩t i l e 树1 0 多比特t i l e 树1 0 地址区间二分查找树l l 基于前缀长度的路由查找1 2 基于d r a m 的结构1 4 基于t c a m 的结构1 5 t c a m 表项更新一1 6 b f 滤波器1 9 l p m b f 算法。2 0 位矢量算法2 l b m t l f 算法原理图2 2 b m 曩算法搜索示意图2 3 免排序t ( 、a m 的设计2 7 索引映射3 1 不同步长下的结点数量3 2 不同步长下的存储空间3 3 不同步长和不同比特初始阵列搭配下的结点数量3 4 网络处理器软硬件结构3 7 网络处理器原型简图3 8 扩展指令的实现3 9 协处理器的实现3 9 路由查找实验平台4 0 t n 结点数据结构4 3 路由查找协处理器4 3 结点指针n p 的计算逻辑4 4 最长匹配前缀的计算逻辑4 5 路由查找协处理器的任务调度4 6 第1 v 页 国防科技大学研究生院学位论文 图4 1 1 哈希函数c r c 4 分割4 7 图4 1 2 低功耗t c a m 的设计 图4 1 3 存储管理算法示例。 4 8 4 9 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题日：圈鳖缝垄墨基型丞统整由查垫篡洼鳇盈盔 学位论文作者签名：i 盏缢壹 日期：聊番年j 1 月l j ，日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书) 学位论文题目：匿垒矬垄墨厦型苤统整白查垫篡洼敛盈盔 学位论文作者签名：经盔羞日期：弘“年，、p l t r 日 作者指导教师签名：窒童圣日期：砷。年f 1 月f s 日 国防科技大学研究生院学位论文 第一章绪论 1 i 网络处理器的发展 网络处理器的出现和路由器的发展是密不可分的。路由器在8 0 年代问世之初，只有 一个通用微处理器，它既负责完成报文转发的实时业务，也负责路由计算、路由表建立和 修改维护、网络管理等系统功能，并且这些功能全部由软件来实现。但是随着i n t e r n e t 规 模的不断扩大，由于通用微处理器的处理能力和软件结构的限制，这种传统的路由器已经 发展到了极限，也不能保证实时业务传送中的服务质量。 为了解决早期路由器的速度问题，人们对其结构进行了改变。路由计算、管理控制等 非实时业务和报文转发等实时业务被分开，前者由通用微处理器完成，而后者则由专用的 报文转发和交换硬件来完成。路由器由输入、输出模块和交换开关三部分组成。输入模块 负责报文的接收和转发处理，报文经过交换开关进入输出模块以决定报文的流向。其中， 通过报文转发硬件的数据流量占整个系统的9 9 以上，因而报文转发硬件是系统的性能瓶 颈，为了达到较高的转发速度，一般采用专用集成电路芯片( a s i c ) 来实现。 随着i n t e m e t 的迅速发展，新的应用如电子商务、网络多媒体不断被开发出来，新的 协议如多协议标签交换、区分服务被提出并采用，正推动着i n t e m 吐进入一个新的发展阶 段。人们对i n t e r a e t 也提出了更高的服务要求：增加网络通信带宽、支持多媒体话音和图 像的传送、保证网络的可靠性和安全性等等。这要求传统的路由器必须具有一定的灵活性， 以保证对新业务的支持能力，这样采用a s i c 芯片实现报文转发硬件的弊端逐渐显露出来： 第一，由于网络协议和应用的复杂化以及对网络设备的智能要求的提高，使得a s i c 设计变得复杂，庞大，导致研发的风险加大，成本增高，研发周期延长。 第二，研发周期延长导致上市时间推迟，而新的应用出现的速度越来越快，使得新的 基于a s i c 芯片的路由器产品的发布可能总是赶不上新的需求。 第三，对于用户而言，一旦选择了基于a s i c 芯片的路由器，面对新的业务的增长， 将无法及时的更新服务以适应新情况，更换设备的成本较大， 第四，a s i c 芯片的设计受制于集成电路的制造工艺，而目前集成电路的制造工艺已 经接近硅半导体的物理极限，要想进一步提高集成度十分困难。 因此，采用a s i c 芯片构建路由器的设计思想陷入困境。而网络处理器的出现改变了 这种状况。网络处理器是一个“专用指令处理器”，它有自己的指令集。路由器设计者和 最终用户可以根据应用的特点，通过软件开发平台编写出专门的处理程序在网络处理器上 运行，从而获得较高的性价比；同时，一旦应用发生改变，也可以通过迅速更新软件来满 足应用的变化，而不需要更新硬件设备。因此，具有灵活性的网络处理器取代限制较大的 a s i c 芯片，成为路由器报文转发的核心功能单元。 第1 页 国防科技大学研冗生院学位论文 根据摩尔定律，随着光纤通信的发展，存储器的访问速度跟不上光纤传输速度的增长， 而网络处理器中的路由查找，报文分类，流量统计等功能都需要进行查表操作，需要访问 存储器，因此其性能都受到存储器访问时间的限制。寻找高速路由查找算法仍是一个十分 艰巨的任务，目前来看最为有效的办法是基于网络处理器，采用专门的路由查找协处理器， 结合t c a m 组成并行流水路由查找引擎。 1 2 路由查找算法面临的问题 1 2 1i p v 4 的地址结构和基于类的路由查找 i p v 4 为目前i n t e r n e t 上广泛使用的协议，它的地址长度为3 2 比特，分为网络号( n e t i d l 和主机号( h o s t i d ) 两个部分，用( n e t i d ，h o s t i d ) 表示。i p 协议最初提出的时候采用的是基 于类的地址结构，它把i p 地址主要分为a 、b 、c 三类，通过i p 地址的最高几位比特来区 分。各类地址的n e t i d 和h o s t i d 比特数都不同，因此不同地址类型的网络能容纳的主机数也 不相同，如图1 1 所示。 图11有类地址结构 网络路径是用地址前缀表示的，在这种情况下，地址前缀就只有3 种，长度分别为8 、 1 6 和2 4 比特，分别对应于到a 类网络、b 类网络和c 类网络的路径。路由器根据分组目 的地址的前3 比特就可以知道地址的类别，然后取出其前若- p ( 8 、1 6 或2 4 ) 比特，到相应 的前缀集合中进行完全匹配查找就可以了。所以在引入c i d r 之前，只有3 种不同长度的 地址前缀，而且可以很容易地确定一个地址属于哪类前缀，则在查找分组的下一中继点时 不需要进行最长前缀匹配搜索，路由查找要简单得多。 基于类的路由查找在早期的i n t e r n e t 中应用情况良好。但随着i n t e r n e t 的发展，这种地 址分配方式存在的问题逐渐暴露出来： 1 i p 地址的浪费。随着i n t e r n e t 的不断增长，i p v 4 地址本来就显得比较紧张，不能 高效率地使用这些珍贵的资源，i p 地址就会很快用尽。更为严重的是，实际分配情况表明 用户对c 类网络的需要量特别大，尽管c 类网络的数量也是最多的，但仍然不能满足实际 需要；而a 、b 两类网络很少需要，特别是a 类网络，可以分配的数量就更少。这样很可 能造成如下的情况：虽然仍然有很多地址没有分配( 这些地址属于a 类或b 类子网) ，但是 已经不能满足用户对i p 地址的需要了。 2 会造成路由表的严重膨胀。近年来，越来越多的网络连接到i n t e r n e t 上，造成路 篇2 页 国防科技大学研究生院学位论文 由表的指数级膨胀。不幸的是，简单地增加路由器的存储器，扩大路由表容量是不能解决 路由查找问题的。路径越多，路由器的控制c p u 计算路由表、应付网络拓扑结构变化就越 为困难。所以，如果允许路由表中的条目无限制地增长，核心路由器最终必定不得不丢弃 某些路径，使得i n t e r n e t 上的某些网段不可达。 1 2 2 无类域问路由c i d r 及最长前缀匹配l p m 问题 为减缓骨干网路由表的增长速度，提高口地址空间的利用率，i n t e r a c t 工作组m t f 在 1 9 9 3 年提出了无类域问路由c i d r ( c l a s s l e s si n t e rd o m a i nr o u t i n g ) 【1 - 2 】技术，在分配地 址时网络号n c t i d 不再限制为7 ，1 4 或者2 1 比特，可以为任意长度。 采用了c m r 以后，每收到一个口分组，路由器根据分组的目的地址查找路由表， 如果结果与该表项的网络地址相等，则找到了一个匹配的表项。由于路由表中对网络地址 进行了聚合，就有可能找到多个匹配的表项。所以，需要在所有匹配的表项中选择前缀长 度最长的表项作为最终的查找结果，这就是最长前缀匹配l p m ( l o n g e s tp r e f i xm a t c h i n g ) 问 题【5 】。例如，某路由器有如表1 1 所示表项，如果有一个分组的目的地址为1 1 1 0 1 l ，则该 地址与表项4 和7 都匹配，由于表项7 为最长匹配，因此分组被转发到下一跳g 。 表1 1路由表示例 序号l234567 前缀o o l l o ol l +0 0 0 0 0 1 l +1 1 1 0 下一跳abcd efg 路由前缀长度分布是不均匀的，如图1 2 所示，给出了主干网上m a e w c s t 路由表中前 缀长度分布情况，其长度分布有3 个特点： i p v 4 路由前缀长度至少为8 ；l p v 4 路由 前缀并不是按其长度平均分布，大部分的前缀分布在前缀长度为1 6 - 2 4 比特之间，路由表 前缀长度为1 6 - 2 4 的前缀占总数的9 9 ，仅前缀长度为2 4 的前缀就占5 0 左右。m v 4 前缀长度为8 1 5 比特和2 5 3 2 前缀所占比例很小。 5 0 4 5 4 0 匿3 5 荤3 0 豳2 5 2 0 1 5 1 0 5 0 前缀长度 。k - i t | | 89l o1 l1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 12 22 32 42 52 62 7 2 8 2 9 3 0 3 l 3 2 图1 2 m a e w e s t 路由表前缀长度分布情况 第3 页 国防科技大学研究生院学位论文 i p v 6 与i p v 4 相比，在地址格式上发生了很大变化，地址长度由原来的3 2 比特变成了 1 2 8 比特，相应地，i p v 6 在整个地址分配上也进行了一定的改进【3 】。尽管i p v 6 的地址结构 与坤v 4 相比有很多不同之处，但是从根本上来说，整个地址空间仍然是层次性结构，仍然 采用类似于c i d r 地址结构下的路由合并，因此新一代网络协议并没有改变路由查找l p m 的本质特点，而且其长达1 2 8 比特的地址使p v 6 的路由查找面临更大的困难。 1 2 3 路由查找算法研究的难点 由于c i d r 技术的采用需要寻找最长匹配前缀，给高速路由查找带来了很大的难度。 尤其是因为目的地址中无前缀长度的标识，从而不能采用与基于类的查找算法相同的简便 方法。因此，要找到与目的地址匹配的最长前缀，一是要确定目的地址中前缀的长度，二 是要找到与之匹配的表项，同时要达到足够高的查找速度和表项更新速度。虽然围绕这一 问题已提出了多种路由查找算法，但这些算法多存在一定的缺陷：要么存储器访问次数太 多，要么表项更新速度太慢。目前的算法还没有很好地解决路由查找问题。 1 3 路由查找算法的评价标准 就路由查找的实现目标来说，有三个主要指标：路由查找的时间复杂度、空间复杂度 j 以及插入、删除和更新路由的速度。时间复杂度是指实现一次路由查找所需要的时间，这 是路由查找最关键的指标，直接影响路由器处理数据包的能力。空间复杂度是指实现路由 查找所构造的数据结构所占用的存储单元的大小，空间复杂度关系到路由器成本。路由的 插入、删除和更新也是评价路由查找算法的重要指标。由于路由插入、删除和更新操作可 能会导致数据包的丢失，操作需要的时间越长，可能丢失的数据包越多。实际上，通常采 用插空更新的方式来减小这种数据包丢失的危险。 1 路由查找速度 路由查找速度是决定路由查找算法性能及报文转发处理能力的最主要因素。路由查找 的速度要求能适应链路速率的需要，不同的链路速率，其路由查找要求的速度也不一样。 在给定链路速率下，要求的查找速度一般有两种计算方式：一种是按照i n t e r a c t 最短分组 长度和最坏情况下的查找速度来计算。在i p v 4 为基础的i n t e r n e t 的流量中，仅t c p 回应报 文( 2 0 字节的m 头+ 2 0 字节t c p 头，计4 0 字节) 就占4 0 左右【6 - 7 】，因此对第一种情况的 速度一般要求按分组长度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 ) 链路来说最 坏情况下的查找速度需要达到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 字节长度分组计算，即o c l 9 2 ( 1 0 g b p s ) 链路的分组速率为2 5 m p p s 。 另一种是按照平均分组长度和平均查找速度来计算。根据现在的统计结果，i n t e r a c t 上传输的i p 分组的平均长度为2 0 0 0 比特左右，假如平均分组长度为2 4 0 字节，对o c 1 9 2 ， 平均查找速度只要达到5 2 1 m p p s 就可以满足要求。表1 2 给出了要求的路由查找性能与链 第4 页 国防科技大学研究生院学位论文 路速率和分组长度的关系。 表1 2各种线路速率下的查找速度 线路类型线路速率4 0 字节分组4 8 字节分组6 4 字节分组2 4 0 字节分组 0 c 4 8 2 5 g b p s7 8 1 m p p s6 1 2 m p p s 3 7 2 m p p s 1 3 0 m p p s 0 c 1 9 2 1 0 g b p s3 1 2 5 m p p s2 5 0 0 m p p s1 4 8 8 m p p s5 2 1 m p p s o c 7 6 8 4 0 g b p s1 2 5 0 0 m p p s1 0 0 0 0 m p p s5 9 6 2 m p p s2 0 8 4 m p p p s 制约路由查找速度的问题之一是存储器的访问时间太慢，远不能满足数据链路速度的 要求。从表1 2 可以看出，如果链路速率为1 0 g b p s ，即使按照平均分组长度计算，查找速 率也要达到5 2 1m b p s ，即1 9 0 n s 要完成一次路由查找。若采用d r a m ( d 3 a a a m i er a a d o m a c c e s sm e m o r y ) 来存储路由表，按照一次访问时间约为5 0 n s 计算，要支持1 0 g b p s 的链路 速率，最多只能进行三次存储器访问。减少访问存储器的次数是提高查找速度的一条有效 的途径。 所以，一次路由查找需要访问存储器的次数是衡量查找算法速度的指标之一。为适应 高速率链路，并行处理技术成为高速路由查找的一个基础。因此，并行处理结构所实现的 路由查找速率和流程的连续性，成为衡量查找算法性能的重要指标。 2 表项更新速度 路由表一般以转发表形式供转发处理模块进行路由查找。通常路由表由包含协议处理 功能的主控模块产生和维护，而将与转发密切相关的信息简化为转发表，被分发到各转发 处理模块保存和使用。转发处理模块根据主控模块发来的指令对转发表进行更新。 根据对转发表更新方式的不同，路由查找算法可以分为两种类型：一种称为静态算法， 即当发生路由更新( 包括增加和删除) 时，转发表数据结构需要完全重新构建；另一种称为 动态更新算法，当发生路由更新时，只需要在原有基础上相应更新，而不需要完全重构。 与静态更新相比，动态更新的速度更快。 研究表明，骨干网路由器的路由表更新频率很高，可以达到1 0 0 次秒【8 】。路由表的频 繁更新，要求查找算法应该能够动态插入删除转发表项：同时，为了不影响查找操作，插 入与删除时间应尽可能短。因此，快速表项更新算法成为研究的一个热点。为了适应高速 链路而采用并行处理路由查找结构，其一个表项更新需要的更新次数( 或对路由查找流程的 中断次数) 、一次更新耗费的时间，成为衡量查找算法性能的重要指标。 3 支持的路由表容量 随着i n t e m e t 的发展，骨干网路由器的路由表容量也在不断增大，并仍然呈显著上升趋 势【4 】，图1 3 描述了骨干网路由表快速增长的趋势。因此，查找算法对路由表容量的扩展 性要好，以容纳足够大的路由表来适应路由表增长的需要。 第s 页 国防科技大学研究生院学位论文 湫 ， j 。略妒 r j 尹 湫 - 膏 一r 蒯 瞄对一 ，盯，哪1 暖； w 图1 31 9 9 5 2 0 0 5 年骨干网路由表大小增长曲线 4 对v 6 的适用性 口地址的长度越长，路由查找的难度就越大。要求路由查找算法随地址长度的扩展性 要好，以适应地址长度为1 2 8 比特的i p v 6 路由查找。 5 所需的存储空间 转发表数据结构所占存储空间应尽可能少，这样不仅可降低成本，还可用快速存储器 如s r a m 实现，从而达到更高的速度。随着微电子技术的快速发展，存储器的容量不断增 加且价格不断下降，使得对算法所需的存储容量有所放宽。 6 算法实现的灵活性 路由查找算法可以软件实现，也可以硬件实现，因此从查找算法的实现灵活性上考虑， 希望算法能够同时具有软件和硬件实现方式。在高速报文处理中，硬件实现将是路由查找 引擎的主要实现方法，因此路由查找算法的设计应该考虑算法在硬件实现的可行性。 路由查找的各目标之间相互存在一定的矛盾，如提高查找速度就相应的要增加存储空 间的要求，减小存储空间又会使得更新难度增加。因此，一个算法需要选择一个较好的平 衡点，根据不同的需要来设计不同的方案，以实现低成本高性能。特别是对核心路由器， 优先追求的性能指标是：查找速度、更新速度、对i p v 6 适应性以及对大路由表的支持。 1 4 本文的工作及论文的组织 本文的工作着力于研究和解决在网络处理器中寻找高速路由查找算法的解决方案。本 文首先介绍了各种路由查找算法，并分析了各算法的优缺点和性能，并讨论了各种路由查 第6 页 獭 御 埘 咐 嘲 啪 撕 。 枷 蜘 鲫 植 曲 国防科技大学研究生院学位论文 找算法的硬件实现方案，提出了路由查找算法进一步研究的思路和方法。在分析已有算法 的基础上，设计了一种新颖的算法：基于长度标记的位图映射b m t l f ( b i tm a pt i l eb a s e d o nl e n g t hf l a g ) 路由查找算法，并设计了一种实现算法的并行流水硬件结梅。在实现过程 中，针对在使用t c a m 时更新路由表需要进行复杂耗时的排序，以及t c a m 功耗高的问 题，本文提出了一种路由表免排序和降低t c a m 功耗的方案。本文还提出了一种可编程指 针的存储管理算法，减少了存储碎片的产生。 本文共分为五章，各章节组织如下： 第一章，绪论。介绍了网络处理器的发展、路由查找面临的问题、路由查找算法的性 能评价标准。 第二章，典型路由查找算法：主要介绍了各种路由查找算法的软硬件结构，并分析各 种路由查找算法的性能及其优缺点。 第三章，b m t l f 路由查找算法的设计。提出了b m t l f 路由查找算法，介绍了算法的 基本原理，提出一种免排序t c a m 的设计方案。用软件模拟了b m t l f 路由查找算法，对 算法的性能进行了评测。 第四章，b m t l f 路由查找引擎的设计。主要介绍了网络处理器原型系统，提出了一 种在网络处理器原型系统上实现b m t l f 路由查找的方案，设计一种采用可编程指针的存 储管理算法，并提出了一种采用哈希函数c r c 4 映射实现低功耗t c m 的设计方案。 第五章，结论。概括了本文研究的结论和意义，指出了b m t l f 路由查找算法进一步 研究的方向。 第7 页 国防科技大学研究生院学位论文 第二章相关算法及性能分析 2 1 二进制t r i e 树 二进制t r i e 树( b i n a r yt r i e ) 是一种基于树的数据结构，通过路由前缀每一位比特的 值来决定树的各个分支。因为路由前缀都是由0 ，1 比特串组成，所以用二进制t r i e 树来表 示路由前缀是一个很自然的方法。 用二进制t r i e 树表示路由前缀并不是把路由前缀存储在结点中，而是用结点的路径表 示前缀。一般规定一个结点到其左分支的路径表示前缀中的对应比特为0 ，节点到其右分 支的路径代表前缀中的对应比特为1 。在二进制t r i e 树中，处于第l 层的结点代表了一类 地址前l 个比特均相同的地址空间，并且这前l 个比特串就是由从根结点到这个结点路径 上的l 个比特组成图2 1 中带阴影的结点表示该结点对应着一个路由前缀，其中包含了与 该地址前缀相关的转发信息如下一跳指针n h p ( n e x th o pp o i n t e r ) 。 图2 1二进制t r i e 树 如果地址长度为w ，二进制t r i e 树在最坏情况下需要读o ( w ) 次存储器，对i p v 4 来说 是3 2 次；对i p v 6 来说是1 2 8 次。文献 9 中指出如果路由表包含的表项个数为n ，平均需 要访问1 4 4 l o g ：n 次存储器。这种算法的性能和现在所需要达到的目标相差甚远，由于这 种算法是很多算法的基础，所以在这里仍然给出了该算法的工作原理。 2 2 路径压缩t r i e 树 路径压缩t r i e 树( p a t h c o m p r e s s e dt r i e ) 是针对存在很长的单分支路径，其中间节点保 存的是未压缩的完整比特串 1 0 。在查找时，只有当目的地址与节点的比特串匹配时才继 续沿该节点的子树查找。正因如此，该算法消除了回溯，最多只需要访问w 次存储器。 点时，则将该结点与其父结点合并，同时在结点中增加两个域：1 比特位置b i p 0 8 i i o n 表示下一个要比较的字符位：2 比特串b i t s t r i n g ，表示从根到该结点位置的路径对应的 位串。路径压缩t r i e 树的每一个叶子结点含有一个路由前缀和一个下一跳信息指针，如图 2 2 所示。当遍历一个路径压缩t r i e 树查找一个地址时，将结点中的位串与待查找的地址 比较。如果该位串是地址的一个前缀，则存储下一跳信息指针( 如果存在) 并且尊粤! ：i ： 结点。当比较失败或到达叶子结点时路由查找终止。此时，最近记录的下一跳信息指针作 为杳找结果被返回。 p r e a ： b ： c ： d ： e ： f ： g ： 图2 2 路径压缩t r i e 树 路径压缩t r i