Workload balancing between nodes in a cluster as required by allocations of IP addresses within a cluster

TECHNICAL FIELD

The present invention relates to clusters of nodes, wherein each node is a computer system, and more particularly for workload balancing of IP addresses allocated between the nodes in the cluster.

BACKGROUND OF RELATED ART

In the input of work to a cluster of nodes from network client sources, the cluster, whether it be real or virtual, is seen by the requesting clients as a single machine even though it is made up of several individual computers or servers, each being a cluster node. The cluster controlling server distributes the IP addresses (i.e., the service addresses of the distributed workload) across all of the nodes in Network Node Balancing wherein input from clients are shared among a plurality or even all of the nodes. Each node may have its own copy of an application, the work of which is distributed and share a database common to the cluster. Network load balancing is particularly significant in high demand Web sites on the Internet. However, Network Workload Balancing, particularly that of the present invention, is just as applicable to NAS services (CIFS or NFS) as well as, for example, FPT, HTTP and iSCSI. Such balancing distributes the current workload as evenly as possible across all of the cluster nodes. Each of the nodes may maintain its own copy of the network site so that if one of the nodes goes inactive, its workload may be redistributed to the other nodes in the cluster. Similarly, if the workload to the cluster increases, more nodes may be added to the cluster and workload from the existing nodes redistributed to the new nodes.

SUMMARY OF THE PRESENT INVENTION

It is noted that in the distribution or redistribution of workload from NIP addresses among M nodes in a cluster, the total number of possible solutions would be: M to the power of N. This would be an exhaustive determination for the optimal distribution of workload when M and N are large.

The present invention provides a simplified solution to workload balancing, of IP addresses allocated to the cluster from a plurality of client network sources that is based upon determinations of distances between IP addresses of work allocated to the cluster.

It should be noted that in current cluster technologies, such as cluster quorum wherein each node has a copy of the quorum database, longer distance clustering dispersement of nodes has become more practical. The present invention does provide a workload cluster node balancing optimization related to the distances between IP addresses allocated to the respective nodes in the cluster.

Accordingly, the present invention provides an implementation for balancing workload required to be allocated between the nodes in the cluster related to workload requests from clients via the network, determining, for each node in the cluster, an imbalance metric for each possible pairing of each IP address allocatable to the node based upon the distances between said IP addresses in each pairing and selectively allocating the IP addresses to the nodes in the cluster based upon minimizing the sum of the imbalance metrics of the nodes in the cluster resulting from the selected allocation of IP addresses.

The imbalance metric is more specifically determined by squaring the distances of all paired IP addresses allocated to the node and calculating the sum of all of said pairings for said node. In this calculation, the distance between a pair of IP addresses is the longest prefix, taken bitwise, common to each of the pair of addresses.

In accordance with a further aspect of this invention, IP addresses are dynamically reallocated from node to node is a result of changes to the sum of the imbalance metric as IP address inputs to the cluster change. In particular, responsive to newly allocating, an IP address to a node in the cluster, the increase in the imbalance metric for the node is determined by squaring the distances of the newly allocated IP address paired with each IP address allocated to the node, then calculating the sum of all of these squared distances of pairings for the node and adding the calculated sum to the existing imbalance metric of the node.

On the other hand, if a node in the cluster goes off-line, its IP addresses are reallocated to one of the remaining nodes in the cluster. This further includes determining the increase in the imbalance metric resulting from the reallocating the IP address to each remaining node in the cluster and reallocating the IP address to the node with the least increase of its imbalance metric.

In accordance with another aspect of this invention, responsive to removing an IP address from a node in the cluster, the decrease in the imbalance metric for the node is calculated by squaring the distances of the removed IP address paired with each remaining IP address allocated to the node, calculating the sum of all squared distances of the pairings for the node and then decreasing the calculated sum from the existing imbalance metric of the node.

Similarly, a removed address may be reallocated to another node in the cluster by determining the increase in the imbalance metric resulting from the reallocation of the removed address to each remaining node in the cluster and reallocating the IP address to the node with the least increase of its imbalance metric with respect to the decrease in the imbalance metric of the node from which the address is being removed.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention will be better understood and its numerous objects and advantages will become more apparent to those skilled in the art with reference to the following drawings, in conjunction with the accompanying specification, in which:

<figref idref="DRAWINGS">FIG. 1</figref> is a generalized diagrammatic view of a network portion, including a cluster of nodes and client sources on the network providing workload input to the cluster;

<figref idref="DRAWINGS">FIG. 2</figref> is an illustrative diagrammatic view of a control processor that may be used for any of the nodes in the cluster of <figref idref="DRAWINGS">FIG. 1</figref>, as well as for the control servers for the cluster;

<figref idref="DRAWINGS">FIG. 3</figref> is a general flowchart of a program set up to implement the present invention for balancing workload between nodes in a cluster; and

<figref idref="DRAWINGS">FIG. 4</figref> is a flowchart of an illustrative run of the program set up in <figref idref="DRAWINGS">FIG. 3</figref>.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Referring to <figref idref="DRAWINGS">FIG. 1</figref>, there is shown a generalized diagrammatic view of a network portion, showing the relationship of cluster <b>10</b> of nodes N<b>1</b>, N<b>2</b>, . . . N<b>5</b>, N<b>6</b>, . . . Nn. The distribution of workload to be subsequently described may be controlled by cluster server <b>11</b>. Alternately, any of the computer systems of nodes N<b>1</b> . . . Nn may provide the server function on which the workload balancing programs of this invention may be carried out. Nodes N<b>1</b> . . . Nn also share a common database <b>12</b>.

Clients S<b>1</b>, S<b>2</b>, S<b>3</b>, S<b>4</b> . . . Sn provide workload, over network <b>20</b>, that may be the World Wide Web through an appropriate gateway <b>13</b> to cluster <b>10</b> that is seen by the clients S<b>1</b> . . . Sn as a single address.

Each node N<b>1</b> through Nn respectively has a set <b>14</b>, <b>15</b>, <b>16</b>, <b>17</b> and <b>18</b> of addresses “A's” allocated to node.

The present invention provides its method and program for workload balancing (to be subsequently described). The invention is based upon workload balancing that relates the distances between the IP addresses of work assigned or allocated to selected nodes in the cluster. As will be hereinafter described in greater detail, allocation or reallocation of addresses is processed optimally when a node goes offline, a “fail over”, and its set of IP addresses are distributed to remaining nodes in the cluster; or when a node comes online, “fail back”, and a set of IP addresses are reallocated hack to the returning node; or when new IP addresses are to be allocated to nodes in a cluster.

With respect to <figref idref="DRAWINGS">FIG. 2</figref>, there is shown an illustrative diagrammatic view of a control processor that may be used for any of the nodes in the cluster of <figref idref="DRAWINGS">FIG. 1</figref>, as well as for the control servers for the cluster in <figref idref="DRAWINGS">FIG. 1</figref>. A central processing unit (CPU) <b>30</b>, such as one of the microprocessors or workstations, e.g. System p series available from International Business Machines Corporation (IBM) is provided and interconnected to various other components by system bus <b>12</b>. An operating system (OS) <b>41</b> runs on CPU <b>30</b>, provides control and is used to coordinate the function of the various components of <figref idref="DRAWINGS">FIG. 2</figref>. Operating system <b>41</b> may be one of the commercially available operating systems. Application programs <b>40</b>, controlled by the system, are moved into and out of the main memory Random Access Memory (RAM) <b>44</b>. These programming applications may be used to implement functions of the present invention in balancing cluster node workloads.

However, it is preferable that the programs used to implement the present invention be stored in a database <b>50</b> connected to CPU <b>30</b> and RAM <b>44</b> via bus <b>12</b>. ROM <b>46</b> includes the Basic Input/Output System (BIOS) that controls the basic computer functions of the computer. RAM <b>44</b>, storage adapter <b>48</b> and communications adapter <b>23</b> are also interconnected to system bus <b>12</b>. Storage adapter <b>48</b> communicates with the database <b>50</b>. Communications adapter <b>34</b> interconnects bus <b>12</b> with the outside or the cluster networks. I/O devices are also connected to system bus <b>12</b> via user interface adapter <b>25</b>. Keyboard <b>24</b> and mouse <b>26</b> may be connected to bus <b>12</b> through user interface adapter <b>25</b>. Display buffer <b>39</b> in display adapter <b>36</b> supports display <b>38</b>.

