MEMORY-EFFICIENT MATRIX-BASED OPTICAL PATH COMPUTATION

摘要

A matrix M indicating a minimum number of all optical paths between pairs of nodes may be generated in one embodiment using an algorithm for transitive closure. In various embodiments, different algorithms and methods may be used to generate matrix M. Once a convergent matrix M has been generated that attains transitive closure, any corresponding reachability matrix RM̂a may be obtained from matrix M in a computationally efficient manner. Matrix M may be used to determine groups of potential regenerator placements and obtain end-to-end optical paths by selecting desired sequences of regenerators.

主权项

1. A method for computation of optical paths in optical networks, the method comprising:
calculating a matrix M, wherein the matrix M indicates, for each pair of nodes in an optical network, a minimum number of all-optical paths between a respective pair of nodes in the matrix M, wherein an all-optical path does not include an optical-electrical-optical (O-E-O) regenerator, and further comprising:
calculating a reachability matrix RM̂1 for each of the pair of nodes in the optical network, wherein a non-zero value in the reachability matrix RM̂1 indicates at least one all-optical path between a respective pair of nodes in the reachability matrix RM̂1; andbased on the reachability matrix RM̂1, for each of the pair of nodes in the optical network, calculating the minimum number of all-optical paths between the respective pair of nodes in the matrix M.