Quality of service routing in information networks over paths having performance-dependent costs
US6697335B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 27, 2000 |
| Grant date | Feb 24, 2004 |
| Priority date | — |
| Expiry date | Apr 2, 2022 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/121
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
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. 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 [L, U] 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·L)}, and a scaled cost c′ is derived for each link wherein c′ 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′ 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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.