Load optimization

• US 7,487,237 B2
• Filed: 02/04/2003
• Issued: 02/03/2009
• Est. Priority Date: 10/17/2000
• Status: Expired due to Term

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: McGuire, James G., Finn, Sean P., Karam, Mansour J., Madan, Herbert S., Villaverde, Jose-Miguel Puildo, Baldonado, Omar C., Lloyd, Michael A.
• Primary Examiner(s): CHRISTENSEN, SCOTT B
• Assistant Examiner(s): Maniwang, Joseph
• Application Number:
  US10/358,681
• Publication Number:
  US 20040205098A1
• Time in Patent Office: 2,191 Days
• Field of Search: 709/224, 718/105
• US Class Current: 709/224
• CPC Class Codes: H04L 12/14 Charging , metering or billing arrangements for data wireline or wireless communications
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0826 for reduction of network costs H04L41/0833 takes precedence
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 41/508 based on type of value added network service under agreement
• CPC Class Codes: H04L 41/5096 wherein the managed service relates to distributed or central networked applications
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• 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/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/22 Alternate routing
• 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]
• CPC Class Codes: H04L 45/80 Ingress point selection by the source endpoint, e.g. selection of ISP or POP
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/283 : in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 67/1001 : for accessing one among a plurality of replicated servers

Abstract

Methods, computer code, and means are described that can control load in a network. In some applications, the monetary cost of operating the network can be reduced. Utilization of links in the network can be monitored. A degree of suboptimality with respect to some criteria can be assessed. In some instances, the criteria could be based at least partly one or more monetary billing structures of some subset of two or more links. A subset of the forwarding decisions of one or more forwarding nodes in the network can be adjusted automatically, based at least partly on the assessing. The adjustment can attempt to reduce the degree of suboptimality.

Claims

1. A computer-usable medium having computer-readable instructions stored thereon for execution by a processor to perform a method to ensure a desired load distribution in a network, the method comprising:

monitoring of at least a first utilization of a first subset of two or more links in the network;

assessing, base at least partly on the monitoring, of a degree of suboptimality with respect to the desired load distribution, wherein the degree of suboptimality corresponds to a measurable difference between a performance of determined load distribution and a performance of the desired load distribution, the assessing including;

generating at least two sets of functions; and

selecting a first set of functions from the at least two sets of functions;

wherein at least one function from the first set of functions gives a first degree of unacceptability of at least one link from the first subset of two or more links, wherein the first degree of unacceptability is based at least partly on a second utilization of the at least one link from the first subset of two or more links, wherein the first degree of unacceptability corresponds to a probability that adjusting a subset of forwarding decisions of one or more forwarding nodes in the network will decrease the measurable difference; and

the at least one function in the first set of functions outputs at least a varying value; and

selecting of a second set of functions from the at least two sets of functions if, for each function in the first set of functions that gives the first degree of unacceptability, the first degree of unacceptability fails a first threshold test; and

adjusting, automatically, of a subset of forwarding decisions of one or more forwarding nodes in the network based at least partly on the assessing;

wherein at least one forwarding decision from the subset of the forwarding decision corresponds to at least one link from a second subset of two or more links in the network; and

the adjusting includes attempting to reduce the degree of suboptimality.

2. The computer-usable medium of claim 1, wherein the first utilization and the second utilization are equal.

3. The computer-usable medium of claim 1, wherein the first utilization and the second utilization are unequal.

4. The computer-usable medium of claim 1, wherein at least one link from the first subset of two or more links is included in the second subset of two or more links.

5. The computer-usable medium of claim 1, wherein at least one link from the first subset of two or more links is not included in the second subset of two or more links.

6. The computer-usable medium of claim 1, wherein at least one of the monitoring, the assessing and the adjusting repeats.

7. The computer-usable medium of claim 1, wherein at least one of the forwarding decisions of the one or more forwarding nodes are described at least partly by at least one Layer 3 Protocol.

8. The computer-usable medium of claim 7, wherein at least one of the forwarding decisions of the one or more forwarding nodes are described at least partly by at least one Internet Protocol (IP).

9. The computer-usable medium of claim 1, wherein at least one of the forwarding decisions of the one or more forwarding nodes are described at least partly by at least one Layer 2 Protocol.

10. The computer-usable medium of claim 1, wherein the adjusting is described at least partly by at least one Border Gateway Protocol (BGP).

11. The computer-usable medium of claim 1, wherein the at least two sets of functions are generated from one or more monetary billing structures of a third subset of two or more links in the network.

12. The computer-usable medium of claim 11, wherein at least one link from the third subset of two or more links is included in at least one of:

1) the first subset of two or more links and

     2) the second subset of two or more links.

13. The computer-usable medium of claim 11, wherein at least one link from the third subset of two or more links is not included in at least one of:

