Enhanced searching method and apparatus for variable bit chains

• US 6,421,660 B1
• Filed: 12/18/1998
• Issued: 07/16/2002
• Est. Priority Date: 12/19/1997
• Status: Expired due to Term

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Glaise, Rene
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): Pardo, Thuy N.
• Application Number:
  US09/216,191
• Time in Patent Office: 1,306 Days
• Field of Search: 370/60, 370/389, 370/392, 707/3, 707/100, 707/102, 707/6
• US Class Current: 707/749
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The present method and apparatus provide a searching operation of variable bit chain keys, the implementation being possible in software and cost effective in hardware. When implemented in the network routers, this solution sustains performance required for routing IPV4 OR IPV6 datagrams node insert and delete operations maintain the data base with no need for further garbage collection. The Extended patricia tree data structure of the invention the determination in advance of the process time and the storage resources which will be used. Variable bit chain keys padded with zeros and their prefix length are stored in the extended patricia tree. A search is performed in two parts, a first up-down displacement in the tree followed by a down-up displacement to find the key stored in one node in the tree having the longest matching prefix with the key to be searched.

Claims

1. A method for searching input variable bit chain keys having a maximum length value, in a Patricia tree based data base, each node in the data base storing a direct parent address pointing to a previous node, two addresses pointing to following nodes, a data value or a pointer to a data value, a bit chain key zero padded up to said maximum length value, the length of said key and the rank of a bit to be tested at this node in the input key;

said method comprising the steps of;

A. pointing to a root node of the tree,

B. padding the input key with zeros up to the maximum length value and reading the bit to test in the input key and according to the value of the bit to test pointing to the following node address,

C. repeating step B and reaching the following nodes until the rank of the bit to test of a following node is equal to or greater than the rank of the bit to test of the previous node, the previous node thereby becoming a terminating node,

D. comparing the key stored in said terminating node on its stored length with the zero padded input key,

E. if a match is found in step D, terminating the search,

F. if a match is not found in step D, pointing to the parent node of the terminating node using the direct parent address, the parent node thereby becoming a new terminating node, and

G. repeating steps D, E and F until the root node is reached or a match is found in step D.

2. A method for searching input variable bit chain keys having a maximum length value, in a Patricia tree based data base, each node in the data base storing a direct parent address pointing to a previous node, two addresses pointing to following nodes, a data value or a pointer to a data value, a bit chain key zero padded up to said maximum length value, the length of said key and the rank of a bit to be tested at this node in the input key;

said method comprising the steps of;

A. pointing to a root node of the tree,

B. padding the input key with zeros up to the maximum length value and reading the bit to test in the input key and according to the value of the bit to test pointing to the following node address,

C. repeating step B and reaching the following nodes until the rank of the bit to test of a following node is equal to or greater than the rank of the bit to test of the previous node,

D. comparing the key stored in said previous node on its stored length with the zero padded input key,

E. if a match is not found, pointing to the parent node using the direct parent address,

F. repeating step E until the root is reached or a match is found,

G. reading the pointer or the data value of said previous node,

H. performing the searching steps according to the method of claim 1 up to step C,

I. inserting a new node between the previous node and the following node and storing in the new node the input key and the input key length,

J. comparing the length of the key of the just reached node with the length of the key of its parent node,

K. if the length of the parent node key is smaller than the length of the key to be inserted, comparing the key of the just reached node on its key length with the key of its parent node,

L. if a match is found, swapping the two key values between the just reached node and its parent node while restoring the node branching;

M. repeating steps I to K until the root is reached.

3. A method of searching a patricia tree for a match on an variable length input key, wherein the input key has a maximum bit lenght, each node in the tree containing a pointer to its parent node, pointers to two child nodes, a data value or a pointer to a data value, a bit key padded with zeros up to the maximum bit length, a prefix length of the bit key and a rank value that identifies a bit to be tested at that node in the input key, comprising

a) padding the input key up to the maximum bit length,

b) pointing to the root node as the present node,

c) testing a bit in the input key identified by the rank value stored in the present node,

d) pointing to one of the child nodes of the present node according to the value of the bit tested in step c), the child node thereby becoming a new present node,

e) repeating steps c) and d) until the rank value stored in the present node is equal to or greater than that of a parent node of the present node,

f) pointing to one of the child nodes of the present node according to the value of the bit tested in the input key, the child node thereby becoming a new present node,

g) comparing the prefix of the key specified by the prefix length, both the key and the prefix length being stored in the present node, with the same prefix of the input key,

h) if the comparison of step g) matches, terminating the search,

I) if the comparison of step g) does not match, pointing to the parent node of the present node, the parent node thereby becoming a new present node,

j) comparing the prefix of the key specified by the prefix length stored in the present node with the same prefix of the input key,

k) if the comparison of step j) matches, terminating the search,

l) if the comparison of step j) does not match, pointing to the parent of the present node as the next present node,

m) repeating steps j), k) and l) until a match is found at step j) or until the tree is exhausted.

4. The method of claim 3 for inserting a node further comprising

performing steps a) through f) of claim 3,

inserting a new node having a key equal to the input key between the present node and the parent of the present node by adjusting the parent node pointers and child node pointers of the present node, the parent node and the inserted node,

pointing to the inserted node as the present node,

beginning with the inserted node and proceeding up the tree towards the root node, comparing the lengths of the keys of adjacent nodes,

if the length of the key of the node closest to the root node is longer than the length of the key of the node below it in the tree, exchanging the stored keys and the prefix lengths of the adjacent nodes and updating the parent and child pointers.

5. A method of searching a patricia tree for a match on an variable length input key, wherein the input key has a maximum bit length, each node in the tree containing a pointer to its parent node, pointers to two child nodes, a data value or a pointer to a data value, a bit key padded with zeros up to the maximum bit length, a prefix length of the bit key and the rank of a bit to be tested in the input key, comprising

a) padding the input key up to the maximum bit length,

b) pointing to the root node as the present node,

c) testing the bit in the input key according to the rank stored in the present node,

d) pointing to one of the child nodes of the present node as the next present node according to the value of the bit tested in step c),

e) repeating steps c) and d) until the rank of the bit to test in the input key specified by the present node is equal to or greater than that of its parent node,

f) pointing to one of the child nodes of the present node as the next present node according to the value of the bit tested in the input key,

g) inserting a new node having a key equal to the input key between the present node and the parent node of the present node by adjusting the parent node pointers and child node pointers of the present node, the parent node and the inserted node,

h) pointing to the inserted node as the present node,

i) comparing the length of the key of the present node with the length of the key of its parent node,

j) if the length of the key of the parent node is smaller than the length of the present node, comparing the prefix of the key of the present node with the prefix of the key of the parent node,

k) if the prefix of the key of the present node equals the prefix of the key of the parent node, exchanging (FIG. 6-112) the key values and the prefix lengths of the inserted node and the parent node and updating the node branching,

l) pointing to the parent of the present node as the new present node, and

m) repeating steps i through l until the root node of the tree is reached.