趙大勝 黃 馨 周 愚

（武漢船舶通信研究所 武漢 430205）

1 引言

某型萬兆網(wǎng)絡(luò)密碼機(jī)采用紅黑隔離架構(gòu)，紅黑區(qū)處理單元均基于通用處理器實(shí)現(xiàn)，紅黑區(qū)之間以FPGA加密卡隔離。網(wǎng)絡(luò)密碼機(jī)內(nèi)置ACL規(guī)則表，每行規(guī)則包含行號(hào)、五元組各字段范圍（上限、下限）、優(yōu)先級(jí)和動(dòng)作（密傳/明傳/丟棄）等信息。CPU根據(jù)來包的五元組信息在規(guī)則表中進(jìn)行分類匹配，決定后續(xù)處理，如密傳/明傳/丟棄等。

該項(xiàng)目流分類技術(shù)難點(diǎn)主要有三點(diǎn)，第一要支持萬兆速率下線速流分類，當(dāng)包長為64字節(jié)時(shí)每秒需進(jìn)行14.88兆次流分類；第二要支持五元組各字段的范圍匹配，不同于傳統(tǒng)算法中IP地址字段僅支持掩碼匹配或精確匹配；第三要支持ACL規(guī)則表實(shí)時(shí)更新，這使得基于規(guī)則表預(yù)生成二叉樹的范圍匹配算法難以適用。FPGA可實(shí)現(xiàn)范圍匹配和規(guī)則表快速更新，但如每個(gè)數(shù)據(jù)包均由FPGA計(jì)算匹配的規(guī)則行號(hào)，再將行號(hào)返回CPU則總線通信開銷極大［1～3］。

本文基于設(shè)備硬件架構(gòu)，設(shè)計(jì)了一種軟硬件協(xié)同的流分類算法。對(duì)于各數(shù)據(jù)流的首包，使用FP?GA進(jìn)行范圍匹配，并在CPU側(cè)建立對(duì)應(yīng)流表；該流的后續(xù)包在CPU側(cè)基于流表進(jìn)行哈希精確匹配，可大幅度降低計(jì)算開銷和通信開銷。此外，設(shè)計(jì)了基于計(jì)數(shù)器同步的規(guī)則表和流表的實(shí)時(shí)分布式更新機(jī)制，由入站流量觸發(fā)動(dòng)態(tài)更新，可降低更新流表的計(jì)算開銷。

2 流分類技術(shù)研究現(xiàn)狀

流分類的規(guī)則匹配分為精確匹配、掩碼匹配和范圍匹配，其中范圍匹配實(shí)現(xiàn)難度最大。五元組范圍匹配實(shí)現(xiàn)方式包括TCAM芯片匹配、CPU側(cè)二叉樹范圍匹配和FPGA側(cè)向量匹配方式［1～6］。

TCAM芯片常用于掩碼匹配，將之用于范圍匹配需要將規(guī)則展開成多行以進(jìn)行掩碼匹配，存在規(guī)則過度擴(kuò)展問題，例如3bit范圍［1，8）展開為3條掩碼規(guī)則｛001，01*，1*｝。多個(gè)字段則展開項(xiàng)為冪次關(guān)系，TCAM存儲(chǔ)空間有限且匹配條目過多時(shí)功耗顯著增加，因此在采用大規(guī)則表時(shí)，規(guī)則表拆解為掩碼造成的規(guī)則條目過度擴(kuò)張將使得TCAM芯片難以滿足要求［4～5］。

CPU側(cè)范圍匹配原理是基于規(guī)則表構(gòu)建二叉樹進(jìn)行范圍匹配，二叉樹的構(gòu)建方式不同影響搜索深度和搜索效率。學(xué)術(shù)界提出了不少優(yōu)化算法，利用規(guī)則表統(tǒng)計(jì)特性提高效率，典型代表為Hyper?cut、Bitcut等算法［6～9］。但此類算法存在三個(gè)問題，第一，二叉樹深度與規(guī)則表統(tǒng)計(jì)特性相關(guān)，不具普適性，使得流分類延時(shí)不固定；第二，當(dāng)規(guī)則庫修改后，二叉樹需要重新構(gòu)建，不能支持規(guī)則庫實(shí)時(shí)更新；第三，其計(jì)算開銷較大，目前常用的軟件流分類算法處理10Gbps速率時(shí)，Bitcut等算法要使用四核Intel E3-1225志強(qiáng)處理器的三個(gè)核心。

FPGA側(cè)基于向量匹配實(shí)現(xiàn)范圍匹配，典型算法為StrideBV和QuYun多域分類算法［10～11］。其將五元組的各字段分別進(jìn)行范圍匹配，獲得五個(gè)N行列向量（N為規(guī)則表行數(shù)），其中對(duì)應(yīng)行為1則表示該字段在匹配范圍內(nèi)，否則為0；而后將五個(gè)列向量相與，結(jié)果為1的行為匹配行，當(dāng)有多個(gè)匹配行時(shí)再進(jìn)行優(yōu)先級(jí)比較，選擇最高優(yōu)先級(jí)的行作為最終匹配成功行。向量匹配方式對(duì)規(guī)則表具有普適性，任何規(guī)則均能適配，其中StrideBV存儲(chǔ)開銷較大，本項(xiàng)目基于QuYun多域分類算法實(shí)現(xiàn)FPGA側(cè)流分類處理。

