Proactive load balancing based on fractal analysis

Patent metadata

Field	Value
Publication number	US-10003538-B2
Application number	US-201615177020-A
Country	US
Kind code	B2
Filing date	Jun 8, 2016
Priority date	Jun 8, 2016
Publication date	Jun 19, 2018
Grant date	Jun 19, 2018

Abstract

The disclosure relates to technology for load balancing link utilization of a networking device based on fractal analysis. In one embodiment, link utilization of switches, routers, etc. in a data center is balanced based on a fractal model of the link utilization. Techniques disclosed herein are proactive. For example, instead of reacting to link congestion, the technique predicts future link utilization based on fractal analysis. Then, packet flows (or flowlets) may be assigned to links based on the predicted future link utilization. Hence, congestion on links may be reduced or prevented.

First claim

What is claimed is:

1. An apparatus comprising:
logic configured to:
access link statistics for a plurality of time periods, wherein separate link statistics are accessed for each of a plurality of egress ports of a networking device;
predict a future link statistic for each of the plurality of egress ports based on a separate fractal analysis of the link statistics for each of the egress ports; and
balance a load at the plurality of egress ports based on the predicted future link statistic for the respective egress ports.

2. The apparatus of claim 1 , wherein the logic is further configured to determine a load balancing weight for each of the plurality of egress ports based on the predicted future link statistic for the respective egress ports.

3. The apparatus of claim 2 , wherein the apparatus comprises the plurality of egress ports, and further comprises a plurality of ingress ports that are configured to receive traffic flows; and
wherein the logic is further configured to select ones of the egress ports for the traffic flows based on the load balancing weight for each of the plurality of egress ports.

4. The apparatus of claim 2 , wherein the apparatus comprises the plurality of egress ports, and further comprises a plurality of ingress ports that are configured to receive traffic flows;
wherein the logic is further configured to:
determine flowlets in the traffic flows; and
select ones of the egress ports for the flowlets based on the load balancing weight for each of the plurality of egress ports.

5. The apparatus of claim 1 , wherein the accessed link statistics for each egress port are organized as a time series, wherein the logic is further configured to predict a next value for each time series, the next value being the future link statistic prediction for the respective egress port.

6. The apparatus of claim 5 , further comprising:
an input configured to receive the time series for each of the plurality of egress ports, each time series comprising a link statistic for each of a plurality of recent time windows; and
an output configured to provide a load balancing weight for each of the plurality of egress ports for a time window that immediately follows the recent time windows.

7. The apparatus of claim 1 , wherein the accessed link statistics for the respective egress ports for the plurality of time periods comprise a traffic rate for each of the respective egress ports for each of the plurality of time periods.

8. The apparatus of claim 1 , wherein the accessed link statistics for the respective egress ports for the plurality of time periods comprise a link utilization for each of the respective egress ports for each of the plurality of time periods.

9. The apparatus of claim 1 , wherein to balance the load at the plurality of egress ports based on the predicted future link statistic for the respective egress ports the logic is configured to:
receive the link statistics from the networking device; and
send a load balancing plan to the networking device.

10. A method of load-balancing, comprising:
accessing link statistics for a plurality of egress ports of a networking device, the link statistics for each of the egress ports based on traffic rates at the respective egress port for each of a plurality of recent time periods;
predicting a future link statistic for each of the plurality of egress ports by applying a separate fractal analysis to the link statistics for each of the egress ports, wherein the future link statistic is for a time period that immediately follows the plurality of recent time periods; and
balancing a load at the plurality of egress ports based on the predicted future link statistic for each of the plurality of egress ports.

11. The method of claim 10 , wherein the balancing a load comprises:
weighting each of the plurality of egress ports inversely based on the predicted future link statistic.

12. The method of claim 11 , further comprising:
selecting one of the egress ports to forward a packet flow that is received at an ingress port of the networking device, wherein the selecting is based on the weighting.

13. The method of claim 11 , further comprising:
selecting one of the egress ports to forward a flowlet of a packet flow that is received at an ingress port of the networking device, wherein the selecting is based on the weighting.

14. The method of claim 10 , wherein the link statistics are organized as a time series for each of the plurality of egress ports, wherein the predicting a future link statistic comprises predicting a next value for each time series, the next value being the future link statistic for the respective egress port.

15. The method of claim 10 , wherein the link statistics for each of the plurality of egress ports comprise a value for a traffic rate for each of a plurality of time windows having the same time length, wherein the predicting a future link statistic comprises predicting a value for the traffic rate for a time window having the same length as the plurality of time windows and that immediately follows the plurality of time windows.

16. The method of claim 10 , wherein the accessing link statistics comprises:
determining link utilization at an access switch in a data center, wherein the access switch has a plurality of ingress ports configured to receive traffic flows from a plurality of servers and forward the traffic flows on the plurality of egress ports.

17. A networking device, comprising:
a plurality of ingress ports configured to receive traffic flows;
a plurality of egress ports;
fractal based analyzer logic configured to predict a traffic rate for each of the plurality of egress ports based on recent traffic rates at the respective egress ports; and
load balancer logic configured to forward the traffic flows received on the plurality of ingress ports over the plurality of egress ports based on the predicted traffic rate of the respective egress ports.

18. The networking device of claim 17 , wherein the load balancer logic is further configured to:
assign a load balancing weight to each of the plurality of egress ports according to the predicted traffic rate of the respective egress ports, wherein egress ports having a lower predicted future traffic rate are assigned a higher load balancing weight and egress ports having a higher predicted future traffic rate are assigned a lower load balancing weight; and
forward the traffic that is received on the plurality of ingress ports over the plurality of egress ports based on the load balancing weights assigned to the respective egress ports.

19. The networking device of claim 17 , wherein the recent traffic rates for each of the respective egress ports comprises a time series having a traffic rate for each of a plurality of points in the time series, wherein the fractal based analyzer logic is configured to predict a next traffic rate in each of the time series, the next traffic rate being the predicted traffic rate.

20. The networking device of claim 17 , further comprising:
a link statistics collector configured to determine the recent traffic rates for each of the egress ports for each of a plurality of recent time periods that each have an equal time length.

21. The networking device of claim 17 , wherein the fractal based analyzer logic is configured to process the recent traffic rate of the respective egress ports using one or more of:
a wavelet based prediction engine, a fractionally autoregressive integrated moving average (F

Assignees

• Futurewei Technologies Inc

Inventors

• Avci Serhat Nazim
• Li Zhenjiang
• Liu Fangping

Classifications

• H04L47/125 Primary

  by balancing the load, e.g. traffic engineering · CPC title

• H04L47/127

  by using congestion prediction · CPC title

• H04L45/70

  Routing based on monitoring results · CPC title

• H04L25/03101

  Theory of the Kalman algorithm · CPC title