Granted Patent B2

US 7,760,719 · App. 10/881,226 · Granted Jul 20, 2010

Abstract

Claims (52)

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. a plurality of packet frame type determination engines configured to be employed in parallel for determining a packet frame type of a packet received via an input port of the packet switching node prior to extraction of packet header field values, wherein the plurality of packet frame type determination engines comprise:

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;

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

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

wherein frame type determinations by the successive frame type elimination engine and the template match frame type identification engine are prioritized over a frame type determination by the hardware frame type identification engine;

b. a packet header field value extractor for selectively extracting, without intermediate processing, packet header field values from the plurality of packet header field values conveyed by each packet based on the source port via which the packet was received;

c. 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;

d. 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

e. 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.

2. A packet switching node as claimed in claim 1 , 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.

3. A packet switching node as claimed in claim 1 , 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.

4. 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.

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

6. A packet switching node as claimed in claim 5 , 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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. determining, by a plurality of frame determination engines, a frame type of packets by:

1. inspecting, by a hardware frame type identification engine, packet header bit values and recognizing standardized packet header bit patterns;

2. conditionally subjecting, by a successive frame type elimination engine, packet header field values successively to a plurality of rules; and

3. comparing, by a template match frame type identification engine, packet header regions against packet header templates, wherein frame type determinations by the successive frame type elimination engine and the template match frame type identification engine are prioritized over a frame type determination by the hardware frame type identification engine;

b. selectively extracting, without intermediate processing, packet header field values from the plurality of packet header field values conveyed by each packet based on the source port via which the packet was received;

c. 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;

d. 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

e. 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.

12. A method as claimed in claim 11 , 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.

13. A method as claimed in claim 11 , 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.

14. A method as claimed in claim 11 , 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.

15. A method as claimed in claim 11 , 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 respectively comprises:

a. querying a switching information database;

b. querying a routing information database; and

c. querying a virtual area networking table.

16. A method as claimed in claim 11 , 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.

17. A method as claimed in claim 11 , 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.

Assignments (11)