Lucent Technologies Inc.

Ayse Funda Ergun

Yihao Lisa Zhang

Rakesh Kumar Sinha

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. Each link has an associated cost-delay function, the optimal path is constrained to an overall delay of D, and a total cost of all links along the path is to be minimized at a value OPT. The method includes maintaining a range &lsqb;L, U&rsqb; for OPT, wherein L is a lower bound and U is an upper bound, and setting initial values for L and U. A cost value V is set corresponding to {square root over (U&middot;L)}, and a scaled cost c&prime; is derived for each link wherein c&prime; corresponds to cn/V&egr;, c is an actual cost for each link, and &egr;>0. If a feasible path having a delay of at most D and a total cost of at most V is found not to exist, then the value of L is increased to V, a new cost value V is set and the link costs c&prime; are further scaled. The values of L and U are reset until U/L<2 and a feasible path continues to exist. The links of the feasible path are then identified as the optimal path using the last-scaled link costs.

Growing community of inventors

Lakewood, OH, United States of America

Ayse Funda Ergun