ASYMMETRIC PACKET FLOW IN A DISTRIBUTED LOAD BALANCER

• US 20140310390A1
• 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 9,553,809 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• 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

A distributed load balancer in which a router receives packets from at least one client and routes packet flows to multiple ingress servers. For unknown packet flows, an ingress server cooperates with primary and secondary flow trackers to establish connections to server nodes. For known packet flows, the ingress server sends the packets to target server nodes. The server nodes randomly select egress servers for outgoing packets of the packet flows. The ingress servers, flow trackers, and egress servers are implemented by multiple load balancer nodes in a load balancer node layer. The ingress and egress servers for a given packet flow may be on different load balancer nodes. The load balancer nodes may use a consistent hash function to compute a consistent hash ring for the nodes according to packet flow client/public endpoint pairs so that nodes associated with given packet flows can be located.

Claims

1. A distributed load balancer system, comprising:

a plurality of load balancer nodes, wherein at least two of the plurality of load balancer nodes are configured as ingress servers, and wherein at least two of the plurality of load balancer nodes are configured as flow tracker nodes;

a plurality of server nodes; and

a router configured to distribute packet flows from one or more clients to the ingress servers according to a hashed multipath routing technique;

wherein each ingress server is configured to;

receive a packet in a packet flow for a client from the router;

determine that the ingress server does not have a mapping for the packet flow to the plurality of server nodes;

determine at least one flow tracker node for the packet flow according to a consistent hash function applied to source and destination address information of the packet;

obtain a mapping of a connection to a particular one of the plurality of server nodes for the packet flow from the at least one flow tracker node; and

send one or more packets of the packet flow to the particular server node.

2. The distributed load balancer system as recited in claim 1, wherein the packet flow is a Transmission Control Protocol (TCP) packet flow.

3. The distributed load balancer system as recited in claim 1,

wherein at least two of the plurality of load balancer nodes are configured as egress servers configured to send outgoing packets from the server nodes to the one or more clients,

wherein the server node is configured to:

select one of the egress servers for the packet flow; and

send one or more outgoing packets for the packet flow to the selected egress server;

wherein the egress server is configured to send the outgoing packets to the client; and

wherein the selected egress server for the packet flow is a different load balancer node than the ingress server for the packet flow.

4. The distributed load balancer system as recited in claim 3, wherein the ingress server encapsulates the one or more packets according to User Datagram Protocol (UDP) prior to sending the packets to the server node, wherein the server node encapsulates the outgoing packets according to UDP prior to sending the outgoing packets to the egress server, and wherein the egress server strips the UDP encapsulation from the outgoing packets prior to sending the outgoing packets to the client.

5. The distributed load balancer system as recited in claim 4, wherein the server node includes a load balancer module configured to:

select the egress server for the packet flow;

receive the incoming encapsulated packets from the ingress server;

strip the UDP encapsulation from the packets and deliver the packets to a server on the server node;

obtain the outgoing packets from the server on the server node;

encapsulate the outgoing packets according to UDP; and

send the encapsulated outgoing packets to the egress server.

6. The distributed load balancer system as recited in claim 1, wherein, to obtain a mapping of a connection to a particular one of the plurality of server nodes for the packet flow from the at least one flow tracker node,

the ingress server sends a message that includes information for the packet flow to a primary flow tracker for the packet flow;

the primary flow tracker sends a message to a secondary flow tracker for the packet flow that includes the information for the packet flow, wherein the primary and secondary flow trackers for the packet flow are different load balancer nodes;

the secondary flow tracker sends an acknowledgement for the packet flow to the client;

the ingress server receives an acknowledgement packet from the client and forwards the acknowledgement packet to the primary flow tracker;

the primary flow tracker randomly selects the particular server node from among the plurality of server nodes as the server node to receive the packet flow and sends a message to the secondary flow tracker indicating the particular server node;

the secondary flow tracker fabricates a synchronization message and sends the fabricated synchronization message to the particular server node;

the secondary flow tracker receives connection information for the packet flow from the particular server node and sends a message including the connection information to the primary flow tracker; and

the primary flow tracker sends a message including the connection information for the packet flow to the ingress server, wherein the connection information maps the packet flow to the particular server node.

7. The distributed load balancer system as recited in claim 6, wherein the server node includes a load balancer module configured to:

receive the fabricated synchronization message from the secondary flow tracker;

determine that a server on the server node can accept a connection;

generate a synchronization packet according to the fabricated synchronization message and deliver the synchronization packet to the server on the server node;

intercept an acknowledgement packet generated by the server on the server node; and

send a message including the connection information to the secondary flow tracker.

8. A method, comprising:

performing, by an ingress server on one of a plurality of load balancer nodes;

receiving a packet in a packet flow for a client, wherein the packet is received from a router that distributes packet flows from one or more clients to the plurality of load balancer nodes according to a consistent hash function;

determining a load balancer node that serves as a flow tracker node for the packet flow according to a consistent hash function applied to source and destination address information of the packet;

obtaining a mapping of a connection to one of a plurality of server nodes for the packet flow from the flow tracker node for the packet flow; and

sending one or more packets of the packet flow to the server node indicated by the mapping.

9. The method as recited in claim 8, wherein the packet flow is a Transmission Control Protocol (TCP) packet flow.

10. The method as recited in claim 8, further comprising the ingress server encapsulating the packets according to User Datagram Protocol (UDP) prior to said sending the one or more packets of the packet flow to the server node.

11. The method as recited in claim 8, further comprising:

selecting, by the server node, one of the plurality of load balancer nodes as an egress server for the packet flow, wherein the selected egress server for the packet flow is on a different load balancer node than the ingress server for the packet flow;

sending, by the server node, one or more outgoing packets for the packet flow to the selected egress server; and

sending, by the egress server, the outgoing packets to the client of the packet flow.

12. The method as recited in claim 11, further comprising:

the server node encapsulating the outgoing packets according to User Datagram Protocol (UDP) prior to said sending the outgoing packets to the egress server; and

the egress server stripping the UDP encapsulation from the outgoing packets prior to said sending the outgoing packets to the client.

13. The method as recited in claim 8, wherein the flow tracker node is a primary flow tracker node for the packet flow, and wherein a next load balancer node in a consistent hash ring according to the consistent hash function is a secondary flow tracker node for the packet flow.

14. The method as recited in claim 13, wherein said obtaining a mapping of a connection to one of a plurality of server nodes for the packet flow from the flow tracker node for the packet flow comprises:

sending, by the ingress server, at least one message to the primary flow tracker node for the packet flow, each message including a packet of the packet flow received from the router;

selecting, by the primary flow tracker node, the server node for the packet flow from among the plurality of server nodes;

sending, by the primary flow tracker node, packet flow information including an indication of the selected server node to the secondary flow tracker node;

facilitating, by the secondary flow tracker node, establishment of the connection to the selected server node for the packet flow by communicating with the server node and the client; and

sending, by the secondary flow tracker node, connection information for the packet flow to the ingress server via the primary flow tracker node, wherein the connection information maps the packet flow to the selected server node.

15. The method as recited in claim 14, wherein the server node includes a load balancer module, wherein said facilitating establishment of the connection to the selected server node for the packet flow by communicating with the server node and the client comprises:

sending, by the secondary flow tracker node, a fabricated synchronization message to the load balancer module on the server node; and

performing, by the load balancer module on the server node;

determining that a server on the server node can accept a connection;

generating a synchronization packet according to the fabricated synchronization message;

delivering the synchronization packet to the server on the server node;

intercepting an acknowledgement packet generated by the server on the server node; and

sending a message including the connection information to the secondary flow tracker node.

16. A non-transitory computer-accessible storage medium storing program instructions computer-executable to implement an ingress server and a flow tracker on each of a plurality of load balancer nodes, each ingress server configured to:

receive a packet in a packet flow for a client, wherein the packet is received from a router that distributes packet flows from one or more clients to the plurality of load balancer nodes according to a consistent hash function;

determine one of the plurality of load balancer nodes that serves as a flow tracker node for the packet flow according to a consistent hash function applied to source and destination address information of the packet;

obtain a mapping of a connection to one of a plurality of server nodes for the packet flow from the flow tracker node for the packet flow; and

send one or more packets of the packet flow to the server node indicated by the mapping.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the program instructions are further computer-executable to implement an egress server on each of the load balancer nodes and a load balancer module on each of the plurality of server nodes, each load balancer module configured to:

select one of the plurality of load balancer nodes as an egress server for a packet flow, wherein the selected egress server for the packet flow is on a different load balancer node than an ingress server for the packet flow; and

send one or more outgoing packets for the packet flow to the selected egress server;

wherein each egress server is configured to send outgoing packets in a packet flow received from a load balancer module to a client of the packet flow.

18. The non-transitory computer-accessible storage medium as recited in claim 17,

wherein each ingress server is further configured to encapsulate the packets according to User Datagram Protocol (UDP) prior to said sending the one or more packets of the packet flow to the server node;

wherein each load balancer module is further configured to;

strip the UDP encapsulation from the packets received from an ingress server and deliver the packets to a server on the respective server node;

intercept the outgoing packets from the server on the respective server node; and

encapsulate the outgoing packets according to UDP prior to said sending the outgoing packets to an egress server;

wherein each egress server is further configured to strip the UDP encapsulation from the outgoing packets prior to said sending the outgoing packets to the client of the packet flow.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the flow tracker node is a primary flow tracker node for the packet flow, and wherein a next load balancer node in a consistent hash ring according to the consistent hash function is a secondary flow tracker node for the packet flow, and wherein, to obtain a mapping of a connection to one of a plurality of server nodes for the packet flow from the flow tracker node for the packet flow:

the ingress server is configured to send at least one message to the primary flow tracker node for the packet flow, each message including a packet of the packet flow received from the router;

the primary flow tracker node is configured to;

select the server node for the packet flow from among the plurality of server nodes; and

send packet flow information including an indication of the selected server node to the secondary flow tracker node;

the secondary flow tracker node is configured to;

facilitate establishment of the connection to the selected server node for the packet flow by communicating with the server node and the client; and

send connection information for the packet flow to the ingress server via the primary flow tracker node, wherein the connection information maps the packet flow to the selected server node.

20. The non-transitory computer-accessible storage medium as recited in claim 19, wherein the program instructions are further computer-executable to implement a load balancer module on each of the plurality of server nodes, and wherein, to facilitate establishment of the connection to the selected server node for the packet flow by communicating with the server node and the client:

the secondary flow tracker node is configured to send a fabricated synchronization message to the load balancer module on the server node; and

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

determine that a server on the server node can accept a connection;

generate a synchronization packet according to the fabricated synchronization message;

deliver the synchronization packet to the server on the server node;

intercept an acknowledgement packet generated by the server on the server node; and

send a message including the connection information to the secondary flow tracker node.