Fast counting the cardinality of flows for big traffic over sliding windows  

作　　者：Jingsong SHAN Yinjin FU Guiqiang NI Jianxin LUO Zhaofeng WU 

机构地区：[1]College of Command Information Systems, PLA University of Science and Technology, Nanjing 223002, China [2]Huaiyin Institute of Technology, Huaian 221002, China

出　　处：《Frontiers of Computer Science》2017年第1期119-129,共11页中国计算机科学前沿（英文版）

基　　金：This work was supported by the National High Tech- nology Research and Development Program of China （2012AA01A510 and 2012AA01AS09）, and partially supported by the National Natural Science Foundation of China （NSFC） （Grant Nos. 61402518, 61403060）, and the Jiangsu Province Science Foundation for Youths （BK20150722）.

摘　　要：Counting the cardinality of flows for massive high-speed traffic over sliding windows is still a challenging work under time and space constrains, but plays a key role in many network applications, such as traffic management and routing optimization in software defined network. In this pa- per, we propose a novel data structure （called LRU-Sketch） to address the problem. The significant contributions are as follows. 1） The proposed data structure adapts a well-known probabilistic sketch to sliding window model; 2） By using the least-recently used （LRU） replacement policy, we design a highly time-efficient algorithm for timely forgetting stale information, which takes constant （O（1）） time per time slot; 3） Moreover, a further memory-reducing schema is given at a cost of very little loss of accuracy; 4） Comprehensive ex- periments, performed on two real IP trace files, confirm that the proposed schema attains high accuracy and high time efficiency.ferences including IEEE TPDS, ACM ToS, JCST, MIDDLEWARE, CLUSTER, NAS, etc. Currently, his research interests include big data management, cloud storage, and distributed file systems.Counting the cardinality of flows for massive high-speed traffic over sliding windows is still a challenging work under time and space constrains, but plays a key role in many network applications, such as traffic management and routing optimization in software defined network. In this pa- per, we propose a novel data structure （called LRU-Sketch） to address the problem. The significant contributions are as follows. 1） The proposed data structure adapts a well-known probabilistic sketch to sliding window model; 2） By using the least-recently used （LRU） replacement policy, we design a highly time-efficient algorithm for timely forgetting stale information, which takes constant （O（1）） time per time slot; 3） Moreover, a further memory-reducing schema is given at a cost of very little loss of accuracy; 4） Comprehensive ex- periments, performed on two real IP trace files, confirm that the proposed schema attains high accuracy and high time efficiency.ferences including IEEE TPDS, ACM ToS, JCST, MIDDLEWARE, CLUSTER, NAS, etc. Currently, his research interests include big data management, cloud storage, and distributed file systems.

关 键 词：probabilistic data structure SKETCH streaming data CARDINALITY flow 

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