POINT-TO-MULTIPOINT PATH COMPUTATION FOR WIDE AREA NETWORK OPTIMIZATION

• US 20170317780A1
• Filed: 07/14/2017
• Published: 11/02/2017
• Est. Priority Date: 12/29/2014
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Wood, David C., Wang, Ping
• Granted Patent: US 10,374,747 B2
• Time in Patent Office: Days
• CPC Class Codes: H04B 10/27 Arrangements for networking
• CPC Class Codes: H04J 14/0267 Optical signaling or routing
• CPC Class Codes: H04J 14/0286 WDM hierarchical architectures
• CPC Class Codes: H04J 2203/0055 Network design, dimensioning, topology or optimisation
• CPC Class Codes: H04J 2203/0098 Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
• CPC Class Codes: H04L 41/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 Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/14 Network analysis or design
• CPC Class Codes: H04L 41/149 for prediction of maintenance
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

In some examples, a controller for a network includes a path computation module configured for execution by one or more processors to obtain configuration information for at least one point-to-multipoint label switched path (P2MP LSP); obtain, from the network via at least one protocol, network topology information defining a network topology for the network; determine, based on the network topology, a first solution comprising first respective paths through the network for the at least one P2MP LSP; determine, after generating a modified network topology based on the network topology, a second solution comprising second respective paths through the network for the at least one P2MP LSP. The controller also includes a path provisioning module configured for execution by the one or more processors to configure the network with the solution of the first solution and the second solution having the lowest total cost.

Claims

1. A method comprising:

obtaining, by a controller of a network, configuration information for a point-to-multipoint label switched path (P2MP LSP);

obtaining, by the controller from the network via at least one protocol, network topology information defining a network topology for the network;

determining, by the controller based on the network topology, a first solution comprising at least one path through the network for the P2MP LSP;

computing, by the controller in response to determining the at least one path has a failure to satisfy a constraint for the P2MP LSP, a penalty for the first solution that is based on a magnitude of the failure, wherein a total cost for the first solution includes the penalty for the first solution;

determining, by the controller after generating a modified network topology based on the network topology, a second solution comprising at least one path through the network for the P2MP LSP; and

outputting, by the controller for configuring the network, topology data for the solution of the first solution and the second solution having a lowest total cost, the lowest total cost of the solution including a total resource cost to the network for the solution.

2. The method of claim 1, wherein the constraint comprises a maximum number of next hops.

3. The method of claim 2, wherein the magnitude of the failure corresponds to a difference between the maximum number of next hops and a number of next hops of a path of the at least one path through the network for the P2MP LSP.

4. The method of claim 1, wherein the constraint comprises a maximum number of overlaps.

5. The method of claim 4, wherein the magnitude of the failure corresponds to a difference between the maximum number of overlaps and a number of overlaps between a first path of the at least one path through the network for the P2MP LSP and a second path of the at least one path through the network for the P2MP LSP.

6. The method of claim 1, wherein the magnitude of the failure corresponds to a number of routing loops of the at least one path through the network for the P2MP LSP.

7. The method of claim 1, further comprising:

obtaining, by the controller from the network via the at least one protocol, updated network topology information defining an updated network topology for the network;

determining, by the controller based on the updated network topology and in response to obtaining the updated network topology information, a new first solution comprising a new at least one path through the network for the P2MP LSP;

determining, by the controller after generating an updated modified network topology based at least on the updated network topology, a new second solution comprising a new at least one path through the network for the P2MP LSP; and

outputting, by the controller for configuring the network, topology data for the solution of the new first solution and the new second solution having the lowest total cost.

8. The method of claim 1,

wherein generating a modified network topology comprises one of blocking, by the controller, a link of a plurality of links in the network topology by applying a link penalty to a metric for the link and unblocking, by the controller, the link by removing the link penalty to the metric for the link, and

wherein determining the second solution comprising at least one path through the network for the P2MP LSP comprises determining the second solution based at least in part on blocking or unblocking the link.

9. The method of claim 1, further comprising:

determining, by the controller, a magnitude of a total cost increase for the second solution from the first solution; and

determining, by the controller, a result of a simulated annealing function based on the magnitude of the total cost increase and a temperature parameter.

10. The method of claim 1,

iteratively determining, by the controller for a number of iterations, additional solutions comprising paths through the network for the P2MP LSP,

wherein outputting topology data for the solution of the first solution and the second solution having the lowest total cost comprises outputting, by the controller for configuring the network, topology data for the solution of the first solution, the second solution, and the additional solutions having the lowest total cost.

11. A controller for a network, the controller comprising one or more processors coupled to a memory, configured to:

obtain configuration information for a point-to-multipoint label switched path (P2MP LSP);

obtain, from the network via at least one protocol, network topology information defining a network topology for the network;

determine, based on the network topology, a first solution comprising at least one path through the network for the P2MP LSP;

compute, in response to a determination the at least one path has a failure to satisfy a constraint for the P2MP LSP, a penalty for the first solution that is based on a magnitude of the failure, wherein a total cost for the first solution includes the penalty for the first solution;

determine, after generation of a modified network topology based on the network topology, a second solution comprising at least one path through the network for the P2MP LSP; and

output, for configuring the network, topology data for the solution of the first solution and the second solution having a lowest total cost, the lowest total cost of the solution including a total resource cost to the network for the solution.

12. The controller of claim 11, wherein the constraint comprises a maximum number of next hops.

13. The controller of claim 12, wherein the magnitude of the failure corresponds to a difference between the maximum number of next hops and a number of next hops of a path of the at least one path through the network for the P2MP LSP.

14. The controller of claim 11, wherein the constraint comprises a maximum number of overlaps.

15. The controller of claim 14, the magnitude of the failure corresponds to a difference between the maximum number of overlaps and a number of overlaps between a first path of the at least one path through the network for the P2MP LSP and a second path of the at least one path through the network for the P2MP LSP.

16. The controller of claim 11, wherein the magnitude of the failure corresponds to a number of routing loops of the at least one path through the network for the P2MP LSP.

17. The controller of claim 11, further configured to:

obtain, from the network via the at least one protocol, updated network topology information defining an updated network topology for the network;

determine, based on the updated network topology and in response to obtainment of the updated network topology information, a new first solution comprising a new at least one path through the network for the P2MP LSP;

determine, after generation of an updated modified network topology based at least on the updated network topology, a new second solution comprising a new at least one path through the network for the P2MP LSP; and

output, for configuring the network, topology data for the solution of the new first solution and the new second solution having the lowest total cost.

18. The controller of claim 11,

wherein generation of the modified network topology comprises one of blocking a link of a plurality of links in the network topology by applying a link penalty to a metric for the link and unblocking the link by removing the link penalty to the metric for the link, and

wherein determination of the second solution comprising at least one path through the network for the P2MP LSP comprises determination of the second solution based at least in part on blocking or unblocking the link.

19. The controller of claim 11, further configured to:

determine a magnitude of a total cost increase for the second solution from the first solution; and

determine a result of a simulated annealing function based on the magnitude of the total cost increase and a temperature parameter.

20. A non-transitory computer-readable medium comprising instructions that, when executed by one or more programmable processors of a controller of a network, cause the one or more programmable processors of the controller to:

obtain configuration information for a point-to-multipoint label switched path (P2MP LSP);

obtain, from the network via at least one protocol, network topology information defining a network topology for the network;

determine, based on the network topology, a first solution comprising at least one path through the network for the P2MP LSP;

compute, in response to a determination the at least one path has a failure to satisfy a constraint for the P2MP LSP, a penalty for the first solution that is based on a magnitude of the failure, wherein a total cost for the first solution includes the penalty for the first solution;

determine, after generation of a modified network topology based on the network topology, a second solution comprising at least one path through the network for the P2MP LSP; and

output, for configuring the network, topology data for the solution of the first solution and the second solution having a lowest total cost, the lowest total cost of the solution including a total resource cost to the network for the solution.