Constraint-based shortest path first method for dynamically switched optical transport networks

Abstract

Method and apparatus for implementing a constraint-based shortest path first (“CSPF”) technique for dynamically switched optical transport networks are described. One embodiment comprises a traffic network element (“TNE”) in a network comprising a traffic engineering network database (“TEND”) that stores network topology information for the network and bandwidth availability information for links in the network; and a routing engine that receives a request for a label switched path (“LSP”) with specified constraints, processes network topology information from the TEND to create a network graph comprising links meeting the specified constraints, and computes a primary path through the network, wherein the primary path comprises links selected from the network graph.

1. A traffic network element (“TNE”) in a network, the TNE comprising:
 a traffic engineering network database (“TEND”) that stores network topology information for the network and bandwidth availability information for links in the network; 
 a routing engine that receives a request for a label switched path (“LSP”) through the network with specified constraints, processes network topology information from the TEND to create a network graph comprising links meeting the specified constraints, and computes a primary path through the network, wherein the primary path comprises links selected from the network graph; and 
 wherein if two or more links have the same cost, the one of the links having the greatest number of data-bearing channels is selected to comprise a portion of the primary path. 
 
     
     
       2. The TNE of  claim 1  wherein the routing engine computes the primary path by applying a shortest path first (“SPF”) algorithm to the network graph. 
     
     
       3. The TNE of  claim 1  wherein the routing engine prunes the network graph to eliminate therefrom links comprising the primary path. 
     
     
       4. The TNE of  claim 3  wherein the routing engine computes a backup path through the network, wherein the backup path comprises links selected from the pruned network graph. 
     
     
       5. The TNE of  claim 4  wherein the routing engine computes the backup path by applying a shortest path first (“SPF”) algorithm to the pruned network graph. 
     
     
       6. A method of computing an explicit route through a network comprising:
 receiving a path setup request message for a new traffic flow in the network, wherein the path setup request message includes specified constraints on the path; 
 generating a network graph from network information stored in a traffic engineering network database (“TEND”), wherein links not meeting the specified constraints for the path are not included in the graph; and 
 calculating a primary explicit route through the network from the generated network graph, wherein a link with a maximum number of data-bearing channels is selected for inclusion in the primary explicit route in a case in which two or more links have a same cost. 
 
     
     
       7. The method of  claim 6  further comprising:
 regenerating the network graph by eliminating from the network graph links that are in the primary explicit route; and 
 calculating a backup explicit route from the regenerated network graph. 
 
     
     
       8. The method of  claim 6  further comprising:
 regenerating the network graph by eliminating from the network graph all links connected to nodes that are in the primary explicit route links; and 
 calculating a backup explicit route from the regenerated network graph. 
 
     
     
       9. The method of  claim 6  further comprising:
 regenerating the network graph by eliminating from the network graph links in the same shared risk group as a link in the primary explicit route; and 
 calculating a backup explicit route from the regenerated network graph. 
 
     
     
       10. The method of  claim 6  wherein the calculating a primary explicit route and calculating a backup explicit route are performed using a least cost analysis. 
     
     
       11. A method of computing an explicit route through a network comprising:
 receiving a path setup request message for a new traffic flow in the network, wherein the path setup request message includes specified constraints on the path; 
 generating a network graph from network information stored in a traffic engineering network database (“TEND”), wherein links not meeting the specified constraints for the path are not included in the graph; and 
 calculating a primary explicit route through the network from the generated network graph; 
 calculating a backup explicit route from a regenerated network graph; 
 wherein the calculating a primary explicit route and the calculating a backup explicit route are performed using a least cost analysis; and 
 wherein a link with a maximum number of data-bearing channels is selected from the regenerated network graph for inclusion in the backup explicit route in a case in which two or more links have a same cost. 
 
     
     
       12. The method of  claim 10  wherein the least cost analysis comprises a shortest path algorithm. 
     
     
       13. The method of  claim 6  wherein the network information stored in the TEND comprises network resources availability information and network topology information. 
     
     
       14. A traffic network element (“TNE”) in a network, the TNE comprising:
 means for storing network topology information for the network and bandwidth availability information for links in the network; and 
 means for processing information from the TEND to create a network graph comprising links meeting specified constraints in a request for a label switched path (“LSP”) and calculating a primary explicit route through the network, wherein the primary explicit route comprises links selected from the network graph and wherein if two or more links have the same cost, the one of the links having the greatest number of data-bearing channels is selected to comprise a portion of the primary explicit route. 
 
     
     
       15. The TNE of  claim 14  wherein the primary explicit route is calculated by applying a least cost analysis to the network graph. 
     
     
       16. The TNE of  claim 14  wherein the primary explicit route is calculated by applying a shortest path first (“SPF”) algorithm to the network graph. 
     
     
       17. The TNE of  claim 14  further comprising means for pruning the network graph to eliminate therefrom at least one of links and nodes that are not diverse with links and nodes included in the primary explicit route. 
     
     
       18. The TNE of  claim 14  further comprising means for pruning the network graph to eliminate therefrom links that are connected to nodes that are not diverse with nodes included in the primary explicit route. 
     
     
       19. The TNE of  claim 14  further comprising means for pruning the network graph to eliminate therefrom links that are in the same shared risk group as a link included in the primary explicit route. 
     
     
       20. The TNE of  claim 14  further comprising means for calculating a backup explicit route through the network, wherein the backup explicit route comprises links selected from the pruned network graph. 
     
     
       21. The TNE of  claim 20  wherein the backup explicit route is calculated by applying a least cost analysis to the pruned network graph. 
     
     
       22. The TNE of  claim 20  wherein the backup explicit route is calculated by applying a shortest path first (“SPF”) algorithm to the pruned network graph.