Address recognition engine with look-up database for storing network information

• US 5,519,858 A
• Filed: 01/10/1992
• Issued: 05/21/1996
• Est. Priority Date: 01/10/1992
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Walton, Andrew, Morgan, Fearghal, O'Callaghan, Joseph, Bryant, Stewart F., Rigby, John, Seaman, Michael J., Quinlan, Una M.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US07/819,490
• Time in Patent Office: 1,593 Days
• Field of Search: 395/200, 395/275, 395/425, 395/600, 395/400
• US Class Current: 1/1
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The present invention is directed to an address recognition apparatus including an address recognition engine coupled to a look-up database. The look-up database is arranged to store network information relating to network addresses. The look-up database includes a primary database and a secondary database. The address recognition engine accepts as an input a network address for which network information is required. The address recognition engine uses the network address as an index to the primary database. The primary database comprises a multiway tree node structure (TRIE) arranged for traversal of the nodes as a function of preselected segments of the network address and in a fixed sequence of the segments to locate a pointer to an entry in the secondary database. The entry in the secondary database pointed to by the primary database pointer contains the network information corresponding to the network address. The address recognition engine includes a table for storing a plurality of database specifiers. Each of the database specifiers contains control information for the traversal of the primary and secondary databases. In addition, each of the nodes in the primary database and each of the entries in the secondary database is provided with control data structures that are programmable to control the traversal of the database.

Claims

1. 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, each one of the plurality of entries containing network information relating to a corresponding network address;

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;

the network information look-up database comprising a primary database and a secondary database, the plurality of entries being arranged in the secondary database, the primary database comprising a plurality of linked nodes for matching to preselected portions of a network address used as a look-up index so that the index input to the primary database traverses the linked nodes according to matches among linked nodes as a function of a sequence of the preselected portions of the network address to locate a secondary database pointer to one of the entries of the secondary database;

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 p-bit digits of the network address of a request at the one node of the primary database.

the address recognition engine using the located secondary database pointer to access and retrieve the corresponding one of the entries from the secondary database.

2. The apparatus of claim 1 wherein the primary database comprises a database having a TRIE structure.

3. The apparatus of claim 1, 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.

4. 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;

a network information look-up database comprising a plurality of entries, each one of the plurality of entries containing network information relating to a corresponding network address;

the address recognition engine operating to use a network address input thereto as a look-up index to the look-up database for access to and retrieval of a corresponding one of the entries;

the network information look-up database comprising a primary database and a secondary database, the plurality of entries being arranged in the secondary database, the primary database comprising a plurality of linked nodes for matching to preselected portions of a network address used as a look-up index so that the index input to the primary database traverses the linked nodes according to matches among linked nodes as a function of a sequence of the preselected portions of the network address to locate a secondary database pointer to one of the entries of the secondary database;

the address recognition engine using the located secondary database pointer to access and retrieve the corresponding one of the entries from the secondary database;

wherein the network address comprises an n-bit field,

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, and

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 p-bit digits of the network address of a request at the one node of the primary database.

5. The apparatus of claim 4 wherein the address recognition engine includes a set of database specifiers, each of the database specifiers including a root field containing root node information to indicate to the address recognition engine the root node at which to commence a traversal of the primary database;

the address recognition engine being controlled to select one of the database specifiers prior to input of an index to the primary database.

6. 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;

a network information look-up database comprising a plurality of entries, each one of the plurality of entries containing network information relating to a corresponding network address;

the address recognition engine operating to use a network address input thereto as a look-up index to the look-up database for access to and retrieval of a corresponding one of the entries;

the network information look-up database comprising a primary database and a secondary database, the plurality of entries being arranged in the secondary database, the primary database comprising a plurality of linked nodes for matching to preselected portions of a network address used as a look-up index so that the index input to the primary database traverses the linked nodes according to matches among linked nodes as a function of a sequence of the preselected portions of the network address to locate a secondary database pointer to one of the entries of the secondary database;

the address recognition engine using the located secondary database pointer to access and retrieve the corresponding one of the entries from the secondary database;

wherein the network address comprises an n-bit field;

.

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; and

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.

7. The apparatus of claim 6, 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.

8. The apparatus of claim 6, 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.

9. The apparatus of claim 8, 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.

10. 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;

a network information look-up database comprising a plurality of entries, each one of the plurality of entries containing network information relating to a corresponding network address;

the address recognition engine operating to use a network address input thereto as a look-up index to the look-up database for access to and retrieval of a corresponding one of the entries;

the network information look-up database comprising a primary database and a secondary database, the plurality of entries being arranged in the secondary database, the primary database comprising a plurality of linked nodes for matching to preselected portions of a network address used as a look-up index so that the index input to the primary database traverses the linked nodes according to matches among linked nodes as a function of a sequence of the preselected portions of the network address to locate a secondary database pointer to one of the entries of the secondary database;

.

the address recognition engine using the located secondary database pointer to access and retrieve the corresponding one of the entries from the secondary database;

wherein the network address comprises an n-bit field;

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 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.

11. The apparatus of claim 10 wherein the preselected transition node is a transition node pointed to by a node pointer having a SAVE_-- RESULT field in the set state.

12. The apparatus of claim 10, 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.

13. 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;

a network information look-up database comprising a plurality of entries, each one of the plurality of entries containing network information relating to a corresponding network address;

the address recognition engine operating to use a network address input thereto as a look-up index to the look-up database for access to and retrieval of a corresponding one of the entries;

the network information look-up database comprising a primary database and a secondary database, the plurality of entries being arranged in the secondary database, the primary database comprising a plurality of linked nodes for matching to preselected portions of a network address used as a look-up index so that the index input to the primary database traverses the linked nodes according to matches among linked nodes as a function of a sequence of the preselected portions of the network address to locate a secondary database pointer to one of the entries of the secondary database;

the address recognition engine using the located secondary database pointer to access and retrieve the corresponding one of the entries from the secondary database;

wherein the network address comprises an n-bit field,

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, and

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 p-bit digits of the network address of a request at the one node of the primary database.

14. The apparatus of claim 13, 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 a s a string of digits for matching to corresponding digits of an index.

15. The apparatus of claim 13, wherein each node pointer further comprises a PTR_-- CTRL field to indicate to the address recognition engine whether the controllable 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.

16. The apparatus of claim 13, wherein each string structure comprises a plurality of words, each of said plurality of words including a control field, and being segmented into x, m-bit digits,

wherein the control fields indicate 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.