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

详细信息    查看全文

• 作者：Jingsong Shan ; Yinjin Fu ; Guiqiang Ni ; Jianxin Luo…
• 关键词：probabilistic data structure ; sketch ; streaming data ; cardinality ; flow
• 刊名：Frontiers of Computer Science
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：11
• 期：1
• 页码：119-129
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Computer Science, general;
• 出版者：Higher Education Press
• ISSN：2095-2236
• 卷排序：11

文摘

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 paper, 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 experiments, performed on two real IP trace files, confirm that the proposed schema attains high accuracy and high time efficiency.