Rerouting tunnel traffic in communication networks

• US 10,425,326 B2
• Filed: 04/23/2018
• Issued: 09/24/2019
• Est. Priority Date: 10/07/2014
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Klincewicz, John Gregory, Choudhury, Gagan, Meier-Hellstern, Kathleen S.
• Primary Examiner(s): Murphy, Rhonda L
• Application Number:
  US15/960,147
• Publication Number:
  US 20180241663A1
• Time in Patent Office: 519 Days
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 47/41 by acting on aggregated flows or links

Abstract

Methods, apparatus, systems and articles of manufacture (e.g., physical storage media) to reroute tunnel traffic in a network are disclosed. Example methods disclosed herein include, in response to detecting an event associated with routing first traffic in the network, determining a plurality of paths to carry respective traffic for a plurality of tunnels between pairs of routers in the network, the plurality of paths being determined based on a quality metric characterizing an aggregate tunnel bandwidth to be carried by the plurality of paths for the plurality of tunnels. Such disclosed example methods also include sending first routing information describing the plurality of paths to the routers in the network to cause the routers to route the respective traffic for the plurality of tunnels using the plurality of paths.

Claims

1. A re-routing method for routers in a network, the re-routing method comprising:

in response to detecting an event associated with routing traffic in the network, determining, by executing an instruction with a processor separate from the routers, a plurality of unique orderings of a plurality of tunnels, respective tunnels included in the plurality of tunnels corresponding to pairs of routers, at least one of the pairs of routers corresponding to more than one of the plurality of tunnels, and at least one of the pairs of routers to communicate via one or more intervening routers;

for respective ones of the plurality of unique orderings, assigning, by executing an instruction with the processor, communication paths to carry respective traffic for the respective tunnels, the communication paths assigned to the respective tunnels in respective sequences specified in respective ones of the plurality of unique orderings; and

when an overall quality metric determined using the communication paths assigned to the respective tunnels in a first sequence specified by a first unique ordering of the plurality of unique orderings satisfies a threshold, causing first routing information describing the communication paths assigned for the first unique ordering of the plurality of unique orderings to be sent to the routers to route the traffic.

2. The re-routing method of claim 1, wherein the overall quality metric corresponds to a total amount of bandwidth supported by the communication paths assigned to the respective tunnels in the first sequence specified by the first unique ordering of the plurality of unique orderings.

3. The re-routing method of claim 1, wherein the assigning of the communication paths to carry the respective traffic for the respective tunnels, includes:

determining whether a first candidate communication path capable of supporting a first tunnel size associated with a first one of the plurality of tunnels is available in the network; and

in response to determining the first candidate communication path is available;

setting a routed bandwidth value for the first one of the plurality of tunnels equal to the first tunnel size; and

decreasing available link capacities of a first set of network links included in the first candidate communication path by the first tunnel size.

4. The re-routing method of claim 3, further including, in response to determining that the first candidate communication path is not available:

determining whether a second candidate communication path capable of supporting a portion of the first tunnel size associated with the first one of the plurality of tunnels is available in the network; and

in response to determining the second candidate communication path is available;

setting the routed bandwidth value for the first one of the plurality of tunnels equal to the portion of the first tunnel size; and

decreasing available link capacities of a second set of network links included in the second candidate communication path by the portion of the first tunnel size.

5. The re-routing method of claim 1, wherein the overall quality metric characterizes an aggregate tunnel bandwidth in the network.

6. The re-routing method of claim 1, wherein the assigning of the communication paths to carry the respective traffic for the respective tunnels includes determining a remaining amount of link capacities of a set of network links included in the communication paths.

7. A tangible machine readable storage medium comprising instructions that, when executed, cause a processor to perform operations including:

in response to detecting an event associated with routing traffic in a network, determining a plurality of unique orderings of a plurality of tunnels, respective tunnels of the plurality of tunnels corresponding to pairs of routers in the network, at least one of the pairs of routers corresponding to more than one of the plurality of tunnels, and at least one of the pairs of routers to communicate via one or more intervening routers;

for respective ones of the plurality of unique orderings, assigning communication paths to carry respective traffic for the respective tunnels, the communication paths assigned to the respective tunnels in respective sequences specified in respective ones of the plurality of unique orderings; and

when an overall quality metric determined using the communication paths assigned to the respective tunnels in a first sequence specified by a first unique ordering of the plurality of unique orderings satisfies a threshold, causing first routing information describing the communication paths assigned for the first unique ordering of the plurality of unique orderings to be sent to the routers in the network to route the traffic.

