实时网络流特征提取系统设计

陈涛+乔佩利+孙广路+朱素霞

摘要：针对包采样技术在高速网络环境中提取流特征准确率低的问题，利用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

（编辑：王萍）