Method and apparatus for an incremental update of a longest prefix match lookup table

• US 7,423,981 B2
• Filed: 12/08/2000
• Issued: 09/09/2008
• Est. Priority Date: 12/10/1999
• Status: Expired due to Term

• Current Assignee: Chartoleaux KG LLC (Intellectual Ventures LLC)
• Original Assignee: Satech Group AB LLC (Intellectual Ventures LLC)
• Inventors: Brown, David A.
• Primary Examiner(s): Pham; Chi H.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US09/733,629
• Publication Number:
  US 20010043602A1
• Time in Patent Office: 2,832 Days
• Field of Search: 370/381, 370/382, 370/383, 370/395.3, 370/395.31, 370/395.32, 370/395.52, 370/395.7, 370/395.71, 370/395.72, 370/399, 370/408, 370/409, 370/256, 709/227, 709/228, 709/242, 709/245, 711/140, 711/150, 711/157, 711/168, 711/169, 711/173
• US Class Current: 370/256
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• 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/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and apparatus for performing an incremental update of a lookup table while the lookup table is available for searching is presented. To add or delete a route, a second set of routes is stored in a second memory space in the lookup table, while access is provided to the first set of routes stored in a first memory space in the lookup table. Access is provided to the first memory space through a first pointer stored in a subtree entry. After storing the second set of routes in the second memory space, access is switched to the first set of routes in the first memory space by replacing the first pointer stored in the subtree entry with a second pointer to the second memory space.

Claims

1. A method for updating a lookup table comprising the steps of:

providing access to a first set of routes stored in nodes of a first subtree within a tree, the first subtree being accessed through a first pointer to a first subtree root node of the first subtree;

providing a second subtree disconnected from the tree, the second subtree being accessed through a second pointer to a second subtree root node of the second subtree and being initially inaccessible via the tree;

storing a second set of routes in nodes of the second subtree while access via the tree is provided to the first set of routes stored in the first subtree by the first pointer, the second set of routes being a copy of the first set of routes with at least a new route added or an existing route deleted; and

switching access to the second set of routes stored in the second subtree by replacing the first pointer to the first subtree root node with the second pointer to the second subtree root node to update the tree by replacing the first subtree with the second subtree.

2. The method as claimed in claim 1 further comprising the step of:

deallocating memory used by the first set of routes after switching access.

3. The method as claimed in claim 1 wherein the number of routes in the first set of routes is less than the number of routes in the second set of routes.

4. The method as claimed in claim 1 wherein the number of routes in the first set of routes is greater than the number of routes in the second set of routes.

5. An apparatus for updating a lookup table comprising:

a first subtree within a tree, the first subtree including a first subtree root node and a first set of routes stored in nodes of the first subtree, the first set of routes being initially accessible via the tree;

a first pointer to the first subtree root node;

a second subtree initially disconnected from the tree, the second subtree including a second subtree root node and a second set of routes stored in nodes of the second subtree, the second set of routes being a copy of the first set of routes with at least a new route added or an existing route deleted and being initially inaccessible via the tree;

a second pointer to the second subtree root node; and

logic to switch access to the second set of routes by replacing in the tree the first pointer to the first subtree root node with the second pointer to the second subtree root node to update the tree by replacing the first subtree with the second subtree.

6. The apparatus as claimed in claim 5 further comprising:

deallocation logic to deallocate memory used by the first set of routes after switching access.

7. The apparatus as claimed in claim 5 wherein the number of routes in the first set of routes is less than the number of routes in the second set of routes.

8. The apparatus as claimed in claim 5 wherein the number of routes in the first set of routes is greater than the number of routes in the second set of routes.

9. An apparatus for updating a lookup table comprising:

a first pointer to a first subtree root node of a first subtree within a tree, the first pointer providing access to a first set of routes stored in nodes of the first subtree;

a second pointer to a second subtree root node of a second subtree disconnected from the tree, the second pointer providing access to a second set of routes stored in nodes of the second subtree, the second set of routes being a copy of the first set of routes with at least a new route added or an existing route deleted and being initially inaccessible via the tree while access via the tree is provided to the first set of routes stored in the first subtree by the first pointer; and

logic to provide access to the second set of routes by replacing the first pointer to the first subtree root node with the second pointer to the second subtree root node to update the tree by replacing the first subtree with the second subtree.

10. The apparatus as claimed in claim 9 further comprising:

deallocation logic to deallocate memory used by the first set of routes after the first pointer is replaced.

11. The apparatus as claimed in claim 9 wherein the number of routes in the first set of routes is less than the number of routes in the second set of routes.

12. The apparatus as claimed in claim 9 wherein the number of routes in the first set of routes is greater than the number of routes in the second set of routes.

13. A method for updating a lookup table, the lookup table providing a longest prefix match for a destination address, comprising the steps of:

providing access to a first set of routes stored in nodes of a first subtree within a tree, the first subtree being accessed through a first pointer to a first subtree root node of the first subtree;

providing a second subtree disconnected from the tree, the second subtree being accessed through a second pointer to a second subtree root node of the second subtree and being initially inaccessible via the tree;

storing a second set of routes in nodes of the second subtree while access via the tree is provided to the first set of routes stored in the first subtree by the first pointer, the second set of routes being a copy of the first set of routes with at least a new route added or an existing route deleted; and

switching access to the second set of routes stored in the second subtree by replacing the first pointer to the first subtree root node with the second pointer to the second subtree root node to update the tree by replacing the first subtree with the second subtree.

14. The method of claim 13, wherein the first set of routes and the second set of routes include a longest prefix route for the destination address.

15. The method of claim 14, wherein the destination address includes an Internet Protocol address.

16. The method of claim 14, wherein the second set of routes includes another route corresponding to the longest prefix route for another destination address.

17. The method of claim 13, wherein the first set of routes and the second set of routes are associated with nodes at the bottom level of a subtree.