Lagrange quality of service routing

• US 7,020,086 B2
• Filed: 06/29/2001
• Issued: 03/28/2006
• Est. Priority Date: 07/03/2000
• Status: Active Grant

• Current Assignee: Unwired Planet LLC (JP Morgan Chase & Co)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Jüttner, Alpár, Mécs, Ildikó
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): ABELSON, RONALD B
• Application Number:
  US09/893,960
• Publication Number:
  US 20020045453A1
• Time in Patent Office: 1,733 Days
• Field of Search: 370237-238, 709238-242, 706/19
• US Class Current: 370/238
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04M 15/00 Arrangements for metering, time-control or time indication ; Metering, charging or billing arrangements for voice wireline or wireless communications, e.g. VoIP
• CPC Class Codes: H04M 15/43 Billing software details
• CPC Class Codes: H04M 15/49 Connection to several service providers
• CPC Class Codes: H04M 15/8016 based on quality of service [QoS]
• CPC Class Codes: H04M 15/8044 Least cost routing
• CPC Class Codes: H04M 2215/32 Involving wireless systems
• CPC Class Codes: H04M 2215/42 Least cost routing, i.e. provision for selecting the lowest cost tariff
• CPC Class Codes: H04M 2215/46 Connection to several service providers
• CPC Class Codes: H04M 2215/7414 QoS
• CPC Class Codes: H04M 2215/745 Least cost routing, e.g. Automatic or manual, call by call or by preselection

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.

Claims

1. A method for determining a delay constrained least cost path in a multi-path communication system, the method comprising the steps of:

finding a first path with a minimum cost and first path delay;

finding a second path with minimum delay and second path cost;

determining the delay constrained least cost path based, in part, on the first path and second path by using a Lagrange relaxation variable, comprising;

calculating a Lagrange relaxation variable; and

,

determining the delay constrained least cost path based on the Lagrange relaxation variable;

wherein the step of calculating a Lagrange relaxation variable comprises;

calculating a first sum equal to the cost of the first path less the cost of the second path;

calculating a second sum equal to the delay of the first path less the delay of the second; and

,

dividing the first sum by the second sum.

2. The method of claim 1, wherein the step of determining the delay constrained least cost path based, in part, on the first path and second path, comprises:

determining that if the first path delay is less than a maximum allowable delay, then the first path is the delay constrained least cost path.

3. The method of claim 1, wherein the step of determining the delay constrained least cost path based, in part, on the first path and second path, comprises:

determining that if the second path delay is greater than the maximum allowable delay then there is no delay constrained least cost path.

4. The method of claim 1, wherein the step of determining the delay constrained least cost path based on the Lagrange relaxation variable, comprises:

determining a third path that minimizes a first modified cost function;

calculating a second modified cost function using the first path;

determining that the delay constrained least cost path is the second path if the second modified cost function equals the first modified cost function.

5. The method of claim 1, wherein the step of determining the delay constrained least cost path based on the Lagrange relaxation variable, comprises:

determining a third path that minimizes a first modified cost function;

calculating a second modified cost function using the first path;

determining that the first modified cost function does not equal the second modified cost function;

determining whether the delay of the third path is greater than the maximum allowable delay, and if yes, replacing the first path with the third path to create a new first path, and if not, replacing the second path with the third path, to create a new second path, and

determining the delay constrained least cost path based on the new first path or new second path.

6. The method of claim 5, wherein the step of determining the delay constrained least cost path based on the new first path or new second path, comprises:

repeating the steps of;

calculating a new Lagrange relaxation variable based on the new first path or based on the new second path, wherein the new first path takes the place of the first path, or the new second path takes the place of the second path;

determining a new third path that minimizes a new first modified cost function, based on the new Lagrange relaxation variable;

calculating a new second modified cost function using the old first path, or new first path and the new Lagrange relaxation variable; and

