Apparatus for hybrid routing in SDN networks to avoid congestion and achieve good load balancing under fluctuating traffic load

Patent metadata

Field	Value
Publication number	US-9503374-B2
Application number	US-201414161496-A
Country	US
Kind code	B2
Filing date	Jan 22, 2014
Priority date	Jan 22, 2014
Publication date	Nov 22, 2016
Grant date	Nov 22, 2016

Abstract

A controller having an application optimally routing traffic to balance fluctuating traffic loads in a SDN network. A processor is configured to control the data plane to establish routing through the plurality of routers, wherein the processor is configured to establish hybrid routing comprising both explicit routing and destination-based routing. The processor utilizes a set of traffic matrices representing the fluctuating traffic load over time. A destination-based multi-path routing algorithm is configured to improve load balancing of the traffic load based on the set of representative traffic matrices. The destination based routing is calculated based on linear programming. The processor comprises a traffic categorization algorithm configured to identify a set of key flows, wherein the processor is configured to explicitly route the set of key flows. The processor is configured such that the set of key flows consume a small fraction of a ternary content-addressable memory (TCAM), and such that the set of key flows provide a routing decision for a large portion of the traffic load.

First claim

What is claimed is:

1. A controller in a software-defined networking (SDN) network having a data plane including a plurality of routers, the controller comprising:
a non-transitory memory storage comprising instructions; and
one or more processors in communication with the memory, wherein the one or more processors execute the instructions to:
control the data plane to establish routing through the plurality of routers,
establish hybrid routing comprising explicit routing and destination-based routing to balance a traffic load in the SDN network during a fluctuating load,
perform a traffic categorization algorithm configured to identify a set of key flows, and
explicitly route the set of key flows, wherein

a number of entries in a ternary content-addressable memory (TCAM) for the hybrid routing is less than half of a number of entries required in the TCAM for optimal explicit routing only.

2. The controller as specified in claim 1 , wherein the one or more processors further executes the instructions to utilize a set of representative traffic matrices representing fluctuating traffic load over time.

3. The controller as specified in claim 2 , wherein the set of representative traffic matrices are based on historical traffic measurement data.

4. The controller as specified in claim 2 , wherein the memory includes a destination-based multi-path routing algorithm executable by the one or more processors to improve load balancing of the traffic load based on the set of representative traffic matrices.

5. The controller as specified in claim 1 , wherein the destination based routing is calculated based on linear programming.

6. The controller as specified in claim 1 , wherein the one or more processors further execute the instructions to combine the destination-based routing and the explicit routing in a complementary way to establish the hybrid routing.

7. The controller as specified in claim 1 , wherein the one or more processors are used in static network planning and dynamic routing.

8. A method of establishing routing in a software-defined networking (SDN) network having a data plane including a plurality of routers, comprising:
controlling, by a processor, the data plane to establish routing through the plurality of routers by
establishing hybrid routing comprising explicit routing and destination-based routing to balance a traffic load in the SDN network during a fluctuating load, wherein
the hybrid routing comprises a traffic categorization algorithm identifying a set of key flows,
the processor explicitly routes the set of key flows, and
a number of entries in a ternary content-addressable memory (TCAM) for the hybrid routing is less than half of a number of entries required in the TCAM for optimal explicit routing only.

9. The method as specified in claim 8 , wherein controlling the data plane further comprises utilizing a set of representative traffic matrices representing fluctuating traffic load over time.

10. The method as specified in claim 9 , wherein the set of representative traffic matrices are based on historical traffic measurement data.

11. The method as specified in claim 9 , wherein the hybrid routing includes a destination-based multi-path routing algorithm improving load balancing of the traffic load based on the set of representative traffic matrices.

12. The method as specified in claim 8 , wherein the destination based routing is calculated based on linear programming.

13. The method as specified in claim 8 , wherein the processor combines the destination-based routing and the explicit routing in a complementary way to establish the hybrid routing.

14. The method as specified in claim 8 , wherein the processor is used in static network planning and dynamic routing.

15. A non-transitory computer-readable medium storing computer instructions for establishing routing in a software-defined (SDN) network having a data plane including a plurality of routers that when executed by one or more processors, cause the one or more processors to perform the steps of:
controlling, by a processor, the data plane to establish routing through the plurality of routers by establishing hybrid routing comprising explicit routing and destination-based routing to balance a traffic load in the SDN network during a fluctuating load, wherein
the hybrid routing comprises a traffic categorization algorithm identifying a set of key flows,
the processor explicitly routes the set of key flows, and
a number of entries in a ternary content-addressable memory (TCAM) for the hybrid routing is less than half of a number of entries required in the TCAM for optimal explicit routing only.

16. The non-transitory computer-readable medium as specified in claim 15 , wherein controlling the data plane further comprises utilizing a set of representative traffic matrices representing fluctuating traffic load over time.

17. The non-transitory computer-readable medium as specified in claim 16 , wherein the set of representative traffic matrices are based on historical traffic measurement data.

18. The non-transitory computer-readable medium as specified in claim 16 , wherein the hybrid routing includes a destination-based multi-path routing algorithm improving load balancing of the traffic load based on the set of representative traffic matrices.

19. The non-transitory computer-readable medium as specified in claim 15 , wherein the destination based routing is calculated based on linear programming.

20. The non-transitory computer-readable medium as specified in claim 15 , wherein the processor combines the destination-based routing and the explicit routing in a complementary way to establish the hybrid routing.

Assignees

• Futurewei Technologies Inc
• Futurewei Technologies Inc

Inventors

• Luo Min
• Chao H Jonathan
• Chou Wu
• Zhang Junjie
• Xi Kang

Classifications

• H04L45/7457 Primary

  Electricity · mapped topic

• H04L45/52 Primary

  Multiprotocol routers · CPC title

• H04L45/74591 Primary

  using content-addressable memories [CAM] · CPC title