Load optimization

• US 20090031025A1
• Filed: 09/26/2008
• Published: 01/29/2009
• Est. Priority Date: 10/17/2000
• Status: Abandoned Application

• Current Assignee: Herbert S. Madan, James G. Mcguire, Jose-Miguel Puildo Villaverde, Mansour J. Karam, Michael A. Lloyd, Omar C. Baldonado, Sean P. Finn
• Original Assignee: Herbert S. Madan, James G. Mcguire, Jose-Miguel Puildo Villaverde, Mansour J. Karam, Michael A. Lloyd, Omar C. Baldonado, Sean P. Finn
• Inventors: Villaverde, Jose-Miguel Puildo, Baldonado, Omar C., Karam, Mansour J., Finn, Sean P., Lloyd, Michael A., McGuire, James G., Madan, Herbert S.
• Application Number:
  US12/286,019
• Publication Number:
  US 20090031025A1
• Time in Patent Office: Days
• 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 reduce the monetary cost of operating 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, based at least partly on the monitoring, of a degree of suboptimality with respect to one or more monetary billing structures of a second subset of two or more links in the network;

wherein at least one of the one or more monetary billing structures receives as input at least a second utilization of the second subset of two or more links; and

at least one of the one or more monetary billing structures includes at least variable cost; 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 decisions points to at least one link from a third subset of two or more links in the network; and

the adjusting attempts to reduce the degree of suboptimality.

2. The computer-usable medium of claim 1, wherein the first utilization of the first subset of two or more links is at least partly indicative of the second utilization of the second subset of two or more links.

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

1) the second subset of two or more links and

     2) the third subset of two or more links.

4. The computer-usable medium of claim 1, wherein at least one link from the second subset of two or more links is included in the third 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 at least one of:

1) the second subset of two or more links and

     2) the third subset of two or more links.

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

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

8. 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.

9. The computer-usable medium of claim 8, 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).

10. 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.

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

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

13. The computer-usable medium of claim 1, wherein each link of at least one link from the second 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.

14. The computer-usable medium of claim 13, wherein the second utilization and the third utilization are equal.

15. The computer-usable medium of claim 13, wherein the second utilization and the third utilization are unequal.

16. The computer-usable medium of claim 13, wherein the third utilization is being determined over time.

17. The computer-usable medium of claim 16, 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 second subset of two or more links.

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

19. 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.

20. The computer-usable medium of claim 13, wherein the assessing includes generating, from the at least one of the one or more monetary billing structures, one or more sets of functions, wherein at least one function in the one or more sets 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 fourth utilization of the at least one link from the first subset of two or more links.

21. The computer-usable medium of claim 20, wherein the first utilization and the fourth utilization are equal.

22. The computer-usable medium of claim 20, wherein the first utilization and the fourth utilization are unequal.

23. The computer-usable medium of claim 20, 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 at least one of the one or more monetary billing structures; and

constructing the one or more sets of functions based at least partly on the utilization distribution.

24. The computer-usable medium of claim 23, 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.

25. The computer-usable medium of claim 23, 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.

26. The computer-usable medium of claim 20, wherein the at least one function in the one or more sets of functions outputs at least a varying value.

27. The computer-usable medium of claim 26, wherein the at least one function in the one or more sets of functions is continuous or piecewise continuous with respect to the fourth utilization.

28. The computer-usable medium of claim 26, wherein the at least one function in the one or more sets of functions is non-decreasing with respect to the fourth utilization.

29. The computer-usable medium of claim 26, wherein the at least one function in the one or more sets of functions receives at least one input, the at least one input at least partly depending on the fourth 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.

30. The computer-usable medium of claim 26, wherein the at least one function in the one or more sets of functions receives at least one input, the at least one input at least partly depending on the fourth 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.

31. The computer-usable medium of claim 20, wherein the assessing includes:

selecting a first set of functions from the one or more sets of functions, wherein at least one function in the first set of functions gives the first degree of unacceptability; and

selecting a second 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) 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 of acceptable unacceptability.

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

33. The computer-usable medium of claim 31, wherein the assessing further includes determining a second degree of unacceptability based at least partly on the first degree of unacceptability.

34. The computer-usable medium of claim 33, 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.

35. The computer-usable medium of claim 31, the method 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.

36. The computer-usable medium of claim 35, wherein:

at least one function in the one or more sets of functions receives at least one input, the at least one input at least partly depending on the fourth 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,

wherein the method further comprises;

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

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

37. The computer-usable medium of claim 35, 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.

38. The computer-usable medium of claim 35, 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.

39. The computer-usable medium of claim 32, wherein the adjusting 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 points to at least a first link from the third subset of two or more links in the network;

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

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

40. The computer-usable medium of claim 1, 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.

41. The computer-usable medium of claim 40, 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 third subset of two or more links.

42. The computer-usable medium of claim 20,

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 third subset of two or more links; and

the assessing 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 third 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 or more winner sets; and

3) excluding, from the at least one or more winner sets, unwanted links, wherein the unwanted links have a third degree of unacceptability failing a second threshold of acceptable unacceptability, wherein the third degree of 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.

43. The computer-usable medium of claim 42, wherein the first threshold of acceptable unacceptability and the second threshold of acceptable unacceptability are equal.

44. The computer-usable medium of claim 42, wherein the first threshold of acceptable unacceptability and the second threshold of acceptable unacceptability are unequal.

45. The computer-usable medium of claim 42, 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.

46. The computer-usable medium of claim 42:

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.

47. The computer-usable medium of claim 42:

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.

48. The computer-usable medium of claim 42, 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 one or more winner sets, further comprises:

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

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

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

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

51. The computer-usable medium of claim 50, wherein the selecting of the forwarding decisions is at least partly random.

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

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

54. The computer-usable medium of claim 50:

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 third subset of two or more links; and

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

55. The computer-usable medium of claim 50, wherein the selecting of the subset of the forwarding decisions is based at least partly on a source external to the third subset of two or more links.

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

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

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

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

60-114. -114. (canceled)

115. A network of nodes configured to reduce the monetary cost of operating a 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 monitoring, a degree of suboptimality with respect to one or more monetary billing structures of a second subset of two or more links in the network;

wherein at least one of the one or more monetary billing structures is configured to receive as input at least a second utilization of the second subset of two or more links; and

at least one of the one or more monetary billing structures includes variable cost 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 assessing;

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

116. (canceled)

117. A method of reducing the monetary cost of operating a network, 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 one or more monetary billing structures of a second subset of two or more links in the network;

wherein at least one of the one or more monetary billing structures receives as input at least a second utilization of the second subset of two or more links; and

at least one of the one or more monetary billing structures includes at least variable cost; 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 decisions points to at least one link from a third subset of two or more links in the network; and

the adjusting attempts to reduce the degree of suboptimality.

118. (canceled)