Constraint-based route selection using biased cost

• US 6,363,319 B1
• Filed: 08/31/1999
• Issued: 03/26/2002
• Est. Priority Date: 08/31/1999
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Hsu, Ivy P.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): PIPALA, EDWARD J
• Application Number:
  US09/387,036
• Time in Patent Office: 938 Days
• Field of Search: 701/202, 701/209, 370/235, 370/238, 370/351, 709/238, 709/241
• US Class Current: 701/202
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5669 Multiprotocol over ATM [MPOA]
• 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/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04W 48/18 Selecting a network or a communication service
• CPC Class Codes: H04W 76/20 Manipulation of established connections

Abstract

The present invention is a method and apparatus for selecting a route for a flow from a plurality of network paths connecting a source to a destination. The method comprises: (a) determining cumulative costs for a plurality of candidate paths from the network paths using a cost bias which is dynamically calculated based on at least one of a flow attribute and a path attribute; and (b) selecting an optimal path having a minimum of the cumulative costs. The optimal path corresponds to the selected route.

Claims

1. A method to select a route for a flow from a plurality of network paths, comprising:

determining cumulative costs for a plurality of candidate paths from the network paths using a cost bias, the cost bias being dynamically calculated based on at least one of a flow attribute characterizing the flow and a path attribute; and

selecting an optimal path having a minimum of the cumulative costs, the optimal path corresponding to the route.

2. The method of claim 1 wherein the flow attribute includes a flow priority and a bandwidth demand.

3. The method of claim 2 wherein the path attribute includes a link bandwidth and a maximum available link bandwidth.

4. The method of claim 3 further comprising:

determining a path bandwidth associated with each of the candidate paths.

5. The method of claim 3 wherein determining the cumulative costs comprises:

selecting a candidate node for a current node in each of the candidate paths not previously included in the corresponding candidate path, the candidate node and the current node being connected in a link having the link bandwidth satisfying the bandwidth demand, the candidate node having a candidate biased cumulative cost less than a previous biased cumulative cost.

6. The method of claim 4 wherein selecting the optimal path comprises:

if there are more than one minimum of the cumulative costs, selecting the optimal path having the minimum of the cumulative costs and a maximum path bandwidth.

7. The method of claim 6 wherein the candidate biased cumulative cost includes a current cumulative cost and a biased static cost, the biased static cost including a static cost of the link biased by a bias value.

8. The method of claim 7 wherein the bias value is a function of the flow priority, the bandwidth demand, the link bandwidth, and the maximum available link bandwidth.

9. The method of claim 7 wherein a decrease in flow priority increases the bias value.

10. The method of claim 7 wherein an increase in link bandwidth decreases the bias value.

11. The method of claim 7 wherein an increase in bandwidth demand increases the bias value.

12. The method of claim 7 wherein the bias value is greater than or equal to 1.

13. The method of claim 6 further comprising:

rejecting the selected optimal path if the minimum of the cumulative costs exceeds an admission threshold.

14. The method of claim 6 wherein the plurality of network paths include an intra-area segment and an inter-area segment.

15. The method of claim 14 wherein the cumulative costs in the inter-area segment exclude the cost bias.

16. The method of claim 14 wherein the inter-area segment has the same cost bias for the candidate paths.

17. A computer program product comprising:

a computer usable medium having computer program code embodied therein to select a route for a flow from a plurality of network paths, the computer program product having;

computer readable program code for determining cumulative costs for a plurality of candidate paths from the network paths using a cost bias, the cost bias being dynamically calculated based on at least one of a flow attribute characterizing the flow and a path attribute; and

computer readable program code for selecting an optimal path having a minimum of the cumulative costs, the optimal path corresponding to the selected route.

18. The computer program product of claim 17 wherein the flow attribute includes a flow priority and a bandwidth demand.

19. The computer program product of claim 17 the path attribute includes a link bandwidth and a maximum available link bandwidth.

20. The computer program product of claim 19 further comprising:

computer readable program code for determining a path bandwidth associated with each of the candidate paths.

