Method and apparatus for least cost routing using multiple path accumulated constraints

1. A method for searching for a path solution in a network, the method performed by a path searching device, the method comprising:

identifying, by the path searching device, combinations of partial paths in the network that satisfy an end-to-end path constraint;

comparing, by the path searching device, attributes of the combinations of partial paths against each other;

pruning, by the path searching device, the combinations of partial paths based on results of the comparing to identify candidate combinations of partial paths, the pruning including keeping a combination of partial paths for which at least one accumulated attribute of the combination of partial paths compares favorably to a corresponding accumulated attribute of another combination of partial paths, the combinations of partial paths that are kept being candidate combinations of partial paths from which a path solution may be selected; and

selecting, by the path searching device, a candidate combination from the candidate combinations of partial paths identified as the path solution.

2. The method of claim 1 wherein identifying, by the path searching device, the combinations of partial paths that satisfy the end-to-end constraint includes expanding a path with a partial path to a node to form an expanded path, the end-to-end constraint being satisfied if attributes of each partial path forming the expanded path, added together, are less than the constraint;

wherein comparing, by the path searching device, the attributes of the combinations of partial paths includes comparing the attributes of the expanded path against attributes of a previously identified candidate combination of partial paths to the node called a previous candidate path, the previous candidate path being stored in a candidate paths container;

wherein pruning, by the path searching device, the combinations of partial paths further includes:

removing the expanded path if the expanded path has no attribute that compares favorably to a corresponding attribute of the previous candidate path;

removing the previous candidate path from the candidate paths container if the previous candidate path has no attribute that compares favorably to a corresponding attribute of the expanded path;

keeping both the expanded path and the previous candidate path in the candidate paths container if each has an attribute that compares favorably to a corresponding attribute of the other; and

wherein selecting, by the path searching device, the candidate combination of partial paths as the path solution includes selecting a candidate path from the candidate paths container as the path solution.

3. The method of claim 1 wherein identifying, by the path searching device, the combinations of partial paths includes disqualifying a combination of partial paths that exceeds an end-to-end path constraint from being compared against other combinations of partial paths.

4. The method of claim 1 wherein identifying, by the path searching device, the combinations of partial paths includes identifying the combinations of partial paths for which respective accumulated latencies satisfy an end-to-end path constraint of latency.

5. The method of claim 1 wherein identifying, by the path searching device, the combinations of partial paths includes identifying the combinations of partial paths for which respective accumulated signal-to-noise ratios satisfy an end-to-end path constraint.

6. The method of claim 1 wherein identifying, by the path searching device, the combinations of partial paths includes identifying the combinations of partial paths for which respective accumulated chromatic dispersions satisfy an end-to-end path constraint.

7. The method of claim 1 wherein pruning, by the path searching device, the combinations of partial paths further includes discarding a combination of partial paths for which accumulated attributes of the combination of partial paths compares unfavorably to corresponding accumulated attributes of another combination of partial paths.

8. The method of claim 1 wherein selecting, by the path searching device, the candidate combination of partial paths as the path solution includes selecting a candidate combination of partial paths having a cost that is less than costs of other candidate combinations of partial paths, the path solution being a path of least cost and satisfying the end-to-end path constraint.

9. The method of claim 1 wherein selecting, by the path searching device, the candidate combination of partial paths as the path solution includes selecting the candidate combination of partial paths for which an end-to-end path attribute is optimum.

10. The method of claim 1 wherein identifying the combinations of partial paths that satisfy the end-to-end constraint includes expanding a path with a partial path to a node to form an expanded path, the end-to-end constraint being satisfied if attributes of each partial path forming the expanded path, added together, are less than the constraint.

11. The method of claim 10 wherein comparing the attributes of the combinations of partial paths includes comparing the attributes of the expanded path against attributes of a previously identified candidate combination of partial paths to the node, the previously identified candidate combination of partial paths to the node being stored in a candidate paths container, and further wherein selecting the candidate combination of partial paths as the path solution includes selecting a candidate path from the candidate paths container as the path solution.

12. The method of claim 11 wherein pruning the combination of partial paths further includes:

removing the expanded path if the expanded path has no attribute that compares favorably to a corresponding attribute of the previous candidate path;

removing the previous candidate path from the candidate paths container if the previous candidate path has no attribute that compares favorably to a corresponding attribute of the expanded path; and

keeping both the expanded path and the previous candidate path in the candidate paths container if each has an attribute that compares favorably to a corresponding attribute of the other.

13. The method of claim 1 wherein identifying, by the path searching device, the combinations of partial paths that satisfy the end-to-end constraint includes expanding a path with a partial path to a node to form an expanded path, and further wherein comparing the attributes of the combinations of partial paths includes comparing the attributes of the expanded path against attributes of a previously identified candidate combination of partial paths to the node, the previously identified candidate combination of partial paths to the node being stored in a candidate paths container.

14. An apparatus to search for a path solution in a network, the apparatus comprising:

an identifying module to identify combinations of partial paths that satisfy an end-to-end path constraint;

a comparing module, communicatively coupled to the identifying module, to compare attributes of the combinations of partial paths against each other;

