Techniques for end-to-end network bandwidth optimization using software defined networking

• US 9,705,783 B2
• Filed: 07/22/2015
• Issued: 07/11/2017
• Est. Priority Date: 06/07/2013
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Inventors: Shaikh, Mukhtiar, Vobbilisetty, Suresh, Jogalekar, Prasad, Krishnan, Ram, Durrani, Muhammad
• Primary Examiner(s): Duong, Frank
• Application Number:
  US14/805,901
• Publication Number:
  US 20150334002A1
• Time in Patent Office: 720 Days
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion

Abstract

Techniques for end-to-end network bandwidth optimization using software defined networking are provided. In one embodiment, a computer system can receive information regarding a flow to be admitted to a network, where the flow is associated with a source and a destination. The computer system can further calculate, for each path in a plurality of paths between the source and the destination, a projected utilization of the path in view of the flow. If the projected utilization of the shortest path in the plurality of paths is less than or equal to a target utilization threshold, the computer system can assign the flow to the shortest path. Otherwise, the computer system can select a path in the plurality of paths that comes closest to the target utilization threshold without exceeding the threshold and can assign the flow to that selected path.

Claims

1. A method comprising:

receiving, by a computer system, information regarding a flow to be admitted to a network, the flow being associated with a source and a destination;

for a shortest path in a plurality of paths between the source and the destination, calculating, by the computer system, a projected utilization of the shortest path in view of the flow;

if the projected utilization of the shortest path is less than or equal to a target utilization threshold, assigning, by the computer system, the flow to the shortest path;

else if the projected utilization of the shortest path is greater than the target utilization threshold;

selecting, by the computer system, another path in the plurality of paths distinct from the shortest path based on one or more selection criteria; and

assigning, by the computer system, the flow to the selected path.

2. The method of claim 1 wherein selecting another path in the plurality of paths distinct from the shortest path based on one or more selection criteria comprises:

selecting a next shortest path in the plurality of paths whose projected utilization in view of the flow is less than or equal to the target utilization threshold.

3. The method of claim 1 wherein selecting another path in the plurality of paths distinct from the shortest path based on one or more selection criteria comprises:

selecting a path in the plurality of paths whose projected utilization in view of the flow comes closest to the target utilization threshold.

4. The method of claim 1 wherein selecting another path in the plurality of paths distinct from the shortest path based on one or more selection criteria comprises:

selecting, at random, a path in the plurality of paths whose projected utilization in view of the flow is less than or equal to the target utilization threshold.

5. The method of claim 1 wherein the flow belongs to a class of service (CoS), and

wherein selecting another path in the plurality of paths distinct from the shortest paths based on one or more selection criteria comprises selecting path in the plurality of paths that is defined for the CoS.

6. The method of claim 1 wherein the flow is associated with a service level agreement (SLA) comprising one or more service requirements, and

wherein the method further comprises verifying whether the selected path meets the one or more service requirements.

7. The method of claim 6 wherein the one or more service requirements include a maximum allowable latency for the flow.

8. The method of claim 1 wherein the projected utilization of the shortest path is based on:

a current utilization percentage of a most utilized link in the shortest path; and

an estimated percentage of the most utilized link that would be consumed by the flow.

9. The method of claim 8 wherein the current utilization percentage of the most utilized link corresponds to an average utilization percentage over a recent time window.

10. The method of claim 1 further comprising, prior to the receiving:

determining topology information and one or more policies for the network; and

computing the plurality of paths using the topology information and the one or more policies.

11. The method of claim 10 wherein the plurality of paths comprise a preconfigured number of shortest paths between the source and the destination.

12. The method of claim 11 wherein the preconfigured number is defined by one of the one or more policies.

13. The method of claim 11 wherein no two paths in the plurality of paths include a common link.

14. The method of claim 1 further comprising:

tracking utilization of the path assigned to the flow; and

if the utilization rises above a reallocation threshold, repeating the steps of claim 1 in order to reassign the flow to a different path in the plurality of paths.

15. The method of claim 14 wherein the utilization of the path is determined based on utilization of a most utilized link in the path.

16. The method of claim 1 wherein the computer system is a software defined networking (SDN) controller device.

17. A non-transitory computer readable medium having stored thereon program code executable by a processor, the program code comprising:

code that causes the processor to receive information regarding a flow to be admitted to a network, the flow being associated with a source and a destination;

for a shortest path in a plurality of paths between the source and the destination, code that causes the processor to calculate a projected utilization of the shortest path in view of the flow;

if the projected utilization of the shortest path is less than or equal to a target utilization threshold, code that causes the processor to assign the flow to the shortest path;

else if the projected utilization of the shortest path is greater than the target utilization threshold;

code that causes the processor to select another path in the plurality of paths distinct from the shortest path based on one or more selection criteria; and

code that causes the processor to assign the flow to the selected path.

18. A computer system comprising:

a processor; and

a non-transitory computer readable medium having stored thereon executable program code which, when executed by the processor, causes the processor to;

receive information regarding a flow to be admitted to a network, the flow being associated with a source and a destination;

for a shortest path in a plurality of paths between the source and the destination, calculate a projected utilization of the shortest path in view of the flow;

if the projected utilization of the shortest path is less than or equal to a target utilization threshold, assign the flow to the shortest path;

else if the projected utilization of the shortest path is greater than the target utilization threshold;

select another path in the plurality of paths distinct from the shortest path based on one or more selection criteria; and

assign the flow to the selected path.