基于LRU—CBF 的大流识别算法

张淋淋　高仲合

曲阜师范大学信息科学与工程学院



基于LRU
—CBF 的大流识别算法

张淋淋高仲合

曲阜师范大学信息科学与工程学院

对网络中的大流进行提取和分析对于网络管理和安全防御具有重要意义。文章通过把最近最久未使用（LRU）策略和计数型布鲁姆过滤器（CBF）两种结构结合起来，取其各自的优点，提出一种新的大流检测算法。该算法针对大流检测漏报率高的缺陷，将“大流过滤”和“大流判断”分离，提高了算法的准确性，降低了空间复杂度。最后通过理论分析和仿真实验进行了算法的验证。

最近最久未使用 布鲁姆过滤器 流量测量 漏报率

近年来，计算机网络呈现向高速化、大规模、复杂化方向发展的趋势，其特点就是产生的数据量大、数据分组到达频率高，使得数据的处理难度越来越大。因此带来的问题就是，硬件的处理速度不能满足实际网络流量测量的需要。因此，如何用有限的硬件资源条件完成高速链路下的流量测量成为当前研究的热点问题。在当前的网络测量中，可以采用不同的测量单位，最通常使用的是以流的方式。所谓流，是指在一段时间内，具有一组相同属性的数据分组的集合，一般情况下我们通过5元组（源IP地址、源端口、目的IP地址、目的端口、传输层协议）来定义流。由于互联网中IP流长度服从重尾分布，也就是少数字节数较大的流占据了网络的大部分流量，大量字节数较小的流分担了网络的小部分流量。在很多的网络应用中，我们只需知道大字节流的信息，即检测出大流，而不需要关注到每条流的状态。基于这样的策略，本文结合最近最久未使用（LIW）和计数型布鲁姆过滤器（CBF）机制，使用两个步骤，LRU负责把大流过滤下来，CBF负责迸一步对大流进行判断，提出了一种大流识别算法（LRU—CBF， least recent used & Counter Bloom f lter）。此算法结构简单，能够精确地将大流量对象提取出来。

1　LRUCBF算法

1.1LRU 思想描述

LRU的基本原理是：建立一个长度固定的LRU缓存，在初始状态下，缓存是空的，按顺序将到达的元素记录到此缓存中，记录的原则是最新到达的放在缓存的顶端，最久未到达的放在缓存的底部。根据这一特点，LRU在计算系统中有着广泛的应用，如数据库缓存管理、在线页面管理以及磁盘缓存管理等领域。由于网络中的流服从重尾分布的规律，而且一般情况下小流的持续时间短、到达频率低，大流持续时间长、访问缓存频繁，所以经过一段时间，小流被淘汰，大流被留下。两种LRU替换方式的情况：1）新报文所

属的流Fn.1已经存在于LRU缓存中，就把该流置于缓存的最顶端，其余流记录依次向底部移动。2）新报文所属的流Fn+l不是缓存中已存在的流，缓存不满时直接添加到缓存顶部，其余流依次向底部移动，缓存已满时，将流Fn+l置于缓存的最前面，其余流向底部移动，底部的流Fn被淘汰。

1.2Bloom Fil ter

Bloom Filter是由Burton Bloom在1970年提出的，是一种简洁的二进制向量数据结构。在查询元素方面具有很好的空间和时间效率，被应用于很多大型系统。BF结构拥有很多显著的优点，空间效率、时间效率都远远超于一般算法，所需硬件条件不高，使其在很多领域应用广泛。近年来，在网络测量方面的应用也备受关注。标准的Bloom Filter的主要组成部分就是一个m位数组加一组散列函数。在标准BF中，不同的元素被哈希函数映射后的位置可能相同，即数组中的某位可能需要置1多次，但是标准BF的数组只包含0或l两种状态，因此多次置1的位只有第一次起作用。因此当需要删除元素时，就会出现错误。标准的BF不是实现元素的删除功能。为了增加删除元素的功能BF在以后的发展中出现了许多改进，其中计数型BF（CBF）是最典型的一种。当进行元素的插入操作时，使用哈希函数将元素进行映射后对应的尼个计数器值均加1；删除操作时，映射得到的七个计数器值减1；查询操作时，检查映射得到的k个计数器的值，若都大于/等于1则判断为属于该集合，只要有等于0的计数器则判断为不属于该集合。

本文提出的LRUCBF算法的核心思想是将CBF和LRU两种结构结合起来，使用两级处理机制，用CBF结构来判断网络中是否存在大流；用LRU来进一步过滤大流，达到更高的准确性，使“大流判断”和“大流过滤”两个过程分离开来。之所以选用这样的机制，有两个方面的优点，先用CBF将大流判断出来后放到缓存中，这时LRu进一步确保这些大流不丢失；另一方面，CBF的预先判断使得LRU不用对所有的数据包进行过滤，用两者的互相帮助来提高算法的执行效率，提高准确性。LRUCBF算法的基本过程：某一新的报文来到，提取出流标识，利用哈希函数的值判断此流是不是大流。如果这条新流是已经识别出来的

大流，就将CBF相应的计数器加1，如果这条新流不是已经识别出来的大流，就将这条新流放到LRU链表的最顶部，然后把LRU链表最底部的流淘汰掉。

2　算法的理论分析

2.1准确性

本文提出的LRUCBF算法由于采用了LRU策略和CBF结构，因此，此算法的错误概率就从这两部分中产生。在LRU中，链表中的大流可能被淘汰出去，而CBF中，由于本身存在的误判会将接收到的小流当作大流提取到LRU链表中，增大LRU的计算压力。因此本算法的错误概率包括LRU的漏判概率PLRU币［1CBF的误判概率RBF。

2.2空间复杂度

在2.1中，随着m、n、k的增大，准确性会迅速提高，随之带来的就是空间的增加。所以CBF中空间复杂度就是哈希函数的个数，以及计数器的个数。

3　结语

本文详细阐述了LRU策略和CBF结构的优缺点，结合两者各自的优点，避开各自的缺点，提出一种新的大流检测算法。可以把将“大流过滤”和“大流判断”分离，这样一方面能够减少测量的误差，提高算法的准确性，另一方面，使用的数据结构较为简单，工作过程也不复杂，降低了空间复杂度。经过实验结果的分析验证，基于LRU.CBF的大流检测算法具有很高的准确性，能够很好地应用到实践中。

［1］刘庆生.反病毒研究与检测技术一一试探式扫描技术［J］.个人电脑，2003（2）：134-135.

［2］李景涛，荆一楠，肖晓春，等.基于相似度加权推荐的P2P环境下的信任模型［J］。软件学报，2007，18（1）：157—167.

［3］窦文.构造基于推荐的Peer-to.Peer环境下的Trust模型［J］.软件学报，2004，15（4）：57卜583

［4］刘文芬.基于信任域的分布式动态信任管理模型［J］.四川大学学报，2014，46（4）：61—66.

［5］高磊，郭玉翠.基于信任迭代的P2P网络信任管理模型［J］.计算机工程，2012，38（19）：92—95.