Methods and apparatus for longest common prefix based caching

• US 7,313,666 B1
• Filed: 12/24/2002
• Issued: 12/25/2007
• Est. Priority Date: 08/10/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sharma, Samar, Panigrahy, Rina, Saminda De Silva, Suran
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US10/328,639
• Time in Patent Office: 1,827 Days
• Field of Search: 709/238, 711/108, 711/173
• US Class Current: 711/173
• 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/7453 using hashing

Abstract

Methods and apparatus are disclosed for longest common prefix based caching. An information space is partitioned into multiple subsets such that a particular subset including a particular prefix also includes all longer prefixes beginning with the particular prefix in the information space. A primary control unit typically maintains the information space and all of the subsets, and selectively distributes some or all of the subsets to basic control units, and each of basic control units does not necessarily receive the same group of subsets. In addition, the group of subsets maintained by a particular basic control unit may change during operation, typically to increase the likelihood that a particular basic control unit will contain the needed subset. When a particular basic control unit does not have the needed subset, it typically sends to the primary control unit, a request for a lookup result, for the primary control unit to process the packet or other information, or for the primary control unit to send the corresponding subset.

Claims

1. An apparatus for routing or manipulating packets or other information, the apparatus comprising:

one or more basic control units each including control logic and one or more first lookup units; and

a supervisor control unit including control logic and a memory, the supervisor control unit coupled to each of said one or more basic control units;

wherein the supervisor control unit is configured to maintain routing information, to partition said routing information into a plurality of routing information subsets such that for a particular prefix in a particular routing information subset, the particular routing information subset includes all longer prefixes beginning with said particular prefix in said routing information, and to distribute routing information subsets to said one or more basic control units; and

wherein each of the one or more basic control units is configured to receive said routing information subsets, to populate its one or more first lookup units with said received routing information subsets, and to perform lookup operations in its one or more first lookup units to generate a result based on a route identifier; and

wherein said partitioning the routing information includes deriving a Patricia tree representation of the routing information; and

wherein the supervisor control unit is configured to repartition the routing information among the plurality of routing information subsets, said repartitioning including modifying a boundary between a first and a second subsets of the plurality of routing information subsets.

2. The apparatus of claim 1,

wherein the supervisor control unit includes one or more second lookup units;

wherein each of the one or more basic control units is configured to communicate a routing request to the supervisor control unit when its one or more first lookup units do not include the routing information subset corresponding to the route identifier;

wherein the supervisor control unit is configured to receive routing requests from the one or more basic control units and to perform lookup operations on said routing information in the one or more second lookup units based on said received routing requests.

3. The apparatus of claim 2, wherein less than all of said one or more second lookup units are selectively enabled when performing a particular lookup operation on said routing information in the one or more second lookup units.

4. The apparatus of claim 1, wherein a particular packet includes the route identifier;

wherein the supervisor control unit includes one or more second lookup units;

wherein each of the one or more basic control units is configured to communicate the particular packet to the supervisor control unit when its one or more first lookup units do not include the routing information subset corresponding to the route identifier;

wherein the supervisor control unit is configured to receive the particular packet and to perform lookup operation on the route identifier in the one or more second lookup units based on said received routing requests.

5. The apparatus of claim 4, wherein less than all of said one or more second lookup units are selectively enabled when performing said lookup operation on the route identifier in the one or more second lookup units.

6. The apparatus of claim 1, wherein less than all of said one or more first lookup units are selectively enabled when performing a particular lookup operation in its one or more first lookup units.

7. The apparatus of claim 1, comprising a supervisor line card including the supervisor control unit;

and a plurality of line cards, each of the plurality of line cards including a different one of the one or more basic control units.

8. The apparatus of claim 1;

wherein the first subset is left of the second subset in a Patricia tree representation, and wherein said adjusting the boundary includes determining a prefix left of the second subset and setting the boundary to the prefix supplemented with ones.

9. The apparatus of claim 1, wherein the first subset is left of the second subset in a Patricia tree representation, and wherein said adjusting the boundary includes determining a prefix right of the first subset and setting the boundary to the prefix supplemented with zeros.

