期刊文献+

一种适合于网络处理器的并行多维分类算法AM-Trie 被引量:6

AM-Trie: A Parallel Multidimensional Packet Classification Algorithm Fitting for Network Processor
下载PDF
导出
摘要 针对当前高速网络应用对分组分类算法的要求以及网络处理器体系结构的特点,提出了一种高速多维分组分类算法——AM-Trie算法(asymmetricalmulti-bittrie,非对称多杈Trie树).该算法具有搜索速度快,并行性、可扩展性良好的特点,特别适合于在网络处理器上实现.同时,给出了一种空间最优的启发式分类字段分段算法,并从理论上证明其在确定AM-Trie树层数的情况下使得存储空间最小.最后,基于IntelIXP2400网络处理器设计并实现了该算法.性能实测表明,该算法性能良好并具有很好的可扩展性,算法速度受规则库大小的影响很小,在各种情况下均达到了2.5Gbps的线速. Nowadays, many high speed Internet applications require high speed multidimensional packet classification algorithms. Based on the uniqueness of Network Processor, this paper presents a multidimensional classification algorithm--AM-Trie (asymmetrical multi-bit trie), AM-Trie is a high speed, parallel and scalable algorithm and very fit for the "multi-thread and multi-core" feature of the Network Processor. A heuristic field division algorithm is also presented, and it is proved theoretically that it can find out the minimum storage cost solution when the height of the AM-Tire is given. Finally, a prototype is implemented based on Intel IXP 2400 Network Processor. The performance testing result shows that AM-Trie is a high-speed and scalable algorithm; the throughput of the whole system is influenced little by the size of rules and it can reach 2.5 Gbps wire speed.
出处 《软件学报》 EI CSCD 北大核心 2006年第9期1949-1957,共9页 Journal of Software
基金 国家自然科学基金重大研究计划重点项目No.90412012 国家重点基础研究发展规划(973)No.2003CB314804 Juniper公司研究基金 Intel IXA大学研究计划
关键词 分组分类 网络处理器 并行算法 多维分类 AM-Trie packet classification network processor parallel algorithm multidimensional AM-Trie
  • 相关文献

参考文献12

  • 1aGupta P, McKeown N. Packet classification on multiple fields. In: Proc. of the ACM SIGCOMM 1999. 1999. 147-160. http://tinytera.stanford.edu/-nickm/papers/Sigcomm99.pdf
  • 2Baboescu F, Varghese G. Scalable packet classification. In: Proc. of the ACM SIGCOMM 2001. 2001. 199-210. http://www.cs.ucsd.edu/groups/sysnet/miscpapers/p2-baboescu.pdf
  • 3Singh S, Baboescu F, Varghese G, Wang J. Packet classification using multidimensional cutting. In: Proc. of the ACM SIGCOMM 2003. 2003.213-224. http://www.sigcomm.org/sigcomm2003/papers/p213-singh.pdf
  • 4Baboescu SSF, Varghese G. Packet classification for core routers: Is there an alternative to cams? In: Proc. of the IEEE INFOCOM 2003. 2003.53-63.
  • 5Lakshminarayanan ARK, Venkatachary S. Algorithms for advanced packet classification with ternary cams. In: Proc. of the ACM SIGCOMM 2005. 2005. 193-204.
  • 6Network processing forum (npf). http://www.npforum.org/
  • 7Network systems design conference.http://www.networkprocessors.com/
  • 8Wolf T, Franklin MS. Design tradeoffs for embedded network processors. In: Proc. of the ARCS 2002. 2002. 149-164.
  • 9Shah N. Understanding network processors. Technical Report, 2001. http://www.gigascale.org/pubs/338.html
  • 10McAuley AJ, Francis P. Fast routing table lookup using CAMs. In: INFOCOM (3). 1993. 1382-1391.

同被引文献48

引证文献6

二级引证文献7

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部