Method and apparatus for two-stage packet classification using most specific filter matching and transport level sharing

• US 20050083935A1
• Filed: 10/20/2003
• Published: 04/21/2005
• Est. Priority Date: 10/20/2003
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kounavis, Michael E., Kumar, Alok, Yavatkar, Raj, Vin, Harrick M.
• Granted Patent: US 7,408,932 B2
• Time in Patent Office: Days
• 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 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A method and apparatus for two-stage packet classification, the two-stage packet classification scheme including a first stage and a second stage. In the first classification stage, a packet is classified on the basis of the packet'"'"'s network path. In the second stage of classification, the packet is classified on the basis of one or more transport (or other) fields of the packet. Also disclosed are embodiments of most specific filter matching and transport level sharing, and either one or both of these techniques may be implemented in the two-stage classification method.

Claims

1. A method comprising:

determining a result based upon a network path of a received packet;

identifying, from a plurality of bins, at least one bin corresponding to the result, each of the plurality of bins including a number of sets of fields; and

searching the at least one corresponding bin to identify a set of fields matching the packet.

2. The method of claim 1, further comprising:

identifying an action associated with the set of matching fields; and

applying the action to the packet.

3. The method of claim 1, wherein the set of matching fields includes a transport level field.

4. The method of claim 1, wherein determining the result comprises identifying a single most specific filter matching the packet.

5. The method of claim 4, wherein the network path of the packet is expressed as a source address and a destination address.

6. The method of claim 5, wherein identifying the single most specific matching filter comprises:

performing a look-up in a first data structure to find an entry matching the source address of the packet; and

performing a look-up in a second data structure to find an entry matching the destination address of the packet.

7. A method comprising:

receiving a packet, the packet having a header including a source address, a destination address, and a number of other fields;

identifying, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the packet, the matching entry including a first identifier;

identifying, from a number of entries in another data structure, an entry having a destination address prefix matching the destination address of the packet, the matching entry including a second identifier;

identifying, from a number of bins, a bin corresponding to the first and second identifiers, the corresponding bin including a number of sets of transport level fields; and

comparing at least one of the other fields of the packet header with each set of transport level fields in the corresponding bin to find a matching set of transport level fields.

8. The method of claim 7, further comprising applying to the received packet an action associated with the matching set of transport level fields.

9. The method of claim 7, wherein the number of other fields in the packet header includes at least one of a protocol, a source port, and a destination port.

10. The method of claim 9, wherein the source address of the packet header comprises a source IP (Internet Protocol) address and the destination address of the packet header comprises a destination IP address.

11. A method comprising:

receiving a packet, the packet having a header including a source address, a destination address, and a number of transport level fields;

searching a source address data structure to find a first index and a third index, the first index associated with a fully specified filter having a source prefix matching the source address of the packet, the third index associated with a partially specified filter having a source prefix matching the source address of the packet;

searching a destination address data structure to find a second index and a fourth index, the second index associated with a fully specified filter having a destination prefix matching the destination address of the packet, the fourth index associated with a partially specified filter having a destination prefix matching the destination address of the packet;

forming a key from the first and second indexes;

searching a primary table for an entry matching the key, the primary table including a number of entries, each entry corresponding to one of a fully specified filter, a fully specified filter intersection, and an indicator filter; and

if a matching entry is found in the primary table, accessing a list of bin pointers associated with the matching entry, each bin pointer of the list identifying a bin containing a number of sets of transport level fields.

12. The method of claim 11, further comprising:

accessing one of the bins identified by one of the bin pointers in the matching entry of the primary table;

comparing the transport level fields of the packet with each set of transport level fields in the accessed bin; and

if the accessed bin has a set of transport level fields matching the transport level fields of the packet, applying an action associated with the matching set of transport level fields to the received packet.

13. The method of claim 11, further comprising:

searching a first of two secondary tables for an entry matching the third index, the first secondary table including a number of entries, each entry corresponding to a partially specified filter;

