Point-to-multipoint path computation for wide area network optimization

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 of the first solution 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,
• 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;
• 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.

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 of the first solution 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, and wherein the constraint comprises one of a maximum number of next hops or a maximum number of overlaps;
• 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.

A controller for a network, the controller comprising one or more processors coupled to a memory, the controller 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 of the first solution 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,
• 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;
• 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.

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 of the first solution 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, and wherein the constraint comprises one of a maximum number of next hops or a maximum number of overlaps;
• 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.