A Packet Classification Approach for Ternary Content-Addressable Memory Using Domain Transformation

doi:10.7652/xjtuxb201310017

您当前的位置：

首页 >

文章列表页 >

A Packet Classification Approach for Ternary Content-Addressable Memory Using Domain Transformation

更新时间：2025-07-09

- A Packet Classification Approach for Ternary Content-Addressable Memory Using Domain Transformation
- Vol. 47, Issue 10, Pages: 97-102(2013)
- 作者机构：
  
  国家数字交换系统工程技术研究中心,郑州,450002
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201310017
  CLC： TN914.42
- Online First：10 October 2013，
  
  Published：2013
- 稿件说明：
移动端阅览
A Packet Classification Approach for Ternary Content-Addressable Memory Using Domain Transformation[J]. 2013, 47(10): 97-102.
DOI：

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Influence of Structural Parameters on the Summer Operational Characteristics of a Three-Tower-in-One Indirect Air-Cooling System

Review of the Application of EBSILON Software in Combined Heat and Power System Optimization

Integrated and Joint Design Optimization of Centrifugal Compressor Impeller and Casing Treatment at Multiple Working Points

Energy Efficiency Optimization of the Cryogenic Air Separation Process for Electronic-Grade Ultra Pure Nitrogen

Bi-Level Multi-Obj ective Optimization of a Wind-Solar Coupled Hydrogen Production System Based on the Synergy of Hybrid Electrolyzer Arrays

Related Author

No data

Related Institution

No data

⁰