實時網絡流特征提取系統設計

陳濤+喬佩利+孫廣路+朱素霞

摘要：針對包采樣技術在高速網絡環境中提取流特征準確率低的問題，利用NetFPGA運行速度快，并行處理能力強的優勢，實現了一個實時網絡流特征提取系統，使其支持千兆級數據吞吐率。該系統有兩個重要模塊：地址映射模塊和流表核心處理模塊，前者將Bob Jenkins哈希算法通過流水線方式設計，實現流記錄的快速索引；后者通過對流記錄的并行查詢與匹配，實現對流表的快速更新。對該系統進行在線流量測試，結果表明其能夠在1Gbps網絡中實現對網絡流特征的實時提取。

關鍵詞：NetFPGA；網絡流特征提取；流水線；Bob Jenkins哈希算法

DOI：1015938/jjhust201702019

中圖分類號： TP3930

文獻標志碼： A

文章編號： 1007-2683（2017）02-0099-06

Abstract：Aiming at the problem that packet sampling technique has lower flow feature extraction accuracy in highspeed network，a realtime network flow feature extraction system is implemented in NetFPGA Making full use of NetFPGA high running speed and powerful parallel processing ability， the system can support gigabit data throughput This realtime extraction system consists of two key elements， including address mapping module and flow table core processing module The former uses pipeline technique to index flow record quickly through Bob Jenkins hash algorithm The latter can update flow table rapidly by parallelizing query and match flow record Online traffic test results show that the system can achieve realtime flow feature extraction in 1Gbps Internet connection

Keywords：NetFPGA； network flow feature extraction； pipeline； Bob Jenkins hash algorithms

0引言

網絡流特征提取技術在網絡管理和網絡安全應用中起到了至關重要的作用，通過長期統計網絡相關特征信息，實現對整個互聯網用戶行為方式的深入理解，從而對網絡資源進行合理的規劃分配與使用[1]，Monshref等[2]通過對每一個流的特征進行統計，為數據中心網絡提供最佳的流量管理方案。DTong等[3]使用網絡流統計特征大大提高了使用機器學習算法實現流分類的精確度。

所以設計一個在高速網絡環境中實時網絡流特征提取系統已成為目前研究的熱點，Alberto Dainotti等[4]指出隨著硬件技術的快速發展，流特征提取技術能夠在高度并行化的硬件架構中實現對流行為的實時分類與檢測。由此，本文設計并實現了一種基于NetFPGA[5]的網絡流特征提取系統。

1相關研究

根據RFC2722[6]的定義，一個流是指在一定時間內具有相同五元組的數據包的集合，目前基于商業上使用的網絡流量提取與分析工具如思科的NetFlow[7]，都是采用此定義來對網絡流進行監測與處理，這些設備的主要優點是不需要添加額外的部件，就可以實現對網絡數據的實時處理，然而在高速與高負載網絡環境中，由于系統資源的限制，將會導致流記錄信息不準確，而且由于采用包采樣技術對網絡流進行分析，并沒有對所有的數據包進行觀測，這也會導致對單包流數據監測誤差[8]。

除了商業上所用的設備外，也有許多基于軟件和可編程硬件實現的網絡流監測與特征提取系統，Danelutto[9]等通過多核與并行編程技術實現了網絡監控系統，并達到10Mpps的吞吐率。文獻[10]提出了一種高速包頭解析方法，并將其用FPGA板卡實現，實驗表明其支持嵌套夾層協議的解析，對基本協議的解析帶寬可達到1128Gb/s。Marco Forconesi[11]等通過NetFPGA10G平臺設計并實現了一個靈活的高速網絡監控系統，實驗表明，其可以同時管理786432條并發流信息。文獻[12]嘗試利用基于IP核的系統設計方法以及針對應用優化的PCI總線接口設計特征提取系統，測試數據表明數據傳輸性能達到300Mb/s。文獻[13]介紹了一種基于PCIE總線的高速數據采集卡設計方案，利用硬件設計的關鍵技術和本地總線的控制邏輯，提高系統的提取性能至320Mb/s。Pati S等[14]在Xilinx VirtexII pro FPGA板卡上實現了一個網絡特征提取系統，然后將其應用于高速網絡入侵檢測系統中，實驗表明該系統可以達到332Gbps的高吞吐率，與傳統采用軟件實現的方法相比，其性能提升了18倍。左震[15]等對IP流匹配技術做了深入的研究，并指出傳統IP包分類算法和抽樣流匹配算法的不足，然后提出了一種基于異或哈希和四級存儲結構的IP包快速流匹配算法，并對其流匹配情況進行了分析，實驗表明，其可以滿足骨干網實時流匹配需求。姜臘林[16]等通過使用NetFPGA10G平臺實現的高速網絡流采集系統中UDP、TCP吞吐率都達到640Mb/s。李彬通過使用NetFPGA板卡實現了對網絡數據的采集與分類[17]，Bando[18]等在FPGA上實現了一個并行hash表來解決IP流查詢提取過程中速度問題，結果表明，其可以實現250Mpps的吞吐率。Rajeswari[19]等通過使用Virtex5 FPGA實現了較高的處理速度，但是其只能同時處理500個并發的流。

