Tuning routing metrics to reduce maximum link utilization and/or provide failure resiliency

Abstract

A metric tuning technique optimizes the maximum link utilization of a set of links incrementally. Changes to the metric are constrained to be metric increases to divert routes from select links, thereby minimizing the number of changes required to achieve the optimization by avoiding the potential cascade of changes caused by attracting routes to a link. An interactive user interface is provided to allow a user to specify limits and constraints, and to select the sets of links to be addressed, including, for example, only the links that exceed a given link utilization threshold, the links having the highest link utilizations, the links having the highest failure effect, and so on. This incremental optimization technique is also used to optimize network resiliency by minimizing the network degradation caused by the failure of one or more links.

1 . A method of tuning routing metrics in a network by diverting routes from certain links in the network, said method comprising:
 obtaining network information from the network, the network information including an identification of links in the network and routing protocols associated with the links;   determining metrics used by the routing protocols to create routes over the links in the network;   determining a set of targeted links in the network that are targeted for optimization;   determining at least one network performance measure of the set of targeted links;   determining a set of candidate links in the network that are available for metric changes; and   determining changes to metrics for the set of candidate links that divert routes from the candidate links and improve the at least one network performance measure of the set of targeted links.   
     
     
         2 . The method of  claim 1 , wherein the determining the at least one network performance measure of the set of targeted links includes measuring link utilization of the set of targeted links. 
     
     
         3 . The method of  claim 1 , wherein determining the set of targeted links comprises selecting links in the network having a link utilization that exceed a threshold. 
     
     
         4 . The method of  claim 1 , wherein determining the set of targeted links comprises selecting links in the network having the highest link utilizations. 
     
     
         5 . The method of  claim 1 , wherein determining the set of targeted links comprises selecting links in the network having the highest failure effect on the network. 
     
     
         6 . The method of  claim 1 , wherein determining a set of targeted links in the network that are targeted for optimization comprises determining links in the network having a link utilization that exceed a specified limit. 
     
     
         7 . The method of  claim 1 , wherein determining changes to metrics for the set of candidate links that divert routes from the candidate links and improve the at least one network performance measure of the set of targeted links comprises determining changes to metrics for the set of candidate links that are within a specified constraint. 
     
     
         8 . The method of  claim 1 , further comprising:
 receiving a second set of candidate links; and   determining changes to metrics for the second set of candidate links that divert routes from the second set of candidate links and improve the at least one network performance measure of the set of targeted links.   
     
     
         9 . The method of  claim 1 , wherein determining the at least one network performance measure of the set of targeted links comprises determining effects of a modification of the routes in the network in response to a failure condition in the network. 
     
     
         10 . A system configured to tune routing metrics in a network by diverting routes from certain links in the network, said system comprising:
 a routing tool configured to obtain network information from the network, the network information including an identification of links in the network and routing protocols associated with the links, and wherein the routing protocols are used in the network to create routes over the links; and   a traffic engineering engine that is configured to determine metrics used by the routing protocols, determine a set of targeted links in the network that are targeted for optimization, determine at least one network performance of the set of targeted links, determine a set of candidate links in the network that are available for metric changes, and determine changes to metrics for the set of candidate links that divert routes from the candidate links and improve the at least one network performance measure of the set of targeted links.   
     
     
         11 . The system of  claim 10 , wherein the traffic engineering engine is configured to measure link utilization of the set of targeted links. 
     
     
         12 . The system of  claim 10 , wherein the traffic engineering engine is configured to select links in the network having a link utilization that exceed a threshold. 
     
     
         13 . The system of  claim 10 , wherein the traffic engineering engine is configured to select links in the network having the highest link utilizations. 
     
     
         14 . The system of  claim 10 , wherein the traffic engineering engine is configured to select links in the network having the highest failure effect on the network. 
     
     
         15 . The system of  claim 10 , wherein the traffic engineering engine is configured to determine changes to metrics for the set of candidate links that divert routes from the candidate links and improve the at least one network performance measure of the set of targeted links that are within a specified constraint. 
     
     
         16 . The system of  claim 15 , wherein the specified constraint comprises a limit on a network parameter. 
     
     
         17 . The system of  claim 15 , wherein the specified constraint comprises a limit on a link utilization for at least one link in the network. 
     
     
         18 . The system of  claim 10 , wherein the traffic engineering engine is configured to receive a second set of candidate links and determine changes to metrics for the second set of candidate links that divert routes from the second set of candidate links and improve the at least one network performance measure of the set of targeted links 
     
     
         19 . The system of  claim 10 , wherein the traffic engineering engine is configured to determine a modification of the routes in the network in response to a failure condition in the network.