作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (1): 271-273,. doi: 10.3969/j.issn.1000-3428.2010.01.094

• 开发研究与设计技术 • 上一篇    下一篇

基于CBF的分布式元组空间叉积算法

周粳迪,程东年,刘勤让,张 震   

  1. (解放军信息工程大学国家数字交换系统工程技术研究中心,郑州 450002)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-01-05 发布日期:2010-01-05

Distributed Tuple Space Crossproducting Algorithm Based on CBF

ZHOU Jing-di, CHENG Dong-nian, LIU Qing-rang, ZHANG Zhen   

  1. (National Digital Switching System Engineering & Technology R&D Center, PLA Information Engineering Unversity, Zhengzhou 450002)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-01-05 Published:2010-01-05

摘要: 针对分布式报文分类算法内存消耗大、可扩展性差的问题,提出分布式元组空间叉积算法。该算法采用独立域搜索引擎与树状多级聚合网络的分类结构,在聚合节点使用计数型布鲁姆过滤器(CBF)加速搜索,利用剪枝技术降低CBF内存消耗。仿真结果表明,对于 5×104条规模的9域规则库,聚合网络总内存消耗被控制在60 Kb内,该算法的查找速度达到100 Mp/s,且具有良好的可扩展性。

关键词: 分布式, 可扩展性, 元组空间, 计数型布鲁姆过滤器

Abstract: Aiming at the problem of huge memory consumption and poor scalability of distributed packet classification algorithm, this paper proposes distributed tuple space crossproducting algorithm. This algorithm uses a classification structure with independent field search engines and dendriform multilevel aggregation network, employs Counting Bloom Filter(CBF) in aggregation nodes to accelerate searching process, and utilizes pruning technology to reduce the memory consumption of CBF. Simulation results indicate that the total memory consumption of aggregation network is below 60 Kb when handling 9-field filter set of 5×104, the searching speed of this algorithm is 100 Mp/s, and the algorithm achieves better scalability.

Key words: distributed, scalability, tuple space, Counting Bloom Filter(CBF)

中图分类号: