（计算机系统结构专业论文）面向ipv6分组转发的路由技术研究.pdf

面向i p v 6 分组转发的路由技术研究；摘要 攘要 自从i n t e m e t 诞生至今，网络互连性能一直是i n t e n e t 网络管理者和学术界所关心的 话题。近年来，随着多媒体网络技术的广泛应用，i n t e m e t 上的数据流量正以每年一倍以 上的速率增长，在可以预见的未来，这个增长速率还会更快。随蓑光透信网络技术的提 出和发展，光纤键路的负载容量每1 2 个月可翻一铸，以满足不断增长的网络流量的需求。 然而，根据摩尔定律，计算机处理能力和硬件水平的扩充大约以1 8 个月一番的速率提高， 这使得i n t e m e t 网络中心节点路由器性能豹发展水平与应用的需求差距缀大。为此，需 要在提高路由器性能方面进行广泛深入的研究，同时为数据传输提供必要的服务质量保 证。 i p v 6 作为下一代赢连网络协议，蠢经开始有计划、有步骤的部署，逐渐取代现阶段 在i n t e r n e t 中广泛应用的i p v 4 网络换议。m v 4 在i n t e m e t 发展初期取褥了巨大的成功， 但是它地址数量不足的问题很大程度上限制了i n t e m e t 规模的进一步扩张。i p v 6 协议吸 收了i p v 41 办议的优点，并对用户在安仝、q o s 等方面的要求提供了支持，其中更熏要的 是重新设计了长达1 2 8 位长度的地址和支持更多层次的编址体系结构，解决了地蛙短缺 的问题。可是，i p v 6 协议又给路由器的设计带来了挑战。一方面，巨大的地址空间必然 带来更多的路由袭项，对海量路由表的查询、维护会给路由器带来繁重的系统负荷；另 一方猫，1 2 8 位长度的地址使得原本应用于i p v 4 路由器的关键算法的效率严重下降，难 以满足分组快速转发的需求。因此，开展基于i p v 6 的路由器关键技术的研究具有熏要的 意义。 本论文在分析i n t e r n e t 发展现状戳及下一代网络协议i p v 6 的篝础上，对于路幽器技 术的发展进行了跟踪，围绕羞路l i | 器协议软件以及路由器分组转发系统关键技术这两大 主题开展研究，论文的创新性工作主要体现在以下几个方面： l ，本文在详细分析了o s p f 路由协议的基础上，比较了o s p f 路由协议与r i p 路由 协议之闯的异国，重点分板了o s p f 路由协议的i p v 6 版本( o s p f v 3 ) 襁昆其i p v 4 版本 的改变。本文通过仔细对照o s p f v 3 路由协议规范，设计并实现了蕊向i p v 6 网络环境的 o s p f v 3 路由协议软件，保证软件实现与协议规范的一致性和功能完整性，尽可能提高 软件静运行效率，减小系统受担。在掰提密的软件实现方案当中，对协议的信令交换机 制、消息的接收处理与消息发送以及协 义实体的状态转换，严格按照协议规范的标准实 现。为了提高路由转发子系统的工作效率，提出了一种面向分组转发子系统的路由表维 护模块设计方案，通过对路由表存储方式的改变，一方面可以减小路由转发予系统的系 统负荷，另一方颓可以提高路e & 协议予系统中路由表更新过程的效率，保涯了路由器整 体性能的提高。 2 ，本文在分析了几种常见的基于i p v 4 的路由搜索算法的基础上，比较了它们在搜 面向i p v 6 分组转发的路由技术研究：摘要 索时间复杂度、空闻复杂度上的差别，分析了它们在i p v 4 网络向i p v 6 网络过渡期的适 应性，参考其中算法性能和可扩展性较好的基于地址前缀长度的二分搜索算法的设计思 想，重点针对该算法在i p v 6 协议体系结构下面临的问题，提出了稀新的基于p v 6 的 快速路e 瞻蹙搜索算法一a b s h 算法。a b s h 算法采阁两级搜索方式，合理划分姥址蘸缀 空间，使得每一个子空间内的算法数据结构改变不会影响到其它子空间内的数据，从而 提高了算法的效率和鲁棒性。通过论证前缀扩展的特性，提出了对一级线性索引表进行 快速添加、删除及更新的方法。在分析努法核心数据结构二分搜索树浆构建形式之 后，提出了两年申构建二分搜索树的方案，进一步优化了算法执行的平均效攀。还针对b s h 算法中更新效率较差的缺点，设计了附加于原算法数据结构之上的新数据结构b m p 树，使得算法的更新效率得封了显著的攥高。a b s h 算法的设计充分考虑了i p v 6 网络环 境和分组格式的特点，使其更加适用于i p v 6 路由器分组转发过程中的路由表搜索模块。 最后，编写程序用软件实现了a b s h 路由表搜索算法，并且通过对测试数据与b s h 算 法的比较，验证了在i p v 6 环境下a b s h 算法的搜索和更新效率都远远优于b s h 算法， 即使执行大援模路e 表的搜索任务，该算法仍可保持优异的性能。 3 ，在深入浅出的阐明i p 分组分类问题之后，分析了几种常见的基于i p v 4 的i p 分 组分类算法，比较了这几种算法在搜索时间复杂度和空间复杂度方丽的麓别，详细论述 了其中一类广泛应用的p 分组分类算法一元组空间接索算法，针对该算法在i p v 6 协 议体系结构下亟临的挑战，并且基于论文工作在路由表搜索算法方灏做出的贡献，提出 了一种改进的元组空间搜索算法，通过a b s h 算法针对i p 分组分类问题和元组空间搜 索算法中剪裁过程的需要进行的修改，提高了元组空间接索算法剪裁的效率。相沈元组 空间搜索算法原本使用的基于e r i e 楗豹丽言，改进骺的算法一方面控制了算法对虎存的 消耗，另一方面将算法的搜索效率提高了5 5 倍，更加适用于i p v 6 网络环境，并且对解 决i p v 4 环境中的分组分类问题具有重要的参考价值。 关键词：i p v 6 ，0 s p f v 3 ，分组转发，路由表焱询算法，路由技术，分组分类 l i 面向i p v 6 分缎转发的路由技术研究：a b s t r a c t r e s e a r c ho nr o u t i n gt e c h n o l o g yf o ri p v 6p a c k e tf o w a r d i n g s u nq i n g n a n ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db yl us h i w e n i n t e n e tt e c h n o l o g ya n dn e t w o r kp e r f o r m a n c ea r eb o t hi s s u e sa t t r a c t i n gal o to fa t t e n t i o n s 。 t h et r a f f i ci nt h ei n t e m e ti se x p l o d i n g 髂i ti sd o u b l i n ge v e r yy e a r e m e r g i n gm u l t i m e d i a a p p l i c a t i o n sw i l lm a k et h ee x p l o s i o ne v e nf a s t e ri nt h ef u t u r e w i t ht h ee m p l o y m e n ta n d e v o l u t i o no ff i b e r - o p t i ct e c h n o l o g i e s , t h ec a r r y i n gc a p a c i t yo ff i b e rl i n k si sd o u b l i n ge v e r y1 2 m o n t h st om e e tt h ef u t u r eb a n d w i d t hd e m a n d s h o w e v e r , a c c o r d i n gt ot h em o o r e sl a w , t h e c o m p u t i n gp o w e rw i l lo n l yd o u b l ee v e r y18m o n t h s ，h e n c ei pr o u t e r sw i l li n e v i t a b l yb e c o m e b o t t l e n e c ki nt h ei n t e m e t m o r e o v e 矗m u l t i m e d i aa n dr e a l - t i m ea p p l i c a t i o n sr e q u i r et i m i n ga n d o t h e rq u a l i t yo fs e r v i c e ( q o s ) g u a r a n t e e s ，b e s i d e sb a n d w i d t h , t h a tp u te v e nm o r eb u r d e no n t h er o u t e r s t h e r e f o r e ，t h ef u t u r eg r o w t ho ft h ei n t e m e tr e q u i r e sd e s i g na n dd e v e l o p m e n to f h i g h - s p e e di pr o u t e r st h a tf o r w a r de x p o n e n t i a l l yi n c r e a s i n gv o l u m eo f t r a f f i ca n dp r o v i d eq o s g u a r a n t e e sa tt h es a m et i m e a san e x tg e n e r a t i o ni n t e m e tp r o t o c o l ，i p v 6p r o t o c o li sb e i n gd e p l o y e ds t e pb ys t e p ，a n d w i l le v e n t u a l l yr e p l a c e si p v 4p r o t o c o lw h i c hi sw i d e l ye m p l o y e di nt h ei n t e r a c t i p v 4p r o t o c o l h a sm a n ya d v a n t a g e sw h i c hl c a daw o n d e r f u ls u c c e s si nt h ep a s to f t h ei n t e m e t b u ti t sl i m i t e d a d d r e s sa m o t m tr e s t r i c t st h es c a l eo f t h en e t w o r k i p v 6p r o t o c o li n h e r i t st h ea d v a n t a g e so f i p v 4 a n d c a no f f e rs e v e r a ln e wf u n c t i o n ss u c ha ss e c u r i t ya n dq o s t h em o s ti m p o r t a n t i m p r o v e m e n ti si t s1 2 8 - b i ta d d r e s sl e n g t h h o w e v e r , i t sac h a l l e n g ef o rn e t w o r kr o u t e r sb a s e d o ni p v 6b e c a u s eo no n eh a n d ，ah u g ea d d r e s ss p a c ew i l lb r i n g sav e r yl a r g er o u t i n gt a b l e ；o n t h eo t h e rh a n d ，t h ep e r f o r m a n c eo fs o m ec o r ea l g o r i t h m sw i l lc o m ed o w nw i mt h e1 2 8 - b i t a d d r e s sl e n g t h ，s or e s e a r c ho np v 6r o u t e rt e c h n o l o g i e sw i l tb es i g n i f i c a n t l yh e l p f u lf o rt h e n e x tg e n e r a t i o nn e t w o r k t h ed i s s e r t a t i o ns t u d i e st h ed e v e l o p m e n to fi n t e r a c tm u t e r t e c h n o l o g i e s ，b a s e do ni p v 6 p r o t o c o la n a l y s i s ，a n df o c u s e so nt w oi s s u e si nt h ea r e a o fr o u t i n gp r o t o c o ls o f t w a r e i m p l e m e n t a t i o na n dp a c k e tf o r w a r d i n gt e c h n o l o g y t h em a j o rc o n t r i b u t i o n so f t h i sd i s s e r t a t i o n a r es u m m a r i z e da sf o l l o w s ： 1 ) t h ed i s s e r t a t i o ns t u d i e st h eo s p fp r o t o c o ls t a n d a r d ，c o m p a r e so s p fp r o t o c o lw i t hr i p p r o t o c o l ，a n di n d i c a t e st h ed i f f e r e n c eb e t w e e nt h e m b a s e do nat h o r o u g hi n v e s t i g a t i o no n o s p fp r o t o c o lf o ri p v 6 ，o s p f v 3 ，t h ed i s s e r t a t i o nd e s i g n sa n di m p l e n m e n t sa no s p f v 3 r o u t i n gp r o t o c o ls o f t w a r ef o ri p v 6 t h es o t h v a r ep r e s e r v e sp r o t o c o lc o n s i s t e n c ya n df u n c t i o n a l i n t e g r a l i t y , p r o v i d e sh i g h e re f f i c i e n c ya n dl o w e rc o s t i nt h es o f t w a r ei m p l e m e n t a t i o n ，i t i i i 面向i p v 6 分组转擞豹路由技米罐f 究：a b s t r a c t s t r i c t l y f o l l o w st h er u l e so ft h ep r o t o c o ls t a n d a r df o rp r o t o c o ls i g n a lc o m m u n i c a t i o n m e c h a n i s m ，m e s s a g es e n d i n g , m e s s a g er e c e i v i n ga n dp r o c e s s i n g ，s t a t et r a n s i t i o n si nt h ef i n i t e s t a t em a c h i n e ，a n ds oo n 。i no r d e rt oh l l p l d v et h ee f f i c i e n c yo fp a c k e tf o r w a r d i n gs u b - s y s t e m , t h ed i s s e r t a t i o np r o p o s e sad e s i g ns c h e m ef o rr o u t i n gt a b l em a i n t e n a n c e ，w h i c hm a yr e d u c e s t h ec o s to f p a e k e tf o r w a r d i n gs u b - s y s t e ma n di m p r o v e st h ep e r f o r m a n c eo f r o u t i n gt a b l eu p d a t e p r o c e s s 蕊翳站d i s s e r t a t i o ni n t r o d u c e ss e v c r 基e o m m o d 疆磷r o u t i n gt a b l el o o k u pa l g o r i t h m s ， c o m p a r e st h e i rs e a r c ht i m ea n dm e m o r yc o s t ，a n da n a l y s e st h ea d a p t a b i l i t yw h e nt h e ya l eu s e d b y 翌酶n e t w o r kr o u t 攫 s ，穗ed l s 涮躲融娆p r e s e n t san e wf a s tr o u t i n gt a b l el o o k u pa l g o r i t h m a p p l i c a b l ef o ri p v 6 。w h i c h i sc a l l e da b s ha l g o r i t h m a b s ha l g o r i t h mc o n s t r u c t sat w o * l e v e i d a t as t n l c k l r e i td i v i d e st h ew h o l ea d d r e s ss p a c ei n t om a n ys u b - s p a c e s d a t as t r u c t u r ec h a n g e i na n ys u b s p a c e sw o n ta f f e c to t h e r s n ea l g o r i t h mi se f f i c i e ma n dr o b u s t i na d d m o n , t h e d i s s e r t a t i o np r e s e n t san e wa l g o r i t h mt oa d d ，d e l e t ea n du p d a t et h ei n d e xt a b l e , a n dd e s i g n sa n e wd a t as t r u c t u r e i e 。b m p - t r e e , t oi m p r o v et h es e a r c h i n ga n du p d a t i n gs p e e d 。确ed e s i g no f a b s ha l g o r i t h mt a k e st h ec h a r a c t e r i s t i c so fi p v 6n e t w o r ke n v i r e m e n ta n di t sp a c k e tf o r 髓a t i m of u l la c c o u n t ，i tw o r k sw e l i i nm u t i n gt a b l el o o k u pm o d u l eo fp a c k e tf o r w a r d i n g s u b - s y s t e m a tl a s t , t h ea l g o r i t h mi si m p l e m e n t e da n dt e s t e d i ti sp r o v e dt h a ta b s ha l g o r i t h m h a sa ne x c e l l e n tp e r f o r m a n c ef o rv e r yl a r g er o u t i n gt a b l el o o k u p ， 3 1t h ed i s s e r t a t i o ni n t r o d u c e st h ei pp a c k e tc l a s s i f i e ri s s u e s , c o m p a r e ss e v e r a li p v 4p a c k e t c l a s s i f i e ra l g o r i t h m s ，a n dd e e p l ya n a l y s e st h et u p l es p a c es e a r c ha l g o r i t h m ，w h i c hi sw i d e l y u s e di nt h e 强v 4n e t w o 蠢，t h ed i s s e r t a t i o ni m p r o v e st h et u n es p a c es e a r c ha l g o r i t h m m o d i f i e s a b s ha l g o r i t h ma n da p p l i e si ti n t ot u p l ep r u n i n g p r o c e s si no r d e rt oo p t i m i z et h ea l g o r i t h m p e r f o r m a n c e c o m p a r e dw i t ht h e o r i g i n a ls e a r c ha l g o r i t h mb a s e do nt i l e ，t h ep r o p o s e dt u n e s p a c es e a r c ha l g o r i t h mc o n t r o l st h em e m o r yc o s ta n di n c r e a s e st h ee x e c u t i v es p e e dt om o r e t h a n5t i m e s f t v t h e r m o r e , t h ei m p r o v e da l g o r i t h mh a sab e t t e rp e r f o r m a n c ei nl p v 6n e t w o r k e n v i r o n m e n t k e y w o r d s ：i p v 6 , o s p f v 3 ，p k e tf o r w a r d i n g , r o u t i n gt a b l el o o k u pa l g o r i t h m r o u t i n g t e c h n o l o g y , p a c k e tc l a s s i f i e r i v 面向i p v 6 分组转发的路由技术研究：图目录 图目录 图1 1o c 1 9 2 i p 主干网网络拓扑图 图2 ，1 基于总线的单处理器体系结构 图2 2 配备了路由缓存的基于总线的多处理器体系结构 图2 3 多重并行转发引擎的基于总线的多处理器体系结构 图2 4 基于交换的多处理器体系结构 图2 5 共享媒介交换结构 图2 6 共享内存交换结构 图2 7 分布式输出缓存交换结构 图2 8 交叉开关交换结构 图3 1o s p f v 3 路由协议软件主模块关系图。 图3 2h e l l o 消息导致的邻居状态转换一 图3 3 数据库描述消息导致的邻居状态转换 国3 4 接口状态转换图 图3 5 最短路径优先算法流程图 图3 6 二叉树节点添加算法程序流程图 一2 9 1 0 1 1 1 2 1 4 1 5 1 6 1 7 2 5 3 l 图3 7o s p f v 3 路由协议软件实验环境拓扑图一 图4 1 在路由器功能缩构中的路国表搜索模块以及它与其他模块问的逻辑关系 图4 2 二迸制1 h e 树 图4 3 经过路径压缩意的二进制t i l e 树 圈4 4b s h 算法的数据结构 图4 5r f c 2 3 7 4 中的i p v 6 可聚合全球单播地址格式 图4 6i p v 4 路由器中的遗址前缀长度分布 强4 7a b s h 算法对遗址前缀的划分 i x ” 弘 弘 勰 档 “ 钳 们 柏 引 甜 筒向i p v 6 分组转发的路由技术研究： 国目录 阁4 8a b s h 算法数据结构5 2 图4 9 羲缀扩展过程中不可能出现的覆盖情况5 4 图4 1 0 一级索弓l 寝结构，5 5 圈4 。1 1 一级索引表项结构5 6 图4 1 3 以o + 节点为擐的多分支树与b m p 书畦示意图，5 8 图4 。1 4 以l + 节点为扳的多分支树与b i v i p 树示意图，5 8 图4 + 1 5 删除前缀p 时，对应p 的前缀扩展范围最小的情况，6 2 图4 1 6 删除前缀p 时，对应p 的前缀扩展范围不是最小的情提，6 3 图4 ，1 7b m p 树结构，6 4 图4 。1 8b s h 算法的h a s h 表结构6 6 图4 19 单个h a s h 表项的数据结构6 7 嘲4 2 0 路由表中前缀长度分布统计图。6 8 图4 2 1 不同结构的二分搜索树6 9 图4 2 2 在一定时间段内进行叠加得到的前缀长度分布7 0 图4 2 3 实验结果对比分析7 l 圈5 1r f c 算法示意图7 4 图5 1 2 过滤规则数据库与元组空间之间的关系7 6 图5 3 过滤规则数据库示意图7 8 图5 4 源地址前缀表与目的地址前缀表7 8 图5 5 原始过滤规则数据库7 9 图5 6 元组空间h a s h 表集合8 0 图5 7 添加了h a s h 表指针的过滤规则数据库8 0 图5 8 源地址前缀表生成过程8l 图5 9 应用于元组空间搜索算法的a b s h 算法数据结构示意图8 2 图5 1 0 不同域对应元组空间的交集8 4 x 面向i p v 6 分组转发的路由技术研究；表尉录 表目录 表3 1 实验环境路由器软硬件配置 表4 2 不问路由表搜索算法复杂度比较 3 9 ，4 7 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含 其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：如衣南日期：弦心， 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者签名：如京匈导师签名：日期：加f ， 第一章引言 第一章引言 1 1 开展面向i p v 6 分组转发的路由技术研究的意义 进入2 0 世纪8 0 年代末期以来，因特网的发展是计算机研究领域最引人注目的事件。 尤其是进入9 0 年代以来，因特网业务发展迅猛，数据流量以每年1 倍的速率增长 k s 9 8 】 在我国，因特网的发展虽然相比发达国家起步较晚，但是在最近几年也取得了长足的进 步。根据c n n i c 最新一期的中国互联网络发展状况统计报告显示，截至到2 0 0 4 年1 2 月3 1 日，我国的上网计算机总数达到了4 1 6 0 万台，同半年前的上一次调查结果相比， 上网计算机总数增加了5 3 0 万台，增长率为1 4 6 ，与一年前同期相比增长了3 4 7 ， 是1 9 9 7 年1 0 月第一次调查结果的1 3 9 1 倍。而我国的上网用户总人数，已经比2 0 0 4 年 年中进行的第十四次统计报告中所显示的数字增长了7 0 0 万人，达到了9 4 0 0 万人，增长 率为8 o 。因特网已经或正在改变了人们的生活习惯、工作方式、传媒方式、商业活动 等，而人们对于网络的要求也不再满足于传统的网络应用，逐渐对网络提出了更高性能 的要求。 i p ( i n t e m e tp r o t o e 0 1 ) 以其开放、灵活、简单的特点成为i n t e m e t 的核心，业界一直流 行着 e v e r y t h i n go ni p ，i po v e re v e r y t h i n g 。 i po v e re v e r y t h i n g 已被实践证明，口以对 上层屏蔽底层的物理细节的差异而实现各种网络互联，这正是i p 的精髓之所在； “e v e r y t h i n go i li p ”中的 e v e r y t h i n g 包括数据、图像和话音等实时和非实时业务。口通过 用户数据封装，对每个数据包独立选路和转发，从而实现了各种业务的统一传输。口和 t c p 的结合，能够实现端到端的可靠网络数据传递，为所有的因特网应用提供了统一方 便的支撑平台。口所具有的技术特性已使它成为一种开放通用的应用技术。 路由器是重要的p 网络设备，也是i n t e m e t 互连的核心设备，实现数据分组的选路 和转发。它的性能直接影响着网络互连的质量，它的处理速度是网络通信的主要瓶颈之 一。在企业网、城域网乃至整个i n t e r n e t 研究中，路由器技术始终处于核心的地位，其 发展历程和方向，成为整个i n t e m e t 研究的一个缩影。随着i n t e m e t 节点数的增多以及大 量宽带应用的出现，路由器需要完成大吞吐量的高速转发，并且保证定的服务质量。 随着用户业务的数据化、口化，主干网的疋化，路由器在主干网的地位和作用显 得日益突出。许多通信企业纷纷建立以路由器为核心的m 主干网。图1 i 显示了美国 q w e s tc o m m u n i c a t i o n s 建立的o c - 1 9 2i p 主干网络拓扑。 中国科学院博士学位论文一面向i p v 6 分组转发的路由技术研究 图1 1o c - 1 9 2 1 p 主干网网络拓扑图 随着网络技术的发展，路由器的结构从传统的总线方式发展到现在的交换式路由器 结构，路由器的结构变得越来越复杂，功能越来越完善，交换容量和交换速度也越来越 高。从功能上看，由于i n t e m e t 的商业化及其业务种类的增多，i s p 要为用户提供相应的 服务质量保证，路由器的功能从简单的路由搜索和转发向支持q o s 的方向发展 就目前来看，路由器主要朝以下两个方向发展： 1 ) 路由器的高速化 技术的发展使得线路带宽成倍提高，这就要求路由器能以线速处理接收的数据，尤 其是骨干网，现在的骨干网线路带宽基本上都是采用2 5 g b i t s 、1 0 g b i t s 甚至更高，因 此路由器必须以很高的速度处理数据，否则将会造成数据包丢包，网络拥塞和网络带宽 利用率的降低。另一方面，为了处理一些实时业务，路由器必须尽量减小口包的处理时 延以适应业务i 拘需要。路由器的高速化要求路由器能支持大容量的口交换，路由器的交 换容量随着端口密度的增加而增加，目前c i s e oc r s 1 路由器支持高达6 4 0 g b i t s 的交换 容量。 总线方式的路由器受限于总线速率，其端口密度不能过大，而采用空分交换结构后， 核心交换部件的速率提高了，而且多个端口可以同时交换数据，可以通过扩大交叉矩阵 的接口来增加端口数量。 为了实现系统的可扩展性，下一代路由器还将会采用并行式结构，并行式结构路由 器在多个接口卡间共享多个转发引擎以实现高速转发的需要。它将路由处理的核心部件 转发引擎集中起来，当接口板接收数据时，进行本地相应的解包处理，然后将m 报 头送往转发引擎进行m 路由及相应的报头处理，完成后再返回路由信息，由接口板完成 数据包的转发采用并行式结构带来的好处是有利于系统升级，当要求系统的交换速率 和交换容量增大时，只需增加转发引擎直到满足系统的要求，而且这种结构有利于增大 端口密度。 2 第一章引言 2 ) 支持q o s 早期的路由器并不支持q o s ，但是随着i n t e r n e t 的快速发展，i n t e m e t 的尽力而为的 方式不再满足服务需求。随着因特网的商用化，i s p 需要为不同的用户提供不同级别的 服务，而另一方面，由于m 网络支持服务的多样化要求坤网络能适应不同服务的特性。 可以看到，随着因特网的大众化，网络的q o s 也将会显得越来越重要。 目前在路由器中实现q o s 通常采用区分服务区分服务为不同的用户提供不同的业 务保证。区分服务首先对用户数据进行分类，并检测用户数据是否满足用户约定，对满 足用户约定的用户数据，路由器通过改写用户数据的t o s 字段以实现对用户数据进行优 先权排队，并通过采用加权公平队列进行排队输出对不满足用户约定的数据，路由器 要么将该数据包丢弃，要么将该数据包放到一个低优先权队列中以实现尽力转发。 i p v 6 作为下一代互连网络协议，已经开始有计划、有步骤的部署，逐渐取代现阶段 在i n t e r n e t 中广泛应用的i p v 4 网络协议i p v 4 在i n t e m e t 发展初期取得了巨大的成功， 但是它地址数量不足的问题很大程度上限制了i n t e r n e t 规模的进一步扩张。i p v 6 协议吸 收了i p v 4 协议的优点，对人们所要求的安全、q o s 等方面提供了支持，更重要的是重新 设计了长达1 2 8 位的地址长度，解决了地址短缺的问题。可是，口v 6 协议又给路由器的 设计带来了挑战。一方面，巨大的地址空间必然带来更多的路由表项，对海量路由表的 查询、维护会给路由器带来繁重的系统负荷；另一方面，1 2 8 位长度的地址使得原本应 用于i p v 4 路由器中关键算法的效率严重下降，无法满足分组快速转发的需求因此，开 展基于i p v 6 的路由器关键技术的研究具有重要的意义。 1 2 本文的贡献 本文的研究工作主要集中在路由协议软件的设计实现、路由表搜索算法和口分组分 类算法这三个方面。个路由器系统可以分为路由协议和路由转发两大子系统。路由协 议子系统通过某种路由协议在不同的路由器之间交换路由信息并计算网络拓扑，生成路 由表；路由转发子系统通过按照路由表生成转发表，将进入路由器的分组按照不同的路 径转发给不同的路由器或主机。在路由协议子系统的范围内，本文首先在分析o s p f 路 由协议的基础上，重点比较了o s p f 路由协议与r i p 路由协议之间的异同，并且重点分 析了o s p f 路由协议的i p v 6 版本，o s p f v 3 ，相比其i p v 4 版本带来的改变。通过详细对 照o s p f v 3 路由协议规范，设计并实现了面向i p v 6 网络环境的o s p f v 3 路由协议软件， 给出了软件实现过程中重点模块的设计思路、实现代码伪码和流程图。在路由转发子系 统的范围内，针对路由表搜索模块和分组分类模块的核心：路由表搜索算法以及妒分组 分类算法开展了研究，在分析了几种经典的路由表搜索算法和i p 分组分类算法各自的实 现方法和优缺点之后，分别提出了两种优化的算法方案，即面向i p v 6 的a b s h 路由搜 索算法和面向i p v 6 的元组空间搜索算法，提高了路由搜索和m 分组分类的效率具体 来说，本论文的主要工作体现在以下几个方面： 中国科学院博士学位论文面向i p v 6 分组转发的路由技术研究 1 设计并实现了o s p f v 3 路由协议软件本文对o s p f 路由协议的实现原理和实 现机制进行了简明的介绍，并且比较了链路状态路由协议o s p f 与距离矢量路 由协议r i p 之间的异同，通过它们之间的比较，说明了o s p f 协议相对于r i p 协议的优点，o s p f 路由协议更加适合作为内部网关路由协议应用于现代网络 中随着i p v 6 协议研究与应用的广泛开展，o s p f v 3 路由协议作为o s p f 协议 的i p v 6 版本，在协议描述上已有很多不同，本文对此也加以介绍。随后，本文 着重介绍了o s p f v 3 路由协议软件的设计与实现方案，包括总体模块设计，关 键算法的流程框图，消息发送、接收处理机制和相应的代码伪码以及协议机制 中的邻居状态机、接口状态机的事件驱动方案设计等。本文出于提高路由器整 体性能的目的，将一部分路由转发子系统中路由表搜索模块所要进行的预处理 工作交由路由协议软件的路由表维护模块处理，在本文中也阐述了这样做的意 义以及相应带来怎样的效率提高。 2 提出了一种面向i i v 6 的快速路由表搜索算法。本文首先介绍了路由表搜索算法 在路由器体系结构中所处的位置，随后给出了对一些已经广泛应用于口v 4 的路 由表搜索的算法的介绍j 并且通过在它们之间的对比，指出它们各自的优点和 局限性。通过吸收这些算法设计思想的精髓，本文提出了一种面向i p v 6 的快速 路由表搜索算法一a b s h 算法。给出了算法实现的各种数据结构以及操作步 骤，并且通过理论分析证明了前缀扩展的特性，进而提出了对一级索引表进行 快速添加、删除和更新操作的方法。为了克服a b s h 算法更新效率较差的缺点， 本文提出在a b s h 算法数据结构之上附加一个称作b m p - t r e e 的数据结构，这样 撒可以显著改善算法的更新效率，本文也对b m p - t r e e 的构建与操作过程进行了 介绍。面向i p v 6 的a b s h 算法一个实现的难点是h a s h 算法的设计，本文也给 出了相应的解决方案。最后，本文通过编写代码实现了该算法，并且通过理论 分析和实验分别验证了算法的效率。 3 提出了一种基于元组空间搜索算法的面向i p v 6 的改进算法。本文首先给出了m 分组分类算法的数学描述，并且介绍了在妒v 4 网络中常见的一些p 分组分类算 法的设计思想，并且以其中一种算法一元组空间搜索算法作为基础，根据i p v 6 协议格式下的分组分类问题的特点，对其加以改进。在对该算法的改进中，其 中一个主要的算法模块是元组空间剪裁模块，而该模块的工作原理与路由表搜 索算法要解决的问题十分类似，因此，本文将a b s h 算法加以进一步改造，使 其能够适用于元组空间搜索算法的元组空间剪裁模块当中，这样便为改进的元 组空间搜索算法提供了更大的可扩展性。最后，本文通过理论验证了算法相对 优化的执行效率。 4 第一章引言 1 3 论文的组织 论文的主题是面向妒v 6 分组转发的路由技术研究，主要研究了三方面内容，包括路 由协议软件的设计实现，面向i p v 6 的路由表搜索算法设计以及面向i p v 6 的p 分组分类 算法设计。论文的总体结构分为六章，除了第一