期刊文献+

联合元组空间和位图设计的二维分组分类算法 被引量:1

Joint design of tuple space and bitmap for two-dimensional packet classification
下载PDF
导出
摘要 基于维度分解思想,设计并实现了一种联合元组空间和位图技术的二维分组分类算法(TB,joint tuple space and bitmap)。TB算法首先分别对源IP地址和目的IP地址进行单维匹配,然后在单维匹配的结果上运用交叉组合形成访问元组空间的路线,最后通过位图过滤技术进一步减少访问元组空间的个数,获得最终匹配的多维规则。相比传统的元组空间算法,TB结构清晰简洁易于更新和实现,TB算法拥有更好的时间和空间性能。实验证明,TB算法平均访问内存次数低于代表算法RSFR约26.6%,空间性能平均低于RSFR算法35.1%。 Based on dimension decomposition idea,a high-performance two-dimensional packet classification algorithm by jointing tuple space and bitmap technology,called TB,was designed and implemented.Firstly,TB processes one-dimension matching for SIP and DIP respectively,then it forms tuple space access route by applying the cross-combination method to the matching results in the first step,finally,to reduce the number of required accessing tuple space,TB obtains the multi-dimensional matched rule by adapting bitmap filtering technique to filter tuple space.Compared to traditional tuple space algorithm,the structure of TB is clearer,more concise and easier to update and implement,TB also has better time and space performance.The experimental results show that TB algorithm saves 35.1% of the space requirement than RSFR algorithm and the number of average memory accesses lower than RSFR 26.6%.
出处 《通信学报》 EI CSCD 北大核心 2011年第9期96-102,共7页 Journal on Communications
基金 国家自然科学基金资助项目(61003305) 国家重点基础研究发展计划("973"计划)基金资助项目(2007CB310702) 博士点基金资助项目(20100161120022) 湖南省自然科学基金资助项目(11JJA003)~~
关键词 分组分类 元组空间 位图 维度分解 packet classification tuple space bitmap dimension decomposition
  • 相关文献

参考文献11

  • 1BABOESCU F, VARGHESE G. Scalable packet classification[J]. IEEE/ACM Transactions on Networking, 2005, 13(1):2 - 14.
  • 2LUNTEREN J V, ENGBERSEN T. Fast and scalable packet classification[J]. IEEE Journal of Selected Areas in Communications, 2003, 21(4): 560-571.
  • 3PI-CHUNG W, CHUN-LIANG L, CHIA-TAI C, et al. Performance improvement of two-dimensional packet classification by filter rephrasing[J]. IEEE /ACM Transactions on Networking, 2007, 15(4): 906-917.
  • 4ZANE F, NARLIKAR G, BASU A. Coolcams: power-efficient TCAMs for forwarding engines[A]. Proc of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications[C]. San Francisco, 2003, 42-52.
  • 5SRINIVASAN V, SURI S, VARGHESE G Packet classification using tuple space search[A]. Proc, of ACMSIGCOMM 1999[C]. Cambridge, Massachusetts, United States, 1999.135-146.
  • 6BABOESCU F, SUMEET S, GEORGE V. Packet classification for core touters: is there an alteraative to CAMs?[A] Proc of IEEE INFOCOM 2003[C]. Toronho, Ontarion, Canada, 2003, 53-63.
  • 7FELDMAN A, MUTHUKRISHNAN S. Tradeoffs for packet classification[J]. IEEE INFOCOM, 2000.1193-1202.
  • 8DAVID E T, JONATHAN S T. ClassBench: a packet classification benchmarks[A]. Proceedings of IEEE/ACM Trans on Networking[C]. San Francisco, CA, USA, 2007,499-511.
  • 9LAKSHMAN T V, STIDIALIS D. High speed policy-based packet forwarding using efficient multi-dimensional range matching [A]. Proc of .ACM SIGCOMM 1998[C]. Vancouver, British Columbia, Canada, 1998, 203-214.
  • 10MALDVOGEL M, VARGHESE G TURNER I, et al. Scalable high speed IP routing lookups[A]. Proc of ACM SIG-COMM, Cannes, France, 1997. 25-36.

同被引文献9

  • 1Chang Y K, Chen H C. Layered cutting scheme for packet classification [ C ] // IEEE International Conference on Advanced Information Networking and Applications(AINA). Biopolis: IEEE, 2011:675 - 681.
  • 2Gupta P, McKeown N. Classifying packets with hierarchical intelligent cuttings[J ]. IEEE Micro, 2000,20( 1 ) : 34 - 41.
  • 3Chen Y H, Oguntoyinbo O. Power efficient packet classification using cascaded Bloom filter and off-theshelf ternary CAM for WDM networks [ J ]. Computer Communications, 2009,32(2) :349 356.
  • 4Pao D, Li Y K, Zhou P. Efficient packet classification using TCAMs[J ]. Computer Networks, 2006,50 (18) : 3523 - 3535.
  • 5Priya A G A, Lim H. Hierarchical packet classification using a Bloom filter and rule-priority tries [ J ]. Computer Communications, 2010,33(10) :1215 - 1226.
  • 6Wicaksana A, Sasongko A. Fast and reconfigurable packet classification engine in FPGA-based firewall [ C ] // International Conference on Electrical Engineering and Informatics( ICEEI). Bandung, 2011 : 1 - 6.
  • 7Jiang W, Prasanna V K. Scalable packet classification on FPGA [ J ]. IEEE Transactions on Very Large Scale Integration ( VLSI ) Systems, 2011,99 : 1 - 13.
  • 8Wang Y G, Zhang T, Zheng Y F, et al. Realization of FPGA-based packet classification in embedded system[Cl// Instrumentation and Measurement Technology Conference. Singapore: IEEE, 2009 : 938 - 942.
  • 9谢鲲,赵姣姣,张大方,毕夏安.基于计数布鲁姆过滤器的快速多维包分类算法[J].电子学报,2010,38(5):1046-1052. 被引量:8

引证文献1

二级引证文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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