论文部分内容阅读
近年来，随着Internet的迅速普及，使用Internet的人数、连接到Internet上的主机数量和数据流量呈现指数式的增长。另一方面，各种新的多媒体业务也不断涌现。因此Internet的容量正在成为一种稀缺资源。为了适应Internet应用的迅速发展，提供更好的服务质量，必须提高网络的容量。随着光纤技术的发展和G比特级交换技术的发展有效的解决了链路带宽、路由器的吞吐量问题，而路由器的转发效率就成为制约网络性能提高的主要瓶颈。路由器转发包的过程包括很多工作：包头的封转、修改TTL域、计算和更新校验域和对包进行分类并将它们排入适当的对列中等等。然而在转发过程中最耗时的是根据数据包的目标地址查找下一跳路由，即路由表查找。因此，设计高速路由查找算法是实现高速分组转发的关键。本论文在综合了国内外近年来在路由查找算法及其实现以及相关技术研究进展的基础上，经过系统深入的研究，最终采用RAM和TCAM结合的Tree Bitmap结构的算法进行路由查找的实现，并下载到Xilinx公司的VinexⅡ系列xc2v1000器件中，经验证功能正确。 本文的特点和创新之处包括： 1．对现有的软件和硬件实现的路由查找算法进行了空间和时间复杂度的分析和比较。 2．根据路由前缀分布的特点，特别是最近几年路由前缀长度大于24位的路由项大幅增加，所以把路由前缀项大于23位的路由项存储在TCAM中，而把其他的路由前缀项使用Bitmap Tree结构存储在RAM中，这样就可以同时进行在RAM和TCAM中进行路由查找，加快查找速度。 3．对于存储在RAM中Tree Bitmap结构中的Internal Prefix和Extending Path同时进行处理，进行路由地址的查找。这样就可以避免回溯访问Bitmap Tree，减少了访问RAM的次数，加快了路由查找的速度。 4．完成了使用此路由查找算法的路由前驱引擎的设计，在前驱引擎中完成数据包的接收、修改TLL域、校验域的计算和更新。 5．所有硬件实现模块使用Top-D0wn的设计方法，用Verilog代码进行代码编写，并在Xilinx公司的XST软件中进行了综合以及最后的下载验证，下载至xc2v1000器件中，经验证功能正确。经XST工具综合，整个模块的速度可达到88MHz，可以满足OC-48高速路由查找的要求。