Metric optimization for traffic engineering in a metric-routed network

• US 7,782,773 B2
• Filed: 01/31/2008
• Issued: 08/24/2010
• Est. Priority Date: 10/18/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cariden Technologies, Inc. (Cisco Systems, Inc.)
• Inventors: Gous, Alan Thornton
• Primary Examiner(s): JAIN, RAJ K
• Application Number:
  US12/023,957
• Publication Number:
  US 20080123534A1
• Time in Patent Office: 936 Days
• Field of Search: None
• US Class Current: 370/230
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 41/083 for increasing network speed
• CPC Class Codes: H04L 41/0836 to enhance reliability, e.g. reduce downtime
• 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/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/06 Generation of reports
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

A method is performed to optimize metrics associated with links of a network that is routed utilizing a shortest-path-first (SPF) routing method. The method includes identifying at least one failure scenario applicable to the network and identifying at least one bandwidth level scenario applicable to point-to-point demands routed through the network. A metric is automatically calculated for each of a plurality of links of a network, such that routings of demands through the network are optimized for the at least one failure scenario, and for the at least one bandwidth level.

Claims

1. A system to optimize metrics associated with links of a network that is routed utilizing a shortest-path-first (SPF) routing method, the system including:

a processor;

a metric traffic engineering module, to identify at least one failure scenario applicable to the network, to identify at least one bandwidth level scenario applicable to point-to-point demands routed through the network, and to automatically calculate a metric for each of a plurality of links of the network, such that routings of demands through the network are optimized into the at least one failure scenario and into the at least one bandwidth level scenario,

wherein the metric traffic engineering module being further configured to identify a plurality of failure scenarios and a plurality of bandwidth level scenarios applicable to the network, and to automatically calculate the metric for each of the plurality of links of the network such that the link utilizations resulting from demand routings determined by the metrics are below a predetermined threshold for each of the plurality of links of the network, for each of the plurality of failure scenarios, and for each of the plurality of bandwidth level scenarios;

wherein the automatic metric calculation is further configured to calculate the metric for each of the plurality of links of the network such that a maximum link utilization for each of the plurality of links, for each of the plurality of failure scenarios, and for each of the plurality of bandwidth level scenarios, is minimized, and the minimization being performed over all possible choices of link metrics; and

a changeover module coupled to the metric traffic engineering module, to signal network configuration changes to a network controller to rediscover the shortest path first routing through the network in accordance with the calculated metric for each of the plurality of links of the network.

2. The system of claim 1, wherein the at least one failure scenario is as a result of a voluntary action taken by a network operator to disable at least a portion of the network.

3. The system of claim 1, being further configured to apply the metric calculated for each of the plurality of links so as to route traffic within the network according to the calculated metrics.

4. The system of claim 1, being further configured to communicate the maximum link utilizations, over the at least one failure scenario and the at least one bandwidth level scenario, which result from an application of the automatically calculated metrics, for at least one link, to a user.

5. The system of claim 4, wherein the communication of the maximum link utilizations includes indicating whether at least one maximum link utilization exceeds a predetermined threshold link utilization.

6. The system of claim 4, wherein the communication of the maximum link utilizations includes generating a user interface in which at least one maximum link utilization is visually indicated.

7. The system of claim 1, being further configured to store the calculated metrics within the network so that the network is routed according to the stored metrics.

8. The system of claim 1, being further configured to identify the plurality of links of the network for which respective metrics are calculated as being core links of the network.

9. The system of claim 8, wherein sets of point-to-point demands are identified that follow a common routing through a core of the network for any choice of metrics of the core links, and demands are aggregated together and treated as a single demand in the automatic metric calculation.

10. A method to optimize metrics associated with links of a network that is routed utilizing a shortest-path-first (SPF) routing method, the method including:

identifying, by a processor, at least one failure scenario applicable to the network;

identifying, by the processor, at least one bandwidth level scenario applicable to point-to-point demands routed through the network;

automatically calculating a metric for each of a plurality of links of a network, such that routings of demands through the network are optimized for the at least one failure scenario, and for the at least one bandwidth level scenario;

identifying a plurality of failure scenarios and a plurality of bandwidth level scenarios applicable to the network, and automatically calculating the metric for each of the plurality of links of the network such that the link utilizations resulting from demand routings determined by the metrics are below a predetermined threshold for each of the plurality of links of the network, for each of the plurality of failure scenarios, and for each of the plurality of bandwidth level scenarios;

wherein the automatic metric calculation is further configured to calculate the metric for each of the plurality of links of the network such that a maximum link utilization for each of the plurality of links, for each of the plurality of failure scenarios, and for each of the plurality of bandwidth level scenarios, is minimized, and the minimization being performed over all possible choices of link metrics; and

signaling network configuration changes to a network controller to rediscover the shortest path first routing through the network in accordance with the calculated metric for each of the plurality of links of the network.

11. The method of claim 10, wherein the at least one failure scenario is as a result of a voluntary action taken by a network operator to disable at least a portion of the network.

12. The method of claim 10, including applying the metric calculated for each of the plurality of links in the shortest-path-first routing method so as to route traffic within the network according to the calculated metrics.

13. The method of claim 10, including communicating the maximum link utilizations, over the at least one failure scenario and the at least one bandwidth level scenario, which result from an application of the automatically calculated metrics, for at least one link, to a user.

14. The method of claim 13, wherein the communication of the maximum link utilizations includes indicating whether at least one maximum link utilization exceeds a predetermined threshold link utilization.

15. The method of claim 13, wherein the communication of the maximum link utilizations includes generating a user interface in which at least one maximum link utilization is visually indicated.

16. The method of claim 10, including storing the calculated metrics within the network so that the network is routed, utilizing the shortest-path-first routing method, according to the stored metrics.

17. The method of claim 10, including identifying the plurality of links of the network for which respective metrics are calculated as being core links of the network.

18. The method of claim 17, wherein sets of point-to-point demands are identified that follow a common routing through a core of the network for any choice of metrics of the core links, and demands are aggregated together and treated as a single demand in the automatic metric calculation.