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

Abstract: 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 attention has been paid to alleviating relative error．Motivated by the importance of reducing relative error in certain applications 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 Filter),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 restrained relative error．Analytical and experimental results show that MT-dlCBF provides significant decrement in relative error and trivial increment in error probability compared to dlCBF．Moreover,MT-dlCBF has higher space efficiency than dlCBF under typical parameter settings.

Key words: Traffic measurement,Bloom filter,Relative error