# US 2019/0356592 A1 · Data plane with heavy hitter detector > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0356592 A1 - Document ID: US20190356592A1 - Status: Published application - Kind: A1 - Application number: 16/051,405 - Filed: 2018-07-31 - Published: 2019-11-21 - Earliest claimed: 2018-05-21 - Assignees: Barefoot Networks, Inc. - Applicants: Barefoot Networks, Inc. - Inventors: Georgios Nikolaidis; Jeongkeun Lee; Changhoon Kim - Web page: https://patentgrep.com/patent/US20190356592A1 ## CPC - H04L 41/142: using statistical or mathematical methods - H04L 43/026: using flow identification - H04L 43/16: Threshold monitoring - H04L 45/16: Multipoint routing - H04L 45/38: {Flow based routing} - H04L 45/64: using an overlay routing layer - H04L 45/7453: using hashing - H04L 47/11: Identifying congestion - H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ] - H04L 47/2483: involving identification of individual flows - H04L 47/32: by discarding or delaying data units, e.g. packets or frames - H04L 49/3009: {Header conversion, routing tables or routing tags} - H04L 49/90: Buffering arrangements - H04L 45/74: Address processing for routing - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract 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. ## Claims ### Claim 1 For a network forwarding element, a data-plane circuit for forwarding data messages within a network, the data-plane forwarding circuit comprising: a plurality of programmable stages to process data tuples associated with data messages received by the data-plane circuit, the programmable stages comprising a first set of programmable stages to perform data message forwarding operations to process received data messages for forwarding within the network, and 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 and designates a subset of the processed data messages to be part of large data message flows. ### Claim 2 (depends on 1) The data-plane forwarding circuit of claim 1, wherein the programmable stages comprise message processing stages with a set of programmable components, the first set of programmable message processing stages performs the data message forwarding operations of the data-plane circuit once the first set programmable components are programmed to process data tuples associated with the received messages to forward the data messages within the network, and the second set of programmable message processing stages implements the large-flow detection circuit once the programmable components of the set are programmed to perform large-flow detection operations of the detection circuit. ### Claim 3 (depends on 1) The data-plane forwarding circuit of claim 1, wherein the data-plane circuit comprises a plurality of stateful processing units in at least a subset of the second set of programmable stages, the stateful processing units comprising a plurality of stateful storages, and the detection circuit comprises: a set of stateful storages to store probabilistic statistical values for the data message flows processed by the first set of programmable stages; and a set of stateful processing units to generate the probabilistic statistical values regarding the processed data message flows, to store the generated probabilistic statistical values in the set of stateful storages, and to identify the subset of the processed data message flows as being part of large data message flows based on the generated probabilistic statistical values. ### Claim 4 (depends on 1) The data-plane forwarding circuit of claim 1, wherein for a received data message, the detection circuit generates at least one address value based on a set of identifiers associated with the data message, uses the generated address value to identify a location in a storage, and based on a set of attributes of the received data message, increments a probabilistic statistical value stored at the identified storage location. ### Claim 5 (depends on 1) The data-plane forwarding circuit of claim 1, wherein for a received data message, the detection circuit generates a plurality of address value based on a set of identifiers associated with the data message, uses the plurality of generated address values to identify a plurality of locations in a set of storage, and based on a set of attributes of the received data message, increments a plurality of probabilistic statistical values stored at the plurality of the identified storage locations. ### Claim 6 (depends on 5) The data-plane forwarding circuit of claim 5, wherein the set of data-message attributes comprise a set of flowing-identifying header values that identify the flow associated with the data message. ### Claim 7 (depends on 6) The data-plane forwarding circuit of claim 6, wherein the detection circuit comprises a set of one or more hash generators that generates a plurality of hash values from the set of flow-identifying header values of the data message, said hash values serving as the generated address values for identifying the plurality of storage locations. ### Claim 8 (depends on 5) The data-plane forwarding circuit of claim 5, wherein the plurality of address values comprises first and second sets of a plurality of address values, each set of address values identifying a different set of storage locations, each set of storage locations storing probabilistic statistical values that are updated for the received data message, but only the probabilistic set of values stored in one set of storage locations is analyzed to determine whether the data message is part of a large data message flow. ### Claim 9 (depends on 8) The data-plane forwarding circuit of claim 8, wherein for a received data message, the detection circuit uses a set of interleaving criteria to select the storage-location set that stores the probabilistic statistical values to analyze, the set of interleaving criteria for interleaving the use of the first and second sets of storage locations as the set of storage locations that stores the probabilistic statistical values to analyze. ### Claim 10 (depends on 1) The data-plane forwarding circuit of claim 1 further comprising a plurality of ports to receive and transmit data messages. ### Claim 11 A network forwarding element comprising a data-plane circuit to forward data messages within a network; and a control-plane circuit to program the data-plane circuit; the data-plane forwarding circuit comprising: a plurality of programmable stages to process data tuples associated with data messages received by the data-plane circuit, the programmable stages comprising a first set of programmable stages to perform data message forwarding operations to process received data messages for forwarding within the network, and 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 and designates a subset of the processed data messages to be part of large data message flows. ### Claim 12 (depends on 11) The network forwarding element of claim 11, wherein the programmable stages comprise message processing stages with a set of programmable components, the first set of programmable message processing stages performs the data message forwarding operations of the data-plane circuit once the first set programmable components are programmed to process data tuples associated with the received messages to forward the data messages within the network, and the second set of programmable message processing stages implements the large-flow detection circuit once the programmable components of the set are programmed to perform large-flow detection operations of the detection circuit. ### Claim 13 (depends on 11) The network forwarding element of claim 11, wherein the data-plane circuit comprises a plurality of stateful processing units in at least a subset of the second set of programmable stages, the stateful processing units comprising a plurality of stateful storages, and the detection circuit comprises: a set of stateful storages to store probabilistic statistical values for the data message flows processed by the first set of programmable stages; and a set of stateful processing units to generate the probabilistic statistical values regarding the processed data message flows, to store the generated probabilistic statistical values in the set of stateful storages, and to identify the subset of the processed data message flows as being part of large data message flows based on the generated probabilistic statistical values. ### Claim 14 (depends on 11) The network forwarding element of claim 11, wherein for a received data message, the detection circuit generates at least one address value based on a set of identifiers associated with the data message, uses the generated address value to identify a location in a storage, and based on a set of attributes of the received data message, increments a probabilistic statistical value stored at the identified storage location. ### Claim 15 (depends on 11) The network forwarding element of claim 11, wherein for a received data message, the detection circuit generates a plurality of address value based on a set of identifiers associated with the data message, uses the plurality of generated address values to identify a plurality of locations in a set of storage, and based on a set of attributes of the received data message, increments a plurality of probabilistic statistical values stored at the plurality of the identified storage locations. ### Claim 16 (depends on 15) The network forwarding element of claim 15, wherein the set of data-message attributes comprise a set of flowing-identifying header values that identify the flow associated with the data message. ### Claim 17 (depends on 16) The network forwarding element of claim 16, wherein the detection circuit comprises a set of one or more hash generators that generates a plurality of hash values from the set of flow-identifying header values of the data message, said hash values serving as the generated address values for identifying the plurality of storage locations. ### Claim 18 (depends on 15) The network forwarding element of claim 15, wherein the plurality of address values comprises first and second sets of a plurality of address values, each set of address values identifying a different set of storage locations, each set of storage locations storing probabilistic statistical values that are updated for the received data message, but only the probabilistic set of values stored in one set of storage locations is analyzed to determine whether the data message is part of a large data message flow. ### Claim 19 (depends on 18) The network forwarding element of claim 18, wherein for a received data message, the detection circuit uses a set of interleaving criteria to select the storage-location set that stores the probabilistic statistical values to analyze, the set of interleaving criteria for interleaving the use of the first and second sets of storage locations as the set of storage locations that stores the probabilistic statistical values to analyze. ### Claim 20 (depends on 18) The network forwarding element of claim 18, wherein the detection circuit periodically resets the first and second sets of storage locations, but resets the first storage-location set at different times than the second storage-location set. ### Claim 21 (depends on 18) The network forwarding element of claim 18, wherein the resetting of the first and second storage-location sets are interleaved so after being reset, each storage-location set operates in a accumulate-only first period to store probabilistic statistical values before being read to determine whether any data message is part of a large data message flow, while the other storage-location set operates in its accumulate-only first period after being reset, each storage-location set operates in an accumulate-and-access second period to store probabilistic statistical values and to provide stored probabilistic statistical values for determining whether any data message is part of a large data message flow.