Method and apparatus for self-tuned adaptive routing

Abstract

Various embodiments provide a method and apparatus for providing adaptive self-tuned routing within a network. In particular, one or more path selection values are adaptable to the changing network utilization and are configured to balance the influence of a first objective and a second objective on the path selection. Advantageously, balancing the influence of the first and second objectives on path selection provides improved efficiency and improved revenue generating capacity when compared to conventional routing methods.

What is claimed is: 
     
       1. An apparatus for selecting a path through a plurality of nodes interconnected via a plurality of links, the apparatus comprising:
 a data storage; and 
 a processor communicatively connected to the data storage, the processor being configured to receive a connection request, update a first objective information based on the connection request and a balance objective, the first objective information being associated with the plurality of links, update a second objective information based on the connection request and a efficiency objective, the efficiency objective information being associated with the plurality of links, determine a first utilization factor based on an association between the first objective information and an actual bandwidth allocation on the plurality of links, determine a second utilization factor based on an association between the second objective information and the actual bandwidth allocation on the plurality of links, and determine a first path selection value based on the first utilization factor and the second utilization factor to select the path based upon a bias that favors either the balance objective or the efficiency objective, wherein the first path selection value changes after either the first utilization factor or the second utilization factor exceeds a threshold value, and the change in the first path selection value is based on a comparison between the first utilization factor, the second utilization factor, and the threshold. 
 
     
     
       2. The apparatus of  claim 1 , wherein the connection request comprises a source node, a destination node, and a bandwidth requirement, the plurality of nodes comprising the source node and the destination node. 
     
     
       3. The apparatus of  claim 1 , wherein the balance objective is a link utilization objective and the efficiency objective is a network utilization objective. 
     
     
       4. The apparatus of  claim 3 , wherein the update of the first objective information comprises configuring the processor to determine a first objective path through the plurality of links based on the connection request and a minimum max-path distribution algorithm, wherein the update of the first objective information is further based on the first objective path. 
     
     
       5. The apparatus of  claim 4 , wherein the update of the second objective information comprises configuring the processor to determine a second objective path through the plurality of links based on the connection request and a minimum hop-path distribution algorithm, wherein the update of the second objective information is further based on the second objective path. 
     
     
       6. The apparatus of  claim 1 , wherein the first utilization factor is further based on a first maximum link utilization of an actual bandwidth allocation on the plurality of links and a second maximum link utilization associated with the first objective information, and the second utilization factor is further based on a first network utilization of the actual bandwidth allocation on the plurality of links and a second network utilization associated with the second objective information. 
     
     
       7. The apparatus of  claim 1 , wherein the processor is further configured to receive a second connection request, and select the path based on the first path selection value and an actual bandwidth allocation on the plurality of links. 
     
     
       8. The apparatus of  claim 7 , wherein the selection of the path comprises configuring the processor to determine a plurality of candidate paths between a source node and a destination node, determine a plurality of path costs corresponding to the candidate paths based on the first path selection value, and a plurality of link utilization values associated with the plurality of candidate paths, and select the one of the plurality of candidate paths having the lowest corresponding path cost. 
     
     
       9. A method for selecting a path through a plurality of nodes interconnected via a plurality of links, the method comprising:
 at a processor communicatively connected to a data storage, receiving a connection request; 
 updating, by the processor in cooperation with the data storage, a first objective information based on the connection request and a balance objective, the first objective information being associated with the plurality of links; 
 updating, by the processor in cooperation with the data storage, a second objective information based on the connection request and an efficiency objective, the second objective information being associated with the plurality of links; 
 determining, by the processor in cooperation with the data storage, a first utilization factor based on an association between the first objective information and an actual bandwidth allocation on the plurality of links; 
 determining, by the processor in cooperation with the data storage, a second utilization factor based on an association between the second objective information and the actual bandwidth allocation on the plurality of links; and 
 determining, by the processor in cooperation with the data storage, a first selection value based on the first utilization factor and the second utilization factor to select the path based upon a bias that favors either the balance objective or the efficiency objective, wherein the first path selection value changes after either the first utilization factor or the second utilization factor exceeds a threshold value, and the change in the first path selection value is based on a comparison between the first utilization factor, the second utilization factor, and the threshold. 
 
     
     
       10. The method of  claim 9 , wherein the connection request comprises a source node, a destination node, and a bandwidth requirement, the plurality of nodes comprising the source node and the destination node. 
     
     
       11. The apparatus of  claim 9 , wherein the balance objective is a link utilization objective and the efficiency objective is a network utilization objective. 
     
     
       12. The method of  claim 9 , wherein updating the first objective information comprises:
 determining, by the processor in cooperation with the data storage, a first objective path through the plurality of links based on the connection request and a minimum max-path distribution algorithm, wherein the update of the first objective information is further based on the first objective path. 
 
     
     
       13. The method of  claim 12 , wherein updating the first objective information comprises:
 determining, by the processor in cooperation with the data storage, a second objective path through the plurality of links based on the connection request and a minimum hop-path distribution algorithm, wherein the update of the second objective information is further based on the second objective path. 
 
     
     
       14. The method of  claim 9 , wherein the first utilization factor is further based on a first maximum link utilization of an actual bandwidth allocation on the plurality of links and a second maximum link utilization associated with the first objective information, and the second utilization factor is further based on a first network utilization of the actual bandwidth allocation on the plurality of links and a second network utilization associated with the second objective information. 
     
     
       15. The method of  claim 9 , wherein the method further comprises:
 receiving, by the processor in cooperation with the data storage, a second connection request; and 
 selecting, by the processor in cooperation with the data storage, the path based on the first path selection value and an actual bandwidth allocation on the plurality of links. 
 
     
     
       16. A non-transitory computer-readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method, the method comprising:
 receiving a connection request; 
 updating a first objective information based on the connection request and a balance objective, the first objective information being associated with the plurality of links; 
 updating a second objective information based on the connection request and an efficiency objective, the second objective information being associated with the plurality of links; 
 determining a first utilization factor based on an association between the first objective information and an actual bandwidth allocation on the plurality of links; 
 determining a second utilization factor based on an association between the second objective information and the actual bandwidth allocation on the plurality of links; and 
 determining a first path selection value based on the first utilization factor and the second utilization factor to select the path based upon a bias that favors either the balance objective or the efficiency objective, wherein the first path selection value changes after either the first utilization factor or the second utilization factor exceeds a threshold value, and the change in the first path selection value is based on a comparison between the first utilization factor, the second utilization factor, and the threshold.