基于平衡三叉树实现归并算法的研究.doc

基于平衡三叉树实现归并算法的研究摘要:本文阐述了如何使用一种新的数据结构“平衡三叉树”flow数据采集协议采集到的数据进行归并。分析和详细说明了平衡三叉树的算法,通过测试数据证明平衡三叉树算法的性能是稳定和良好的。关键字:归并算法,数据结构,平衡三叉树ResearchofMergingAlgorithmofImplementbasedonBalancedTrifurcateTreeAbstract::MergingAlgorithm,DataStructure,BalancedTrifurcateTree1(引言随着互联网应用的日益广泛,有效地获取、整理和利用网络流量可以拒绝病毒攻击,界定正常流量,规划服务及计费等,flow是一种网络流量数据采集协议,利用网络中信息流的特性在对网关性能影响较小的情况下提供了详细的数据采集,并高效处理过滤的数据包和安全服务的访问列表,完成了网络流量采集的功能。2(,如果采用一种通用的数据结构(使用模板技术),运行时同时支持多种归并算法,就能够降低软件的复杂度和成本。一个算法对应一个由通用数据结构派生出的特定数据结构;通用的数据结构对于每种算法的时间复杂度要求相同。对于同一个网关的一次运行,算法不可变,所以不需考虑指定的数据结构在运行中发生变化。如果同时进行多算法的数据采集和归并,若对每一种算法都建立一个数据结构并将流复制到该结构中,则会产生多份数据拷贝,大大影响运行速度。在这种情况下,基于性能方面的考虑,采用的数据结构中应该只是存放流的索引。从本质上来说,多算法之间的区别是选取哪一些Key字段进行相等比较。表现在数据结构层面上仅仅是比较运算的区别。由此可见,如果只有一种比较方法,如:只是重载比较操作符(operator<),就无法同时支持多种比较,也无法同时支持多种算法。归并算法应该具有可扩展性,允许用户根据需要选取所需Key字段进行归并,所以Key字段的范围最大将是所有算法的Key字段的并集。配置文件可以灵活指定任意一种归并算法,无论是已有的归并算法,还是用户自定义的归并算法,它们的Key字段都必须确定。确定了算法所需要比较的Key字段后,Flow要求在一定的时间间隔后对采集到的数据进行归并。依据不同算法建立起不同的索引结构,并且按照该算法的要求进行排序,这样将能大大地减少归并的工作量。因为对于大量无序数据进行归并,必须多次遍历所有Node,时间开销是相当大的;而有序序列只需要处理相邻且相等的结构,操作时指针不必回朔,一次遍历即可完成。,我们把线程按照功能分为三大类:数据采集线程,数据归并线程,数据保存线程。其中数据采集线程根据配置文件中指定的通信协议实时接收来自网关的数据报,接收到的数据放入接收数据缓冲区中,等待归并线程处理。数据归并线程按照配置文件中指定的算法和时间间隔对接收缓冲区内的数据进行定时归并。