基于ASIC实现的高速可扩展并行IP路由查找算法

High Speed IP Lookup Algorithm with Scalability and Parallelism Based on ASIC Implementation

本文提出的IP路由查找算法基于ASIC实现 ,用多个Hash函数对不同长度的前缀进行映射并保存在不同的组相联存储器中 ,运用组相联存储器的特性很好地解决了Hash碰撞 ,并极大地减少了空间耗费 .查找时并行查找所有存储器以进行最长前缀匹配 ,可在一次访存时间内完成查表 ,而路由更新平均只需数次访存 .该算法在使用 10ns的存储器件时已可满足OC 76 8接口的线速转发要求 ,而且具有良好的可扩展性和并行性 ,可满足更大容量的路由表和更高速度网络单元的线速转发要求 .

This paper proposes a high performance IP routing lookup algorithm based on ASIC implementation. It keeps prefixes of different length in different group associated CAMs, and uses different Hash functions to map the prefixes into the corresponding groups of the CAMs. By this means it reduces the Hash collisions and the memory usage. This scheme can finish the lookup within 1 memory access time and need only a few memory accesses for each update in average. With 10 ns memory, this scheme can fully match the link speed of OC-768. For its good scalability and parallelism, it can be extended to adapt larger forwarding tables and faster forwarding requirements.