1) the first subset of two or more links and

     2) the second subset of two or more links.

14. The computer-usable medium of claim 11, wherein at least one of the one or more monetary billing structures is for at least one Internet Service Provider (ISP).

15. The computer-usable medium of claim 11, wherein each link of at least one link from the third subset of two or more links has a third utilization, and at least one of the one or more monetary billing structures receives as input at least the third utilization.

16. The computer-usable medium of claim 15, wherein the first utilization of the first subset of two or more links is at least partly indicative of the third utilization of the third subset of two or more links.

17. The computer-usable medium of claim 15, wherein at least one of the first utilization and the second utilization is being determined over time.

18. The computer-usable medium of claim 17, wherein the third utilization is computed at least partly from

at least one of:

1a) a maximum and 1b) an average;

of at least one of;

2a) one or more percentiles and 2b) one or more averages;

and of one or more sets of utilization samples of the at least one link from the third subset of two or more links.

19. The computer-usable medium of claim 17, wherein the at least one of the one or more monetary billing structures is continuous or piecewise continuous with respect to the third utilization.

20. The computer-usable medium of claim 15, wherein the generating includes:

compiling a list of at least two sums, wherein at least one sum of the list adds at least two of the third utilizations;

determining, for a subset of the list, a utilization distribution based at least partly on the least one of the one or more monetary billing structures; and

constructing the at least two sets of functions based at least partly on the utilization distribution.

21. The computer-usable medium of claim 20, wherein the utilization distribution minimizes a monetary cost of operating the network, with respect to the at least one of the one or more monetary billing structures.

22. The computer-usable medium of claim 20, wherein the utilization distribution uses at least a steepest descent strategy with respect to the at least one of the one or more monetary billing structures.

23. The computer-usable medium of claim 1, wherein the monitoring uses one or more of Simple Network Monitoring Protocol (SNMP), flow information export, NetFlow, span port, and a source external to the first subset of two or more links.

24. The computer-usable medium of claim 1, wherein at least one function in the at least two sets of functions is continuous or piecewise continuous with respect to the second utilization.

25. The computer-usable medium of claim 1, wherein at least one function in the least two sets of functions is non-decreasing with respect to the second utilization.

26. The computer-usable medium of claim 1, wherein at least one function in the at least two sets of functions receives at least one input, the at least one input at least partly depending on the second utilization, wherein the at least one function outputs at least:

1)a first constant value for values of the at least one input up to a threshold value; and

2)a second constant value for values of the at least one input above the threshold value.

27. The computer-usable medium of claim 1, wherein at least one function in the at least two sets of functions receives at least one input, the at least one input at least partly depending on the second utilization, wherein the at least one function outputs at least:

1)a first constant value for values of the at least one input ranging from a second constant value to a third constant value,

2)a linear function of at least one input for values of the at least one input ranging from the third constant value to a fourth constant value, and

3)a fifth constant value for values of the at least one input exceeding the fourth constant value.

28. The computer-usable medium of claim 1, wherein the adjusting includes attempting to reduce the degree of suboptimality based on least partly on the first degree of unacceptability.

29. The computer-usable medium of claim 28, wherein the adjusting further includes attempting to reduce the degree of suboptimality by changing at least one forwarding decision from the subset of the forwarding decisions, wherein:

prior to the changing, the at least one forwarding decision from the subset of the forwarding decisions corresponds to at least a first link from the second subset of two or more links in the network;

after the changing, the at least one forwarding decision from the subset of the forwarding decisions corresponds to at least a second link from the second subset of two or more links in the network; and

wherein the first degree of unacceptability of the at least first link from the second subset is more unacceptable than the first degree of unacceptability of the at least the second link from the second subset.

30. The computer-usable medium of claim 1, wherein the assessing includes determining a second degree of unacceptability based at least partly on the first degree of unacceptability, wherein the second degree of unacceptability corresponds to a status of a link for routing over the network.

31. The computer-usable medium of claim 30, wherein the determining of the second degree of unacceptability includes treating the first degree of unacceptability as a probability value, and assigning, using the probability value, one of a plurality of states to the second degree of unacceptability.

32. The computer-usable medium of claim 1, further comprising:

ordering the one or more sets of functions into an ordered list of the one or more sets of functions; and

wherein the first set of functions and the second set of functions are adjacent in the ordered list of the one or more sets of functions.

33. The computer-usable medium of claim 32, wherein:

at least one function in the one or more sets of functions received at least one input, the at least one input at least partly depending on the second utilization, wherein the at least one function outputs at least;

1)a first constant value for values of the at least one input ranging from a second constant value to a third constant value;

2)a linear function of at least one input for values of the at least one input ranging from the third constant value to a fourth constant value; and

3)a fifth constant value for values of the at least one input exceeding the fourth constant value, further comprising;