21. The computer program product of claim 17 wherein the computer readable program code for determining the cumulative costs comprises:

computer readable program code for selecting a candidate node for a current node in each of the candidate paths not previously included in the corresponding candidate path, the candidate node and the current node being connected in a link having the link bandwidth satisfying the bandwidth demand, the candidate node having a candidate biased cumulative cost less than a previous biased cumulative cost.

22. The computer program product of claim 20 wherein the computer readable program code for selecting the optimal path comprises:

computer readable program code for selecting the optimal path having the minimum of the cumulative costs and a maximum path bandwidth if there are more than one minimum of the cumulative costs.

23. The computer program product of claim 22 wherein the candidate biased cumulative cost includes a current cumulative cost and a biased static cost, the biased static cost including a static cost of the link biased by a bias value.

24. The computer program product of claim 23 wherein the bias value is a function of the flow priority, the bandwidth demand, the link bandwidth, and the maximum available link bandwidth.

25. The computer program product of claim 23 wherein a decrease in flow priority increases the bias value.

26. The computer program product of claim 23 wherein an increase in link bandwidth decreases the bias value.

27. The computer program product of claim 23 wherein an increase in bandwidth demand increases the bias value.

28. The computer program product of claim 23 wherein the bias value is greater than or equal to 1.

29. The computer program product of claim 22 further comprising:

rejecting the selected optimal path if the minimum of the cumulative costs exceeds an admission threshold.

30. The computer program product of claim 22 wherein the plurality of network paths include an intra-area segment and an inter-area segment.

31. The computer program product of claim 30 wherein the cumulative costs in the inter-area segment exclude the cost bias.

32. The computer program product of claim 31 wherein the inter-area segment has the same cost bias for the candidate paths.

33. A system comprising:

a processor; and

a memory coupled to the processor, the memory containing program code to select a route for a flow from a plurality of network paths, the program code when executed causing the processor to determine cumulative costs for the network paths using a cost bias, the cost bias being dynamically calculated based on at least one of a flow attribute characterizing the flow and a path attribute, and

select an optimal path having a minimum of the cumulative costs, the optimal path corresponding to the route.

34. The system of claim 33 wherein the flow attribute includes a flow priority and a bandwidth demand.

35. The system of claim 33 wherein the path attribute includes a link bandwidth and a maximum available link bandwidth.

36. The system of claim 33 wherein the program code further causing the processor to determine a path bandwidth associated with each of the candidate paths.

37. The system of claim 33 wherein the program code determining the cumulative costs causes the processor to select a candidate node for a current node in each of the candidate paths not previously included in the corresponding candidate path, the candidate node and the current node being connected in a link having the link bandwidth satisfying the bandwidth demand, the candidate node having a candidate biased cumulative cost less than a previous biased cumulative cost.

38. The system of claim 37 wherein the program code selecting the optimal path causes the processor to:

select the optimal path having the minimum of the cumulative costs and a maximum path bandwidth if there are more than one minimum of the cumulative costs.

39. The system of claim 38 wherein the candidate biased cumulative cost includes a current cumulative cost and a biased static cost, the biased static cost including a static cost of the link biased by a bias value.

40. The system of claim 39 wherein the bias value is a function of the flow priority, the bandwidth constraint, the link bandwidth, and the maximum available link bandwidth.

41. The system of claim 39 wherein a decrease in flow priority increases the bias value.

42. The system of claim 39 wherein an increase in link bandwidth decreases the bias value.

43. The system of claim 39 wherein an increase in bandwidth demand increases the bias value.

44. The system of claim 39 wherein the bias value is greater than or equal to 1.

45. The system of claim 38 wherein the program code further causing the processor to reject the selected optimal path if the minimum of the cumulative costs exceeds an admission threshold.

46. The system of claim 38 wherein the plurality of network paths include an intra-area segment and an inter-area segment.

47. The system of claim 46 wherein the cumulative costs in the inter-area segment exclude the cost bias.

48. The system of claim 46 wherein the inter-area segment has the same cost bias for the candidate paths.