3 算法描述

3.1 流分類處理流程

當(dāng)數(shù)據(jù)流通過網(wǎng)卡進(jìn)入CPU后，CPU首先根據(jù)五元組哈希值查詢流表，如果查詢不到則將五元組通過PCIe總線交FPGA處理。FPGA返回五元組信息及匹配到的行號(hào)，CPU收到匹配結(jié)果后建立對(duì)應(yīng)的流表表項(xiàng)。CPU對(duì)該流后續(xù)包計(jì)算hash值，在哈希桶中獲取流表index索引值，根據(jù)該值在流表中進(jìn)行索引，獲取對(duì)應(yīng)的規(guī)則表行號(hào)，進(jìn)而使用該行號(hào)索引規(guī)則表，根據(jù)規(guī)則表中規(guī)則進(jìn)行對(duì)應(yīng)處理。流分類示意圖如圖1所示。

圖1 流分類流程

以下以1024行規(guī)則為例，介紹FPGA側(cè)流分類引擎處理流程。流分類引擎由8個(gè)五元組匹配模塊（PE）和8個(gè)優(yōu)先級(jí)比較模塊（PR）組成。每個(gè)PE包含128行五元組比較單元（LINE），每個(gè)PR處理128行規(guī)則的優(yōu)先級(jí)比較。PE中每個(gè)LINE對(duì)應(yīng)一行規(guī)則，包含5個(gè)比較器FE，每個(gè)FE處理五元組中的一個(gè)字段的范圍比較，5個(gè)FE結(jié)果相與作為該行范圍匹配的結(jié)果。PR中128行的比較器采用兩兩比較方式，橫向多級(jí)比較后輸出該128行匹配結(jié)果。

流分類引擎采用二維流水線方式，五元組沿PE縱向移動(dòng)匹配，每個(gè)PE將匹配結(jié)果送入PR中進(jìn)行優(yōu)先級(jí)比較，PR優(yōu)先級(jí)比較的結(jié)果（匹配與否、行號(hào)、優(yōu)先級(jí)）沿各PR縱向移動(dòng)匹配，本PR與上一個(gè)PR中結(jié)果比較后將結(jié)果送入下一個(gè)PR中。FPGA側(cè)修改規(guī)則表參數(shù)相對(duì)容易，修改規(guī)則僅需修改BRAM或寄存器中對(duì)應(yīng)值即可，刪除規(guī)則將對(duì)應(yīng)行無效即可。FPGA流分類引擎組成如圖2所示。

圖2 FPGA流分類引擎

CPU側(cè)流表匹配使用DPDK自帶的Cuckoo hash算法，又稱布谷鳥哈希，由于其結(jié)構(gòu)緊湊（CPU Cache友好），空間利用率高且訪存性能確定，被In?tel公司用于DPDK數(shù)據(jù)轉(zhuǎn)發(fā)平面查表操作。布谷鳥哈希查找首先利用主hash函數(shù)對(duì)五元組計(jì)算hash值，對(duì)hash值取余或移位作為主表哈希桶索引在該桶中查找，哈希桶中包含8個(gè)hash值高位字節(jié)（8×32bit）和8個(gè)index值（8×32bit）。如果hash值匹配則返回流表索引index，index用于指示流表行號(hào)。如果主表未查到，則利用副hash函數(shù)在副表中查找。布谷鳥哈希插入時(shí)采用hash桶方式，并使用主表、副表進(jìn)一步降低沖突概率，如果發(fā)生沖突則將原位置數(shù)據(jù)移出，再進(jìn)行插入操作。DPDK實(shí)現(xiàn)的hash庫的最大優(yōu)點(diǎn)，在于其一次查找到時(shí)間具有上限。官方試驗(yàn)結(jié)果表明，只有當(dāng)哈希表節(jié)點(diǎn)使用率達(dá)到95%時(shí)才會(huì)出現(xiàn)插入失敗，在50%以下時(shí)基本可以保證絕大部分節(jié)點(diǎn)都保存在主哈希桶中［12］。

流表匹配過程如圖3所示，圖中設(shè)置計(jì)數(shù)器目的是解決規(guī)則表修改后流表的分布式更新。

3.2 規(guī)則表更新處理流程

