Generating flows using common match techniques

Patent metadata

Field	Value
Publication number	US-9686185-B2
Application number	US-201414487057-A
Country	US
Kind code	B2
Filing date	Sep 15, 2014
Priority date	Sep 15, 2013
Publication date	Jun 20, 2017
Grant date	Jun 20, 2017

Abstract

Some embodiments provide a method for a forwarding element that forwards packets. The method receives a packet and performs a hash lookup operation on one or more hash tables to find a matching rule for a packet. The method consults a common match data set to generate a wildcard mask. The method generates a flow based on the matching rule and the wildcard mask. The flow is used to process other packets that match each bit which is un-wildcarded.

First claim

What is claimed is:

1. 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;
examining a first set of rules to find a common match which includes a set of one or more bits that the rules have in common with one another, each bit of the common match corresponding to a bit in a header of the packet;
defining a wildcard mask comprising a plurality of bits, each bit in the wildcard mask (i) corresponding to a bit in the header of the packet and (ii) initially set as a wildcard bit;
identifying a position of a differing bit from a first set of bits of the packet header that is different from a corresponding bit in the common match;
from the wildcard mask, unmasking a bit that is at a same bit position as the position of the differing bit;
comparing a second set of bits in the packet header with a second set of rules to find a matching rule; and
generating a flow entry comprising a set of un-wildcarded bits based on the matching rule and said unmasked bit 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 non-transitory machine readable medium of claim 1 , wherein the set of instructions for examining the first set of rules comprises a set of instructions for generating a common match data set that includes a common match value and a common match mask, the common match value identifying the value of each common bit, and the common match mask identifying the position of each common bit.

3. The non-transitory machine readable medium of claim 2 , wherein the set of instructions for finding the common match comprises a set of instructions for initializing a value of the common match value using the value of one of the first set of rules.

4. The non-transitory machine readable medium of claim 2 , wherein the set of instructions for finding the common match comprises a set of instructions for initializing a mask for the common match based on a mask associated with a hash table.

5. The non-transitory machine readable medium of claim 2 , wherein the set of instructions for examining the first set of rules comprises sets of instructions for:
initializing the value of the common mask based on a first rule in the first set of rules; and
folding each other rule in the first set of rules into the common match data set.

6. The non-transitory machine of claim 5 , wherein the set of instructions for folding each other rule comprises a set of instructions for calculating shared bit data to determine which bits are shared between the other rule and the common match value.

7. The non-transitory machine readable medium of claim 6 , wherein the set of instructions for folding the other rule further comprises a set of instructions for calculating a new common match mask that takes into account the other rule.

8. The non-transitory machine readable medium of claim 6 , wherein the set of instructions for folding the other rule further comprises a set of instructions for calculating a new common match value to set all of the bits that are not part of the common match mask to zero.

9. The non-transitory machine readable medium of claim 2 , wherein the set of instructions for identifying the position of the differing bit comprises a set of instructions for calculating a value that indicates which bits are different from the packet header and a value of the common match.

10. The non-transitory machine readable medium of claim 9 , wherein the set of instructions for identifying the position of the differing bit comprises a set of instructions for generating a differing mask by restricting a calculated value of the common match to only each bit which is common between all of the rules.

11. The non-transitory machine readable medium of claim 10 , wherein the set of instructions for defining the wildcard mask comprises a set of instructions for selecting one bit from the differing mask and unmasking a corresponding bit from the wildcard mask.

12. A computing device comprising:
at least one processing unit;
a storage, which stores a program that when executed by the at least one processing unit implements a forwarding element, the forwarding element for:
receiving a packet;
examining a first set of rules to find a common match which includes a set of one or more bits that the rules have in common with one another, each bit of the common match corresponding to a bit in a header of the packet;
defining a wildcard mask comprising a plurality of bits, each bit in the wildcard mask (i) corresponding to a bit in the header of the packet and (ii) initially set as a wildcard bit;
identifying a position of a differing bit from a first set of bits of the packet header that is different from a corresponding bit in the common match;
from the wildcard mask, unmasking a bit that is at a same bit position as the position of the differing bit;
comparing a second set of bits in the packet header with a second set of rules to find a matching rule; and
generating a flow entry comprising a set of un-wildcarded bits based on the matching rule and said unmasked bit of the wildcard mask, wherein the flow entry is used to process other packets that match each un-wildcarded bit of the flow entry.

13. The computing device of claim 12 , wherein the forwarding element further identifies a plurality of differing bits comprising said differing bit by examining a plurality of sets of rules comprising said first set of rules to find common matches, wherein each common match includes a set of one or more bits that each rule in one of the sets of rules has in common with one another.

14. The computing device of claim 13 , wherein the forwarding element examines the plurality of sets of rules by generating, for each set of rule, a common match data set that includes a common match value and a common match mask, the common match value identifying the value of each common bit, and the common match mask identifying the position of each common bit.

15. The computing device of claim 14 , wherein the forwarding element examines the plurality of sets of rules further by attempting to fold each rule in a set of rules into one of the common match data sets.

16. The computing device of claim 15 , wherein the forwarding element examines the plurality of sets of rules further by creating a new common match data set if the fold operation results in the common match data set indicating that the set of rules collectively have no bits in common.

17. The computing device of claim 14 , wherein the forwarding element generates the wildcard mask by generating a plurality of differing masks using the common match masks by selecting one bit from each common match mask and unmasking a corresponding bit from the wildcard mask.

18. For a forwarding element that forwards packets, a method comprising:
receiving a packet;
examining a first set of rules to find a common match which includes a set of one or more bits that the rules have in common with one another, each bit of the common match corresponding to a bit in a header of the packet;
defining a wildcard mask comprising a plurality of bits, each bit in the wildcard mask (i) corresponding to a bit in the header of the packet and (ii) initially set as a wildcard bit;
identifying a position of a differing bit from a first set of bits of the packet header that is different from a corresponding bit in the common match;
from the wildcard mask, unmasking a bit that

Assignees

• Nicira Inc

Inventors

• Shelly Nicholas
• Jackson Ethan J
• Koponen Teemu

Classifications

• H04L45/7453

  using hashing · CPC title

• H04L45/38 Primary

  Flow based routing · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title