一种基于Netflow机制的大流抽样算法设计*

李川，李岷

（绵阳职业技术学院，四川绵阳621000）

一种基于Netflow机制的大流抽样算法设计*

李川，李岷

（绵阳职业技术学院，四川绵阳621000）

在网络测量中，如何在快速存储器容量一定的条件下提高对大流的测量精度是目前研究的一个热点问题。首先在不影响应用需求的前提下，提出了对双向流进行抽样测量的思想。然后对流抽样算法进行了一定的数学分析，证明了测量双向流能有效提高流表的利用率，较好地提高大流测量精度。为实现基于Netflow机制的抽样算法，详细设计了哈希函数，流表表项结构，重点解决了将双向流映射到同一个流表表项的问题。最后利用网络实测数据对该算法进行了仿真验证，结果表明，当存储资源一定时，该算法的大流测量精度要优于单向流测量算法。

大流抽样，双向流，Netflow，测量精度

0　引言

网络流量测量对网络计费、网络性能评估和异常检测等网络功能的实现具有重要的意义。网络流量测量的对象主要有报文测量和流测量两种类型，由于流可以反映网络端到端的应用状况，因此，流测量研究已经成为目前网络测量研究最主要的方向之一［1-2］。

IETF推荐的流测量方法是在测量设备中维护一个流表,为每个流保存一个流记录，但是现在网络中流的数量十分巨大，而目前的半导体技术无法提供容量足够大的快速存储器SRAM用来记录每个流的信息［3］，因此，实现起来十分困难。大量的研究表明，互联网中的流大小呈重尾分布［4-5］,即少量的大流占据了网络中大部分的流量。文献［6］对AS之间的流量测量结果显示，9%的大流产生了90%的流量。对于一些网络应用，例如网络计费，网络流量分布测量而言，大流能提供足够准确的信息，因此，对于这些应用，只测量大流能较好地解决快速存储器SRAM容量不足的问题。

目前大流的抽样测量方法主要有Multistage Filters［7］,Sample and Hold［8］、Smart Sampling［9］和LRU［10］4种，这些方法都是根据大流字节数多，持续时间长等特点来设计算法对单方向上的大流进行测量。考虑网络流量的产生是用户与网络服务交互的结果，即网络中既有用户至网络服务方向的上行流，又有网络服务至用户方向的下行流，从流测量的目的是反映端到端的应用状况来看，可以将该上行流和其对应的下行流归为一个双向流处理。上述几种方法测量的都是单向大流，如果在某个双向流中的任一方向上均是小流，而该双向流却是一大流，上述几种方法将无从检测。

因此，本文将首先证明测量双向流能有效提高大流测量的精度，然后结合广泛使用的Netflow［11-12］技术设计一种对双向流的采样算法，最后利用网络实测数据进行仿真验证。

1　流抽样算法分析

为了提高抽样设备的处理速度以适应高速网络环境，大多数流抽样方法都是利用报文经过哈希映射得到的哈希值作为流表中相应表项的索引。属于某个流的所有报文都将被映射到同一个流表表项中以记录该流的信息。但是由于流表的表项数小于网络中流的数量，将会有不同的流映射到同一个表项中，可能造成以下3个不良影响：

①不同的大流映射在同一个表项中，导致分析测量结果时得到的大流数偏低，影响了流量分布的测量，对某个大流流量大小估计的准确度也将大大降低。

②一些小流和某个大流映射在同一个表项中，分析测量结果时这些小流会被当作大流流量的一部分，导致对该大流的流量大小估计的准确度降低。

③某些小流映射在同一表项中，汇聚的结果导致抽样设备误以为检测到一条大流，从而影响了网络流量分布的测量结果。

由于网络中的流大小服从重尾分布，大流的数量很少，而小流的数量极多，因此，情形①发生的概率较低，而情形②、③却经常发生。要提高对大流流量、分布的测量精度，就必须降低这些不良事件发生的概率。

假设某抽样设备的流表共有m项表项，所使用的哈希映射函数也完全随机。如果在一定的时间Δt内，经过该抽样设备的流总数为n，满足1≤n≤m，那么在Δt时间内至少有两个流映射到同一表项的概率为

由式（1）知

其中，1≤n+1≤m，因此可以推知h

即P是n的单调递增函数。当由单向流的测量改为双向流的测量时，某些端点之间的上行流和下行流将被合并为一条流处理，流的总数n将会降低，不同流映射到同一表项的概率P将随之减少。因此，上述不良事件发生的概率会降低，大流的测量精度将得到提高。

2　流抽样算法设计

2.1大流的定义

目前在测量领域广泛使用的是基于五元组的流定义，即具有相同的源IP地址、目的IP地址、源端口、目的端口和协议类型的数据报文组成一个流。双向流是将使用相同的协议类型，来往于对应源宿端点之间数据报文看作一个流。

NetFlow机制使用以下规则来判断一个流是否结束：①新到达TCP报文首部的FIN或RST标志位被置位，则对应的流结束。②一定的时间内没有属于某一流的数据报文到达，则该流结束。该时间间隔称为流超时时间。③流的持续时间超过阈值，则认为该流结束。该时间称为流持续时间。

