XS-TCAM-104x320：基于FPGA的TCAM開源實(shí)現(xiàn)（一）
發(fā)布時(shí)間：2018-03-06
當(dāng)前FAST開源項(xiàng)目中通用匹配引擎（GME）規(guī)則匹配能力有限，只支持64條規(guī)則長(zhǎng)度為512比特的帶掩碼匹配功能，對(duì)需要大量規(guī)則匹配的環(huán)境，只能采用片外的TCAM器件。
為此，湖南新實(shí)網(wǎng)絡(luò)科技有限公司基于FPGA內(nèi)部的查找表邏輯和RAM資源，設(shè)計(jì)實(shí)現(xiàn)了具有TCAM功能的IP核——XS-TCAM-104x320。目前XS-TCAM-104x320 IP的源代碼已經(jīng)開源，對(duì)提升FAST流水線查表引擎的能力具有重要意義。
一、XS-TCAM-104x320的基本指標(biāo)
目前實(shí)現(xiàn)的指標(biāo)：
1．編譯速率：125Mhz
2．規(guī)則條數(shù)：320條
3．LUT資源：16799
4．RAM(M10K)資源：368
5．查詢周期：首次單條規(guī)則查詢12周期出結(jié)果，后續(xù)連續(xù)查詢則1個(gè)時(shí)鐘周期出結(jié)果。
二、XS-TCAM-104x320的實(shí)現(xiàn)原理
針對(duì)FAST前期版本支持流表項(xiàng)條目少的不足，目前對(duì)查找算法進(jìn)行了改進(jìn)，實(shí)現(xiàn)了XS-TCAM-104x320 IP，其優(yōu)點(diǎn)如下：
1.支持按優(yōu)先級(jí)查找匹配；
2.支持硬件進(jìn)行規(guī)則更新；
3.支持規(guī)則條目的按需擴(kuò)展；
4.支持匹配域關(guān)鍵字的按需擴(kuò)展；
5.支持規(guī)則查找/更新按掩碼匹配；
6.采用流水化并行的處理方式可實(shí)現(xiàn)高速查找匹配。
1、設(shè)計(jì)思想：
XS-TCAM-104x320 IP使用二維數(shù)組的存儲(chǔ)方式，并行的進(jìn)行規(guī)則更新及查找匹配，并采用流水化的方式實(shí)現(xiàn)多條規(guī)則匹配查找，從而實(shí)現(xiàn)高效快速的分類查找的目的。另外，此算法支持靈活的匹配域及流表表項(xiàng)的擴(kuò)展能力，可滿足將來(lái)匹配域擴(kuò)展及流表表項(xiàng)擴(kuò)展的需求。
XS-TCAM-104x320 IP是基于FPGA每個(gè)內(nèi)嵌RAM塊可配置成512*20的雙端口RAM進(jìn)行的實(shí)現(xiàn)，圖1為XS-TCAM-104x320 IP基本處理結(jié)構(gòu)圖，由于RAM塊為512*20因此切分的匹配域關(guān)鍵字（Key）為9位，查找邏輯以9位Key為查找地址對(duì)表項(xiàng)進(jìn)行訪問(wèn)，得到20位的規(guī)則索引標(biāo)識(shí)位，優(yōu)先級(jí)選擇器則根據(jù)優(yōu)先級(jí)輸出最高優(yōu)先級(jí)的規(guī)則索引。此算法將索引0位的規(guī)則定義為最高優(yōu)先級(jí)的索引位。
圖1 XS-TCAM-104x320 IP基本處理結(jié)構(gòu)圖
參照?qǐng)D2，圖2為流表匹配域的存儲(chǔ)結(jié)構(gòu)圖，其為512*20的RAM存儲(chǔ)塊，在此可視為512*20的二維數(shù)組，其中行地址512個(gè)，為匹配域關(guān)鍵字（Key）字段；列地址為20個(gè)，為規(guī)則索引字段(Index)。圖2將9位的Key作為地址查找RAM（Key=00111_1111），查找出的結(jié)果為此關(guān)鍵字段命中的20條規(guī)則的索引標(biāo)識(shí)位（Index_Bitmap）為0_0005，其中第0，2，位為1，表示該key匹配了上述2條規(guī)則。由于0為高優(yōu)先級(jí)位，因此0號(hào)索引被輸出。
圖2 流表匹配域存儲(chǔ)結(jié)構(gòu)圖
2、規(guī)則長(zhǎng)度擴(kuò)展
對(duì)于104位的五元組信息，需12個(gè)9*20TCAM_CORE即可實(shí)現(xiàn)，輸出的bitmap進(jìn)行比特與即可得到匹配的bitmap，如圖3所示；
圖3 規(guī)則長(zhǎng)度擴(kuò)展到五元組處理流程圖
最后，通過(guò)優(yōu)先級(jí)選擇器選擇優(yōu)先級(jí)比較高的索引輸出。
3、規(guī)則數(shù)目擴(kuò)展
通過(guò)TCAM_Block模塊可以實(shí)現(xiàn)規(guī)則數(shù)目的擴(kuò)展，如圖4所示，通過(guò)將不同的規(guī)則對(duì)應(yīng)到不同TCAM_Block模塊的Bitmap中，則可以并行的擴(kuò)展規(guī)則的數(shù)目。通過(guò)此方式在資源允許的情況下可以無(wú)限制的擴(kuò)展。
圖4 規(guī)則擴(kuò)展結(jié)構(gòu)圖
目前基于Altera A5 FPGA 的FAST架構(gòu)只實(shí)現(xiàn)的320條規(guī)則，若用戶需要更多表項(xiàng)即可按需擴(kuò)展。
三、XS-TCAM-104x320的代碼說(shuō)明
以下為XS-TCAM-104x320的頂層代碼其主要分為四部分：時(shí)鐘復(fù)位接口、規(guī)則配置接口、匹配關(guān)鍵字Key輸入接口以及規(guī)則輸出索引號(hào)Index_ID具體如下圖5所示，其Quartus II 中代碼結(jié)構(gòu)如圖6所示，代碼文件如表1所示。
圖5 XS-TCAM-104x320 IP頂層接口圖
圖6 XS-TCAM-104x320的代碼結(jié)構(gòu)
XS-TCAM-104x320的代碼文件說(shuō)明如表1所示:
目前XS-TCAM-104x320已經(jīng)完成調(diào)測(cè)試，在FAST未來(lái)發(fā)展規(guī)劃中，XS-TCAM-104x320將作為重要的改進(jìn)特性加入到FAST流水線的GME中。我們后續(xù)將對(duì)XS-TCAM-104x320的使用方法進(jìn)行進(jìn)一步介紹。
目前XS-TCAM-104x320 IP代碼可訪問(wèn)www.fastswitch.org，選擇“代碼”選項(xiàng)卡，點(diǎn)擊FAST UM，點(diǎn)擊如下按鈕開始下載：
