Flow distribution table for packet flow load balancing

A method comprising:

• by a controller for a plurality of traffic nodes that are configured as a distributed computing system to apply a service to packet flows received by any of the plurality of traffic nodes, receiving a resource utilization report from a source traffic node of the plurality of traffic nodes,
• wherein the source traffic node of the plurality of traffic nodes stores a flow distribution table comprising a plurality of flow distribution table entries that each associates a corresponding flow key range of a plurality of flow key ranges with an owner traffic node of the plurality of traffic nodes for the corresponding flow key range, wherein each of the plurality of flow key ranges comprises a contiguous range of flow key values;
• sending, by the controller in response to the resource utilization report and to the source traffic node, a rebalance notification message that directs source traffic node to migrate at least one flow key range of the plurality of flow key ranges;
• receiving, by the controller from the source traffic node, a range migration update message that indicates the source traffic node is ready to migrate ownership of a flow key range for migration to a target traffic node of the plurality of traffic nodes;
• and
• broadcasting, by the controller to the plurality of traffic nodes, a range migration broadcast message that indicates the target traffic node is an owner traffic node of the flow key range for migration.

A system comprising:

• a plurality of traffic nodes that are configured as a distributed computing system to apply a service to packet flows received by any of the plurality of traffic nodes, wherein the plurality of traffic nodes includes a source traffic node and a target traffic node, wherein the source traffic node comprises:
• a control unit comprising a processor;
• a computer-readable storage medium configured to store a flow distribution table comprising a plurality of flow distribution table entries that each associates a corresponding flow key range from a plurality of flow key ranges with an owner traffic node of the plurality of traffic nodes for the corresponding flow key range, wherein each of the plurality of flow key ranges comprises a contiguous range of flow key values,
• wherein an existing flow distribution table entry of the flow distribution table entries associates an existing flow key range with the source traffic node;
• a distribution manager executed by the control unit and configured to generate a new flow distribution table entry that associates a new flow key range with the target traffic node, wherein the new flow key range is a sub-range of the existing flow key range;
• and
• a flow router executed by the control unit and configured to receive an initial packet of a packet flow from the packet flows, match the initial packet to the new flow key range of the new flow distribution table entry, and forward the initial packet of the packet flow to the target traffic node based at least on the new flow distribution table entry that associates the new flow key range with the target traffic node.

A controller device for a plurality of traffic nodes that are configured as a distributed computing system to apply a service to packet flows received by any of the plurality of traffic nodes, the controller device comprising:

• a processor configured to:
• receive a resource utilization report from a source traffic node of the plurality of traffic nodes, wherein the source traffic node of the plurality of traffic nodes stores a flow distribution table comprising a plurality of flow distribution table entries that each associates a corresponding flow key range of a plurality of flow key ranges with an owner traffic node of the plurality of traffic nodes for the corresponding flow key range, wherein each of the plurality of flow key ranges comprises a contiguous range of flow key values;
• send, in response to the resource utilization report and to the source traffic node, a rebalance notification message that directs source traffic node to migrate at least one flow key range of the plurality of flow key ranges;
• receive, from the source traffic node, a range migration update message that indicates the source traffic node is ready to migrate ownership of a flow key range for migration to a target traffic node of the plurality of traffic nodes;
• and
• broadcast, to the plurality of traffic nodes, a range migration broadcast message that indicates the target traffic node is an owner traffic node of the flow key range for migration.