星上路由查找设计与算法实现

田 园,张曙光,乔庐峰,邵世雷

(解放军理工大学通信工程学院,江苏 南京 210007)

随着宽带业务需求的不断增长,地面 Internet、4G移动通信系统及卫星网络互相结合、互为补充的模式逐渐成为全球互联网的基本结构。卫星网络将成为下一代全球信息网络的重要组成部分。卫星通信从非再生中继式的载波弯管,再生式的比特弯管,逐步发展到更加复杂高效的星上处理和星上交换。基于IP技术的星上路由器,相较于星上ATM交换技术在提高业务性能、接纳控制能力、资源利用率和全网的协议一致性等方面都有很大的优势,已成为研究的一个热点。但由于卫星空间环境的特殊要求,使得星载路由交换系统在设计上受到体积、功耗、可靠性等诸多因素的限制。路由查找是路由器实现路由转发功能的关键技术之一,设计一个适合星上的路由查找算法就显得的格外重要。也即面临着如何采用简捷高效的设计、在有限平台资源条件下达到更高性能的问题。

1 算法分析

目前的路由查找都是基于最长地址前缀匹配方式的,即从所有和目的 IP地址匹配的路由表项中找出前缀最长的作为最终的路由查找结果。该方法在查找过程中,不仅需要与地址前缀的比特值进行匹配查找,而且还需要考虑地址前缀的长度,因此各种路由查找算法都可以归结为两个方面的匹配查找过程:基于地址前缀值的路由查找算法和基于地址前缀长度的路由查找算法。在路由查找算法中,最为极端的是线性查找和采用内容匹配(CAM:Content Addressable Memory)的路由查找。采用线性查找时,输入的IP地址和路由表中的每个表项进行逐一比较,如果表项长度为 N,那么就需要比较 N次,从中找出最长匹配的前缀。这种方式下需要至少N个时钟周期才能完成匹配操作,所以不实用。采用CAM结构时,输入IP地址同时跟N个表项中的内容进行匹配比较,同时给出匹配结果,然后根据匹配结果的优先级给出最长前缀匹配结果。采用CAM结构时,其匹配时间只需要1个时钟周期,但其资源消耗和功耗都比较大。

除了上述两种极端的情况之外,采用各种算法来实现路由查找功能是研究的热点,主要包括二进制Trie树算法、路径压缩Trie树算法、多分支Trie树算法、前缀长度的二分查找法以及地址区间的二分查找法等。在关键字长度为 W,前缀数目为 N,步长为k的情况下,不同算法的复杂度如表1所示。

从上分析可知基于硬件和软件的查找算法各有利弊,硬件查找(如 TCAM 算法)的速度快,但内存利用率低、资源消耗大,不能直接用于星上处理;而软件算法(如Trie树等)具有较好的数据组织结构,对资源消耗小,但性能有限。FPGA芯片是目前实现复杂数字系统时常用的可编程逻辑器件,可以更加灵活高效地实现查找功能。因此,本文利用软硬件协同设计的思想,主要是通过软件算法来实现路由表在节点存储区的组织结构,而具体的查找过程交由硬件来完成,这样既可以克服存储资源有限的限制,又可以满足较快的查找速度。

表 1 不同算法复杂度比较

2 路由查找设计

在研究中我们先设计出了一个 8端口星上路由器的系统硬件结构图,如图 1所示。该体系采用了基于FPGA的设计架构,将功能分为三个模块:查找引擎、队列管理器与交换结构。查找引擎负责数据链路层协议的处理(如封装改变)、IP包的提取和依据路由表对目的地址进行匹配查找;队列管理器按照一定的调度策略对目标是同一输出队列的分组进行排队和调度管理;交换结构实现高性能的数据交换。可见设计星上路由器的一个瓶颈是如何在有效的资源条件下实现快速有效的路由查找机制。

图1 8端口路由器硬件平台结构

图2是IP路由查找电路的基本结构示意图。图中的IP报文输入缓冲区用于暂存来自同一端口或不同端口的 IP报文,其应具有一定深度。IP路由查找引擎负责提取输入 IP报文头部的目的地址区域,并以目的地址为索引在节点存储区内进行最长匹配查找。最长匹配查找到的结果是路由表索引,根据该索引,IP路由查找引擎从路由表中读出该报文的转发端口。在路由表中,除了常规的转发表项外,还包括一些特殊的转发表项,如缺省转发、多投、转交给星载处理器等控制信息。IP路由查找引擎内部有路由表管理寄存器,该寄存器可以被星载处理器所访问,星载处理器可以通过路由表管理寄存器对节点存储区和路由表进行维护和更新。需要说明的是,路由表的建立和更新是由星载处理器依靠路由协议来完成的,但不在本文的研究范围之内。本设计假设路由表项数量较大,存储资源有限的情况,采用路径压缩Trie树算法;当然表项数量少,可用存储资源较充裕的情况下,可以采用传统的 Trie树算法或是多分支Trie树算法,本文并未考虑。

