NETWORK TOPOLOGY OPTIMIZATION WITH FEASIBLE OPTICAL PATHS

• US 20160191194A1
• Filed: 06/30/2015
• Published: 06/30/2016
• Est. Priority Date: 12/29/2014
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Salsi, Massimiliano, Alleston, Steven B., Wood, David C.
• Granted Patent: US 9,780,909 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 general, techniques are described for dynamically determining a logical network topology for more efficiently transporting network traffic over a physical topology based on end-to-end network traffic demands and optical transport network (OTN) characteristics of the network. The techniques may be applicable to meeting network traffic demands placed upon a multi-layer network having a base transport layer and a logical or overlay Internet Protocol (IP) layer routed on the transport layer.

Claims

1. A method comprising:

obtaining, by a management device of a multi-layer network comprising a network layer and an underlying transport layer, a plurality of candidate links, wherein each candidate link of the plurality of candidate links is associated with an optical path in the transport layer;

determining, by the management device based at least on optical network data that describes optical characteristics of fibre links of the transport layer, each candidate link of the plurality of candidate links that has a feasible optical path;

determining, by the management device, a plurality of filtered candidate links comprising each candidate link determined to have a feasible optical path;

determining, by the management device, a first solution comprising a network topology for the network layer that includes a first selected subset of the filtered candidate links;

determining, by the management device after generating a modified network topology based at least on the network topology, a second solution comprising the modified network topology for the network layer that includes a second selected subset of the filtered candidate links; and

outputting, by the management device, topology data for one of the first solution or the second solution having a lowest total cost, the lowest total cost including a total resource cost to the network for the one of the first solution or the second solution.

2. The method of claim 1, further comprising:

obtaining, by the management device, abstract link data describing at least one of the plurality of filtered candidate links,

where determining the first solution comprises determining, by the management device based on the abstract link data, the network topology for the network layer that includes the first selected subset of the filtered candidate links.

3. The method of claim 2,

wherein the abstract link data indicates at least one Shared Risk Link Group for the at least one of the plurality of filtered candidate links,

wherein determining the second solution comprises determining, by the management device based at least on the network topology and the at least one Shared Risk Link Group for the at least one of the plurality of filtered candidate links, the second solution by applying a penalty cost to a first filtered candidate link and a second filtered candidate link of the second subset of the plurality of filtered candidate links, and

wherein the lowest total cost of the second solution includes the penalty cost.

4. The method of claim 2, wherein obtaining abstract link data comprises receiving, by the management device, an abstract link data structure for the transport layer, the abstract link data structure including the abstract link data.

5. The method of claim 4, wherein receiving the abstract link data structure comprises receiving, by the management device from a network management system that manages a transport network that implements the transport layer, the abstract link data structure.

6. The method of claim 1, further comprising:

routing, by the management device, a plurality of traffic demands to the network topology, each traffic demand of the plurality of traffic demands representing an end-to-end traffic flow for the network layer.

7. The method of claim 6, further comprising:

determining, by the management device, the first selected subset of the filtered candidate links by selecting filtered candidate links on which the management device has routed a traffic demand of the plurality of traffic demands.

8. The method of claim 1, wherein the modified network topology comprises a first modified network topology, the method further comprising:

determining, by the management device after generating a second modified network topology based on the first modified network topology and in response to determining that the second solution has a lower total cost than the first solution, a third solution comprising the second modified network topology for the network layer that includes a third selected subset of the filtered candidate links; and

determining, by the management device after generating a third modified network topology based on the network topology in response to determining that the second solution has a higher total cost than the first solution, a fourth solution comprising the third modified network topology for the network layer that includes a third selected subset of the filtered candidate links.

9. The method of claim 1, further comprising:

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

determining, by the management device, 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 9, further comprising:

setting, by the management device, the temperature parameter according to a target probability for the simulated annealing function, the target probability being a probability that a total cost for the second solution from the first solution increases.

11. The method of claim 1, wherein the modified network topology comprises a first modified network topology, the method further comprising:

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

determining, by the management device, a result of a simulated annealing function based on the magnitude of the total cost increase and a temperature parameter;

determining, by the management device after generating a second modified network topology based on the first modified network topology and in response to determining that the second solution has a lower total cost than the first solution and only if the result of the simulated annealing function is positive, a third solution comprising the second modified network topology for the network layer that includes a third selected subset of the filtered candidate links; and

determining, by the management device after generating a third modified network topology based on the network topology in response to determining that the second solution has a higher total cost than the first solution and only if the result of the simulated annealing function is negative, a fourth solution comprising the third modified network topology for the network layer that includes a third selected subset of the filtered candidate links.

