Programmable hash-tuple generation with parallel rule implementation independence

• US 7,894,440 B2
• Filed: 03/13/2009
• Issued: 02/22/2011
• Est. Priority Date: 03/13/2009
• Status: Expired due to Fees

• Current Assignee: North Star Innovations Inc. (Wi-LAN Inc.)
• Original Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Inventors: Xu, Kun, Kramer, David
• Primary Examiner(s): Vu, Thong H
• Application Number:
  US12/404,140
• Publication Number:
  US 20100232434A1
• Time in Patent Office: 711 Days
• Field of Search: 370/352, 370/395, 370/360, 370/252, 370/230, 370/392, 709/223
• US Class Current: 370/392
• 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/745 Address table lookup; Address filtering

Abstract

Techniques have been developed to facilitate concurrent evaluation of hash rule entries in ways that allow an implementation to maintain a deterministic resultant hash irrespective of variations in the allocation of particular rules to particular storage banks or evaluation logic, such as may occur with rule set revisions. Similarly, uniform deterministic hash results can be assured even across a range of implementations that support greater or lesser levels of concurrent rule evaluations.

Claims

1. An apparatus comprising:

matching logic configured to concurrently evaluate packet header information against respective entries of a rule set coded in storage; and

a hash generator for calculating a hash result relative to the evaluated packet information, the hash generator including intermediate and final portions and a filtration stage coupled therebetween,

wherein the intermediate portion is configured as a chain of hash-intermediate stages each coupled to calculate a rule entry evaluation-specific contribution for possible inclusion in the hash and, for lower-order ones of the hash-intermediate stages, for possible propagation down chain and inclusion in a next higher-order hash-intermediate stage contribution, and

wherein the filtration stage is selective for a rule entry-specific contribution from a particular one of the hash-intermediate stages for supply to the final portion for use in completing calculation of the hash result.

2. The apparatus of claim 1, further comprising:

the storage, wherein the storage is implemented as plural banks of memory and wherein each of the concurrently evaluated against rule entries is accessed from a different one of the plural banks.

3. The apparatus of claim 1, further comprising:

first-level filtration stages coupled between the hash-intermediate stages of the chain, the first-level filtration stages selectively coupling respective values down chain for possible inclusion in the hash.

4. The apparatus of claim 3,

wherein, for a particular one of the first-level filtration stages, the value coupled down chain is selected, based on a corresponding evaluation by the matching logic, from a set of values that includes:

a rule entry-specific contribution from an immediately preceding hash-intermediate stage; and

an intermediate output from a previous cycle.

5. The apparatus of claim 3,

wherein the matching logic is coupled to supply selection control signals to respective ones of the first-level filtration stages.

6. The apparatus of claim 3,

wherein for individual ones the first-level filtration stages, selection of a contribution from the immediately preceding hash-intermediate stage for coupling down chain is based on a match-type evaluation of the match logic in accord with a corresponding hash-enabled one of the rule entries.

7. The apparatus of claim 3,

wherein the selected-from set of values further includes a hash reset value, and

wherein for individual ones the first-level filtration stages, selection of the hash reset value for coupling down chain is based on a fail-type evaluation of the match logic in accord with a compound set of the rule entries.

8. The apparatus of claim 7, wherein the compound set includes one or more of:

an AND chain of rule entries; and

a cluster of rule entries.

9. The apparatus of claim 1,

configured for multi-cycle operation whereby the packet header information is evaluated, in one or more successive cycles, against additional rule entries from the rule base;

and

further comprising a recycle path coupled from output the filtration stage back to the hash-intermediate stage for possible selection in a next cycle.

10. The apparatus of claim 9,

wherein upon completion and accumulation of an intermediate output that includes contribution from plural successive cycles and hash-intermediate stages thereof, the intermediate output is supplied to the final portion for use in the completing of the hash result calculating.

11. The apparatus of claim 1,

wherein the filtration stage is further selective amongst outputs of the hash-intermediate stages, a hash reset value, and a prior cycle intermediate output.

12. The apparatus of claim 1,

wherein the hash generator is implemented as multi-level logic and partitioned such that one or more initial levels thereof are replicated at each of the plural hash-intermediate stages of the intermediate portion and remaining levels thereof implement the final portion.

13. The apparatus of claim 1, further comprising:

plural processing resources,

wherein the hash generator is coupled to supply a load balancer with the hash result and thereby distribute packets to the plural processing resources.

14. The apparatus of claim 1,

configured as a communications controller in which the hash result is employed to maintain a core affinity routing of packet traffic.

15. A method of generating a hash in correspondence with evaluation of packet header information against constituent rule entries of a rule base, the method comprising:

concurrently performing plural evaluations of the packet header information against respective ones of the rule entries retrieved from storage;

calculating the hash relative to the evaluated packet information using logic partitioned into intermediate and final portions, wherein the intermediate portion of the hash calculating is performed using a chain of stages each coupled to supply a rule entry evaluation-specific contribution for possible inclusion in the hash and, for lower-order ones of the stages, to selectively propagate down chain a rule entry evaluation-specific contribution for possible inclusion in a next higher-order stage contribution, and

filtering the rule entry evaluation-specific contributions to select a particular one for supply to the final portion of the hash calculating.

16. The method of claim 15,

wherein the storage includes plural banks of memory, and

further comprising accessing each of the concurrently evaluated against rule entries from a different one of the plural banks.

17. The method of claim 15,

performing first-level filtering between the stages of the chain, the first-level filtering selectively coupling respective values down chain for possible inclusion in the hash.

18. The method of claim 15, wherein, for particular ones of the first-level filterings, the value coupled down chain is:

for a match-type evaluation of a hash-enabled rule, a rule entry-specific contribution from an immediately preceding stage; and

for a fail-type evaluation of a hash-enabled rule, a hash reset value.

19. The method of claim 15, further comprising:

repeating, relative first to an initial subset of the rule entries and thereafter for subsequent subsets thereof, both the concurrent evaluations of packet header information and the intermediate portion of the hash calculating, and

performing for each repetition of the intermediate portion of the hash calculating, second-level filtering to select a particular one of the rule entry evaluation-specific contributions for possible inclusion in the hash, wherein for an initial and successive non-final performances of the second-level filtering, the selected rule entry evaluation-specific contributions are fed back for inclusion in a next repeat of the intermediate portion of the hash calculating, and wherein a final performance of the second-level filtering constitutes the filtering to select a particular rule entry evaluation-specific contribution for supply to the final portion of the hash calculating.

20. An apparatus comprising:

means for concurrently performing plural evaluations of the packet header information against respective ones of the rule entries retrieved from storage;

means for calculating the hash relative to the evaluated packet information using logic partitioned into intermediate and final portions, wherein the intermediate portion of the hash calculating is performed using a chain of stages each coupled to supply a rule entry evaluation-specific contribution for possible inclusion in the hash and, for lower-order ones of the stages, to selectively propagate down chain a rule entry evaluation-specific contribution for possible inclusion in a next higher-order stage contribution;

means for filtering the rule entry evaluation-specific contributions to select a particular one for supply to the final portion of the hash calculating; and

means for repeating, relative first to an initial subset of the rule entries and thereafter for subsequent subsets thereof, both the concurrent evaluations of packet header information and the intermediate portion of the hash calculating.