<figref idref="DRAWINGS">FIG. 3</figref> is a general flowchart of an illustrative program set up to implement the present invention for the optimum balancing of workload between the nodes in a cluster. Provision is made for such optimum balancing in a cluster of nodes connected via a network to a plurality of client sources of work. Provision is made for determining, for each node, the distances between the IP addresses of every possible pairing of such IP addresses of work allocated to the node, step <b>51</b>. Provision is made, step <b>52</b>, for calculating the square of each of the distances determined in step <b>51</b> for each node. Provision is made for totaling the sum of all of the squares of the distances calculated in step <b>52</b> wherein this sum is the imbalance metric of the node, step <b>53</b>. Provision is made for reallocating the IP addresses from node to node and dynamically recalculating the resulting imbalance metric for the nodes, step <b>54</b>. Provision is made for reallocating the addresses of a node that has gone off-line to a node the imbalance metric of which is least affected by the reallocating of in address, step <b>55</b>. Provision is made for reallocating the addresses of nodes within a cluster to balance the workload between nodes in the cluster by allocating an address to the node having the least increase in its imbalance metric with respect to the decrease in the imbalance metric of the node from which the IP address was removed, step <b>56</b>.

The IP address distances are thus used to determine the costs of assigning addresses to the same nodes. This IP address distance is based upon the longest common prefix of a pair of addresses taken bitwise. Therefore, this address distance calculation is applicable to most types of network addresses (including IPv4, IPv6 and IPX). The cost is measured as the imbalance metric for each node and is calculated as the sum of the squares of the address distance between each pair of addresses on the node. The algorithm that will subsequently be detailed is the Longest Common Prefix Squared (LCP2). In effect, the imbalance metric of a cluster may be defined as the maximum cost associated with its nodes. A cluster with a high imbalance metric is, thus, less balanced than a cluster with a lower imbalance metric.

When adding an IP address to a node, the incremental cost is calculated as the sum of the squares of the address distance between the IP address being added and each IP address already on the node. Likewise, when removing an IP address from a node, the decremental cost is calculated as the sum of the squares of the address distance between the IP address being removed and each IP address remaining on the node.

A simple illustrative example of a run of the process set up in <figref idref="DRAWINGS">FIG. 3</figref> is described with respect to the flowchart of <figref idref="DRAWINGS">FIG. 4</figref>. When running the algorithm, the affects, on the imbalance metrics of assigning IP addresses, are weighed in making the assignment. Then, “fail over” effect of reallocating the IP addresses of a node that goes off-line. Its IP addresses are moved to a pool of unallocated IP addresses. The incremental cost of adding each unallocated address to each on-line node is calculated. The algorithm ensures that the IP address/node combination with the lowest incremental cost is performed. This calculation is repeated until there are no unassigned addresses or no further assignment is possible.

Next, the fail-back effect when a node returns to on-line status first sets such a node as a target node and all of the other nodes in the cluster are source nodes of IP addresses for possible reallocation. Then the source node with the highest imbalance metric is selected and the decremental cost of removing each IP address is calculated. The incremental cost of moving each address from this source node to each target node and the resulting imbalance metric for the target node are calculated. The moving of IP addresses from a source to a target node is desirable if the resulting imbalance metric of the target node will be less than the initial imbalance metric of the source node. A reduction in the imbalance metric of the cluster is the object of the process. Of the possible desirable moves of IP addresses, the move with the lowest imbalance of the target node is selected. If there are no further desirable moves from a source node, the iteration involving a selected source is terminated, another source node is selected and the calculation for IP address moves is repeated.

An illustrative run is now described with respect to <figref idref="DRAWINGS">FIG. 4</figref>. In the routine operation of the cluster, a determination is made as to whether there is an IP address input to the cluster address <b>61</b>. If Yes, the imbalance metric for each cluster node is calculated as previously described in step <b>62</b> and the IP address is assigned to the node, wherein there would be the least effect on the imbalance metric, step <b>63</b>. Such routine assignment of IP addresses continues until a node in the cluster goes off-line (node fail-out), as indicated by a Yes decision in step <b>64</b>, i.e. if the decision is No, the process is branched back to step <b>61</b> wherein the routine processing of IP addresses is continued. However, if Yes, a node goes off-line, then a first IP address from the off-line node is assigned to the node with the least effect on the imbalance metric, step <b>65</b>, as previously described. This is continued with each next address in the off-line node until the last address in the node has been assigned as indicated by a Yes decision in step <b>66</b>, i.e. a No decision in step <b>66</b> results in a return to step <b>65</b> wherein more node IP addresses may be reassigned. However, if Yes, routine processing of assigning IP addresses input to the cluster to appropriate nodes as indicated by a No decision in step <b>67</b> as to whether a Node has returned on-line (fail-in). However, upon a Yes decision in step <b>67</b>, a node goes on-line, then, step <b>68</b>, an IP address from one of the other nodes having the high imbalance metric is assigned to the new node. This is continued with each next IP address in the other nodes until an optimum imbalance metric is achieved, a Yes in decision step <b>69</b> as previously described.

