Multi-dimensional associative search engine

#The present invention relates to associative search engines (ASEs) and, in particular, to associative search engines for performing operations on multi-dimensional entries having associated data or actions, in response to a multi-dimensional input key.

#Packet classification, a well-known problem in computer science, can be defined as follows: given a data packet with certain predefined multiple components, also called packet fields, and an action taken on field-specific packet, this packet can be sorted on the basis of a different action to be taken. Classification is the action of sorting, among all the data packets, the packets that result in the same action.

#The set of rules that determines the class to which the packet belongs, is stored in an information base called Classification Information Base (CIB) or a Classifier. The relevant components or fields of a specific data packet classification are assembled into a construct called a Classification Key. The Classification Key forms a CIB query, which results in a specific action to be taken on the packet. Since the Classification Key incorporates multiple fields, and since the CIB results are multiple-field dependent, the result is defined as a Multi-Field Classification.

#The invention is herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of the preferred embodiments of the present invention only, and are presented in the cause of providing what is believed to be the most useful and readily understood description of the principles and conceptual aspects of the invention. In this regard, no attempt is made to show structural details of the invention in more detail than is necessary for a fundamental understanding of the invention, the description taken with the drawings making apparent to those skilled in the art how the several forms of the invention may be embodied in practice.

#In the drawings:

#FIG. 1 is a graphical illustration of the combination of two overlapping ranges and the resulting equivalent set of non-overlapping ranges;

#The present invention is a method of, and device performing operations on multi-dimensional entries having associated data or actions, in response to a multi-dimensional input key, using associative search engines. A novel concept, Multi-Dimensional Ranges (MDRs), is introduced, and the utility of such MDRs in compactly representing multi-field information bases is shown. The present invention is particularly suitable for packet classification in the communications field.

#The concept presented here provides the capability to decompose a d-Dimensional Range Information Base into d one-dimensional ranges, and each d-Dimensional Key into d one-dimensional keys, and thus transform the difficult search procedure in a d-Dimensional Information Base into d one-dimensional range searches, which can be readily performed by d one-dimensional Range Search Engines (RSEs). This concept can be used for a d-Dimensional Information Base with single (or “binary”) integers, which can be viewed as a special case of a d-Dimensional Range Information Base.

#The search algorithm presented involves the use of a Tag as a result (or associated data) of each one-dimensional range search, and concatenate this Tag with the next one-dimensional key searched in the next dimension of the Range Information Base in the following step. This sequence of d concatenated steps results in an Associated Data A (or Action A), which is associated with the d-dimensional range. The search algorithm steps can be pipelined to maximize the d-dimensional search throughput, regardless of the latency of the search procedure.