Dynamic flow-based multi-path load balancing with quality of service assurances

A network device comprising:

• an initial load balancer to dynamically assign incoming flows of network packets to network paths in a plurality of network paths to a destination, wherein the initial load balancer assigns the incoming flows such that the network paths have sufficient available bandwidth to satisfy Quality of Service (QoS) bandwidth requirements associated with the incoming flows, and wherein the incoming flows are load balanced among the network paths;
• a load rebalancer to select a flow assigned to one of the network paths when the network path does not have sufficient available bandwidth to satisfy a QoS bandwidth requirement associated with the flow and to un-assign the selected flow from the network path;
• a packet scheduler to send the network packets of the incoming flows to the destination via the assigned network paths, such that the QoS requirements associated with the flows are satisfied;
• and
• a queue structure to hold a hierarchy of network packet queues,
• wherein the queue structure comprises one or more destination queues to contain all unsent network packets awaiting transmission to a destination,
• wherein a destination queue in the queue structure for a destination comprises one or more path queues to contain all unsent network packets awaiting transmission to the destination via a network path,
• wherein a path queue in the queue structure for a network path comprises one or more QoS class queues to contain all unsent network packets awaiting transmission to the destination via the network path that belong to a QoS class, and
• wherein a QoS class queue in the queue structure of a QoS class comprises one or more flow queues to contain all unsent network packets awaiting transmission to the destination via the network path that belong to the QoS class and that belong to a network flow.

A computer-readable medium comprising instructions, the instructions causing a programmable processor to:

• dynamically assign incoming flows of network packets to network paths in a plurality of network paths to a destination, wherein the incoming flows of network packets are assigned such that the network paths have sufficient available bandwidth to satisfy Quality of Service (QoS) bandwidth requirements associated with the incoming flows, and wherein the incoming flows are load balanced among the network paths;
• forward the network packets of the incoming flows along the assigned network paths such that the QoS bandwidth requirements associated with the flows are satisfied;
• select a flow assigned to one of the network paths when the network path does not have sufficient available bandwidth to satisfy a QoS bandwidth requirement associated with a flow assigned to the network path;
• un-assign the selected flow from the network paths;
• and
• maintain a queue structure to hold a hierarchy of network packet queues,
• wherein the queue structure comprises one or more destination queues to contain all unsent network packets awaiting transmission to a destination,
• wherein a destination queue in the queue structure for a destination comprises one or more path queues to contain all unsent network packets awaiting transmission to the destination via a network path,
• wherein a path queue in the queue structure for a network path comprises one or more QoS class queues to contain all unsent network packets awaiting transmission to the destination via the network path that belong to a QoS class, and
• wherein a QoS class queue in the queue structure of a QoS class comprises one or more flow queues to contain all unsent network packets awaiting transmission to the destination via the network path that belong to the QoS class and that belong to a network flow.