相对误差受限的数据流流量测量算法

摘要：

数据流流量测量的精度采用错误概率和相对误差进行衡量.现有的流量测量算法主要关注如何降低错误概率,而对如何减小相对误差则缺乏研究.考虑到减小相对误差对于流量计费等应用的重要意义,提出了一种相对误差受限的数据流流量测量算法MT-dlCBF(Multi-Tier d-left Counting Bloom Filter).MT-dlCBF由多层dlCBF (d-left Counting Bloom Filter)构成,且随着层数的提高,dlCBF中数据流指纹长度和流量计数器宽度也逐步增加,这样,可减轻长流对于短流的干扰,从而达到减小相对误差的目的.理论分析和仿真实验的结果表明,与dlCBF相比,MT-dl-CBF的错误概率略有增大,但相对误差显著减小.此外,在典型的参数条件下,MT-dlCBF的空间效率略优于dlCBF.

关键词：流量测量、布鲁姆过滤器、相对误差

所属期刊栏目：40

分类号：TP393(计算技术、计算机技术)

资助基金：江苏省自然科学基金项目BK2010103

在线出版日期：2013-07-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：80-83,118