12. The method of claim 1, further comprising:

routing, by the management device, a plurality of traffic demands to the network topology, each traffic demand of the plurality of traffic demands representing an end-to-end traffic flow mapped to a label-switched path for the network layer.

13. The method of claim 1, wherein determining whether a candidate link of the plurality of candidate links has a feasible optical path comprises:

determining an impairment to an optical path for the candidate link;

determining, in response to determining an optical node that terminates the optical path includes an optical receiver that is available and able to tolerate the impairment, the candidate link has a feasible optical path; and

determining, in response to determining an optical node that terminates the optical path does not include an optical receiver that is available and able to tolerate the impairment, the candidate link does not have a feasible optical path.

14. The method of claim 13, wherein the impairment comprises at least one of polarization mode dispersion, polarization dependent loss, and chromatic dispersion.

15. The method of claim 1, wherein determining whether a candidate link of the plurality of candidate links has a feasible optical path comprises:

determining an aggregate optical signal-to-noise ratio (OSNR) for an optical path for the candidate link;

determining, in response to determining an optical node that terminates the optical path includes an optical receiver that is available and able to receive an optical signal having the aggregate OSNR, the candidate link has a feasible optical path; and

determining, in response to determining an optical node that terminates the optical path does not include an optical receiver that is available and able to receive an optical signal having the aggregate OSNR, the candidate link does not have a feasible optical path.

16. The method of claim 1, further comprising:

determining, by the management device, one or more optical paths in the transport layer to underlie a network link that connects a pair of routers in the network layer; and

generating, by the management device, candidate links of the plurality of candidate links that are each defined at least in part by an optical path of the one or more optical paths and the pair of routers.

17. A management device for a multi-layer network comprising a network layer and an underlying transport layer, the management device comprising:

one or more processors coupled to a memory; and

a topology computation module configured for execution by the one or more processors to;

obtain a plurality of candidate links, wherein each candidate link of the plurality of candidate links is associated with an optical path in the transport layer;

determine, based at least on optical network data that describes optical characteristics of fibre links of the transport layer, each candidate link of the plurality of candidate links that has a feasible optical path;

determine a plurality of filtered candidate links comprising each candidate link determined to have a feasible optical path;

determine a first solution comprising a network topology for the network layer that includes a first selected subset of the filtered candidate links; and

determine, after generating a modified network topology based at least on the network topology, a second solution comprising the modified network topology for the network layer that includes a second selected subset of the filtered candidate links,

wherein the one or more processors are configured to output, for configuring the multi-layer network, topology data for one of the first solution or the second solution having a lowest total cost, the lowest total cost including a total resource cost to the network for the one of the first solution or the second solution.

18. The management device of claim 17,

wherein the topology computation module is further configured to obtain abstract link data describing at least one of the plurality of filtered candidate links, and

wherein to determine the first solution the topology computation module is further configured to determine, based on the abstract link data, the network topology for the network layer that includes the first selected subset of the filtered candidate links.

19. The management device of claim 18,

wherein the abstract link data indicates at least one Shared Risk Link Group for the at least one of the plurality of filtered candidate links,

wherein to determine the second solution the topology computation module is further configured to determine, based at least on the network topology and the at least one Shared Risk Link Group for the at least one of the plurality of filtered candidate links, the second solution by applying a penalty cost to a first filtered candidate link and a second filtered candidate link of the second subset of the plurality of filtered candidate links, and

wherein the lowest total cost of the second solution includes the penalty cost.

20. The management device of claim 18, wherein to obtain abstract link data the topology computation module is further configured to receive an abstract link data structure for the transport layer, the abstract link data structure including the abstract link data.

21. The management device of claim 20, wherein to receive the abstract link data structure the topology computation module is further configured to receive, from a network management system that manages a transport network that implements the transport layer, the abstract link data structure.

22. The management device of claim 17,

wherein the topology computation module is further configured to route a plurality of traffic demands to the network topology, each traffic demand of the plurality of traffic demands representing an end-to-end traffic flow for the network layer.

23. The management device of claim 22,

wherein the topology computation module is further configured to determine the first selected subset of the filtered candidate links by selecting filtered candidate links on which the management device has routed a traffic demand of the plurality of traffic demands.

24. The management device of claim 17,

wherein the modified network topology comprises a first modified network topology,

