CAJ | 학술논문

针对传统大流检测算法漏检率高的缺陷,提出了一种基于 LRU-BF(least recent used & Bloom filter)策略的流量测量算法.该算法使用 LRU 淘汰机制、Bloom filter 快速表示方案,将“大流过滤”和“大流判断”分离,较大地提高了测量的准确性.基于“概率论”的相关知识,对算法进行了理论分析,建立了错误概率上界的解析表达式.仿真结果表明:与传统 Na?ve-LRU 算法相比,LRU-BF 具有较低错误概率和空间复杂度的同时,也能满足单线路10Gbit/s 的线速报文处理能力.
침대전통대류검측산법루검솔고적결함,제출료일충기우 LRU-BF(least recent used & Bloom filter)책략적류량측량산법.해산법사용 LRU 도태궤제、Bloom filter 쾌속표시방안,장“대류과려”화“대류판단”분리,교대지제고료측량적준학성.기우“개솔론”적상관지식,대산법진행료이론분석,건립료착오개솔상계적해석표체식.방진결과표명:여전통 Na?ve-LRU 산법상비,LRU-BF 구유교저착오개솔화공간복잡도적동시,야능만족단선로10Gbit/s 적선속보문처리능력.
Aiming at the na?ve algorithm’s deficiency of high false negative probability, a novel scheme called LRU-BF(least recent used & Bloom filter) was presented. In order to achieve high accuracy, the algorithm adopted mechanisms of LRU eliminating and Bloom filter representation 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 Na?ve-LRU algorithm. Meanwhile, it can also support the 10Gbit/s line-speed processing.