基于索引和压缩的超高速路由查找及更新算法  

Very Fast Routing Table Lookup and Update Algorithm Based on Index and Compression

作　　者：周昔平[1] 高德远[1] 樊晓桠[1] 张盛兵[1] 

机构地区：[1]西北工业大学航空微电子中心,769信箱陕西西安710072

出　　处：《小型微型计算机系统》2006年第6期1029-1033,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60273088)资助

摘　　要：在下一代核心路由器的研究中,需要在规定的硬件成本和功耗限制下同时实现超高速路由表的查找和更新是目前研究的难点.论文提出了一个全新的超高速路由表查找及更新算法.该算法采用了基于索引和路由表隐式压缩的方案,不仅实现了可以在每一个SRAM的访问延时周期内输出一个路由查找结果,而且能够在两次SRAM的读写访问延时下完成路由更新.该算法功耗小,存储效率高,整个路由表的信息都可存放在容量接近于1M字节的SRAM中.Internet protocol （IP） address lookup is a critical function of the network processors. While lots of solutions to this problem have been presented, few of them achieves line rate lookup and high update performance, high memory efficiency, and low hardware cost simultaneously. It is popular to use the content addressable memory devices for current commercial products, but it is a high cost, high power solution, particularly when applied to large databases. This paper presentes a novel high performance routing table lookup and update algorithm. According to the all-around performance, such as search and update performance, cost and consuming power, this work is better than the state-of-the-art. This algorithm is based on the index and compressed bit vector. Here not only one SRAM access cycle routing table lookup performance is accomplished but also two SRAM access cycles update performance is achieved in a pipelined scheme. The search and update proeess is illustrated in details. A maximum 530k routing entries can be held in about 1Mbytes SRAM space.

关 键 词：路由查找与更新 索引 压缩位向量 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]