为解决高速网络测量中面临的如何平衡测量速度、精度与存储器容量的问题，采用自适应非线性采样方法，基于高速现场可编程门阵列（FPGA）硬件平台，研究了针对高速网络流量的测量装置FAST.通过控制状态机设计、存储器功能划分和并行回导设计，FAST原型系统可根据实时流量动态调整采样概率，在较高的计数器压缩率下，保持99%以上的平均测量精度，分组测量吞吐量达27.4 Mpps.
Aiming at the problem that how to trade off the access throughput, accuracy and capacity of counter memory in high-speed network measurement, the non-linear sampling was adopted to develop an FPGA-based network measurement system FPGA-based adaptive sampling measurement (FAST). The key designs of FAST include the centralized state machine, the separate function banks in counter memory and the parallel export operations. Through numerous evaluations, this FAST prototype can adaptively tune sampling rate according to real-time flow volume and reach a high counter compression rate with more than 99% average accuracy rate. The throughput attains to 27.4Mpps.
面对高达每秒数百亿bit线速的网络链路，线性测量方法难以兼顾高速链路测量对大容量计数器和高吞吐量的需求.工业界普遍采用随机采样方法，通过局部数据样本估计完整的原始统计信息.但是，基于每流测量的NetFlow需要专用内容寻址存储器(CAM, content addressable memory)查找硬件支持，兼容性较差.基于分组测量的sFlow的精度较低.与之相比，自适应非线性采样能够根据实时流量大小，动态调整采样率，对大流降低采样率，对小流增加采样率，从而有效提高对小流的测量精度，同时具有更高的压缩率[1-2].
提出了利用现场可编程门阵列(FPGA，field programmable gate array)硬件平台和静态随机存取存储器(SRAM, static random access memory)高速存储器实现对流量自适应非线性采样测量的方案，包括采样决策、功能结构、数据通路和控制状态机设计，实现对高速链路的有效测量.最后给出实际系统的测试验证结果.
1 自适应非线性采样对业务流的每流(Per-Flow)测量而言，2个基本的统计量是分组数(Number of Packets)和流容量(Number of Bytes).自适应非线性采样方法ANLS-Ⅰ和ANLS-Ⅱ分别针对这2个统计目标，对流量进行高精度压缩测量，大大缓解了重载流量下计数器空间不足的问题.
1.1 测量分组数ANLS-Ⅰ用于测量业务流的分组数，为每个流分配一个分组数计数器，当一个新分组到达时，通过式(1) 计算本次测量的采样概率
| $ {p_{\rm{A}}}({c_{\rm{A}}}) = \frac{1}{{f({c_{\rm{A}}} + 1)-f({c_{\rm{A}}})}} $ | (1) |
其中：cA为当前分组数计数器的值，函数f(x)是一组单调递增凸函数簇，其中一个实例可定义为
| $ f\left( x \right) = \frac{{{b^x}-1}}{{b-1}} $ | (2) |
其中：b(b>1) 是压缩参数.计数器的更新决策为
| $ c{\prime _{\rm{A}}} = \left\{ \begin{array}{l} {c_{\rm{A}}} + 1, 依概率{p_{\rm{A}}}({c_{\rm{A}}})\\ {c_{\rm{A}}}, 依概率 1-{p_{\rm{A}}}({c_{\rm{A}}}) \end{array} \right. $ | (3) |
数据恢复时，通过
ANLS-Ⅱ用于测量业务流的容量，为每个流分配一个流容量计数器.每次分组测量增量由基本增量和采样增量两部分组成.当一个新分组到达时，ANLS-Ⅱ先通过式(4) 计算出本次测量的基本增量Δ(cD, l)，
| $ \Delta ({c_{\rm{D}}}, l) = \left| {{f^{-1}}(l + f({c_{\rm{D}}}))-{c_{\rm{D}}}} \right|-1 $ | (4) |
其中：cD为当前流容量计数器的值，l为本次到达分组的真实长度, 函数f(x)在形式上与式(2) 相同，但压缩参数(记为b′)的选取与ANLS-Ⅰ不同.然后，通过式(5) 计算当前分组采样概率.
| $ {p_{\rm{D}}}({c_{\rm{D}}}, l) = \frac{{l + f({c_{\rm{D}}})-f({c_{\rm{D}}} + \Delta ({c_{\rm{D}}}, l))}}{{f({c_{\rm{D}}} + \Delta ({c_{\rm{D}}}, l) + 1)-f({c_{\rm{D}}} + \Delta ({c_{\rm{D}}}, l))}} $ | (5) |
流容量计数器的更新决策为
| $ c{\prime _{\rm{D}}} = \left\{ \begin{array}{l} {c_{\rm{D}}} + \Delta ({c_{\rm{D}}}, l) + 1, 依概率 {p_{\rm{D}}}\left( {c, l} \right)\\ {c_{\rm{D}}} + \Delta ({c_{\rm{D}}}, l), 依概率 1-{p_{\rm{D}}}\left( {c, l} \right) \end{array} \right. $ | (6) |
通过
为了达到测量高速链路的吞吐量要求，利用FPGA可编程硬件对流量进行非线性采样测量，开发并行统计每流分组数与流容量的测量装置FAST.测量时，从待测链路上接出旁路分支到IP分组预处理装置，其作用是通过IP分组的五元组信息获取所属业务流的流号；同时提取IP分组长度，把流号和长度封装成统计帧发送给FAST装置.
FAST装置的逻辑功能结构如图 1所示.分组数计算模块实现ANLS-Ⅰ采样方法；流容量计算模块实现ANLS-Ⅱ方法.测量装置在基于FPGA的可编程开发硬件平台上搭建.其中，SRAM存储器利用片外SRAM实现；其他功能模块均在FPGA芯片内搭建，利用Verilog硬件语言实现全部系统功能.硬件平台上的晶振发出统一系统时钟，各个模块根据自己的功能需要进行适当的分频或倍频.
|
图 1 FAST装置的逻辑功能结构 |
地址映射模块根据流号在哈希表中查找该流的计数器地址.如果哈希表中没有该流，说明当前分组是本流的第1个到达分组，此时在哈希表中新建一个对应表项，从空闲地址池中分配一个新计数器地址，写入哈希表项.地址映射模块把流计数器地址传送给控制单元.
控制单元获得当前分组对应的流计数器地址后，从SRAM中读取当前流的计数器值.该计数器值由分组数和流容量两部分组成.控制单元按照预设格式解析出分组数和流容量值，分别传给对应的2个计算模块.同时，控制单元还把收到的当前分组长度传给流容量计算模块，以计算计数器的基本增量.
分组数计算模块由采样概率计算单元和比较模块构成.其中，采样概率计算单元接收从控制单元送来的当前流分组数值，通过式(1) 计算出对应的计数器采样概率，把此概率输出到比较模块.需要说明的是，FPGA硬件的浮点运算能力较差，每次乘、除、浮点运算操作都会消耗大量的逻辑资源和运算周期，所以诸如式(1) 的计算极易成为整个测量装置的瓶颈.为此，FAST中采取空间换取时间的思路，预先把每个计数器值对应的概率值都计算好，存在FPGA片内存储器中，每次需要计算采样概率时，只需要查表即可，显著提高了计算效率.比较模块把采样概率与由随机数产生模块(由基于32-bit线性反馈移位寄存器的LFSR算法[3]实现)实时发出的随机数作比较，根据式(3) 决定是否对该分组进行采样计数.如果确定采样，则比较模块向写回模块发出采样命令.与之类似，流容量计算模块由浮点运算单元和比较模块构成.其中，浮点运算单元从控制单元获得当前分组长度和流容量.利用式(4) 和式(5) 计算流容量的基本增量和采样概率.比较模块通过比较采样概率和实时随机数，根据式(6) 做出采样决定，连同基本增量一起传给写回模块.
写回模块分别从2个计算模块中接收采样命令.根据式(3) 计算新的分组数值；根据式(6) 计算新的流容量值.然后把两部分计数器新值按照原始解析格式合并成一个完整计数器值，写回给控制单元.控制单元收到更新后的计数器值后，将其写回到SRAM中的流计数器原地址中，完成一次完整的分组测量.
2.2 双功能Bank划分与“乒乓切换”控制单元收到更新后的计数器值后，首先检查计数器是否溢出，即满足下列两个条件之一.
溢出回导条件1：单一计数器纵向溢出.控制单元从写回模块收到的计数器新值达到当前计数器位宽所能表示的最大数值；
溢出回导条件2：计数器表项数横向溢出.当前维护的流计数器数量达到了SRAM的最大地址容量.
当计数器发生溢出时，SRAM存储器需要把当前使用的计数器单元数据全部导出，此时无法再对后续到达的分组进行统计.为了不影响正常的测量工作，FAST把一块物理SRAM芯片的全部存储空间划分为2个相同容量的存储Bank，利用最高地址位(置0或置1) 进行区分.在FAST装置的控制单元中，用一个1-bit寄存器RA储存当前测量Bank的最高位地址.用BaseAddr表示SRAM存储单元的低位偏址(Offset)，则[RA, BaseAddr]即为当前测量Bank中存储单元的完整地址；[~RA, BaseAddr](“~”为取反操作符)为回导Bank中计数器的地址.回导时，控制单元按地址顺序将回导Bank中的每个流计数器的值读出并写入输出FIFO，通过物理层接口发给外部设备.如果当前的测量Bank发生计数器溢出，为了不使实时测量工作停顿，需要立即将另一个空闲Bank切换为测量Bank，利用新的测量Bank开始下一个测量周期.同时，发生溢出的原测量Bank随即变为回导Bank，开始向外导出数据.也就是说，SRAM的2个Bank会在溢出时刻发生“乒乓式”的对换.实现上，通过RA寄存器取反操作完成.
2.3 控制单元状态机中的并行回导控制单元是FAST装置的核心，负责统筹和协调各模块之间的数据交互和状态.利用有限状态机实现控制单元功能.由于SRAM的2个功能Bank共享同一套地址和数据总线，为保证回导数据能及时导出，在状态机设计中，把回导操作“穿插”在测量周期的“SRAM空闲阶段”进行，实现测量和回导并行工作，力图最大限度地利用SRAM的访存能力.具体而言，测量工作只有在读取计数器旧值和写回更新值时需要读写SRAM，在2个计算模块计算计数器新值的过程中，并不涉及SRAM操作.可以在这个“SRAM空闲阶段”，利用地址和数据总线进行数据回导.因此，在对每个到达分组的测量周期内，都可以导出一个回导Bank中的计数器值.最坏情况下(即每次到达分组均为新流)，也能保证在测量Bank地址被填满溢出时，回导Bank“刚好”完成回导清空，准备就绪切换为新的测量Bank，不会造成系统停顿.
需要说明的是，读SRAM的时间远小于2个运算模块计算计数器更新值的时间.这保证了在等待计时器更新值的状态中，SRAM输出的回导数据会先于写回模块输出的计数器新值到达控制单元，不会影响下次分组测量周期中对SRAM的访存.
3 原型系统实现与性能评测 3.1 FAST原型系统实现在以Altera Stratix Ⅳ E FPGA芯片(运行频率400 MHz)为核心的可编程开发板[4]上实现FAST原型系统.开发板上的片外存储资源为一块QDR Ⅱ + SRAM芯片(运行频率400 MHz)，容量72 Mbit，地址总线20 bit.系统中所需的预处理工作由一台通用服务器完成.服务器的配置为Intel Xeon E3-1230处理器，4核心8线程，单核3.20 GHz主频，32 GB内存，运行Linux Fedora 15操作系统.服务器通过以太网与开发板连接通信.为了提高传输效率，服务器把每100个分组的长度信息封装成以太帧，发给FAST系统.FAST解析帧后，进入分组测量周期.
分组数和流容量计数器的位宽分别设为12 bit和20 bit，SRAM地址线宽20 bit，测量和回导Bank地址线宽均为19 bit，可寻址512K流计数器地址.ANLS-Ⅰ的压缩参数设为1.002；ANLS-Ⅱ压缩参数设为(1+1/256).从计数器压缩率、精度和吞吐量三方面对FAST系统进行测试，使用CAIDA截取的真实链路Trace文件作为测试样本，其中包含17 007 643个分组，共计301 719个业务流.
3.2 测试结果为验证FAST的计数器采样压缩能力，在测试Trace中选取一个包含8 510个分组，总容量为12.7 MB的流.在该流分组到达过程中，比较FAST装置的自适应采样计数器与无压缩的线性计数器的增长速度，结果如图 2所示.与无压缩的线性增长计数器相比，FAST通过自适应采样显著减缓计数器的增长速度.分组数和流容量计数器的最终值为1 455和2 767，仅为真实值的17%和0.022%，不仅大大增加了相同位宽下计数器的存储能力，也通过降低溢出回导的频率减少了回导开销和测量误差.
|
图 2 单一流计数器随分组积累的增长趋势 |
图 3描述了FAST对测试Trace测量的平均每流相对误差的累计分布函数(CDF，cumulative distribution function)曲线.对于分组数，将近95%的流的相对误差在1%以下，平均每流相对误差为0.32%；对于流容量，90%的流相对误差在1%以下，平均每流相对误差为0.52%.
|
图 3 FAST测量平均每流相对误差累计概率分布 |
最后，测试FAST装置的测量吞吐量，通过在不同链路速率下的多次测试，最差情况下(所有待测分组均为64 B)，测得能使原型系统输入FIFO“不溢出”的最大待测链路速率为27.4 Mpps，预处理服务器与原型系统之间链路最大支持速率为274 Mpps(每帧装载100个分组信息).此时，FAST原型系统的最低测量吞吐量为27.4 M×64×8=14 Gbit/s；在平均每分组长度为250 B的正常情况下，FAST原型系统的一般测量吞吐量可达27.4×250×8=54.8 GB/s.
4 结束语研究并实现了面向高速网络链路的流量测量装置FAST，利用自适应非线性采样方法测量每流的实时分组数和流容量.在以FPGA为核心的硬件平台上实现FAST原型系统，包括完整输入输出接口、控制和运算逻辑状态机.利用硬件的速度优势，实现对高速大容量网络链路的有效测量.通过存储器双功能Bank划分和“乒乓切换”，FAST装置可以并行完成流量测量与数据回导工作，而不产生停顿.经过实际系统测试，FAST原型系统在较高的压缩率下，能够保持99%以上的平均测量精度，分组测量吞吐量达27.4 Mpps.
| [1] | Hu Chen, Wang Sheng, Tian Jia, et al. Accurate and efficient traffic monitoring using adaptive non-linear sampling method[C]//INFOCOM 2008. Phoenix: IEEE, 2008: 421-429. http://citeseerx.ist.psu.edu/viewdoc/summary?cid=9263969 |
| [2] | Hu Chengchen, Liu Bin, Zhao Hongbo, et al. Discount counting for fast flow statistics on flow size and flow volume[J]. IEEE Trans on Networking, 2014, 22(3): 970–981. doi: 10.1109/TNET.2013.2270439 |
| [3] |
张雪锋, 范九伦. 基于线性反馈移位寄存器和混沌系统的伪随机序列生成方法[J]. 物理学报, 2010, 59(4): 2289–2297.
Zhang Xuefeng, Fan Jiulun. Pseudo-random sequence generating method based on LFSR and chaotic system[J]. Acta Physica Sinica, 2010, 59(4): 2289–2297. doi: 10.7498/aps.59.2289 |
| [4] | Altera Corporation. Altera Stratix Ⅳ E FPGA developmentKit.[EB/OL].US: Altera, 2014(2014-11-20)[2017-02-25].http://www.altera.com/products/devkits/altera/kit-stratix-iv-e.html. |