wherein the topology computation module is further configured to determine, after generating a second modified network topology based on the first modified network topology and in response to determining that the second solution has a lower total cost than the first solution, a third solution comprising the second modified network topology for the network layer that includes a third selected subset of the filtered candidate links, and

wherein the topology computation module is further configured to determine, after generating a third modified network topology based on the network topology in response to determining that the second solution has a higher total cost than the first solution, a fourth solution comprising the third modified network topology for the network layer that includes a third selected subset of the filtered candidate links.

25. The management device of claim 17,

wherein the topology computation module is further configured to determine a magnitude of a total cost increase for the second solution from the first solution, and

wherein the topology computation module is further configured to determine a result of a simulated annealing function based on the magnitude of the total cost increase and a temperature parameter.

26. The management device of claim 25,

wherein the topology computation module is further configured to set the temperature parameter according to a target probability for the simulated annealing function, the target probability being a probability that a total cost for the second solution from the first solution increases.

27. The management device of claim 17,

wherein the modified network topology comprises a first modified network topology,

wherein the topology computation module is further configured to determine a magnitude of a total cost increase for the second solution from the first solution,

wherein the topology computation module is further configured to determine a result of a simulated annealing function based on the magnitude of the total cost increase and a temperature parameter,

wherein the topology computation module is further configured to determine, after generating a second modified network topology based on the first modified network topology and in response to determining that the second solution has a lower total cost than the first solution and only if the result of the simulated annealing function is positive, a third solution comprising the second modified network topology for the network layer that includes a third selected subset of the filtered candidate links, and

wherein the topology computation module is further configured to determine, after generating a third modified network topology based on the network topology in response to determining that the second solution has a higher total cost than the first solution and only if the result of the simulated annealing function is negative, a fourth solution comprising the third modified network topology for the network layer that includes a third selected subset of the filtered candidate links.

28. The management device of claim 17,

wherein the topology computation module is further configured to route a plurality of traffic demands to the network topology, each traffic demand of the plurality of traffic demands representing an end-to-end traffic flow mapped to a label-switched path for the network layer.

29. The management device of claim 17, wherein to determine whether a candidate link of the plurality of candidate links has a feasible optical path the topology computation module is further configured to:

determine an impairment to an optical path for the candidate link;

determine, in response to determining an optical node that terminates the optical path includes an optical receiver that is available and able to tolerate the impairment, the candidate link has a feasible optical path; and

determine, in response to determining an optical node that terminates the optical path does not include an optical receiver that is available and able to tolerate the impairment, the candidate link does not have a feasible optical path.

30. The management device of claim 29, wherein the impairment comprises at least one of polarization mode dispersion, polarization dependent loss, and chromatic dispersion.

31. The management device of claim 17, wherein to determine whether a candidate link of the plurality of candidate links has a feasible optical path the topology computation module is further configured to:

determine an aggregate optical signal-to-noise ratio (OSNR) for an optical path for the candidate link;

determine, in response to determining an optical node that terminates the optical path includes an optical receiver that is available and able to receive an optical signal having the aggregate OSNR, the candidate link has a feasible optical path; and

determine, in response to determining an optical node that terminates the optical path does not include an optical receiver that is available and able to receive an optical signal having the aggregate OSNR, the candidate link does not have a feasible optical path.

32. The management device of claim 17, wherein the topology computation module is further configured to:

determine one or more optical paths in the transport layer to underlie a network link that connects a pair of routers in the network layer; and

generate candidate links of the plurality of candidate links that are each defined at least in part by an optical path of the one or more optical paths and the pair of routers.

33. The management device of claim 17, further comprising:

a topology provisioning module configured for execution by the one or more processors to output, for configuring the multi-layer network, the topology data.

34. A non-transitory computer-readable medium comprising instructions for causing one or more programmable processors of a management device of a multi-layer network comprising a network layer and an underlying transport layer to perform operations comprising:

obtaining a plurality of candidate links, wherein each candidate link of the plurality of candidate links is associated with an optical path in the transport layer;

determining, based at least on optical network data that describes optical characteristics of fibre links of the transport layer, each candidate link of the plurality of candidate links that has a feasible optical path;

determining a plurality of filtered candidate links comprising each candidate link determined to have a feasible optical path;

determining a first solution comprising a network topology for the network layer that includes a first selected subset of the filtered candidate links;

determining, after generating a modified network topology based at least on the network topology, a second solution comprising the modified network topology for the network layer that includes a second selected subset of the filtered candidate links; and

outputting topology data for one of the first solution or the second solution having a lowest total cost, the lowest total cost including a total resource cost to the network for the one of the first solution or the second solution.