Dynamic network load balancing using roundtrip heuristic

• US 20080066073A1
• Filed: 09/11/2006
• Published: 03/13/2008
• Est. Priority Date: 09/11/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sen, Siddhartha
• Granted Patent: US 8,799,918 B2
• Time in Patent Office: Days
• 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. At least one computer-readable media having computer-executable instructions, which when executed perform steps, comprising:

determining a relative load between first and second servers of a cluster based upon a first time value that corresponds to how much time is taken by the first server to handle a packet set comprising at least one packet, and a second time value corresponding to how much time is taken by the second server to handle a packet set comprising at least one packet; and

transferring at least some load between the first server and second server based upon the relative load.

2. The computer-readable media of claim 1 wherein determining the relative load comprises sending the packet set from the first server to the second server, and for each received packet at the second server, associating a second server processing time with a return packet that corresponds to the received packet.

3. The computer-readable media of claim 2 wherein associating the second server processing time with the return packet comprises, stamping the received packet with a received time, modifying the received packet into the return packet, and stamping the return packet with the sending time.

4. The computer-readable media 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.

5. The computer-readable media 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.

6. The computer-readable media 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.

7. The computer-readable media of claim 6 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.

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

measuring a first time for a first server to handle a packet set comprising at least one packet;

measuring a second time for a second server to handle another packet set comprising at least one packet; and

assigning responsibility for handling incoming network traffic based upon the first and second times.

9. The method of claim 8 wherein measuring the second time comprises sending a request packet from the first server to the second server, and in response, receiving a return packet from the second server at the first server, and determining when the request packet was received at the second server and when the return packet was sent by the second server.

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

11. The method of claim 8 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.

12. The method of claim 11 wherein determining the first and second subsets comprising moving at least one value from the first subset to the second subset, in which each value is used to determine whether to handle an incoming request based on a hash of an IP address associated with that incoming request.

13. In a cluster of servers that share handling of network traffic load, a system comprising:

a load balancing component that;

determines a relative load between two servers of the cluster based on packet handling times taken by those servers; and

balances the network traffic load between the servers based on the relative load.

14. The system of claim 13 wherein the load balancing component includes an instance that runs in each of the servers.

15. The system of claim 13 wherein the load balancing component comprises a driver that runs in a network stack.

16. The system of claim 13 wherein the load balancing component runs in one server, and further comprising a load responder component that runs in the other server to respond to requests from the load balancing component.

17. The system of claim 13 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.

18. The system of claim 13 further comprising a mechanism that selects the two servers for balancing the network traffic load between those two servers based on the relative load.

19. The system of claim 18 wherein the mechanism comprises a tree-based algorithm that operates the load balancing mechanism to balance pairs of servers represented by nodes in a tree.

20. The system of claim 19 wherein at least two pairs of servers are balanced substantially in parallel.