searching a second of the two secondary tables for an entry matching the fourth index, the second secondary table including a number of entries, each entry corresponding to a partially specified filter; and

if no match is found in the primary table and a matching entry is found in one of the two secondary tables, accessing a list of bin pointers associated with the matching entry, each bin pointer of the list identifying a bin containing a number of sets of transport level fields.

14. The method of claim 13, further comprising:

accessing one of the bins identified by one of the bin pointers in the matching entry of the one secondary table;

comparing the transport level fields of the packet with each set of transport level fields in the accessed bin; and

if the accessed bin has a set of transport level fields matching the transport level fields of the packet, applying an action associated with the matching set of transport level fields to the received packet.

15. The method of claim 13, further comprising:

if no match is found in either of the secondary tables, accessing a list of bin pointers associated with a default entry, each bin pointer of the list identifying a bin containing a number of sets of transport level fields.

16. The method of claim 15, wherein the default entry corresponds to an entire two-dimensional address space.

17. The method of claim 11, further comprising

searching the source address data structure to find a fifth index associated with a wide filter having a source prefix matching the source address of the packet;

searching the destination address data structure to find a sixth index associated with a wide filter having a destination prefix matching the destination address of the packet;

forming a second key from the fifth and sixth indexes;

searching a wide filter table for an entry matching the second key, the wide filter table including a number of entries, each entry corresponding to a wide filter; and

if no match is found in the primary table and a matching entry is found in the wide filter table, accessing a list of bin pointers associated with the matching entry in the wide filter table, each bin pointer of the list identifying a bin containing a number of sets of transport level fields.

18. The method of claim 17, further comprising:

accessing one of the bins identified by one of the bin pointers in the matching entry of the wide filter table;

comparing the transport level fields of the packet with each set of transport level fields in the accessed bin; and

if the accessed bin has a set of transport level fields matching the transport level fields of the packet, applying an action associated with the matching set of transport level fields to the received packet.

19. The method of claim 17, wherein each wide filter contained in the wide filter table comprises a fully specified filter having a number of indicator filters exceeding a specified threshold.

20. The method of claim 11, wherein the number of transport level fields in the received packet comprises at least one of a source port, a destination port, and a protocol.

21. A method comprising:

grouping a plurality of rules of a packet classification database into a number of rule sets, each rule set including rules having a source and destination address pair, each rule set associated with a filter corresponding to the source and destination address pair;

associating a small bin with each of the filters, each small bin including a group of a number of sets of transport level fields, each set of transport level fields in the group associated with one of the rules in the associated rule set.

22. The method of claim 21, wherein at least two of the filters are associated with a same small bin.

23. The method of claim 21, further comprising identifying a number of filter intersections, each filter intersection corresponding to an intersection of at least two of the filters.

24. The method of claim 23, further comprising associating a large bin with each of the filter intersections, the large bin of each filter intersection comprising a union of the small bins associated with each of the at least two filters of the intersection.

25. The method of claim 24, further comprising identifying a number of indicator filters, each indicator filter formed from a source address of one of the filters and the destination address of another of the filters.

26. The method of claim 25, wherein the filters associated with the classification database includes fully specified filters, partially specified filters extending an entire source address space, and partially specified filter extending an entire destination address space.

27. The method of claim 26, further comprising:

creating a primary table including a number of entries, each entry of the primary table associated with one of the fully specified filters, one of the filter intersections, or one of the indicator filters, each entry of the primary table including a key and at least one pointer to the small bin associated with the corresponding filter of that entry;

creating a first secondary table including a number of entries, each entry of the first secondary table associated with one of the partially specified filters having a source address extending the entire source address space, each entry of the first secondary table including a key and a pointer to the small bin associated with the corresponding filter of that entry; and

creating a second secondary table including a number of entries, each entry of the second secondary table associated with one of the partially specified filters having a destination address extending the entire destination address space, each entry f the second secondary table including a key and a pointer to the small bin associated with the corresponding filter of that entry.

28. The method of claim 27, wherein the at least one pointer in one entry of the primary table identifies a large bin associated with a corresponding filter intersection of that entry.