determining whether the new second modified cost function equals the new first modified cost function, and if yes, then the delay constrained least cost path equals either the new second path or second path used in calculating the new second modified cost function, and if not, determining whether the delay of the new third path is greater than or equal to the maximum allowable delay, and if yes, replacing the new first path or first path, with the new third path, and if not, replacing the new second path or second path, with the new third path, until the delay constrained least cost path is determined.

7. The method of claim 1, wherein the step of finding a first path with minimum cost, comprises:

using a Dijkstra Algorithm.

8. The method of claim 1, wherein the step of finding a second path with minimum delay, comprises:

using a Dijkstra Algorithm.

9. The method according to claim 4, wherein the step of determining a third path that minimizes a first modified cost function, comprises:

using a Dijkstra Algorithm.

10. The method of claim 4, wherein the step of determining a third path that minimizes a first modified cost function, comprises:

defining the modified cost function defined as the cost of the third path plus the product of the Lagrange relaxation variable and the delay of the third path.

11. The method of claim 1, wherein the step of determining the delay constrained least cost path based, in part, on the first path and second path, comprises:

determining that if the cost of the second path is within a certain percentage of the cost of the first path, the second path is the delay constrained least cost path.

12. A method for determining a delay constrained least cost path, in a multi-path communication system, the method comprising the steps of:

finding a first path with minimum cost and a first path delay;

finding a second path with minimum delay and a second path cost;

generating a series of Lagrange relaxation variables, each Lagrange relaxation variable having an associated third path, each third path having a delay and cost; and

determining the delay constrained least cost path, based on the first path, second path, Lagrange relaxation variable, and third path.

13. The method of claim 12, wherein the step of determining the delay constrained least cost path, based on the first path, second path, Lagrange relaxation variable, and third path, comprises:

selecting a first group of associated third paths, the delays of which are greater than or equal to a maximum allowable delay;

selecting a second group of associated third paths, the delays of which are less than a maximum allowable delay;

determining a primary Lagrange relaxation variable, from the first group of associated third paths, the primary Lagrange relaxation variable being the maximum associated Lagrange relaxation variable, the primary Lagrange relaxation variable having an associated primary third path;

determining a secondary Lagrange relaxation variable, from the second group of associated third paths, the secondary Lagrange relaxation variable being the minimum associated Lagrange relaxation variable, the secondary Lagrange relaxation variable having an associated secondary third path; and

selecting the primary third path to be a first path, and selecting the secondary third path to be a second path.

14. A method for determining a least cost path satisfying multiple constraints in a multi-path communication system, the method comprising the steps of:

finding multiple paths, one for each of multiple constraints, each of the multiple paths having a different minimum constraint, a first multiple path being a minimal cost path;

calculating a first set of multiple Lagrange relaxation variables, one for each of the multiple constraints;

determining a minimizing path that minimizes a first multi-term modified cost function;

calculating a second multi-term modified cost function using the first multiple path; and

determining the least cost path satisfying multiple constraints.

15. The method of claim 14, wherein the step of determining the least cost path satisfying multiple constraints comprises:

determining that the first multi-term modified cost function equals the second multi-term modified cost function; and

determining which of the multiple paths minimizes the maximal exceeding of the constraints, that path being the path satisfying multiple constraints.

16. The method of claim 15, wherein the step of determining which of the multiple paths that minimizes the maximal exceeding of the constraints comprises:

comparing the constraints of the multiple paths, and determining which path has a lowest constraint value for a maximal constraint, that path being the least cost path satisfying multiple constraints.

17. The method of claim 14, wherein the step of determining the least cost path satisfying multiple constraints, comprises:

determining that the first multi-term modified cost function does not equal the second multi-term modified cost function;

calculating multiple sets of multiple Lagrange relaxation variables, each set corresponding to a particular path of multiple paths; and

determining which of the multiple sets of multiple Lagrange relaxation variables is a maximum set of Lagrange relaxation variables, and the particular path of the multiple paths associated with that maximum set of multiple Lagrange relaxation variables, is the least cost path satisfying multiple constraints.