一種基于軟硬件協(xié)同的流分類技術研究

趙大勝 黃 馨 周 愚

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

1 引言

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

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

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

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

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

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

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

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

3 算法描述

3.1 流分類處理流程

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

圖1 流分類流程

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

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

圖2 FPGA流分類引擎

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

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

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

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

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

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

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

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

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

4 效能分析

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

5 結(jié)語

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