29. The method of claim 27, wherein the primary table includes a subset of the number of indicator filters.

30. The method of claim 27, wherein the filters associated with the classification database further includes wide filters.

31. The method of claim 30, further comprising creating a wide filter table including a number of entries, each entry of the wide filter table associated with one of the wide filters, each entry of the wide filter table including a key and a pointer to the small bin associated with the corresponding filter of that entry.

32. The method of claim 21, further comprising:

creating a source address data structure, the source address data structure including a number of entries, each of the entries including a source prefix corresponding to one of the filters; and

creating a destination address data structure, the destination address data structure including a number of entries, each of the entries including a destination prefix corresponding to one of the filters.

33. A data structure comprising:

a plurality of filters, each filter including a source address prefix and a destination address prefix; and

a plurality of bins, each bin comprising a number of triplets, each triplet including at least one transport level field, an action, and a priority;

wherein each of the plurality of filters is associated with at least one of the bins.

34. The data structure of claim 33, wherein one of the bins is associated with at least two of the filters.

35. The data structure of claim 33, wherein the source address prefix comprises a source IP (Internet Protocol) address prefix and the destination address prefix comprises a destination IP address prefix.

36. The data structure of claim 33, wherein the at least one transport level field comprises one of a protocol, a source port, and a destination port.

37. The data structure of claim 33, wherein each of at least some of the bins comprises a small bin.

38. The data structure of claim 37, wherein at least one of the bins comprises a large bin, the large bin comprising a union of the small bins associated with a filter intersection.

39. A data structure comprising:

a source address data structure, the source address data structure including a number of entries, each of the entries having a source prefix, a filter type, and an index;

a destination address data structure, the destination address data structure including a number of entries, each of the entries having a destination prefix, a filter type, and an index;

a primary table, the primary table including a number of entries, each of the entries having a key and at least one bin pointer, wherein each of the entries is associated with one of a fully specified filter, a fully specified filter intersection, and an indicator filter; and

two secondary tables, each of the secondary tables including a number of entries, each of the entries having a key and at least one bin pointer, wherein each entry of each of the two secondary tables is associated with a partially specified filter.

40. The data structure of claim 39, wherein one of the secondary tables is associated with partially specified filters having a source address expanding an entire source address space, and the other of the two secondary tables is associated with partially specified filters having a destination address expanding an entire destination address space.

41. The data structure of claim 39, wherein the filter type in each of the source address and destination address look-up tables indicates one of a fully specified filter and a partially specified filter.

42. The data structure of claim 39, further comprising a wide filter table, the wide filter table including a number of entries, each of the entries having a key and at least one bin pointer, wherein each entry of the wide filter table is associated with a wide filter.

43. The data structure of claim 42, wherein the filter type in each of the source address and destination address look-up tables indicates one of a fully specified filter, a partially specified filter, and a wide filter.

44. The data structure of claim 39, wherein each of the bin pointers in the entries of the primary and secondary tables identifies one of a plurality of bins of a second data structure, each bin including a number of triplets, each triplet having at least one transport level field, an action, and a priority

45. The data structure of claim 44, wherein each source address prefix in the source address data structure comprises a source IP (Internet Protocol) address prefix and each destination address prefix in the destination address data structure comprises a destination IP address prefix.

46. The data structure of claim 45, wherein the at least one transport level field comprises one of a protocol, a source port, and a destination port.

47. The data structure of claim 39, wherein the primary table includes entries for a subset of all possible indicator filters.

48. An apparatus comprising:

a processing device;

a memory coupled with the processing device, the memory having a first data structure stored therein, the first data structure including

a source address look-up data structure, the source address look-up data structure including a number of entries, each of the entries having a source prefix, a filter type, and an index,

a destination address look-up data structure, the destination address look-up data structure including a number of entries, each of the entries having a destination prefix, a filter type, and an index,

a primary table, the primary table including a number of entries, each of the entries having a key and at least one bin pointer, wherein each of the entries is associated with one of a fully specified filter, a fully specified filter intersection, and an indicator filter, and

