Client-side load balancing

• US 7,930,427 B2
• Filed: 03/03/2008
• Issued: 04/19/2011
• Est. Priority Date: 03/03/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Josefsberg, Arne, Dunagan, John D, Scheibel, Mark D., Wolman, Alastair
• Primary Examiner(s): Coulter; Kenneth R
• Application Number:
  US12/041,600
• Publication Number:
  US 20090222583A1
• Time in Patent Office: 1,142 Days
• Field of Search: 709/245, 709/226, 709217-219, 718/105, 718/104, 718/102
• US Class Current: 709/245
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1038 Load balancing arrangements to avoid a single path through a load balancer

Abstract

An exemplary method for load balancing includes accessing a range of values for IP addresses associated with a virtual IP address associated with a domain name; selecting, using a local statistical algorithm, a value in the range; and, based at least in part on the selected value, connecting to a remote resource at one of the IP addresses. In such a method, a client can perform local load balancing when connecting to one of many fungible resources “behind” a virtual IP address. With many such clients, the task of load balancing is distributed as opposed to being centralized at a server farm or cluster. Other methods, devices and systems are also disclosed.

Claims

1. A method for load balancing, implemented by a client computing device, the method comprising:

determining a virtual IP (VIP) address associated with a domain name based on an Internet Location Coordinate (ILC) of the VIP address;

accessing a range of values for IP addresses associated with the VIP address;

selecting, using a local statistical algorithm, a value in the range, wherein the local statistical algorithm resides locally on the client computing device; and

based at least in part on the selected value, connecting to a remote resource at one of the IP addresses.

2. The method of claim 1 wherein the accessing comprises receiving the range of values in response to a request for resolution of the domain name.

3. The method of claim 2 wherein the receiving comprises receiving the range of values from a Domain Name System server (DNS server).

4. The method of claim 1 wherein the accessing comprises accessing a Domain Name System (DNS) resolver cache.

5. The method of claim 1 wherein the statistical algorithm achieves load balancing for resources associated with the virtual IP address.

6. The method of claim 1 wherein the statistical algorithm comprises a random function.

7. The method of claim 1 wherein the selecting comprises randomly selecting a value in the range.

8. The method of claim 1 further comprising disconnecting from the remote resource and then repeating the accessing and selecting to reconnect to a remote resource at one of the IP addresses.

9. The method of claim 1 wherein the range comprises a lower value and an upper value.

10. The method of claim 1 wherein the range comprises a value and a delta that define the range.

11. The method of claim 1 further comprising a time-to-live (TTL) for the range.

12. The method of claim 11 wherein, upon expiration of the TTL, a request issues for a range of values associated with the virtual IP address.

13. The method of claim 1 wherein the remote resource comprises a host server for the domain name.

14. The method of claim 1 wherein the selecting comprises using a local operating system service.

15. The method of claim 1, wherein the range comprising contiguous IP address values between a lower value and an upper value, the range of values represented in a single IP address format having the lower value with the upper value being appended to the single IP address format.

16. A method for load balancing, implemented at least in part by a client computing device, the method comprising:

accessing a range of values for IP addresses associated with a virtual IP address associated with a domain name, the virtual IP address being further associated with an Internet Location Coordinate and the range of values representing the IP addresses in a condensed format;

selecting, using a local statistical algorithm, a value in the range, wherein the local statistical algorithm resides locally on the client computing device; and

upon failure to connect to a remote resource at the IP address associated with the selected value, repeating the selecting.

17. The method of claim 16 further comprising:

after failing to connect to one or more IP addresses for a given virtual IP address associated with the domain name, accessing a range of values for IP addresses associated with a different virtual IP address associated with the same domain name;

selecting, using a local statistical algorithm, a value in the range; and

based on the selecting, attempting to connect to a remote resource at one of the IP addresses associated with the different virtual IP address.

18. The method of claim 16 further comprising deleting the selected value from the range prior to repeating the selecting.

19. The method of claim 16 further comprising, prior to accessing, selecting a virtual IP address, associated with a domain name, based at least in part on Internet Location Coordinate information.

20. A client-side load balancing module for execution on a hardware client computing device, the module comprising:

instructions for determining Internet Location Coordinate (ILC) information for the client computing device, the determining being based on communication with one or more network beacons by the client computing device;

instructions for accessing Internet Location Coordinate (ILC) information for multiple Virtual Internet Protocol (VIP) addresses in a resolver cache;

instructions for comparing the ILC information for the client computing device with the ILC information for the multiple VIP addresses;

instructions for selecting an optimal VIP address associated with a domain name based on the comparing;

instructions to access range information in the resolver cache, the range information corresponding to IP addresses associated with the optimal virtual IP address; and

instructions to directly or indirectly select, using a local statistical algorithm, one of the IP addresses, the local statistical algorithm residing locally on the client computing device.