如果在一定的时间内，某条流的流量大小超过了阈值，则该流被认为是大流。

2.2哈希函数的选择

为了提高流表中表项的利用率，降低上述不良事件发生的概率，用作映射的哈希函数应具有较好的随机性。目前公认能产生随机序列最好的哈希函数是MD5、SHA1等加密性哈希函数，但是这些哈希函数进行运算的时间复杂度高，很难适应于高速的网络测量环境。现在许多研究都倾向于使用H3函数来进行哈希映射［13-14］。文献［15］也对H3、Bob、CRC32生成的哈希值分布的均匀性进行了卡方检验，H3函数被证明随机性最好。

H3哈希函数是通过如下的线性变换：

将一个n位的二进制串映射为一个m位的二进制串，矩阵R=（rij）m×n是一个二进制随机矩阵。运算中的乘法和加法相当于与逻辑和或逻辑，用计算机很容易实现，因此，H3哈希函数的运算速度很快，适用于高速的网络测量环境。

将IP报文中32位的源IP串记为a1，目的IP串记为a2，16位的源端口串记为a3，目的端口串记为a4，8位的协议类型串记为a5，本文哈希值h的计算公式如下：

2.3流表表项结构设计

为了实现基于NetFlow机制的流抽样算法，流表表项中记录的流信息，至少应包含以下几项：

①流的首个报文到达时间，该项可以用于帮助判断流是否超出持续时间，共8 Byte。

②流的最新报文到达时间，该项可用于帮助判断流是否超时。由于某些时间信息在①中已经存储，所以该项只需4 Byte。

③流，该项用于标示出特定的流。采用五元组后，共13个Byte。

④到达报文标识符，该项可用于判断一个TCP流是否结束，共1个Byte。

⑤流的总字节数，用于记录流量的大小，共4 Byte，可以记录流量的最大值为4 G的流。

一个表项总共需要30个Byte的存储空间。报文经H3函数映射后得到的哈希值是一个m位的二进制串，将其作为流表中表项的索引，一共可以表示2m项，所以流表的大小为30×2m个字节。目前的半导体工艺能提供的最大SRAM为64 M，可以提供大约2 M个表项。

2.4算法流程

采用NetFlow机制的大流抽样算法的具体流程如图1所示，处理流记录流程图如图2所示。

双向流测量要将上行流和下行流映射到同一个表项中，为了实现这一点，每到达一个报文，先将它的源IP地址和目的IP地址串，源端口和目的端口串互换位置再计算它的哈希值。计算公式如下：

图1　大流抽样流程图

图2　处理流记录流程图

然后判断该报文是否属于对应h'表项记录的流中。判断的条件有：①该流记录是否存在；②若流记录存在，其表示的流是否结束。如果未结束，则说明该报文是属于该表项对应的流中，此时，更新该流记录。如果表项表示的流结束，则对其进行处理，处理的流程如图2所示。然后利用式（5）重新计算哈希值h，判断报文是否属于新的哈希值对应表项记录的流中，是的话更新流记录，否则处理该流记录。这样，可以保证双向流两个方向的报文均映射到同一个流表表项中。

当报文是第1次进入流记录的处理过程中时，将首先判断该表项对应的流是否为大流。如果是，则保存该流信息至外存中供以后分析使用，然后置空该表项供以后的流使用。如果该表项对应的是小流则不必保存流信息，直接将其置空即可。当该报文是第2次进入流记录处理过程中时，说明该报文来自一个新流，此时判断完是否保存以前的流信息后，直接覆盖该表项以记录新的流信息即可。

3　仿真验证

本文仿真验证中所使用的数据是由MAWI工作组在互联网上采集得到的。设在一定的时间内网络中共有大流的数量为l条，总的字节数为b1；小流的数量为x条，总的字节数为b2。采用流抽样算法进行测量后，测得的大流字节数为，相对误差，由上述情形②、③造成的被误测的小流数为，占小流总数的比例，用指标来衡量流抽样算法的好坏。

将字节数超过链路容量0.01%的流认为是大流，流的超时时间设为Netflow默认的15 s，流的持续时间设为默认的30 min。仿真所使用的数据由MAWI工作组在互联网上采集得到，共有单向流11 500条，其中，大流所占比例为11.59%，大流字节数所占比例为86.12%；双向流9 588条，其中大流所占比例14.08%，大流字节数所占比例87.66%。显然，该实验数据服从重尾分布。SRAM存储器作为流表共有2m个表项，由于目前存储器的最大值为64 M，故m≤12。

分别采用单向流和双向流算法对大流进行测量，所得结果如表1所示。

表1　实验结果对比表

不同索引位数条件下单双向流测量误测小流相对值、绝对值比较见图3、图4。

图3　不同索引位数条件下单双向流测量误测小流相对值比较

图4　不同索引位数条件下单双向流测量误测小流相对值比较

