Dynamic network load balancing using roundtrip heuristic

• US 8,799,918 B2
• Filed: 09/11/2006
• Issued: 08/05/2014
• Est. Priority Date: 09/11/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sen, Siddhartha
• Primary Examiner(s): Kawsar, Abdullah Al
• Application Number:
  US11/518,673
• Publication Number:
  US 20080066073A1
• Time in Patent Office: 2,885 Days
• Field of Search: 709/223, 709/226, 718/105
• US Class Current: 718/105
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs

Abstract

Described is a technology by which a relative load of network traffic handling is determined between servers of a cluster, based upon time values that correspond to the time taken by each server to handle a packet. Load may then be transferred between the servers based upon the relative load, for example by having a less-loaded server take some of the responsibility for processing incoming traffic from a more-loaded server. For example, the processing time of a server may be determined by when a receiving server receives a request packet, and when that server sends a return packet. A round trip time for a request and return communication may also be established. A logical tree of nodes representing the servers may be constructed to select pairs of servers for balancing with one another, with the selection algorithm operating recursively, in parallel, and/or repeatedly, until the cluster is balanced.

Claims

1. A method, comprising:

using a processor of a first server of a cluster, selecting a second server for load balancing with the first server using a tree-based, recursive algorithm;

determining a relative load between the first server and the second server of the cluster based upon a first time value that corresponds to a quantity of time taken by the first server to handle a packet set comprising at least one packet measured as a difference between a timestamp associated with a response to the packet set sent by the first server and a timestamp associated with receipt of the packet set by the first server, the packet set exercising a longest packet-processing path in the first server, and a second time value corresponding to a quantity of time taken by the second server to handle a packet set comprising at least one packet measured as a difference between a timestamp associated with a response to the packet set sent by the second server and a timestamp associated with receipt of the packet set by the second server, wherein each of the first server and the second server comprises a packet handing selection mechanism and each of the packet handling selection mechanism includes a plurality of values in which each value is used to determine whether to handle an incoming request based on a hash of an IP (Internet Protocol) address associated with that incoming request; and

transferring, by the first server, at least some load from the first server to the second server based upon the relative load by altering values of the packet handling selection mechanism of the first server and the second server.

2. The method of claim 1 wherein determining the relative load comprises sending the packet set from the first server to the second server, and for each packet sent to the second server, determining a round trip time for a return packet received back from the second server.

3. The method of claim 1 wherein transferring at least some load between the first server and second server comprises moving at least one value corresponding to one or more connections between the first and the second server.

4. The method of claim 1 wherein third and fourth servers of the cluster perform load balancing by similarly determining another relative load between the third and fourth servers and transferring at least some load between the third and fourth servers based on the other relative load, and having further computer-executable instructions comprising, after transferring at least some load between the first server and second server, and after transferring at least some load between the third server and fourth server, determining a new relative load between the first and third servers of the cluster, and transferring at least some load between the first server and the third server based on the new relative load.

5. The method of claim 4 having further computer-executable instructions comprising constructing a logical tree of nodes representing the servers to establish which server is the first server, which server is the second server, which server is the third server, and which server is the fourth server.

6. In a cluster of servers, a method comprising:

selecting by a first server of the cluster, a second server of the cluster for load balancing with the first server using a tree-based, recursive algorithm;

measuring, by a first server, a first time for the first server to handle a packet set comprising at least one packet, the first time measured as a difference between a timestamp associated with a response to the packet set sent by the first server and a timestamp associated with receipt of the packet set by the first server;

determining, by the first server, a second time for a second server to handle another packet set comprising at least one packet, the second time determined as a difference between a timestamp associated with a response to the packet set sent by the second server and a timestamp associated with receipt of the packet set by the second server, wherein each of the first server and the second server comprises a packet handing selection mechanism and each of the packet handling selection mechanism includes a plurality of values in which each value is used to determine whether to handle an incoming request based on a hash of an IP (Internet Protocol) address associated with that incoming request; and

assigning responsibility for handling incoming network traffic to the first server and the second server, by the first server, based upon the first and second times by altering values of the packet handling selection mechanism of the first server and the second server.

7. The method of claim 6 wherein measuring the second time comprises sending a request packet from the first server to the second server.

8. The method of claim 6 wherein measuring the first time comprises sending a packet from the first server to the first server to determine a first processing time.

9. The method of claim 6 wherein assigning responsibility for handling incoming network traffic comprises determining a first subset of at least one value corresponding to connections that the first server is responsible for handling, and determining a second, other subset of at least one other value corresponding to other connections that the second server is responsible for handling, based upon the first and second times.

10. In a cluster of servers that share handling of network traffic load, a computing device comprising:

a first server comprising a processor coupled to a memory, the memory storing a load balancing component that;

selects a second server for load balancing with the first server using a tree-based, recursive algorithm;

measures a packet handling time of the first server as a difference between a timestamp associated with a response to a packet set sent by the first server and a timestamp associated with receipt of the packet set by the first server and determines a packet handling time of the second server as a difference between a timestamp associated with a response to the packet set sent by the second server and a timestamp associated with receipt of the packet set by the second server;

determines a relative load between the first server and a second server of the cluster based on the packet handling times taken by those servers, wherein each of the first server and the second server comprises a packet handing selection mechanism and each of the packet handling selection mechanism includes a plurality of values in which each value is used to determine whether to handle an incoming request based on a hash of an IP (Internet Protocol) address associated with that incoming request; and

the first server load balances the network traffic load between the servers based on the relative load by altering values of the packet handling selection mechanism of the first server and the second server.

11. The computing device of claim 10 wherein the load balancing component includes an instance that runs in each of the servers.

12. The computing device of claim 10 wherein the load balancing component comprises a driver that runs in a network stack.

13. The computing device of claim 10 wherein the load balancing component runs in the first server, and further comprising a load responder component that runs in the second server to respond to requests from the load balancing component.

14. The computing device of claim 10 wherein each server is associated with a filter mechanism that determines which network traffic to process, and wherein the load balancing component balances the network traffic load by communicating filtering data to the filtering mechanism.

15. The computing device of claim 10 wherein at least two pairs of servers are balanced substantially in parallel.