Forwarding element with a data plane load balancer

1. A forwarding element for forwarding data messages in a network, the forwarding element comprising:

a data-plane circuit to forward data messages in the network; and

a control-plane circuit to configure the data-plane circuit,

the data-plane circuit comprising:

a load balancer to forward message flows to different nodes of a node group, the load balancer comprising:

(i) a set of storages to store a plurality of different address mapping sets with each address mapping set corresponding to a different set of nodes in the node group;

(ii) a destination selector to receive a set identifier for each message flow and to select a node for each message flow from a mapping set identified by the set identifier received for the message flow;

(iii) a set ID allocator to assign (1) a first set identifier for each message flow processed during a first sub-interval of an update interval when the node group is being modified, and (2) first and second set identifiers for each message flow processed during a second sub-interval of the update interval when the node group is being modified; and

(iv) a cache stage that during the first sub-interval, is to store values that identify the message flows processed during the first sub-interval, and during the second sub-interval, is to assign the first set identifier to each message flow when the cache stage stores a value that identifies the message flow as being processed during the first sub-interval, and is to assign the second set identifier to each message flow when the cache stages does not store such a value for the message flow.

2. The forwarding element of claim 1 , wherein the data-plane circuit further comprises a plurality of configurable data processing circuits in a plurality of data processing stages, the data processing circuits comprising:

a plurality of data processing circuits configured to process data tuples associated with data messages received by the forwarding element in order to forward the data messages within a network, and

a plurality of data processing circuits configured to implement the destination selector and set ID allocator of the load balancer.

3. The forwarding element of claim 2 , wherein the control-plane circuit is to configure the data-plane circuit by configuring the configurable data processing circuits of the data plane forwarding circuit, the control-plane circuit to configure a set of data processing circuits that implement the set ID allocator to operate either in a transient-interval mode when the node group is not being modified, or in an update-interval mode when the node group is being modified.

4. The forwarding element of claim 3 , wherein during the transient-interval mode, the set ID allocator is to assign one set identifier for each message flow.

5. The forwarding element of claim 1 , wherein the data-plane circuit further comprises:

a plurality of configurable data processing circuits in a plurality of data processing stages,

wherein the data processing circuits are configured to process data tuples associated with data messages received by the forwarding element, and a subset of data processing circuits further configured to implement the set ID allocator and the cache stage of the load balancer, and

wherein the set ID allocator and the cache stage output set identifiers and cache hit/miss values by storing the set identifiers and cache hit/miss values in the data tuples processed by the set ID allocator and cache stage.

6. The forwarding element of claim 1 , wherein the second sub-interval is an integer multiple of the first sub-interval.

7. The forwarding element of claim 1 , wherein the data-plane circuit further comprises:

a connection storage to store for each of a plurality previously processed message flows, a message flow identifier and a set identifier,

a plurality of configurable data processing circuits in a plurality of data processing stages,

wherein the control-plane circuit is to configure a subset of data processing circuits to implement (1) the set ID allocator, and (2) the connection storage.

8. The forwarding element of claim 7 , wherein

when a message is received, the subset of data processing circuits (1) is to determine whether the connection storage stores a set identifier for the message's flow identifier, (2) if so, output the stored set identifier for the destination selector to use, and (3) if not, direct the set ID allocator to output a set identifier for the destination selector to use, and

the second sub-interval is larger than an expected duration for the control-plane circuit to store in the connection storage the set identifiers that are stored in preceding first sub-interval in the cache stage.

9. The forwarding element of claim 8 , wherein the second sub-interval is an integer multiple of the expected duration.

10. The forwarding element of claim 1 , wherein the data-plane circuit further comprises:

a connection storage to store for each of a plurality previously processed message flows, a message flow identifier and a set identifier, wherein for a received message, the connection storage (1) is to determine whether it stores a set identifier for the received message's flow identifier, (2) if so, outputs the stored set identifier for the destination selector to use, and (3) if not, directs the set ID allocator to output a set identifier for the destination selector to use.

11. The forwarding element of claim 10 , wherein the data-plane circuit further comprises a trigger circuit to receive set identifiers output from the set ID allocator along with corresponding message flow identifiers, and to provide at least a subset of the set identifiers and corresponding message flow identifiers to the control-plane circuit to store in the connection storage.

12. The forwarding element of claim 11 , wherein the data-plane circuit further comprises a plurality of configurable data processing circuits in a plurality of data processing stages, the data processing circuits comprising:

a plurality of data processing circuits configured to process data tuples associated with data messages received by the forwarding element in order to forward the data messages within a network, and

a plurality of data processing circuits configured to implement the connection storage, the set ID allocator, the cache stage and the destination selector of the load balancer,

wherein the connection storage, the set ID allocator and the cache stage write to the processed data tuples in order to provide their outputs.

13. The forwarding element of claim 1 , wherein the data-plane circuit further comprises a plurality of configurable data processing circuits in a plurality of data processing stages, the data processing circuits comprising stateful arithmetic logic units at least one of which is configured to implement the cache stage.