Compact packet operation device and method

• US 7,869,411 B2
• Filed: 06/01/2006
• Issued: 01/11/2011
• Est. Priority Date: 11/21/2005
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Tzeng, Shrjie
• Primary Examiner(s): D AGOSTA, STEPHEN M
• Application Number:
  US11/444,373
• Publication Number:
  US 20070115966A1
• Time in Patent Office: 1,685 Days
• Field of Search: 370/338, 370/395, 370/389, 370/397, 370/401, 370/393, 370/351, 370/352, 370/355, 370/356, 455/418, 455/419, 455/420, 455/422.1, 455/450, 709/240
• US Class Current: 370/338
• 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/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A network device and a method of handling a frame in a network device defining a common header for each rule in a rules table of a search engine, wherein the common header comprises a source port specifying a corresponding rule to be applied to a port or ports, and a frame format specifying a format applied to the corresponding rule. A port receives a frame, with the frame having multiple field values. A pre-parser parses the received frame to obtain the field values and corresponding slices. A search engine receives the slices and determines matches between the slices and the common header of each rule in the rules table. A policy table performs indexing based on the determined matches to obtain an action entry. An action resolution takes an action based on the obtained action entry.

Claims

1. A method of handling a frame in an electronic network device, the method comprising:

receiving a frame having multiple field values at a port of the electronic network device;

parsing the received frame to obtain the field values and generating two or more slices from the received frame, wherein each slice contains at least some of the parsed field values including a source port field value and a frame format field value;

applying the two or more slices to a search engine having a rules table, wherein each rule in the rules table has a common header comprising a source port identifier specifying the port or ports to which the rule applies and a frame format identifier specifying the frame format to which the rule applies, wherein the source port identifier specifies that the rule applies to frames received on at least one of a specific port, an even port or any port, and the frame format identifier specifies the rule applies to at least one of 1 q_tagged frames, double_tagged frames, 802_—

2 frames, CPU frames, tagged frames, stacked frames, or stacked and tagged frames;

determining matching rules by matching information in the two or more slices with information in the common header of each rule in the rules table by executing a parallel comparison at wire speed between the information in the two or more slices and the information in the common header of each rule in the rules table;

selecting a highest priority rule from the matching rules;

using the address of the highest priority rule to index a policy table to obtain an action to perform on the received frame; and

performing the action obtained from the policy table on the received frame.

2. The method as recited in claim 1, wherein performing the action obtained from the policy table on the received frame comprises performing at least one of dropping the frame, replacing field values in the frame, redirecting the frame, changing the forwarding port map, adding a forwarding port, assigning a frame priority or changing the frame'"'"'s VLAN tag.

3. The method as recited in claim 1, wherein using the highest priority rule to index the policy table comprises using the address of the highest priority rule as an index into the policy table.

4. The method as recited in claim 1, wherein parsing the received frame to obtain the field values comprises parsing the received frame to obtain user defined field values for at least one of the two or more slices.

5. The method as recited in claim 1, wherein the rules in the rules table are programmed as entries in a Ternary Content Addressable Memory (TCAM).

6. The method as recited in claim 1, wherein at least three slices are generated from the received frame, and the field values contained in a third slice include source_port, frame format, tag_id, VLAN_tag, Length/Type, IP_protocol, IP_version, IP_DSCP, IP_TTL, and UDF field values, where TTL is a time-to-live field value and UDF is a user defined field value.

7. The method as recited in claim 1, wherein at least three slices are generated from the received frame, and the field values contained in a third slice include source_port, frame_format, IP_DA, L4_destination_port, L4_source_port, and UDF field values, where DA is a destination address field value and UDF is a user defined field value.

8. The method as recited in claim 1, further comprising processing the frame at a rate defined by a rate meter.

9. The method as recited in claim 1, wherein the number of slices generated from the frame depends upon the bandwidth required to process the frame.

10. An electronic network device to handle a frame, comprising:

a rules table, wherein each rule in the rules table has a common header comprising a source port identifier specifying the port or ports to which the rule applies, and a frame format identifier specifying the frame format to which the rule applies, wherein the source port identifier specifies that the rule applies to frames received on at least one of a specific port, an even port or any port, and the frame format identifier specifies the rule applies to at least one of 1 q_tagged frames, double_tagged frames, 802_—

2 frames, CPU frames, tagged frames, stacked frames, or stacked and tagged frames;

a port for receiving a frame, with the frame having multiple field values;

a pre-parser for parsing a received frame to obtain its field values and for generating two or more slices from the received frame, wherein each slice contains at least some of the parsed field values including a source port field value and a frame format field value;

a search engine for receiving the two or more slices, determining matches between information contained in the slices and the common header of each rule in the rules table by executing a parallel comparison at wire speed between the information contained in the two or more slices and the information contained in the common header of each rule in the rules table, and selecting a highest priority matching rule;

a policy table indexed by the address of the highest priority matching rule, for determining an action to perform on the received frame; and

an action resolution unit for acting on the received frame according to the action obtained from the policy table.

11. The network device as recited in claim 10, further comprising:

a rate meter defining a rate each frame or slice is to be processed and output.

12. The network device as recited in claim 10, wherein the action comprises at least one of dropping the frame, replacing field values in the frame, redirecting the frame, changing the forwarding port map, adding a forwarding port, assigning a frame priority or changing VLAN tag.

13. The network device as recited in claim 10, wherein the rules table comprises the contents of a Ternary Content Addressable Memory (TCAM).