10. An apparatus for routing or manipulating packets or other information based on a route identifier, the apparatus comprising:

a plurality of basic control units; and

a supervisor control unit, coupled to each of the said basic control units;

wherein the supervisor control unit includes;

means for partitioning a routing space into a plurality of routing information subsets such that for a particular prefix in a particular routing information subset, the particular routing information subset includes all longer prefixes beginning with said particular prefix in said routing information; and

means for distributing less than all of the plurality of routing information subsets to each of the said basic control units such that at least two of said basic control units are said distributed different subsets of said routing information subsets; and

wherein each of the one or more basic control units includes;

means for receiving said routing information subsets; and

means for determining a result based on the route identifier;

wherein said supervisor control unit is configured to provide additional one or more subsets of said routing information subsets to each particular basic control unit of said basic control units based on the routing requirements during operation of said particular basic control unit.

11. The apparatus of claim 10, wherein the supervisor control unit includes means for collecting statistics from said basic control units;

and wherein the supervisor control unit is configured to said provide additional one or more subsets of said routing information subsets to said basic control units in response to said statistics.

12. The apparatus of claim 10, wherein said means for partitioning the routing space includes means for deriving a Patricia tree representation including plurality of routing information subsets.

13. The apparatus of claim 10, wherein said means for determining the result based on the route identifier includes:

means for sending a request to the supervisor control unit; and

means for receiving the result from the supervisor control unit.

14. The apparatus of claim 13, wherein the supervisor control unit includes:

means for receiving the request;

means for determining the result based on the request; and

means for communicating the request to a particular basic control unit of said one or more basic control units.

15. The apparatus of claim 10, wherein said means for determining the result based on the route identifier includes means for forwarding a particular packet to the supervisor control unit.

16. The apparatus of claim 10, wherein the supervisor control unit is configured to repartition the routing space among the plurality of routing information subsets.

17. The apparatus of claim 16, wherein said repartitioning including modifying a boundary between a first and a second subsets of the plurality of routing information subsets.

18. A method for routing or manipulating packets or other information, the method comprising:

partitioning an information space into a plurality of information subsets such that for a particular prefix in a particular information subset, the particular information subset includes all longer prefixes beginning with said particular prefix in the information space;

distributing less than all of the plurality of information subsets to each of a plurality of basic control units such that at least two of said basic control units are said distributed different subsets of said routing information subsets;

performing a lookup operation in a particular one of said one or more basic control units based on a first identifier to identify a first result;

manipulating a first set of information based on the first result; and

providing additional one or more subsets of said information subsets to each particular basic control unit of said basic control units based on the requirements during operation of said particular basic control unit.

19. The method of claim 18, including providing the particular one of said one or more basic control units an additional information subset of the plurality of information subsets.

20. The method of claim 18, wherein said partitioning the information space includes deriving a Patricia tree representation including the plurality of information subsets.

21. The method of claim 18, further comprising:

the particular one of said one or more basic control units identifying a second identifier;

the particular one of said one or more basic control units determining that an information subset corresponding to the second identifier is not stored within the particular one of said one or more basic control units;

the particular one of said one or more basic control units sending a request to a control unit;

the control unit returning a response to the particular one of said one or more basic control units; and

the particular one of said one or more basic control units manipulating a second set of information based on the second result.

22. The method of claim 18, further comprising:

the particular one of said one or more basic control units identifying a second identifier;

the particular one of said one or more basic control units determining that an information subset corresponding to the second identifier is not stored within the particular one of said one or more basic control units;

the particular one of said one or more basic control units sending a request to process the second to a control unit;

the control unit performing a lookup operation based on the second identifier to generate a second result; and

the control unit manipulating a second set of information based on the second result.

23. The method of claim 18, comprising:

repartitioning the information among the plurality of information subsets.

24. The method of claim 23, wherein said repartitioning including modifying a boundary between a first and a second subsets of the plurality of information subsets.