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

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

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

1 算法分析

目前的路由查找都是基于最长地址前缀匹配方式的,即从所有和目的 IP地址匹配的路由表项中找出前缀最长的作为最终的路由查找结果。该方法在查找过程中,不仅需要与地址前缀的比特值进行匹配查找,而且还需要考虑地址前缀的长度,因此各种路由查找算法都可以归结为两个方面的匹配查找过程:基于地址前缀值的路由查找算法和基于地址前缀长度的路由查找算法。在路由查找算法中,最为极端的是线性查找和采用内容匹配(CAM:Content Addressable Memory)的路由查找。……