two secondary tables, each of the secondary tables including a number of entries, each of the entries having a key and at least one bin pointer, wherein each entry of each of the two secondary tables is associated with a partially specified filter.

49. The apparatus of claim 48, further comprising:

a second memory coupled with the processing device, the second memory having a second data structure stored therein, the second data structure including a plurality of small bins, each small bin including a number of triplets, each triplet having at least one transport level field, an action, and a priority;

wherein each of the bin pointers in the entries of the primary and secondary tables identifies one of the small bins of the second data structure.

50. The apparatus of claim 49, wherein the second memory comprises a content addressable memory.

51. The apparatus of claim 49, wherein the at least one transport level field comprises one of a protocol, a source port, and a destination port.

52. The apparatus of claim 51, wherein the second data structure stored in the second memory includes at least one large bin, the large bin comprising a union of small bins associated with a filter intersection.

53. The apparatus of claim 48, wherein the memory comprises at least one of a SRAM, DRAM, SDRAM, and a DDRDRAM.

54. The apparatus of claim 48, wherein the memory comprises part of the processing device.

55. The apparatus of claim 48, wherein one of the secondary tables is associated with partially specified filters having a source address expanding an entire source address space, and the other of the two secondary tables is associated with partially specified filters having a destination address expanding an entire destination address space.

56. The apparatus of claim 48, wherein the filter type in each of the source address and destination address look-up tables comprises one of a fully specified filter and a partially specified filter.

57. The apparatus of claim 48, wherein the first data structure further comprises a wide filter table, the wide filter table including a number of entries, each of the entries having a key and at least one bin pointer, wherein each entry of the wide filter table is associated with one of a wide filter and an indicator filter.

58. The apparatus of claim 57, wherein the filter type in each of the source address and destination address look-up data structures comprises one of a fully specified filter, a partially specified filter, and a wide filter.

59. The apparatus of claim 48, wherein each source address prefix in the source address look-up data structure comprises a source IP (Internet Protocol) address prefix and each destination address prefix in the destination address look-up data structure comprises a destination IP address prefix.

60. The apparatus of claim 48, wherein the primary table includes entries for a subset of all possible indicator filters.

61. An apparatus comprising:

a content addressable memory (CAM), the CAM having stored therein a plurality of bins, each of the bins including a number of sets of fields; and

a processing device coupled with CAM, the processing device capable of determining a result based upon the network path of the packet and identify, from the plurality of bins, at least one bin corresponding to the result, the CAM to search the at least one corresponding bin to identify a set of fields matching the packet.

62. The apparatus of claim 61, wherein the CAM returns an action associated with the set of matching fields, the processing device capable of executing the action.

63. The apparatus of claim 61, wherein the matching set of fields includes a transport level field.

64. The apparatus of claim 61, wherein the processing device, when determining the result, identifies a single most specific filter matching the packet.

65. An article of manufacture comprising:

a machine accessible medium providing content that, when accessed by a machine, causes the machine to

determine a result based upon a network path of a received packet;

identify, from a plurality of bins, at least one bin corresponding to the result, each of the plurality of bins including a number of sets of fields; and

search the at least one corresponding bin to identify a set of fields matching the packet.

66. The article of manufacture of claim 65, wherein the content, when accessed, further causes the machine to:

identify an action associated with the set of matching fields; and

apply the action to the packet.

67. The article of manufacture of claim 65, wherein the set of matching fields includes a transport level field.

68. The article of manufacture of claim 65, wherein the content, when accessed, further causes the machine, when determining the result, to identify a single most specific filter matching the packet.

69. The article of manufacture of claim 68, wherein the network path of the packet is expressed as a source address and a destination address.

70. The article of manufacture of claim 69, wherein the content, when accessed, further causes the machine, when identifying the single most specific matching filter, to:

perform a look-up in a first data structure to find an entry matching the source address of the packet; and

perform a look-up in a second data structure to find an entry matching the destination address of the packet.