摘要
针对传统大流检测算法漏检率高的缺陷,提出了一种基于LRU-BF(least recent used&Bloom filter)策略的流量测量算法。该算法使用LRU淘汰机制、Bloom filter快速表示方案,将"大流过滤"和"大流判断"分离,较大地提高了测量的准确性。基于"概率论"的相关知识,对算法进行了理论分析,建立了错误概率上界的解析表达式。仿真结果表明:与传统Na ve-LRU算法相比,LRU-BF具有较低错误概率和空间复杂度的同时,也能满足单线路10Gbit/s的线速报文处理能力。
Aiming at the naive algorithm＇s deficiency of high false negative probability, a novel scheme called LRU-BF（least recent used ＆ Bloom filter） was presgnted. In order to achieve high accuracy, the algorithm adopted mechanisms of LRU eliminating and Bloom filter represeentation to separate the process of heavy-hitter fliteration from the heavy-hitter recognition. Based on statistical theory, ,analytical expressions about upper-bound error probability were deduced. Simulated results indicate that LRU-BF can achieve space saving and lower error probability compared with Naive-LRU algorithm. Meanwhile, it can also support,the 10Gbit/s line-speed processing.
出处
《通信学报》
EI
CSCD
北大核心
2013年第1期111-120,共10页
Journal on Communications
基金
国家重点基础研究发展计划("973"计划)基金资助项目(2012CB312901
2012CB312905)~~
