Combined pipelined classification and address search method and apparatus for switching environments

• US 20060002386A1
• Filed: 06/30/2004
• Published: 01/05/2006
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Synaptics Incorporated
• Original Assignee: Zarlink Semiconductor Inc. (Microchip Technology Incorporated)
• Inventors: Chang, Rong-Feng, Barrack, Craig, Lin, Eric, Ta, John, Yik, James
• Granted Patent: US 7,760,719 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

A packet switching node having a pipelined packet processing architecture processing packets received via an input port associated with the packet switching node is presented. The method performed by the apparatus includes: determining a packet frame type of the packet received; selectively extracting packet header field values specific to a packet frame type, the extracted packet header field value including packet addressing information; ascribing to the packet a preliminary action to be performed in respect of the packet; searching packet switching information tracked by the packet switching node based on extracted packet addressing information; formulating a preliminary switch response for the packet; classifying the packet into one of a plurality of packet flows; modifying the preliminary switch response in accordance with one of the preliminary action, the packet flow into which the packet was classified, and a default port action corresponding to the input port; modifying the packet header in accordance with one of the preliminary action, the packet flow, and the default port action; and processing the packet in accordance with the switch response. Advantages are derived from: pipelined processing of packets which enables short-cutting the rest of the processing for improper packets; a flexible frame type determination which is fast for well know frame types yet flexible in support of new frame types delaying obsolescence of a particular implementation; an early determination of a processing action which is successively refined by subsequent stages; a combined Layer-2 and Layer-3 network addressing search engine operating on short bit length indexed Layer-2 and Layer-3 network addresses reducing network address table storage requirements, requiring a reduced data transfer bandwidth for network address table access, a large external hashed primary network address table, and a small internal secondary network address table; an early determination of a switch response; and packet-classification-based switch response and packet header modification.

Claims

1. A packet switching node having a pipelined packet processing architecture for processing packets received via a plurality of packet switching node source ports, the packet switching node comprising:

a. means a packet header field value extractor for selectively extracting packet header field values from the plurality of packet header field values conveyed by each packet based on one of the source port via which the packet was received and a previously determined packet frame type;

b. means for ascribing a match type to the packet, the match type preclassifying the packet based on the extracted packet header field values irrespective of the format of the packet frame;

c. means for searching one of packet switching information, packet routing information, and protocol virtual local area networking information tracked by the packet switching node based on one of extracted packet header field values, the match type, and the source port for formulating a preliminary switch response for the packet; and

d. a packet classifier for classifying the packet into one of a plurality of packet processing flows based on one of the source port identifier, the preliminary switch response, extracted packet header field values, and the match type.

3. A packet switching node as claimed in claim 1, further comprising means for determining the packet frame type of each received packet, the frame type preclassifying the packet based on the format of the packet frame.

4. A packet switching node as claimed in claim 3, wherein the means for determining the packet frame type comprises one of:

a. a hardware frame type identification engine having hardware logic for inspecting packet header bit values and hardware logic for recognizing standardized packet header bit patterns;

b. a successive frame type elimination engine having hardware logic for conditionally subjecting packet header field values successively to a plurality of rules; and

c. a template match frame type identification engine including a plurality of packet header templates for comparison against packet header regions.

5. A packet switching node as claimed in claim 4, wherein the successive frame type elimination engine comprises one of:

a. a decision tree parsing engine per source port; and

b. a decision table per source port, each decision table having a plurality of decision table records, each decision tree record specifying a packet header offset of a frame type identification bit pattern, a frame type identification test bit pattern, and one of a jump instruction specifying the decision table row index of a subsequent decision table record and a frame type identifier.

6. A packet switching node as claimed in claim 4, further comprising a frame type selector for selecting a frame type when at least two of the hardware frame type identification engine, the successive frame type elimination engine, and the template match frame type identification engine identify differing frame types.

7. A packet switching node as claimed in claim 1, wherein the header field value extractor further comprises an extraction lookup table having a plurality of frame type indexed extraction table records, each record specifying packet header field offsets.

8. A packet switching node as claimed in claim 7, wherein the means for ascribing a match type comprises a match type specifier for each extraction table record.

