Variable length data sequence backtracking a trie structure

• US 5,787,430 A
• Filed: 12/17/1996
• Issued: 07/28/1998
• Est. Priority Date: 06/30/1994
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sharma, Mohan, Karjoth, Gunter, Doeringer, Willibald, Dykeman, Douglas, Nassehi, Mehdi
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): HAVAN, THU THAO
• Application Number:
  US08/765,764
• Time in Patent Office: 588 Days
• Field of Search: 707/7, 707/6, 707/2, 707/100, 707/3
• US Class Current: 1/1
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The building, maintenance, and use of a database is described having a trie-like structure for storing entries and retrieving an at least partial match, preferably the longest partial match, or all partial matches of a search argument (input key) from said entries, said database having nodes (20), with each node containing first link information (21) leading to at least one previous node (parent pointer) and second link information (25,26) leading to at least one following node (child pointer), at least a stored key (entry, 23, 24), or a combination, thereof. The particular structure of the nodes allows a two-step search process, in which segments of a search argument are firstly used to determine a search path through the trie-like database, said search path being backtracked in the second part of the search. During the second part of the search the entire search argument is compared to entries stored in the nodes until a match is found. The described database allows an efficient use of memories and is advantageously applied to fast data retrieval, in particular related to communication within computer networks. No recursive procedures are applied.

Claims

1. Method for retrieving a prefix match, a postfix match or a complete match, preferably the longest prefix- or postfix match, or all prefix- or postfix matches of a search argument (input key) from entries stored in a database with a trie-like structure having nodes (20), with each node containing first link information (21) leading to at least one previous node (parent pointer) and second link information (25,26) leading to at least one following node (child pointer), at least one stored key (entry,23,24), or a combination, thereof, said method comprising the steps of

entering at a node of said database (root node);

determining a search path from one node to another through said trie-like database by successively processing segments of said search argument which comprise only those parts of the entries which are necessary to identify the next (child) node, and said second link information (25,26) until said segments are consumed or a (leaf) node lacking said second link information (25,26) is reached;

comparing with said search argument an entry stored in the node at which said search path ended; and

if no at least partial match between the search argument and said entry is found in said current node,

backtracking said search path by processing said first link information (21) of said current node; and

repeating the previous two steps until said at least partial match is found or said root node is reached.

2. Method in accordance with claim 1, wherein each node further contains an index (22) and while determining the search path only the segment of the search argument which is identified by the index is processed at any one of the nodes.

3. Method in accordance with claim 1 or 2, wherein a segment of a search argument contains one or more bits.

4. Method in accordance with claim 1, wherein the step of determining the search path is essentially characterized by a one-bit comparison.

5. Method in accordance with one of claim 1, wherein the search argument represents a unit address in a communication network.

6. Method in accordance with one of claim 1, wherein the search argument represents syntax from one network protocol to be translated into syntax of another network protocol.

7. Method in accordance with one of claim 1, wherein a new entry is inserted by steps comprising:

using said new entry as search argument,

terminating the search when a (leaf) node lacking said second link information is reached,

determining a maximum number of matching bits between an entry at the (leaf) node at which the previous step ended,

again entering the database, and interrupting the path at a node beyond which no longer match is possible by comparing said maximum number with an index stored at each node of the data base,

identifying said node as insertion node,

comparing said new entry with an entry stored in the insertion node, and

storing said new entry in said insertion node or in a newly created node located in said trie-like structure immediately before or after the insertion node depending on the result of the previous comparing step.

8. Method in accordance with one of claim 1, wherein a stored entry is deleted from the database by steps comprising:

the use of said stored entry as search argument,

deleting the stored entry, and

deleting the remaining node if a remaining stored entry or remaining second link information can be transferred to a previous (parent) node and deleting said previous node if the entry stored in it can be transferred to a further previous node.

9. Database with a trie-like structure for storing entries and retrieving a prefix match, a postfix match or a complete match, preferably the longest prefix- or postfix match, or all prefix- or postfix matches of a search argument (input key) from said entries, said database having nodes (20) which contain first link information (21) leading to at least one previous node (parent pointer), second link information (25,26) leading to at least one following node (child pointer), two stored keys (entries,23,24), and an index (22) identifying a segment at which the two stored entries differ, said second link information (25,26) being processable for determining a search path from one node to another through said trie-like database by successively processing said segments and said entries being comparable with said search argument and if no prefix-, postfix- or complete match between said search argument and said entry is found in said node, said first link information (21) being processable for backtracking said search path.

10. Apparatus for storing entries and retrieving a prefix match, a postfix match or a complete match, preferably the longest prefix- or postfix match, or all prefix- or postfix matches of a search argument (input key) from said entries, said apparatus comprising

at least one memory unit (6) for storing said entries in nodes (20) of a trie-like structure, some of said nodes containing first link information (21) leading to at least one previous node (parent pointer) and second link information (25,26) leading to at least one following node (child pointer) and a stored key (entry,23,24) and an index,

register means (2) for intermediately storing said search argument,

a fetch unit (4) using said index for identifying and providing a segment of said search argument,

a comparator unit (3) for comparing said segment of said search argument with the corresponding part of an entry stored in a node, and

a search engine (5) for addressing and/or receiving entries stored in said memory, for determining a search path through said nodes depending on the output of said fetch unit (4), and for backtracking said search path depending on the output of said comparator unit (3) by comparing with said search argument an entry stored in the node at which said search path ends and if no prefix-, postfix-, or complete match between said search argument and said entry is found in said node, processing said first link information (21) of said node and repeating the previous two steps until said at least partial match is found or a root node is reached.

11. The apparatus in accordance with claim 10, further comprising a maintenance engine (7) for adding a stored entry and restoring the tree-like structure by

using said new entry as search argument,

terminating the search when a (leaf) node lacking said second link information is reached,

determining a maximum number of matching bits between an entry at the leaf node at which the previous step ended,

again entering the database, and interrupting the path at a node beyond which no longer match is possible by comparing said maximum number with an index stored at each node of the data base,

identifying said node as insertion node,

comparing said new entry with an entry stored in the insertion node, and

storing said new entry in said insertion node or in a newly created node located in said trie-like structure immediately before or after the insertion node depending on the result of the previous comparing step and for deleting a stored entry and restoring the tree-like structure by

using said stored entry as search argument,

deleting the stored entry, and

deleting the remaining node if a remaining stored entry or remaining second link information can be transferred to a previous (parent) node and deleting said previous node if the entry stored in it can be transferred to a further previous node.

12. A network switching apparatus comprising an apparatus in accordance with claim 10.

13. A.network protocol converter comprising an apparatus in accordance with claim 10.