computing, for each set of functions in the one or more sets of functions, a level, wherein the level is based at least partly on a sum of at least the fourth constant values across the one or more functions in each set of functions; and

performing the ordering based at least partly on the level computed for each set of functions.

34. The computer-usable medium of claim 32, wherein the sum of at least the fourth constant values across the one or more functions in each set of functions, sums at least one function of the one or more functions in each set of functions.

35. The computer-usable medium of claim 32, wherein the sum of the fourth constant values across the one or more functions in each set of functions, sums all functions of the one or more functions in each set of functions.

36. The computer-usable medium of claim 1, wherein at least one forwarding decision from the subset of forwarding decisions at least partly influences one or more objects, wherein the one or more objects includes one of a prefix, a flow and a network application.

37. The computer-usable medium of claim 36, wherein the assessing is further based at least partly on quality characterizations of the one or more objects, wherein the quality characterizations are with respect to at least one link from the second subset of two or more links.

38. The computer-usable medium of claim 36, wherein the assessing further includes:

selecting at least one object from the one or more objects;

selecting at least one set of functions from the one or more sets of functions; and

constructing one or more winner sets for the at least one object and the least one set of functions, wherein each winner set from the one or more winner sets includes a corresponding quality characterization threshold, wherein the constructing includes;

1)including in at least one of the one or more winner sets one or more links from the second subset of two or more links;

2)excluding, from the at least one or more winner sets, links for which the quality characterizations of the at least one object fails the corresponding quality characterization threshold included by each winner set from the one ore more winner sets; and

3)excluding, from the at least one or more winner sets, unwanted links, wherein the unwanted links have a second threshold of acceptable unacceptability, wherein the second threshold of acceptable unacceptability is based at least partly on the first degree of unacceptability given by the at least one set of functions; and

selecting one or more links from a non-empty winner set from the one or more winner sets, wherein the non-empty winner set has a low corresponding quality characterization threshold from all corresponding quality characterization thresholds included by all winner sets from the one or more winner sets.

39. The computer-usable medium of claim 38, wherein the first threshold test and the second threshold test are equal.

40. The computer-usable medium of claim 38, wherein the first threshold test and the second threshold test are unequal.

41. The computer-usable medium of claim 38, wherein the low corresponding quality characterization threshold is the lowest corresponding quality characterization threshold from all corresponding quality characterization thresholds included by all winner sets from the one or more winner sets.

42. The computer-usable medium of claim 38, wherein:

the constructing of a first one or more winner sets is done for a third set of functions from the one or more sets of functions; and

the constructing of a second one or more winner sets is done for a fourth set of functions from the one or more sets of functions if;

1) the one or more sets of functions includes at least two sets of functions; and

2) all of the first one or more winner sets are empty.

43. The computer-usable medium of claim 38:

wherein the constructing of a first one or more winner sets is done for a first object from the one or more objects; and

the constructing of a second one or more winner sets is done for a second object from the one or more objects if;

1) the one or more objects includes at least two objects, and

2) all of the first one or more winner sets are empty.

44. The computer-usable medium of claim 38, wherein the excluding, from the at least one or more winner sets, links for which the quality characterizations of the at least one object fails the corresponding quality characterization threshold included by each winner set from the at least one or more winner sets is further comprised of:

identifying at least one best link from the one or more links from the second subset of two or more links, wherein the at least one best link has a high quality characterization from at least one or more links from a second subset of two or more links, and

determining the corresponding quality characterization threshold based at least partly on the high quality characterization.

45. The computer-usable medium of claim 44, wherein the high quality characterization is the highest quality characterization from the at least one of the one or more links from the second subset of two or more links.

46. The computer-usable medium of claim 1, further including selecting the subset of the forwarding decisions of one or more forwarding nodes automatically.

47. The computer-usable medium of claim 46, wherein the selecting of the subset of the forwarding decisions is at least partly random.

48. The computer-usable medium of claim 46, wherein the selecting of the subset of the forwarding decisions is independent from the assessing.

49. The computer-usable medium of claim 46, wherein the selecting of the subset of the forwarding decisions uses a flow monitoring device.

50. The computer-usable medium of claim 46,

wherein at least one forwarding decision from the subset of the forwarding decisions at least partly influences one or more objects, wherein the one or more objects includes at least one of a prefix, a flow, and a network application;

the assessing is further based at least partly on quality characterizations of the one or more objects, wherein the quality characterizations are with respect to at least one link from the second subset of two or more links; and

the selecting of the subset of the forwarding decisions is based at least partly on a measuring of the quality characterizations of the one or more objects.

51. The computer-usable medium of claim 46, wherein the selecting of the subset of the forwarding decisions is based partly on a source external to the second subset of two or more links.

52. The computer-usable medium of claim 1, wherein the computer code is at least partly software.

