DATA PLANE WITH HEAVY HITTER DETECTOR
Some embodiments of the invention provide a data-plane forwarding circuit (data plane) that can be configured to identify large data message flows that it processes for forwarding in a network. In this document, large data message flows are referred to as heavy hitter flows. To perform its forwarding operations, the data plane includes several data message processing stages that are configured to process the data tuples associated with the data messages received by the data plane. In some embodiments, parts of the data plane message-processing stages are also configured to implement a heavy hitter detection (HHD) circuit. The operations of the data plane's message processing stages are configured by a control plane of the data plane's forwarding element in some embodiments.
1 . A method of identifying large data message flows processed by a network forwarding element, the method comprising
in a data-plane circuit of the network forwarding element
performing data message forwarding operations to process received data messages for forwarding within a network, and
generating probabilistic statistical values regarding the processed data message flows,
based on the generated probabilistic statistical values, identifying a subset of the processed data messages to be part of large data message flows, and
associating with a large-flow tag each data message in the subset of data message in order to designate the data message as being part of a large flow.
2 . The method of claim 1 further comprising:
configuring a first set of programmable stages of the data-plane circuit to perform the data message forwarding operations; and
configuring a second set of programmable stages to implement a detection circuit that (i) generates probabilistic statistical values, identifies the subset of the processed data messages to be part of large data message flows, and associates each data message in the subset of data message with the large-flow tag.
3 . The method of claim 1 further comprising:
for a particular data message that is associated with the large-flow tag, performing a forwarding operation based on the large-flow tag.
4 . The method of claim 3 , wherein the forwarding operation comprises selecting, from a plurality of paths to a destination, a path for the particular data message and adjusting at least one header value of the particular data message to ensure that the particular data message traverses the selected path.
5 . The method of claim 3 , wherein
the particular data message is addressed to a first destination address in the network,
the forwarding operation comprises sending a copy of the particular data message to a computer at a second destination address in the network, said computer to further analyze data messages associated with large flows.
6 . The method of claim 3 , wherein the forwarding operation is performed by another network forwarding element.
7 . The method of claim 1 further comprising:
based on the large flow tags, performing a queue management operation in a traffic manager of the data-plane circuit in order to ensure that large flows do not adversely affect processing of smaller flows.
8 . The method of claim 1 , wherein the data-plane circuit comprises a set of stateful storages, the method further comprising storing in the set of stateful storages the generated probabilistic statistical values for the data message flows.
9 . The method of claim 1 further comprising
for a received data message, generating a hash value based on a set of identifiers associated with the data message,
using the generated address value to identify a location in a set of stateful storages, and
based on a set of attributes of the received data message, incrementing a probabilistic statistical value stored at the identified storage location.
10 . The method of claim 9 further comprising periodically resetting the values stored in the set of storage locations.
11 . A non-transitory machine readable medium storing a program for identifying large data message flows processed by a network forwarding element, the program for execution by at least one hardware processing unit, the program comprising sets of instructions for:
configuring a first set of programmable stages of a data-plane circuit of the network forwarding element to perform data message forwarding operations to process received data messages for forwarding within a network, and
configuring a second set of programmable stages to implement a detection circuit that (i) generates probabilistic statistical values regarding the processed data message flows, (ii) based on the generated probabilistic statistical values, identifies a subset of the processed data messages to be part of large data message flows, and (3) associating with a large-flow tag each data message in the subset of data message in order to designate the data message as being part of a large flow.
12 . The non-transitory machine readable medium of claim 11 , wherein the hardware processing unit is a hardware processing unit of a control-plane circuit of the network forwarding element.
13 . The non-transitory machine readable medium of claim 11 , wherein the program further comprises a set of instructions for performing, for a particular data message that is associated with the large-flow tag, a forwarding operation based on the large-flow tag.
14 . The non-transitory machine readable medium of claim 13 , wherein the forwarding operation comprises selecting, from a plurality of paths to a destination, a path for the particular data message and adjusting at least one header value of the particular data message to ensure that the particular data message traverses the selected path.
15 . The non-transitory machine readable medium of claim 13 , wherein
the particular data message is addressed to a first destination address in the network,
the forwarding operation comprises sending a copy of the particular data message to a computer at a second destination address in the network, said computer to further analyze data messages associated with large flows.
16 . The non-transitory machine readable medium of claim 13 , wherein the forwarding operation is performed by another network forwarding element.
17 . The non-transitory machine readable medium of claim 11 , wherein the program further comprises a set of instructions for performing, based on the large flow tags, a queue management operation in a traffic manager of the data-plane circuit in order to ensure that large flows do not adversely affect processing of smaller flows.
18 . The non-transitory machine readable medium of claim 11 , wherein the data-plane circuit comprises a set of stateful storages, the program further comprising a set of instructions for storing in the set of stateful storages the generated probabilistic statistical values for the data message flows.
19 . The non-transitory machine readable medium of claim 11 , wherein the program further comprises sets of instructions for
generating, for a received data message, a hash value based on a set of identifiers associated with the data message,
using the generated address value to identify a location in a set of stateful storages, and
based on a set of attributes of the received data message, incrementing a probabilistic statistical value stored at the identified storage location.
20 . The non-transitory machine readable medium of claim 19 , wherein the program further comprises a set of instructions for periodically resetting the values stored in the set of storage locations.
21 . A method of identifying large data message flows processed by a network forwarding element, the method comprising
for a data message received by the forwarding element, generating two sets of a plurality of storage address values;
to account for the received data message, incrementing statistical values stored in two sets of a plurality of storage locations identified by the two sets of generated address values;
based on a set of interleaving criteria that identifies one of the two sets of storage locations that stores the statistical values that have to be analyzed for the message, analyzing the statistical values stored by the identified set of storage locations to determine whether the message is part of a large flow;
designating the data message as a message that is part of a large flow based on a determination that the data message is part of a large flow.