a pruning module, communicatively coupled to the comparing module, to prune the combinations of partial paths based on results of the comparing to identify candidate combinations of partial paths, the pruning module configured to keep a combination of partial paths for which at least one accumulated attribute of the combination of partial paths compares favorably to a corresponding accumulated attribute of another combination of partial paths, the combinations of partial paths that are kept being candidate combinations of partial paths from which the selecting module may select a path solution;

a selecting module, communicatively coupled to the pruning module, to select a candidate combination from the candidate combinations of partial paths identified as the path solution.

15. The apparatus of claim 14 wherein the identifying module is configured to disqualifying a combination of partial paths that exceeds an end-to-end path constraint from being compared to other combinations of partial paths.

16. The apparatus of claim 14 wherein the identifying module is configured to identify the combinations of partial paths for which respective accumulated latencies satisfy an end-to-end path constraint.

17. The apparatus of claim 14 wherein the identifying module is configured to identify the combinations of partial paths for which respective accumulated signal-to-noise ratios satisfy an end-to-end path constraint.

18. The apparatus of claim 14 wherein the identifying module is configured to identify the combinations of partial paths for which respective accumulated chromatic dispersions satisfy an end-to-end path constraint.

19. The apparatus of claim 14 wherein the pruning module is further configured to discard a combination of partial paths for which accumulated attributes of the combination of partial paths compares unfavorably to corresponding accumulated attributes of another combination of partial paths.

20. The apparatus of claim 14 wherein the selecting module is configured to select a candidate combination of partial paths having a cost that is less than costs of other candidate combinations of partial paths, the path solution being a path of least cost and satisfying the end-to-end path constraint.

21. The apparatus of claim 14 wherein the selecting module is configured to select the candidate combination of partial paths for which an end-to-end path attribute is optimum.

22. A computer program product comprising a non-transitory computer readable medium having stored thereon a computer readable program, the computer readable program when loaded into a computer processor transforms the computer processor into a programmed computer processor and when executed causes the programmed computer processor to:

identify combinations of partial paths that satisfy an end-to-end path constraint;

compare attributes of the combinations of partial paths against each other;

prune the combinations of partial paths, based on results of the comparing to identify candidate combinations of partial paths, including keeping a combination of partial paths for which at least one accumulated attribute of the combination of partial paths compares favorably to a corresponding accumulated attribute of another combination of partial paths, the combinations of partial paths that are kept being candidate combinations of partial paths from which a path solution may be selected; and

select a candidate combination from the candidate combinations of partial paths identified as the path solution.

23. A method for searching for a path solution in a network, the method performed by a path searching device, the method comprising:

identifying, by the path searching device, combinations of partial paths in the network that satisfy an end-to-end path constraint;

comparing, by the path searching device, attributes of the combinations of partial paths against each other;

pruning, by the path searching device, the combinations of partial paths based on results of the comparing to identify candidate combinations of partial paths; and

selecting, by the path searching device, a candidate combination from the candidate combinations of partial paths identified as the path solution, wherein:

the identifying includes expanding a path with a partial path to a node to form an expanded path, the end-to-end constraint being satisfied if attributes of each partial path forming the expanded path, added together, are less than the constraint;

the comparing includes comparing the attributes of the expanded path against attributes of a previously identified candidate combination of partial paths to the node called a previous candidate path, the previous candidate path being stored in a candidate paths container;

the pruning includes:

removing the expanded path if the expanded path has no attribute that compares favorably to a corresponding attribute of the previous candidate path;

removing the previous candidate path from the candidate paths container if the previous candidate path has no attribute that compares favorably to a corresponding attribute of the expanded path; and

keeping both the expanded path and the previous candidate path in the candidate paths container if each has an attribute that compares favorably to a corresponding attribute of the other; and

the selecting includes selecting a candidate path from the candidate paths container as the path solution.

24. A method for searching for a path solution in a network, the method performed by a path searching device, the method comprising:

identifying, by the path searching device, combinations of partial paths in the network that satisfy an end-to-end path constraint;

comparing, by the path searching device, attributes of the combinations of partial paths against each other;

pruning, by the path searching device, the combinations of partial paths based on results of the comparing to identify candidate combinations of partial paths; and

selecting, by the path searching device, a candidate combination from the candidate combinations of partial paths identified as the path solution, wherein:

the identifying includes expanding a path with a partial path to a node to form an expanded path, the end-to-end constraint being satisfied if attributes of each partial path forming the expanded path, added together, are less than the constraint;

the comparing includes comparing the attributes of the expanded path against attributes of a previously identified candidate combination of partial paths to the node, the previously identified candidate combination of partial paths to the node being stored in a candidate paths container, and

the selecting includes selecting a candidate path from the candidate paths container as the path solution.

25. A method for searching for a path solution in a network, the method performed by a path searching device, the method comprising:

identifying, by the path searching device, combinations of partial paths in the network that satisfy an end-to-end path constraint;

comparing, by the path searching device, attributes of the combinations of partial paths against each other;

pruning, by the path searching device, the combinations of partial paths based on results of the comparing to identify candidate combinations of partial paths; and

selecting, by the path searching device, a candidate combination from the candidate combinations of partial paths identified as the path solution wherein:

the identifying includes expanding a path with a partial path to a node to form an expanded path; and

the comparing includes comparing the attributes of the expanded path against attributes of a previously identified candidate combination of partial paths to the node, the previously identified candidate combination of partial paths to the node being stored in a candidate paths container.