支持访问控制列表100Gbps线速查找的流水线方案研究
|
摘要
访问控制列表查找作为路由器的关键技术,可以根据IP数据包头信息对数据包进行更细粒度的分类,特别是对高速路由器中的快速查找技术的研究需求非常紧迫.访问控制列表根据几何分割可以生成决策树,查找过程可以通过遍历决策树加流水线的方式来实现.简单的流水线实现会带来内存利用不均匀的问题,为了解决该问题,本文采用双端口静态随机存储器技术,提出环形线性流水线结构来实现遍历树.该方法能均匀分布流水线中各段的内存,支持100Gbps线速处理.
Access control lists lookup as a key technology of the router classifies the IP packet more granular based on the information of IP packet header,which has important significance. The decision tree can be generated from access control lists,and the lookup process can be achieved by traversing the decision tree which can be implemented by simple pipeline to improve the throughout. However,it results in unbalanced memory allocation over the different pipeline stages. In this paper,we proposed a novel SRAM-based circular linear pipeline architecture for decision tree traversal. Our architecture achieves perfectly balanced memory distribution and can achieve access control lists lookup at 100 Gbps line rates theoretically.
Access control lists lookup as a key technology of the router classifies the IP packet more granular based on the information of IP packet header,which has important significance. The decision tree can be generated from access control lists,and the lookup process can be achieved by traversing the decision tree which can be implemented by simple pipeline to improve the throughout. However,it results in unbalanced memory allocation over the different pipeline stages. In this paper,we proposed a novel SRAM-based circular linear pipeline architecture for decision tree traversal. Our architecture achieves perfectly balanced memory distribution and can achieve access control lists lookup at 100 Gbps line rates theoretically.
引文
[1]Yadi Ma,Suman Banerjee.A smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classification[C].Proceedings of ACM Special Interest Group on Data Communication,2012:335-346.
[2]Le Hoang.A SRAM-based architecture for trie-based IP lookup using FPGA[C].Field-Programmable Custom Computing Machines,2008:33-42.
[3]Gupta P,McKeown N.Packet classification on multiple fields[C].Proceedings of ACM Special Interest Group on Data Communication,1999:147-160.
[4]Singh S,Baboescu F,Varghese G,et al.Packet classification using multidimensional cutting[C].Proceedings of ACM Special Interest Group on Data Communication,2003:213-224.
[5]Eatherton W,Varghese G,Dittia Z.Tree bitmap:hardware/software IP lookups with incremental updates[C].ACM SIGCOMM Computer Communications Review,2004,34(2):97-122.
[6]Basu A,Narlikar G.Fast incremental updates for pipelined forwarding engines[C].IEEE/ACM Transactions Network,2005,13(3):690-703.
[7]Baboescu F,Tullsen D M,Rosu G,et al.A tree based router search engine architecture with single port memories[C].Proc.International Speech Communication Association,2005.
[8]Kumar S,Becchi M,Crowley P,et al.CAMP:fast and efficient IP lookup architecture[C].Proc.Architectures for Networking and Communications Systems,2006:51-60.
[9]IEEE 803-3ba.Higher Speed Ethernet Standard[S].2010.
[10]Altera stratix V FPGA[EB/OL].http://www.altera.com.2012.
[2]Le Hoang.A SRAM-based architecture for trie-based IP lookup using FPGA[C].Field-Programmable Custom Computing Machines,2008:33-42.
[3]Gupta P,McKeown N.Packet classification on multiple fields[C].Proceedings of ACM Special Interest Group on Data Communication,1999:147-160.
[4]Singh S,Baboescu F,Varghese G,et al.Packet classification using multidimensional cutting[C].Proceedings of ACM Special Interest Group on Data Communication,2003:213-224.
[5]Eatherton W,Varghese G,Dittia Z.Tree bitmap:hardware/software IP lookups with incremental updates[C].ACM SIGCOMM Computer Communications Review,2004,34(2):97-122.
[6]Basu A,Narlikar G.Fast incremental updates for pipelined forwarding engines[C].IEEE/ACM Transactions Network,2005,13(3):690-703.
[7]Baboescu F,Tullsen D M,Rosu G,et al.A tree based router search engine architecture with single port memories[C].Proc.International Speech Communication Association,2005.
[8]Kumar S,Becchi M,Crowley P,et al.CAMP:fast and efficient IP lookup architecture[C].Proc.Architectures for Networking and Communications Systems,2006:51-60.
[9]IEEE 803-3ba.Higher Speed Ethernet Standard[S].2010.
[10]Altera stratix V FPGA[EB/OL].http://www.altera.com.2012.