# US 9,438,703 B2 · Method of forming a hash input from packet contents and an apparatus thereof

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,438,703 B2
- Document ID: US9438703B2
- Status: Granted
- Kind: B2
- Application number: 14/309,739
- Filed: 2014-06-19
- Published: 2015-12-24
- Granted: 2016-09-06
- Earliest claimed: 2014-06-19
- Assignees: Cavium, Inc.
- Applicants: XPLIANT, Inc
- Inventors: Vishal Anand; Tsahi Daniel; Gerald Schmidt
- Web page: https://patentgrep.com/patent/US9438703B2

## CPC

- H04L 69/22: Parsing or analysis of headers
- H04L 49/00: Packet switching elements
- H04L 69/324: in the data link layer [OSI layer 2], e.g. HDLC
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Embodiments of the apparatus for forming a hash input from packet contents relate to a programmable flexible solution to form hash inputs, allowing for hardware changes and for adding support for newer protocols as and when they are defined in the future. A packet is split into individual layers. Each layer is given a unique layer type number that helps identify what that layer is. Based on the layer type, each layer is expanded to a generic format. Each layer has a set of hash commands that is generic to that layer. Fields of each hash command are fieldOffset, fieldLen, hashMask, and hashMaskMSB. These hash commands allow information in the packet to be extracted in a programmable manner. The fields extracted from each protocol layer of the packet are concatenated to form a hash layer. A bit vector indicates which hash layers are used to form the hash input.

## Claims

### Claim 1

A method of implementing a parser engine, the method comprising:
identifying one or more protocol layers of a packet, wherein each of the protocol layers have one or more fields;
for each protocol layer of the protocol layers, expanding the protocol layer to a generic format based on the identification of the protocol layer thereby forming an expanded protocol layer;
selecting one or more of a set of generic hash commands based on a layer type of the expanded protocol layer; and
selecting contents from each of the expanded protocol layers to apply a hash function by applying the one or more of the set of generic hash commands to the expanded protocol layer.

### Claim 2 (depends on 1)

The method of claim 1, wherein each of the protocol layers has a unique layer type number and is identified based on the unique layer type number.

### Claim 3 (depends on 1)

The method of claim 1, wherein the generic format defines a super-set of all fields that the protocol layers can have.

### Claim 4 (depends on 1)

The method of claim 1, wherein the selecting contents from each of the expanded protocol layers comprises applying at least one from the one or more of the set of generic hash commands to the expanded protocol layer to extract a field from the expanded protocol layer.

### Claim 5 (depends on 4)

The method of claim 4, wherein fields of each of the generic hash commands are fieldOffset, which specifies offset within the expanded protocol layer where a field to be extracted starts, fieldLen, which specifies a number of bytes that should be extract from that specified offset, hashMask, which is a bit mask, and hashMaskMSB, which indicates whether the bit mask is to be applied to the most significant byte or the least significant byte of the extracted field.

### Claim 6 (depends on 4)

The method of claim 4, wherein fields of each of the generic hash commands are software defined.

### Claim 7 (depends on 4)

The method of claim 4, further comprising:
applying a logical AND operation on a bit mask and one byte of the extracted field, wherein the bit mask is specified by the at least one hash command;
forming a hash input layer based on at least the result of the logical AND operation; and
retrieving a bit vector that indicates which hash input layers of the expanded protocol layers are to be used to form a hash input to the hash function.

### Claim 8 (depends on 7)

The method of claim 7, further comprising using the hash input as an input to the hash function.

### Claim 9

