Patent ID: 8479138

Claim:
A routing method for a computer system having one or more computer processors and a non-transitory computer-readable storage medium storing a computer readable program for performing the method, the method comprising: for a set of connections subject to constraints including a set of elongation constraints, generating, with one or more of the computer processors, an initial set of topological paths without considering at least some of the elongation constraints, wherein the elongation constraints include at least one constraint that can be addressed by changing a length or delay of a path of one or more connections subject to the constraint; estimating, with one or more of the computer processors, an initial set of elongations that would, when applied to at least some paths in the initial set, cause the initial set of paths to meet the elongation constraints, the initial set of elongations including increased length or delay in one or more paths in the initial set of paths, wherein an elongation refers to changing a length or delay of a path of one or more connections that are subject to the constraint; generating, with one or more of the computer processors, a new set of topological paths by re-routing at least some paths in the initial set to reduce an overall estimated increased length or delay for the initial set of paths; estimating, with one or more of the computer processors, a new set of elongations that would, when applied to at least some paths based on the new set of paths, cause the paths based on the new set of paths to meet the elongation constraints; generating, with one or more of the computer processors, an elongated set of paths by applying, with one or more of the computer processors, the new set of elongations to the paths based on the new set of paths; storing path information based on the elongated set of paths in the computer-readable storage medium; and after generating the new set of paths and prior to estimating the new set of elongations, determining geometric paths based on the new set of paths.