（通信与信息系统专业论文）基于路由查找算法的研究与硬件实现.pdf

摘要 摘要 近年来，随着i n t c r n c t 的迅猛发展和人们对网络应用的各种需求，现有网络带宽的容量逐渐受 到日益严重的挑战。由于用于主干网络互联的核心路由器的接口速率已经达到了几十个g b p s ，这一 速率要求核心路由器每秒能够转发几百万乃至上千万个数据包文。 随着光通信技术的发展，现有的物理介质能够保证有足够的传输速度和传输质量满足网络流量 的要求，但另一方面，网络结点的包处理转发能力却没有跟上物理层传输速度的步伐。因此，网络 结点的较低的数据包处理转发能力成为了一个很重要的需要克服的瓶颈。在网络结点对数据包的处 理过程中，最主要的制约整个处理转发速度的步骤就是路由查找。因为基于软件实现的路由查找算 法无法满足更快的网络要求，所以本论文的重点就是对路由查找算法进行研究、完成基于硬件实现 的查找结构并进行实现。 本文对现有的软件路由查找算法进行了归纳和总结，重点分析了各种算法查找速度，存储空间， 更新复杂度等方面的优缺点。并介绍了c a m 和t c a m 器件在路由查找方面的应用 精确匹配是路由查找中的重要内容，其查找速度的快慢，关系到网络结点对数据链路层报文查 找的速度。对于精确匹配，本文对基于h a s h 的路由查找的性能进行了分析，实现了采用多重h a s h 进行查找的硬件结构，并对双重h a s h 的路由查找算法进行了硬件实现，所实现的硬件结构具有自 学习功能，最后对所实现的硬件程序进了仿真。 最大长度匹配是路由查找中的另一个重要内容。也是制约网络层数据包转发速度的主要因素。 对于最大长度匹配，本文采取了并行结构和变步长多分支压缩树相结合的算法，对算法性能进行了 分析，井对所设计的硬件结构进行了硬件实现和仿真。最后将程序下载到x i n l i n x 公司的v r t e x - 系列f p g a 器件中，搭建相应的测试平台，对查找性能进行了验证。 ， 关键词：路由查找、精确匹配、最大长度匹配、h a s h 算法、并行结构、变长多分支压缩树 东南大学硕士论文 a b s t r a c t n o w d a y s w i t ht h er a p i dd e v e l o p m e n to fi m e m e ta n dp e o p l e sa l lk i n d so fr e q u i r e m e n tf o rn e t w o r k , t h ee x i s t i n gn e t w o r kb a n d w i d t hi sb e i n gc h a l l e n g e d ，f o rc o r er o u t e r sw h i c ha r eu s e di nb a c k b o n en e t w o r k a l r e a d yh a v ea b o u ts e v e r a lg b p si n t e r f a c ev e l o c i t y , t h e ys h o u l dh a v et h ec a p a c i t yo fd e a l i n gw i t hm i l l i o n s o fd a t ap a c k e t w i t ht h ei m p r o v e m e n to ff i b e rt e c h n o l o g y , t h ee x i s t i n gp h y s i c a lm e d i u mh a se n o u g ht r a n s m i t i n g s p e p x ia n dt r a n s m i t i n gq u a l i t yt ok e e pu pw i t ht h en e t w o r kb a n d w i d t h sr e q u i r e m e n t o nt h eo t h e rh a n d ，t h e a b i l i t yo f n e t w o r kn o d ed e a l i n gw i t ht h ed a t ap a c k e ti sb e h i n d s o ，i tb e c o m e st h eb o t t l e n e c ko f e n h a n c i n g t h en e t w o r kb a n d w i d t h w h e nt h en e t w o r kn o d ed e a l sw i t hd a t ap a c k e b ，t h em a i nr e a s o no fr e s t r i c t i n gt h e s p e e di st h er o u t el o o k u p b e c a u s et h es o f t w a r e - b a s e dr o u t i n ga l g o r i t h mc a n tm c e tl a r g e rn e t w o r k b a n d w i d t h ，t h i st h e s i sw i l lf o c u so nh a r d w a r e - b a s e dr o u t i n ga l g o r i t h ma n di t sr e a l i z a t i o n t h i st h e s i sw i l lc o n c l u dt h e e x i s t i n gs o f t w a r e - b a s e dr o u t i n ga l g o r i t h m s ，a n a l y z et h ea l g o r i t h m s s e a r c h i n gs p e e d ，s t o r a g er e q u i r e m e n ta n dc o m p l i c a t i o no fu p a a t e a l s ot h i st h e s i sw i l li n t r o d u c et h ec a m a n dt c a m sa p p l i c a t i o ni nr o u t el o o k u p t h ee x a c t - p r e f i xm a t c h i n gi sa ni m p o r t a n tc o n t e n to fr o u t el o o k u p ，f o ri t ss e a r c h i n gs p e e di sr e l a t e d w i t ht h en e t w o r kn o d e sd e a l i n gw i t hd a t ap a c k e to fl a y e r2 t h i st h e s i sw i l lr e s e a r c ho nh a s h - b a s e d r o u t i n ga l g o r i t h m , a n dc o m p l e t et h eh a r d w a r ea r c h i t e c t u r eo fm u l t i p l eh a s ha l g o r i t h m t h er e a l i z a t i o no f t h em u l t i p l eh a s ha l t o r i t h mh a st h ea b i l i t yo fs e l fl e a r n i n g a n dt h ev e r i l o gh d l p r o g r a m si ss i m u l a t e d t h el o n g e s t - p r e f i xm a t c h i n gi st h eo t h e ri m p o r t a n tc o n t e n to f r o u t el o o k u p ，a n da l s oi st h em a i nf a c t o r o fd e a l i n gw i t ht h ed a t ap a c k e to fl a y e r3 a b o u tt h el o n g e s tp r e f i xm a t c h i n g ，t h i st h e s i sw i l lu s ep a r a l l e l a r c h i t e c t u r ea n dv a r i a b l e - s t r i d ea n dp a t hc o m p r e s s i o na l g o r i t h m , a n a l y z ea n dc o m p l e t et h eh a r d w a r e a r c h i t e c t u r ea n dr e a l i z a t i o n a tt h el a s t ，t h ep r o g r a mw i l lb ed o w n l o a d e di n t ot h ev i r t e x 一1 if p g ao fx i n l i n x c o r p ，t h et e s t i n gp l a t f o r mw i l lb ec o n s t r u c t e da n dt h ep e r f o r m a n c eo fr o u t i n ga l g o r i t h mw i l lb ev e r i f i e d k e yw o r d s ：r o u t el o o k u p ，e x a c t - p r e f i xm a t c h i n g ，l o n g e s t - p r e f i xm a t c h i n g ，h a s ha l g o r i t h m , p a r e l l e l a r c h i t e c t u r e ，v a r i a b l e - s t r i d ea n dp a t hc o m p r e s s i o na l g o r i t h m 插图目录 插图目录 图1 - 1 路由器体系架构图3 图2 1 二进制t r i e 表示图l l 图2 - 2 路径压缩t r i e 及结点数据结构1 2 图2 - 32 分支t r i e 结点数据结构1 3 图2 42 分支t r i e 结构图1 3 图2 5 基于前缀长度的路由查找1 5 图2 石基于t c a m 的路由查找结构1 8 图3 - 1 数据报文的解析流程2 l 图3 - 2i e e e8 0 2 3 x 数据报文格式2 2 图3 3 单重h a s h 算法查找总体硬件结构图2 5 图3 4 多重表项结构图2 8 图3 5 双重h a s h 查找硬件结构图。2 9 图3 - 6 双重h a s h 具体硬件实现图3 0 图3 - 7m a ck e yc o n i r o l 模块具体硬件实现图。3 1 图3 8m a c m e mc o n t r o l 模块具体硬件实现图3 2 图3 - 9 仿真波形图之一3 2 圈3 1 0 仿真波形图之二3 3 图4 1m v 4 地址分布规律3 6 图4 2d 瓜2 4 8 b a s i c 算法硬件结构图3 6 图4 - 3t b l 表项格式3 7 图4 4d i r 一2 4 8 矾t 算法硬件结构图3 7 图4 5d 皿- 2 1 3 算法的硬件结构图3 8 图4 石m v 4 报头和坤v 6 报头的比较3 8 图4 7 通过h a s h 分类的并行查找结构4 0 图4 8 通过i p 地址比特位分类的并行查找结构4 l 图4 9 并行查找结构排队论模型4 2 图4 - 1 0 等待时间期望e ( w ) 与平均服务率p 的关系4 3 图4 - 1 1 前缀结点的二进制t r i e 树结构4 4 图4 - 1 2 子树划分图4 4 图4 - 1 3 路径压缩子树部分, 1 5 图4 - 1 4 变长多分支压缩树整体结构图4 5 图4 - 1 5 子树信息存放示意图4 6 图4 - 1 6 并行变步长多分支压缩树路由查找整体硬件结构图4 7 图4 - 1 7 查找单元硬件结构图4 7 图4 - 1 8 输出控制单元硬件结构图4 8 图4 1 9 仿真波形图1 一4 8 图4 - 2 0 仿真波形图2 4 8 图5 1f p g a 设计流程5 2 图5 - 2v i r t e x i i 系列f p g a 结构图5 4 图5 - 3 性能测试平台系统结构图5 6 v 表格目录 表格目录 表1 - 1m v 4 地址范围分类4 表2 - 1 常见路由查找算法的性能比较1 9 表4 1m 地址分布柏 表5 一l 基于双重h a s h 的精确匹配路由查找模块的综合结果。5 5 v i l 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 p | ib 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 期：歹丛：! ：1 2 第一章绪论 1 1 引言 第一章绪论 近年来，随着i n t e r n e t 的迅猛发展，使_ h ji n t e m e t 的人数、连接到i n t e m e t 上的主机数量都迅 速地增长，各种新的多媒体业务也不断被应用。随着人们对网络应用的各种需求逐渐增加，现有的 网络带宽容量逐渐受到日益严重的挑战，为了适应i n t c m e t 的迅速发展，提供更好的网络服务，必 须提高网络带宽的容量。 i n t e r a c t 由相互连接在一起的路由器网络构成其主要组成部分。目前i n t e m e t 上的结点间主要 使用m 协议进行通讯，而路由器的核心功能是在路由表中为从不同链路接收到的口报文寻找最佳路 由，并按照最佳路由所指定的路径将报文转发到下一台路由器，如此不断重复该过程，直到报文最 终到达其目的地。为m 报文在路由器等网络结点上的路由表中查找最佳路由的算法，称为m 路由查 找算法。因此如何提高路由器的包处理转发能力，从而提高整个网络的带宽和容量，逐渐成为大家 比较关心的问题。 近几年来随着光通信技术的发展，现有的物理介质能够保证有足够的传输速度和传输质量满足 网络流量的要求，但另一方面，路由器的包处理转发能力却没有跟上物理层传输速度的步伐。因此， 路由器的较低的包处理转发能力成为了一个很重要的需要克服的瓶颈。在路由器对报文的转发过程 中，最耗时的是根据疋分组的目标地址域查找下一跳路由，即路由表查找。因此。设计高速路由查 找算法是实现高速分组转发的关键。 为了满足包处理转发过程中的查表需要，人们提出了一些路由查找算法来满足快速查找的需要。 由于网络需求对查表速度的要求越来越高，所以原有的一些基于软件的实现方法在中高端路由器中 已变的越来越不现实，因为软件的执行速度决定了它不可能达到骨干网所需要的高速网络要求。所 以一些基于硬件实现特别是基于a s i c ( 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 ) 设计的路由查找实现方 法几乎成为解决问题的唯一出路。 1 2 路由器简介 1 2 1 路由器在网络中的作用 顾名思义，路由器的一个主要作用是选择传输信息的路线。选择通畅快捷的近路，能大大提高 信息传输的速度，减轻网络系统的通信负荷，节约网络系统的资源，提高网络系统利用率，从而让 网络有更高的带宽和效率。 对于i n t e r n e t 网络而言，整个网络由许多子网络构成，各个子网络又由许多主机组成。子网内 部的主机通信，由链路协议直接进行，子网之间的主机通信，要通过路由器来完成。路由器是多个 子网的成员，它是互联网的主要结点设备在它的内部有一张表示网络号与下一跳端1 2 1 对应关系的 l 东南大学硕士学位论文 路由表。通信起点主机发出i p 包被路由器接收后，路由器查路由表确定下一跳输出端口，发给下 一台路由器，这台路由器又转发给另外一台路由器，用这样- - # h 接着一跳的方式，直到通信终点的 另一台主机收到这个口包。 按照t c p i p 模型，舻协议把网络划分为物理层、数据链路层、网络层、传输层及应用层五个 层次l ”。处理物理层的设备为集线器，处理链路层的设备为数据链路层的以太交换机，路由器处于 模型的网络层，是在网络层转发数据的设备。路由器高度的智能化，对各种路由协议、网络协议和 网络接口的广泛支持，还有其独具的安全性和访问控制等功能和特点是网络层数据传输非常需要的。 路由器的中低端产品可以用于连接骨干网设备和小规模端点的接入，高端产品可以用于骨干网之间 的互联以及骨干网与互联网的连接。特别是对予骨干网的互联和骨干网与互联网的互联互通，不但 技术复杂，涉及通信协议，路由协议和众多接口，信息传输速度要求高，而且对网络安全性的要求 也比其他场合高得多。因此采用高端路由器作为互联设备，有着其它互联设备不可比拟的优势。 从过滤网络流量的角度来看，路由器的作用与交换机和两桥非常相似。但是与工作在物理层上 的交换机不同，路由器使用专门的软件协议从逻辑上对整个网络进行划分。例如，一台支持口协议 的路由器可以把网络划分成多个子网段，只有指向特殊i p 地址的数据包才可以通过路由器。对于每 一个接收到的数据包，路由器都会重新计算其校验值，并写入新的物理地址。因此，使用路由器转 发和过滤数据的速度往往要比只查看数据包物理地址的交换机慢。但是，对于那些结构复杂的网络， 使用路由器可以提高网络的整体效率。路由器的另外一个明显优势就是可以自动过滤网络广播。从 总体上说，在网络中添加路由器的鹅个安装过程要比即插即刚的交换机复杂很多。 然而，近年来，随着人规模集成电路技术的迅速发展，一些基于a s i c 实现的路由器很方便的 逐渐集成了数据链路层的交换机功能，这就是所谓的3 层交换机。对于3 层交换机来讲，它既具有数 据链路层的交换功能，又具有网络层的路由功能，这样在些既需要交换又需要路由的场合，它都 可以很好的工作，替代了传统的一个独立的路由器加一个独立的交换机的模式，从而可以减少研发、 生产、维护等多方面的开销。为了实现3 层交换机的转发功能，需要在路由查找中既完成地址的查 找，又完成m a c 地址的查找，所以本文将在这两方面的查找上都分别进行研究，并进行基于f p g a 的硬件实现。 1 2 2 路由器的工作原理 路由器工作在网络层，负责在各个子网间转发数据，路由器的内部可以划分为上层控制和数据 通道。在上层控制中，路由器通过路由协议交换网络中各种不同协议之间的拓扑结构信息，依照拓 扑结构动态生成路由表。在数据通道上，转发引擎从输入线路接收m 包后，分析并修改包头。使用 路由表查找输出端口，把数据交换到输出线路上。对数据报文的主要转发流程包括线路输入、包头 分析、数据存储、包头修改、队列管理雨j 线路输出。 路由协议根据网络拓扑结构动态生成路由表。职协议把整个网络划分为管理区域，这些管理区 域称为自治域，自治域区号实行全网统一管理。这样，路由协议就有域内协议和域间协议之分。域 内路由协议。如o s p f 、i s - i s ，在路由器间交换管理域内代表网络拓扑结构的链路状态，根据链路 2 第一章绪论 状态推导出路由表。域问路由协议相邻结点交换数据，不能使用多播方式，只能采用指定的点到点 连接。 1 2 3 路由器的体系架构 图1 - 1 是一般路由器的体系架构图。主要由以下几部分组成：路由查找单元、包头更新、路由 表、队列管理单元、数据包存储单元等。一个数据包到来以后，数据包先存储到数据包存储单元， 包头信息经过一定的分析处理后进入路由查找单元进行查找，然后进行包头的替换，然后队列管理 单元根据包的优先级进行队列管理，最后包头取得各自的数据包后结合路由查找单元的查找结果 到达目的端口其中，对路由表的查找，构成了路由器转发数据包过程中晟主要的部分。由于每个 通过路由器并需要其转发的数据包都要对路由表进行查找，所以路由表的查找效率如何往往决定了 整个路由器的性能。 在路由器对数据包的转发过程中。为适应不同的线路速度，不同的系统容量，采用了不同的路 由查找技术。路由器的结构体系正式根据路由查找算法的实现机理来区分。简单而言，可以分为软 件转发路由器和硬件转发路由器。软件转发路由器使用c p u 软件技术实现路由查找，根据使用c p u 的数目。进一步区分为单c p u 的集中式和多c p u 的分布式。硬件转发路由器使用a s i c 或网络处 理器硬件技术完成路由查找，若使用网络处理器进行路由查找，则可进一步细分为单网络处理器的 集中式、多网络处理器的负荷分担并行式和中心交换分布式 1 3 路由查找现状 图1 1 路由器体系架构图 在i n t e m e t 的发展初期，i p v 4 地址采用的是基于类的地址结构口l 。整个i p 地址空间一共分为5 类： 为单播地址设计的a ，b c 类；为组播地址设计的d 类；为今后使用而保留的e 类地址，各个类之间由 地址的前几个比特位来区分，如表1 - 1 所示。基于类的地址结构在i n t e r n e t 发展的初期，由于其结 构的简单性而得到了广泛的应用。但是，随着网络的不断发展，使用这种地址结构产生了两个问题。一 个问题是地址分配的不灵活导致了地址空间的大量消耗以及路由表规模的不断增大。由于基于类的 地址结构将整个地址空间简单地分成了5 个类别，这就导致了地址的分配非常不灵活。另一个问题是， 由于路由器需要记录所有已经分配的网络地址，特别是对于c 类地址来说，由于它的地址前缀特别多， 3 东南大学硕士学位论文 如果记录所有的c 类地址，那么路由表的规模将变得非常大。 表1 - 1i p v 4 地址范围分类 类最高( 几) 位网络号主机号地址范围 ao1 7 b i t8 3 1 b i t0 o 0 0 - 1 2 7 2 5 5 2 5 5 2 5 5 b1 02 1 5 b i t1 6 3 l b i t1 2 8 0 0 0 - 1 9 1 2 5 5 2 5 5 2 5 5 cl l o3 2 3 b “2 乒3 1 b i t1 9 2 0 0 0 - 2 2 3 2 5 5 2 5 5 2 5 5 d ( 组播) 1 1 1 02 2 4 o o o - 2 3 9 2 5 5 2 5 5 ，2 5 5 e ( 保留)1 1 1 1 0 2 4 0 o o 0 - 2 5 5 2 5 5 2 5 5 2 5 5 路由查找就是为了查得与i p 地址相匹配的信息，这就需要查找路由表。为了提高查表效率，得 到最理想的路由查找方法，人们做了许多尝试和研究。根据其发展历程，最先是线性查找算法。线 性表的结构是最简单的查找数据结构，此方法是把所有的路由地址前缀用线性连标的方式组织起来。 每一次查找需要遍历线性表中的所有表项，遍历过程中记录最长的路由前缀项，直到遍历完整个线 性链表。 其次是缓存策略，也就是c a c h e 机制p j ，该算法把最近最常川的地址对应的最长匹配前缀路由 规则放在路由缓存表中，只有当路由缓存表中查找失败的时候才需要进行完整的最长前缀匹配查 找。这种技术的性能与缓存的大小以及网络流量目标地址的短时分布特性有关。然而随着i n t e m e t 的 迅速发展，网络用户的不断增加，网络流量目标地址的短时分布特性逐渐变得越来越不明显，因此 这种方法中缓存的命中率也大大下降，从而路由查找速度也变得很低。为了能够在查找性能上获得 较大的提高，缓存的命中率就需要有一定的保证。这会使得求c a c h e 的体积很大，所以成本也会很 高。因此，该方法很难适应未来的发展。 除此之外，在一些路由器中也有采川c a m 的方法c a m 是一种特殊的存储器，与一般的存储 器由地址得到数据不同，它可以由数据得到相应的地址，是通过物理方法实现查找的，在此基础上 又有了t c a m ，t c a m 比c a m 具有更好的查找功能，可以完成对某些位的忽略，然后找出与其匹 配的内容的地址，从而可以实现最大长度匹配，这在一些高端核心路由器中会是一个考虑的策略， 然而这两种物理结构也存在着一些缺陷，比如成本过高，以及发热过大，并且如果t c a m 器件的工 作频率不能达到更高要求的话，也将限制它的广泛应用 1 4 论文的主要内容和安排 本文主要研究路由查找算法的硬件实现问题，论文结构安排如下： 第一章是绪论。首先介绍了路由查找算法的产生背景，分析了路由器在网络中的作用。工作原 理以及体系架构，回顾了路由查找算法的研究背景，最后描述了本文的组织结构。 4 第一章绪论 第二章对传统的路由查找算法从软件实现和硬件器件实现两个角度进行研究。对于软件算法的 复杂度进行了比较，对于硬件器件实现进行了分析和研究。 第三章对基于h a s h 的精确匹配路由查找算法进行了研究，并采用多重h a s h 的算法进行了硬 件实现。 第四章选取了一种变长多分支压缩树的软件算法进行了分析和硬件实现，并针对该算法的特点 采用了并行查找结构加快查找速度，从而达到了较好的查找效果。 第五章对本文设计的f p g a 验证进行了阐述，介绍了x i l i n xv e r t e xi if p g a 的功能和特点，并 说明了路由查找算法的f p g a 实现流程和性能验证 第六章进行了总结，概括了本论文所做的工作，并对进一步的工作进行了展望。 5 第二章常用路由查找算法 第二章常用路由查找算法 2 1 路由查找的研究背景 2 1 1 可变长子网掩码( v l s m ) 与无类域问路由( c i d r ) i n t e m v t 最初使用两层结构( 包括网络地址和主机地址) 来构建网络随着时间的推移，网络计 算逐渐成熟和发展，单一的i n t e r a c t 连接再也不能满足要求，于是一个网络下面可以分出多个网络， 也就是子网。随着子网的出现，子网掩码的概念就随之产生，因为网络需要按一定的规则进行划分 和组织。对于子网掩码，整个网络只能由一个子网掩码。因此，当用户选择了一个子网掩码之后， 就不能支持不同尺寸的子网了。任何对更大尺寸子网的要求意味着必须改变整个网络的子网掩码。 从这里的分析可以看出，这是非常复杂和耗时的工作。1 9 8 7 年i e t f ( i n t e m e t e n g i n e e r i n g t a s k f o r c e ) 针对这一问题提出了解决方法 4 j ，规范了如何使用多个子网掩码分子网。新的子网化技术称为 v l s m ( v a r i a b l e l e n g t hs u b n e t m a s k ) ，v l s m 技术使子网的划分具有更大的灵活性，对节点较多的子 网使用较短的子网掩码，而对节点较少的子网使用较长的子网掩码，这样就使得一个组织的口地址 空间被更有效的使用，使网络管理员能够按子网的特殊需要定制子网掩码。 如果没有v l s m 技术的使用，将会造成一个网络内很多妒地址的浪费。例如，假设一个口地址为 1 7 2 1 8 6 0 ，这是一个b 类地址，使用1 6 位的网络号。使用6 位扩展网络前缀会得至i j 2 2 位的扩展网络 前缀。从数学上讲，有6 2 个可用的子网地址，每个子网内有1 0 2 2 个可用的主机地址。这种子网化策 略对需要超过3 0 个子网和每个子网内超过5 0 0 个主机的组织是合适的。但是，如果这个组织由一个超 过5 0 0 个主机的稍大分部，和许多小的只有4 0 5 0 个主机设备的分部组成，那么，地址的大部分就被 浪费了每个组织即使不需要，也被分配一个有1 0 2 2 个主机地址的子网。小的分部大约浪费9 0 0 多个 主机地址。因为子网化的网络只能用单一的掩码，且这个掩码是预定义的固定长度，所以这种地址 浪费就不可避免。子网化是对于“有限地址快速耗尽”这一棘手问题的理想解决办法。使私有网络能 够对主机地址部分重定义为子网和主机，将极大地减少巾地址的浪费。然而，在现实世界中，对子 网的要求是不一样的。希望一个组织或网络把其分成相同大小的子部分，是很不现实的。因此，使 用固定长度的子网掩码会导致子网内口主机地址的浪费。 解决这个矛盾的方法是允许使用不同大小的子网掩码，对口地址空间进行灵活的子网化。以上 述情况为例，网络管理员可以把基地址切分成不同的子网掩码，少数的大组织可以继续使用2 2 位的 扩展网络前缀，而小的组织可以分给2 5 或2 6 位的扩展网络前缀，2 5 位的前缀能包含1 2 6 个主机子网， 2 6 位的前缀允许每个子网有6 2 个主机，这也就是v l s m 在子网划分方面所起到的作用。 为了提高地址空间的利用率以及降低路由表规模的增长速度，i e t f 提出了一种称为无类域间路 由( 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 i d r ) 的地址结构”i 。c i d r 摒弃了传统上基于类的地址分配 方式规定可以使用任意长度的网络地址部分，因此产生了路由地址前缀的概念。为了满足网络规模不 断增长的需要，i e t f 设计了新一代的网络协议i p v 6 ，i p v 6 与i p v 4 相比，地址长度由原来的3 2 位变 7 东南大学硕士学位论文 成了1 2 8 位湘应地i p v 6 在籀个地址分配上也进行了一定的改进。尽管i p v 6 的地址结构与m v 4 相 比有很多的不同之处，但是从根本上来说，整个地址空间仍然是层次性结构，仍然支持类似于口v 4 c i d r 地址结构下的路由合并，因此新一代的网络协议并没有改变路由查找的本质特点。 c i d r 是传统地址分配策略的重大突破，它完全抛弃了有类地址，以i p v 4 地址为例，以前的 有类地址用8 位表示一个a 类网络号，1 6 位表示一个b 类网络号，2 4 位表示一个c 类网络号。c i d r 用 网络前缀代替了这些类，前缀可以任意长度，而不仅仅是8 位，1 6 位或2 4 位。这允许c d r 根据网络 大小分配网络地址空间，而不是在预定义的网络地址中做裁剪。每一个c i d r 网络地址和一个相应 的掩码一起广播，这个掩码的作用是为了识别网络前缀的长度。c i d r 的出现，大大减小了在互联 网络中所需路由表的大小，使网络具有更好的可扩展性。也是因为c i d r 的使用，大部分h l t e m e t 上 的路由器采用了地址汇聚的功能，所以在中间节点上可能存在多条到达目的地的路由项。中间节点 必须尽最大的可能将报文送达目的地，要在多条可达的路由项中查找目的地最有可能在的那条路由， 这样在路由查找中就必须考虑最大长度匹配的问题了。 2 1 2 路由查找的原理 报文转发是路由器要完成的最土要的功能之一，也就是将到达路由器输入端口的报文转发到正 确的输出端i ：1 ，为此，在路由器中通常需要维护一个路由表，该路由表通过各种路由协议维护，路 由表中包含了不同目的i p 地址对应的下一跳输山端口。路由查找是在路由表中为口包头中的目的地 址选择一个转发端e l 和卜一跳地址的过程，路由器中的路由表是通过路由协议生成的或者网络管理 员直接配置的静态路由。路由器接收到i p 包后，对需要转发的包，先取出口包中的目的p 地址，然 后从路由表中找到与该目的地址相匹配的信息，最后利用相关信息完成对m 包的处理和转发。 随着因特网用户的不断增长，路由器中的路由表项越来越大，c i d r 技术的出现，将3 2 位的 i p v 4 地址分为网络部分( 通常成为前缀) 和主机部分，可以根据需要来配置网络部分的大小。然而， 由于c i d r 路由的网络部分的地址长度不同定，所以通过路由协议生成路由表时，路由协议需要传 送该地址相应的掩码，掩码也采用3 2 位长，它对应的m 地址的网络部分用l 表示，主机部分用0 表示， 将m 地址和相应的掩码相与就可以知道i p 地址的网络部分。通过这些i p 地址和相应的地址掩码就可以 构造路由表。 在进行路由查找时，由于i p 包头中只有目的地址而没有相应的掩码，查找时是用目的口地址去 匹配路由表中的表项，冈此路由查找算法必须支持c i d r 技术以满足最长前缀匹配。最长前缀匹配 要求路由查找时口目的地址与路由表中的前缀匹配晟多的位数。例如：假设一个i p 包的目的地址是 1 9 2 1 6 8 2 1 2 ，路由表中有两个表项1 9 2 1 6 8 和1 9 2 1 6 8 2 ，最大长度匹配会选择更长、确定性 更强的地址前缀1 9 2 1 6 8 2 项所指示的下一个子网或主机。 然而，对于同时具有路由功能和交换功能的3 层交换机来说，除了完成上述的口查找外，还需 要完成对m a c 地址的精确匹配，例如：若到达3 层交换机的数据包具有0 x 0 1 8 2 3 f f e 0 0 1 2 的m a c 地址，就需要到已配置或学习到的m a c 表中搜索与其完全匹配的表项，然后将该表项对应的相关 信息取出，从而决定对数据包的处理及转发。 8 第二章常用路由查找算法 目前实现路由查找主要有软件和硬件两种方法，硬件实现的速率一般较高，适合于高端路由器 的实现，其吞吐量较大，支持g 比特链路速率。硬件实现快速查找要求实现上简单，查找次数少。 软件实现路由查找的速率一般低于硬件实现，但根据算法的不同，软件实现路由查找能适合中低档 次的路由器。由于中低端路由器对路由查找的速率要求不是很高闪此通常采用软件实现。现在有 许多路由查找算法支持g 比特链路，查找速度能达到几兆p p s ( p a c k e t p e rs e c o n d ) ，因此这些算法 可以应用在高端路由器中以降低路由器的成本 目前用软件实现路由查找一般采用树结构，最简单的就是二进制t i l e 树( 1 3 i n a r yt r i o ) 结构。但 是由于二进制t r i e 树的搜索深度较大，查找速率相对较慢所以提出其他的改进算法以减小树的搜 索深度，从而减小内存访问的次数，例如路径压缩树算法、i c t r i e 树算法等就是基于这种思想设 计的。 采用硬件实现快速路由查找一般都是根据腰地址一定的位长来构造一个线性表，由于线性表中 的地址连续分配，进行路由查找时可以很好地进行定位操作，从而减少内存访问的次数提高路由 查找速度。为了节省存储空间，一般采用多级线性表结构，通过增加访存的次数来减小存储空间的 需求。除此之外，还有一些路由器采用c a m 及t c a m 等硬件器件实现路由查找。 路由查找是路由器中的关键技术之一，路由查找的快慢直接关系着路由器的速度和性能，而且 它可能会成为路由器的瓶颈。虽然本论文的目的是研究能够具有较快查找速度的硬件实现算法，但 软件算法和硬件算法是互相联系的，一个好的有较快查找速度的软件算法，经过一定的处理和硬件 架构后可以实现为很好的硬件结构来进行路由查找。所以本章首先对一些传统的基于t i l e 的软件路 由查找算法进行分析，然后再介绍基于硬件器件的实现方法。 2 1 3 路由查找的目标 路由查找的实现有三个主要指标：路由查找的时间复杂度、空间复杂度和更新路由的速度。时间 复杂度是指实现一次路由查找所需要的时间，这是路由查找最关键的指标，直接影响路由器处理数 据包的能力，实现一次路由查找的时间越小，路由器的转发速率越高。空间复杂度是指实现路由查 找所构造的数据结构所占用的存储单元的量，空间复杂度关系到路由器成本，路由表所占用的存储 单元越小，路由器的成本将会越低。路由的更新也是路由查找算法的重要指标。假设网络中的路由 每秒更新r 次，依照这种频率，假定路由查找的速度是n g e p p s ，每次插入、删除和更新所需时间为d j ， 由于在更新时间内不能进行路由查找，所以实际上的路由查找速度将会由于更新操作而达不到n 兆 p p s ，每秒钟内r 次更新所需要的时间0 是： r = r x d ( 2 1 ) 也就是用于更新的时间是f ，在t ，时间内，路由查找的次数碍是： m | 2 f r ，l 也就是说路由查找速度将会减小巩。 9 ( 2 2 ) 东南大学硕士学位论文 由于路由更新操作可能会导致数据包的丢失，操作需要的时间越长，可能丢失的数据包越多。 实际上，在路由查找中，通常采用在没有数据包到来、或数据包到达的频率较小的情况下进行更新， 这样可以减小数据包丢失的可能性。 路由查找的三个目标之间存在一定的矛盾，提高查找速度就相应的要增加存储空间的需求，减 小存储空间又会使得更新路由表的难度增加。因此要使一个算法既能实现查找上的快速性，又能使 存储空间的需求量较小，并且实现更新路由表的难度也比较小，就需要在这三者中选择一个较好的 平衡点，根据不同的需要来设计不同的路由查找方案，以实现低成本高性能的路由器。 2 2 基于t r i e 的软件路由查找算法 2 2 1t r i e 简介 就目前来看，采用软件实现路由查找的算法基本上都是基于树结构的。通过构造特定的结构来 减小树的搜索深度，从而提高查找速度。 t r i e 是一种用于快速字符串检索的多义树结构，它的每一个结点代表了一个字符，而它的每一 条边就代表了字符串的连接关系。其原理是利用字符串的公共前缀来降低时空开销，从而达到提高 程序效率的目的。 搜索t i l e 的方法为：( 1 ) 从根结点开始第一次搜索：( 2 ) 取得要查找关键词的第一个字母，并根 据该字母选择对应的子树，并转到该子树继续进行检索；( 3 ) 在相应的子树上，取得要查找关键诃的 第二个字母，并进一步选择对应的子树进行检索；( 4 ) 迭代上述过程；( 5 ) 在某个结点处，关键词与 其对应的字母已经匹配，则读取附在该结点上的信息即完成查找。 2 2 2 二进制t r i e 查找算法 二进制疵查找”l ，叉称为二进制树夯找这是m 路由查找中使用的最基本的t i l e 算法，也就是 我们常提到的二叉树。用t i l e 表示前缀并不是存储在t r i e 的节点中，而是用节点间的路径表示前缀， 一般规定一个节点到其左子节点的路径表示前缀中的对应比特为0 ，节点到其右子节点的路径代表前 缀中的对应比特为1 。因为路由前缀都是由o 、l 组成，所以t i l e 适合表示路由前缀。在这种结构中， 每次进行结点相关操作时，都是以一个比特作为比较对象的，其下属分支最多包含左右两个结点：o ( 左 结点) 和l ( 右结点) 。 二进制t i l e 结构包含了所有的可能的网络前缀，但并非每一个结点都被使用。使用的结点将会 存有转发信息。一个位于树的第n 层上的结点k 表示所有具有同样的头1 3 位的路由前缀的集合。结点k 的每一个分支按照下一位是0 或1 分别指向对应子树的根结点，该子树根结点代表了所有具有同样的 头1 1 + l 位的路由前缀。由于采用最长前缀匹配原则，每一次结点访问过程中，要从t i l e 的根结点 开始，按包中目标地址的每一位是0 或1 决定下一个要访问的结点。搜索到叶子结点后搜索过程才结 束。在t i l e 的遍历过程中，记录目前匹配的最长地址前缀从而获取下一跳信息。结点的增加或删除 i o 第二