期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于TCAM的二维前缀报文分类算法 被引量：2

A TCAM-Based Two-Dimensional Prefix Packet Classification Algorithm
下载PDF
导出
摘要 报文分类已成为保障网络应用的服务质量及安全性的重要手段,而二维的前缀报文分类则是其中最为常用的.通过对规则冲突的分析,提出了一个基于三态内容可寻址存储器(TCAM)的二维前缀报文分类算法,该算法借助TCAM的并行查找能力,在一个指令周期内找到前缀的最长匹配,采用内存映像及相关数据结构消除了规则之间的冲突,实现了快速的二维前缀分类查找.与其他二维分类算法相比,该算法具有最小的查找时间复杂度和较小的内存空间复杂度. Packet classification (PC) becomes an important method to support the QoS and security of network, in which two-dimensional prefix PC is the most popular one. Based on the analysis of ruler conflict, a TCAM-based two-dimensional prefix PC algorithm was presented. This algorithm adopts the parallelism of TCAM to look up the longest prefix in one instruction cycle. Then it uses a memory image and associated data structures to eliminate the ruler conflicts, and performs a fast two-dimensional prefix PC. Compared with other algorithms, it has the least time complexity and less space complexity.
作者 王志恒 李晓勇 白英彩
机构地区 上海交通大学计算机科学与工程系
出处 《上海交通大学学报》 EI CAS CSCD 北大核心 2004年第1期9-13,共5页 Journal of Shanghai Jiaotong University
基金 IntelIXAProject(No.9078)
关键词 三态内容可寻址存储器 报文分类算法 二维前缀报文分类 ternary content addressable memory(TCAM) packet classification(PC) algorithm two-(dimensional) prefix PC
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献7

  • 1[1]Tsuchiya P. A search algorithm for table entries with non-contiguous wildcarding [EB/OL]. http: //citeseer. nj. nec. com/tsuchiya92search. html, 1992.
  • 2[2]Srinivasan V, Suri S, Varghese G,et al. Fast and scalable layer4 switching [A]. Proc ACM Sigcomm [C].Vancouver :ACM Sigcomm, 1998. 203- 214.
  • 3[3]Srinivasan V, Suri S, Varghese G. Packet classification using tuple space search[A]. Proc ACM Sigcomm [C]. Massachusetts :ACM Sigcomm, 1999. 135- 146.
  • 4[4]Gupta P, McKeown N. Packet classification on multiple fields [A]. Proc ACM Sigcomm [C]. Massachusetts :ACM Sigcomm, 1999. 147- 160.
  • 5[5]Wang Zhi-heng, Bai Ying-cai. Fast update algorithm for TCAM-based routing lookups [J]. Journal of Shanghai Jiaotong University, 2002,E (7): 8- 14.
  • 6[6]Devavrat Shah, Pankaj Gupta. Fast Updating algorithms for TCAMS [J]. IEEE Micro, 2001,21 (1): 36-47.
  • 7[7]Merit Inc. Ipma statistics[EB/OL]. http: ∥nic. merit. edu/ipma, 2002.

同被引文献22

  • 1Fu Jing, Rexford J. Efficient IP-address Lookup with a Shared Forwarding Table for Multiple Virtual Routers[C]// Proc. of the 4th International Conference on Emerging Networking Experiments and Technologies. Madrid, Spain ACM Press, 2008.
  • 2Psenak P, Mirtorabi S, Roy A, et al. Multi-Topology(MT) Routing in OSPF[EB/OL]. (2012-06-15). http://www.ietf. org/rfc/rfc4915.txt.
  • 3Srinivasan V, Varghese G. Faster IP Lookups Using Controlled Prefix Expansion[C]//Proc. of the 1998 Joint International Conference on Measurement and Modeling of Computer Systems. Madison, USA: ACM Press, 1998.
  • 4Eatherton W, Varghese G, Dittia Z. Tree Bitmap: Hardware/software IP Lookups with Incremental Updates[J].ACM SIGCOMM Computer Communication Review, 2004, 34(2): 97-122.
  • 5Song Haoyu, Turner J, Lockwood J. Shape Shifting Tries for Faster IP Lookup[C]/lProc. of the 13th IEEE International Conference on Netvcork Protocols. Boston, USA: IEEE Press, 2005.
  • 6Spitznagel E, Taylor D, Turner J. Packet Classification Using Extended TCAMs[C]//Proc. of the llth IEEE International Conference on Network Protocols. Busan, Korea: IEEE Press, 2003.
  • 7Gupta P, McKeown N. Classifying Packets with Hierarchical Intelligent Cuttings[J]. IEEE Micro, 1999, 20(1): 34-41.
  • 8Singh S, Baboescu F, Varghese G, et al. Packet Classification Using Multidimensional Cutting[C]//Proc. of Conference on Computer Communications. Karlsruhe Germany: ACM Press, 2003.
  • 9Gupta P, McKeown N. Packet Classification on Multiple Fields[J]. Computer Communication Review, 1999, 29(4): 147-160.
  • 10Lakshman T V, Stiliadis D. High Speed Policy-based Packet Forwarding Using Efficient Multidimentional Range Matching[J]. Computer Communication Review, 1998, 28(4): 203-214.

引证文献2

二级引证文献1

上海交通大学学报
2004年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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