Device and a method for determining routing paths in a communication network in the presence of selection attributes

• US 20040233850A1
• Filed: 07/29/2003
• Published: 11/25/2004
• Est. Priority Date: 07/30/2002
• Status: Abandoned Application

• Current Assignee: Alcatel SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Gandibleux, Xavier, Thomin, Philippe, Rui Figueira, Jose, Randriamasy, Claire-Sabine
• Application Number:
  US10/628,265
• Publication Number:
  US 20040233850A1
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS

Abstract

A device (D) for determining data routing paths in a communication network including a multiplicity of nodes (Nn) includes processing means (M) adapted i) to ensure that at least a portion of said multiplicity of nodes are connected, ii) for said nodes of said portion, to calculate possible paths between a departure node and an arrival node, allowing for at least two chosen criteria, and then to deduce an ideal solution (Z()) from performances (Z(r*)) of said possible paths (r*) based on said criteria, iii) to assign each possible path a value of interest allowing for the ideal solution, and then to classify the possible paths allowing for their respective values of interest, and iv) to select from the classified possible paths the k best classified paths, in order to route data via one of said k paths.

Claims

1. A method of determining data routing paths in a communication network including a multiplicity of nodes (Nn), which method is characterized in that it includes the following steps:

a) ensuring that at least a portion of said multiplicity of nodes (Nn) are connected,

b) for said nodes of said portion, calculating possible paths (r*) between a departure node (Ns) and an arrival node (Nt), allowing for at least two chosen criteria, and then deducing an ideal solution (Z()) from performances (Z(r*)) of said possible paths (r*) based on said criteria,

c) assigning each possible path (r*) a value of interest (U(r)) allowing for said ideal solution (Z()), and then classifying said possible paths allowing for their respective values of interest, and

d) selecting from said classified possible paths the k best classified paths, in order to route data via one of said k paths.

2. A method according to claim 1, characterized in that step a) begins by determining from said multiplicity of nodes (Nn) all the pairs of nodes that can establish between them an oriented link each supporting at least one chosen local constraint, after which it is ensured that all the nodes of said pairs are connected.

3. A method according to claim 1, characterized in that at the end of step b) there are retained from said possible paths (r*) those that each satisfy at least one chosen global constraint so that in step c) values of interest (U(r)) are assigned to said retained possible paths (r*).

4. A method according to claim 1, characterized in that at least one of said criteria is of the non-additive type.

5. A method according to claim 4, characterized in that step b) integrates a trace storing a route corresponding to a partial path, in order to detect and prevent cycles in the paths under construction.

6. A method according to claim 5, characterized in that in step b), during the procedure of eliminating said partial paths, there are retained solutions that are “

weakly non-dominated”

on the non-additive criterion.

7. A method according to claim 1, characterized in that connectivity is verified by a mechanism of propagation from the departure node (Ns) to all the other nodes (Nn) of said multiplicity of nodes, so that each node (Nn) is visited.

8. A method according to claim 1, characterized in that in step b) representative values (Z(r)) of its “

performance”

are determined for each path with respect to each of said chosen criteria and a path (r) for which said performance values (Z(r)) are “

non-dominated”

is qualified as a possible path (r*).

9. A method according to claim 8, characterized in that in step b) the best performance value (Z*(r)) observed over said possible paths, referred to as the “

optimum value”

, is determined for each criterion and said ideal solution (Z()) is then constructed in the form of a multiplet of components constituted of the various optimum values thus determined.

10. A method according to claim 9, characterized in that in step c) said value of interest (U(r)) assigned to each possible path (r) characterizes the greatest value of the components associated with the various chosen criteria of a weighted Tchebychev function of differences between the performance of said possible path (r*) and the corresponding optimum value of said ideal solution (Z()).

11. A method according to claim 10, characterized in that said k possible paths retained have the k lowest values of interest (U(r)).

12. A method according to claim 2, characterized in that said local and/or global constraints are selected from a group comprising at least the minimum bandwidth required, the maximum length of the path, the maximum duration of the path, at least one prohibited link, the maximum number of hops on the path, and a path color restriction.

13. A method according to claim 1, characterized in that said criteria are selected from a group comprising at least the available bandwidth (C2), the number of hops on the path (C3), and the duration of the path (C1).

14. A method according to claim 13, characterized in that said chosen criteria used in step b) comprise the available bandwidth (C2) and the duration of the path (C1).

15. A method according to claim 14, characterized in that in step b) said criterion relating to the duration of the path (C1) is impacted by a penalty.

