Default route coding

• US 7,715,385 B2
• Filed: 08/10/2006
• Issued: 05/11/2010
• Est. Priority Date: 12/27/2000
• 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): NGUYEN, STEVEN H D
• Application Number:
  US11/502,587
• Publication Number:
  US 20070115968A1
• Time in Patent Office: 1,370 Days
• Field of Search: None
• 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 comprising:

searching a plurality of mappers for a search result based on a search key, wherein at least one mapper comprises a first default route memory configured to store at least one value from a set of values comprising an inherit code and a default route index associated with a set of one or more entries corresponding to a set of one or more subtree nodes in a search tree, wherein the inherit code indicates that a default route index corresponding to the set of one or more subtree nodes is a default route index stored in a second default route memory associated with a root node corresponding to the set of one or more subtree nodes; and

returning the default route index stored in the second default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and an inherit code is stored in the first default route memory.

2. The method of claim 1, wherein the root node corresponding to the set of one or more subtree nodes is a subtree node of a higher-level root node, and wherein the second default route memory is configured to store at least one value from a set of values comprising an inherit code and a default route index associated with the root node, wherein the inherit code indicates that a default route index corresponding to the root node is a default route index stored in a third default route memory associated with the higher-level root node, and wherein the method further comprises:

returning the default route index stored in the third default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and inherit codes are stored in the first and second default route memories.

3. The method of claim 1, further comprising:

updating the default route index stored in the second default route memory; and

returning the updated default route index stored in the second default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route code, and an inherit code is stored in the first default route memory.

4. The method of claim 2, further comprising:

updating the default route index stored in the third default route memory; and

returning the updated default route index stored in the third default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and inherit codes are stored in the first and second default route memories.

5. The method of claim 1, wherein at least one entry in the set of one or more entries comprises a descriptor that includes a pointer to the first default route memory.

6. The method of claim 3, wherein updating the default route index stored in the second default route memory is completed in a single write to the second default route memory.

7. The method of claim 4, wherein updating the default route index stored in the third default route memory is completed in a single write to the third default route memory.

8. The method of claim 1, further comprising:

returning the default route index stored in the first default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and a default route index is stored in the first default route memory.

9. The method of claim 1, wherein the default route memory is a field in an entry of the set of one or more entries if the set of one or more entries only contains a single entry.

10. A system comprising:

a plurality of mappers configured to return a search result in response to a search based on a search key, wherein a first mapper comprises a first default route memory configured to store at least one value from a set of values comprising an inherit code and a default route index associated with a set of one or more entries corresponding to a set of one or more subtree nodes in a search tree, wherein the inherit code indicates that a default route index for the set of one or more subtree nodes is a default route index stored in a second default route memory associated with a root node corresponding to the set of one or more subtree nodes, and wherein the plurality of mappers is configured to return the default route index stored in the second default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and an inherit code is stored in the first default route memory.

11. The system of claim 10, wherein the root node corresponding to the set of one or more subtree nodes is a subtree node of a higher-level root node, and wherein the second default route memory is configured to store at least one value from a set of values comprising an inherit code and a default route index associated with the root node, wherein the inherit code indicates that a default route index corresponding to the root node is a default route index stored in a third default route memory associated with the higher-level root node, and wherein the plurality of mappers is configured to return the default route index stored in the third default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and inherit codes are stored in the first and second default route memories.

12. The system of claim 10, wherein if the default route index stored in the second default route memory is updated, the plurality of mappers is configured to return the updated default route index stored in the second default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and an inherit code is stored in the first default route memory.

13. The system of claim 10, wherein the plurality of mappers comprises a default route index pipeline configured to forward a default route index from a default route memory to a default route index selector configured to return a default route index as an output of the plurality of mappers.

14. The system of claim 11, wherein if the default route index stored in the third default route memory is updated, the plurality of mappers is configured to return the updated default route index stored in the third default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and inherit codes are stored in the first and second default route memories.

15. The system of claim 12, wherein the default route index stored in the second default route memory is updated in a single write to the second default route memory.

16. The system of claim 10, wherein the plurality of mappers is configured to return the default route index stored in the first default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and a default route index is stored in the first default route memory.

17. The system of claim 10 wherein the inherit code indicates that a default route index corresponding to the set of one or more subtree nodes is a default route index stored in a fourth default route memory associated with a different set of one or more subtree nodes.

18. The system of claim 10, wherein the first default route memory is a field in an entry of the set of one or more entries if the set of one or more entries only contains a single entry.

19. A system comprising:

means for returning a search result in response to a search based on a search key, wherein the means for returning a search result comprises a first means for storing entries, wherein the first means for storing entries comprises a first default route memory configured to store at least one value from a set of values comprising an inherit code and a default route index associated with a set of one or more entries corresponding to a set of one or more subtree nodes in a search tree, wherein the inherit code indicates that a default route index for the set of one or more subtree nodes is a default route index stored in a second default route memory associated with a root node corresponding to the set of one or more subtree nodes, and wherein the means for returning a search result returns the default route index stored in the second default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a default route indicator, and an inherit code is stored in the first default route memory.

20. The system of claim 19, wherein the root node corresponding to the set of one or more subtree nodes is a subtree node of a higher-level root node, and wherein the second default route memory is configured to store at least one value from a set of values comprising an inherit code and a default route index associated with the root node, wherein the inherit code indicates that a default route index corresponding to the root node is a default route index stored in a third default route memory associated with the higher-level root node, and wherein the means for returning a search result returns the default route index stored in the third default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and inherit codes are stored in the first and second default route memories.

21. The system of claim 19 wherein if the default route index stored in the second default route memory is updated, the means for returning a search result returns the updated default route index stored in the second default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and an inherit code is stored in the first default route memory.

22. The system of claim 20, wherein if the default route index stored in the third default route memory is updated, the means for returning a search result returns the updated default route index stored in the third default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and inherit codes are stored in the first and second default route memories.

23. The system of claim 19, wherein the first default route memory is a field in an entry of the set of one or more entries if the set of one or more entries only contains a single entry.

24. The system of claim 21, wherein the default route index stored in the second default route memory is updated in a single write to the second default route memory.

25. The system of claim 19, wherein the means for returning a search result returns the default route index stored in the first default route memory if the search key corresponds to an entry in the set of one or more entries corresponding to the set of one or more subtree nodes, the corresponding entry comprises a use default route indicator, and a default route index is stored in the first default route memory.

26. The system of claim 19, wherein the inherit code indicates that a default route index corresponding to the set of one or more subtree nodes is a default route index stored in a fourth default route memory associated with a different set of one or more subtree nodes.