Address recognition engine

Claim 2

The apparatus of claim 1 wherein the primary database comprises a database having a multiway tree node (TRIE) structure, wherein the network address comprises an n-bit field; and wherein the address recognition engine segments the n-bit address into a plurality of m-bit digits for traversal through the primary database, each m-bit digit having one of 2 m distinct values.

Claim 3

The apparatus of claim 2, wherein the plurality of linked nodes includes at least one set of transition nodes and a set of termination nodes linked to each one of the at least one set of transition nodes, each of the at least one set of transition nodes being linked to a root node and each of the at least one root node and each node of the at least one set of transition nodes includes 2 m node pointers for linking to subsequent nodes, each one of the node pointers of one of the root and transition nodes corresponds to one of the 2 m distinct values and points to a subsequent one of one of the at least one set of transition nodes and the linked set of termination nodes, each one of the termination nodes includes 2 m secondary database pointers, each one of the secondary database pointers of one of the termination nodes corresponds to one of the 2 m distinct values and points to one of the entries of the secondary database, the digits of the network address being matched, one at a time, in a preselected sequence of digits, to a corresponding sequence of linked node pointers of a root node and subsequent transition nodes to traverse the primary database to one of the termination nodes, wherein each of the node pointers further comprises control information for use by the address recognition engine to redirect traversal of the primary database at a preselected one of the digits, wherein each of the transition nodes includes a 2 m +1 node pointer, and the control information includes an IDI_CNT field and a LOAD_IDI field; the LOAD_IDI field representing one of a set state and a clear state, the set state indicating to the address recognition engine that the traversal of the primary database is to be redirected at a preselected one of the digits and the clear state indicating to the address recognition engine that traversal of the primary database is to continue without redirection, the IDI_CNT field contains an integer that indicates to the address recognition engine the preselected one of the digits at which the traversal is to be redirected; the 2 m +1 node pointer points to another one of the set of transition nodes for redirection of traversal by the address recognition engine when a digit to be matched at the respective transition node is a preselected one of the digits as indicated in an IDI_CNT field of a previous transition node.

Claim 4

The apparatus of claim 3, wherein the control information includes an area match information field, the area match information field representing a set state and a clear state, the set state indicating to the address recognition engine that the traversal of the primary database is to be redirected at a preselected one of the digits and the clear state indicating to the address recognition engine that the traversal of the primary database is to continue without redirection; and wherein the address recognition engine includes a set of database specifiers, each of the database specifiers including control information for redirecting the traversal of the primary database when the area match information in one of the node pointers matching a digit of the network address is in the set state; the address recognition engine being controlled to select one of the database specifiers prior to input of an index to the primary database, wherein the control information of each one of the database specifiers includes an area match count field and an area match root field, each area match count field indicates to the address recognition engine the preselected one of the digits at which a redirection of traversal of the primary database is to occur when the area match information at any one digit of the index is in the set state, and each area match root field indicates to the address recognition engine a preselected node of the primary database where the traversal of the primary database is to continue for remaining subsequent digits of the index.

Claim 5

The apparatus of claim 3, wherein each one of the transition nodes includes an intermediate secondary database pointer for use by the address recognition engine for a best match result; and wherein each one of the node pointers further comprises a SAVE_RESULT field representing one of a set state and a clear state, the set state indicating to the address recognition engine that an intermediate secondary database pointer of a preselected transition node is to be used as a best match result, wherein the preselected transition node is a transition node pointed to by a node pointer having a SAVE_RESULT field in the set state, wherein each node pointer further comprises a PTR_CTRL field to indicate when there is a look-up-fail-use-best-match-result to the address recognition engine so that the address recognition engine then uses the intermediate secondary database pointer of the preselected transition node indicated by the SAVE_RESULT field in the set state, for access to and retrieval of an entry of the secondary database.

Claim 6

The apparatus of claim 3, wherein each one of preselected ones of the plurality of linked nodes includes a controllably variable string structure for controllably matching a preselected number of digits of a request at the one node of the primary database, wherein each string structure comprises at least one word and a control field, each one of the at least one word being segmented into x m-bit digits, and the control field indicating to the address recognition engine a set of the x m-bit digits that are valid for use as a string of digits for matching to corresponding digits of an index, wherein each node pointer further comprises a PTR_CTRL field to indicate to the address recognition engine whether the controllably variable string structure of a node pointed to by the respective node pointer is to be used in a match with digits of an index, wherein the at least one word comprises a plurality of words and a control field for each one of the plurality of words.

Claim 7

An address recognition apparatus, which comprises: an address recognition engine adapted to receive as an input a network address; a network information look-up database coupled to the address recognition engine; the network information look-up database comprising a plurality of entries; the plurality of entries comprising a first set of entries and a second set of entries; the address recognition engine operating to use a network address input thereto as a look-up index to the lookup database for access to and retrieval of a corresponding one of the first set of the entries; each one of the first set of entries comprising a common block containing network information relating to the network address used to locate the corresponding one of the first set of entries; each one of the second set of entries comprising an adjacency block containing additional network information relating to network information contained in the common blocks; and a set of path split blocks; each one of the set of path split blocks being linked to one of the common blocks; each one of the set of path split blocks comprising a set of adjacency block pointers, each arranged to point to a preselected one of the set of adjacency blocks for controllably linking the respective common block to a preselected set of adjacency blocks.

Claim 8

An address recognition apparatus, which comprises: an address recognition engine adapted to receive as an input a network address; a network information look-up database coupled to the address recognition engine; the network information look-up database comprising a plurality of entries; the address recognition engine operating to use a network address input thereto as a look-up index to the lookup database for access to and retrieval of a corresponding one of the entries; each one of the entries comprising a common block containing network information relating to the network address used to locate the corresponding one of the entries; each one of the common blocks including a bridging information field; and wherein the address recognition engine is controlled to perform a bridging operation to read and write bridging information from and to the bridging information field.

Claim 9

An address recognition apparatus, which comprises: an address recognition engine adapted to receive as an input a network address; a network information look-up database coupled to the address recognition engine; the network information look-up database comprising a plurality of entries; the address recognition engine operating to use a network address input thereto as a look-up index to the lookup database for access to and retrieval of a corresponding one of the entries; each one of the entries comprising a common block containing network information relating to the network address used to locate the corresponding one of the entries; a set of database specifiers, each of the database specifiers including an information mask to indicate to the address recognition engine preselected portions of the network information contained in the respective one of the entries, to be returned in a look-up operation using the index; and the address recognition engine being controlled to select one of the database specifiers prior to input of an index to the look-up database.