Bit stream ternary match scheme

Details Bit stream ternary match scheme Bit stream ternary match scheme

2000-02-04

2003-09-02

Homere, Jean R. (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C365S049130

Reexamination Certificate

active

06615210

ABSTRACT:

BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates to an information match scheme and apparatus capable of providing Don't Care Bits for searching information in a digital information system, especially to a bit-stream ternary match scheme and apparatus capable of flexibly adjusting the design parameters according to the concern of cost, performance and power consumption.
B. Description of the Prior Art
The technology of digital information search has been widely applied in the area which requires large data storage and processing. The search speed and its correctness depend on the algorithm applied. The vigorous growth of Internet services and applications has made the search mechanism in large search pool and database systems more demanding. Apparently, the conventional exact match has been insufficient for such purposes. For the new search environment and applications, the technology of ternary match scheme has become the choice for the digital information search of next generation. Currently, the bit-stream ternary match scheme technology can be widely applied in the area, such as IP routing, packet flow classification, packet content-sensitive flow classification, and security system.
The difference between the ternary match scheme and the conventional exact match scheme is that it provides an additional “Don't Care bit” for the bit matching in addition to “0” and “1”. The “Don't Care Bit” is immune to the match results of “0” or “1”. With reference to
FIG. 1
, in a ternary bit-stream 11, each bit can be “1”, “1” or “X” , which respectively represent the bit value matches with “0”, “1” or “X” (either of them). In practical application, the value of two bits can be represented by one bit, i.e., 00→0, 01→1, 10→X or 11→X.
In general, the bit-stream ternary match scheme can be illustrated in
FIG. 2
which includes: a rule table
21
hand an information table
22
. The procedure of the match scheme is as follows: first, input a match information
23
consisting of a bit-stream. Then, perform a ternary match between the match information
23
and the entries of the rule table
21
. Finally, determine if there is a hit according to the match result. If not, it indicates that there is no hit in the rule table
21
. If yes, use the sequence number of the rule (rule ID) matched in the rule table
21
as an index to lookup the information table
22
.
Refer to
FIG. 3
for showing the format of the rule table
21
. Each rule table
21
contains multiple rules. And each rule consists of a ternary bit-stream. The size of the rule table
21
is defined according to the maximum allowable length of the rules (W-bit) and the maximum number of rules (L). Each rule has a piece of correspondent information stored in the information table
22
. The sequence of each piece of information in the information table
22
is correspondent to the sequence of the rules in the rule table
21
. In that case, the number of the pieces of information stored in the information table
22
is also L. The sequence of the rules in the rule table
21
is arranged according to its priority order. The priority decreases as the rule ID number increases. For this reason, when there are more than two rules matched with the information in the information table
21
, the rule ID with the highest priority will be selected.
However, the bottleneck for the current bit-stream ternary match scheme is that it cannot flexibly adjust the design parameters and search speed according to the concern of cost. Consequently, the cost/performance issue for implementing the bit-stream ternary match scheme and increasing the search speed is very high for large search spool and database systems.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide a method and apparatus for bit-stream ternary match scheme with design flexibility, thereby to speed up the search in constant time.
It is another object of the present information to provide a method and apparatus for bit-stream ternary match scheme which can flexibly adjust the design parameters according to the concern of cost, performance, and power consumption, thereby to meet the requirement of different needs.
Accordingly, it is an aspect of the present invention to provide an apparatus for bit-stream ternary match scheme. The apparatus of the invention includes: multiple memory tables and equal number of corresponding selectors, a product module, and a priority encoder. Each memory table includes multiple memory banks. After the match information is input to the ternary match module, it is divided into several sub-bit-streams. Then, each sub-bit-stream is input to a correspondent selector for obtaining the content of a selected memory bank. The content of the memory bank contains the bit-streams after pre-computation procedure. Then, the output of each selector is forwarded to the product module to compute an unencoded match result. Finally, the unencoded match result is forwarded to the priority encoder for generating the encoded match result and match flag. If the match flag is negative, it indicates that there is no match between the match information and the rule table. If the result is positive, the encoded match result serves as an index for looking up the information table.
In an aspect of the present invention, a method for bit-stream ternary match scheme is provided. The method includes the steps of: (a) Determine the space of a rule table according to a maximum allowable bit-length (W) of a rule, and the number of maximum allowable rules (L). (b) Divide the maximum allowable bit-length (W) into N+1 sub-bit-streams, where N is an integer. (c) Determine N+1 memory tables and N+1 selectors according to the number of sub-bit-streams of the step (b). (d) Determine the scale of each memory table and each selector according the bit-length of correspondent sub-bit-stream of the step (b). (e) Encode a plurality of rules according to a pre-computation procedure and generate a plurality of encoded entries. (f) Sequentially store the plurality of encoded entries in the rule table. (g) Send the output of each of the N+1 selectors into a product module to compute an unencoded match result in response to match information. (h) Forward the unencoded match result of the product module to a priority encoder to perform priority encoding and generate an encoded match result and a match flag. And (i) determine if there is a match information existed according to the match flag. When the match flag indicates a negative result, there is no match between said match information and the rule table. On the other hand, when the match flag indicates a positive result, the encoded match result acts as an index for searching the information table.
According to the concern of cost, performance and power consumption, the present invention can be more flexible to divide the execution steps into several stages following the pipeline technology. Thus, the design parameters can be flexibly adjusted. Eventually, the throughput can be efficiently improved, thereby to reduce the power consumption. Moreover, the present invention can largely reduce the search time into constant time and save the cost according to a desirable performance.
Further scope of the applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.
BRIEF DESCRIPTION OF THE DRAWINGS
These and other objects and advantages of the present invention will become apparent by reference to the following description and accompanying drawings, which are given by way of illustration only, and thus are not limitative of the present invention, and

Affiliated with

Also associated with

Rating

Bit stream ternary match scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Bit stream ternary match scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit stream ternary match scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3107855