Load optimization

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.

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 . (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)