Method and apparatus for performing pattern search functions

Claim 2

The method according to claim 1 characterized in that it comprises the following step: g) reading a final control block chained to the control block of the second type and comprising information related to the found pattern when a match is detected at step e).

Claim 3

The method according to claim 1 or 2, characterized in that the step of providing control blocks includes: - writing in the control blocks located in the search table at addresses derived from the values of the selected field of k-bits of the p patterns, information indicative of at least one operation which starts the search in binary trees comprised of the (n-k) remaining bits of the patterns among the p patterns having the same combinations of k bits in the selected k-bit field, - chaining to each control block at an address derived from the the selected field of k bits, a number of chains of control blocks equal to the number of leafs of the corresponding binary tree and writing in the control blocks of each of said chains information indicative of the operations which lead to a leaf, said operations comprising test operations of the first type on bits at positions where jumps exist in the binary tree, if any, and at least one compare operation of the second type wherein the specified value is the value of the (n-k) bits of one of the p patterns of the said binary tree, - providing an operation of the third type in the control blocks at addresses derived from combinations of the k bits of the selected field which do not exist in the p patterns.

Claim 4

A searching apparatus for searching a n-bit pattern among a plurality of p n-bit patterns, where n and p are integer numbers and p is lower than 2 n and the p patterns are any patterns among the 2 n possible patterns, comprising a search table stored in a storing means (52), said search table comprising control blocks (CB) which are chained together and the contents of which is indicative of operations to be performed on the to-be-searched pattern, said apparatus being characterized in that it includes: - writing means (74,82, Fig.6) for writing the control blocks in the search table, said control blocks being of a first type indicative of test operations on at least one selected bit of the to- be- searched pattern and of 0 second type indicative of compare operations with a specified value and of a third type indicative that no operations have to be performed, and chaining control blocks in at least one chain in such a way that each control block chain determine operations which lead to the finding of one of the p patterns, depending upon the values of the p patterns, - means (44,54,56,102) for reading a first control block at a search table address which is derived from a selected field of k of the to-be-searched pattern, with k being an integer number lower than n, - means (106,134,136) for generating a not-found pattern signal if the read control block is of the third type, - means (114,108,118) for executing the operations indicated in the first read control block and the control blocks chained thereto, until a control block of the second type is is reached, - comparing means (120) for comparing the to be searched pattern with the specified value in the control block of the second type, - means (134,136) for generating a "not found pattern" information if a mismatch is detected by the comparing means, - means (130,132) for generating a "found pattern" information if a match is detected by the comparing means, whereby the "found pattern" information indicates that the to-be-searched pattern is one pattern among the p patterns.

Claim 5

The apparatus according to claim 4 characterized in that it comprises: means (124, 126) responsive to the detection of a match by the comparing means for reading a final control block (LEAF) chained to the control block of the second type and comprising information related to the found pattern.

Claim 6

The apparatus according to claim 4 or 5, characterized in that the control blocks writing means comprises: - means (152, 164, 162) for writing in the control blocks located in the search table at addresses derived from the values of the selected field of k-bits of the p patterns, information indicative of the operations which start the search in binary trees comprised of the (n-k) remaining bits of the patterns among the p patterns having the same combinations of k bits in the selected k-bit field, - means (176,192,194) for chaining to each control block at an address derived from the the selected field of k-bits, a number of chains of control blocks equal to the number of leafs of the corresponding binary tree and writing in the control blocks of each said chain the operations which lead to a leaf, said operations comprising test operations of the first type on bits at positions where jumps exist in the binary tree, if any, and at least one compare operation of the second type wherein the specified value is the value of the (n-k) bits of one of the p patterns of the said binary tree.

Claim 7

A connecting device (10) between communication networks linking stations, wherein each station has an address of n bits, so that the set of addresses of the active stations pertaining to the communication networks connectable by the connecting device through input and output ports comprise p patterns of n bits, said bridge being responsive to the frames received on an input port from a source station comprising a source station address field and a destination address field for determining the output port to which the frame has to be routed, said connecting device being characterized in that it comprises: - a first searching apparatus according to any one of claims 4, 5 or 6, which is responsive to the destination address for searching the destination address pattern, and if the destination address pattern is found, reading the final control block wherein the related pattern information is a frame routing information, - a second searching apparatus according to any one of claims 4, 5, or 6 which is responsive to the source address for searching the source address pattern and if the source address pattern is not found, updating the control blocks in the search table and writing new control blocks so that the control blocks needed to find said address pattern be inserted in the search table.

Claim 8

The connecting device according to claim 7 characterized in that it comprises a sequencing means which alternatively activates the first and the second searching apparatuses whereby the operations performed on the source address and destination address patterns are interleaved.

Claim 9

The connecting device according to claim 7 or 8 characterized in that it comprises an updating means (74) which is responsive to the "pattern not found" information generated by the second searching apparatus for initiating a search of the not found pattern comprising the steps of: reading the first control block at the address derived from the the k-bit field of the not found pattern, if said first control block is empty, writing at said address the first control block of the chain which leads to the compare control block wherein the specified value is equal to the (n-k) bits of the not found pattern, if not, reading the control blocks chained to the first control block until a compare control block is read, comparing the (n-k) bits of the not found pattern with the specified value in said control block, detecting the first mismatch bit position (bm) where a mismatch exists, writing a new control block of the first type indicative of a test operation on the bit at the mismatch position, and chaining thereto a control block of the second type wherein the specified value comprises the (n-k) bits of the not found pattern and a final control block (LEAF) including at least routing information.

Claim 10

The connecting device according to claim 9 characterized in that the final control block of the chains comprises an age field which is written to the current time value each time a pattern is found by the second searching apparatus, said age fields in the final control blocks of the control block chains being read at regular intervals by the updating mechanism which is responsive to age values to update the control blocks in such a way that the the address patterns which have not been searched for a time higher than a fixed limit be no more found by the first and second searching apparatuses.

Claim 11

The connecting device according to any one of claims 7 to 10 characterized in that the control block chains in the search table comprise control blocks of the second type wherein the specified value comprises selected fields of the p patterns, chained with at least one intermediate final control block (LI) in order to detect that the to- be- searched pattern partially match with one of the p patterns.

Claim 12

The connecting device according to claim 11, characterized in that it comprises means for storing each one of the p patterns found as a result of a compare operation with each one selected field in order to determine the pattern among the p patterns which best matchs with the to be searched pattern.