9. A packet switching node as claimed in claim 8, wherein the header field value extractor further comprises means for ascribing a preliminary action to be performed in respect of the packet, each extraction table record further comprising a preliminary action specifier.

10. A packet switching node as claimed in claim 1, wherein the header field value extractor further comprises means for ascribing a preliminary action to be performed in respect of the packet.

11. A packet switching node as claimed in claim 1, wherein means for searching one of packet switching information, packet routing information, and protocol virtual local area networking information comprises:

a. a Layer-2 search engine interacting with a switching information database;

b. a Layer-3 search engine interacting with a routing information database; and

c. a virtual local area networking search engine interacting with a virtual area networking table.

12. A packet switching node as claimed in claim 1, wherein the packet classifier further comprises a classification rule table having classification rule entries, each classification rule entry having a match type specific format, each classification rule entry specifying a processing flow identifier to be conditionally associated with the packet if the conditions specified in the entry are met, each classification rule entry optionally specifying a rule weight specifying the precedence of the rule entry.

13. A packet switching node as claimed in claim 1, further comprising:

a. means for determining an action to be taken based on one of the source port, the frame type, and the processing flow classification;

b. a switch response modifier selectively modifying the preliminary switch response in accordance with the action;

c. a packet header modifier selectively modifying the packet header in accordance with the action; and

d. means for processing the packet in accordance with the switch response.

2. (canceled)

14. A method for processing packets received via a plurality of source ports of a packet switching node having a pipelined packet processing architecture, the method comprising:

a. selectively extracting packet header field values from the plurality of packet header field values conveyed by each packet based on one of the source port via which the packet was received and a previously determined packet frame type;

b. pre-classifying the packet, irrespective of the format of the packet frame, based on the extracted packet header field values and ascribing a match type to the packet;

c. searching one of packet switching information, packet routing information, and protocol virtual local area networking information tracked by the packet switching node based on one of extracted packet header field values, the match type, and the source port for formulating a preliminary switch response for the packet; and

d. classifying the packet into one of a plurality of packet processing flows based on one of the source port identifier, the preliminary switch response, extracted packet header field values, and the match type.

15. A method as claimed in claim 14, further comprising prior steps of pre-classifying each received packet based on the format of the packet frame and ascribing a frame type to the packet.

16. A method as claimed in claim 15, further comprising determining the frame type of the packet by one of:

a. inspecting packet header bit values and recognizing standardized packet header bit patterns;

b. conditionally subjecting packet header field values successively to a plurality of rules; and

c. comparing packet header regions against packet header templates.

17. A method as claimed in claim 16, wherein conditionally subjecting packet header filed values successively to a plurality of rules, the method further comprises:

a. subjecting a packet header field value extracted from the packet header based on a packet header offset specified in a decision table record of a plurality of decision table records stored in decision table to a frame type identification test bit pattern specified in the decision table record; and

b. selectively selecting a subsequent decision table record from the plurality of decision table records if a definitive frame type determination was not reached, and ascribing a frame type identifier specified in the decision table record otherwise.

18. A method as claimed in claim 16, further comprising selecting a frame type when at least two of inspecting packet header bit values and recognizing standardized packet header bit patterns, conditionally subjecting packet header field values successively to the plurality of rules, and comparing packet header regions against packet the header templates yields differing frame types.

19. A method as claimed in claim 14, wherein subsequent to selectively extracting packet header field values from the plurality of packet header field values conveyed by each packet, the method further comprises ascribing a preliminary action to be performed in respect of the packet.

20. A method as claimed in claim 14, wherein searching one of packet switching information, packet routing information, and protocol virtual local area networking information tracked by the packet switching node the method respectfully comprises:

a. querying a switching information database;

b. querying a routing information database; and

c. querying a virtual area networking table.

21. A method as claimed in claim 14, wherein classifying the packet into one of a plurality of packet processing flows the method further comprises conditionally ascribing a processing flow identifier to the packet based on conditions specified in one of a plurality of classification rule entries.

22. A method as claimed in claim 14, further comprising:

a. determining an action to be taken based on one of the source port, the frame type, and the processing flow classification;

b. selectively modifying the preliminary switch response in accordance with the action;

c. selectively modifying the packet header in accordance with the action; and

d. processing the packet in accordance with the switch response.