規(guī)則表僅千行量級(jí)，但流表數(shù)以百萬計(jì)，為降低開銷，本文通過對(duì)流表和規(guī)則行設(shè)置計(jì)數(shù)器實(shí)現(xiàn)由數(shù)據(jù)流觸發(fā)的分布式同步更新。對(duì)于兩行規(guī)則A、B而言，如果存在交集，則指有數(shù)據(jù)流同時(shí)滿足A規(guī)則和B規(guī)則。對(duì)于交集中的流分類應(yīng)選擇優(yōu)先級(jí)高的規(guī)則行作為匹配結(jié)果。因此，對(duì)某行規(guī)則的修改可能會(huì)影響與之有交集的對(duì)應(yīng)行。規(guī)則更新包括刪除行、插入行和修改行，各種操作對(duì)流表影響不同，以下分別分析。

在規(guī)則表中刪除行操作：刪除時(shí)把對(duì)應(yīng)行號(hào)的使能值調(diào)整為0。則數(shù)據(jù)流進(jìn)入時(shí)，CPU查閱規(guī)則表后發(fā)現(xiàn)該行已失效，會(huì)觸發(fā)FPGA重新計(jì)算流分類值進(jìn)而更新對(duì)應(yīng)流表。

在規(guī)則表中插入行操作：將某行插入時(shí)需要計(jì)算與該行有交集的規(guī)則行，如果本行優(yōu)先級(jí)高于與之有關(guān)聯(lián)的行，則將相關(guān)關(guān)聯(lián)行的計(jì)數(shù)值加一，在有相關(guān)數(shù)據(jù)流時(shí)觸發(fā)關(guān)聯(lián)行涉及流表的重新計(jì)算。

在規(guī)則表中修改行操作：規(guī)則表修改涉及范圍修改和優(yōu)先級(jí)修改，與插入行影響類似。此時(shí)需要計(jì)算與之有交集的規(guī)則行，如果待修改行的優(yōu)先級(jí)高于交集中關(guān)聯(lián)規(guī)則行，則相應(yīng)關(guān)聯(lián)規(guī)則行的計(jì)數(shù)值加一。

規(guī)則表修改流程如圖4所示。

圖4 規(guī)則表修改流程

4 效能分析

設(shè)計(jì)關(guān)注的指標(biāo)包括流表插入速率、檢索速率、規(guī)則更新速度和通信開銷等，利用Intel Xeon E5-2699志強(qiáng)處理器和Xilinx公司的K7325T FPGA進(jìn)行測試驗(yàn)證。流表插入方面，目前DPDK18.05使用的哈希算法為Sameh Gobriel等學(xué)者設(shè)計(jì)的RTE-Hash布谷鳥哈希算法，3200萬條五元組流表可放入cache內(nèi)。使用4個(gè)CPU核時(shí)流表插入速率可達(dá)20MPPS（Packet Per Second），使用8個(gè)核時(shí)插入速率超過35MPPS［12］。流表檢索方面，使用單CPU核時(shí)100萬條流表哈希查找速率超過16MPPS，3200萬條流表查找速率超過15MPPS，使用4個(gè)CPU核進(jìn)行流表查找時(shí)千萬級(jí)流表查找速率超過50MPPS，F(xiàn)PGA側(cè)進(jìn)行范圍匹配時(shí)在K7325T上時(shí)鐘頻率可達(dá)200MHz，流分類速度達(dá)到400MPPS，二者組合后遠(yuǎn)遠(yuǎn)超過萬兆64字節(jié)小包的14.88MPPS線速流分類要求。規(guī)則更新方面，涉及FPGA側(cè)規(guī)則更新和CPU側(cè)規(guī)則更新。FPGA側(cè)更新僅需更新BRAM或寄存器中參數(shù)值，更新速度可達(dá)一百萬次/秒［11］。CPU側(cè)處理規(guī)則更新時(shí)，刪除規(guī)則僅需將規(guī)則表中對(duì)應(yīng)行失效即可，修改規(guī)則時(shí)需要計(jì)算與之有交集的規(guī)則行，當(dāng)程序在E5-2699CPU上運(yùn)行時(shí)，對(duì)于1000條規(guī)則計(jì)算時(shí)延小于0.5ms，因此規(guī)則更新速度可達(dá)2000次/秒。通信開銷方面，僅流的首包需要涉及CPU與FPGA間總線開銷，后續(xù)包由CPU自行進(jìn)行流分類，以一個(gè)流平均20包計(jì)算，相比FPGA流分類再將結(jié)果返還CPU方式，可以節(jié)約95%的總線通信開銷。

5 結(jié)語

本文提出的軟硬件協(xié)同流分類算法，可支持流分類范圍匹配和流分類規(guī)則的快速更新。在FPGA上采用成熟的范圍匹配算法，在CPU側(cè)使用DPDK自帶的布谷鳥哈希算法，降低了開發(fā)風(fēng)險(xiǎn)和難度。并通過在流表和規(guī)則表中設(shè)置計(jì)數(shù)器，實(shí)現(xiàn)了由流觸發(fā)的流表自動(dòng)更新機(jī)制，可以顯著降低流表計(jì)算開銷和規(guī)則更新時(shí)延。