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

Per-Flow Traffic Measurement Algorithm with Restrained Relative Error

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

The accuracy of per-flow traffic measurement is evaluated using the metrics of both error probability and rela- tive error. Current research on flow traffic measurement mainly focuses on reducing error probability, while little atten- tion has been paid to alleviating relative error. Motivated by the importance of reducing relative error in certain applica- tions such as usage accounting, this study presented a new algorithm named MT-dlCBF （Multi-Tierd-left Counting Bloom Filter） with restrained relative error. MT-dlCBF consists of several tiers of dlCBF （d-left Counting Bloom Fil- ter）, and dlCBF at higher tier has longer flow fingerprints and wider flow traffic counters than that of dlCBF at lower tier respectively. In this way, the interference of long flow to short ones can be alleviated significantly, resulting in re- strained relative error. Analytical and experimental results show that MT-dlCBF provides significant decrement in rela- tive error and trivial increment in error probability compared to dlCBF. Moreover, MT-dlCBF has higher space efficiency than dlCBF under typical parameter settings.