# US 2019/0379606 A1 · Packet classification with multiple classifiers

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

- Number: US 2019/0379606 A1
- Document ID: US20190379606A1
- Status: Published application
- Kind: A1
- Application number: 16/003,077
- Filed: 2018-06-07
- Published: 2019-12-12
- Earliest claimed: 2018-06-07
- Assignees: VMware, Inc.
- Applicants: VMware, Inc.
- Inventors: Cheng-Chun Tu; Yifeng Sun; Yi-Hung Wei; Benjamin L. Pfaff; Justin Pettit
- Web page: https://patentgrep.com/patent/US20190379606A1

## CPC

- H04L 45/7453: using hashing
- H04L 47/2483: involving identification of individual flows
- H04L 43/028: by filtering
- H04L 67/568: Storing data temporarily at an intermediate stage, e.g. caching
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Some embodiments provide a method for a forwarding element that receives a packet. The method determines whether the packet matches any flow entries in a first cache that uses a first type of algorithm to identify matching flow entries for packets. When the packet does not match any flow entries in the first cache, the method determines whether the packet matches any flow entries in a second cache that uses a second, different type of algorithm to identify matching flow entries for packets. The method executes a set of actions specified by a flow entry matched by the packet in one of the first and second caches.

## Claims

### Claim 1

For a forwarding element, a method comprising:
receiving a packet at the forwarding element;
determining whether the packet matches any flow entries in a first cache that uses a first type of algorithm to identify matching flow entries for packets;
when the packet does not match any flow entries in the first cache, determining whether the packet matches any flow entries in a second cache that uses a second, different type of algorithm to identify matching flow entries for packets; and
executing a set of actions specified by a flow entry matched by the packet in one of the first and second caches.

### Claim 2 (depends on 1)

The method of claim 1, wherein:
the first cache comprises a decision tree and the second cache comprises a plurality of tables, each table based on a different set of packet header fields;
determining whether the packet matches any flow entries in the first cache comprises searching the decision tree;
determining whether the packet matches any flow entries in the second cache comprises performing a tuple space search over the plurality of tables.

### Claim 3 (depends on 2)

The method of claim 2 further comprising:
identifying a new flow entry to add to the first and second caches;
adding the new flow entry to the second cache; and
storing the new flow entry for addition to the first cache with any other new flow entries upon rebuilding of the decision tree.

### Claim 4 (depends on 3)

The method of claim 3, wherein the new flow entry matches on a particular set of packet header fields, wherein adding the new flow entry to the second cache comprises adding the new flow entry to a particular table based on the particular set of packet header fields.

### Claim 5 (depends on 4)

The method of claim 4 further comprising:
after adding the new flow entry to the second cache but prior to rebuilding the decision tree, receiving a second packet;
determining whether the second packet matches any flow entries in the decision tree cache;
when the second packet matches a flow entry in the decision tree cache, searching at least the particular table to determine whether the packet matches any flow entries in the particular table with a higher priority than the flow entry matched in the decision tree cache.

### Claim 6 (depends on 3)

The method of claim 3 further comprising rebuilding the decision tree to include the new flow entry and any additional flow entries added to the second cache after a previous instance of rebuilding the decision tree.

### Claim 7 (depends on 3)

The method of claim 3, wherein the decision tree is rebuilt after a fixed period of time.

### Claim 8 (depends on 3)

The method of claim 3, wherein the decision tree is rebuilt after a miss rate for the first cache exceeds a threshold.

### Claim 9 (depends on 2)

The method of claim 2, wherein each of the flow entries comprises a set of match conditions and a set of actions to execute if the set of match conditions are met, the method further comprising:
identifying a flow entry in the first and second caches for which the set of actions is to be modified; and
modifying the set of actions specified by the flow entry in both of the first and second caches.

### Claim 10 (depends on 2)

The method of claim 2 further comprising:
identifying a particular flow entry to remove from the first and second caches, wherein the particular flow entry is stored in a particular table of the plurality of tables;
removing the particular flow entry from the particular table; and
marking as invalid a leaf node of the decision tree that corresponds to the particular flow entry.

