Apparatus and method for two-stage packet classification using most specific filter matching and transport level sharing

• US 20050226235A1
• Filed: 04/08/2004
• Published: 10/13/2005
• Est. Priority Date: 04/08/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kounavis, Michael E., Chandra, Prashant R., Kumar, Alok, Kuo, Chen-Chi, Lakshmanamurthy, Sridhar, Yavatkar, Raj, Vin, Harrick M.
• Granted Patent: US 7,525,958 B2
• Time in Patent Office: Days
• US Class Current: 370/386
• 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 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and apparatus for two-stage packet classification. In the first stage, which may be implemented in software, a packet is classified on the basis of the packet'"'"'s network path and, perhaps, its protocol. In the second stage, which may be implemented in hardware, the packet is classified on the basis of one or more transport level fields of the packet. An apparatus of two-stage packet classification may include a processing system for first stage code execution, a classification circuit for performing the second stage of classification, and a memory to store a number of bins, each bin including one or more rules.

Claims

1. A method comprising:

providing a plurality of bins stored in a memory, each of the bins including a number of rules, each rule specifying a source port range and a destination port range;

identifying, from the plurality of bins, a bin corresponding to a network path and a protocol of a received packet;

comparing a source port and a destination port of the received packet with the rules of the corresponding bin; and

if the source port of the received packet is within the source port range of a rule and the destination port of the received packet is within the destination port range of the rule, applying an action associated with the rule to the received packet.

2. The method of claim 1, wherein the rule matching the source and destination ports of the received packet comprises a highest priority matching rule.

3. The method of claim 1, wherein:

the source port range of each rule is specified by a source port lower bound and a source port upper bound;

and the destination port range of each rule is specified by a destination port lower bound and a destination port upper bound.

4. The method of claim 3, wherein:

the source port of the received packet is within the source port range of a rule if the packet'"'"'s source port is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and

the destination port of the received packet is within the destination port range of the rule if the packet'"'"'s destination port is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

5. The method of claim 1, wherein identifying a bin corresponding to a network path and a protocol of a received packet comprises:

identifying, from a number of entries in a data structure, an entry having a source address prefix matching a source address of the received 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 a destination address of the received packet, the matching entry including a second identifier; and

identifying, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

6. The method of claim 1, wherein identifying a bin corresponding to a network path and a protocol of a received packet comprises:

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 index, the second index, and the protocol; and

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;

wherein an entry of the primary table matching the key will identify the corresponding bin.

7. The method of claim 6, further comprising:

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

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

wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

8. The method of claim 7, wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

9. The method of claim 6, 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 index, the sixth index, and the protocol; and

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;

wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

10. The method of claim 9, 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.

11. A method comprising:

identifying, from a plurality of bins stored in a memory, a bin corresponding to a network path of a received packet, each of the bins including a number of rules;

issuing a command to a classification circuit, the command identifying the corresponding bin;

copying the rules of the corresponding bin from the memory to the classification circuit, wherein the classification circuit compares at least one transport level field of the received packet with each of the rules and provides a match signal if a rule matches the at least one transport level field of the packet; and

in response to the match signal, applying an action associated with the matching rule to the received packet.

12. The method of claim 11, wherein the matching rule comprises a highest priority matching rule.

13. The method of claim 11, wherein the at least one transport level field of the received packet comprises a source port and a destination port.

14. The method of claim 13, wherein each rule of a bin includes a source port lower bound, a source port upper bound, a destination port lower bound, and a destination port upper bound.

15. The method of claim 14, wherein a rule matches the at least one transport level field of the packet if:

the source port of the received packet is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and

the destination port of the received packet is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

16. The method of claim 11, wherein the corresponding bin further corresponds to a protocol associated with the received packet.

17. The method of claim 16, wherein identifying a bin corresponding to a network path of a received packet comprises:

identifying, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the received 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 received packet, the matching entry including a second identifier; and

identifying, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

18. The method of claim 16, wherein identifying a bin corresponding to a network path of a received packet comprises:

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 index, the second index, and the protocol; and

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;

wherein an entry of the primary table matching the key will identify the corresponding bin.

19. The method of claim 18, further comprising:

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

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

wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

20. The method of claim 19, wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

21. The method of claim 18, 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 index, the sixth index, and the protocol; and

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;

wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

22. The method of claim 21, 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.

23. An apparatus comprising:

a memory, the memory having a plurality of bins stored therein, each bin including a number of rules;

a processing system, the processing system programmed to identify, from the plurality of bins, a bin corresponding to a network path of a received packet; and

a classification circuit coupled with the memory and the processing system, the classification circuit to identify, from the rules of the corresponding bin, a rule matching at least one transport level field of the packet.

24. The apparatus of claim 23, wherein the rule matching the at least one transport level field comprises a highest priority matching rule.

25. The apparatus of claim 23, wherein the at least one transport level field of the packet includes a source port and a destination port, and wherein each rule of a bin includes a source port lower bound, a source port upper bound, a destination port lower bound, and a destination port upper bound.

26. The apparatus of claim 25, wherein the classification circuit comprises:

a first comparison circuit to compare the source port of the received packet with the source port lower and upper bounds of one of the rules;

a second comparison circuit to compare the destination port of the received packet with the destination port lower and upper bounds of the rule; and

an output circuit to output a match signal if a rule of the corresponding bin matches the source and destination ports of the received packet.

27. The apparatus of claim 26, wherein the rule matches the source and destination ports of the received packet if:

the source port of the received packet is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and

the destination port of the received packet is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

28. The apparatus of claim 23, wherein the corresponding bin further corresponds to a protocol associated with the received packet.

29. The apparatus of claim 28, wherein to identify a bin corresponding to a network path of a received packet, the processing system is programmed to perform operations including:

identifying, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the received 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 received packet, the matching entry including a second identifier; and

identifying, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

30. The apparatus of claim 28, wherein to identify a bin corresponding to a network path of a received packet, the processing system is programmed to perform operations including:

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 index, the second index, and the protocol; and

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;

wherein an entry of the primary table matching the key will identify the corresponding bin.

31. The apparatus of claim 30, wherein to identify a bin corresponding to a network path of a received packet, the processing system is programmed to perform operations further including:

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

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

wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

32. The apparatus of claim 31, wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

33. The apparatus of claim 30, wherein to identify a bin corresponding to a network path of a received packet, the processing system is programmed to perform operations further including:

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 index, the sixth index, and the protocol; and

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;

wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

34. The apparatus of claim 33, 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.

35. The apparatus of claim 23, wherein the memory, the processing system, and the classification circuit comprise a single processing device.

36. A system comprising:

a bus;

a processing device coupled with the bus, the processing device including

a memory, the memory having a plurality of bins stored therein, each bin including a number of rules,

a processing engine, the processing engine programmed to identify, from the plurality of bins, a bin corresponding to a network path of a received packet, and

a classification circuit coupled with the memory and the processing engine, the classification circuit to identify, from the rules of the corresponding bin, a rule matching at least one transport level field of the packet; and

a network interface coupled with the bus, the network interface to couple the system with an optical link.

37. The system of claim 36, wherein the rule matching the at least one transport level field comprises a highest priority matching rule.

38. The system of claim 36, wherein the at least one transport level field of the packet includes a source port and a destination port, and wherein each rule of a bin includes a source port lower bound, a source port upper bound, a destination port lower bound, and a destination port upper bound.

39. The system of claim 38, wherein the classification circuit comprises:

a first comparison circuit to compare the source port of the received packet with the source port lower and upper bounds of one of the rules;

a second comparison circuit to compare the destination port of the received packet with the destination port lower and upper bounds of the rule; and

an output circuit to output a match signal if a rule of the corresponding bin matches the source and destination ports of the received packet.

40. The system of claim 39, wherein the rule matches the source and destination ports of the received packet if:

the source port of the received packet is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and

the destination port of the received packet is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

41. The system of claim 36, wherein the corresponding bin further corresponds to a protocol associated with the received packet.

42. The system of claim 41, wherein to identify a bin corresponding to a network path of a received packet, the processing engine is programmed to perform operations including:

identifying, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the received 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 received packet, the matching entry including a second identifier; and

identifying, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

43. The system of claim 41, wherein to identify a bin corresponding to a network path of a received packet, the processing engine is programmed to perform operations including:

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 index, the second index, and the protocol; and

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;

wherein an entry of the primary table matching the key will identify the corresponding bin.

44. The system of claim 43, wherein to identify a bin corresponding to a network path of a received packet, the processing engine is programmed to perform operations further including:

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

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

wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

45. The system of claim 44, wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

46. The system of claim 43, wherein to identify a bin corresponding to a network path of a received packet, the processing engine is programmed to perform operations further including:

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 index, the sixth index, and the protocol; and

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;

wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

47. The system of claim 46, 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.

48. The system of claim 36, wherein the memory comprises a static random access memory (SRAM).

49. An article of manufacture comprising:

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

identify, from a plurality of bins stored in a memory, a bin corresponding to a network path of a received packet, each of the bins including a number of rules;

issue a command to a classification circuit, the command identifying the corresponding bin;

copy the rules of the corresponding bin from the memory to the classification circuit, wherein the classification circuit compares at least one transport level field of the received packet with each of the rules and provides a match signal if a rule matches the at least one transport level field of the packet; and

in response to the match signal, apply an action associated with the matching rule to the received packet.

50. The article of manufacture of claim 49, wherein the matching rule comprises a highest priority matching rule.

51. The article of manufacture of claim 49, wherein the at least one transport level field of the received packet comprises a source port and a destination port, and wherein each rule of a bin includes a source port lower bound, a source port upper bound, a destination port lower bound, and a destination port upper bound.

52. The article of manufacture of claim 51, wherein a rule matches the at least one transport level field of the packet if:

the source port of the received packet is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and

the destination port of the received packet is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

53. The article of manufacture of claim 49, wherein the corresponding bin further corresponds to a protocol associated with the received packet.

54. The article of manufacture of claim 53, wherein the content, when accessed, further causes the machine, when identifying a bin corresponding to a network path of a received packet, to:

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

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

identify, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

55. The article of manufacture of claim 53, wherein the content, when accessed, further causes the machine, when identifying a bin corresponding to a network path of a received packet, to:

search 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;

search 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;

form a key from the first index, the second index, and the protocol; and

search 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;

wherein an entry of the primary table matching the key will identify the corresponding bin.

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

search a first of two secondary tables for an entry matching a key formed from the third index and the protocol, the first secondary table including a number of entries, each entry corresponding to a partially specified filter; and

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

wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

57. The article of manufacture of claim 56, wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

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

search 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;

search 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;

form a second key from the fifth index, the sixth index, and the protocol; and

search 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;

wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

59. The article of manufacture of claim 58, 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.