At this point, or at any point in the process, if there is a determination that the session is over, Yes, step <b>70</b>, the session is Exited. Otherwise, a No decision, the process is returned to step <b>61</b> via branch “A” and routine processing of input addresses is continued.

In the following sections, an example set of annotated instructions in Python object oriented language for the practice of the process of <figref idref="DRAWINGS">FIG. 4</figref> is set forth.

<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0" pgwide="1"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="273pt" align="center" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Code snippets:</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="273pt" align="left" /><tbody valign="top"><row><entry>def ip_to_list_of_ints(ip):</entry></row><row><entry> # Be lazy... but only expose errors in IPv4 addresses, since</entry></row><row><entry> # they'll be more commonly used. :-)</entry></row><row><entry> try:</entry></row><row><entry>  I = socket.inet_pton(socket.AF_INET6, ip)</entry></row><row><entry> except:</entry></row><row><entry>  I = socket.inet_pton(socket.AF_INET, ip)</entry></row><row><entry> return map(lambda x: struct.unpack:(‘B’, x)[0], I)</entry></row><row><entry>def ip_distance(ip1, ip2):</entry></row><row><entry> “““Calculate the distance between 2 IPs.</entry></row><row><entry> This is the length of the longest common prefix between the IPs.</entry></row><row><entry> It is calculated by XOR-ing the 2 IPs together and counting the</entry></row><row><entry> number of leading zeroes.”””</entry></row><row><entry> distance = 0</entry></row><row><entry> fo′(o1, o2) in zip(ip_to_list_of_ints(ip1), ip_to_list_of_ints(ip2)):</entry></row><row><entry>  # XOR this pair of octets</entry></row><row><entry>  x = o1 {circumflex over ( )} o2</entry></row><row><entry>  # count number leading zeroes</entry></row><row><entry>  if x == 0:</entry></row><row><entry>   distance += 8</entry></row><row><entry>  else:</entry></row><row><entry>   # bin( ) gives minimal length ‘0bNNN’ string</entry></row><row><entry>   distance += (8 − (len(bin(x)) − 2))</entry></row><row><entry>   break</entry></row><row><entry> return distance</entry></row><row><entry>def ip_distance_2_sum(ip, ips):</entry></row><row><entry> “““Calculate the IP distance for the given IP relative to IPs.</entry></row><row><entry> This could be made more efficient by inserting ip_distance_2 into</entry></row><row><entry> the loop in this function. However, that would result in some</entry></row><row><entry> loss of clarity and also will not be necessary in a C</entry></row><row><entry> implemntation.”””</entry></row><row><entry>  sum = 0</entry></row><row><entry>  for i in ips:</entry></row><row><entry>   sum += ip_distance(ip, i) ** 2</entry></row><row><entry>  return sum</entry></row><row><entry> def imbalance_metric(ips):</entry></row><row><entry>  “““Return the imbalance metric for a group of IPs.</entry></row><row><entry>  This is the sum of squares of the IP distances between each pair of IPs.”””</entry></row><row><entry>  if len(ips) &gt; 1:</entry></row><row><entry>   (h, t) = (ips[0], ips[1:])</entry></row><row><entry>   return ip_distance_2_sum(h, 1) + imbalance_metric(t)</entry></row><row><entry>self.events += 1</entry></row><row><entry># Don't bother with the num_healthy stuff. It is an</entry></row><row><entry># irrelevant detail.</entry></row><row><entry># We just keep the allocate IPs in the current_addresses field</entry></row><row><entry># of the node. This needs to readable, not efficient!</entry></row><row><entry>if self.deterministic_public_ips:</entry></row><row><entry> # Remap everything.</entry></row><row><entry> addr_list = sorted(list(self.all_public_ips))</entry></row><row><entry> for (i, ip) in enumerate(addr_list):</entry></row><row><entry>  self.quietly_remove_ip(ip)</entry></row><row><entry>  # Add addresses to new node.</entry></row><row><entry>  pnn = i % len(self.nodes)</entry></row><row><entry>  self.nodes[pnn].current_addresses.add(ip)</entry></row><row><entry>  verbose_print(“%s -&gt; %d” % (ip, pnn))</entry></row><row><entry># Remove public addresses from unhealthy nodes.</entry></row><row><entry>for (pnn, n) in enumerate(self.nodes):</entry></row><row><entry> if not n.healthy:</entry></row><row><entry>  verbose_print([“%s &lt;- %d” % (ip, pnn)</entry></row><row><entry>      for ip in n.current_addresses])</entry></row><row><entry>  n.current_addresses = set( )</entry></row><row><entry># If a node can't serve an assigned address then remove it.</entry></row><row><entry>fo′n in self.nodes:</entry></row><row><entry> verbose_print([“%s &lt;- %d” % (ip, pnn)</entry></row><row><entry>     for ip in n.current_addresses - n.public_addresses])</entry></row><row><entry> n.current_addresses &amp;= n.public_addresses</entry></row><row><entry>newly_healthy = [pnn for (pnn, n) in enumerate(self.nodes)</entry></row><row><entry>     if len(n.current_addresses) == 0 and n.healty]</entry></row><row><entry>for n in self.nodes:</entry></row><row><entry> n.set_imbalance( )</entry></row><row><entry># Assign as many unassigned addresses as possible. Keep</entry></row><row><entry># selecting the optimal assignment unt I we don't manage to</entry></row><row><entry># assign anything.</entry></row><row><entry>assigned = set([ip for n in self.nodes for ip in n.current_addresses])</entry></row><row><entry>unassigned = sorted(list(self.all_public_ips - assigned))</entry></row><row><entry>should_loop = True</entry></row><row><entry>while len(unassigned) &gt; 0 and should_loop:</entry></row><row><entry> should_loop = False</entry></row><row><entry>debug_begin(“ CONSIDERING MOVES (UNASSIGNED)”)</entry></row><row><entry>minnode = −1</entry></row><row><entry>mindsum = 0</entry></row><row><entry>minip = None</entry></row><row><entry>for ip in unassigned:</entry></row><row><entry> for dstnode in range(len(self.nodes)):</entry></row><row><entry>  if self.nodes[dstnode].can_node_serve_ip(ip) and \</entry></row><row><entry>    self.nodes[dstnode].healthy:</entry></row><row><entry>   dstdsum = ip_distance_2_sum(ip, self.nodes[dstnode].current_addresses,</entry></row><row><entry>   dstimbl = self.nodes[dstnode].get_imbalance( ) + dstdsum</entry></row><row><entry>   debug_print(“ %s -&gt; %d [+%d]” % \</entry></row><row><entry>       (ip,</entry></row><row><entry>        dstnode,</entry></row><row><entry>        dstimbl - self.nodes[dstnode].get_imbalance( )))</entry></row><row><entry>   if (minnode == −1) or (dstdsum &lt; mindsum):</entry></row><row><entry>    minnode = dstnode</entry></row><row><entry>    minimbl = dstimbl</entry></row><row><entry>    mindsum = dstdsum</entry></row><row><entry>    minip = ip</entry></row><row><entry>    should_loop = True</entry></row><row><entry>debug_end( )</entry></row><row><entry>if minnode != −1:</entry></row><row><entry> self.nodes[minnode].current_addresses.add(minip)</entry></row><row><entry> self.nodes[minnode].set_imbalance(self.nodes[minnode].get_imbalance( ) + mindsum)</entry></row><row><entry> verbose_print(“%s -&gt; %d [+%d]” % (minip, minnode, mindsum))</entry></row><row><entry> unassigned.remove(minip)</entry></row><row><entry>for ip in unassigned:</entry></row><row><entry> verbose_print(“Could not find node to take over public address %s” % ip)</entry></row><row><entry># Reassign as many IPs from heavily “loaded” nodes to nodes</entry></row><row><entry># that are newly healthy. Loop until we fail to reassign an</entry></row><row><entry># IP.</entry></row><row><entry>should_loop = True</entry></row><row><entry>while should_loop:</entry></row><row><entry> should_loop = False</entry></row><row><entry> if self.no_ip_failback:</entry></row><row><entry>  break</entry></row><row><entry> ##</entry></row><row><entry> if len(newly_healthy) == 0:</entry></row><row><entry>  return</entry></row><row><entry> if self.deterministic_public_ips:</entry></row><row><entry>  continue</entry></row><row><entry> # Get the node with the highest imbalance metric.</entry></row><row><entry> srcnode = −1</entry></row><row><entry> maximbl = 0</entry></row><row><entry> for (pnn, n) in enumerate(self.nodes):</entry></row><row><entry>  b = n.get_imbalance( )</entry></row><row><entry>  if (srcnode == −1) or (b &gt; maximbl):</entry></row><row><entry>  srcnode = pnn</entry></row><row><entry>  maximbl = b</entry></row><row><entry># This means that all nodes had 0 or 1 addresses, so can't</entry></row><row><entry># be imbalanced.</entry></row><row><entry>if maximbl == 0:</entry></row><row><entry>  break</entry></row><row><entry># We'll need this a few times...</entry></row><row><entry>ips = self.nodes[srcnode].current_addresses</entry></row><row><entry># Find an IP and destination node that best reduces imbalance.</entry></row><row><entry>optimum = None</entry></row><row><entry>debug_begin(“ CONSIDERING MOVES FROM %d [%d]” % (srcnode, maximbl))</entry></row><row><entry>for ip in ips:</entry></row><row><entry> # What is this IP address costing the source node?</entry></row><row><entry> srcdsum = ip_distance_2_sum(ip, ips - set([ip]))</entry></row><row><entry> srcimbl = maximbl - srcdsum</entry></row><row><entry> # Consider this IP address would cost each potential</entry></row><row><entry> # destination node. Destination nodes are limited to</entry></row><row><entry> # those that are newly healthy, since we don't want to</entry></row><row><entry> # do gratuitous failover of IPs just to make minor</entry></row><row><entry> # balance improvements.</entry></row><row><entry> for dstnode in newly_healthy:</entry></row><row><entry>  if self.nodes[dstnode].can_node_serve_ip(ip) and \</entry></row><row><entry>   self.nodes[dstnode].healthy:</entry></row><row><entry>  dstdsum = ip_distance_2_sum(ip, self.nodes[dstnode].current_addresses)</entry></row><row><entry>  dstimbl = self.nodes[dstnode].get_imbalance( ) + dstdsum</entry></row><row><entry>  debug_print(“ %d [%d] -&gt; %s -&gt; %d [+%d]” % \</entry></row><row><entry>        (srcnode,</entry></row><row><entry>         srcimbl - self.nodes[srcnode].get_imbalance( ),</entry></row><row><entry>         ip,</entry></row><row><entry>         dstnode,</entry></row><row><entry>         dstimbl - self.nodes[dstnode].get_imbalance( )))</entry></row><row><entry>   if (dstimbl &lt; maximbl) and (dstdsum &lt; srcdsum):</entry></row><row><entry>    if optimum is None:</entry></row><row><entry>     optimum = (ip, srcnode, srcimbl, dstnode, dstimbl)</entry></row><row><entry>    else:</entry></row><row><entry>     (x, sn, si, dn, di) = optimum</entry></row><row><entry>     if (srcimbl + dstimbl) &lt; (si + di):</entry></row><row><entry>       optimum = (ip, srcnode, srcimb , dstnode, dstimbl)</entry></row><row><entry>debug_end( )</entry></row><row><entry>if optimum is not None:</entry></row><row><entry>self.nodes[dstnode].set_imbalance(dstimbl)</entry></row><row><entry>verbose_print(“%d [%d] -&gt; %s -&gt; %d [+%d]” % \</entry></row><row><entry>      (srcnode,</entry></row><row><entry>     srcimbl - ini_srcimbl,</entry></row><row><entry>     ip,</entry></row><row><entry>     dstnode,</entry></row><row><entry>     dstimbl - ini_dstimbl))</entry></row><row><entry>should_loop = True</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment, including firmware, resident software, micro-code, etc.; or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit”, “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable mediums having computer readable program code embodied thereon.

Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared or semiconductor system, apparatus or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a Random Access Memory (“RAM”), a Read Only Memory (“ROM”), an Erasable Programmable Read Only Memory (“EPROM” or Flash memory), an optical fiber, a portable compact disc read only memory (“CD-ROM”), an optical storage device, a magnetic storage device or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain or store a program for use by or in connection with an instruction execution system, apparatus or device.

A computer readable medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electromagnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate or transport a program for use by or in connection with an instruction execution system, apparatus or device.

Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including, but not limited to, wireless, wire line, optical fiber cable, RE, etc., or any suitable combination the foregoing.

Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language, such as Java, Smalltalk, C++ and the like, and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the later scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (“LAN”) or a wide area network (“WAN”), or the connection may be made to an external computer (for example, through the Internet, using an Internet Service Provider).

Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer or other programmable data processing apparatus to produce a machine, such that instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified flowchart and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus or other devices to function in a particular manner; such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

The flowchart and block diagram in the Figures illustrate the architecture, functionality and operations of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustrations can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

Although certain preferred embodiments have been shown and described, it will be understood that many changes and modifications may be made therein without departing from the scope and intent of the appended claims.