利用抽样技术和分层多哈希方法实现长流的识别

2016-09-22景泉

现代经济信息 2016年5期

景泉

摘要：本文提出了一种利用抽样技术和分层多哈希的方法来识别长流，选取合适的哈希函数，能够方便还原出五元组信息，减少了资源的开销;使用多哈希函数，可以极大的降低哈希冲突，保证数据的准确性。

关键词：抽样技术;分层多哈希

中图分类号：TP393.08 文献识别码：A 文章编号：1001-828X（2016）005-000-01

随着互联网规模和用户数量的迅速扩大，导致网络流量不断增大，网络行为越剧复杂，安全攻击的频率和对网络造成的破坏性也在急剧的增长。为了更好的保障网络安全，需要对网络流量进行有效的监测和分析。现代网络面临的又一紧迫任务是为用户提供可靠的业务质量保障。而用户获得的服务质量以及网络供应商可提供的服务能力都必须通过流量数据分析获得。因此，研究网络流量特性是改善网络服务质量问题的一个关键。而网络流量测量技术是目前唯一能用于分析网络状况、掌握流量特性的有效方法。

一、国内外研究概况、水平和发展趋势

Cristian Estan在长流识别的过程中就提出了一种抽样技术和哈希技术结合的算法——sample and hold算法。sample and hold 算法是按照一定的概率对字节进行抽样，如果一个报文被抽到，且其所属的流标识未被创建，则以概率P创建这个流标识;而一个流的标识在内存中已经存在，则更新属于该流标识的报文的记录。这种方法可以较精确地识别长流，所用的内存空间也较小，但它对每个报文进行处理的同时都要访问内存，因此要求内存的速度达到线速，给测量系统带来很大的压力。同时哈希的过程中也会造成一定的冲突，导致一定的误差。并且在哈希的过程中还要记录流标识的信息，会带来存储空间的增加。

国内的网络测量研究起步较晚，近年研究网络行为学逐步增加。长流占据了大部分的网络通信量，了解长流的信息就能对一次通信行为有着很好的描述。长流识别在网络测量领域也有很大的研究，提出了多种识别长流的方法。

二、识别过程

（一）分层随机抽样

分层随机抽样：如果每层中的抽样都是独立地按照简单随机抽样进行的，那么这样的抽样称为分层随机抽样，所得的样本称为分层随机样本。

分层随机抽样由于抽样在每一层中独立进行，所以各层的数据可以用于对本层（子总体）进行较精确的参数估计，然后将这些总和全部累加，就能得到对总体的一个较精确的参数估计。使用分层随机抽样可使样本中分布更加均匀，从而具有更好的代表性。这样就避免了样本分布不平衡的现象。

（二）Bloom Filter的使用

Bloom Filter最早由Burton Bloom提出，并开始广泛的应用到数据库领域中，最近在网络研究中得到了广泛的应用，并取得了一些进展。如在高速网络测量方面。

Bloom Filter是一个基于多个哈希函数映射来压缩参数空间的数据结构，它支持成员查询、随机存储。其具体的工作原理是，它描述了一个源串的集合S={x1， x2…， xn}，我们把xi称作是一个源串。申请一个内存大小为m比特位的存储空间A，并定义一个哈希函数集合H={H1， H2，…， Hk}，我们把Hi称作是一个哈希函数。对于源串集合S中的任何一个元素xi来说，通过集合H中的K个独立的哈希函数映射到存储空间A中，得到K个[1…m]之间的数，并把存储空间A中的这K个对应比特位置1。也可以利用哈希函数集合H的映射过程来检验是否属于集合S。下面的两个算法分别描述了源串集合S中的元素被哈希到存储空间的过程和验证给定元素是否属于源串集合S的过程。

（三）阈值的确定

识别长流的第一步就是要确定阈值。中给出了两种确定阈值的办法。第一种方法是考虑到收集的数据集合存在着重尾分布的特征。第二种方法更加的直接。阈值的确定会考虑到操作的环境。它要求计算一个参数，这个参数与总通信量有着密切的关系。利用这一参数可以把流分为两类：一类就是超出了这个参数值，我们这一类的流定义为长流。另一类是没有超过这个参数值，就把它们定义为短流。

本文采用的确定阈值的方法类似第二种办法。即在测量的过程中利用一个计数器记录总的报文数，设为M。我们约定把占据报文总数1%以上的流记为长流，则阈值T=M/100。在测量结束后，Bloom Filter中具有相同流标识的报文的命中次数如果超出了T值，就把这个流识别出来。

然后，我们要在测量的时间内选用简单的哈希函数对到来的报文按照报文头中的流标识分组，并对分组后的流标识进行Counting Bloom Filter变换。测量结束后，利用第二部分中所介绍的长流的定义，对每个哈希空间中的命中次数加以统计，把超出阈值的流识别出来，并存储在存储器中。我们利用段地址重叠的比特还原出主机的原始信息。中指出活跃IP分布是非常不均匀的重尾分布，相邻网段或者IP活跃度较大。但是他们的活跃度相差较大不会影响我们分析的结论，我们可以用短标签重叠的比特进行纠正。

（四）识别的基本步骤

1.构建一个多哈希站的模块，每个哈希站都存放一个独立的哈希函数

2.利用分层哈希方法依次哈希到对应的存储空间

3.统计在某一时间粒度下总的报文数，并计算阈值。

4.对TCP的五元组进行Counting Bloom Filter变换。

5.统计每个流的报文数，把超过阈值的流记录下来。

6.对记录下的长流进行原始信息的还原。

图1利用Counting Bloom Filter进行长流识别的过程。结构体BF由两个成员组成。分别携带了主机原始信息和经过哈希函数作用后所命中该存储空间中的报文数。图中把IP地址分为三段，每一段都维护一个相应的Bloom Filter数据结构。把超出阈值的信息存储在存储器中。

图1 利用Counting Bloom Filter进行长流识别的过程

三、结论

本文使用抽样技术和分层多哈希方法实现了长流的识别，利用Bloom Filter这种数据结构在识别长流的过程中可以不用维护五元组信息，降低了在维护五元组信息的过程中带来的资源的开销。经数据测试，本文提出的识别长流的算法在识别长流的同时，可以还原成五元组信息，使用多哈希可以降低冲突，保证数据的准确性。

参考文献：