Apparatus and method for dynamic hybrid routing in SDN networks to avoid congestion and balance loads under changing traffic load

Patent metadata

Field	Value
Publication number	US-9680665-B2
Application number	US-201514695832-A
Country	US
Kind code	B2
Filing date	Apr 24, 2015
Priority date	Apr 24, 2014
Publication date	Jun 13, 2017
Grant date	Jun 13, 2017

Abstract

Given a large number of traffic matrices, the matrices are divided into M clusters, where M is a relatively small number. A load-balancing apparatus is implemented as an application over the SDN controller. Such an application is executed to configure and reconfigure the switches to achieve near-optimal load balancing, even when the traffic load changes. For each cluster, a near-optimal explicit routing configuration is determined. The combination of explicit routing (cluster-specific) and destination-based routing (same for all clusters) is used to achieve near-optimal load balancing for each cluster.

First claim

What is claimed is:

1. An apparatus for performing dynamic hybrid routing in a centrally controlled network comprising:
a data plane comprising a plurality of switches;
a storage device configured to store historical traffic data; and
a controller coupled to the data plane and the storage device, wherein the controller is configured to:
generate a plurality of traffic matrices from the historical traffic data, wherein the traffic matrices represent previous traffic load fluctuations;
form a plurality of clusters from the traffic matrices by merging the traffic matrices until a merge cost reaches a predetermined threshold;
generate explicit routing configurations for the clusters; and
deploy a first explicit routing configuration which improves traffic load balance.

2. The apparatus of claim 1 , wherein the controller is further configured to:
generate a destination-based routing configuration based on the traffic matrices; and
configure a first switch of the plurality of switches using the destination-based routing configuration.

3. The apparatus of claim 2 , wherein the controller is further configured to:
divide a period of time into smaller periods of time; and
determine a destination-based routing configuration for each smaller period of time based on the historical traffic data.

4. The apparatus of claim 2 , wherein the controller is further configured to configure a second switch of the centrally controlled network using the explicit routing configuration when a change in traffic conditions of the centrally controlled network is detected.

5. The apparatus of claim 4 , wherein the configuring the second switch comprises applying the explicit routing configuration to traffic moving between a set of source-destination pairs.

6. The apparatus of claim 1 , wherein forming a plurality of clusters from the traffic matrices comprises iteratively merging the traffic matrices into larger clusters until the merge cost reaches the pre-determined threshold.

7. The apparatus of claim 1 , wherein the controller is further configured to:
select a maximum demand volume for a pair of nodes of the traffic matrices; and
generate a basic traffic matrix based on the maximum demand volume, wherein the basic traffic matrix represents a worst-case traffic load.

8. A method for performing dynamic hybrid routing based on historical traffic data, comprising:
generating a set of traffic matrices from historical traffic data representing previous traffic load fluctuations;
generating a first traffic matrix representing a worst-case traffic load based on the set of traffic matrices;
determining a destination-based routing scheme based on the first traffic matrix;
determining one or more explicit routing schemes for one or more traffic matrices of the set of traffic matrices;
merging traffic matrices of the set of traffic matrices to form clusters until a merge cost reaches a predetermined threshold; and
upon detecting a change in traffic load, selecting an explicit routing scheme.

9. The method of claim 8 , wherein the selected explicit routing scheme improves traffic load balance.

10. The method of claim 9 , further comprising applying the explicit routing configuration to traffic moving between a set of source-destination pairs.

11. The method of claim 10 , wherein configuring one or more network switches comprises using an SDN controller.

12. The method of claim 8 , wherein determining a destination-based routing scheme comprises using linear programming.

13. The method of claim 12 , wherein the linear programming is performed using CPLEX.

14. The method of claim 9 , further comprising periodically checking a traffic load of a link and adding a new traffic matrix representing the link to the set of traffic matrices when a traffic load of the link exceeds a threshold value.

15. The method of claim 14 , wherein the threshold value is based on a percentage of maximum traffic load associated with the link.

16. A method of dynamic hybrid routing and load balancing for software-defined networking comprising:
determining an explicit routing scheme for a plurality of clusters of traffic matrices;
calculating a merge cost for pairs of the clusters;
identifying a first pair of clusters having a minimum merge cost;
merging the first pair of clusters together;
recording the explicit routing for the merged cluster;
identifying one or more key flows of the first cluster based on the two or more traffic matrices, wherein the key flows contribute to network congestion;
applying the explicit routing scheme to the key flows; and
applying a destination-based routing scheme to a first set of traffic, wherein the first set of traffic does not include the key flows.

17. The method of claim 16 , further comprising configuring one or more SDN switches using the explicit routing.

18. The method of claim 16 , further comprising using a heuristic algorithm to determine a combination of explicit routing and destination-based routing to improve load balancing.

19. The method of claim 16 , wherein merging the pair of clusters together does not cause a significant increase in traffic congestion.

20. The method of claim 16 , further comprising merging pairs of clusters together until a threshold merge cost is reached.

21. The method of claim 16 , further comprising using linear programming to determine a combination of explicit routing and destination-based routing to improve traffic load balance.

22. The method of claim 21 , wherein the linear programming is performed using CPLEX.

Assignees

• Futurewei Technologies Inc

Inventors

• Luo Min
• Zhang Junjie
• Xi Kang
• Chao Hung-Hsiang

Classifications

• H04L47/125

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

• H04L67/1023

  based on a hash applied to IP addresses or costs · CPC title

• H04W36/08

  Reselecting an access point · CPC title

• H04L12/6418 Primary

  Hybrid transport · CPC title

• H04L67/1025

  Dynamic adaptation of the criteria on which the server selection is based · CPC title