Browse Prior Art Database

Efficient Multi-Field Classification using SRAM-based emulated TCAM

IP.com Disclosure Number: IPCOM000010855D
Original Publication Date: 2003-Jan-28
Included in the Prior Art Database: 2003-Jan-28
Document File: 3 page(s) / 83K

Publishing Venue

IBM

Abstract

A method and data structure is provided for encoding ternary characters into binary characters.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 3

Efficient Multi-Field Classification using SRAM-based emulated TCAM

"Dynamic Multi-Field Packet Classification", J. van Lunteren and T. Engbersen, Proc. IEEE Globecom, November 2002, describes a multi-field packet classification scheme based on the concept shown in Figure 1 below, with the 'field searches' based on SRAM and the 'final search' being implemented in TCAM (Ternary Content Addressable Memory). Results of the various field searches are combined into an intermediate result vector, which is the input for the TCAM-based final search that determines the classification result: The rule with the highest priority that matches the (input) field values.

search d

intermediate result vector

field 1

field 2 field d

search 1

             final . 2searchsearch

. .


classification result

Figure 1

This proposal involves a technique to efficiently implement the final search using SRAM or DRAM technology by emulating the TCAM search in a novel way.

The conventional way of emulating a TCAM using SRAM or DRAM technology, is by representing a ternary vector using a binary 'base vector' and a binary 'mask vector', where the base vector specifies the values of the non-'don't care' bits (0,1) and the mask vector specifies the positions of these bits within the ternary vector. For example, an 8-bit ternary vector 'xx10x0x1' can be represented by a base vector '00100001' and a mask vector '00110101'. Testing if the original ternary vector matches a given input value can be performed by determining the bitwise Exclusive-OR product between the input value and the base vector, and determining the bitwise AND product of the first result and the mask vector: (<input value> XOR <base vector>) AND <mask vector>. If the result equals zero, then the ternary vector matches the input value. With this form of `TCAM-emulation', a ternary vector consisting of W bits is represented by two binary vectors consisting a total of 2*W bits.

The proposal involves a technique to represent ternary vectors consisting of W bits by less than 2*W binary bits, and, thus, improve the storage efficiency, by exploiting characteristics of the ternary vectors as will be explained below.

The following ternary vectors are examples of vectors that could be used by the above multi-field packet classification scheme:

1

[This page contains 1 picture or other non-text object]

Pa...