Fast counting the cardinality of flows for big traffic over sliding windows
| Autor: | Guiqiang Ni, Yinjin Fu, Jianxin Luo, Jingsong Shan, Zhaofeng Wu |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Forgetting
General Computer Science Spacetime Computer science Real-time computing Probabilistic logic 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Data structure 01 natural sciences Sketch Theoretical Computer Science 010201 computation theory & mathematics Sliding window protocol Schema (psychology) 0202 electrical engineering electronic engineering information engineering Software-defined networking Algorithm |
| Zdroj: | Frontiers of Computer Science. 11:119-129 |
| ISSN: | 2095-2236 2095-2228 |
| DOI: | 10.1007/s11704-016-6053-x |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink