关键词: 布鲁姆过滤器, CPBF 算法, IP 包识别, 识别失效代价, Hash 函数

Abstract: As the traditional Bloom filters adopt the same process for different IP packages and ignore not only IP package identification invalidation cost but also hardware resource in the process of flow identification,an algorithm called CPBF ( Classified and Pipelined Bloom Filter) for IP package identification is presented.CPBF differentiates IP packages depending on ToS ( Type of Service),which can reflect their identification invalidation cost in some ways.In order to minimize the identification invalidation rate,different numbers of Hash functions are applied to different types of IP packages.Specifically,pipelined Hash functions are adopted to accelerate the identification speed.Moreover,on the basis of the theories of probability and differential equation,the description and analytical expression of CPBF are deduced.Finally,an implementation of CPBF is conducted on FPGA.The results indicate that CPBF is superior to standard Bloom filter and multi-dimensional Bloom filter because it helps achieve lower i- dentification invalidation rate and hardware resource cost without sacrificing identification speed.

Key words: Bloom filter, CPBF algorithm, IP package identification, identification invalidation cost, Hash function