綜上可見，將數據包采集與網絡流處理通過FPGA實現可以滿足較好的實時性并可實現較高的吞吐率。

2系統架構

圖1為該系統的頂層模塊架構圖：整個系統按照流水線方式運行，實現了對數據的線速處理，其中包頭解析模塊根據以太網幀在NetFPGA中傳輸的格式提取創建流表所需的基本元素，時間戳模塊打入數據包進入板卡的起始時間，地址映射模塊根據數據包五元組信息生成查詢流表的起始地址，流表核心處理模塊根據起始地址查詢流表，完成對流表中流信息的創建，更新，刪除操作。流表輸出模塊實時將流統計信息輸出。

21包頭解析模塊

此模塊接收所有來自鏈路層的以太網幀，并根據更新流表的需要，提取以太網幀中的五元組和數據包的長度信息。然后根據五元組信息確定該數據包的傳送方向。如果接收到的以太網幀不是TCP或UDP，則直接將其丟掉。

22時間戳模塊

該模塊為從以太網幀提取的TCP或UDP數據包打入時間戳，這里的時間戳是指該系統的啟動時間。

23地址映射模塊

此模塊根據從包頭解析模塊獲取的五元組信息計算其流記錄存儲的地址信息。這里采用了Bob Jenkins的哈希算法lookup3[20]，因為其具有非常低的沖突率，并且該哈希算法具有較高的運行速度，適合于硬件實現。此哈希算法原理如下：

1）將輸入數據X按比特分為3塊，表示為K[0]，K[1]，K[2]，每塊長度為32bit。

2）選取二個隨機數golden_ratio與seeding_value，這兩個元素為0～（232-1）之間的隨機數。

3）用選取的隨機數將K[0]，K[1]，K[2]初始化為A，B，C。

4）將A，B，C經過兩次mix函數迭代運算最終得到Hash關鍵值。

以上過程可以描述為

A=B=golden_ratio；

C=seeding_value；

A=A+K[0]，

B=B+K[1]，

C=C+K[2]，

mix（A，B，C）；

mix（A，B，C）；

mix（a，b，c）{

a=（a-（b+c））⊕（c>>13）；

b=（b-（c+a））⊕（a<<8）；

c=（c-（a+b））⊕（b>>13）；

a=（a-（b+c））⊕（c>>12）；

b=（b-（c+a））⊕（a<<16）；

c=（c-（a+b））⊕（b>>5）；

a=（a-（b+c））⊕（c>>3）；

b=（b-（c+a））⊕（a<<10）；

c=（c-（a+b））⊕（b>>15）；

}

根據該哈希算法的特點，我們將其采用如圖2所示的方式實現。圖（a）為該哈希算法初始化階段，也是該哈希算法的第一級流水線，將輸入k[0]，k[1] ，k[2]經過初始化模塊得到a（1），b（1），c（1）。由mix函數特點我們可以看出每個mix函數內部都是由相應的加，減，移位，異或這四種邏輯運算組成，每一級運算所需的步驟都是相同的，只是移位的次數與邏輯操作運算的對象不同，所以我們可以將mix函數根據其自身的特點分為三個mix函數子塊，圖（b）為第i塊mix函數子塊的RTL級結構圖，由圖可以看出該mix函數子塊被劃分為三級流水線進行處理，這樣可以使運算速度大大加快。圖（c）為該哈希算法塊級別架構，整個哈希算法被我們分解為三部分，初始化階段，mix1函數階段，mix2函數階段，其中mix1函數階段與mix2函數階段內部又被分為三個子塊， 每個子塊都是按照三級流水線方式進行處理，所以該流水線架構可以快速獲取key值。

24流表核心處理模塊

該模塊是整個網絡流特征提取系統最重要的模塊，其主要完成對流表的查詢，創建，更新，刪除，提交操作，并且將相應流表位置的信息及時輸出到下一模塊。由于我們采用哈希索引流表，其會出現兩個不同的數據包得到相同哈希值的狀況。所以我們設計了一個高性能流表結構和高效的流表條目管理機制應用于流表核心處理模塊。

241流表設計