### Claim 11 (depends on 1)

The method of claim 1, wherein when the packet does not match any flow entries in the first or second caches, the forwarding element processes the packet according to a plurality of flow entries organized in a set of flow tables having a plurality of stages.

### Claim 12 (depends on 11)

The method of claim 11, wherein the plurality of flow entries organized in the set of flow tables are OpenFlow entries.

### Claim 13 (depends on 11)

The method of claim 11 further comprising generating a new flow entry for the first and second caches based on the processing of the packet according to the plurality of flow entries.

### Claim 14 (depends on 1)

The method of claim 1, wherein the first and second caches are aggregate caches, wherein each of a plurality of flow entries in the first and second caches specifies a set of actions to execute on packets for an aggregate group of data flows that have a set of packet header field values in common.

### Claim 15 (depends on 14)

The method of claim 14 further comprising, prior to determining whether the packet matches any flow entries in the first cache, determining whether the packet matches any flow entries in an exact-match cache, wherein each flow entry in the exact match cache specifies a set of actions to execute on packets for a single data flow.

### Claim 16 (depends on 1)

The method of claim 1, wherein the forwarding element is a software forwarding element that executes in virtualization software of a host machine.

### Claim 17

A non-transitory machine readable medium storing a forwarding element for execution by at least one processing unit, the forwarding element comprising sets of instructions for:
receiving a packet;
determining whether the packet matches any flow entries in a first cache that uses a first type of algorithm to identify matching flow entries for packets;
when the packet does not match any flow entries in the first cache, determining whether the packet matches any flow entries in a second cache that uses a second, different type of algorithm to identify matching flow entries for packets; and
executing a set of actions specified by a flow entry matched by the packet in one of the first and second caches.

### Claim 18 (depends on 17)

The non-transitory machine readable medium of claim 17, wherein:
the first cache comprises a decision tree and the second cache comprises a plurality of tables, each table based on a different set of packet header fields;
the set of instructions for determining whether the packet matches any flow entries in the first cache comprises a set of instructions for searching the decision tree;
the set of instructions for determining whether the packet matches any flow entries in the second cache comprises a set of instructions for performing a tuple space search over the plurality of tables.

### Claim 19 (depends on 18)

The non-transitory machine readable medium of claim 18, wherein the forwarding element further comprises sets of instructions for:
identifying a new flow entry to add to the first and second caches;
adding the new flow entry to the second cache; and
storing the new flow entry for addition to the first cache with any other new flow entries upon rebuilding of the decision tree.

### Claim 20 (depends on 19)

The non-transitory machine readable medium of claim 19, wherein the forwarding element further comprises a set of instructions for rebuilding the decision tree to include the new flow entry and any additional flow entries added to the second cache after a previous instance of rebuilding the decision tree.

### Claim 21 (depends on 18)

The non-transitory machine readable medium of claim 18, wherein each of the flow entries comprises a set of match conditions and a set of actions to execute if the set of match conditions are met, the forwarding element further comprising sets of instructions for:
identifying a flow entry in the first and second caches for which the set of actions is to be modified; and
modifying the set of actions specified by the flow entry in both of the first and second caches.

### Claim 22 (depends on 18)

The non-transitory machine readable medium of claim 18, wherein the forwarding element further comprises sets of instructions for:
identifying a particular flow entry to remove from the first and second caches, wherein the particular flow entry is stored in a particular table of the plurality of tables;
removing the particular flow entry from the particular table; and
marking as invalid a leaf node of the decision tree that corresponds to the particular flow entry.

### Claim 23 (depends on 17)

The non-transitory machine readable medium of claim 17, wherein the forwarding element further comprises sets of instructions for:
when the packet does not match any flow entries in the first or second caches, processing the packet according to a plurality of flow entries organized in a set of flow tables having a plurality of stages; and
generating a new flow entry for the first and second caches based on the processing of the packet according to the plurality of flow entries.
