Deadlock-free traffic rerouting in software-deifned networking networks

Patent metadata

Field	Value
Publication number	US-10728140-B2
Application number	US-201715845280-A
Country	US
Kind code	B2
Filing date	Dec 18, 2017
Priority date	Dec 18, 2017
Publication date	Jul 28, 2020
Grant date	Jul 28, 2020

Abstract

Concepts and technologies disclosed herein are directed to deadlock-free traffic rerouting in software-defined networking (“SDN”) networks. According to one aspect of the concepts and technologies disclosed herein, a centralized SDN controller can determine that a packet flow along a path within at least a portion of a network is to be rerouted from the path to a new path. The centralized SDN controller can initiate a reroute of the packet flow to the new path. The centralized SDN controller can request a bandwidth for the new path. The bandwidth can be determined such that bandwidth oversubscription on the new path is avoided. In response to the packet flow settling on the new path, the centralized SDN controller can adjust a requested bandwidth of the packet flow to a desired value to complete the reroute of the packet flow from the path to the new path.

First claim

We claim:

1. A centralized software-defined networking controller comprising:
a processor;
memory having instructions stored thereon that, when executed by the processor, cause the processor to perform operations comprising
determining that at least a portion of a network is in a congested state, wherein the network comprises a plurality network nodes that, in various combinations, form a plurality of network links, each of which has a specific bandwidth capacity, wherein the congested state comprises the specific bandwidth capacity of a first portion of the plurality of network links being exceeded by a first bandwidth demand of a first path, and wherein the congested state further comprises the specific bandwidth capacity of a second portion of the plurality of network links being exceeded by a second bandwidth demand of a second path,
determining, based upon the congested state, that the first path is to be rerouted to a new first path,
determining, based upon the congested state, that the second path is to be rerouted to a new second path,
determining that the first path cannot be rerouted to the new first path and the second path cannot be rerouted to the new second path due to a deadlock condition,
initiating, due to the deadlock condition, a first reroute of the first path to the new first path by requesting a first requested bandwidth comprising a first proportionally small bandwidth of the first bandwidth demand of the first path,
completing the first reroute by adjusting the first requested bandwidth from the first proportionally small bandwidth to a first desired bandwidth,
initiating, due to the deadlock condition, a second reroute of the second path to the new second path by requesting a second requested bandwidth comprising a second proportionally small bandwidth of the second bandwidth demand of the second path, and
completing the second reroute by adjusting the second requested bandwidth from the second proportionally small bandwidth to a second desired bandwidth.

2. The centralized software-defined networking controller of claim 1 , wherein:
the network comprises a multiprotocol label switching network;
the first path comprises a first label switched path;
the second path comprises a second label switched path;
the new first path comprises a new first label switched path; and
the new second path comprises a new second label switched path.

3. The centralized software-defined networking controller of claim 1 , wherein the operations for initiating the first reroute, completing the first reroute, initiating the second reroute, and completing the second reroute are based upon at least one routing model.

4. The centralized software-defined networking controller of claim 3 , wherein initiating the first reroute, completing the first reroute, initiating the second reroute, and completing the second reroute each comprises generating commands directed to at least one route, and sending the commands to at least one router.

5. The centralized software-defined networking controller of claim 1 , wherein requesting the first proportionally small bandwidth does not cause notable traffic loss.

6. The centralized software-defined networking controller of claim 1 , wherein requesting the second proportionally small bandwidth does not cause notable traffic loss.

7. The centralized software-defined networking controller of claim 1 , wherein the first proportionally small bandwidth comprises a percentage of a total bandwidth.

8. The centralized software-defined networking controller of claim 7 , wherein the first desired bandwidth comprises the total bandwidth.

9. The centralized software-defined networking controller of claim 1 , wherein the second proportionally small bandwidth comprises a percentage of a total bandwidth.

10. The centralized software-defined networking controller of claim 9 , wherein the second desired bandwidth comprises the total bandwidth.

11. A computer-readable storage medium comprising computer-executable instructions that, when executed by a processor of a centralized software-defined networking controller, causes the centralized software-defined networking controller to perform operations comprising:
determining that at least a portion of a network is in a congested state, wherein the network comprises a plurality of network nodes that, in various combinations, form a plurality of network links, each of which has a specific bandwidth capacity, wherein the congested state comprises the specific bandwidth capacity of a first portion of the plurality of network links being exceeded by a first bandwidth demand of a first path, and wherein the congested state further comprises the specific bandwidth capacity of a second portion of the plurality of network links being exceeded by a second bandwidth demand of a second path;
determining, based upon the congested state, that the first path is to be rerouted to a new first path;
determining, based upon the congested state, that the second path is to be rerouted to a new second path;
determining that the first path cannot be rerouted to the new first path and the second path cannot be rerouted to the new second path due to a deadlock condition;
initiating, due to the deadlock condition, a first reroute of the first path to the new first path by requesting a first requested bandwidth comprising a first proportionally small bandwidth of the first bandwidth demand of the first path;
completing the first reroute by adjusting the first requested bandwidth from the first proportionally small bandwidth to a first desired bandwidth;
initiating, due to the deadlock condition, a second reroute of the second path to the new second path by requesting a second requested bandwidth comprising a second proportionally small bandwidth of the second bandwidth demand of the second path; and
completing the second reroute by adjusting the second requested bandwidth from the second proportionally small bandwidth to a second desired bandwidth.

12. The computer-readable storage medium of claim 11 , wherein:
the network comprises a multiprotocol label switching network;
the first path comprises a first label switched path;
the second path comprises a second label switched path;
the new first path comprises a new first label switched path; and
the new second path comprises a new second label switched path.

13. The computer-readable storage medium of claim 11 , wherein the operations for initiating the first reroute, completing the first reroute, initiating the second reroute, and completing the second reroute are based upon at least one routing model.

14. The computer-readable storage medium of claim 11 , wherein:
the first proportionally small bandwidth comprises a percentage of a total bandwidth;
the first desired bandwidth comprises the total bandwidth.

15. The computer-readable storage medium of claim 11 , wherein:
the second proportionally small bandwidth comprises a percentage of a total bandwidth;
the second desired bandwidth comprises the total bandwidth.

16. A method comprising:
determining, by a centralized software-defined networking controller comprising a processor, that at least a portion of a network is in a congested state, wherein the network comprises a plurality of network nodes that, in various combinations, form a plurality of network links, each of which has a specific bandwidth capacity, wherein the congested state comprises the specific bandwidth capacity of a first portion of the plurality of network links being exceeded by a first bandwidth demand of a first path, and wherein the congested state

Assignees

• At & T Ip I Lp

Inventors

• Choudhury Gagan
• Xi Kang
• Tse Simon
• Padi Narayan
• Goddard Alvin
• Raghuram Aswatnarayan

Classifications

• H04L41/0896

  Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities (flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76) · CPC title

• H04L45/22

  Alternate routing · CPC title

• H04L45/64

  using an overlay routing layer · CPC title

• H04L45/28

  using route fault recovery · CPC title

• H04L45/42

  Centralised routing · CPC title