Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-10-18
2004-02-24
Robertson, David L. (Department: 2186)
Data processing: database and file management or data structures
Database design
Data structure types
C711S108000
Reexamination Certificate
active
06697803
ABSTRACT:
FIELD OF INVENTION
The invention generally relates to performing comparison operations between or among digital data and generating data entries to be used for such operations. In particular, it is directed to computer processes, network communication systems, pattern recognition systems, or any system in which data entries are generated to be used for comparison operation with incoming data or with each other in order to make content-based decisions.
BACKGROUND OF INVENTION
There are many areas of digital data processing in which two or more digital data are compared with each other to derive relationships between or among them. Some examples are to classify data according to criteria, to parse packet data to identify their protocol type, and to perform database searches to name a few.
Data network communication systems are an area where these operations can be described in more detail. The increasing network traffic and the diversity of services provided by today's networks, require some distinction to be made for some type of services and packets. For example, network requirements for voice or video packet transmission are not the same as for File Transfer Protocol (ftp) application packet, or network management packets. The recent introduction of Quality of Service (QoS) and Class of Service (CoS) concepts in networks, are making packet classification more critical than it was in the past. In order to be able to prioritize and provide a required quality of service for a given packet, the packet has to be recognized as requiring certain QoS or CoS. Packet classification is an important step in providing QoS and CoS based services. The packets are classified according to the values contained within their headers, which indicate the type of their flow. The more precise the packet analysis, the better the classification. Many encapsulated headers may be looked-up to make a decision about the packet class.
In general, packet classification involves first identifying different incoming network packet headers and more specifically fields contained within these headers. The second step involves comparing the different header fields to fixed values or comparing the fields between themselves. In differentiated service systems, i.e., system implementing CoS and QoS whereby the type of service can be differentiated in order to increase the processing rates, the time allocated for packet header processing has to be minimized.
Many conventional packet classification techniques involving software are currently used or under development, which perform classifications using binary trees or accelerated search algorithms. These conventional techniques use a “perfect match” approach (exact equality comparison) wherein the search data are compared with a fixed value and either an exact match is found or a mismatch or miss is detected.
Recent advances in content addressable memories (CAMs) have provided an attractive hardware alternative for implementing such packet classification tasks to the conventional software techniques. CAMs perform parallel searches of specified data vs. stored data to output a match or a mismatch result designated by an address (in the case of a match). CAM cell structure can be either binary or ternary. Binary CAM cells can store either a logic “0” or “1”, while ternary CAM cells can store a logic “0”, “1”, or a “don't care” state. A “don't care” state or value, also denoted by “x” means that the value can be either a “0” or a “1”. Typically, these three states are encoded using two bits. For example, the value “0” can be stored as “00”, the value “1” as “01” and the “don't care” value as “10” with the fourth case “11” being an unused state.
Generally, both binary and ternary CAMs have mask registers that can be used during search operations to ignore or “mask” some of the bits for comparisons. In this description, a bit in the mask bit register that is set to “0” means that the corresponding bit in the input data (or the key) is to be compared to the corresponding bit in the CAM entries. A mask bit that is set to “1” in the mask bit register, means that the result of the comparison of the corresponding bit in the input data (key) with the corresponding bit in the CAM entries does not matter. In the case of ternary CAMs, bits that are set to “don't care” value in CAM entries, will always match the corresponding bits in the input data independently of the mask value for these bits. In the remainder of the description, concepts will be equally applicable to both binary and ternary CAMs unless otherwise specified.
The introduction of masking in binary CAMs and “don't care” values in ternary CAMs allow comparisons other than the “equality”. Comparisons such as “greater than”, “less than”, and “inequality” to a fixed value, as well as comparing two fields of incoming data can be implemented. Mask register and “don't care” features are used in several prior art implementations. For example, U.S. Pat. No. 5,920,886 Jul. 6, 1999 Feldmeier uses these features to implement hierarchical address filtering and translation. In this prior art reference, masks and the “don't care” values are used to perform comparisons extending the “equality” relationship but it uses a priority fields to represent hierarchical levels.
U.S. Pat. No. 4,996,666 Feb. 26, 1991 Duluk, Jr. describes a CAM system for performing fully parallel magnitude comparisons between ‘stored and input data based on a specific hardware implementation. The proposed CAM implementation is also capable of performing multiple comparisons on multiple fields of the CAM entries in one clock cycle. Comparisons such as “equality”, “less than”, “less than or equal to”, “greater than”, “greater than or equal to”, “inequality”, and “don't care” (field ignored) can be performed. The results of the different comparisons are stored in flag bits associated with each CAM entry. The more flag bits the CAM′ has, the larger is the number of comparisons and fields of the CAM. However, the proposed solution is a custom hardware solution requiring significant area. Furthermore, the patent fails to describe techniques of flexibly generating the CAM entries.
U.S. Pat. No. 3,320,592 May 16, 1967 Rogers et al. also describes a hardware implementation of a CAM based comparisons other than equality in one cycle. This implementation supports binary data storage only and is hardware-specific.
U.S. Pat. No. 3,389,377 Jun. 18, 1968 Cole describes a CAM capable of performing “greater than” and “less than” comparisons using a bit-sequential algorithm where bits of a field to be compared are scanned from the most significant bit to the least significant bit. This reference describes only binary CAMs with no masking capabilities with hardware-specific modifications to conventional CAMs. A non-flexible sensing scheme is also described which further constrains the flexibility of CAMs.
In summary, all these prior art solutions describe either software implementations or customized hardware solutions for performing comparison operations. In addition, none of the above prior art references describes a flexible and efficient way of generating searchable entries intended to minimize the number of entries required for performing the search and compare functions.
The invention therefore addresses techniques of generating searchable data entries in a storage medium. The invention also resides in techniques of performing comparison operation between an unknown value, against a fixed value or between fields within a digital stream. The present invention does not require any specific hardware implementation except the ability to use masks during a search operation, or alternately the ability to have “don't care” states stored. The storage medium can be of the type of CAM used; i.e. binary or ternary SRAM or DRAM-based CAMs can be used to implement the present invention.
SUMMARY OF INVENTION
Briefly stated, the invention is directed to a method of generating data entries to be written in a storage medium which supp
Kerins John C.
Miles & Stockbridge P.C.
Mosaid Technologies Inc.
Robertson David L.
LandOfFree
Generating searchable data entries and applications therefore does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generating searchable data entries and applications therefore, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating searchable data entries and applications therefore will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3315062