基于三态内容寻址存储器的路由表压缩和存储技术研究  

Research on Routing Table Compression and Storing in Ternary Content Addressable Memory

作　　者：刘刚[1] 张德运[1] 李胜磊[1] 高磊[1] 

机构地区：[1]西安交通大学电子与信息工程学院,西安710049

出　　处：《西安交通大学学报》2003年第10期1025-1028,1033,共5页Journal of Xi'an Jiaotong University

基　　金：陕西省重大技术创新基金 (CX2 0 0 1 6)

摘　　要：针对高性能路由器中的路由存储和快速查找问题,提出了将冗余裁减算法和掩码扩展技术相结合的方法来压缩路由表.冗余裁减算法寻找路由表中的等价路由并删除冗余表项;掩码扩展技术则利用三态内容寻址存储器(TCAM)的非连续掩码的特点,对具有相同下一跳和相同前缀长度的路由项进行归并,并利用基于前缀扩展和逻辑最小化思想的增量更新算法,实现路由表动态更新过程中路由的重新归并.实验结果表明,本方法可以将路由表条目至少减少40%.To solve the problem of routing look up and storing in high performance routers, a method is proposed by using pruning algorithm and extendable mask technique to compress routing table. The algorithm searches for equivalent routing items and deletes redundant ones. The routing items with same next hop and same prefix length are merged as many as possible by the extendable mask technique which taking advantage of the characteristic of discontinuous mask based on ternary content addressable memory (TCAM). The increment update algorithm which uses the logic minimization ideas and prefix extension is utilized to carry out the remerge in the process of dynamical update of the routing table. Experiments indicate that the number of routing items can be reduced more than 40%.

关 键 词：路由表 内容寻址存储器 非连续掩码 

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