HK1220832B - A method of handling large protocol layers for configurable extraction of layer information and an apparatus thereof - Google Patents

Description

Method and device for processing large protocol layers with configurable extraction of layer information

Technical Field

The present invention relates to a network data packet, and more particularly to a method and device for processing a large protocol layer with respect to configurable extraction of layer information.

Background Art

Network packets include multiple service layers or protocol layers, each of which is independent of the other layers. While traditional hardware implementations provide parsing capabilities, traditional hardware implementations are not flexible enough and are resource inefficient. One limitation of this inflexibility and inefficiency is the maximum length of each layer. This limitation is dominated by the field selection circuitry that must be built into the hardware. The logic that goes into the hardware is proportional to the maximum layer length. For example, in order to extract "T" total bytes from a layer in a programmable manner, where the layer can have a size of "L" bytes, the total number of byte MUXs required for the layer is T*(L:1) MUXs. Therefore, the larger "L", the larger the size of the field selection circuitry, which increases the hardware cost. If the parser engine is capable of processing multiple layers in a packet, then the total MUX structure cost is the size of the field selection circuitry multiplied by the number of layers supported by the parser engine.

Summary of the Invention

An embodiment of an apparatus for processing large protocol layers involves the implementation of optimized field selection circuitry. This implementation provides a hardware parser engine with software-like flexibility when parsing packets. The implementation limits the size of each layer and separates any layers exceeding that size into smaller layers. The parser engine extracts data from the separated layers just as it would from a non-separated layer and then concatenates the extracted data into a final result.

In one aspect, a method of implementing a parser engine is provided. The method includes separating layers of a data packet based on protocol layers, such that each of the protocol layers of the data packet is separated. In some embodiments, separating the layers of the data packet includes storing a layer type of each protocol layer of the data packet in a first array and storing an offset of a location where each protocol layer of the data packet ends in a second array.

The method further includes separating each of the protocol layers of the data packet having a size greater than a predetermined size into a plurality of layers. The first array and the second array are updated based on the further separation. In some embodiments, the predetermined size is software defined.

The method includes processing all of the separation layers. In some embodiments, processing all of the separation layers includes reducing each layer of the separation layers to a common format and selecting content from each of the reduced separation layers. In some embodiments, selecting content from each of the reduced separation layers includes applying at least one from a common command set to the reduced separation layers to extract fields from the reduced separation layers. In some embodiments, each of the common command sets is independent of a specific field in a protocol layer.

In some embodiments, the method includes concatenating results from the processing to form a token, wherein the token is used for further processing of the data packet.

In some embodiments, the method includes applying the bit vector to a result from the processing to form an input to a hash function, wherein an output of the hash function is a unique signature identifying which of the equal-cost multi-path routes the data packet should take.

In another aspect, a method of implementing a parser engine is provided, wherein the method includes separating layers of a data packet based on a protocol layer such that each of the protocol layers of the data packet is separated.

The method also includes maintaining information about a layer type for each of the protocol layers and an offset of where each of the protocol layers ends. In some embodiments, information about the layer type is stored in a first array and information about the offset is stored in a second array.

The method further includes separating any protocol layer of the data packet having a size greater than a predetermined size into a first portion and a second portion, wherein the first portion has the predetermined size. The predetermined size is software-defined.

The method further includes updating the information based on the further separation.In some embodiments, updating the information includes storing information about layer types of the first portion and the second portion in sequence elements of the first array, and storing information about offsets of the first portion and the second portion in sequence elements of the second array.

The method further includes repeating the steps of further separating and updating for the second portion based on determining that the second portion has a size greater than a predetermined size.

The method further comprises processing all of the separated layers. In some embodiments, prior to processing, each of the separated layers is summarized into a common format. In some embodiments, processing the separated layers comprises extracting data from the summarized layers.

In another aspect, a method for implementing a network switch is provided. The method includes parsing a data packet based on protocol layers, thereby initializing a first array and a second array. In some embodiments, parsing the data packet includes identifying a layer type for each layer in the data packet, storing the layer type for each layer in the first array, identifying an offset for a location where each layer ends in the data packet, and storing the offset for the location where each layer ends in the second array. In some embodiments, the method includes storing the first array and the second array in a memory of the network switch.

