DISTRIBUTED LOAD BALANCER

• US 20140310418A1
• Filed: 04/16/2013
• Published: 10/16/2014
• Est. Priority Date: 04/16/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: SORENSON, JAMES CHRISTOPHER III, LAURENCE, DOUGLAS STEWART, SRINIVASAN, VENKATRAGHAVAN, VAIDYA, AKSHAY SUHAS, ZHANG, FAN
• Granted Patent: US 10,069,903 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: H04L 45/72 Routing based on the source address
• 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/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
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A distributed load balancer in which a router receives packets from at least one client and routes packet flows to multiple load balancer (LB) nodes according to a per-flow hashed multipath routing technique. For a given packet flow, the LB nodes randomly select a server node as a target for the packet flow from among multiple server nodes and send a connection request to the server node. A load balancer module on the server node makes the decision on whether to accept or reject the connection based on one or more metrics indicating a respective server'"'"'s current load. If the module accepts the connection request, a connection is established between the server and the client. Otherwise, the load balancer nodes may select another server node and try again. The connections established between clients and servers pass through the load balancer nodes, but are not terminated at the load balancer nodes.

Claims

1. A distributed load balancer system, comprising:

a plurality of load balancer nodes; and

a plurality of server nodes each comprising a server and a load balancer module;

wherein the plurality of load balancer nodes is configured to distribute packet flows from one or more clients among the plurality of server nodes, wherein, to distribute the packet flows among the plurality of server nodes, the plurality of load balancer nodes is configured to;

select server nodes from among the plurality of server nodes to receive connection requests for the packet flows from the clients; and

send the connection requests to the selected server nodes;

wherein the load balancer module on each server node is configured to;

receive a connection request for a packet flow from one of the plurality of load balancer nodes;

determine if the connection is to be accepted by the server on the server node;

if the server cannot accept the connection, reject the connection request; and

if the server can accept the connection, cooperate with the plurality of load balancer nodes to establish a connection for the packet flow between the respective client and the respective server.

2. The distributed load balancer system as recited in claim 1, further comprising a router configured to distribute the packet flows from the one or more clients among the plurality of load balancer nodes according to a hashed multipath routing technique.

3. The distributed load balancer system as recited in claim 1, wherein, to determine if the connection is to be accepted by the server on the server node, the load balancer module is configured to analyze one or more current resource usage metrics of the server on the server node to determine if the server can accept the connection, wherein the one or more current resource usage metrics include one or more of CPU utilization, bandwidth consumption, server latency, and number of established connections.

4. The distributed load balancer system as recited in claim 1, wherein the plurality of load balancer nodes is further configured to select the server nodes from among the plurality of server nodes to receive the connection requests according to a random selection technique.

5. The distributed load balancer system as recited in claim 1, wherein the plurality of load balancer nodes is further configured to select another server node from among the plurality of server nodes to receive a rejected connection requests and send the connection request to the other server node.

6. The distributed load balancer system as recited in claim 1, wherein each packet flow is a Transmission Control Protocol (TCP) packet flow, and wherein each connection established between a client and a server is a TCP connection.

7. The distributed load balancer system as recited in claim 1, wherein each connection established between a client and a server originates at the client, passes through one or more of the plurality of load balancer nodes, and is terminated by the server.

8. A method, comprising:

performing, by one or more of a plurality of load balancer nodes;

receiving a packet in a packet flow for a client; and

sending a connection request for the packet flow to a server node selected from among a plurality of server nodes;

performing, by the selected server node;

determining if a server on the server node can or cannot accept the connection;

rejecting the connection request upon determining that the server cannot accept the connection; and

accepting the connection request upon determining that the server can accept the connection.

9. The method as recited in claim 8, wherein said accepting the connection request comprises the selected server node cooperating with the one or more load balancer nodes to establish a connection between the respective client and the respective server for the packet flow.

10. The method as recited in claim 9, wherein the packet flow is a Transmission Control Protocol (TCP) packet flow, and wherein the connection established between the client and the server is a TCP connection.

11. The method as recited in claim 9, wherein the established connection originates at the client, passes through one of the plurality of load balancer nodes, and is terminated by the server.

12. The method as recited in claim 8, wherein the packet is received from a router that distributes packet flows from one or more clients among the plurality of load balancer nodes according to a hashed multipath routing technique.

13. The method as recited in claim 8, wherein said determining if a server on the server node can or cannot accept the connection comprises analyzing one or more current resource usage metrics of the server to determine if the server can accept the connection.

14. The method as recited in claim 8, further comprising the one or more load balancer nodes selecting the server node from among the plurality of server nodes according to a random selection technique.

15. The method as recited in claim 8, further comprising, if the selected server node rejects the connection request, the one or more load balancer nodes sending the connection request to another server node selected from among the plurality of server nodes.

16. A non-transitory computer-accessible storage medium storing program instructions computer-executable to implement a load balancer module on each of a plurality of server nodes, each load balancer module operable to:

receive, from one of a plurality of load balancer nodes, a connection request for a packet flow from a client;

determine if a server on the server node can or cannot accept the connection;

reject the connection request upon determining that the server cannot accept the connection; and

communicate with the load balancer node and with the server to establish a connection between the client and the server for the packet flow upon determining that the server can accept the connection.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein, to determine if a server on the server node can or cannot accept the connection, the load balancer module is operable to analyze one or more current resource usage metrics of the server to determine if the server can accept the connection.

18. The non-transitory computer-accessible storage medium as recited in claim 17, wherein the one or more current resource usage metrics include one or more of CPU utilization, bandwidth consumption, server latency, and number of established connections.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the program instructions are further computer-executable to implement the load balancer node randomly selecting the server node from among the plurality of server nodes to receive the connection request.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein, to reject the connection request, the load balancer module is operable to decrement a time to live (TTL) counter in the connection request and return the connection request to the load balancer node, wherein the program instructions are further computer-executable to implement the load balancer node:

checking the TTL counter in the returned connection request;

if the TTL counter is above a threshold, selecting another server node from among the plurality of server nodes to receive the connection request; and

if the TTL counter is at or below the threshold, dropping the connection request.