A Fast Head-Tail Expression Generator for TCAM -- Application to Packet Classification

Author

Syafalni, Infall ; Sasao, Tsutomu

Author_Institution

Dept. of Comput. Sci. & Electron., Kyushu Inst. of Technol., Iizuka, Japan

fYear

2012

fDate

19-21 Aug. 2012

Firstpage

27

Lastpage

32

Abstract

This paper presents a method to generate head-tail expressions for Ternary Content Addressable Memories (TCAMs). First, we derive head-tail expressions for interval functions. We introduce a fast prefix sum-of-product (PreSOP) generator (FP) which generates products using the bit patterns of the endpoints. Next, we propose a direct head-tail expression generator (DHT). Experimental results show that DHT generates much smaller TCAM than FP. The proposed algorithm is useful for simplified TCAM generator for packet classification.

Keywords

Internet; content-addressable storage; pattern classification; DHT; FP; Internet; PreSOP; TCAM; direct head-tail expression generator; fast head-tail expression generator; packet classification; prefix sum-of-product generator; ternary content addressable memories; Absorption; Associative memory; Generators; Indexes; Internet; Random access memory; Vectors; TCAM simplification; head-tail expression; packet classification;

fLanguage

English

Publisher

ieee

Conference_Titel

VLSI (ISVLSI), 2012 IEEE Computer Society Annual Symposium on

Conference_Location

Amherst, MA

ISSN

2159-3469

Print_ISBN

978-1-4673-2234-8

Type

conf

DOI

10.1109/ISVLSI.2012.47

Filename

6296443