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

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