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

• US 20010043602A1
• Filed: 12/08/2000
• Published: 11/22/2001
• Est. Priority Date: 12/10/1999
• Status: Active Grant

• Current Assignee: Chartoleaux KG LLC (Intellectual Ventures LLC)
• Original Assignee: Mosaid Technologies Incorporated (MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management))
• Inventors: Brown, David A.
• Granted Patent: US 7,423,981 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• 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 and associated first subtree entry stored in a first memory space in the lookup table through a first pointer to the first subtree entry; and

storing a second set of routes and associated second subtree entry in a second memory space in the lookup table; and

switching access to the second set of routes stored in the second memory by replacing the first pointer stored to the first subtree entry with a second pointer to the second subtree entry.

2. The method as claimed in

claim 1

further comprising the step of:

deallocating the first memory space 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 pointer to a first subtree entry, the first subtree entry providing access to a first set of routes stored in a first memory space; and

means for storing a second set of routes and associated second subtree entry in a second memory space while access is provided to the first set of routes stored in the first memory space by the first pointer and switching access to the second set of routes by replacing the first pointer with a second pointer to the second subtree entry, the second subtree entry providing access to the second memory space.

6. The apparatus as claimed in

claim 5

further comprising:

means for deallocating the first memory space 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 entry, the first subtree entry providing access to a first set of routes stored in the first memory space;

a second memory space for storing a second set of routes and associated second subtree entry while access is provided to the first set of routes stored in the first memory space by the first pointer; and

logic which provides access to the second set of routes by replacing the first pointer with a second pointer to the second subtree entry, the second subtree entry providing access to the second memory space after the second set of routes are stored in the second memory.

10. The apparatus as claimed in

claim 9

further comprising:

deallocation logic which deallocates the first memory space 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.