哈尔滨工程大学学报Issue(10)：1247-1252,6.DOI:10.3969/j.issn.1006-7043.201306057
基于Bloom滤波器的快速路由查找方法
A fast method for IP lookups based on Bloom filters
摘要
Abstract
To solve the problem of the longest prefix matching in IP routing lookups, a fast IP routing lookup meth⁃od based on Bloom filters was proposed. A first⁃byte indexing table was established to reduce the number of Bloom filters to be queried in parallel. The number of Bloom filters was optimized based on the non⁃uniform distribution of the prefix lengths of IP addresses, so that the number of Bloom filters required in IP lookups was reduced. The up⁃date of routing tables was supported by associating a counter with each bit in the bit vectors of the basic Bloom fil⁃ters. The theoretical analysis showed the proposed method is more efficient than the existing methods with less aver⁃aged number of times to probe into the route selection tables, and lowers its upper bound under the worst circum⁃stances. Experimental results validated the efficacy of the proposed method and proved the accuracy of the perform⁃ance analysis.关键词
路由查找/最长前缀匹配/前缀汇聚/Bloom滤波器/并行查询/路由表/IP网络/互联网Key words
IP routing lookups/longest prefix matching/prefix aggregation/Bloom filter/parallel query/route ta-ble/IP network/internet分类
信息技术与安全科学引用本文复制引用
于明,王振安,王东菊..基于Bloom滤波器的快速路由查找方法[J].哈尔滨工程大学学报,2014,(10):1247-1252,6.基金项目
国家自然科学基金资助项目（61172059）；辽宁省博士启动基金资助项目（20111022）． （）
