Patent ID: 8000250

Claim:
A method of determining routes for transmitting signals through a network, the method comprising: obtaining network data, including link type data, spare capacity data, vendor data, and common mileage data; obtaining demand data for a plurality of demands, including origination node data, termination node data, and diversity requirement data; storing the network data and the demand data; processing the demand data using a shortest path routing method to obtain an initial route for each demand, where each demand is routed without changing the route of previously routed demands and without regard to any outstanding demands to be routed; updating the network data by decreasing the spare capacity data in accordance with the initial route; computing an initial cost based on the initial routes for all demands; updating the network data by increasing the spare capacity data in accordance with deleting the initials routes; re-processing the demand data using a constrained diverse shortest path routing method by individually re-routing each demand until a stop criterion is satisfied and obtaining a final route for each demand, the constrained diverse shortest path routing method including creating a plurality of partial paths starting at an originating node of the demand, evaluating a partial path cost for each created partial path, each partial path cost including only new diversity requirement violations, selecting one of the created partial paths based on the evaluated partial path cost, and repeating, using an end node of the selected partial path as starting node, until a destination node of the demand is reached; computing a final cost based on the final routes; and outputting the final routes and the final cost.