# US 2021/0344596 A1 · Dynamically-Optimized Hash-Based Packet Classifier

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

- Number: US 2021/0344596 A1
- Document ID: US20210344596A1
- Status: Published application
- Kind: A1
- Application number: 16/865,560
- Filed: 2020-05-04
- Published: 2021-11-04
- Earliest claimed: 2020-05-04
- Assignees: Mellanox Technologies, Ltd.
- Applicants: Mellanox Technologies, Ltd.
- Inventors: Guy Mittelman
- Web page: https://patentgrep.com/patent/US20210344596A1

## CPC

- H04L 45/742: {Route cache; Operation thereof}
- H04L 45/7453: using hashing
- H04L 45/74591: {using content-addressable memories [CAM]}
- H04L 69/22: Parsing or analysis of headers
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A network element includes multiple ports and a packet classifier. The packet classifier is configured to receive rules and Rule Patterns (RPs), each RP corresponding to a subset of the rules and specifies positions of unmasked packet-header bits to be matched by the rules in the subset, to store in a RAM a grouping of the RPs into Extended RPs (ERPs), each ERP defining a superset of the unmasked bits in the RPs associated therewith, to receive packets and match each packet to one or more of the rules by accessing the ERPs in the RAM, to determine counter values, each counter value corresponding to a respective RP and is indicative of a number of the received packets that match the RP, and to adaptively modify grouping of the RPs into the ERPs depending on the counter values.

## Claims

### Claim 1

A network element, comprising:
multiple ports, configured to transmit and receive packets over a network;
a packet classifier, configured to:
receive a corpus of rules and a plurality of Rule Patterns (RPs), wherein each RP corresponds to a subset of the rules and specifies positions of unmasked packet-header bits to be matched by the rules in the subset;
define, in a Random-Access Memory (RAM), multiple memory regions that are read sequentially one after another;
store, in the multiple memory regions, a grouping of the RPs into Extended RPs (ERPs), each ERP defining a superset of the unmasked bits in the RPs associated therewith;
receive packets, and match each packet to one or more of the rules by accessing the ERPs in the RAM;
determine multiple counter values, wherein each counter value corresponds to a respective RP and is indicative of a number of the received packets that match the RP; and
adaptively modify (i) grouping of the RPs into the ERPs and (ii) allocation of the ERPs to the memory regions, depending on the counter values; and
a packet handler, configured to apply actions to the packets depending on matching of the packets to the rules.

### Claim 2 (depends on 1)

The network element according to claim 1, wherein the packet classifier is configured to increment the counter values in response to received packets that match the RPs corresponding to the counter values, and to modify the grouping of the RPs into the ERPs based on the incremented counter values.

### Claim 3 (depends on 1)

The network element according to claim 1, wherein, in performing a given modification of the grouping of the RPs, the packet classifier is configured to reduce an average number of times the RAM is read per packet.

### Claim 4 (depends on 1)

The network element according to claim 1, wherein, in performing a given modification of the allocation of the ERPs to the memory regions, the packet classifier is configured to reduce an average number of times the RAM is read per packet.

### Claim 5 (depends on 1)

The network element according to claim 1, wherein the packet classifier is configured to modify the grouping of the RPs by finding, for a given region of the RAM, an RP grouping that corresponds to a highest aggregate number of the counter values and still fits within the given region.

### Claim 6 (depends on 1)

The network element according to claim 1, wherein the packet classifier is configured to periodically reset the multiple counter values.

### Claim 7 (depends on 1)

The network element according to claim 1, further comprising a Ternary-Content-Addressable Memory (TCAM) that is configured to hold, at least temporarily, a subset of the rules, wherein the packet classifier is configured to match a received packet to the rules stored in the TCAM upon failing to find a successful match in the RAM.

### Claim 8

A method, comprising:
in a network element that transmits and receives packets over a network, receiving a corpus of rules and a plurality of Rule Patterns (RPs), wherein each RP corresponds to a subset of the rules and specifies positions of unmasked packet-header bits to be matched by the rules in the subset;
defining, in a Random-Access Memory (RAM), multiple memory regions that are read sequentially one after another;
storing, in the multiple memory regions, a grouping of the RPs into Extended RPs (ERPs), each ERP defining a superset of the unmasked bits in the RPs associated therewith;
receiving packets, and matching each packet to one or more of the rules by accessing the ERPs in the RAM;
determining multiple counter values, wherein each counter value corresponds to a respective RP and is indicative of a number of the received packets that match the RP;
adaptively modifying (i) grouping of the RPs into the ERPs and (ii) allocation of the ERPs to the memory regions, depending on the counter values; and
applying actions to the packets depending on matching of the packets to the rules.

### Claim 9 (depends on 8)

The method according to claim 8, wherein determining the counter values comprises incrementing the counter values in response to received packets that match the RPs corresponding to the counter values, and wherein modifying the grouping comprises modifying the grouping of the RPs into the ERPs based on the incremented counter values.

### Claim 10 (depends on 8)

The method according to claim 8, wherein performing a given modification of the grouping of the RPs comprises reducing an average number of times the RAM is read per packet.

### Claim 11 (depends on 8)

The method according to claim 8, wherein performing a given modification of the allocation of the ERPs to the memory regions comprises reducing an average number of times the RAM is read per packet.

### Claim 12 (depends on 8)

The method according to claim 8, wherein modifying the grouping comprises finding, for a given region of the RAM, an RP grouping that corresponds to a highest aggregate number of the counter values and still fits within the given region.

### Claim 13 (depends on 8)

The method according to claim 8, wherein determining the counter values comprises periodically resetting the multiple counter values.

### Claim 14 (depends on 8)

The method according to claim 8, further comprising storing in a Ternary-Content-Addressable Memory (TCAM), at least temporarily, a subset of the rules, and matching a received packet to the rules stored in the TCAM upon failing to find a successful match in the RAM.

### Claim 15 (depends on 1)

The network element according to claim 1, wherein, in adaptively modifying the allocation of the ERPs to the memory regions, the packet classifier is configured to move a given ERP from one of the memory regions to another of the memory regions based on at least some of the counter values.

### Claim 16 (depends on 8)

The method according to claim 8, wherein adaptively modifying the allocation of the ERPs to the memory regions comprises moving a given ERP from one of the memory regions to another of the memory regions based on at least some of the counter values.
