Lagrange quality of service routing
US7020086B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 29, 2001 |
| Grant date | Mar 28, 2006 |
| Priority date | — |
| Expiry date | Apr 4, 2024 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04M2215/745
- WIPO fieldTelecommunications
- WIPO sectorElectrical engineering
Abstract
A method for practical QoS routing, which provides a solution to the delay constrained least cost routing problem, is presented. The method uses the concept of aggregated costs and finds the optimal multiplier based on Lagrange relaxation. The method is polynomial in running time, and produces a theoretical lower bound (i.e. optimal solution), along with the result. The differences between the lower bound and result are small, indicating the quality of the result. Additionally, by further relaxing the desire for an optimal solution, an option is provided to control the trade-off between running time of the algorithm and quality of the result.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.