A method of implementing a parser engine, the method comprising:
identifying one or more protocol layers of a packet, wherein each of the protocol layers have one or more fields;
for each protocol layer of the protocol layers, expanding the protocol layer to a generic format based on the identification of the protocol layer thereby forming an expanded protocol layer; and
selecting contents from each of the expanded protocol layers to apply a hash function, wherein the expanding of the protocol layer comprises:
maintaining a bit vector for the expanded protocol layer, wherein the bit vector includes a bit for each byte of the expanded protocol layer such that each of the bits corresponds to one of the bytes of the expanded protocol layer;
for each of the bits, setting the bit to a first value if the corresponding byte is a part of a valid field of the protocol layer, wherein each of the valid fields is a field existing in the protocol layer of the packet before the protocol layer has been expanded to the expanded protocol layer; and
for each of the bits, setting the bit to a second value if the corresponding byte is a part of an invalid field of the protocol layer, wherein each of the invalid fields is a field that did not exist in the protocol layer of the packet before the protocol layer has been expanded to the expanded protocol layer.

### Claim 10 (depends on 9)

The method of claim 9, further comprising using a compressed format to express the expanded protocol layer.

### Claim 11

A method of implementing network switch, the method comprising:
receiving a packet having a packet header at an incoming port of the network switch, wherein the packet header includes one or more protocol headers;
for each of the protocol headers, generalizing the protocol header to a generic format for a corresponding protocol thereby forming a generalized protocol header;
for each generalized protocol header, extracting one or more fields from the generalized protocol header;
for each generalized protocol header, concatenating the one or more extracted fields from the generalized protocol header to form a hash layer; and
using a bit vector to determine which hash layers of all expanded protocol headers are to be selected to form a hash input.

### Claim 12 (depends on 11)

The method of claim 11, wherein the network switch includes a parser engine configured to generalize each protocol header, to extract one or more fields from the generalized protocol header, to concatenate the one or more extracted fields from the generalized protocol header to form the hash layer, and to use the bit vector to determine which hash layers of all expanded protocol headers are to be selected to form the hash input.

### Claim 13 (depends on 12)

The method of claim 12, wherein the generalizing of the protocol header comprises:
the parser engine determining a layer type of the protocol header and a variant of the layer type;
the parser engine detecting missing fields from the protocol header based on the layer type and the variant; and
based on the detection, the parser engine expanding the protocol header to the generic format.

### Claim 14 (depends on 12)

The method of claim 12, wherein extracting one or more fields comprises applying one or more generic hash commands to the generalized protocol header.

### Claim 15 (depends on 14)

The method of claim 14, wherein fields of each of the generic hash commands are fieldOffset, which specifies offset within the generalized protocol header where a field to be extracted starts, fieldLen, which specifies a number of bytes that should be extract from that specified offset, hashMask, which is a bit mask, and hashMaskMSB, which indicates whether the bit mask is to be applied to the most significant byte or the least significant byte of the extracted field.

### Claim 16 (depends on 14)

The method of claim 14, further comprising, prior to receiving the packet, programming fields of each of the one or more generic hash commands via software.

### Claim 17 (depends on 11)

The method of claim 11, further comprising, prior to receiving the packet:
allowing for software-defined mappings of generic formats of protocols; and
storing the software-defined mappings in a memory of the network switch.

### Claim 18 (depends on 11)

The method of claim 11, further comprising, after extracting one or more fields and before concatenating the one or more extracted fields, applying a logical AND operation on a bit mask and one byte of an extracted field, wherein the bit mask is specified by a generic hash command.

### Claim 19 (depends on 11)

The method of claim 11, further comprising, before using the bit vector, indexing a local table using a packet identifier of the packet, wherein the table stores bit vectors for each known protocol layer combination.

### Claim 20

A network switch comprising:
an input port and an output port for receiving and transmitting packets having headers including one or more protocol layers;
a memory for storing a set of software-defined mappings of generic protocol layer formats for one or more protocols and for storing sets of generic hash commands for extracting desired fields from the protocol layers that have been converted into one of the generic protocol layer formats, and for storing a table of bit vectors; and
a parser engine for:
performing a header generalization process on the header of each of the packets to generalize each of the protocol layers of the header of the packet according to one of the generic protocol layer formats thereby forming an expanded protocol layer:
selecting one or more of a set of generic hash commands based on a layer type of the expanded protocol layer; and
for selecting contents from the expanded protocol layers to apply to a hash function by applying the one or more of the set of generic hash commands to the expanded protocol layer.