我們采用FPGA片內塊RAM存儲資源來存儲流表條目，并且將地址映射模塊中Bob Jenkins哈希算法得出哈希值的低12位用來查詢流表條目，我們為每一個哈希值設計了四塊存儲空間來存放沖突的流。最終整個流表可以存儲16384個條目信息。每個流表條目存儲單元信息如表1所示：由于數據流具有時效性，我們應定期清空過期條目，這不僅高效利用了流表存儲空間，而且提高了流表信息提取的準確性。為了解決時效性問題，我們采用局部清空流表（每隔一定時間檢查流表中固定條目的時效性），與觸發檢查（索引流表時檢查該條目的時效性）兩種方式來清空過期條目。

242流表核心處理模塊設計

圖3為流表核心處理模塊的結構框圖。其有兩種工作模式一種是局部清空模式，另一種是正常查詢模式，這兩種工作模式交替進行。為了使整個系統能夠實時處理網絡數據，局部清空模式每次只查詢四個流表位置的信息，所以在高速，高負載網絡環境中，整個系統并不會出現相應的丟包現象。另外我們將存儲流表的塊RAM分割為四份，采用并發查詢的方式處理流信息，這樣只需8個時鐘周期就可以完成對流表的處理工作，避免了傳統串行查詢流表速度慢，系統吞吐率低的問題。

局部清空模式工作流程為全局清空模塊向流表讀取模塊發送局部清空信號，然后流表讀取模塊并發讀取四片塊RAM中相應流位置的時間戳信息，并將相應的流信息緩存到數據包流表緩存模塊。流表判斷模塊根據從塊RAM中接收的時間戳信息檢測是否有超時流存在，如果有超時流則發送超時命令給流表決策模塊，流表決策模塊控制數據包流表緩存模塊將超時網絡流信息輸出，并對超時流表塊RAM位置清空。整個局部清空模式按照流水線方式進行，4個時鐘周期就可以完成一次局部清空操作，避免了傳統在高速與速與高負載網絡中一次清空所有超時流表條目出現的丟包與速度慢的問題。

正常查詢模式為主要的工作模式，其完成對新來數據包的查詢，創建，更新，刪除操作。由于我們為每一個索引Hash值分配了四塊存儲空間，并采用并發查詢這四塊存儲空間的方式來處理流表中的數據，這加速了流表核心處理模塊的處理過程，也使得整個系統可以在更高的工作頻率下運行。其工作流程為流表讀取模塊從FIFO1中讀取數據包索引流表所需的地址映射信息，從FIFO2中讀取數據包的五元組，長度，時間戳信息。然后流表讀取模塊根據地址映射信息并發查詢四片塊RAM中相應位置的信息。流表判斷模塊接收從塊RAM中傳來的流的五元組，長度，個數，時間戳信息和從FIFO2中傳來的數據包五元組，長度，個數信息。并根據塊RAM中流統計信息和數據包記錄信息判斷該數據包是否存在于流表中。如果五元組信息一致，且流表相應位置無超時則表明新來的數據包屬于該流，這時我們將更新過的流的統計信息寫入數據包流表緩存模塊，并將更新命令發送到流表決策模塊。

如果五元組信息不一致或五元組信息一致且相應位置出現超時現象時，我們需要把相應的超時命令與匹配錯誤命令發送到流表決策模塊，并且將數據包與塊RAM中相應信息寫入數據包流表緩存模塊。流表決策模塊根據四個流表判斷模塊發送的命令判斷對流表做何種操作。具體執行操作如圖4所示。

整個流表核心處理模塊被劃分為上面幾個模塊，這幾個模塊像流水線一樣排列，整個處理過程最長只需要八個時鐘周期，這大大縮短了對網絡流數據的處理時間，使得整個系統可以運行在高速網絡特征提取環境中。

25流表輸出模塊

該模塊將流表核心處理模塊提交的相應流統計信息提交給PC機，并由PC機對提取的流信息做進一步處理。

3實驗與結果

整個系統由Verilog編碼設計，并且在Xilinx ISE 101上進行仿真綜合，最終在NetFPGA板卡上實現了該原型系統，圖5為整個系統的資源利用率使用情況，從圖中可以看出由于我們采用并發查詢流表機制，這雖然加快了數據的處理速度，但是也增加了資源的利用率。

圖6為整個網絡流特征提取系統的仿真波形圖，其中udp_reg_req為提取網絡流流統計信息請求信號，當其有效時，給出相應存儲流的地址信息udp_reg_addr，并且在讀地址udp_reg_rd_wr_L為高電平時，在8個時鐘周期后就可以獲取網絡流的統計信息數據udp_reg_data。

最終的測試是通過抓取哈爾濱理工大學校園網19G數據，并用Tcpreplay軟件在另一臺PC機上分別以800Mbps，1000Mbps，1200Mbp和1400Mbps重放該測試數據集，然后將其發送到NetFPGA網絡流特征提取系統中，并用Wireshark軟件實時監測發送的數據，最后將Wireshark監測結果進行統計并與該系統提取的結果進行對比分析，對比結果如表2所示。結果表明該系統最高可以工作在1000Mbps的發送速率下，這大大提高了整個網絡流特征提取系統的性能。

