Phantom queue link level load balancing system, method and device
View Patent ↗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.
1. A dynamic load balancing system on a processing microchip, the system comprising:
a multipath interface group comprising a plurality of paths for outputting packets from the processing microchip, wherein each of the paths is coupled to an output port of the processing microchip;
link selection logic that receives input traffic packets and, for each of the input traffic packets, selects which one of the output ports the input traffic packet is to be output from onto the path coupled to the one of the output ports; 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 that corresponds to a quantity of the input traffic packets sent to the output port by the link selection logic during a time period;
wherein for each of the input traffic packets the link selection logic determines whether to perform output port congestion-based selection based on whether the input traffic packet has or does not have a transmission control protocol (TCP) format, the output port congestion-based selection comprising:
if the input traffic packet does have the TCP format, select the one of the output ports independent of the congestion level of each of the output ports; and
if the input traffic packet does not have the TCP format, select the one of the output ports based on the congestion level of each of the output ports such that the link selection logic performs the output port congestion-based selection for all of the input traffic packets that do not have the TCP format.
2. The system of claim 1 , wherein if the input traffic 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 input traffic 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 input traffic 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 input traffic 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.
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 input traffic 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 input traffic 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 input traffic 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 that corresponds to the quantity of the input traffic packets sent to the output port by the link selection logic during the time period.
11. The system of claim 1 , wherein each of the plurality of shapers monitors the outputting of the input traffic packets out of the output port to determine whether a rate of data output by the output port is above a data output rate threshold.
12. A link selection logic element stored on a non-transitory computer-readable medium of a processing microchip having a plurality of shapers and a multipath interface group including a plurality of paths for outputting packets from the processing microchip, wherein each of the paths is coupled to an output port of the processing microchip and each of the shapers is coupled to one of the output ports, the link selection logic element configured to:
receive a plurality of input traffic packets input by the processing microchip;
for each of the input traffic packets, determine whether to perform output port congestion-based selection based on whether the input traffic packet has or does not have a transmission control protocol (TCP) format; and
for each of the input traffic packets, select which one of the output ports the input traffic packet is to be output from onto the path coupled to the one of the output ports, wherein if the input traffic packet does have the 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 input traffic 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 such that the link selection logic element performs the output port congestion-based selection for all of the input traffic packets that do not have the TCP format;
wherein each of the shapers indicate the congestion level of the output port coupled to the shaper that corresponds to a quantity of the input traffic packets sent to the output port by the link selection logic element during a time period.
13. The link selection logic element of claim 12 , wherein if the input traffic packet does have the TCP format, the link selection logic element 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.
14. The link selection logic element of claim 13 , wherein if the input traffic 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.
15. The link selection logic element of claim 14 , wherein if the input traffic 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.
16. The link selection logic element of claim 15 , wherein the metric is one of the group consisting of round robin, random, and smallest congestion level first.
17. The link selection logic element of claim 16 , 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 input traffic 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.
18. The link selection logic element of claim 17 , 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.
19. The link selection logic element of claim 18 , wherein the processing 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 input traffic packets to be output by the output ports.
20. The link selection logic element of claim 19 , wherein the link selection logic element determines the congestion level of each of the output ports based on a number of the input traffic packets within a packet queue associated with the output port.
21. The link selection logic element of claim 20 , wherein the processing 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 that corresponds to the quantity of the input traffic packets sent to the output port by the link selection logic element during the time period, and further wherein if the input traffic 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.
22. The link selection logic element of claim 12 , wherein each of the plurality of shapers monitors the outputting of the input traffic packets out of the output port to determine whether a rate of data output by the output port is above a data output rate threshold.
23. A method of dynamic load balancing within a dynamic load balancing system, the method comprising:
receiving a plurality of input traffic packets with link selection logic on a processing microchip having a plurality of shapers and a multipath interface group including a plurality of paths for outputting packets from the processing microchip, wherein each of the paths is coupled to an output port of the processing microchip and each of the shapers is coupled to one of the output ports;
for each of the input traffic packets, determining whether to perform output port congestion-based selection based on whether the input traffic packet has or does not have a transmission control protocol (TCP) format with the link selection logic; and
for each of the input traffic packets, selecting which one of the output ports the input traffic packet is to be output from onto the path coupled to the one of the output ports with the link selection logic, wherein if the input traffic packet does have the 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 input traffic 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 such that the output port congestion-based selection is performed for all of the input traffic packets that do not have the TCP format;
wherein each of the shapers indicate the congestion level of the output port coupled to the shaper that corresponds to a quantity of the input traffic packets sent to the output port by the link selection logic during a time period.
24. The method of claim 23 , further comprising, if the input traffic packet does have the TCP format, selecting the one of the output ports based on a hash of the input traffic packet and an equal or weighted cost multipath selection protocol with the link selection logic.
25. The method of claim 24 , further comprising, if the input traffic packet does not have the TCP format, selecting the one of the output ports according to a metric with the link selection logic wherein the link selection logic removes 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.
26. The method of claim 25 , further comprising, if the input traffic packet does not have the TCP format and all of the output ports have a congestion level that is above the congestion threshold value, selecting the one of the output ports according to the metric with the link selection logic while including all of the output ports in the pool despite the congestion level of all of the output ports.
27. The method of claim 26 , wherein the metric is one of the group consisting of round robin, random, and smallest congestion level first.
28. The method of claim 23 , 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;
further comprising as each of the input traffic packets is output by one of the output ports, removing, with the shaper coupled to the one of the output ports, 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.
29. The method of claim 28 , further comprising determining the congestion level of each of the output ports with the link selection logic based on a number of credits within the phantom queue coupled to the output port.
30. The method of claim 29 , wherein the processing microchip further comprises a plurality of packet queues each coupled with one of the output ports such that the queues receive and queue each of the input traffic packets to be output by the output ports.
31. The method of claim 30 , further comprising determining the congestion level of each of the output ports with the link selection logic based on a number of the input traffic packets within a packet queue associated with the output port.
32. The method of claim 31 , wherein the processing microchip has one or more additional shapers such that each of the additional shapers is coupled to one of the output ports and monitors the outputting of the input traffic packets out of the output port to determine whether a rate of data output by the output port is below 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 that corresponds to the quantity of the input traffic packets sent to the output port by the link selection logic during the time period, and further wherein if the input traffic packet does not have the TCP format, the selecting of the one of the output ports is based on the congestion level and the additional congestion levels of each of the output ports.
33. The method of claim 23 , wherein each of the plurality of shapers monitors the outputting of the input traffic packets out of the output port to determine whether a rate of data output by the output port is above a data output rate threshold.