### Claim 21 (depends on 20)

The network switch of claim 20, wherein the header generalization process is used on different variants of protocol layers of one or more of the protocols.

### Claim 22 (depends on 20)

The network switch of claim 20, wherein the header generalization process is used on different protocols of the protocols.

### Claim 23 (depends on 20)

The network switch of claim 20, wherein after the packet is processed by the parser engine, the packet includes canonicalized protocol layers.

### Claim 24 (depends on 23)

The network switch of claim 23, wherein each of the canonicalized protocol layers is one of the expanded protocol layers that was generalized based on one of the protocol layers of the header of the packet.

### Claim 25 (depends on 20)

The network switch of claim 20, wherein the parser engine further applies at least one hash command from one of the sets of generic hash commands to each of the expanded protocol layers to extract one or more fields from the expanded protocol layers.

### Claim 26 (depends on 25)

The network switch of claim 25, wherein the one of the set of generic hash commands is specific to the protocol of the expanded protocol layer to which the one of the set of generic hash commands is being applied.

### Claim 27 (depends on 25)

The network switch of claim 25, wherein the fields that are to be extracted by each of the generic hash commands are software defined.

### Claim 28 (depends on 25)

The network switch of claim 25, wherein the at least one hash command specifies a bit mask and a byte location of the extracted field to apply the bit mask to.

### Claim 29 (depends on 28)

The network switch of claim 28, wherein the parser engine further applies a logical AND operation on the bit mask and the byte location of the extracted field.

### Claim 30 (depends on 29)

The network switch of claim 29, wherein the result from the logical AND operation is concatenated with other results from other AND operations to form a hash input layer.

### Claim 31 (depends on 30)

The network switch of claim 30, wherein the parser engine accesses the table of bit vectors to retrieve therefrom one of the bit vectors to apply to hash input layers to form a hash input for the hash function.

### Claim 32

A parser engine comprising a circuit configured to:
identify one or more protocol layers of a packet, wherein each of the protocol layers have one or more fields;
for each protocol layer of the protocol layers:
expand the protocol layer to a generic format based on the identification of the protocol layer thereby forming an expanded protocol layer;
selecting one or more of a set of generic hash commands based on a layer type of the expanded protocol layer; and
select contents from the expanded protocol layer to apply to a hash function by applying the one or more of the set of generic hash commands to the expanded protocol layer.

### Claim 33 (depends on 32)

The parser engine of claim 32, wherein each of the protocol layers has a unique layer type number and is identified based on the unique layer type number.

### Claim 34 (depends on 32)

The parser engine of claim 32, wherein the generic format defines a super-set of all fields that the protocol layers can have.

### Claim 35 (depends on 32)

The parser engine of claim 32, wherein the circuit is also configured to apply at least one from a set of generic hash commands to the expanded protocol layer to extract one or more fields from the expanded protocol layer.

### Claim 36 (depends on 35)

The parser engine of claim 35, wherein fields of each of the generic hash commands are fieldOffset, which specifies offset within the expanded protocol layer where a field to be extracted starts, fieldLen, which specifies a number of bytes that should be extract from that specified offset, hashMask, which is a bit mask, and hashMaskMSB, which indicates whether the bit mask is to be applied to the most significant byte or the least significant byte of the extracted fields.

### Claim 37 (depends on 35)

The parser engine of claim 35, wherein fields of each of the generic hash commands are software defined.

### Claim 38 (depends on 35)

The parser engine of claim 35, wherein the circuit is also configured to:
apply a logical AND operation on a bit mask and one byte of the extracted field, wherein the bit mask is specified by at least one of the generic hash commands;
form a hash input layer based on at least the result of the logical AND operation; and
retrieve a bit vector that indicates which hash input layers of the expanded protocol layers are to be used to form a hash input to the hash function.