Path determination in a data network

• US 6,956,821 B2
• Filed: 06/11/2001
• Issued: 10/18/2005
• Est. Priority Date: 01/30/2001
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Szentesi, Aron, Jüttner, Alpár, Szviatovszki, Balázs
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): WAHBA, ANDREW W
• Application Number:
  US09/877,206
• Publication Number:
  US 20020141345A1
• Time in Patent Office: 1,590 Days
• Field of Search: 370/237, 370/238, 370/238.1, 370/351, 370/400, 370/229, 370/230, 370/254, 370/255
• US Class Current: 370/237
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A path through a data network is calculated that accounts for priority levels of already-established paths. Potential new paths are determined taking into account priority level information associated with data network links. Of the determined paths, the path selected is preferably one having the least pre-emptive effect on lower priority traffic. The bandwidth reservation information for each data network link is determined along with the maximum bandwidth of each link and the available bandwidth at each priority level. Links with insufficient resources are eliminated from consideration. For the remaining candidate paths, determination for each link are make: which lower priority levels will be affected by the setup of the new path, how much reserved bandwidth will be pre-empted at each priority level, and how much free bandwidth is available at the lowers priority level. A path is selected that reduces or preferably minimizes some aspect of pre-emption.

Claims

1. A method for determining a new path through a data network that accounts for priority levels associated with established paths in the data network, wherein the paths are Label Switched Paths (LSPs) established using Multi-Protocol Label Switching (MPLS), comprising:

determining data network link attributes provided by various label switched routers in the data network;

storing the determined link attributes in a database;

determining a highest priority level on which preemption will occur to establish a new LSP;

determining a bandwidth that will be preempted by the new LSP;

determining a total bandwidth that will be preempted on all priority levels by the new LSP and the unreserved bandwidth at a lowest priority level; and

making a new LSP selection.

2. The method in claim 1, further comprising:

determining a priority level associated with the new LSP.

3. The method in claim 2, further comprising:

determining a resource requirement associated with the new LSP.

4. The method in claim 2, further comprising:

analyzing priority level information associated with data network links.

5. The method in claim 4, further comprising:

using the priority level information, selecting as the new LSP a LSP that has a minimal impact on established LSPs having a priority level lower than the priority level associated with the new LSP.

6. The method in claim 5, further comprising:

taking into account which or how many priority levels of established LSPs would be preempted by different LSP candidates.

7. The method in claim 1, further comprising:

selecting as the new LSP a shortest LSP from different LSP candidates having a requisite bandwidth and requisite priority with a least preemptive effect on established LSPs.

8. The method in claim 1, further comprising:

selecting as the new LSP a LSP that reduces preemption of lower priority established LSPs.

9. The method in claim 1, further comprising:

selecting as the new LSP a LSP that preempts a lowest priority level established LSP.

10. The method in claim 1, further comprising:

selecting as the new LSP a LSP that preempts a least amount of reserved resources of an established LSP.

11. The method in claim 1, further comprising:

selecting as the new LSP a LSP that preserves a largest amount of unreserved resources of an established LSP at a lowest priority level.

12. A method for selecting a new path through a data network that accounts for preemption of an established path in the data network by the new path, wherein the paths are Label Switched Paths (LSPs) established using Multi-Protocol Label Switching (MPLS), comprising:

determining data network link attributes provided by various label switched routers in the data network;

storing the determined link attributes in a database;

determining a highest priority level on which preemption will occur to establish a new LSP;

determining a bandwidth that will be preempted by the new LSP; and

determining a total bandwidth that will be preempted on all priority levels by the new LSP and the unreserved bandwidth at a lowest priority level; and

selecting the new LSP.

13. The method in claim 12, further comprising:

using one or more parameters to estimate the preemption.

14. The method in claim 13, wherein the one or more parameters include a maximum bandwidth for each link in the data network.

15. The method in claim 13, wherein the one or more parameters include a maximum reservable bandwidth for each link in the data network.

16. The method in claim 13, wherein the one or more parameters include an available bandwidth at each of multiple priority levels for each link in the data network.

17. The method in claim 12, further comprising:

selecting a LSP with a minimal number of preempted priority levels.

18. The method in claim 12, further comprising:

selecting a LSP with a minimal preempted bandwidth.

19. The method in claim 12, further comprising:

at a priority level that will be affected by the new LSP, selecting a LSP with a minimal bandwidth of the affected priority level.

20. The method in claim 12, further comprising:

selecting a LSP that maximizes unreserved bandwidth at a lowest priority level.

21. The method in claim 12, further comprising employing one or more of the following to reduce preemption:

(1) selecting a LSP that minimizes a number of preempted priority levels,

