Method of searching using longest match based Randix Search Trie with variable length keys and having prefix capability

• US 6,396,842 B1
• Filed: 04/30/1998
• Issued: 05/28/2002
• Est. Priority Date: 04/30/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Rochberger, Haim
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): NGUYEN, TOAN D
• Application Number:
  US09/070,452
• Time in Patent Office: 1,489 Days
• Field of Search: 370/255,256,258,392,393,395,397,399,408,409
• US Class Current: 370/408
• CPC Class Codes: H04L 2012/5685 Addressing issues
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A method of searching utilizing a longest match based Radix Search Trie with variable length keys and having the ability to handle keys being prefixes of other keys. The method is based on the well known Patricia search trie algorithm. The address prefixes representing the keys for the tree are modified before being processed by the algorithm. A single byte is added to the beginning of each address prefix which is set equal to the length of the address prefix. The combined address length byte followed by the address prefix is used by the Patricia algorithm . When one address is the prefix of another, the length byte will make both addresses unique and distinct from each other. The conventional Patricia search can now be used since the keys have been made unique. A circular prefix list is maintained in descending numerical order comprising an entry for each distinct value of address length insure that the longest matching address is found.

Claims

1. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:

inserting a key into the tree;

modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;

inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;

providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field;

updating said list so as to maintain said entries in descending numerical order of the length field;

searching the tree for a search key;

determining the largest key length in said list;

concatenating the key length onto the search key to form a modified search key;

searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and

determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.

2. The method according to claim 1, wherein said step of modifying a key comprises the step of adding a number represented by a fixed length to the beginning of a key, said number having a value equal to the length of said key.

3. The method according to claim 1, wherein said step of modifying a key comprises the step of adding a byte of data to the beginning of a key, said byte of data having a value equal to the length of said key.

4. The method according to claim 1, wherein said keys may be of variable length and may be prefixes of other keys in the tree.

5. The method according to claim 1, wherein said keys comprise address prefixes.

6. The method according to claim 3, wherein said byte of data comprises a Private Network Node Interface (PNNI) level value.

7. The method according to claim 1, wherein said list comprises a circularly linked list.

8. The method according to claim 1, further comprising the step of incrementing the count field of an entry in said list when a key is added to said tree, said entry corresponding to the length of said key.

9. The method according to claim 1, further comprising the step of decrementing count field of an entry in said list when a key is removed from said tree, said entry corresponding to the length of said key.

10. The method according to claim 1, further comprising the step of removing an entry from said list when a key is removed from said tree and said key was the last key with that particular length.

11. The method according to claim 1, further comprising the step of storing a plurality of identical keys in said tree.

12. The method according to claim 11, wherein said step of storing comprises the step of storing said plurality of identical keys in a circularly linked list, said circularly linked list stored in said tree in similar fashion to that of other keys.

13. The method according to claim 1, wherein said of determining the largest key length in said list comprises the step of maintaining a longest length variable indicating the entry in said list with the longest length.

14. The method according to claim 7, wherein said step of determining the next largest length in said list comprises the step of traversing the list to the next entry pointed to by the current entry.

15. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:

inserting a key into the tree;

modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof, said step of modifying a key comprises adding a byte of data to the beginning of a key, said byte of data having a value equal to the length of said key, said byte of data comprises a Private Network Node Interface (PNNI) level value;

inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;

providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field;

updating said list so as to maintain said entries in descending numerical order of the length field;

searching the tree for a search key;

determining the largest key length in said list;

concatenating the key length onto the search key to form a modified search key;

searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and

determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.

16. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:

inserting a key into the tree;

modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;

inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;

providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field, said list comprising a circularly linked list;

updating said list so as to maintain said entries in descending numerical order of the length field;

searching the tree for a search key;

determining the largest key length in said list;

concatenating the key length onto the search key to form a modified search key;

searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and

determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.

17. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:

inserting a key into the tree;

modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;

inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;

storing a plurality of identical keys in a circularly linked list, said circularly linked list stored in said tree in similar fashion to that of other keys;

providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field;

updating said list so as to maintain said entries in descending numerical order of the length field;

searching the tree for a search key;

determining the largest key length in said list;

concatenating the key length onto the search key to form a modified search key;

searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and

determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.

18. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:

inserting a key into the tree;

modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;

inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;

providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field;

updating said list so as to maintain said entries in descending numerical order of the length field;

searching the tree for a search key;

determining the largest key length in said list, said determining comprises the step of maintaining a longest length variable indicating the entry in said list with the longest length;

concatenating the key length onto the search key to form a modified search key;

searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and

determining the next largest key length in said list and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.

19. A method of searching utilizing a conventional Patricia search tree constructed from one or more nodes for storing one or more keys, said method comprising the steps of:

inserting a key into the tree;

modifying said keys to be inserted into the tree so as to make each key unique with respect to other keys that may be prefixes thereof;

inserting said modified each key into the tree utilizing a conventional Patricia search tree algorithm;

providing a list which includes entries for each different key length represented in the tree, each entry in said list including a length field and a count field, said list comprising a circularly linked list;

updating said list so as to maintain said entries in descending numerical order of the length field;

searching the tree for a search key;

determining the largest key length in said list;

concatenating the key length onto the search key to form a modified search key;

searching said tree with said modified search key utilizing a conventional Patricia search algorithm; and

determining the next largest key length in said list by traversing the list to the next entry pointed to by the current entry and repeating said steps of concatenating and searching until either said modified search key is found or the entries in said list are exhausted.