Patent ID: 6697335
Filing Date: 2004-02-24
Classification: H04L

Abstract:
A method of determining an optimal path from a source node to a destination node over a number of links in an information network having n nodes, wherein each link has an associated cost-delay function and the optimal path has an overall delay of at most D, and a total cost of all links along the optimal path is minimized to a value OPT, the method comprising:maintaining a range [L, U] for OPT, wherein L is a lower bound and U is an upper bound; setting an initial value of L; setting an initial value of U to a value corresponding to an expected greatest cost; setting a cost value V corresponding to {square root over (UÂ·L)}scaling a given cost c of each link from c to câ€², wherein câ€² corresponds to c(n/V&egr;), and &egr;>0; determining if a feasible path exists having a delay of at most D and a total cost of at most V and, if no feasible path exists, then increasing the value of L and returning to the cost value setting and the link cost scaling steps; decreasing the value of U and continuing to increase the value of L until U/L<2 and a feasible path continues to exist; and identifying the links of the feasible path as the optimal path.