53. The computer-usable medium of claim 1, wherein the computer code is all software.

54. The computer-usable medium of claim 1, wherein the computer code is at least partly hardware.

55. The computer-usable medium of claim 1, wherein the computer code is all hardware.

56. The computer-usable medium of claim 1, wherein the performance is a cost incurred by a load distribution.

57. A network of nodes configured to ensure a desired load distribution in a network, the network comprising:

means for monitoring at least a first utilization of a first subset of two or more links in the network;

means for assessing, based at least partly on the means for monitoring, a degree of suboptimality with respect to the desired load distribution, wherein the degree of suboptimality corresponds to a measurable difference between a performance of determined load distribution and a performance of the desired load distribution, wherein the means for assessing is configured to;

generate a list of at least two sets of functions;

select a first set of functions from the list of at least two sets of functions

wherein at least one function from the first set of functions gives a first degree of unacceptability of at least one link from the first subset of two or more links, wherein the first degree of unacceptability is based at least partly on a second utilization of the at least one link from the first subset of two or more links, wherein the first degree of unacceptability is based at least partly on a second utilization of the at least one link from the first subset of two or more links, wherein the first degree of unacceptability corresponds to a probability that adjusting a subset of forwarding decisions of one or more forwarding nodes in the network will decrease the measurable difference, and at least one function in the first set of functions outputs at least a varying value, and

selecting a second set of functions from the at least two sets of functions if;

1) at least one function in the first set of functions gives the first degree of unacceptability; and

2) for each function in the first set of functions that gives the first degree of unacceptability, the first degree of unacceptability fails a first threshold test, and

means for adjusting automatically a subset of the forwarding decisions of one or more forwarding nodes in the network based at least partly on the means for assessing;

wherein at least one forwarding decision from the subset of the forwarding decisions corresponds to at least one link from a second subset of two or more links in the network, the means for adjusting attempts to reduce the degree of suboptimality.

58. A method of attempting to ensure a desired load distribution in a network, the method comprising

monitoring at least a first utilization of a first subset of two or more links in the network;

assessing, based at least partly on the monitoring, a degree of suboptimality with respect to the desired load distribution, wherein the degree of suboptimality corresponds to a measurable difference between a performance of determined load distribution and a performance of the desired load distribution, the assessing including;

generating at least two sets of functions; and

selecting a first set of functions from the at least two sets of functions

wherein at least one function from the first set of functions gives a first degree of unacceptability of at least one link from the subset of two or more links, wherein the first degree of unacceptability is based at least partly on a second utilization of the at least one link from the first subset of two or more links, wherein the first degree of unacceptability corresponds to a probability that adjusting a subset of forwarding decisions of one or more forwarding nodes in the network will decrease the measurable difference; and

the at least one function in the first set of functions outputs at least a varying value;

selecting a second set of functions from the at least two sets of functions if, for each function in the first set of functions that gives the first degree of unacceptability, the first degree of unacceptability fails a first threshold test; and

adjusting automatically a subset of forwarding decisions of one or more forwarding nodes in the network based at least partly on the assessing;

wherein at least one forwarding decision from the subset of the forwarding decision corresponds to at least one link from a second subset of two or more links in the network; and

the adjusting includes attempting to reduce the degree of suboptimality.

59. A method of controlling load distributions on a computer network having multiple nodes coupled by multiple links, the method comprising:

monitoring load distributions on a first subset of the multiple nodes on the network;

generating from one or more billing structures corresponding first and second sets of unacceptability functions, wherein the first set of functions is used to determine first amounts that measurable performances associated with the monitored load distributions differ from a first threshold and the second set of functions is used when the first amounts all exceed the first threshold and is used to determine second amounts that measurable performances associated with the monitored load distributions differ from a second threshold;

wherein the first set of functions generates a probability value that a measure of a first use on a first subset of the multiple links has a value that differs from a threshold; and

automatically adjusting forwarding decisions on a second subset of the multiple nodes based on the first or the second amounts, thereby controlling load distributions on the computer network.

60. The method of claim 59, wherein the first subset of nodes is different from the second subset of nodes.

61. The method of claim 59, wherein the first use corresponds to a load.

62. The method of claim 59, wherein the first use corresponds to a load on one of the multiple links per a capacity of the one link.

63. The method of claim 59, wherein the second set of functions assigns a link from the multiple links to one of two states, wherein the one of the two states corresponds to a winner set from which links are selected for forwarding.

64. The method of claim 59, wherein generating the first set of functions comprises:

determining a list of sums of load, wherein at least one sum in the list corresponds to the sums of different combinations of load on the multiple links;

determining, for different values of sums of load, an optimal distribution of use on one of the multiple links; and

constructing the two sets of functions based at least partly on the optimal distribution of use.