8. The tangible machine readable storage medium of claim 7, wherein the overall quality metric corresponds to a total amount of bandwidth supported by the communication paths assigned to the respective tunnels in the first sequence specified by the first unique ordering of the plurality of unique orderings.

9. The tangible machine readable storage medium of claim 7, wherein the assigning of the communication paths to carry respective traffic for the respective tunnels includes:

determining whether a first candidate communication path capable of supporting a first tunnel size associated with a first one of the plurality of tunnels is available in the network; and

in response to determining the first candidate communication path is available;

setting a routed bandwidth value for the first one of the plurality of tunnels equal to the first tunnel size; and

decreasing available link capacities of a first set of network links included in the first candidate communication path by the first tunnel size.

10. The tangible machine readable storage medium of claim 9, wherein the operations further include:

in response to determining that the first candidate communication path is not available determining whether a second candidate communication path capable of supporting a portion of the first tunnel size associated with the first one of the plurality of tunnels is available in the network;

in response to determining the second candidate communication path is available;

setting the routed bandwidth value for the first one of the plurality of tunnels equal to the portion of the first tunnel size; and

decreasing available link capacities of a second set of network links included in the second candidate communication path by the portion of the first tunnel size.

11. The tangible machine readable storage medium of claim 7, wherein the respective tunnels of the plurality of tunnels have respective target tunnel sizes.

12. The tangible machine readable storage medium of claim 7, wherein the assigning of the communication paths to carry the respective traffic for the respective tunnels includes determining a remaining amount of link capacities of a set of network links included in the communication paths.

13. The tangible machine readable storage medium of claim 7, wherein the overall quality metric characterizes an aggregate tunnel bandwidth in the network.

14. A controller to re-route tunnel traffic for routers in a network, the controller separate from the routers, the controller comprising:

memory including machine readable instructions; and

a processor to execute the machine readable instructions to perform operations including;

in response to detecting an event associated with routing traffic in the network, determining a plurality of unique orderings of a plurality of tunnels, respective tunnels of the plurality of tunnels corresponding to pairs of routers in the network, at least one of the pairs of routers corresponding to more than one of the plurality of tunnels, and at least one of the pairs of routers coupled via one or more intervening routers;

for respective ones of the plurality of unique orderings, assigning communication paths to carry respective traffic for the respective tunnels, the communication paths assigned to the respective tunnels in respective sequences specified in respective ones of the plurality of unique orderings; and

when an overall quality metric determined using the communication paths assigned to the respective tunnels in a first sequence specified by a first unique ordering of the plurality of unique orderings satisfies a threshold, sending first routing information describing the communication paths assigned for the first unique ordering of the plurality of unique orderings to the routers in the network for routing the traffic.

15. The controller of claim 14, wherein the overall quality metric corresponds to a total amount of bandwidth supported by the communication paths assigned to the respective tunnels in the first sequence specified by the first unique ordering of the plurality of unique orderings.

16. The controller of claim 14, wherein the assigning of the communication paths to carry the respective traffic for the respective tunnels includes:

determining whether a first candidate communication path capable of supporting a first tunnel size associated with a first one of the plurality of tunnels is available in the network; and

in response to determining the first candidate communication path is available;

setting a routed bandwidth value for the first one of the plurality of tunnels equal to the first tunnel size; and

decreasing available link capacities of a first set of network links included in the first candidate communication path by the first tunnel size.

17. The controller of claim 16, wherein the operations further include:

in response to determining that the first candidate communication path is not available, determining whether a second candidate communication path capable of supporting a portion of the first tunnel size associated with the first one of the plurality of tunnels is available in the network;

in response to determining the second candidate communication path is available;

setting the routed bandwidth value for the first one of the plurality of tunnels equal to the portion of the first tunnel size; and

decreasing available link capacities of a second set of network links included in the second candidate communication path by the portion of the first tunnel size.

18. The controller of claim 14, wherein the respective tunnels of the plurality of tunnels have respective target tunnel sizes.

19. The controller of claim 14, wherein the assigning of the communication paths to carry the respective traffic for the respective tunnels includes determining a remaining amount of link capacities of a set of network links included in the communication paths.

20. The controller of claim 14, wherein the overall quality metric characterizes an aggregate tunnel bandwidth in the network.