Phantom queue link level load balancing system, method and device

Patent metadata

Field	Value
Publication number	US-10103993-B2
Application number	US-201815862509-A
Country	US
Kind code	B2
Filing date	Jan 4, 2018
Priority date	Aug 28, 2014
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

A data processing system includes a phantom queue for each of a plurality of output ports each associated with an output link for outputting data. The phantom queues receive/monitor traffic on the respective ports and/or the associated links such that the congestion or traffic volume on the output ports/links is able to be determined by a congestion mapper coupled with the phantom queues. Based on the determined congestion level on each of the ports/links, the congestion mapper selects one or more non or less congested ports/links as destination of one or more packets. A link selection logic element then processes the packets according to the selected path or multi-path thereby reducing congestion on the system.

First claim

I claim:

1. A dynamic load balancing system on a microchip,
the system comprising:
a plurality of output ports;
link selection logic that receives packets and, for each of the packets, selects which one of the output ports the packet is to be output from; and
a plurality of shapers, wherein each of the shapers is coupled to one of the output ports, and further wherein each of the shapers indicate a congestion level of the output port coupled to the shaper;

wherein for each of the packets:
if the packet has a transmission control protocol (TCP) format, the link selection logic selects the one of the output ports independent of the congestion level of each of the output ports; and
if the packet does not have the TCP format, the link selection logic selects the one of the output ports based on the congestion level of each of the output ports.

2. The system of claim 1 , wherein if the packet does have the TCP format, the link selection logic selects the one of the output ports based on a hash of the input traffic packet and an equal or weighted cost multipath selection protocol.

3. The system of claim 2 , wherein if the packet does not have the TCP format, the link selection logic selects the one of the output ports according to a metric except the link selection logic will remove all of the output ports whose congestion level is above a congestion threshold value from a pool of the output ports that are able to be selected according to the metric.

4. The system of claim 3 , wherein if the packet does not have the TCP format and all of the output ports have a congestion level that is above the congestion threshold value, the link selection logic selects the one of the output ports according to the metric while including all of the output ports in the pool despite the congestion level of all of the output ports.

5. The system of claim 4 , wherein the metric is one of the group consisting of round robin, random, and smallest congestion level first.

6. The system of claim 5 , wherein each of the shapers comprise:
a phantom queue; and
a credit generator that deposits a credit into the phantom queue at a predefined credit deposit rate;

wherein as each of the packets is output by one of the output ports, the shaper coupled to the one of the output ports removes one or more credits from the phantom queue of the shaper such that a total value of the removed one or more credits is equal to or greater than a size of the packet.

7. The system of claim 6 , wherein the link selection logic determines the congestion level of each of the output ports based on the number of credits within the phantom queue coupled to the output port.

8. The system of claim 7 , further comprising a plurality of packet queues each coupled with one of the output ports such that the queues receive and queue each of the packets to be output by the output ports.

9. The system of claim 8 , wherein the link selection logic determines the congestion level of each of the output ports based on a number of the packets within a packet queue associated with the output port.

10. The system of claim 9 , further comprising one of more additional shapers, wherein each of the additional shapers is coupled to one of the output ports and monitors the outputting of the packets out of the output port to determine whether a rate of data output by the output port is above an additional data output rate threshold, and further wherein each of the additional shapers indicate an additional congestion level of the output port coupled to the additional shaper.

11. A link selection logic element stored on a non-transitory computer-readable medium of a microchip having a plurality of shapers and a plurality of output ports, wherein each of the shapers is coupled to one of the output ports, the link selection logic element configured to:
receive a plurality of packets input by the microchip;
and
for each of the packets, select which one of the output ports the packet is to be output from, wherein if the packet has transmission control protocol (TCP) format, selection of the one of the output ports is independent of a congestion level of each of the output ports, and if the packet does not have the TCP format, selection of the one of the output ports is based on the congestion level of each of the output ports;

wherein each of the shapers indicate the congestion level of the output port coupled to the shaper.

12. The link selection logic element of claim 11 , wherein if the packet does have the TCP format, the link selection logic element selects the one of the output ports based on a hash of the packet and an equal or weighted cost multipath selection protocol.

13. The link selection logic element of claim 12 , wherein if the packet does not have the TCP format, the link selection logic element selects the one of the output ports according to a metric except the link selection logic element will remove all of the output ports whose congestion level is above a congestion threshold value from a pool of the output ports that are able to be selected according to the metric.

14. The link selection logic element of claim 13 , wherein if the packet does not have the TCP format and all of the output ports have a congestion level that is above the congestion threshold value, the link selection logic element selects the one of the output ports according to the metric while including all of the output ports in the pool despite the congestion level of all of the output ports.

15. The link selection logic element of claim 14 , wherein the metric is one of the group consisting of round robin, random, and smallest congestion level first.

16. The link selection logic element of claim 15 , wherein each of the shapers comprise:
a phantom queue; and
a credit generator that deposits a credit into the phantom queue at a predefined credit deposit rate;

wherein as each of the packets is output by one of the output ports, the shaper coupled to the one of the output ports removes one or more credits from the phantom queue of the shaper such that a total value of the removed one or more credits is equal to or greater than a size of the input traffic packet.

17. The link selection logic element of claim 16 , wherein the link selection logic element determines the congestion level of each of the output ports based on a number of credits within the phantom queue coupled to the output port.

18. The link selection logic element of claim 17 , wherein the microchip has a plurality of packet queues each coupled with one of the output ports such that the queues receive and queue each of the packets to be output by the output ports.

19. The link selection logic element of claim 18 , wherein the link selection logic element determines the congestion level of each of the output ports based on a number of the packets within a packet queue associated with the output port.

20. The link selection logic element of claim 19 , wherein the microchip further comprises one of more additional shapers such that each of the additional shapers is coupled to one of the output ports, wherein each of the additional shapers indicate an additional congestion level of the output port coupled to the additional shaper, and further wherein if the packet does not have the TCP format, the link selection logic element selects the one of the output ports based on the congestion level and the additional congestion levels of each of the output ports.

21. A method of dynamic load balancing within a

Assignees

• Cavium Inc

Inventors

• White Martin Leslie

Classifications

• G06F9/505

  considering the load · CPC title

• H04L47/11

  Identifying congestion · CPC title

• H04L43/0882

  Utilisation of link capacity · CPC title

• G06F9/5083

  Techniques for rebalancing the load in a distributed system · CPC title

• H04L47/122

  by diverting traffic away from congested entities · CPC title