The method further includes comparing each element of the first array to a programmable register to determine whether the layer associated with the element needs to be separated. In some embodiments, the programmable register includes a layer type (layerType) field that indicates what matches the corresponding input; a split length (splitLength) field that indicates the offset at which the corresponding layer should be separated; and a new layer type (newLayerType) field that indicates the layer type value of the newly separated layer. In some embodiments, before parsing the packet, the method includes programming the layer type field, the split length field, and the new layer type field via software.

The method also includes separating the layer based on determining that the layer associated with the element needs to be separated.

The method also includes updating the first array and the second array according to the separation and extracting data from a layer associated with each element of the first array.

In some embodiments, the method includes combining the extracted data to thereby form a final result. In some embodiments, the bit vector is applied to a result from a logical AND operation, wherein each of the logical AND operations is applied to the extracted data from the layer and the bit mask.

In another embodiment, a parser engine is provided. The parser engine includes circuitry configured to separate layers of a data packet based on a protocol layer, such that each of the protocol layers of the data packet is separated, further separate each of the protocol layers of the data packet having a size greater than a predetermined size into a plurality of layers, and process all of the separated layers.

In some embodiments, information about the layer type of each of the protocol layers and the offset of the location where each of the protocol layers ends is maintained, and the information is updated after each protocol layer having a size greater than a predetermined size among the protocol layers of the data packet is further separated into a plurality of layers.

In some embodiments, the circuitry is further configured to concatenate results from the processing to form a token, wherein the token is used for further processing of the data packet.

In some embodiments, the circuitry is further configured to apply the bit vector to a result from the processing to form an input to the hash function.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing will become apparent from the following more particular description of exemplary embodiments of the present invention, as illustrated in the accompanying drawings, wherein like reference numerals refer to like parts throughout the various views. The accompanying drawings are not necessarily drawn to scale, with emphasis placed upon illustrating embodiments of the present invention.

FIG1 illustrates a method of a parser engine according to some embodiments of the present invention.

FIG2 illustrates another method of a parser engine according to some embodiments of the present invention.

FIG3 illustrates a method of a network switch according to some embodiments of the present invention.

DETAILED DESCRIPTION

In the following description, various details are listed for explanation. However, those skilled in the art will appreciate that the present invention can be practiced without using these specific details. Thus, the present invention is not intended to be limited to the embodiments shown, but rather should be given the broadest scope consistent with the principles and features described herein.

An embodiment of an apparatus for processing large protocol layers involves an implementation of optimized field selection circuitry. This implementation provides a hardware parser engine with software-like flexibility when parsing packets. The implementation limits the size of each layer and separates any layer exceeding that size into smaller layers. The parser engine extracts data from the separated layers just as it would from a non-separated layer and then concatenates the extracted data into a final result.

A network device, such as a network switch, is capable of switching/routing network traffic. The network switch includes at least one input/entry port and at least one output/egress port for receiving and sending data packets. In some embodiments, the network switch further includes a parser and a rewriter. The parser may include one or more parser engines to identify the content of network data packets, and the rewriter may include one or more rewrite engines to modify the data packets before they are sent from the network switch. The parser engine(s) and the rewriter engine(s) are flexible and operate on a programmable basis.

The network switch also includes a memory for storing data used by the network switch. For example, the memory stores at least two arrays used in the implementation to keep track of the separation layer. In another example, the memory stores a set of common commands for extracting fields from protocol headers. In yet another example, the memory also stores counters and statistical information.

In Ethernet, a data packet consists of multiple protocol layers. Each protocol layer carries different information. Some well-known examples of layers are:

Ethernet

PBB Ethernet

ARP

IPV4

IPV6

MPLS

FCOE

TCP

UDP

ICMP

IGMP

GRE

ICMPv6

VxLAN

TRILL

CNM

Theoretically, the protocol layers can appear in any order. However, only certain well-known combinations of these layers can occur. Some examples of valid combinations of these layers are:

Ethernet

Ethernet, ARP

Ethernet,CNM

Ethernet,FCoE

Ethernet,IPV4

Ethernet,,IPV4,ICMP

Ethernet,IPV4,IGMP