(2) selecting a LSP that minimizes a the total amount of preempted bandwidth,

(3) at an affected priority level, selecting a LSP that minimizes a bandwidth of the affected priority level, and

(4) selecting a LSP that maximizes unreserved bandwidth at a lowest priority level.

22. The method in claim 21, further comprising:

selecting a shortest LSP from candidate paths that satisfy one or more of (1)-(3).

23. The method in claim 12, wherein the data network link attributes are provided by Interior Gateway Protocol (IGP) extensions.

24. The method in claim 12, further comprising minimizing preemption of established LSP by performing one or more of the following:

(1) minimizing affected priority levels;

(2) at the affected priority level, minimizing the bandwidth preempted;

(3) maximizing unreserved bandwidth at a lowest priority level along the LSP; and

(4) any combination of (1)-(3).

25. A method for selecting a new path through a data network that reduces or minimizes a preemptive effect on one or more established paths in the data network by the new path, wherein the paths are Label Switched Paths (LSPs) established using Multi-Protocol Label Switching (MPLS), comprising:

determining data network link attributes provided by various label switched routers in the data network;

storing the determined link attributes in a database;

determining a hiahest priority level on which preemption will occur to establish a new LSP;

determining a bandwidth that will be preempted by the new LSP;

determining a total bandwidth that will be preempted on all priority levels by the LSP and the unreserved bandwidth at a lowest priority level; and

making a new LSP selection.

26. The method in claim 25, further comprising:

determining a priority level and a bandwidth associated with the new LSP.

27. The method in claim 26, further comprising:

determining bandwidth reservations for each link in the data network including a maximum bandwidth and an available bandwidth at each priority level.

28. The method in claim 27, further comprising:

eliminating links with insufficient resources to support the new LSP.

29. The method in claim 28, further comprising:

restricting remaining links to least cost LSPs.

30. The method in claim 28, further comprising:

for remaining paths, determining one or more of the following;

(1) which lower priority level or levels will be affected by set up of the new LSP, (2) how much reserved bandwidth will be preempted at each priority level by the new LSP, and (3) how much free bandwidth is available at a lowest priority level.

31. The method in claim 30, further comprising:

selecting from one or more of (1)-(3) a LSP that preempts the lowest priority level, the least amount of reserved bandwidth, or most amount of unreserved bandwidth at the lowest priority level.

32. The method in claim 25, wherein the path selection is made using a Constrained Shortest Path First (CSPF)-based algorithm.

33. Apparatus for determining a new path through a data network comprising:

a database for storing attributes for links in the data network including priority level information associated with the data network links, and

data processing circuitry coupled to the database and configured to determine the new path taking into account the priority level information associated with the data network links stored in the database;

wherein the paths are Label Switched Paths (LSPs) established using Multi-Protocol Label Switching (MPLS) and the database stores link attributes from various label switched routers in the data network, and wherein the data processing circuitry is configured to;

determine a highest priority level on which preemption will occur in establishing a new LSP;

determine a bandwidth that will be preempted by the new LSP;

determine a total bandwidth that will be preempted on all priority levels by the new LSP and the unreserved bandwidth at a lowest priority level; and

make a new LSP selection.

34. The apparatus in claim 33, wherein the data processing circuitry is configured to determine a priority level associated with the new LSP.

35. The apparatus in claim 34, wherein the data processing circuitry is configured to determine a resource requirement associated with the new LSP.

36. The apparatus in claim 34, wherein the data processing circuitry is configured to analyze priority level information associated with data network links.

37. The apparatus in claim 36, wherein the data processing circuitry is configured to use the priority level information in selecting as the new LSP a LSP that has a minimal impact on established LSPs having a priority level lower then the priority level associated with the new LSP.

38. The apparatus in claim 37, wherein the data processing circuitry is configured to take into account which or how many priority levels of established LSPs would be preempted by different LSP candidates.

39. The apparatus in claim 33, wherein the data processing circuitry is configured to select as the new LSP a shortest LSP from different LSP candidates having a requisite bandwidth and requisite priority with a least preemptive effect on established LSPs.

40. The apparatus in claim 33, wherein the data processing circuitry is configured to select as the new LSP a LSP that reduces preemption of lower established LSPs.

41. The apparatus in claim 33, wherein the data processing circuitry is configured to select as the new LSP a LSP that preempts lowest priority level established LSPs.

42. The apparatus in claim 33, wherein the data processing circuitry is configured to select as the new LSP a LSP that preempts a least amount of reserved resources of an established LSP.

43. The apparatus in claim 33, wherein the data processing circuitry is configured to select as the new LSP a LSP that preserves a largest amount of reserved resources of an established LSP at a lowest priority level.

