Default route coding

• US 20070115968A1
• Filed: 08/10/2006
• Published: 05/24/2007
• Est. Priority Date: 12/27/2000
• Status: Active Grant

• Current Assignee: Chartoleaux KG LLC (Intellectual Ventures LLC)
• Original Assignee: Satech Group AB LLC (Intellectual Ventures LLC)
• Inventors: Brown, David
• Granted Patent: US 7,715,385 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A multi-level lookup table includes a plurality of search levels with each search level including a plurality of subtrees, each subtree representing a plurality of nodes. A search of the multi-level lookup table for an entry corresponding to a search key results in a value stored in an entry associated with the node in a subtree. A default value is associated with the root of the subtree. Multiple entries for the subtree can store the default value. To minimize route update time, the default value associated with the subtree is stored in a single location. Instead of storing the default value in multiple entries, each entry stores a use default indicator to indicate that the default value stored in the single location is to be used. To further reduce the number of locations to modify to update the default route, the single location can store an inherit indicator to indicate that the default value for the subtree is inherited from another subtree.

Claims

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

providing a default route memory for storing a default route for a subtree;

sharing the default route by nodes in the subtree; and

modifying the default route by performing a single write to the default route memory.

2. The method as claimed in claim 1 wherein the default route memory stores a route corresponding to the route associated with the root of the subtree.

3. The method as claimed in claim 1 wherein the default route memory stores an inherit indicator to indicate that the default route corresponding to the route associated with the root of the subtree is inherited from another subtree.

4. The method as claimed in claim 3 wherein the inherited default route is forwarded by a default index pipeline.

5. The method as claimed in claim 1 wherein the subtree is a dense subtree and a dense subtree descriptor associated with the subtree includes the default route memory.

6. The method as claimed in claim 5 wherein the default route is shared by storing a use default indicator in a mapper entry associated with at least one node in the subtree.

7. The method as claimed in claim 6 further comprising the step of:

returning the default route as a result of a search of the lookup table upon detecting the use default indicator stored in the mapper entry.

8. The method as claimed in claim 1 wherein the subtree is a sparse subtree, the number of routes in the sparse subtree is greater than one and a sparse subtree entry associated with the subtree includes the default route memory.

9. The method as claimed in claim 1 wherein the subtree is a sparse subtree, the number of routes in the sparse subtree is one, and a default route memory associated with the sparse subtree stores the default route.

10. A multi-level lookup table comprising:

a default route memory which stores a default route shared by nodes in a subtree; and

default logic which returns the default route as a result of a search of the lookup table.

11. The multi-level lookup table as claimed in claim 10 wherein the default route memory stores a default route for the route corresponding to the root of the subtree.

12. The multi-level lookup table as claimed in claim 10 wherein the default route memory stores an inherit indicator to indicate that the route corresponding to the root of the subtree is inherited from another subtree.

13. The multi-level lookup table as claimed in claim 12 further comprising:

a default index pipeline which forwards the inherited default route.

14. The multi-level lookup table as claimed in claim 10 wherein the subtree is a dense subtree and a dense subtree entry associated with the subtree includes the default route memory.

15. The multi-level lookup table as claimed in claim 14 further comprising:

a mapper entry associated with at least one node in the subtree, the mapper entry stores a use default indicator which indicates that the default route stored in the default route memory is the default route for the at least one node, the default route is modified by performing a single write to the default route memory.

16. The multi-level lookup table as claimed in claim 15 wherein the default logic returns the default route upon detecting the use default indicator stored in the mapper entry.

17. The multi-level lookup table as claimed in claim 10 wherein the subtree is a sparse subtree number of routes in the sparse subtree is greater than one and a sparse subtree entry associated with the subtree includes the default route memory.

18. The multi-level lookup table as claimed in claim 10 wherein the subtree is a sparse subtree, the number of routes in the sparse subtree is one, and the default route memory is stored in a default mapper entry associated with the sparse subtree descriptor.

19. A multi-level lookup table comprising:

a default route memory which stores a default route for nodes in a subtree; and

means for returning the default route as a result of a search of the lookup table upon detecting the use default indicator stored in the mapper entry.

20. The lookup table as claimed in claim 19 wherein the default route memory stores a default route associated with the root of the subtree.

21. The lookup table as claimed in claim 19 wherein the default route memory stores an inherit indicator to indicate that the default route associated with the root of the subtree is inherited from another subtree.

22. The lookup table as claimed in claim 21 further comprising:

means for forwarding the inherited default index.

23. The lookup table as claimed in claim 19 wherein the subtree is a dense subtree and a dense subtree descriptor associated with the subtree includes the default route memory.

24. The lookup table as Claimed in claim 19 further comprising:

means for sharing the default route amongst nodes in the subtree by storing a use default indicator in a mapper entry associated with at least one node in the subtree and modifying the default route by performing a single write to the default route memory.

25. The lookup table as claimed in claim 19 wherein the subtree is a sparse subtree the number of routes in the sparse subtree is greater than one and a sparse subtree descriptor associated with the sparse subtree includes the default route memory.

26. The lookup table as claimed in claim 19 wherein the subtree is a sparse subtree, the number of routes in the sparse subtree is one, and the default route memory is stored in a default mapper entry associated with the sparse subtree descriptor.