14. The network device as recited in claim 10, wherein the pre-parser parses the received frame into at least three slices, and the field values contained in a third slice includes source_port, frame format, tag_id, VLAN_tag, Length/Type, IP_protocol, IP_version, IP_DSCP, IP_TTL, and UDF field values, where TTL is a time-to-live field value and UDF is a user defined field value.

15. The network device as recited in claim 10, wherein the pre-parser parses the received frame into at least three slices, and the field values contained in a third slice includes source_port, frame_format, IP_DA, L4_destination_port, L4_source_port, and UDF field values, where DA is a destination address field value and UDF is a user defined field value.

16. The network device as recited in claim 10, wherein the number of slices generated from the frame depends upon the bandwidth required to process the frame.

17. The network device as recited in claim 10, wherein the pre-parser parses the received frame to obtain user defined field values for at least one of the two or more slices.

18. A method of handling a frame in an electronic network device, the method comprising:

receiving a frame having multiple field values at a port of the electronic network device;

parsing the received frame to obtain the field values and generating two or more slices containing information parsed from the received frame, wherein the information contained in a first corresponding slice is predefined and includes the source port, frame format, destination MAC address and source MAC address, and the information contained in a second corresponding slice is programmable;

applying the two or more slices to a search engine having a rules table, wherein each rule in the rules table has a common header comprising a source port identifier specifying the port or ports to which the rule applies and a frame format identifier specifying the frame format to which the rule applies;

determining matching rules by matching information in the two or more slices with information in the common header of each rule in the rules table, wherein the matching rules are determined by executing a parallel comparison at wire speed between the information in the two or more slices and the information in the common header of each rule in the rules table;

selecting a highest priority rule when multiple matching rules are found;

using the address of the highest priority matching rule to index a policy table to obtain an action to perform on the received frame; and

performing the action obtained from the policy table on the received frame.

19. The method as recited in claim 18, wherein performing the action obtained from the policy table on the received frame comprises performing at least one of dropping the frame, replacing field values in the frame, redirecting the frame, changing the forwarding port map, adding a forwarding port, assigning a frame priority or changing the frame'"'"'s VLAN tag.

20. The method as recited in claim 18, wherein using the highest priority rule to index the policy table comprises using the address of the highest priority rule as an index into the policy table.

21. The method as recited in claim 18, wherein parsing the received frame to obtain the field values comprises parsing the received frame to obtain user defined field values for at least one of the two or more slices.

22. The method as recited in claim 18, wherein the rules in the rules table are programmed as entries in a Ternary Content Addressable Memory (TCAM).

23. The method as recited in claim 18, wherein at least three slices are generated from the received frame, and the field values contained in a third slice include source_port, frame_format, tag_id, VLAN_tag, Length/Type, IP_protocol, IP_version, IP_DSCP, IP_TTL, and UDF field values, where TTL is a time-to-live field value and UDF is a user defined field value.

24. The method as recited in claim 18, wherein at least three slices are generated from the received frame, and the field values contained in a third slice include source_port, frame_format, IP_DA, L4_destination_port, L4_source_port, and UDF field values, where DA is a destination address field value and UDF is a user defined field value.

25. The method as recited in claim 18, further comprising processing the frame at a rate defined by a rate meter.

26. The method as recited in claim 18, wherein the number of slices generated from the frame depends upon the bandwidth required to process the frame.

27. An electronic network device to handle a frame, comprising:

a rules table, wherein each rule in the rules table has a common header comprising a source port identifier specifying the port or ports to which the rule applies, and a frame format identifier specifying the frame format to which the rule applies;

a port for receiving a frame, with the frame having multiple field values;

a pre-parser for parsing a received frame to obtain its field values and for generating two or more slices containing information parsed from the received frame, wherein the information contained in a first corresponding slice is predefined and includes the source port, frame format, destination MAC address and source MAC address, and the information contained in a second corresponding slice is programmable;

a search engine for receiving the two or more slices and determining matches between information contained in the slices and the common header of each rule in the rules table, wherein the search engine determines the matches by executing a parallel comparison at wire speed between the information in the slices and the information in the common header of each rule in the rules table, selects a highest priority rule when multiple matches are found;

a policy table indexed by the addresses of the matched rules, for determining an action to perform on the received frame based on the address of the highest priority matched rule; and

an action resolution unit for acting on the received frame according to the action obtained from the policy table.

28. The network device as recited in claim 27, further comprising:

a rate meter defining a rate each frame or slice is to be processed and output.

29. The network device as recited in claim 27, wherein the action comprises at least one of dropping the frame, replacing field values in the frame, redirecting the frame, changing the forwarding port map, adding a forwarding port, assigning a frame priority or changing VLAN tag.

30. The network device as recited in claim 27, wherein the rules table comprises the contents of a Ternary Content Addressable Memory (TCAM).

31. The network device as recited in claim 27, wherein the pre-parser parses the received frame into at least three slices, and the field values contained in a third slice includes source_port, frame_format, tag_id, VLAN_tag, Length/Type, IP_protocol, IP_version, IP_DSCP, IP_TTL, and UDF field values, where TTL is a time-to-live field value and UDF is a user defined field value.

32. The network device as recited in claim 27, wherein the pre-parser parses the received frame into at least three slices, and the field values contained in a third slice includes source_port, frame_format, IP_DA, L4_destination_port, L4_source_port, and UDF field values, where DA is a destination address field value and UDF is a user defined field value.

33. The network device as recited in claim 27, wherein the number of slices generated from the frame depends upon the bandwidth required to process the frame.

34. The network device as recited in claim 27, wherein the pre-parser parses the received frame to obtain user defined field values for at least one of the two or more slices.