44. A router for use in a data communications network, comprising:

path selection circuitry configured to determine a new path through the data network taking into account preemption information associated with data network links stored in the database;

data packet forwarding circuitry configured to forward data packets on established paths and

a database coupled to the oath selection circuitry for storing attributes for data network links,

wherein the paths are Label Switched Paths (LSPs) established using Multi-Protocol Label Switching (MPLS), wherein link attributes from various label switched routers in the data network are stored in the database, and wherein the path selection circuitry is configured to;

determine a highest priority level on which preemption will occur in establishing a new LSP;

determine a bandwidth that will be preempted by the new LSP;

determine a total bandwidth that will be preempted on all priority levels by the new LSP and the unreserved bandwidth at a lowest priority level; and

select a new LSP.

45. The router in claim 44, wherein the path selection circuitry is configured to use one or more attributes to estimate the preemption.

46. The router in claim 44, wherein the one or more attributes includes a maximum bandwidth for each data network link.

47. The router in claim 44, wherein the one or more attributes includes a maximum reservable bandwidth for each data network link.

48. The router in claim 44, wherein the one or more attributes includes an available bandwidth at each of multiple priority levels for each data network link.

49. The router in claim 44, wherein the path selection circuitry is configured to select a LSP that reduces a number of preempted priority levels.

50. The router in claim 44, wherein the path selection circuitry is configured to select a LSP that reduces a total amount of preempted bandwidth.

51. The router in claim 44, wherein at a priority level that will be affected by the new LSP, the path selection circuitry is configured to select a LSP that reduces a bandwidth of the affected priority level.

52. The router in claim 44, wherein the path selection circuitry is configured to select a LSP that reduces unreserved bandwidth at a lowest priority level.

53. The router in claim 44, wherein the path selection circuitry is configured to employ one or more of the following to reduce preemption by:

(1) selecting a LSP that minimizes a number of preempted priority levels,

(2) selecting a LSP that minimizes a total amount of preempted bandwidth,

(3) at an affected priority level, selecting a LSP that minimizes a bandwidth of the affected priority level, and

(4) selecting a LSP that maximizes unreserved bandwidth at a lowest priority level.

54. The router in claim 53, wherein the path selection circuitry is configured to select a shortest LSP from candidate paths that satisfy one or more of (1)-(3).

55. The router in claim 44, wherein the link attributes are provided by Internet Gateway Protocol (IGP) extensions.

56. The router in claim 44, wherein the path selection circuitry is configured to use link attributes in selecting the new LSP.

57. The router in claim 44, wherein the path selection circuitry is configured to employ a Constrained Shortest Path First (CSPF)-based algorithm to select the new LSP.

58. The router in claim 44, wherein the path selection circuitry is configured to minimize preemption of links by performing one or more of the following

(1) minimizing a number of priority levels along the LSP that will be affected by the new LSP;

(2) at an affected priority level, minimizing the bandwidth preempted;

(3) maximizing unreserved bandwidth at a lowest priority level along the LSP;

(4) any combination of (1)-(3).

59. A Label Switched Router (LSR), comprising:

means for storing attributes of links in a data network;

means for selecting a new path through a data network that minimizes a preemptive effect on one or more established paths in the data network by the new path; and

means for forwarding data packets on established paths,

wherein the oaths are Label Switched Paths (LSPs) established using Multi-Protocol Label Switching (MPLS), link attributes from various label switched routers in the data network are stored in the means for storing, and wherein means for selecting includes;

means for determining a highest priority level on which preemption establishing a new LSP;

means for determining a bandwidth that will be preempted by the new LSP;

means for determining a total bandwidth that will be preempted on all priority levels by the new LSP and the unreserved bandwidth at a lowest priority level; and

means for selecting the new LSP.

60. The LSR in claim 59, further comprising:

means for determining a priority level and a bandwidth associated with the new LSP.

61. The LSR in claim 60, further comprising:

means for determining bandwidth reservations for data network links including a maximum bandwidth and an available bandwidth at each priority level.

62. The LSR in claim 61, further comprising:

means for eliminating links with insufficient resources to support the new LSP.

63. The LSR in claim 62, further comprising:

means for restricting remaining links to least cost LSPs.

64. The LSR in claim 62, further comprising:

means for remaining links, determining one or more of the following;

(1) which lower priority level or levels will be affected by set up of the new LSP, (2) how much reserved bandwidth will be preempted at each priority level by the new LSP , and (3) how much free bandwidth is available at a lowest priority level.

65. The LSR in claim 64, further comprising:

means for selecting a LSP that preempts the lowest priority level, the least amount of reserved bandwidth, or most amount of unreserved bandwidth at the lowest priority level.