利用域转换的三态内容寻址存储器报文分类算法

田乐; 陈庶樵; 黄慧群; 马腾

doi:10.7652/xjtuxb201310017

您当前的位置：

首页 >

文章列表页 >

利用域转换的三态内容寻址存储器报文分类算法

更新时间：2025-07-09

- 利用域转换的三态内容寻址存储器报文分类算法
- A Packet Classification Approach for Ternary Content-Addressable Memory Using Domain Transformation
- 西安交通大学学报 2013年47卷第10期页码：97-102
- 作者机构：
  
  国家数字交换系统工程技术研究中心,郑州,450002
- 作者简介：
- 基金信息：
  
  : 2013-03-06。作者简介: 田乐(1987—),男,硕士生;陈庶樵(通信作者),男,教授。基金项目: 国家“973计划”资助项目(2012CB315901);国家“863计划”资助项目(2011AA01A103);国家科技支撑计划资助项目(2011BAH19B01)
- DOI：10.7652/xjtuxb201310017
  中图分类号： TN914.42
- 网络首发：2013-10-10，
  
  纸质出版：2013
- 稿件说明：
移动端阅览
田乐, 陈庶樵, 黄慧群, 等. 利用域转换的三态内容寻址存储器报文分类算法[J]. 西安交通大学学报, 2013,47(10):97-102.

A Packet Classification Approach for Ternary Content-Addressable Memory Using Domain Transformation[J]. 2013, 47(10): 97-102.
田乐, 陈庶樵, 黄慧群, 等. 利用域转换的三态内容寻址存储器报文分类算法[J]. 西安交通大学学报, 2013,47(10):97-102. DOI： 10.7652/xjtuxb201310017.

A Packet Classification Approach for Ternary Content-Addressable Memory Using Domain Transformation[J]. 2013, 47(10): 97-102. DOI： 10.7652/xjtuxb201310017.

摘要

针对基于三态内容寻址存储器(TCAM)的报文分类存在范围扩张导致空间利用率较低的问题

提出了一种利用域转换的报文分类算法(DTRM)。首先将规则集独立的范围预编码算法中范围规则编码所需的比特数量由2

-1替换为任意值

从而能够利用TCAM中的所有冗余位进行编码

实现新范围域的构建

然后利用范围规则的分布特征

以规则集能够表示为较少的TCAM表项为原则

设计域转换函数

将规则集原始范围域转换为新构建的范围域。报文分类时

利用域转换函数将报文头部转换为新构建范围域中的某一数值或范围

并与TCAM表项进行并行比较

最终得到分类结果。仿真结果表明

与并行报文分类算法相比

DTRM算法的范围扩张因子由1.6减少至1.21

TCAM空间利用率由63%增加至82%

同时支持规则的增量更新。

Abstract

A novel algorithm using domain transformation

called DTRM

is proposed to solve the range expansion problem of ternary content-addressable memory(TCAM)

in which the rules containing range fields have to be represented by multiple TCAM entries. Firstly

the number of encoding bits of 2

-1 needed in the database independent range pre-encoding algorithm is replaced by any value so that the extra bits in TCAM entries can be fully used to encode and to construct a new range domain; Secondly

the relationships among rules are used to design a domain transformation function

and the original domain of each field is transformed to a new domain so that the classifier can be expressed by a small number of TCAM entries. When a packet arr

ives

the packet header is transformed to the new domain with the corresponding approach

and the transformed result is then compared with all the TCAM entries to get match rules. Simulation results and comparisons with the parallel packet classification algorithm show that the proposed algorithm not only reduces range expansion from 1.6 to 1.21 and increases the storage efficiency from 63% to 82%

but also gains better update performance.

关键词

Keywords

references

KOMPELLA R R, LEVCHENKO K, SNOEREN A C. Every microsecond counts: tracking fine-grain latencies with a lossy difference aggregator [C]∥ Proceedings of ACM SIGCOMM. New York, USA: ACM, 2009: 255-266.

NETLOGIC. Knowledge-based processors datasheet [EB/ OL]. [2013-02-24]. http:∥www.broadcom.com/

products/Knowledge-Based-Process-ors/Layers-2-4/NL91024.html.

IDT. 7 Network search engine datasheet [EB/OL]. [2009-08-20]. http:∥www.idt.com/products/

Knowledge-Based-Processors/75K72100.html.

SRINIVASAN V, VARGHESE G, SURI S. Fast and scalable layer for switching [C]∥Proceedings of ACM SIGCOMM: New York, ACM, 1998: 191-202.

SPITZNAGEL E, TAYLOR D, TURNER J. Packet classification using extended TCAMs [C]∥ Proceedings of 11th IEEE International Conference on Network Protocols. Piscataway, NJ, USA: IEEE, 2003: 120-131.

朱国胜, 余少华. 基于TCAM的范围匹配方法:C-TCAM [J]. 通信学报, 2012(1): 31-37.

ZHU Guosheng, YU Shaohua. Range matching method based on TCAM: C-TCAM [J]. Journal on Communications, 2012(1): 31-37.

BREMLER-BARR A, HENDLER D. Space efficient TCAM-based classification using gray coding [J]. IEEE Transactions on Computers, 2012, 61(1): 18-30.

ROTTENSTREICH O, KESLASSY I. Worst-case TCAM rule expansion [C]∥Proceedings of INFOCOM. Piscataway, NJ, USA: IEEE, 2010: 1-5.

LAKSHMINARAYANAN K, RANGARAJAN A, VENKATACHARY S. Algorithms for advanced packet classification with ternary CAMs [C]∥ Proceedings of ACM SIGCOMM. New York, USA: ACM, 2005: 193-204.

LIU Huan. Efficient mapping of range classifier into Ternary-CAM [C]∥Proceedings of 10th Symposium on High Performance Interconnects. Piscataway, NJ, USA: IEEE, 2002: 95-100.

BREMLER-BARR A, HAY D, HENDLER D. Layered interval codes for TCAM-based classification [C]∥ Proceedings of INFOCOM. Piscataway, NJ, USA: IEEE, 2009: 1305-1313.

TAYLOR D E, TURNER J S. ClassBench: a packet classification benchmark [J]. IEEE/ACM Transactions on Networking, 2007, 15(3): 499-511.

DAVID S J, JEFFREY D. A worst-case performance bounds for simple one-dimensional packing algorithms [J]. SIAM Journal on Computing, 1974, 3(4): 487-494.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

采用机器学习的大规模并行程序I/O性能建模与预测方法

融合物理信息与深度算子网络的变压器绕组热-流场快速计算方法

混合电解槽阵列协同的风光耦合制氢系统双层多目标优化

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建

采用试验设计方法的第三代CO2气体箔轴承箔片几何参数敏感性分析