For packet parsing operations, packets are broken down into layers. This separation is based on well-known layers, such as those listed above. As explained above, in conventional hardware implementations, in order to programmatically extract "T" total bytes from a layer, where the layer may be of size "L" bytes, the total number of byte MUXs required for that layer is T*(L:1) MUXs. Consequently, the larger "L" is, the larger the field selection circuitry, which increases hardware cost.

The current implementation optimizes the field selection circuitry of the parser engine. The current implementation relies on an assumption about the order in which bytes are processed. Typically, the order in which bytes are output from the parser engine matches the order in which the bytes appear in the incoming layer. For example, if byte 1, byte 3, and byte 5 are to be selected, then the order in which the bytes appear is 1, 3, 5, not 3, 1, 5 or 5, 3, 1 or any other such combination. Based on this assumption, the total number of MUXs required is no longer T*(L:1), but (L:1)+(L-1:1)+(L-2:1)+(L-3:1)+…+(T:1), assuming T<L.

Because the cost of hardware is proportional to the length of a layer "L," current implementations limit the size of "L" they support and split any layer exceeding length "L" into N smaller layers. Information from the N separate layers is extracted just as the parser engine extracts from a single layer and then concatenated back into the final result. The extracted data can be used to form a token or hash input. Exemplary data extraction from packets is discussed in U.S. patent application Ser. No. [Agent Docket No. XPL-02100], filed on [date], entitled "A Method of Extracting Data from Packets and An Apparatus thereof," and U.S. patent application Ser. No. [Agent Docket No. XPL-02200], filed on [date], entitled "A Method of Forming a Hash Input from Packet Contents and An Apparatus thereof," both of which are incorporated herein by reference in their entireties.

The current implementation advantageously achieves the same functionality at reduced hardware cost. The sequence of the current implementation can be summarized as:

(1) Parse the incoming data packet and identify the layer type of each layer and the offset of the location where each layer ends. This information is stored in two arrays, layerType[] and layerEndPtr[].

(2) At the end of parsing, each layerType[] is compared with a programmable register. The programmable register includes the following fields:

layerType: indicates the layer type matched by the corresponding input;

splitLength: an offset indicating where the layer will be split; and

newLayerType: indicates the layer type value of the new separated layer.

An exemplary pseudo code for this comparison is shown in Table 1.

Table 1

The parser engine is a highly configurable hardware parser engine that provides software-like flexibility in how network traffic is parsed. FIG1 illustrates a method 100 of a parser engine according to some embodiments of the present invention. The parser engine is part of a network switch and identifies the contents of a network packet. In step 105, the layers of the packet are separated based on the protocol layer so that each of the protocol layers of the packet is separated. The layer type of each protocol layer of the packet is stored in a first array, layerType[]. The offset of where each protocol layer of the packet ends is stored in a second array, layerEndzptr[].

At step 110, each protocol layer in the protocol layers of the data packet having a size greater than a predetermined size is further separated into a plurality of layers. The first array and the second array are based on the further separation. The predetermined size is software defined.

At step 115, all separation layers are processed. In some embodiments, each of the separation layers is summarized into a common format. Content is selected from each of the summarized separation layers. In some embodiments, at least one of a set of common commands is applied to the summarized separation layers, thereby extracting fields from the summarized separation layers. In some embodiments, each of the set of common commands is independent of a specific field in a protocol layer. In some embodiments, the results from the processing are concatenated to form a token, which is used for further processing of the data packet. Alternatively, a bit vector is applied to the results from the processing to form an input to a hash function, wherein the output of the hash function is a unique signature that identifies which of the equal-cost multipath routes the data packet should take.

2 illustrates another method 200 of a parser engine according to some embodiments of the present invention. At step 205, the layers of the data packet are separated based on the protocol layer, such that each of the protocol layers of the data packet is separated.

In step 210, information about the layer type of each of the protocol layers and the offset of the location where each of the protocol layers ends is maintained. Information about the layer type is stored in a first array (e.g., layerType[]). Information about the offset is stored in a second array (e.g., layerEndzptr[]).

At step 215, any protocol layer in the protocol layer of the data packet having a size greater than a predetermined size is further separated into a first portion and a second portion, wherein the first portion has a predetermined size. The predetermined size is software-defined.

