基于BV算(suàn)法的片上(shàng)TCAM解決方案
為(wèi)此,湖(hú)南(nán)智投互動網絡科技(jì)有限公司基于FPGA内部的查找表邏輯和RAM資源,設計實現了具有TCAM功能(néng)的IP核——XS-TCAM-104x320。
一(yī)、XS-TCAM-104x320的基本指标
目前實現的指标:
- 1. 編譯速率:125Mhz
- 2. 規則條數:320條
- 3. LUT資源:16799
- 4. RAM(M10K)資源:368
- 5. 查詢周期:首次單條規則查詢12周期出結果,後續連續查詢則1個(gè)時鍾周期出結果。
二、XS-TCAM-104x320的實現原理
XS-TCAM-104x320 IP,優勢如下(xià):
- 1. 支持匹配域關鍵字的按需擴展;
- 2. 支持規則條目的按需擴展;
- 3. 支持硬件(jiàn)進行規則更新;
- 4. 采用流水(shuǐ)化并行的處理方式可實現高(gāo)速查找匹配;
- 5. 支持規則查找/更新按掩碼匹配;
- 6. 支持按優先級查找匹配。
2.2
設計思想
XS-TCAM-104x320
IP使用二維數組的存儲方式,并行的進行規則更新及查找匹配,并采用流水(shuǐ)化的方式實現多(duō)條規則匹配查找,從(cóng)而實現高(gāo)效快速的分類查找的目的。另外,此算(suàn)法支持靈活的匹配域及流表表項的擴展能(néng)力,可滿足将來匹配域擴展及流表表項擴展的需求。
XS-TCAM-104x320
IP是基于FPGA每個(gè)内嵌RAM塊可配置成512*20的雙端口RAM進行的實現, 圖1為(wèi)XS-TCAM-104x320
IP基本處理結構圖,由于RAM塊為(wèi)512*20因此切分的匹配域關鍵字(Key)為(wèi)9位,查找邏輯以9位Key為(wèi)查找地址對表項進行訪問,得到(dào)20位的規則索引标識位,優先級選擇器(qì)則根據優先級輸出最高(gāo)優先級的規則索引。此算(suàn)法将索引0位的規則定義為(wèi)最高(gāo)優先級的索引位。
圖
1 XS-TCAM-104x320 IP基本處理結構圖
參照(zhào)圖2,圖2為(wèi)流表匹配域的存儲結構圖,其為(wèi)512*20的RAM存儲塊,在此可視為(wèi)512*20的二維數組,其中行地址512個(gè),為(wèi)匹配域關鍵字(Key)字段;列地址為(wèi)20個(gè),為(wèi)規則索引字段(Index)。圖2将9位的Key作為(wèi)地址查找RAM(Key=00111_1111),查找出的結果為(wèi)此關鍵字段命中的20條規則的索引标識位(Index_Bitmap)為(wèi)0_0005,其中第0,2,位為(wèi)1,表示該key匹配了上(shàng)述2條規則。由于0為(wèi)高(gāo)優先級位,因此0号索引被輸出。
圖
2流表匹配域存儲結構圖
2.3
規則長(cháng)度擴展
對于104位的五元組信息,需12個(gè)9*20TCAM_CORE即可實現,輸出的bitmap進行比特與即可得到(dào)匹配的bitmap,如圖3所示;
圖3
規則長(cháng)度擴展到(dào)五元組處理流程圖
最後,通(tōng)過優先級選擇器(qì)選擇優先級比較高(gāo)的索引輸出。
2.4
規則數目擴展
通(tōng)過擴展TCAM_Block模塊可以實現規則數目的擴展,如圖4所示,通(tōng)過将不同的規則對應到(dào)不同TCAM_Block模塊的Bitmap中,則可以并行的擴展規則的數目。通(tōng)過此方式在資源允許的情況下(xià)可以無限制的擴展。
圖4
規則擴展結構圖
目前基于Altera A5 FPGA
的FAST架構隻實現的320條規則,若用戶需要更多(duō)表項即可按需擴展。