Method and apparatus for packet classification in a data communication system

• US 6,600,744 B1
• Filed: 03/23/1999
• Issued: 07/29/2003
• Est. Priority Date: 03/23/1999
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel Canada Inc. (Nokia Corporation)
• Inventors: Nadj, Paul, Carr, David W.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Pezzlo, John
• Application Number:
  US09/274,720
• Time in Patent Office: 1,589 Days
• Field of Search: 370/389, 370/392, 370/412, 370/428, 370/465, 370/466, 370/218, 709/230, 709/238, 709/228, 709/240
• US Class Current: 370/392
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

A method and apparatus for packet classification stores rules or parameters for classifying the packets in a memory structure. The memory structure receives a set of rule selection signals, where the memory provides a selected set of rules in response to the rule selection signals. A comparison block operably coupled to the memory receives a key, which is also preferably derived from the header information for the packet. The key includes the relevant information for classifying the packet according to the rules stored in the memory. The comparison block compares the key with each of the rules in the selected set of rules, and when a favorable comparison is determined, the comparison block provides an indication of the favorable comparison. A prioritization block operably coupled to the comparison block prioritizes the rules that resulted in a favorable comparison to determine a preferred rule, where the preferred rule includes the resulting classification information for the packet.

Claims

1. A packet classification engine comprising:

a memory, wherein the memory stores a plurality of rules, wherein each rule of the plurality of rules defines a region in an N-dimensional space, wherein the memory is operably coupled to receive rule selection signals, wherein a first set of rule selection signals selects a selected set of rules of the plurality of rules, wherein the selected set of rules includes at least one rule;

a comparison block operably coupled to the memory, wherein the comparison block is operably coupled to receive a key, wherein the key defines a point within the N-dimensional space, wherein the comparison block compares the key to the selected set of rules, wherein when the comparison block determines a favorable comparison between the key and a matching rule within the selected set of rules, the comparison block generates an indication of the favorable comparison, wherein the favorable comparison indicates that the point defined by the key is within the region defined by the matching rule; and

a prioritization block operably coupled to the comparison block, wherein the prioritization block receives indications of favorable comparisons and determines a preferred favorable comparison from the indications, wherein the preferred favorable comparison determines a preferred rule of the plurality of rules.

2. The packet classification engine of claim 1 further comprises a key generation block operably coupled to the comparison block, wherein the key generation block extracts fields from a header of a data communication packet and generates the key based on the fields.

3. The packet classification engine of claim 1 further comprises a result register, wherein each rule stored in the memory includes result data, wherein the prioritization block stores in the result register result data corresponding to the preferred rule.

4. The packet classification engine of claim 1, wherein the memory is a dynamic random access memory (DRAM) that provides at least one row of data that includes the selected set of rules in response to the first set of rule selection signals.

5. A packet classification engine, comprising:

a data array, wherein the data array stores a plurality of data sets;

a data selection block operably coupled to the data array, wherein the data selection block selects a selected set of data sets from the plurality of data sets based on data selection information, wherein the selected set of data sets includes at least one data set;

a comparison block operably coupled to the data array, wherein the comparison block is operably coupled to receive a key data set, wherein the comparison block compares the key data set with each data set of the selected set of data sets to generate comparison results; and

a prioritization block operably coupled to the comparison block, wherein the prioritization block prioritizes the comparison results to determine a preferred matching data set having a favorable comparison to the key data set.

6. The packet classification engine of claim 5 further comprises a result buffer operably coupled to the prioritization block, wherein each of the plurality of data sets includes result data, wherein result data corresponding to the preferred matching data set is stored in the result buffer.

7. The packet classification engine of claim 6, wherein the data selection block further comprises a lookup table operably coupled to receive a start index as part of the data selection information, wherein the lookup table generates an offset based on the start index, wherein the offset is used to determine the selected set of data sets.

8. The packet classification engine of claim 7, wherein the data selection block further comprises a linked list operably coupled to receive the offset, wherein the linked list provides a subsequent offset in response to the offset, wherein the subsequent offset is used to select a subsequent set of data sets for comparison with the key data set.

9. The packet classification engine of claim 5, wherein the data array further comprises a random access memory, wherein the data selection block selects a row within the random access memory, wherein data sets stored in the row are provided to the comparison block.

10. The packet classification engine of claim 9, wherein the data sets stored in the random access memory include rules corresponding to handling of data packets in a data communications system.

11. The packet classification engine of claim 5, wherein the comparison block further comprises a plurality of comparators that are configurable to allow comparison of the key data set with the selected set of data sets, wherein outputs of the plurality of comparators are merged to produce the comparison results.

12. The packet classification engine of claim 11, wherein adjacent comparators of the plurality of comparators are concatenated to perform comparisons of a concatenated comparison width that is greater than a maximum non-concatenated width associated with non-concatenated comparisons utilizing non-concatenated comparators.

13. The packet classification engine of claim 11, wherein the plurality of comparators includes multiple comparators for a particular portion of the key data set and a corresponding portion of each data set of the selected set of data sets, wherein an partial comparison result is selected from results of the multiple comparators based on comparison selection data in one of the key data set and the selected set of data sets.