At step 220, the information is updated based on the further separation. Information about the layer types of the first and second parts is stored in sequence elements of the first array. Information about the offsets of the first and second parts is stored in sequence elements of the second array.

At step 225, based on determining that the second portion has a size greater than the predetermined size, repeating steps 215 and 220 for the second portion; and

All of the separated layers are processed at step 230. In some embodiments, each of the separated layers is reduced to a common format prior to step 230. In some embodiments, processing the separated layers includes extracting data from the reduced layers.

FIG3 illustrates a method 300 for a network switch according to some embodiments of the present invention. At step 305, a packet is parsed based on protocol layers. Based on the parsing, a first array (e.g., layerType[]) and a second array (e.g., layerEndzptr[]) are initialized. As the packet is parsed, the layer type of each layer in the packet is identified and stored in the first array, and the offset of each layer in the packet is identified and stored in the second array. The first and second arrays are stored in the memory of the network switch.

At step 310, each element of the first array is compared to a programmable register to determine whether the layer associated with the element needs to be separated. The programmable register includes: a layer type (layerType) field, which indicates what matches the corresponding input; a split length (splitLength) field, which indicates the offset at which the corresponding layer should be separated; and a new layer type (newLayerType) field, which indicates the layer type value of the newly separated layer. Typically, the layer type field, the split length field, and the new layer type field are programmed via software before step 305.

At step 315 , based on determining that the layer associated with the element needs to be separated, the layer is separated.

At step 320 , the first array and the second array are updated according to the separation.

At step 325, data is extracted from the layer associated with each element of the first array. In some embodiments, the extracted data is combined to form a final result. Alternatively, the bit vector is applied to the result from a logical AND operation, wherein each logical AND operation is applied to the extracted data from the layer and the bit mask.

This implementation relies on the assumption that the order in which the bytes are output by the parser engine matches the order in which they appear in the incoming layer, thereby advantageously optimizing the field selection circuitry of the parser engine. Any layer that exceeds a predetermined size is split into smaller layers. The parser engine extracts data from the separated layer just as it would from a non-separated layer and then concatenates the extracted data into the final result.

Those skilled in the art will recognize that other uses and advantages exist. Although the present invention has been described with reference to numerous specific details, those skilled in the art will recognize that the present invention may be embodied in other specific forms without departing from the spirit of the invention. Thus, those skilled in the art will understand that the present invention is not limited to the foregoing illustrative details, but is defined by the appended claims.

Claims (32)