4結語

設計并實現了一個基于NetFPGA平臺的網絡流特征提取系統，此系統可以工作在高速網絡環境中，可以對網絡中的數據包進行建流，并對流的統計信息進行實時處理，提交。由于板卡本身資源的限制，使得流表的數量過小，出現了較多的流沖突，為了改進系統可以使用片外大容量的存儲單元SRAM或SDRAM來替代塊RAM。

整個設計采用模塊化的方式實現，這有利于對整個系統的修改，作為網絡流分類系統的一部分，為下一步做數據研究打好基礎。

參 考 文 獻：

[1]MATA F， GARCADORADO J L， ARACIL J Detection of Traffic Changes in Largescale Backbone Networks： The Case of the Spanish Academic Network[J]. Computer Networks the International Journal of Computer & Telecommunications Networking， 2012， 56（2）：686-702

[2]MOSHREF M， YU M， SHARMA A， et alScalable Rule Management for Data Centers[C]// Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation Lombard， USA： USENIX Association， 2013：157-170

[3]TONG D， SUN L， MATAM K， et al High Throughput and Programmable Online Trafficclassifier on FPGA[C]// Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays Monterey， CA， USA： ACM， 2013：255-264

[4]DAINOTTI A， PESCAPE A， CLAFFY K Issues and Futuredirections in Traffic Classification[J]. IEEE Network the Magazine of Global Internetworking， 2012， 26（1）：35-40

[5]CAO J， ZHENG X， SUN L， et alThe Development Status and Trend of NetFPGA[C]// International Conference on Network and Information Systems for Computers Wuhan， Hubei， China： IEEE， 2015：101-105

[6]BROWNLEE N， MILLS C， RUTH G Traffic Flow Measurement： Architecture[M]. Auckland： RFC Editor， 1999

[7]CISCO IncNetflow Services Solutions Guide[EB/OL].（2001-05-09） [2007-01-22] http：//wwwciscocom/c/en/us/td/docs/ios/solutions_docs/netflow/nfwhitehtml

[8]左震 光纖骨干網實時流測量關鍵技術研究[D]. 長沙：國防科學技術大學，2012

[9]DANELUTTO M， DERI L， DE Sensi D Network Monitoring on Multicores with Algorithmic Skeletons[C]//PARCO Ghent， Belgium： Elsevier， 2011： 519-526

[10]肖寅東， 王厚軍， 田書林，等 高速網絡入侵檢測系統中包頭解析方法[J].儀器儀表學報， 2012， 33（6）：1414-1419

[11]FORCONESI M， SUTTER G， LOPEZBUEDO S， et al Accurate and Flexible Flowbased Monitoring for High Speed Networks[C]// International Conference on Field Programmable Logic and Applications Porto， Portugal： IEEE， 2013：1-4

[12]FAN Z， ZHAO G， SU JIAN The Design of Highspeed Data Acquisition System Based on IP core[J]. Microcomputer Information， 2007， 23（29）：159-161

[13]潘玉霞 基于PCI Express總線高速數據采集卡的設計[D]. 太原：中北大學，2011

[14]PATI S， NARAYANAN R， MEMILK G， et al Design and Implementation of an FPGA Architecture For Highspeed Network Feature Extraction[C]// International Conference on FieldProgrammable

Technology Kokurakita， Kitakyushu， JAPAN：IEEE， 2007： 49-56

[15]ZUO Zhen， HUANG Zhiping， SU Shaojing，et al Research on a Fast IP Packet Flow Match Algorithm Based on Xor Hash and Fourlayer Memory Hierarchy[C]// PacificAsia Workshop on Computational Intelligence and Industrial Application Wuhan， China： IEEE， 2010： 244-248

[16]姜臘林， 楊嘉佳， 姜磊，等 高速網絡流采集系統的設計與實現[J]. 計算機應用， 2014， 34（11）：3201-3205

[17]李彬 基于NetFPGA的網絡流量分類[D]. 成都：電子科技大學， 2011

[18]BANDO M， ARTAN N S， CHAO H J Flashlook： 100Gbps Hashtuned Route Lookup Architecture[C]// International Conference on High PERFORMANCE Switching and Routing Paris，France：IEEE， 2009：1-8

[19]RAJESWARI P， NAGARAJAN N An FPGAbased Hardware Architecture for Network Flow Analysis[J]. European Journal of Scientific Research， 2012， 83（3）： 337-338

[20]JENKINS B Functions for Producing 32bit Hashes for Hash Table Lookup[EB/OL]. （2006-05-11） [2009-04-16] http：//wwwburtleburtlenet/bob/hash/doobshtml

（編輯：王萍）