FFS search and edit pipeline separation

The present invention is directed to fast flexible search and edit pipeline separation. A system suitable for providing a search may include a central controller and at least one search engine. The central controller is suitable for implementing search and edit operations. The at least one search engine is communicatively coupled to the central controller. The central controller performs parallel execution of a search operation and an edit operation through utilization of the at least one search engine.

FIELD OF THE INVENTION

The present invention generally relates to the field of search engines, and particularly to fast flexible search and edit pipeline separation.

BACKGROUND OF THE INVENTION

Data communications is most often accomplished by sending a group of data in a packet, together with the address of the location for which the data is intended. For instance, a search for data may be accomplished by conducting a binary search based on the address or prefix where the data are retained, or stored, and the data returned in a packet to the requesting address. The search is conducted by a lookup procedure that matches the query address with the stored address.

However, lookup procedures may be a major source of bottlenecks in high performance compliers and routes. Lookup techniques are used in various compilers such as compilers used in designing semiconductor and integrated circuit chips, and in network applications such as Internet address (URL) lookup in high performance data routers where large search tables or databases are employed. Searching large tables or databases may require increased time or hardware requirements, or both, resulting in more expensive systems in terms of increased search delays and larger memories. Problems associated with such lookups increase with the size of the table or database, may increase with the address length encountered, increase with traffic flow, and the introduction of higher speed links may result in a bottleneck. For example, with use of the next generation IPv6 protocol, which uses 128-bit addresses, such problems may increase as more numerous and longer addresses are encountered.

Additionally, in systems employing present search techniques, edit operations may interfere with search operations, thereby greatly affecting the efficiency and performance of the system as a whole.

Therefore, it would be desirable to provide improved search engine architecture for efficient operation.

SUMMARY OF THE INVENTION

Accordingly, the present invention is directed to fast flexible search and edit pipeline separation. In a first aspect of the present invention, a system suitable for providing a search includes a central controller and at least one search engine. The central controller is suitable for implementing search and edit operations. The at least one search engine is communicatively coupled to the central controller. The central controller performs parallel execution of a search operation and an edit operation through utilization of the at least one search engine.

In a second aspect of the present invention, a search engine suitable for providing a search includes a memory, a priority controller, an edit module, a search module and an address cache. The memory is suitable for storing electronic data and the priority controller is communicatively coupled to the memory. The edit module is communicatively coupled to the priority controller, the edit module configured to perform calculations for an edit operation. The search module is communicatively coupled to the priority controller, the search module configured to perform calculations for a search operation. The address cached is communicatively coupled to the memory and the priority controller, the address cache suitable for storing electronic data. The priority controller manages access to the memory by the edit module, search module and address cache.

In a third aspect of the present invention, a system suitable for providing a search includes a central controller and a plurality of search engines. The central controller is suitable for implementing search and edit operations and suitable from inputting and outputting external communications. The plurality of search engines are arranged in zero through k levels, wherein a k level search engine of the plurality of search engines is communicatively coupled to the central controller and a zero level search engine of the plurality of search engines is communicatively coupled to the central controller. The central controller performs parallel execution of a search operation and an edit operation through utilization of at least one of the plurality of search engines.

DETAILED DESCRIPTION OF THE INVENTION

Referring generally now toFIGS. 1 through 2, exemplary embodiments of the present invention are shown. The present invention provides the ability to perform edit operations, such as insert and delete, without interrupting searches being performed at the same time. For instance, this invention may be applied to fast flexible search high speed lookup engines for perfect and longest prefix matches, such as the search engines described in U.S. patent application Ser. No. 09/679,313, titled “Fast Flexible Search Engine for Perfect Match,” filed Oct. 4, 2000; and U.S. patent application Ser. No. 09/679,209, titled “Fast Flexible Search Engine for Longest Prefix Match,” filed Oct. 4, 2000, which are herein incorporated by reference in their entirety, and is applicable for any search engine with similar pipeline structures, as well as other structures contemplated by a person of ordinary skill in the art without departing from the spirit and scope of the present invention.

For example, a sorted binary search tree may be provided having a fixed number of levels, in which the bottom vertices contain keys and associated data. The hierarchy vertices or nodes may contain one key for each child vertex and a vertex address pointing to the vertex containing that key. The keys are arranged in a predetermined order, such as address order, across the vertices of each level such that a search into a given hierarchy vertex is directed into a specific group of keys. The search tree is structured so that all search paths are the same length. Nodes or vertices may be inserted and deleted at most levels, thereby maintaining the equal length to all search paths. The tree may employ perfect matching techniques which seek a perfect match between the input or query key and the key being sought. If a perfect match is not returned, the search reports a false return.

In some instances of longest prefix searching, the prefix may be any length, such as up to W−1, where W is the maximum length of an address. Since W=32 in IPv4 Protocol and W=128 in IPv6 protocol, the prefix may be any length between 1 and 31 bits in IPv4 protocol and between 1 and 127 bits in IPv6 Protocol. Thus, a vast number of variable-length prefixes may exist in both IPv4 and IPv6 protocols. The number of memory accesses required by traditional perfect match search of variable length prefixes increases with the number of prefixes. Consequently, the number of memory accesses may be large, thereby slowing the search process. One method utilized to address this problem is described in co-pending application titled “Fast Flexible Search Engine for Longest Prefix Match” referenced previously, which describes a system and method for establishing a single length for all prefixes and subprefixes, such as equal to the length of the addresses.

Such improvements may be further utilized through implementation of the present invention. The present invention provides a protocol for search engine operation interaction, which allows the parallel execution of an uninterrupted search stream on one side and one of the edit operations, such as insert and delete, on the other side. Preferably, the execution latency of the search operation remains the same as without simultaneous edit operation. The search operation may start at any clock rate.