1. A method of implementing a parser engine, the method comprising: separating a header of a data packet using the parser engine, the header having a plurality of protocol layers, wherein the separation is based on the protocol layers such that each of the protocol layers of the header is separated; further separating, using the parser engine, each of the protocol layers of the header having a size greater than a predetermined size into a plurality of layer sub-segments; and All of the sub-segments are processed using the parser engine. 2. The method of claim 1 , wherein separating the layers of a data packet comprises storing a layer type of each protocol layer of the data packet in a first array and storing an offset of where each protocol layer of the data packet ends in a second array. 3 . The method of claim 2 , wherein further separating each layer of the data packet comprises updating the first array and the second array based on the further separation. 4. The method of claim 1 , wherein processing all of the sub-segments comprises: reducing each of the sub-segments to a common format; and Content is selected from each of the summarized sub-segments. 5 . The method of claim 4 , wherein selecting content from each of the summarized subsegments comprises applying at least one general command from a set of general commands to the summarized subsegments to thereby extract fields from the summarized subsegments. The method according to claim 5 , wherein each general command in the general command set is agnostic to a specific field in the protocol layer. 7. The method of claim 1, further comprising concatenating results from the processing to form a token, wherein the token is used for further processing of the data packet. 8. The method of claim 1, further comprising applying a bit vector to a result from the processing to form an input to a hash function. 9. The method of claim 1 , wherein the data packet has a body, and the separation of the data packet comprises separation of the header, thereby forming separated parts of the header, and the further separation of the protocol layer comprises separating the separated parts of the header into sub-parts. 10. A method of implementing a parser engine, the method comprising: separating a header of a data packet using the parser engine, the header having a plurality of protocol layers, wherein the separation is based on the protocol layers such that each of the protocol layers of the header is separated; maintaining information regarding a layer type for each of the protocol layers and an offset for a location at which each of the protocol layers ends; further separating any of the protocol layers of the header having a size greater than a predetermined size into a first portion and a second portion, wherein the first portion has the predetermined size; updating the information based on the further separation; repeating the further separating and updating steps for the second portion based on determining that the second portion has a size greater than the predetermined size; and All separated layers were processed. The method of claim 10 , wherein the information about the layer type is stored in a first array and the information about the offset is stored in a second array. 12. The method of claim 11, wherein updating the information comprises: storing information about layer types of the first portion and the second portion in sequence elements of the first array; and Information about offsets of the first portion and the second portion is stored in sequence elements of the second array. 13. The method of claim 10, further comprising software defining the predetermined size before retaining the information. 14. The method of claim 10, further comprising: prior to processing, reducing each of the separated layers to a common format. The method of claim 14 , wherein processing the separated layers comprises extracting data from the summarized layers. 16. A method of implementing a network switch, the method comprising: parsing a header of a data packet, the header having a plurality of protocol layers, wherein the parsing is based on the protocol layers, thereby separating each protocol layer of the protocol layers of the header and initializing a first array and a second array; comparing each element of the first array with a programmable register to determine whether one of the protocol layers associated with the element needs to be separated; separating the one of the protocol layers based on determining that the one of the protocol layers associated with the element needs to be separated; updating the first array and the second array according to the separation; and Data is extracted from the protocol layer associated with each element of the first array. 17. The method according to claim 16, wherein parsing the data packet comprises: Identifying a layer type of each of the protocol layers in the data packet; storing the layer type of each of the protocol layers in the first array; an offset identifying a location in the data packet where each of the protocol layers ends; and The offset of the location where each of the protocol layers ends is stored in the second array. 18. The method of claim 16, wherein the programmable register comprises: A layer type field, which indicates which matches the corresponding input; a separation length field indicating an offset at which a corresponding one of the protocol layers should be separated; and A new layer type field indicates the layer type value of the new separation layer. 19. The method of claim 18, further comprising programming the layer type field, the separation length field, and the new layer type field via software before parsing the data packet. 20. The method of claim 16, further comprising storing the first array and the second array in a memory of the network switch. 21. The method of claim 16, further comprising combining the extracted data to thereby form a final result. 22. The method of claim 16, further comprising applying a bit vector to results from logical AND operations, wherein each of the logical AND operations is applied to the extracted data and a bit mask from one of the protocol layers. 23. A network switch comprising: an input port and an output port for receiving and sending data packets, each of the data packets having a header including a plurality of protocol layers; a memory for storing a first array and a second array to keep track of the protocol layers; and A parser engine for separating the header of the data packet into the protocol layers, for further separating any of the protocol layers exceeding a predetermined size into a plurality of sub-layers, and for extracting data from all of the sub-layers. 24. The network switch of claim 23, wherein the predetermined size is software defined. 25. The network switch of claim 23, wherein the parser engine further concatenates the extracted data to form tokens, wherein the tokens are used for further processing of the data packets. 26. The network switch of claim 23, wherein the parser engine further: applying a logical AND operation on the extracted data and the bit mask for each of the sub-layers; and The bit vector is applied to the result from the logical AND operation to form the input to the hash function. 27. The network switch of claim 26, wherein the output of the hash function is a unique signature that identifies which of the equal-cost multi-path routes the data packet should take. 28. A parser engine comprising circuitry configured to: separating a header of a data packet, the header having a plurality of protocol layers, wherein the separation is based on the protocol layers such that each of the protocol layers of the header is separated; further separating each of the protocol layers of the header having a size greater than a predetermined size into a plurality of sub-layers; and All of the sub-layers are processed. 29. The parser engine of claim 28, wherein information is maintained regarding a layer type of each of the protocol layers and an offset of where each of the protocol layers ends. 30. The parser engine of claim 29, wherein the information is updated after each of the protocol layers of the data packet having a size greater than a predetermined size is further separated into a plurality of sub-layers. 31. The parser engine of claim 28, wherein the circuitry is further configured to concatenate results from the processing to form tokens, wherein the tokens are used for further processing of the data packet. 32. The parser engine of claim 28, wherein the circuitry is further configured to apply a bit vector to a result from the processing to form an input to a hash function.