14. The packet classification engine of claim 11, wherein the plurality of comparators includes at least one of equality comparators, range comparators, mask and compare comparators, and mask and range comparators.

15. The packet classification engine of claim 5 further comprises a control processor interface operably coupled to the data array, wherein the control processor interface allows an external processor to modify data sets in the data array.

16. The packet classification engine of claim 5 further comprises a first request interface operably coupled to the comparison block and the data selection block, wherein the first request interface is operably coupled to receive comparison requests, wherein each of the comparison requests includes a corresponding key data set and corresponding data selection information.

17. The packet classification engine of claim 5, wherein the request interface further comprises a request buffer, wherein the request buffer stores pending comparison requests.

18. The packet classification engine of claim 17 further comprises:

a control processor interface operably coupled to the data array, wherein the control processor interface allows an external processor to modify data sets in the data array; and

a scheduler operably coupled to the control processor interface, the request interface, and the data selection block, wherein the scheduler controls ordering of execution of comparison requests and modifications to the data sets in the data array.

19. The packet classification engine of claim 18 further comprises a sequencer operably coupled to the prioritization block, the scheduler, and the data selection block, wherein the sequencer provides the data selection information to the data selection block based on whether the prioritization block has determined the preferred matching data set.

20. The packet classification engine of claim 18 further comprises a second request interface operably coupled to the comparison block and the scheduler, wherein the second request interface is operably coupled to receive additional comparison requests for execution.

21. The packet classification engine of claim 5, wherein the packet classification engine is implemented as an integrated circuit.

22. A method for packet classification, comprising:

receiving a packet classification request, wherein the packet classification request includes a key and a start index;

generating a first address offset based on the start index;

applying the first address offset to a memory, wherein the memory stores a plurality of rules, wherein the memory provides a first set of rules in response to the first address offset;

comparing each rule of the first set of rules with the key; and

when at least one of the rules in the first set of rules compares favorably with the key, selecting a preferred rule from rules in the first set of rules that compare favorably with the key.

23. The method of claim 22 further comprises:

storing a result value corresponding to the preferred rule in a register, wherein each rule of the plurality of rules stored in the memory includes a corresponding result value; and

asserting a signal indicating that the register contains the result value.

24. The method of claim 22 further comprises:

when all of the rules in the first set of rules compares unfavorably with the key;

generating a second address offset based on the first address offset;

applying the second address offset to the memory, wherein the memory provides a second set of rules in response to the second address offset;

comparing each rule of the second set of rules with the key; and

when at least one of the rules in the second set of rules compares favorably with the key, selecting the preferred rule from rules in the second set of rules that compare favorably with the key.

25. The method of claim 24, wherein generating the second address offset further comprises applying the first address offset to a linked list, wherein the linked list provides the second address offset in response to the first address offset.

26. The method of claim 22, wherein selecting the preferred rule further comprises structuring the rules in an ordered pattern in the memory such that the preferred rule is a first rule in the ordered pattern that compares favorably with the key.

27. The method of claim 22, wherein generating the first address offset further comprises applying the start index to a lookup table, wherein the lookup table returns the first address offset in response to the start index.

28. A method for packet classification, comprising:

receiving a packet classification request, wherein the packet classification request includes a key and a start index;

generating a first address offset based on the start index;

applying the first address offset to a memory, wherein the memory stores a plurality of rules, wherein the plurality of rules includes at least a first class of rules and a second class of rules, wherein the memory provides a first set of rules in response to the first address offset, wherein the first set of rules includes rules from the first class and the second class;

comparing each rule of the first set of rules with the key;

when at least one of the rules from the first class of rules in the first set of rules compares favorably with the key, selecting a preferred first class rule from first class rules in the first set of rules that compare favorably with the key;

when at least one of the rules from the second class of rules in the first set of rules compares favorably with the key, selecting a preferred second class rule from second class rules in the first set of rules that compare favorably with the key; and

when at least one of the preferred first class rule and the preferred second class rule is not selected based on comparison of the key with the first set of rules;

generating a second address offset based on the first address offset;

applying the second address offset to the memory, wherein the memory provides a second set of rules in response to the second address offset, wherein the second set of rules includes rules from the first class and the second class; and

comparing each rule of the second set of rules with the key, wherein when a favorable comparison is determined for a rule of a class for which a preferred rule has not been selected, selecting the preferred rule from rules in the second set of rules that compare favorably with the key.

29. The method of claim 28, wherein generating the second address offset further comprises applying the first address offset to a linked list, wherein the linked list provides the second address offset in response to the first address offset.

30. The method of claim 28, wherein selecting a preferred rule for each of the first class and the second class further comprises structuring the rules in an ordered pattern in the memory such that the preferred rule for each of the first class and the second class is a first rule, for each respective class, in the ordered pattern that compares favorably with the key.

31. The method of claim 28, wherein generating the first address offset further comprises applying the start index to a lookup table, wherein the lookup table returns the first address offset in response to the start index.