全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

基于Bloom滤波器的快速路由查找方法

DOI: 10.3969/j.issn.1006-7043.201306057

Keywords: 路由查找, 最长前缀匹配, 前缀汇聚, Bloom滤波器, 并行查询, 路由表, IP网络, 互联网

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对IP路由查找中的最长前缀匹配问题,提出了一种基于Bloom滤波器的快速路由查找方法。首先,通过建立首字节索引表,减少了需要并行查询的Bloom 滤波器的数量。其次,基于IP地址前缀长度分布的不均匀性对Bloom滤波器组的设置进行了优化,降低了查询过程对Bloom滤波器总数的需求。最后,将基本Bloom滤波器位向量中的每一比特位与一个计数器相关联,实现了对路由更新的支持。理论分析表明,与现有方法相比,利用该方法进行路由查找可以实现更低的选路表平均探测次数,并在最坏情况下具有更低的平均探测次数上界。实验结果验证了该方法的有效性及相关理论分析的正确性。

References

[1]  NIU Yun, WU Liji, ZHANG Xiangmin. An IPsec accelerator design for a 10Gbps in-line security network processor[J]. Journal of Computers (Finland), 2013, 8(2): 319-325.
[2]  胥小波,郑康锋,李丹,等.基于并行BP神经网络的路由查找算法[J].通信学报, 2012, 33(2): 61-68.XU Xiaobo, ZHENG Kangfeng, LI Dan, et al. Routing lookup algorithm based on parallel BP neural network [J]. Journal of Communications, 2012, 33(2): 61-68.
[3]  袁博,汪斌强,王志明. 并行多流水绿色路由查找架构和算法[J]. 西安电子科技大学学报, 2012, 39(2): 145-152.YUAN Bo, WANG Binqiang, WANG Zhiming. Green IP lookup architecture and algorithm based on the parallel multi-pipeline[J]. Journal of Xidian University, 2012, 39(2): 145-152.
[4]  SARANG D, PRAVEEN K, TAYLOR D E. Longest prefix matching using bloom filters[J]. IEEE/ACM Transactions on Networking, 2006, 14(2): 397-409.
[5]  LIM Hyesook, LIM Kyuhee, LEE Nara, et al. On adding Bloom filters to longest prefix matching algorithms[J]. IEEE Transactions on Computers, 2014, 63(2): 411-423.
[6]  SONG Haoyu, KODIALAM M, HAO Fang, et al. Building scalable virtual routers with trie braiding[C]//Proceedings of IEEE INFOCOM 2010. San Diego, USA, 2010: 14-19.
[7]  LUO Layong, XIE Gaogang, XIE Yingke, et al. A hybrid hardware architecture for high speed IP lookups and fast route updates[J]. IEEE/ACM Transactions on Networking, 2014, 22(3): 957-969.
[8]  李鲲鹏,兰巨龙. 基于TCAM的高效浮动关键词匹配算法[J]. 计算机工程, 2012, 38(4): 269-274.LI Kunpeng, LAN Julong. Efficient unfixed keywords matching algorithm based on TCAM[J]. Computer Engineering, 2012, 38(4): 269-274.
[9]  GUO Deke,LIU Yunhao, LI Xiangyang, et al. False negative problem of counting Bloom filter[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(5): 651-664.
[10]  ROTHENBERG C E, MACAPUNA C A B, VERDI F L, et al. The deletable Bloom filter: a new member of the Bloom family[J]. IEEE Communications Letters, 2010, 14(6): 557-559.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133