（微电子学与固体电子学专业论文）路由查找算法的研究及其fpga实现.pdf

摘要 摘要 近年来，随着i n t e m c t 的迅速普及，使用i m e m e t 的人数、连接到i n t e m e t 上的主 机数量和数据流量呈现指数式的增长。另一方面，各种新的多媒体业务也不断涌 现。因此i n t e m e t 的容量正在成为一种稀缺资源。为了适应i n t e m e t 应用的迅速发 展，提供更好的服务质量，必须提高网络的容量。随着光纤技术的发展和g 比特 级交换技术的发展有效的解决了链路带宽、路由器的吞吐量问题，而路由器的转 发效率就成为制约网络性能提高的主要瓶颈。路由器转发包的过程包括很多工作 包头的封转、修改t t l 域、计算和更新校验域和对包进行分类并将它们排入适当 的对列中等等。然而在转发过程中最耗时的是根据数据包的目标地址查找下跳 路由，即路由表查找。因此，设计高速路由查找算法是实现高速分组转发的关键。 本论文在综合了国内外近年来在路由奄找算法及其实现以及相关技术研究进展 的基础上，经过系统深入的研究，最终采用r a m 和t c a m 结合的t r e eb i t n l a d 组 构的算法进行路由查找的实现，并下载到x i l i l l ) 公司的v i r t e x i i 系列x c 2 v 1 0 0 0 器件 中，经验证功能正确。 本文的特点和创新之处包拽 1 对现有的软件和硬件实现的路由查找算法进行了空间和时间复杂度的分 析和比较。 2 根据路由前缀分布的特点，特别是最近几年路由前缀长度大于2 4 位的路 由项大幅增加，所以把路由前缀项大于2 3 位的路由项存储在t c a m 中，而 把其他的路由前缀项使用b i t m a pt r e e 结构存储在r a m 中，这样就可以同 时进行在r a m 和t c a m 中进行路由查找，加快查找速度。 3 对于存储在r a m 中t r e eb i t m a p 结构中的i n t e r n a lp r e f i x 和e x t e n d i n g p a t h 同时进行处理，、进行路由地址的查找。这样就可以避免回溯访问 b i tt i l a pt r e e ，减少工访问r a m 的次数，加快了路由查找的速度。 4 完成了使用此路由查找算法的路由前驱引擎的设计，在前驱引擎中完成 数据包的接收、修改t 性域、校验域的计算和更新。 5 所有硬件实现模块使用t 一d o n 的设计方法，用v e r i 1o g 代码进行代码编 写，并在x i l i n x 公司的x s t 软件中进行了综合以及最后的下载验证f 载 至x c 2 v l 0 0 0 器件中，经验证功能正确。经x s t 工具综合，整个模块的速度 可达到8 8 m h z ，可以满足o c 一4 8 高速路由查找的要求。 关键字：t c a m ，t r e eb i t m a p ，f p g a ，路由前驱引擎 a b s t r a c t a b s t r a c t r e c e n t l y ，i n t e m e ti sp o p l l l 盯i np e o p l e sl i f ea 1 1 dm o r ea i l dm o r em a c h i n e sa r e c o n n e 曲酣t om ei m e m e t 0 nm eo t h e rh 卸d ，l en e wm e d i as e r v i c eb a s e do nm e i n t e m e te m e r g e d s o 也ei n t e r n e tc a p a b i l i t yb e c o m e st h er a r er e c o u r c e i no r d e rt o a d 印tt h er a p i di m p m v e m e n to fi n t e m e t 印p l i c a t i o na n dp r o v i d em o r ce 仃c c t i v e s e r v i c eq u a l “y ，1 en e t w o r kc 印a b i l i t ym u s tb ei m p r o v e d w i 也t h ei m p r o v e m e n to f f i b e rt e c t l l l o l o g ya i l d g b i ts w i t c ht e c l l n o l o g y ，t h en e t 、v o r kb a i l d 、v i d t ha l l dm u t c r 恤d u g h p u th a v e b e e ne m c t i v er e s o l v e d b u tt l l er o u t e r st r a i l s m i te m c i e n c yb e c o m e s t l l eb o t t l e n e c kt ol i m i tn l ed e v e l o p m e mo fn e t w o r k t h et r a n s m i tp a c k a g eo fr o u t e r i n c l u d e st l l c s ep m c e s s ：p a c k a g ch e a da s s e m b l e ，u p 出t et t lf i e l d ，c a c u i a t ea n du p d a t e c r cf i e l d ，c l a s s 姆t h ep a c k a g ea n dp u tt 1 1 ep a c k a g ei n t ot 1 1 e 印p m p r i a t eq u e u ea n d s oo n h o w e v e r ，m es e a r c hn e x th o pa c c o r d m gt op a c k a g e sd e s t i n a t i o na d d r e s si nt h e t r a n s m i tp r o c e s si s 也em o s tt i i l l e c o n s 啪i n g s o ，h o wt 0i i r l p l e m e mt h eh j g hs p e e d r o u t e rl o o k u pi s t 1 1 ek e yt oi m p l e m e ml l i 曲s p e e dt m s m i tp a c k a g e hm i st h e s i s ， b a s e do n 吐1 ei pa d d r e s s1 0 0 k u pa l g o 栅l r l l s ，m e i ri m p l e m e n t i n gp a m sa i l dm e i rr e l a t i v e t c c h n o l o g i e sa r ed e v e l o p e di i l 也e s ef i e l d s t h er a m a n dt c a ma r ea d o p t e dt os t o r e i pl o o k u pi t e m s 1 1 1 e nt 1 1 et r e eb i t m 印s 饥i c t u l ei si m p l e m e n t e di no u rd e s i g nw i t h x c 2 v 1 0 0 0d e “c eo fx i l i n xv i n e x i is e r i e s s e v e r a la s p e c t sa r ei n c l u d e di nt l l et h e s i s ： 1 a r c ri m p l e m c n t i n gt h ei pl o o h l pa l 誉谢也m si ns o f c w a r ea n dh a r d 、v a r e ，i t s c o m p l e x i t yi ns p a c ea i l dt i m ed o m a i na r ea l l a l y z e da n dc o m p a r e d 2 a c c o r d i n gt ot h ep r e f i xl e n g t | ld i s t r i b u t i o n ，e s p e c i a l l ym ep r e f i xl o n g e rt h a n 2 4h a v eg r o w nf 如t l yi nr e c e m l yy e 盯s ot h ep r i n xw h i c h 虹l el e n g ml o r l g e r t l l a n2 3a r e p u t e d i n t o t c a m ，a n d 协eo t h e r sa r es t o r e d i n t h e r a m 埘t 1 1 t h e t r e eb i t n l 印s t n l c t u r e ，t h e n 1 ei pl o o k u pc a l lb es e a r c h e di nt 1 1 er a ma i l d t c a m 3 t h ei n t e m a lp r e f i x 肌de x t e n d m gp a mi t e ma r cs y n c h m n i z e dd e a l e dw i t hi n o l l rd e s i g n ，w h e nm cp r c f i xa r cb e 啦s e a r c h c di nt l l er a m t h i sc a np r e v e n t a l g o r i t l l m 仃a c eb a c k 趾dr e d u r ea c c e s sm el t a md m e s ，q u i c k e nt 1 1 es p e e do f s e a r c hi pl o o k u p 4 t t l ef b n j l ，a r de n g i n eu s i n gt h ea b o v ei pl o o k u pa i g o r i t h m si si m p l e m e n t e d ， t h ef o r w a r de n 百n er e a l i z et h e s ef u l l c t i o n s ：r e c e i v ep a c k a g e ，c h e c kc r c f i e l d ，u p d 砒et t l f i e l da n dc r cf i e l d 5 t h et o p d o w nd e s i g nm e m o d o l o g yi su s e di no u rd e s i g na n da um o d u l e sa r e c o d i n gi nv e r i l o g h d l t h ed e s i g nh a sb e e ni m p l e m e n t i n gi n x c 2 v 1 0 0 0 a b s t r a c t d e v i c eo f x i l 访xv i r t e x i is e r i e ss u c c e s s f m l y t h em a x i m a ls p e e do f i p1 0 0 k u p m o d u l ec a l lr e a c h8 8 m h zi nx s ts ”t h e s i st 0 0 1 t h ed e s i g i lc a nm e e t t h e r e q u i r e m e mo f o c 4 8h i 曲s p e c d d e l i v e rp a c k a g e k c yw o r d s ：t c a m ，t r e eb i 缸n a p ，f p g a ，f o 九v a r de n g i n e 学位论文独创性声明 本人所星交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果。对本文的研究做出露要贡献的个人和集体，均已在 文中作了e 碡确说明并表示谢意。 作者签名 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名 彩硪旌 日期：2 垃：y 倚 p o 备玉 ：l 趔 黝 堋 第一章绪论 第一章绪论 1 1 引言 互联网从8 0 年代发展至今，其规模和数量都今非昔比。对于目前来说，随着 i n t e r n e t 的用户的数目的急剧增长，其数据流量大约每3 个月增长一倍。所以， 为了满足数据流量的增加和网络的熬体性能，必须增加网络带宽提高数据链路速 度是不够的，还要提高路由器的性能。由于光传输技术的出现可以大大提高网络 的带宽，使用波长多路复用( w a v e l e n g t h d i v i s i o nm u lt i p l e x e d ) 技术【l 】就可 以使单根光纤具有3 0 0 个传输通道，而每个通道的速率为1 1 6 g b s 。而提高路由 器的性能可以通过提高路由器的数据交换性能和数据包转发速率来实现。可以使 用交换背板等交换技术将数据包从路由器的输入接口快速传送至输出接口。在文 献【2 】中就提到一个使用m e m s 来实现光纤交换系统，它的交换速率可以达到千兆每 秒。因此，当前提高i n t e r n e t 性能的关键的问题是需要更快的速度转发数据包。 目前，用于主干网络互联的核心路由器的接口速度已经达到了1 0 g b p s 一4 0 gb p s 。 这一速度要求核心路由器每秒能够转发上千万个以上的分组，而分组转发的重要 一步就是查找路由表，路由表构造和查找是路由器数据转发机制中的重要组成部 分。所以，快速的路由查找算法以及优化的路由表结构是实现高速分组转发的关 键也是提高路由器接口速度的要点。 路由查找属于路由前驱引擎( 图卜1 所示) 的一部分。网络接口在接收到数据 包后，通过交换器把数据包发送给前驱引擎。前驱引擎的主要功能是首先对数据 包头进行c r c 交验，然后根据数据包的目的地址进行路由查找，查询出此包下一 图卜1 路由前驱引擎示意图 跳得端口号。在结束路由查找后，就要更新t t l ( t i m et ol i v e ) 域，然后重新计 算c r c 交验域。最后，修改数据包的m a c 地址，通过交换网络把数据包送到正确 的端口号发送出去。 第一章绪论 1 2 路由查找算法的研究现况 嚣麓路邀舞法主要是在无炎壤越路由( e l 氇s s l e s si n t e r d o 璐a i nr o u t i n g ， 简称c i d r ) 【3 叫的地址结构的越础上进行最长前缀匹酉己查找。无类域间路由地址 结竣镬瘸 对采表示爨凌疆。鼹囊查我藏是要壤摇器静遣蛙在鼹 由项中查找出长度最长的路由颁。由于在到达的数据包中的目的地址的域中，并 没有携媾有关此售息，霹以絮麓刿叛鼗嚣的逮疑戆最长篱缀匿裁长度，掰鼓裁无 法使用普通的h a s h 4 1 1 方法或二分查找伫”的方法进行晟长前缀匹配。因此，缀 藤缀查找需要考虑最长匹配鼹由项豹长度积在路出褒孛包含越长度的熊匹寨 数据戗目的地址的路幽项。 羁 l f ，磺究主要有疆个方麟，一方露是改遴已有敬软辞算法，使之疑更快的 实现路由查找。另一方面，是把些软件算法用硬件电路来实现或者使用新的硬 件结构如t c 燃等来实现路由套找。虽然，使用硬件实现来实现没有软传的灵溪， 但是使用硬件来实现路由查找鼹比软件快的多，所以目前主干嗣络上的核心路由 器的路由查找都是由硬传来实现的，蔼一些小的局域刚的路由设各还是通过软传 来实现。 软件实现的路由查找算法只有分为蕊类，一类是以b i n a r yt r i e 结构为基础 的算法i 1 2 3 4 ，1 7 ，1 鄯，这袋算法邋过对b i n a r y 伢i e 结构作了一燕算法时澜和空阐 上的优化来加快高速的路由。其中l u l e a 【1 8 】查找算法通过将第一、二级路由表项 进行压缩，放入c u p 的c a e h e 中实现鬻速的路由查我。但是这魏算法静路由更新 需要较长的时间。还有一类是二分查找算法【2 1 ，2 3 1 ，这类算法属于区间焱找算法， 通过逐步缩，j 、凌我区阐的范豳来实现漆由静豢我，这类算法期硬箨实现院较困 难。 磺 牟实瓒靛路蠹套我方法魂主要势为两类，一类怒把多分支i e 类鍪静髯 法移植到硬件中，如d i r 一2 4 _ 8 b a s i c 路由查找方法【2 5 】就是利用骨干嘲上核心路 由器中翡绝大多数静鼹由蓠缀长凄不怒遘2 4 键戆这个统计特点，实瑗路垂套我 方法，但是这类算法很难应用到下一代i p v 6 网络的路由查找。还有类是通过 善c a m 柬实瑷潞盘查筏，搜瑙下e a 搿来实瑗辫出盎我稳优点麓哭霉要一次嚣豹 地址麒配就可以得到下一跳的端口号，但是使用t c a m 实现路由查找的缺点在 于下e a m 存耱熬路蠹藩缀顼豢按蘸缀长疫蓑 黪，覆置代a 醚燕一耱功耗壤大豹 芯片。所以科研人员为了克服以上t c a m 的缺点提出了多种解决方法【3 6 ” 3 8 1 。 公司路交设善名称系统容爨 接疆 c i s c o1 2 0 0 0g s r 6 0 g b i t sa t m ，s o n e t ，咀奠i 网 2 第一章绪论 l u c e n tp a c k e ts t a r3 2 g b i t s a t m ，s o n e t ，以太网l 【j u n i p e r m 4 04 0 g b i t sa t m ，s o n e t ，以太网l 0 s i c o m g i g a m u x 8 0 g b i t sa t m ，s o n e t ，以太网j 表卜1 交换式路由器产品 1 3 本论文选题意义和研究内容 1 3 1 本论文选题意思 随着因特网的发展，对于主干路由器的性能和功能提出的要求越来越高。数 据包输入处理日益成为主干路由器的瓶颈，而路由查找部分正是造成这种现象的 关键因素，所以如何实现快速路由查找成为了路由器的关键因素。而且，随着网 络技术的发展，网络安全成为一个国家安全的一部分，而路由器又是网络的核心 组成部分。所以，我们必须致力于研究自主版权的互联网主干路由器，而路由查 找功能又是路由器不可或缺的部分。 从目前对i p v 4 的结构来看，今后在地址体系结构以及最长前缀查找机制方面 将不会发生非常大的变化，因此从这个角度来看，完全有理由、也有必要采用速 度快、集成化程度高的硬件集成电路系统来实现路由查表系纠洲。对于路由查 找问题。需要查找速度快、占用空间小、更新速度与查找速度可比的最差情况下 的算法。 本文根据目前软件对于路由查表速度瓶颈的局限性和v l s i 技术的长足发展， 提出研究网络加速器硬件查表系统，属于网络路由器n e t w o r kp r o c e s s o r 关键部 位。这种硬件查表系统是用来执行网络数据包处理和转发过程中对路由表查询的 高速处理器。本文主要根据已有的路由算法，提出合理的硬件结构，来实现快速 的路由查找算法，以提高路由器的交换速度。 1 3 2 本论文的研究内容 本文主要涉及路由查找算法的硬件实现进行了研究和优化，涉及算法的选 择、系统结构的设计、f p g a 的实现和验证等方面。论文的各章内容如下： 第一章绪论，主要阐述路由查找算法的重要性和研究意义。 第二章简单介绍了路由器的构成，以及路由地址的变化。 第三章主要是介绍了各种使用软件来实现的路由查找算法，以及对这些算法的 复杂度进行了比较。 第四章详细地介绍了硬件实现的路由查找算法，特别是对t c a m 的实现进行了具 体的介绍，在本章最后提出了一种r a m 和t c a m 方法实现的路由查找方法，并对其 中的路由存储的结构进行了优化。 第一章绪论 第五章为本文的重点，主要介绍了通过r a m 和t c a m 的方式来实现快速路由查找算 法的设计过程。 第六章对本文设计的f p g a 验证进行了阐述，介绍了x i l i n xv e r t e xi if p g a 的功 能和特点，并说明了。 第七章对整个论文进行了总结和讨论。 4 第二章路由器简介 第二章路由器简介 2 1 互联网的发展历史 互联网( i n t e r n e t ) 是由数千万台计算机和上亿个用户所组成的全球信息资 源的超大型集合体。所有采用t c p i p 协议的计算机都可以加入因特网，实现信息 共享和互相通信。i n t e r n e t 的基础建立于7 0 年代发展起来的计算机网络群之上， 它开始是由美国国防部资助的称为a r p a n e t 的网络，原始的a r p a n e t 早已被扩展和 替换了，现在由其后代i n t e r n e t 所取代。第一个应用i n t e r n e t 类似技术的试验 网络用了四台计算机，建立于1 9 6 9 年。 1 9 8 3 年美国加利福尼亚大学伯克莱分校把t c p i p 软件集成到该校研制的b s d u n i x 中，使计算机的操作系统具有了t c p i p 网络通信功能，不需要其他的设备就 可以使得运行b s d 洲i x 的计算机就可以方便地互连起来，诞生了现在i n t e r n e t ， a r p a n t 成了i n t e r n e t 的骨干网。8 0 年代中期，美国国家科学基金会( n s f ) 意识到 i n t e r n e t 对科学研究的重要性，决定资助i n t e r n e t 的发展和t c p i p 技术，开始建 设使用t c p i p 协议的n s f n e t 。由于美国国家科学资金的资助和鼓励，很多大学、 政府科研机构甚至私营的科研机构都纷纷将自己的局域网并入n s f n e t 网，最终 n s f n e t 取代了a r p a n t 成为i n t e r n e t 骨干网。 随着包括中国在内的世界计算机网络规模的不断扩大，基于t c p i p 协议的 i n t e r n e t 已经成为全世界最大的计算机互连网。而t c p i p 协议也因此成为事实上 的工业标准，i p 网络正逐步成为当代乃至未来计算机网络的主流。随着这种互联 网的迅猛发展，路由技术在网络技术中已经逐渐成为关键部分，路由器也随之成 为最重要的网络设备。用户对网络信息多样性需求推动着路由技术的发展和路由 器的普及，人们已经不满足于仅在本地网络上共享信息，而希望最大限度地利用 全球各个地区、各种类型的网络资源。而在目前的情况下，任何一个有一定规模 的计算机网络( 如企业网、校园网、办公大厦等) ，无论采用的是快速以大网技术、 f d d i 技术，还是a t m 技术，都离不开路由器，否则就无法正常运作和管理。而路 由器作为i n t e r n e t 通信网络的核心，其地位的作用十分重要，它的性能直接影响 到整个网络的整体性能，因此在整个i n t e r n e t 领域中，路由器技术始终处于核心 地位，其发展历程和方向，成为整个i n t e r n e t 网络研究的缩影，是一个国家信息 领域的技术水平高低的重要标志。 2 2i n t e r n e t 地址结构及其发展 为了使的互联网上的计算机能够共享信息和资料，就必须给每台上网的计算 机一个唯一的标识符，而这个标识符就相当于这台计算机的地址。随着，连到 第二章路由器简介 i n t e r n e t 上计算机的数艟不断增加，其地址结构发生了3 次较大的变化。 2 2 1 藻于分类的地址结构 l p v 遂垃爱盘霾令8 谴楚二遽裁数字壤缀或，慈长发为令字节弱3 2 经二避锻 数( 理论上可组成4 ，2 9 4 ，9 6 7 ，2 9 6 个不同的i p 地址，约4 2 亿多，实际上却少得 多) 。自熟，l1 0 0 0 0 0 0 一l o l o l 0 0 e 0 0 0 0 0 0 0 l e l o 0 0 0 l o 表了敷羹1 9 2 。1 6 8 。l 。6 6 。 在i n t e r n e t 建立时，对i p 地址的管理采用了种简单的地址结构，基于分类的地 蛙结构。这砖分类方法蹶鸯i p v 4 遗娃分为5 类。为攀搔地蛙设计瓣a 、8 、e 类， 为组播地址设计的d 类以及为以后使用渐保留的e 类地址( 图2 一1 ) 。 o o - 0 o1 2 8o 0 - o1 9 2 0 0 - o2 2 4 o o - o2 4 0 o 0 0 2 5 5 2 5 5 2 5 5 2 5 s c l a 8 s ac l a s sbc l 锚s cc l a s s dc l 鼬s e 图2 1i p v 4 网络地纰分类 每类懿避城毒秀秘努组成，第一部努受网终谖别号，第二粼势震采耩苯该溺 络上的主机。使用这种方法来标识网络地址，如果用来标示网络识别号豹比特使 越多，则该网终瘊能骞绫弱主撬裁越少，反之亦然。媳篷2 一l 艨示，矗类遮址懿 最高位为o ，接下来的7 做标示网络识别母，剩余的2 4 位二进制使用来标永主机号， a 类地缝鼹于主搬数目非常多鹣网终。a 类遗址允许1 2 8 个网终，每个网络大约 千七百万台主帆。b 类地址的最高位为1 0 ，接下来的1 4 位完成网络识别号，剩余 款1 6 位二进制能代表主极，b 类地址用于中型瓢大型的网络。b 类地址允许1 6 3 鼹 个网络，每个嘲络大约6 5 0 0 0 台主机。c 类地址的最高傲为1 1 0 ，接下来的2 l 位完 成网络识别号，剩余的8 位二逃制位代表主极，c 类地址用于小越本地嬲络。c 类 地址允许大约二酉万个网络，每个网络有2 5 4 台主机。d 类地址的最高位为l n o 。 剩余的位标示客户枫参加的特定组。d 类地址用于多援。一个多播地址w 能包括l 台或更多主机，或根本没有。裰多播揉作中没翁弼络或主机位，数据包将传送翔 网络中选定的主机子集中。只囊注册了多播地址的主机才能接收到数据包【，j 。 基予分类的地址结构降低了路由查找的复杂程度，图2 2 就是一种蒸于分类 地址结构的路幽查找的方法【引。整个路由转发表可以分成3 个部分，每部分转发 表可以分莉保存酾是a 粪、8 类潋及e 类魏整的潮络遗址帮分，邋些途鬣的长疫都 是相等的，因此路由表态找问题实际上就成了搬每张转发表中的关键字精确查找 阍蘧。查找过耩可疆表述如下：首先毒精静遗熬瀚蘸凡个经褥到静该遗疆蕊耩髓 基类别，然后根据得到的基类别提取出目的地址的网络地址部分，从而去查找栩 第二章潞虫器筵奔 应的h a 8 h 散列表，最后查找到的结构就是正确的转发路出。 r u l w 弧u u i gi a d l c | d e 鲢由械酶na d d 糟8 s 。一 ，一、 一一h 黔h 一一 一； 一、。 fd 酏材撖1 c i a s s a ：“ a d 出雠s ：一： 、 【 c i 黼8 j 伍j 厂一、 、一 n e 埘广 i 、 叫r 一一 v 一 ：i ic l a s s bf 一_ n e x t h o p a d d f e s s 銎2 2 蘩于分类建整结穆熬蘧凌查找示意鍪 在i n t e r n e t 剐组建的时候，分类瑭址结构褥到广泛的应用。组怒，随着网络 的日懿扩大，就产生了二个问题。第一个问题燧，路由表的规模黛的越来越大。 由于c 畿网络用2 4 个比特来标示网络识别号，可以包括约二百万个网络。所以， 随着c 类蹲络的不断增加，鼹由表的规模将无法肖效的控制。第二个问题是，地 蛙分熬翁不灵活嚣造戏懿筑疆空阙懿大量渡爨。鼹予一令矗粪网终可黻容续运二 千万台的差机，其每个地蛙空阐不可能都被分配了。所以，基予以上二个闽题藏 提出了一种新的网络地址结构。 2 。2 。2 觅类别域问路由结构 麓了海缳路壶表豹魏摸熬壤长速度爨及糖凑建蛙空闼斡裂鬻攀， 骚f ( 1 h e i n t e r n e te n g i n e e r i n gt a s kf o r e e ) 提出了一种称为无类域闯路巍( c l a s s i e s s i n t e r d o m a i nr o u t i n g ，简称c i d r ) 的地址结构i ”j 。无类别域间路幽选择，有时 又称之为超网( s u p e r n e t w o r k ) ，是互联网中一种新的地址方式，与传统的a 类、 b 类和c 类寻址模式相比，c i d r 在i p 地址分配和利用方面更为离散。而且，有 效豹降低了主子路由器懿鼹蠢表魏援模。e i d r 攒蹇了媾绞上基于分类豹遗蛙分醚 方式，照定可以使廷任意妖发豹弼络速垃部分，隧忿产生了疆由蟪蟪藩缀的概念。 每个i p 地址都有网络前缀，它标识了网络的总数或单独一个网络，这个前缀也被 指定为i p 地址的一部分，而闰还因为需要不同，遗个地址的长短也会有所不同( 这 一点不同于过去的i p 地址分配方法) 。 7 第二章路由器简介 在分类地址结构中对映a 类、b 类和c 类地址的前缀长度分别为8 位、1 6 位、 2 4 位。无类别域间选路结构可以使用任意长度的位前缀长度，而不是只限于8 位、 1 6 位、2 4 位的地址前缀长度。使用c i d r 的地址结构使i n t e r n e t 成为一个层次行的 拓扑结构。从而使得路由器上维护的路由表的信息不再是网络级的，而是任何网 络的聚集。所以，c i d r 的好处是明显的，它提高了地址空间的利用率。例如为3 0 0 台主机分配网络地址只需使用一个2 3 位网络地址前缀长度的网络地址( 可以支持 5 1 2 台主机) 就可以满足要求，而无需将此网络设置一个b 类网络，从而大大节约 了t p 地址。 为了理解这个c i d r 是如何工作的，让我们考虑以下的从2 0 8 1 2 1 6 2 4 到 2 0 8 1 2 3 1 2 4 的1 6 个c 类网络。并假设以上1 6 个c 类网络可以通过同一个路由服务 提供者来实现数据传输。我们可以看到这1 6 个网络地址的前2 0 个比特位是相同的 ( 1 10 1 0 0 0 00 0 0 0 1 1 0 0o 0 0 1 ) 。因此，我们可以把这1 6 个网络聚为一个使用2 0 个比 特前缀的超网，这个超网可以用十进制表示为2 0 8 1 2 1 6 2 0 ( 图2 3 ) 。 2 0 81 21 6 ，2 42 0 81 22 1 ，2 4 2 0 81 23 l ，2 4 。一ii ii 斗_ + 。ii ! 卜_ 一一 0 t o t a l i p v 4a d d r e s ss p a c e 2 ”1 2 0 81 21 6 ，2 411 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 2 0 81 22 1 ，2 41 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 l + 2 0 81 23 1 ，2 41 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 + 2 0 81 21 6 ，2 0l1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 + i pa d d r c s sa 鹤r e g a t i o n 图2 3 网络地址聚集示意图 当路由器向这1 6 个c 类网络广播地址时，改而只要广播带有2 0 8 1 2 1 6 2 0 网 络f j 缀的地址，从而大大缩减了路由器的路由表大小。这办法可行的前提是地址 是连续的，不然，就不可能设计出包含所需地址、但排除不需要地址的前缀。然 j | ，当这1 6 网络中的其中一个网络( 例如2 0 8 1 2 2 1 2 4 ) 改变了路由服务提供 者束实现数据传输。这样一来我们就不能用前面的方法把这1 6 个网络集聚起来， 不得不在路由器的路有表中保存这1 6 个网络的路由信息。对于这种情况的一种解 决方法就是为着1 6 个网络设置2 条路由信息，一条是2 0 8 1 2 1 6 2 0 ，另一条是 第二章路由器简升 2 0 8 1 2 2 1 2 4 。使用这种方法时，由于路由前缀的交迭，有些网络就会在路由表 有多个匹配项。所以，当这种情况发生时就要找出最匹配的路由前缀，这就是最 长路由前缀匹配。总之，在路由器中的路有查询就是在路由表中找出匹配数据包 的目的地址的最长前缀的项。对于上面的这个例子，当目的地址是2 0 8 1 2 2 1 x x x 时候，最匹配的项就是2 0 8 1 2 2 l 2 4 路由项，而对于其他1 5 个网络其最匹配的项 就是2 0 8 1 2 1 6 2 0 。 2 2 3i p v 6 地址结构 i p v 6 被称作下一代互联网协议，它是由i e t f 设计的用来替代现行的i p v 4 协议 的一种新的i p 协议。与i p v 4 的3 2 地址相比，i p v 6 的地址要长的多，i p v 6 共有1 2 8 位地址，i p v 6 的提出从根本上解决了网络规模的不断增加的趋势。相应的，i p v 6 在地址空间分配上也进行了相应的改变【9 l 。虽然，i p v 6 在结构和空间上有很大的 变化。但是，其地址空间仍然是层次结构。所以，其路由查找方法和i p v 4 的路有 查找方法没有本质的区别，还是基于c i d r 地址结构的网络聚集。 2 3i n t e r n e t 协议的层次结构 网络协议通常分不同层次进行开发，每一层分别负责不同的通信功能。在目 前，诸多网络互连协议中t c p i p ( t r a n s m i s s i o nc o n t r 0 1p r o t o c o l i n t e r n e t p r o t o c 0 1 ) 协议是一个使用非常普遍的网络互连标准协议。t c p i p 协议，是一组 不同层次上的多个协议的组合。目前，由于众多的网络产品厂家都支持t c p i p 协议，t c p i p 已成为一个事实上的工业标准。t c p i p 通常被认为是一个四层协议 系统【”】，如图2 4 所示。 应用层 运输层 网络层 链路层 t e l n e t 、f t p 和e m a i l 等 t c p 和u d p i p 、i c m p 和i g m p 设备驱动程序及接口卡 图2 4t c p i p 协议族的四个层次 每一层负责不同的功能： ( 1 ) 链路层，有时也称作数据链路层或网络接口层，通常包括操作系统中的设备 驱动程序和计算机中对应的网络接口卡。它们一起处理与电缆( 或其他任何传输 媒介) 的物理接口细节。 ( 2 ) 网络层，有时也称作互联网层，处理分组在网络中的活动，例如分组的选路。 第二章路由器简介 在t c p i p 协议族中，网络层协议包括i p 协议( 网际协议) ，i c m p 协议( i n t e r n e t 互联网控制报文协议) ，以及i g m p 协议( i n t e r n e t 组管理协议) 。 ( 3 ) 运输层主要为两台主机上的应用程序提供端到端的通信。在t c p i p 协议族中， 有两个互不相同的传输协议：t c p ( 传输控制协议) 和u d p ( 用户数据报协议) 。 t c p 为两台主机提供高可靠性的数据通信。它所做的工作包括把应用程序交给它 的数据分成合适的小块交给下面的网络层，确认接收到的分组，设置发送最后确 认分组的超时时钟等。由于运输层提供了高可靠性的端到端的通信，因此应用层 可以忽略所有这些细节。而另一方面，u d p 则为应用层提供一种非常简单的服务。 它只是把称作数据报的分组从一台主机发送到另一台主机，但并不保证该数据报 能到达另一端。任何必需的可靠性必须由应用层来提供。这两种运输层协议分别 在不同的应用程序中有不同的用途。 ( 4 ) 应用层负责处理特定的应用程序细节。几乎各种不同的t c p i p 实现都会提供 t e l n e t 远程登录、f t p 文件传输协议、s m t p 简单邮件传送协议、s n m p 简单网络管 理协议。 2 4 路由器的结构 因特网出现之初的路由器通常由一台拥有多个网络接口的工作站，运行相应 的协议软件完成报文转发功能。随着因特网的蓬勃发展，人们对路由器的性能提 出了越来越高的要求，导致路由器在结构上发生了多次变化。路由器结构广义上 可以被分为两类：集中式路由器结构 图2 5 a 和分布式路由器结构 图2 5 b 。集 中式路由器结构是由连接在交换器上的若干网络接口、前驱引擎和路由控制器 ( r o u t ec o n t r o l l e r ) 以及管理控制器( m a n a g e m e mc o n 乜0 l l e r ) 组成。 匪訇 c o n t r o i l c r 臣童哥一_ 墨 莹篡睦l ! ! ! ! ! ! i f a b d 。i 二二= ：卜 陌五妇 c 廿0 1 1 e r ( a )( b ) 图2 5 集中式和分布式路由器结构示意图 分布式路由器结构和集中式路由器结构的主要的区别就是把路由查找引擎 集成到了网络接口中去了。当前，高端的路由器都是采用分布式结构。路由表的 1 0 篷 一 摹习 第二章路由器简介 生成和维护都是由路由控制器完成。 一个典型的路由器结构如图2 6 所示，网络接口包括了从物理层到路由层甚 至传输层的数据处理，它是路由器数据的进出口。但是随着更新的应用程序和协 议的发展，网络接口的功能将更加复杂。随着，网络数据流量的日益增大，网络 接口对外必须要支持全双工网络连接，对内连接交换网络则要达到o c 一4 8 ( 2 5 g b p s ) 的标准。网络接口为了提供高效的数据传输，通常由以下几个功能模 块组成： ( 1 ) 收发模块主要完成光一电、电一光转换以及串并、并串转换。 ( 2 ) 帧模块主要完成物理层的数据包的打包。 ( 3 ) 网络处理模块主要实现路由表的查找和数据包的分类和修改。 ( 4 ) 流量管理模块主要提供数据流的控制功能。 ( 5 ) 中央处理模块提供路由表的更新、寄存器、缓存等的管理。 图2 6 典型的路由器结构示意图 2 5 路由器发展的趋势 传统上路由器工作于i p 协议层，其主要任务是接收来自一个网络接口的数据 包，根据其中所含的目的地址，决定转发到哪一个下一个目的地( 可能是路山器 也可能就是最终目的点) ，并决定从哪个网络接口转发出去。这是路由器最基本 功能数据包转发功能。为了维护和使用路由器，路由器还需要有配置或者控 制功能。 但是，随着互联网的普及以及语音电话、实时视频等新应用的出现，传统路 第二章路由器简介 h 器的功能无法满足互联网的变化。所以，路由器发展的趋势将朝以下几个方面 发展。 ( 1 ) 业务高性能高性能不仅仅是转发的高性能，而应该包括业务的高性能、高品 质的服务，路由器应该在处理各种业务时游刃有余，同时转发性能也不会出 现明显下降。 ( 2 ) 集成化为了灵活应对多样化的业务环境，新一代路由器需要支持全面的i p 业务能力并进行了优化设计，包括完善的路由、m p l s 、v p n 、组播、语音、安 全、q o s 、i p v 6 、宽带接入等，各种业务流程融合无间。同时，为满足集成一 体化组网的需求，路由器还需要融合防火墙、入侵防御、v p n 网关、语音网关、 宽带接入、以太网交换机、无线网关等设备的功能。 ( 3 ) 业务智能化新一代路由器需要更加智能化，具备更加灵活的业务感知和处理 能力，如：业务部署的灵活性、业务感知的灵活性等。 ( 4 ) 高可靠因此无论是在电信、大型行业还是企业应用环境，新代路由器都需 要具备更高的可靠性。 ( 5 ) 高安全网络安全问题不可能通过某种一劳永逸的技术来解决，而是随着安全 状态的变化，综合考虑时间、空间、网络层次的因素，不断调整安全策略。 因此路由器作为基础网络设施，首先应该保证硬件体系结构及网络操作系统 层次的安全，同时应具备全面的安全特性并能够灵活调整。 ( 6 ) 易使用随着网络不断向行业、企业甚至家庭环境延伸，需要路由器考虑更多 的人性化设计，屏蔽复杂的技术细节，使路由器真正平民化。 2 6 本章小结 本章主要介绍了互联网地址变化以及由此对路由查找的影响，然后对现在使 用的路由器的结构作了一些介绍，最后简单论述了路由器的发展趋势。 第三章软件路由查找算法 第三章软件路由查找算法 报文转发是路由器需要完成的最主要的功能之一，即将到达路由器输入端口 的报文转发到正确的输出端口，为此，在路由器中通常需要维护一个转发表，浚 转发表通过各种路由协议维护，转发表中包含了不同目的i p 地址对应的下一跳输 出端口。报文到达后，以报文的目的i p 地址作为索引，查找转发表，得到报文对 应的下一跳输出端