Distributed load balancer

Patent metadata

Field	Value
Publication number	US-10069903-B2
Application number	US-201313864167-A
Country	US
Kind code	B2
Filing date	Apr 16, 2013
Priority date	Apr 16, 2013
Publication date	Sep 4, 2018
Grant date	Sep 4, 2018

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.

First claim

What is claimed is:

1. A distributed load balancer system, comprising:
a plurality of load balancer nodes in a provider network; and
a plurality of server nodes in the provider network, 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 one or more 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 of a client for a packet flow from one of the plurality of load balancer nodes;
determine if a data communications protocol connection for the packet flow is to be accepted by the server on the server node;
if the server cannot accept the data communications protocol connection, reject the connection request; and
if the server can accept the data communications protocol connection, cooperate with the plurality of load balancer nodes to establish the data communications protocol connection for the packet flow between the client and the server;

wherein, after establishing the data communications protocol connection for the packet flow between the client and the server, the load balancer module on each server node is further configured to:
receive incoming data communications protocol packets for the data communications protocol connection from one of the load balancer nodes;
send the received incoming data communications protocol packets to the server on the server node;
select one of the plurality of load balancer nodes to act as an egress server for the data communications protocol connection, wherein the selection is based at least in part on an identifier for the packet flow between the client and the server;
intercept outgoing data communications protocol packets for the data communications protocol connection; and
send the intercepted outgoing data communications protocol packets to the selected egress server for delivery to the client.

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 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.

4. 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.

5. 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 data communications protocol connection established between a client and a server is a TCP connection.

6. The distributed load balancer system as recited in claim 1 , wherein each data communications protocol connection established between a client and a server is a direct data communications protocol connection that originates at the client, passes through one or more of the plurality of load balancer nodes, and is terminated by the server, wherein the one or more load balancer nodes do not act as proxies for the data communications protocol connection and do not terminate the data communications protocol connection.

7. The distributed load balancer system as recited in claim 1 , wherein, to determine if the data communications protocol 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 data communications protocol 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 data communications protocol connections.

8. A method, comprising:
performing, by one or more of a plurality of load balancer nodes:
receiving a data communications protocol 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 a data communications protocol connection for the packet flow;
rejecting the connection request upon determining that the server cannot accept the data communications protocol connection; and
accepting the connection request upon determining that the server can accept the data communications protocol connection, wherein said accepting the connection request comprises:
cooperating with the one or more load balancer nodes to establish the data communications protocol connection between the client and the server for the packet flow; and
selecting one of the plurality of load balancer nodes to act as an egress server for the data communications protocol connection based at least in part on an identifier for the packet flow, wherein outgoing data communications protocol packets on the data communications protocol connection are sent to the client via the selected egress server.

9. The method as recited in claim 8 , wherein said determining, said rejecting, and said accepting are performed by a load balancer module on the selected server node, the method further comprising performing, by the load balancer module after accepting the connection request:
receiving incoming data communications protocol packets for the data communications protocol connection from one of the load balancer nodes and sending the incoming data communications protocol packets to the server on the server node; and
intercepting the outgoing data communications protocol packets for the data communications protocol connection and sending the outgoing data communications protocol packets to the selected egress server for delivery to the client.

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

11. The method as recited in claim 9 , wherein the established data communications protocol connection is a direct data communications protocol connection that originates at the client, passes through one or more of the plurality of load balancer nodes, and is terminated by the server, wherein the one or more load balancer nodes do not act as proxies for the data communications protocol connection and do not terminate the data communications protocol connection.

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 , 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 te

Assignees

• Amazon Tech Inc

Inventors

• Sorenson Iii James Christopher
• Laurence Douglas Stewart
• Srinivasan Venkatraghavan
• Vaidya Akshay Suhas
• Zhang Fan

Classifications

• H04L67/1008

  based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) · CPC title

• H04L45/72

  Routing based on the source address · CPC title

• H04L67/1038

  Load balancing arrangements to avoid a single path through a load balancer · CPC title

• H04L29/06

  Electricity · mapped topic

• H04L67/1002 Primary

  Electricity · mapped topic