从表1及图3、图4可以看出，当SRAM容量一定时，虽然大多数情况下采用双向流抽样算法得到的误测小流相对值Δ要略高于单向流抽样算法（超出幅度小于1%），但是其误测小流的绝对值x'却明显低于单向流抽样。这说明，双向流测量能更有效地提高流表的利用率，减少小流被误检的概率。大流相对误差的测量结果表明，双向流对大流测量的精度要优于单向流，充分证明了算法分析中的结论。如果在一定的时间内，网络中的任一单向流都有其对应的反向流，那么使用双向流测量可以使这段时间内流的数量减少一半，所测得大流相对误差将明显低于单向流测量的结果。

4　结束语

随着高速网络的不断发展，网络流量测量的应用变得越来越普遍。本文提出的双向流抽样算法能在SRAM容量一定的前提下提高大流的测量精度。由于抽样算法采用的是目前已在路由器中广泛使用的Netflow技术，因此实现和应用方便。对双向流进行抽样的思想也能推广至其他的网络流量抽样算法中。

虽然两个大流映射至同一表项的概率很低，但一旦发生，造成的后果很严重，因此，本文下一步的工作是继续研究如何以较小的时空代价完全避免这种情况的发生。

［1］程光，龚俭，互联网流测量［M］.南京：东南大学出版社，2008.

［2］刘琼，刘珍，黄敏.基于机器学习的IP流量分类研究［J］.计算机科学，2010，37（12）：35-40.

［3］裴育杰，王洪波，程时端.基于两级LRU机制的大流检测算法［J］.电子学报，2009，37（4）：684-685.

［4］Feldmann A，Greenberg A，Lund C，etal.Deriving Traffic Demands for Operational IP Networks:Methodology and Experience［J］.IEEE/ACM Transactions on Networking，2001，9（3）：265-280.

［5］Zhang Y，Breslau L，Paxson V，etal.On the Characteristics and Origins of Internet Flow Rates［C］//In Proceedings of the 2002 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.New York:ACM，2002：309-322.

［6］Fang W，Peterson L.Inter-AS Traffic Patterns and Their Implications［C］//In Global Telecommunications Conference（GLOBECOM'99），Piscataway:IEEE，1999：1859-1868.

［7］Cristian E，George V.New Directions in Traffic Measurement and Accounting［J］.SIGCOMM Computer CommunicationReview，2002，32（4）：323-336.

［8］Broder A，Mitzenmacher M.Network Applications of Bloom Filters:A Survey［J］.Internet Mathematics，2002，1（4）：485-509.

［9］Duffield N G，Lund C，Thorup M.Flow Sampling under Hard Resource Constraints［C］//Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems,New York,ACM Press，2004：85-96.

［10］Smitha，KimI，Reddy A.Identifyinglong-termhigh-band-width Flows at a Router［C］//In Proceedings of the 8th International Conference on High Performance Computing,Berlin，Springer-Verlag，2001：361-371.

［11］Chio B Y，Bhattacharyya S.Observations on Cisco Sampled NetFlow［J］.Special Issue on the First ACM SIGMETRICS Workshop on Large Scale Network Inference，2005，33（3）：18-23.

［12］陈亮，龚俭.基于NetFlow记录的高速应用流量分类方法［J］.通信学报，2012，33（1）：145-152.

［13］Keys K,Moore D，Estan C.A Robust System for Accurate Real-time Summaries of Internet Traffic［C］//In Proceedings of the 2005 ACM SIGMETRICS International Conference,Banff，Alberta，Canada，2005：85-96.

［14］Zhao Q，Kumar A，Xu J.Joint data Streaming and Sampling Techniques for Detection of Super Sources and Destinations［C］//In Proceedings of Internet Measurement Conference 2005，Berkeley，CA，2005：77-90.

［15］王洪波.互联网测量系统可扩展性问题及其关键算法研究［D］.北京:北京邮电大学，2006.

Design of a Large Flow Sampling Algorithm Based on Netflow Mechanism

LI Chuan，LI Min
（Mianyang Vocational and Technical College，Mianyang 621000，China）

It is a hot issue in the current study on network measurement that how to improve the measurement accuracy of the large flow under the certain condition of the limited fast memory capacity. First of all，the idea of a two-way flow sampling measurement has been put up while not affecting the application requirements.It is proved that the measurement of the two-way flow can improve the utilization of the stream table and the measurement accuracy of the large flow effectively based on the mathematical analysis of flow sampling algorithm.To realize the sampling algorithm based on the Netflow mechanism，the hash function and the structure of the stream table entry have been designed in detail and the problem that a two-way flow mapping to the same stream table entry has been focused on and solved.Finally，the algorithm has been simulated with the actual data from the network.The result indicates that the flow measurement accuracy of the algorithm is superior to that of the unidirectional flow measurement algorithm when the storage resource is limited.

large flow sampling，two-way flow，netflow，measurement accuracy

TP391

A

1002-0640（2015）08-0127-04

2014-06-25

2014-08-19

四川省教育厅自然科学重点基金资助项目（15ZA0369）

李川（1972-），男，汉族，四川绵阳人，硕士，副教授。研究方向：信号处理与传输等。