Method and system for frame and protocol classification

• US 6,775,284 B1
• Filed: 01/07/2000
• Issued: 08/10/2004
• Est. Priority Date: 01/07/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Heddes, Marco C., Leavens, Ross Boyd, Calvignac, Jean Louis, Siegel, Michael Steven, Davis, Gordon Taylor, Gallo, Anthony Matteo
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Swickhamer, Christopher M
• Application Number:
  US09/479,027
• Time in Patent Office: 1,677 Days
• Field of Search: 370/252, 370/254, 370/255, 370/392, 370/455, 370/466, 370/469, 370/470, 370/471, 370/474, 370/476, 370/395.5, 709/201, 709/238, 709/249
• US Class Current: 370/392
• CPC Class Codes: H04L 69/18 Multiprotocol handlers, e.g. single devices capable of handling multiple protocols
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A system and method of protocol and frame classification in a system for data processing (e.g., switching or routing data packets or frames). The present invention includes analyzing a portion of the packet or frame according to predetermined tests, then storing key characteristics of the packet for use in subsequent processing of the frame. The key characteristics for the frame (or input information unit, such as the type of layer 3 protocol used in the frame, the layer 2 encapsulation technique, the starting instruction address and flags indicating whether the frame uses a virtual local area network, preferably using hardware to quickly and in a uniform time period. The stored key characteristics of the packet are then used by the network processing complexes in its further processing of the frame. The processor is preconditioned with a starting instruction address and the location of the beginning of the layer 3 header as well as flags for the type of frame. That is, the instruction address or code entry point is used by the processor to start processing for a frame at the right place, based on the type of frame. Additionally, additional instruction addresses can be stacked and used sequentially at branches to avoid additional tests and branching instructions.

Claims

1. An apparatus comprising:

a semiconductor substrate;

N processing units fabricated on the substrate, where N>

1;

first internal data memory fabricated on said substrate, said data memory for storing information accessible to said N processing units;

a dispatcher fabricated on the semiconductor substrate and operatively coupled to the N processing units for receiving and transmitting to one of the N processing units an input information unit;

a classifier coupled to the dispatcher, said classifier fabricated on the semiconductor substrate and including a comparison unit for determining a data format for an input information unit and for generating and storing in the internal data memory output indicators for the input information unit output indicators indicating the data format of the input information unit and a starting address for the input information unit, indicators and the starting address which are available to the one of the N processing units during its processing the input information unit and used in the processing of the input information unit; and

a completion unit carried on the semiconductor substrate and operatively connected to the N processing units for receiving the information unit processed by the one of the N processing units.

2. An apparatus of the type described in claim 1 wherein the comparison unit includes a test for a virtual local area network field contained in the input information data and the generated output indicators include an indicator for identifying the presence of the virtual local area network field in the input information unit.

3. The apparatus of claim 1 wherein the classifier includes a plurality of hardware devices formed in the substrate.

4. An apparatus of the type described in claim 1 wherein the output indicators include indicators identifying the type of input information unit and its layer 2 encapsulation technique.

5. An apparatus of the type described in claim 1 wherein the indicators include a default code entry point.

6. An apparatus of the type described in claim 1 wherein the classifier includes a system for determining a code entry point based on the type of input information unit and its encapsulation technique as determined by the classifier.

7. An apparatus of the type described in claim 1 wherein the classifier includes a system for determining a default code entry point and a code entry point based on the type of input information unit.

8. An apparatus of the type described in claim 7 wherein the apparatus further includes a selector for selecting from the default code entry point and the code entry point based on the type of input information unit.

9. An apparatus of the type set forth in claim 8 further including a system for identifying whether virtual local area network information is included in the input information unit.

10. A method of processing an input information unit comprising the steps of:

receiving the input information unit at a dispatcher;

sending the input information unit from the dispatcher to one of a plurality of processors for processing;

reading selected bits from the input information unit while the information unit is being sent from the dispatcher to the one of the plurality of processors without using a plurality of look-up tables and concatenated classification keys;

testing the read bits from the input information unit against known indicators identifying predetermined types of input information units to identify the type and protocol of the input information unit or that the input information unit does not meet any predetermined identifying type of input information unit; and

based on the results of the testing of bits from the input information unit, storing indicators of the type of input information unit and other information about that input information unit; and

using at the one of a plurality of processing units the stored indicators and the other stored information about the input information unit in the processing of the input information unit.

11. A method including the steps of claim 10 wherein the step of generating the indicators and storing the indicators occurs while the input information unit is being sent to one of the plurality of processors so that, when the one of the plurality of processors processes the input information unit, the indicators and the other information have been determined and stored and the one of the plurality of processors uses the indicators and other information about the input information unit in processing that input information unit.

12. A method including the steps of claim 10 and further including the step of generating a starting address for the further processing of the input information unit based on the content of the input information unit and the step of using the stored indicators at the one of the plurality of processing units includes using the starting address.

13. A method including the steps of claim 10 wherein the step of reading and testing is accomplished in hardware, whereby the process is accomplished in fewer processing cycles than if the reading and testing was accomplished by executing a series of stored instructions.

14. A method including the steps of claim 13 wherein the step of using hardware to accomplish the identification of the type of input information unit and storing indicators is accomplished within two machine cycles, whereby the step of using the indicators in one of the plurality of processing units occurs earlier than if the tests were accomplished by executing a series of programmed instructions in sequence.

15. A method of processing information units of the type described in claim 14 wherein the step of testing and storing indicators for an input information unit overlaps with the step of receiving the input information unit from the dispatcher at one of the plurality of processing units.

16. A method of identifying an input frame and providing indicators relating to that frame for further processing of the frame, the steps of the method comprising:

determining from the input frame a type of encapsulation and a protocol type by comparing a section of the input frame with a predetermined content indicative of a type of encapsulation and a protocol type;

generating and storing with respect to each input frame indicators of the type of encapsulation and the protocol type for that input frame without using a plurality of look-up tables and concatenated classification keys;

determining and storing the location of a layer 3 header for the input frame; and

determining and storing a beginning point for further processing of the input frame, based on the determined type of protocol and encapsulation method, whereby said location and beginning point may be used in further processing of the input frame.

17. A method of determining the characteristics of an input frame including the steps of claim 16 wherein the step of determining a beginning point for further processing includes the step of determining a default code entry point from the input frame, then using the input frame protocol and encapsulation method to determine if a stored control entry point has been stored for that combination of encapsulation and protocol, using the stored control entry point for the starting point for further processing if one exists and otherwise using the default code entry point as the starting point for further processing.

18. A device for receiving from a network and processing data packets of varying formats comprising:

a plurality of processors, each operating independent of the other, for processing a data packets and providing an output data packet which is based on the input data packet;

a dispatch unit connected to the processors for receiving a data packet from the network and assigning the packet to one of the plurality of independent processors;

a classification device connected to the dispatch unit for receiving the packet and determining its protocol and encapsulation technique as well as a starting address for further processing of the packet by the processing units, the classification device including;

logic to determine the encapsulation technique based on a portion of the packet without using a plurality of look-up tables and concatenated classification keys;

logic to determine the presence of a virtual local area network information in the packet; and

an output for each packet including the type of encapsulation and the starting address for further processing.

19. An apparatus of the type described in claim 18 wherein the classifier is embodied in hardware without a stored program.

20. An apparatus of the type described in claim 18 wherein the classification occurs in two cycles so that further processing of the packet by one of the processing units can begin within two cycles after the packet is dispatched by the dispatching unit.

21. An apparatus of the type described in claim 18 wherein the starting address is determined by generating a default starting address from the packet and using that default address as the starting address for processing the packet unless a different starting address is stored for the encapsulation method and protocol determine by the classification system.

22. An apparatus for analyzing a frame of information having a variable protocol and encapsulation and for providing a starting location for processing that frame and a pointer to the initial instruction for processing that frame, the apparatus comprising:

a comparator for looking at predetermined bytes of the frame and determining if those bytes indicate a length or a protocol without using a plurality of look-up tables and without classification keys being concatenated;

logic for determining the protocol and encapsulation system for the frame;

using the protocol and encapsulation system to determine a starting location for processing the frame and a pointer to the initial instruction for processing the frame.

23. A method of processing an input information unit comprising the steps of:

receiving the input information unit at a dispatcher;

sending the input information unit from the dispatcher to one of a plurality of processors for processing;

reading in hardware selected bits from the input information unit while the information unit is being sent from the dispatcher to the one of the plurality of processors;

testing in hardware the read bits from the input information unit against known indicators identifying predetermined types of input information units to identify the type and protocol of the input information unit or that the input information unit does not meet any predetermined identifying type of input information unit within two machine cycles, whereby the process of reading and testing is accomplished in fewer processing cycles than if the reading and testing was accomplished by executing a series of stored programmed instructions in sequence; and

based on the results of the testing of bits from the input information unit, storing indicators of the type of input information unit and other information about that input information unit; and

using at the one of a plurality of processing units the stored indicators and the other stored information about the input information unit in the processing of the input information unit.

24. A method of processing information units of the type described in claim 23 wherein the step of testing and storing indicators for an input information unit overlaps with the step of receiving the input information unit from the dispatcher at one of the plurality of processing units.

25. A device for receiving from a network and processing data packets of varying formats comprising:

a plurality of processors, each operating independent of the other, for processing a data packets and providing an output data packet which is based on the input data packet;

a dispatch unit connected to the processors for receiving a data packet from the network and assigning the packet to one of the plurality of independent processors;

a classification device connected to the dispatch unit for receiving the packet and determining its protocol and encapsulation technique within two cycles so that further processing of the frame by one of the processing units can begin within two cycles after the packet is dispatched by the dispatching unit as well as a starting address for further processing of the packet by the processing units, the classification device including;

logic to determine the encapsulation technique based on a portion of the packet

logic to determine the presence of a virtual local area network information in the packet; and

an output for each packet including the type of encapsulation and the starting address for further processing.