图2 IP路由查找电路示意图

3 算法实现

从表 1中我们知道,路径压缩算法的查找复杂度为 O(W),算法的时间复杂度与表项的数目没有关系,只与关键字 W的长度有关,对于硬件实现来说则取决于处理器访问内存的频率。采用路径压缩算法不仅可以减少节点存储区内存消耗,还可以缩短平均搜索的深度。但由于传统的Trie树算法使用的树的节点灵活度非常高,所以直接用于硬件实现不太可取,需要改进。本算法的思想是利用硬件的并行技术的优势,通过一次查找多个比特,来减少内存访问的次数,提高查找的速度。算法中定义一次最多能查找4个比特,以降低FPGA实现的难度。同时利用多进制压缩算法良好的数据组织结构来减少存储空间的消耗,从而在速度和资源上取得了很好的平衡。程序用C语言编写,测试环境为Visual C++ 6.0,路由表的IP地址和Mask地址均由随机函数rand()生成。

算法数据结构及初始化:

1)每个结点有如下字段:左儿子下标 LSON、右儿子RSON、是否扩展SF、路由索引RINDEX;

2)树结点用结构数组存储,数组名是Tree[];

3)第 0个元素是总树根,Root=0,开始时,Tree[0]所有字段为0;

4)其它树结点从1号元素开始分配;每分配一个结点,把该结点清零;

5)令路由表R={r1,r2,…,rn},其中每个ri=,最高位定义为第1位,最低位定义为第32位;

6)调用下面算法构造Trie树:

ErrFlag=BuildTrieTree(R,Root,1);

算法如下:

算法的优点是无需对路由表进行排序,并且在构造过程中没有回溯,提高了树构造的效率。为了便于说明我们随机生成了表项数为7的路由表,如图3所示。实际中路由表由路由协议生成或是人工配置。算法运行后,路由表表项在节点存储区的数据结构见表 2,表中的节点序号对应于节点在内存的存储地址,并采用了十六进位制,便于直观显示。其 Trie树结构如图4所示,灰色的节点表示对应着路由表索引,节点内的数字为节点序号,同样为十六进位制。

图3 随机生成的路由表表项

图4 节点存储区的树结构

表2 节点存储区数据结构

图5为算法的测试程序界面,其中“叶子个数”为图 4中灰色节点,表示路由表中表项的数目,“树的大小”为形成树的总的节点数等于节点存储区中占用的地址数,“时钟”为构造树消耗的硬件时钟周期,单节点耗费为＝“时钟/树的大小”。经过多次测试表明,算法的平均压缩比为 1:4,平均单节点消耗为 400个时钟周期。在星上路由器的设计中,若采用的处理器的时钟频率为 50MHz,SRAM 容量为64*40 K /8 = 320KB 。采用的路由表的表项数目为1K 项,算法数据结构占用的存储空间为1K *4*64/8 = 32KB ,仅占SRAM容量的10%。算法在最差的情况下需要查找 32次,查找一次所需的时间为 32/50*10-6=640ns ,查找速度可以达到每秒 150万次。Gupta等人在文献中通过统计Internet网络中前缀长度的分布,发现 99.93%的前缀长度都分布在24或小于 24的范围内。因此实际速度每秒可以达到200万次,假设数据报的长度是40bye(IP报的最短长度),则转发速度为 200*40*8*106=640Mbit/s ,可以满足宽带卫星通信系统业务的需求。

图5 算法测试程序

4 结束语

本文从硬件的角度对星上IP路由查找算法实现做了一系列的分析,并提出了改进的 Trie树算法,给出了相应的便于用硬件实现的 IP路由表的数据结构。由于VHDL/Verilog HDL语言固有的灵活性和可编程性,可以更为灵活和高效的实现路由查找。所以,使用FPGA芯片来实现路由查找,是未来的趋势。

[1]Del R E, Pierucci L. Next-generation Satellite Networks[J].IEEE Communication Magazine,2002,40(9):50-159.

[2]肖鹏,张涛,刘锋. 基于无线接入的一体化星载路由交换系统[J].计算工程,2008,34(12):277-279.

[3]徐恪,吴建平,徐明伟.高等计算机网络[M].北京:机械工业出版社,2003.

[4]M.Sanchez, E.W.Biersack, W.Dabbous, Surey and taxonomy of IP address lookup algorithms[J], IEEE Network,2001,15(2):18-23.

[5]Pankaj Gupta, Steven Lin, and Nick Mckeown. Routing Lookups in Hardware at Memory Acess Speeds[C]//Proceeding of the IEEE INFOCOM,1998.