Default route coding
First Claim
1. A method for updating a multi-level lookup table comprising the steps of:
- providing a default route memory for storing an inherit indicator to indicate that a default route corresponding to the route associated with the root of a subtree is inherited from another subtree, wherein the inherited default route is forwarded by a default index pipeline;
sharing the default route by nodes in the subtree; and
modifying the default route of the root of the subtree, in a single write, by updating the default route memory of the root of the subtree to include a route index value.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
17 Claims
-
1. A method for updating a multi-level lookup table comprising the steps of:
-
providing a default route memory for storing an inherit indicator to indicate that a default route corresponding to the route associated with the root of a subtree is inherited from another subtree, wherein the inherited default route is forwarded by a default index pipeline; sharing the default route by nodes in the subtree; and modifying the default route of the root of the subtree, in a single write, by updating the default route memory of the root of the subtree to include a route index value. - View Dependent Claims (2, 3)
-
-
4. 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, wherein the subtree is a dense subtree and a dense subtree descriptor associated with the subtree includes the default route memory; sharing the default route by nodes in the subtree; and modifying the default route of a root node, in a single write, by updating the default route memory of the root node to include a route index value. - View Dependent Claims (5, 6)
-
-
7. A multi-level lookup table comprising:
-
a default route memory which stores an inherent indicator to indicate that a default route associated with the root of the subtree is inherited from another subtree;
default logic which returns the default route as a result of a search of the lookup table; anda default index pipeline which forwards the inherited default route. - View Dependent Claims (8, 9)
-
-
10. A multi-level lookup table comprising:
-
a default route memory which stores a default route shared by nodes in a subtree, wherein the subtree is a dense subtree and a dense subtree entry associated with the subtree includes the default route memory; and default logic which returns the default route as a result of a search of the lookup table. - View Dependent Claims (11, 12)
-
-
13. A multi-level lookup table comprising:
-
a default route memory which stores an inherit indicator to indicate that a default route associated with the root of the subtree is inherited from another subtree;
means for returning the default route as a result of a search of the lookup table; andmeans for forwarding the inherited default index. - View Dependent Claims (14, 15)
-
-
16. A multi-level lookup table comprising:
-
a default route memory which stores a default route for nodes in a subtree, wherein the subtree is a dense subtree and a dense subtree descriptor associated with the subtree includes the default route memory; 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.
-
-
17. A multi-level lookup table comprising:
-
a default route memory which stores a default route for nodes in a subtree;
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; andmeans 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 of a root node, in a single write, by updating the default route memory of the root node to include a route index value.
-
Specification