面向NDN中名字查找的哈希布鲁姆过滤器  

Hash Bloom Filters for Name Lookup in Named Data Networking

作　　者：李玮 张大方 徐冰 

机构地区：[1]湖南大学信息科学与工程学院,长沙410082

出　　处：《电子科技大学学报》2017年第5期734-740,共7页Journal of University of Electronic Science and Technology of China

基　　金：国家973项目(2012CB315805);国家自然科学基金(61173167;61472130)

摘　　要：该文设计了一种面向NDN中名字查找的哈希布鲁姆过滤器(HBF)。HBF由位于片内存储器中的g个计数器布鲁姆过滤器(CBF)、g个计数器和位于片外存储器中的g个哈希表组成,每个哈希表与1个CBF和1个计数器关联。为了避免因部分CBF存入名字过多而导致HBF的高误判率,HBF通过二次哈希选择算法将NDN路由器中FIB/CS/PIT表项完整信息均匀分散保存于g个CBF和g个哈希表中,同时也利于数据包转发的并行处理。理论分析和实验结果表明在名字查找过程中,HBF利用片内存储器中CBF的定位与过滤作用,大幅度减少片外存储器的访问开销,提高数据包转发速率,有效避免泛洪攻击。To provide quick name lookup technique, the paper designs a Hash bloom filter （HBF）. The HBF consists of g on-chip counter bloom filters （CBFs）, g on-chip counters and g off-chip Hash tables. Each Hash table is associated with a CBF and a counter. To reduce the false positive rate introduced by unbalanced name insertion in to CBFs, we propose two-Hash-choice algorithm which evenly disperses the FIB/CS/PIT entries into g Hash tables and CBFs. Moreover, HBF has a good feature of parallel processing of data packet forwarding because HBF adopts multiple Hash tables and CBFs. Theoretical and simulated results demonstrate that HBF can achieve very efficient name lookup by well utilizing the on-chip memory through localization and filtering function of CBF. Therefore, the proposed HBF improves data packet forwarding rate and effectively avoids flooding attacks.

关 键 词：数据包转发速率 哈希布鲁姆过滤器 命名数据网络 名字查找 二次哈希选择算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]