Performing a multi-stage lookup to classify packets

Patent metadata

Field	Value
Publication number	US-9674087-B2
Application number	US-201414487060-A
Country	US
Kind code	B2
Filing date	Sep 15, 2014
Priority date	Sep 15, 2013
Publication date	Jun 6, 2017
Grant date	Jun 6, 2017

Abstract

Some embodiments provide a method for a forwarding element that forwards packets. The method receives a packet. The method performs a first stage lookup of a hash table for a first hash of a first set of header fields and un-wildcards bits of a wildcard mask that corresponds to the first set of header fields. If a matching hash is found in the first stage lookup, the method performs a second stage lookup of the hash table for a second hash of a second set of header fields and un-wildcards bits of the wildcard mask that corresponds to the second set of header fields. The method identifies a matching rule for the packet. The method generates a flow based on the matching rule and the wildcard mask, wherein the flow is used to process each other packets that match each bit which is un-wildcarded.

First claim

What is claimed is:

1. A method for a forwarding element that forwards packets, the method comprising:
receiving a packet;
defining a wildcard mask comprising a plurality of bits, each bit in the wildcard mask (i) corresponding to a bit in a header of the packet and (ii) initially set as a wildcard bit;
performing a first stage lookup, of a hash table comprising a set of rules, for a first hash of a first set of fields of the header of the packet and un-wildcarding a first set of bits of the wildcard mask that corresponds to the first set of fields;
if a matching hash is found in the first stage lookup, performing a second stage lookup of the hash table for a second hash of a second set of fields of the header of the packet and un-wildcarding a second set of bits of the wildcard mask that corresponds to the second set of fields;
identifying a matching rule for the packet based on the first stage lookup of the hash table and the second stage lookup of the hash table; and
generating a flow entry comprising a set of un-wildcarded bits based on the matching rule and the un-wildcarded first and second sets of bits of the wildcard mask, wherein the flow entry is used to process other packets that match each un-wildcarded bit of the flow entry.

2. The method of claim 1 , wherein the first stage lookup is performed on a first stage of the hash table, the method further comprising, prior to performing the second stage lookup, determining whether the hash table comprises a second stage.

3. The method of claim 1 , wherein the hash table is a first hash table, the method further comprising performing a first stage lookup of a second, different, hash table for a third hash of a third set of fields of the packet header and un-wildcarding bits of the wildcard mask that corresponds to the third set of fields of the packet header.

4. The method of claim 3 , wherein each of the first and second hash tables is searched in order based on a maximum priority value associated with the hash table.

5. The method of claim 4 further comprising, prior to performing the first stage lookup of the second hash table, determining whether to search the second hash table based on the maximum priority value associated with the second hash table.

6. The method of claim 1 , wherein the hash table comprises a plurality of stages comprising at least one of a first stage associated with a set of register or metadata fields, a second stage associated with a set of metadata and network layer 2 (L2) fields, a third stage associated with a set of metadata, L2, and network layer 3 (L3) fields; and a fourth stage associated with each set of fields, wherein each of said first stage lookup of the hash table and the second stage lookup of the hash table lookup one of said plurality of stages of the hash table.

7. The method of claim 6 , wherein the lookup of the hash table is performed on each stage of the hash table in an order starting with the first stage if the corresponding stage in included in the hash table and the lookup results in a match.

8. A non-transitory machine readable medium storing a program that when executed by at least one processing unit forwards packets, the program comprising sets of instructions for:
receiving a packet;
defining a wildcard mask comprising a plurality of bits, each bit in the wildcard mask (i) corresponding to a bit in a header of the packet and (ii) initially set as a wildcard bit;
performing a first stage lookup, of a hash table comprising a set of rules, for a first hash of a first set of fields of the header of the packet and un-wildcarding a first set of bits of the wildcard mask that corresponds to the first set of fields;
performing, if a matching hash is found in the first stage lookup, a second stage lookup of the hash table for a second hash of a second set of fields of the header of the packet and un-wildcarding a second set of bits of the wildcard mask that corresponds to the second set of fields;
identifying a matching rule for the packet based on the first stage lookup of the hash table and the second stagelookup of the hash table; and
generating a flow entry comprising a set of un-wildcarded bits based on the matching rule and the un-wildcarded first and second sets of bits of the wildcard mask, wherein the flow entry is used to process other packets that match each un-wildcarded bit of the flow entry.

9. The non-transitory machine readable medium of claim 8 , wherein the first stage lookup is performed on a first stage of the hash table, wherein the program further comprises a set of instructions for determining, prior to performing the second stage lookup, whether the hash table comprises a second stage.

10. The non-transitory machine readable medium of claim 8 , wherein the hash table is a first hash table, the program further comprising a set of instructions for performing a first stage lookup of a second, different, hash table for a third hash of a third set of fields of the packet header and un-wildcarding bits of the wildcard mask that corresponds to the third set of fields of the packet header.

11. The non-transitory machine readable medium of claim 10 , wherein each of the first and second hash tables is searched in order based on a maximum priority value associated with the corresponding hash table.

12. The non-transitory machine readable medium of claim 11 , wherein the program further comprises a set of instructions for determining, prior to performing the first stage lookup of the second hash table, whether to search the second hash table based on the maximum priority value associated with the second hash table.

13. The non-transitory machine readable medium of claim 8 , wherein the hash table comprises a plurality of stages comprising at least one of a first stage associated with a set of register or metadata fields, a second stage associated with a set of metadata and network layer 2 (L2) fields, a third stage associated with a set of metadata, L2, and network layer 3 (L3) fields; and a fourth stage associated with each set of fields, wherein each of said first stage lookup of the hash table and the second stage lookup of the hash table looks up one of said plurality of stages of the hash table.

14. The non-transitory machine readable medium of claim 13 , wherein the lookup of the hash table is performed on each stage of the hash table in an order starting with the first stage if the corresponding stage in included in the hash table and the lookup results in a match.

15. A computing device comprising:
at least one processing unit; and
a storage, which stores a program that when executed by the at least one processing unit implements a forwarding element, the program comprising sets of instructions for:
receiving a packet;
defining a wildcard mask comprising a plurality of bits, each bit in the wildcard mask (i) corresponding to a bit in a header of the packet and (ii) initially set as a wildcard bit;
performing a first stage lookup, of a hash table comprising a set of rules, for a first hash of a first set of fields of the header of the packet and un-wildcarding a first set of bits of the wildcard mask that corresponds to the first set of fields;
performing, if a matching hash is found in the first stage lookup, a second stage lookup of the hash table for a second hash of a second set of fields of the header of the packet and un-wildcarding a second set of bits of the wildcard mask that corresponds to the second set of fields;
identifying a matching rule for the packet based on the first stage lookup of the hash table and the second stage lookup of the hash table; and
generating a flow e

Assignees

• Nicira Inc

Inventors

• Jackson Ethan J
• Rajahalme Jarno

Classifications

• H04L45/7453 Primary

  using hashing · CPC title

• H04L45/38

  Flow based routing · CPC title

• H04L45/742

  Route cache; Operation thereof · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title