Referring now toFIG. 1, an exemplary embodiment of the present invention is shown wherein an architecture and communication between search engine levels is shown. By employing the present invention, a pipeline architecture may be supplied that allows uninterrupted execution of search operations and an insert and delete operation. The present invention may be applied to a variety of search engines, and thus the present discussion will not differentiate the types of the search engine which may be employed, such as perfect, longest prefix match (the pipeline structure is the same for both cases) and like structures as contemplated by a person of ordinary skill in the art.

The engine100contains k+1=_numb_level level blocks104,106,108&110and a central controller102. The number _numb_level is the depth of the search tree, such as a search tree utilized in perfect match search engine. The level index increases from 0 for the bottom tree level110to the maximal value k=(_numb_level−1) for the top104. The top level104corresponds to the root tree vertex. Any two neighbor levels are connected in both directions. The central controller102is connected with the top104and bottom levels110in both directions too. The external pins112&114belong to the central controller102.

There are three sets of connections: one for the search116, a second for the edit operation118and a third one for control of an address cache120. In an embodiment, the search connections116progress in one direction: from the central controller102to the top level104, from the top level104to the (k−1)-th level106, from (k−1)-th level106to 1-th level108, from the 1-th level108to the bottom level110, and from the bottom level110to the central controller102.

The edit connections118may progress in both directions. The cache connections120are similar to the search connections, but a signal is not provided from the bottom level to the central controller. The cache bus may be employed utilizing a single wire.

The search bus may contain the following: (1) key for search; (2) address in memory of the next tree vertex; (3) degree of the tree vertex; (4) mask of subprefixes in the longest prefix match case; and like data as contemplated by a person of ordinary skill in the art.

The connection from the bottom level110to the central controller102may include searched data too. The edit bus has the same field and a few control bits to specify commands from one engine level to another.

In contemplated embodiments, the execution time of edit operation is reciprocally proportional to the input search stream density.

Referring now toFIG. 2, an embodiment of the present invention is shown wherein contents of an exemplary search engine200are described. Each engine stage104,106,108&110(FIG. 1) may contain a separate processor and a memory202. The memory stores vertices of the corresponding tree level. The processor has 4 main parts: a search module204; an edit module206; a memory address cache210; and a priority controller208. Connections between modules202,204,206,208&210are shown inFIG. 2.

The search module204performs calculations for the search operation. The search module204obtains input signals from similar search module of the upper neighbor (previous) level and sends output signals to the search module of the next level. For instance, a search module of the (K−1)-th engine level106may obtain output signals from the K-th engine level104(FIG. 1). The input of the top search module104may be obtained from the central controller102. The output of the 0-th engine level110search module is provided to the central controller102.

The search module204communicates with the memory202through the priority controller208. For instance, the search module204may send the address “A” and a control bit “R” to the priority controller208, which may be 1 if a search is in an active state and zero otherwise. The search module204receives a data “DO” from the memory202.

The edit module206performs calculations for insert and delete operations. The edit module has inputs and outputs from both neighboring levels. For instance, referring again toFIG. 1, the (K−1)-th engine level may send and receive data from both the k-th engine level104and the 1-th engine level108. The top and bottom edit modules, as included in the k-th engine level104and 0-th engine level110, have connections with the central controller102.

The edit module206connects with the level memory202through the memory controller (priority controller208). The edit module206sends to the priority controller208the address “A” and control bits “R” and “W”. The bit “R” may be equal to 1, if edit module206tries to read from memory202. The bit “W” is equal to 1 if edit module206tries to write into the memory202. The edit module206receives data “DO” from the memory202and sends data “DI” to the memory202. The edit module206may also receive signal “READY” from the priority controller208. If the “READY” signal is equal to 1, the priority controller208allows the edit module206to access the memory202.

The priority controller208has connections to the memory202, cache module210, search module204and edit module206. The priority controller208manages accessing by these modules204,206&210to the memory. The cache module210may modify addresses to provide correct searches.

A problem in separation of the search and edit operations is simultaneous memory access by both types of operations. The edit operation transforms memory content relatively slowly, level by level. Additionally, the search operation is correct only if the edit operation has finished. The present invention addresses these issues through the use of the priority controller208.

For instance, a search operation requires just read access to the memory. The edit operation needs read and write access to the memory. In a contemplated embodiment, the search operation has priority, and the priority controller208allows communication of the edit module206with the memory202only in the case when search does not read the memory202.

In order to provide reliable and accurate access by the search operation to the memory202, controller208may access an address cache module210. For example, if an edit operation requests a read of memory address A1of the memory202, the content of memory address A1is copied to a free address, A2, and pair (A1, A2) is stored in the cache210, which may include small content addressable memory (CAM). The memory controller is looking for the search address A in the left side of the CAM. If it exists there, for example A=A1, it will be replaced by the right component of the corresponding CAM entry, i.e. A2. This guaranties that a search reads from the memory the same information as before the start of the edit operation.

After the edit operation is finished, the cache may be cleared. To perform this procedure, the central controller may send a signal through the cache bus to the memory controllers. Signal synchronization with the search stream allows the system of the present invention to preserve correctness at this period of time.

Referring again toFIG. 1, the central controller102communicates with the outside world. The central controller102receives external commands and transfers them to one of the pipelines: search116or edit118. The central controller102controls the edit operation's execution and saves the current execution edit command and information associated with it, such as address, data and the like. The central controller102may utilize this information to produce the answer for the search operation. From a user point of view, all operations (search, insert, delete) execute in the order received.

In an embodiment of the present invention, the central controller102rejects any edit operation issued before the current edit operation is finished. In the case of the insert operation the associated data does not travel through the pipeline. The central controller102sends it immediately to the bottom processor.