通信网络-tcam路由更新的硬件优化

《通信网络-tcam路由更新的硬件优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、TCAM路由更新的硬件优化颜永红，张帆（湖南大学物理系，湖南长沙410082）摘要现代核心路由器对查找速率、表项更新速度、查找表容量等提出越来越高的要求。目前工业厂商大多采用基于TCAM（三态内容关联存储器）的解决方案。TCAM最大特点是查找速度快，但其更新算法会浪费很大的存储空间。针对这个问题该文提出一种利用FPGA提供硬件支持的路由更新方法，增加新表项时，只需对新增表项进行一次预处理，转发表无需按前缀长度排序，消除了预留空闲表项造成的存储空间浪费。关键词：路由器；三态内容关联存储器；前缀；转发表；HardwareOptimizationofTCAMr

2、outeupdatingAbstractThemoderncorerouterputsforwardhigherandhigherstandardsonthespeedofupdatingtable,look-uprateandcapacityoflook-uptable.NowadaystheproduceradoptsthesolutionbasedonTCAMCternarycontentaddressablememory.TheattractiveadvantageofTCMACgoesthefastspeedoflook-up,andyetth

3、eupdatingalgorithmwillwasterelatinghugevolumeofstorage.Astothisproblem,thispaperpresentsanovelmethodtoupdatetheRouterbyusingFPGAtoprovidethehardwaresupports.Whenincreasingthenewitems,weonlyneedtodealwiththenewly-increaseditemsinadvance,anditisunnecessaryforforwardingtabletobeorde

4、redbythelengthofprefix.Asaresult,thevolumeofstoragereservedfortheorderingofprefixiseliminated.Keywords:router;TCAM;prefix;forwardingtable;文献标识码：A中图分类号：TN431湖南省自然科学基金基金号05-JJ400951前言快速路由查找一直是一个热门研究项目。近年来人们提[1][2-5]出很多基于软件或硬件的实现方法，随着路由器接口速度的不断提高，使用软件方法实现高速路由查找已经越来越困难了。目前工业界使用最多的硬件路

5、由查找方法是使用TCAM。TCAM的优点是它所保留的表项在长度要求上非常灵活，可以在同一个TCAM芯片中保存任意长度的关键字表[6]项，因此TCAM非常适用于最长前缀路由的查找。但由于TCAM仅简单地将地址最低的匹配表项的存储地址作为结果（索引）输出，要保障最长前缀匹配，表项的存储必须按前缀长度相对地址降序排列，即低地址存储前缀较长的表项，高地址存储前缀较短的表项。这种存储顺序关系使得TCAM的更新操作变得复杂。当加入一条新的前缀表项时，为了能仍然保持表项间的顺序关系，就需要移动一些前缀表图1PLO-OPT算法图示[5]项。现有的针对IPV4的PLO-O

6、PT算法（prefixlengthorderingconstraintalgorithm）是目前处理TCAM表项更新的最优算法。该算法从低地址到高地址，依次存放由长到短的不同长度前缀的表项，并将空闲的TCAM表项集中于前缀表项所存储地址区的中间位置，构成一个空闲池，如图1。当有新表项加入时则加入位置以上或以下的各表项依次向中间的空闲池移动一个地址，以创建一个空闲空间。假设TCAM中存储了N条路由信息，则空闲空间的大小必须保持在N/2个表项，这在具有几十万个表项的骨干路由器上显然代价过高。2更新表项预处理为了提高TCAM存储空间利用率，我们希望表项更新时无

7、关项能避免移动，以消除构造空闲池的必要。如果低地址的表项能确保不包含高地址表项即低地址表项的前缀不是高地址表项前缀的前缀，则搜索TCAM得到的结果就一定是具有最长前缀匹配的表项。为了使低地址表项不包含高地址表项，本文提出如下算法：1，构建一个存放前缀长度的RAM，深度与TCAM一致，宽度为5位（适合IPV4），当表项插入时将其前缀长度保存在RAM中，存放位置与其在TCAM的位置一致，以方便查询。2，以更新表项中的地址部分（更新表项以〈地址、掩码〉序偶形式出现）为关键字对TCAM进行读操作。3，若有匹配项存在，则根据TCAM输出结果读取存放在RAM中的前缀

8、长度，设为a。若无匹配项则可将更新表项写入TCAM中最后一个表项的下一个地址。4