16. A method according to claim 15, characterized in that said penalty applies to the administration cost (CA) of the path.

17. A method according to claim 1, characterized in that said criteria are chosen as a function of the type of service required.

18. A method according to claim 1, characterized in that said chosen criteria are weighted as a function of their importance in the light of management information.

19. A method according to claim 2, characterized in that said constraints and their associated values are chosen as a function of the quality of service required.

26. A device according to claim 1, characterized in that said processing means (M) are adapted to verify connectivity by a mechanism of propagation from the departure node (Ns) to all the other nodes (Nn) of said multiplicity of nodes, so that each node (Nn) is visited.

39. Use of the method according to claim 1 in IP communication networks.

40. Use of the method according to claim 1 with link state routing protocols supporting TE-LSA traffic management.

20. A device for determining data routing paths (D) in a communication network including a multiplicity of nodes (Nn), which device is characterized in that it includes processing means (M) adapted to:

a) ensure that at least a portion of said multiplicity of nodes (Nn) are connected,

b) for said nodes of said portion, calculate possible paths (r*) between a departure node (Ns) and an arrival node (Nt), allowing for at least two chosen criteria, and then deducing an ideal solution (Z()) from performances (Z(r*)) of said possible paths (r*) based on said criteria,

c) assign each possible path (r*) a value of interest (U(r)) allowing for said ideal solution (Z()), and then classifying said possible paths allowing for their respective values of interest, and

d) select from said classified possible paths the k best classified paths, in order to route data via one of said k paths.

21. A device according to claim 20, characterized in that said processing means are adapted to begin by determining from said multiplicity of nodes (Nn) all the pairs of nodes that can establish between them an oriented link each supporting at least one chosen local constraint, after which it is ensured that all the nodes of said pairs are connected.

22. A device according to claim 20, characterized in that said processing means are adapted to retain from said possible paths (r*) those that each satisfy at least one chosen global constraint so that values of interest (U(r)) are assigned to said retained possible paths (r*).

23. A device according to claim 20, characterized in that at least one of said criteria is of the non-additive type.

24. A device according to claim 23, characterized in that said processing means (M) are adapted to integrate into the computation of said possible paths (r*) a trace storing a route corresponding to a partial path, in order to detect and prevent cycles in the paths under construction.

25. A device according to claim 24, characterized in that said processing means (M) are adapted to retain solutions that are “

weakly non-dominated”

on the non-additive criterion during the procedure of eliminating said partial paths.

27. A device according to claim 20, characterized in that said processing means (M) are adapted to determine representative values (Z(r)) of its “

performance”

for each path with respect to each of said chosen criteria and to qualify as a possible path (r*) a path (r) for which said performance values (Z(r)) are “

non-dominated”

.

28. A device according to claim 27, characterized in that said processing means (M) are adapted to determine the best performance value (Z*(r)) observed over said possible paths, referred to as the “

optimum value”

, for each criterion, and then to construct said ideal solution (Z()) in the form of a multiplet of components constituted of the various optimum values thus determined.

29. A device according to claim 28, characterized in that said processing means (M) are adapted to assign to each possible path (r) a value of interest (U(r)) that characterizes the greatest value of the components associated with the various chosen criteria of a weighted Tchebychev function of differences between the performance of said possible path (r*) and the corresponding optimum value of said ideal solution (Z()).

30. A device according to claim 29, characterized in that said k possible paths (r*) retained have the k lowest values of interest (U(r)).

31. A device according to claim 21, characterized in that said local and/or global constraints are selected from a group comprising at least the minimum bandwidth required, the maximum length of the path, the number of hops on the path, at least one prohibited link, and a path color restriction.

32. A device according to claim 20, characterized in that said criteria are selected from a group comprising at least the available bandwidth (C2), the number of hops on the path (C3), and the duration of the path (C1).

33. A device according to claim 32, characterized in that said chosen criteria comprise the available bandwidth (C2) and the duration of the path (C1).

34. A device according to claim 33, characterized in that said processing means (M) are adapted to impact said criterion relating to the duration of the path (C1) by a penalty.

35. A device according to claim 34, characterized in that said penalty applies to the administration cost (CA) of the path.

36. A device according to claim 20, characterized in that said criteria are chosen as a function of the type of service required.

37. A device according to claim 20, characterized in that said chosen criteria are weighted as a function of their importance in the light of management information.

38. A device according to claim 21, characterized in that said constraints and their associated values are chosen as a function of the quality of service required.