Super point detection based on sampling and data streaming algorithms  

基于抽样和数据流算法的超点检测(英文)

作　　者：程光[1] 强士卿[2] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]东南大学江苏省计算机网络技术重点实验室,南京210096

出　　处：《Journal of Southeast University(English Edition)》2009年第2期224-227,共4页东南大学学报（英文版）

基　　金：The National Basic Research Program of China(973Program)(No.2009CB320505);the Natural Science Foundation of Jiangsu Province(No. BK2008288);the Excellent Young Teachers Program of Southeast University(No.4009001018);the Open Research Program of Key Laboratory of Computer Network of Guangdong Province (No. CCNL200706)

摘　　要：In order to improve the precision of super point detection and control measurement resource consumption, this paper proposes a super point detection method based on sampling and data streaming algorithms （SDSD）, and proves that only sources or destinations with a lot of flows can be sampled probabilistically using the SDSD algorithm. The SDSD algorithm uses both the IP table and the flow bloom filter （BF） data structures to maintain the IP and flow information. The IP table is used to judge whether an IP address has been recorded. If the IP exists, then all its subsequent flows will be recorded into the flow BF; otherwise, the IP flow is sampled. This paper also analyzes the accuracy and memory requirements of the SDSD algorithm , and tests them using the CERNET trace. The theoretical analysis and experimental tests demonstrate that the most relative errors of the super points estimated by the SDSD algorithm are less than 5%, whereas the results of other algorithms are about 10%. Because of the BF structure, the SDSD algorithm is also better than previous algorithms in terms of memory consumption.为了提高超点检测的精度并控制测量资源的使用,提出了一种基于抽样和数据流算法的超点检测方法.该方法通过抽样从概率上保证发送或接收大量流的节点能被检测,同时采用数据流技术建立了IPtable和流BF(BF)两个数据结构.其中IPtable结构用于判断IP是否已经被创建,如果已经被创建,则将属于该IP的所有后续的流记录在流BF结构中;如果IPtable结构中不存在该IP记录,则对属于该IP的流进行抽样.对提出方法的精度和内存需求从理论上进行了分析,并采用CERNET数据进行验证.理论分析和实验测试表明,提出的超点检测算法的测量误差基本控制在5%以内,而其他算法的误差在10%左右.另外,由于使用BF数据结构,提出的算法在使用空间上也优于其他算法.

关 键 词：super point flow sampling data streaming 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]