Patent for Sale:

Contents Addressable Memories (CAM) Technology    

For CAM, the invention involves methods for accelerating the prefix match search operation without increasing circuit size.

Overview

The feature of this CAM is its capability to carry out the longest prefix match search operation correctly without pre-sorting a search table after the search table is updated.

The longest prefix match search operation is necessary for a router function. In a router, the search table that stores routing information is updated every 30 seconds in order to reflect disconnection of existing routes and addition of new routes.

Primary Application of the Technology

Internet infrastructure

The Problem Solved by the Technology

- Accelerating the execution speed of IPv6 (IP address: 128 bits) equivalent to that of IPv4 (IP address: 32 bits)
- Reducing the total cost by removing unnecessary hardware and CPUs and narrowing the chip area
- Setting the broad price range so that both the low-end market and the high-end market would be available.
- Reducing the total cost by removing the expensive CPU for sorting, or by using the CPU for the other means of processing.
- Providing multiple searching modes in a single chip
- Accelerating the processing speed of dynamic packet filtering
- Employing the first-order control taking advantage of sequent uploading during LPM

Competitive Advantage

The special CAM developed here can update its search table in order to reflect disconnection of existing routes and addition of new routes on an arbitrary timing as same as an ordinary static RAM. During the transfers of the packet, with the exception of the routing information of the packet, the search table of this CAM can be updated. Therefore, searching capability of the CAM reaches its maximum effect.

By comparison, in conventional CAM, the longest prefix match search operation is realized by the combination of pre-sorting and the priority encoder. Whenever even one route is added or disconnected, the conventional CAM need to sort its search table again. While the sorting table is updated, the conventional CAM requires re-sorting and it can not carry out the longest prefix match search operation during the sorting.

Patent Summary

U.S. Patent Classes & Classifications Covered in this listing:

Class 711: Electrical Computers And Digital Processing Systems: Memory

This class provides, within an electrical computer or digital data processing system, for the following processes and apparatus 1. for addressing memory wherein the processes and apparatus involve significant address manipulating (e.g., combining, translating, or mapping and other techniques for formatting and modifying address data) and are combined with specific memory configurations or memory systems; 2. for accessing and controlling memory (e.g., transferring and modifying address data, selecting storage devices, scheduling access); and 3. for forming memory addresses (e.g., virtual memory addressing, address translating, translation-lookaside buffers (TLBs), boundary checking, and page mode).

Subclass 108: Content addressable memory (CAM)
Subclass 128: Associative
Subclass 156: Status storage

Class 365: Static Information Storage And Retrieval

Apparatus or corresponding processes for the static storage and retrieval of information. For classification herein, the storage system must be (1) static, (2) a singular storage element or plural elements of the same type, (3) addressable.

Subclass 189.07: Including signal comparison
Subclass 230.03: Plural blocks or banks

Class 710: Electrical Computers And Digital Data Processing Systems: Input/Output

This class provides, within a computer or digital data processing system with the following processes or apparatus for 1. transferring data from one or more peripherals to one or more computers or digital data processing systems for the latter to process, store, or further transfer or for transferring data from the computers or digital data processing systems to the peripherals; 2. for interconnecting or communicating between two or more components connected to an interconnection medium (e.g., a bus) within a single computer or digital data processing system; 3. for preventing access to a shared resource of a computer or digital data processing system; 4. for granting access to a shared resource of a computer of digital data processing system by one of a plurality of components of the computer or digital data processing system by interrogating each of the components in a predetermined order; 5. for determining which of a plurality of components of a computer or digital data processing system contending for access to a shared resource shall be granted access at any one time based upon a predetermined criteria; and 6. for stopping, halting, or suspending a current processing function within a computer or digital data processing system.

Subclass 49: Masking

Class 707: Data Processing:Database And File Management Or Data Structures

This is the generic class for data processing apparatus and corresponding methods for the retrieval of data stored in a database or as computer files. It provides for data processing means or steps for generic data, file and directory upkeeping, file naming, and file and database maintenance including integrity consideration, recovery, and versioning. There are three main divisions: 1. database and file accessing; 2. database schema and data structure; 3. file and database maintenance.

Subclass E17.035: Using parallel associative memories (EPO)

Class 709: Electrical Computers And Digital Processing Systems: Multicomputer Data Transferring

This class provides for an electrical computer or digital data processing system or corresponding data processing method including apparatus or steps for transferring data or instruction information between a plurality of computers wherein the computers employ the data or instructions before or after transferring and the employing affects said transfer of data or instruction information. The class includes - process or apparatus for transferring data among a plurality of spatially distributed (i.e., situated, at plural locations) computers or digital data processing systems via one or more communications media (e.g., computer networks).


Class 370: Multiplex Communications

This is the generic class for multiplexing or duplexing systems, methods, or apparatus.

Subclass 392: Processing of address header for routing, per se
Subclass 395.32: Employing particular searching function (e.g., hashing, alternate, re-routing)