Direct load balancing using a multipath protocol

Multipath load balancing methods and apparatus that may be implemented on or by load balancers in load balanced systems. The multipath load balancing method may leverage a multipath network protocol to establish multiple paths for at least some connections between client hosts and server hosts in load balanced systems, each connection corresponding to a particular data flow between a respective client host and server host. Using the multipath load balancing method, a load balancer may operate to establish a bi-directional connection directly between a client host and a server host after first establishing a connection between the client host and server host that passes through the load balancer. Most or all of the traffic that would move between the client host and the server host via the load balancer can then be diverted onto the second, more direct connection between the client host and the server host.

BACKGROUND

As the scale and scope of network-based applications and network-based services such as cloud computing services have increased, data centers may house hundreds or even thousands of host devices (e.g., web servers) that need to be load balanced. Conventional load balancers may generally include one or more network interface controllers (NICs), for example eight NICs, that handle inbound traffic from/outbound traffic to clients and inbound traffic to/outbound traffic from the host devices (e.g., servers such as web servers) that are being load balanced. Load balancers typically also include logic that implements load balancing techniques such as round robin and/or least connections (least conns) techniques to select which host device will handle a connection from a client.

In conventional load balancers, clients communicate with selected host devices on connection(s) that pass through the load balancer, and thus the data exchanged between a client and a selected host device in a conventional load balanced system flows through the load balancer. Some conventional load balancers may serve as proxies to the host devices that they front, and thus may terminate connections (e.g., Transmission Control Protocol (TCP) connections) from the clients and send the client traffic to the host devices on connections (e.g., TCP connections) established between the host devices and the load balancer. In other conventional load balancers, the load balancer does not terminate connections from the client and the host device. Instead, connections (e.g., Transmission Control Protocol (TCP) connections) are established between clients and host devices that pass through the load balancer. The load balancer modifies header information (e.g., TCP and IP header information) in packets that pass through the load balancer on the connections to transparently route traffic between the clients and host devices. These load balancers may be viewed as serving as routing/network address translation (NAT) firewalls between the clients and the load balanced host devices.

Multipath TCP

Multipath TCP (MPTCP) is a network protocol proposed by the Internet Engineering Task Force (IETF) in the document Request for Comments (RFC) 6824. In traditional Transmission Control Protocol/Internet Protocol (TCP/IP), communication is restricted to a single path per connection, even though multiple possible paths may exist between peers. RFC 6828 presents MPTCP as a set of extensions to traditional TCP to support multipath operation and thus allow multiple TCP flows across two or more potentially disjoint paths for a connection between two peers. Note that both peers would need to support the MPTCP protocol in order to establish multiple paths for a connection according to MPTCP.

DETAILED DESCRIPTION

Various embodiments of methods and apparatus for load balancing using a multiple path (multipath) protocol are described. Embodiments of a multipath load balancing method are described that may be implemented on or by load balancers in load balanced systems. The multipath load balancing method may leverage a multipath network protocol, for simplicity referred to herein as a multipath protocol, to establish multiple (two or more) paths for at least some connections between client hosts and server hosts in load balanced systems, each connection corresponding to a particular data flow between a respective client host and server host. While any suitable multipath protocol may be used, an example multipath protocol that may be used in at least some embodiments is Multipath Transmission Control Protocol (Multipath TCP, or MPTCP). Using an embodiment of the multipath load balancing method, a load balancer may operate to establish a bi-directional connection (e.g., an MPTCP subflow) directly between a client host and a server host after first establishing a connection (e.g., via MPTCP) between the client host and server host that passes through the load balancer. Most or all of the traffic that would conventionally move between the client host and the server host via the load balancer can then be diverted onto the second, more direct connection (e.g., an MPTCP subflow) between the client host and the server host.

FIG. 1Aillustrates an example load balanced system in which embodiments of a multipath load balancing method may be implemented. In a load balanced system, a load balancer100may front multiple server hosts120A,120B . . .120N. As a non-limiting example, a load balancer100may be a device that includes a network interface102, for example implemented as or by one or more network interface controllers (NICs), that handles inbound traffic from/outbound traffic to client hosts130and inbound traffic to/outbound traffic from the server hosts120that are being load balanced. Load balancer100may also include logic110(one or more processors, memory, software, data, drivers, etc.) that implements load balancing functionality including but not limited to a load balancing technique (e.g., least conns) used to select a particular server host120from among the multiple server hosts120fronted by the load balancer100to receive a given data flow from a client130.

Load balancer100may front tens, hundreds, or thousands of server host120. Each server host120may publish one or more IP addresses to the load balancer100. Further, each server host120may include one or more instances of a server or service that is being load balanced. Examples include, but are not limited to, application servers, web servers, or in general any type of server, as well as services such as storage services. As a non-limiting example, server hosts120may be implemented as slot-mounted computing devices, for example blade servers, mounted in racks in a data center that implements a service provider's network, and the servers on the server hosts120may collectively represent a service (or services) provided by the service provider to one or more clients of the service provider.FIG. 6illustrates an example computing device that may be used as a server host120in at least some implementations of a load balanced system.

Load balancer100may receive connection requests from multiple client hosts130A,130B . . .130M for access to the service(s) provided by the server hosts120fronted by the load balancer100. Note that a load balancer100may serve any number (tens, hundreds, thousands, or more) of client hosts130. Each client host130may be a computing device that may include one or more instances of one or more applications that may access the service provided by the service provider and implemented on or by the load balanced system, and that thus may generate connection requests that are received by the load balancer100.FIG. 6illustrates an example computing device that may be used as a client host130. As a non-limiting example of an application that may access the service provided by the service provider and implemented on or by the load balanced system, a client host130may include a web browser via which a client may access the service. As another example, an application on a client host130may be a program or module that accesses a storage service implemented on the load balanced system, with each server host120being a storage host that includes or fronts one or more storage devices.

As another example of a load balancer system in which embodiments may be implemented, the server hosts120may collectively implement a service on a network, and client hosts130may be components, nodes, or instances of another service on the network. For example, server hosts120may implement a storage service on a service provider's network, and client hosts130may be components of another service that uses the storage service for data storage and retrieval. As another example, server hosts120may implement a storage service on a service provider's network that provides virtualized storage to a plurality of clients, and client hosts130may be instances of virtual computation resources (e.g., virtual machines (VMS)) on the service provider network that are provided to the clients through a hardware virtualization service and that may access the virtualized storage service implemented on the storage hosts120for data storage and retrieval.

In a load balancer100as illustrated inFIG. 1Athat acts as a proxy between client hosts130and server hosts120, a client host130may connect to the load balancer100(e.g., to a Virtual IP (VIP) address hosted by the load balancer) according to a network protocol (e.g., Transmission Control Protocol (TCP)). The connection between the client host130and the load balancer100may be referred to as a client connection132. For example, client host130A may communicate with load balancer100according to TCP to establish a client connection132A. The load balancer100then uses a load balancing technique (e.g., least connections, or least conns) to select a particular server host120from among the multiple server hosts120fronted by the load balancer100, and establishes a connection to the selected server host120, for example a TCP connection to an IP address of the selected server host120. The connection between the load balancer100and the server host120may be referred to as a server connection122. For example, load balancer100may establish a server connection122A to server host120A. Packets (e.g., TCP segments) may then be exchanged between the client host130A and server host120A via the load balancer100. The load balancer100may essentially act as a proxy between the client host130A and the server host120A. The load balancer100terminates the connection from the client host130A (the client connection132A) and sends the client traffic to the respective server host120A via the server connection122A. Similarly, return traffic from the server host120A to the client host130A is sent via the server connection122A, which is terminated by the load balancer100, which sends the return traffic to the respective client host130A via the client connection132A.

FIG. 1Ashows each client host130A,130B . . .130M with one client connection132A,132B . . .132M to load balancer100, and also shows a corresponding server connection122A,122B . . .122M from load balancer100to one of the server hosts120A,120B . . .120N. However, in at least some implementations, each client host130may establish one, two, or more client connections132to a load balancer100, and that load balancer100may establish one, two, or more server connections122to each server host120. Note that there may generally not be a one-to-one correspondence between client hosts130and server hosts120; in other words, while M may be equal to N, typically, M≠N. Also note that while load balanced systems as illustrated inFIG. 1Amay have many server hosts120and many client hosts130, load balanced systems may be implemented where M is at least one and N is at least two. In other words, a load balanced system may have two or more server hosts120and one or more client hosts130.

FIG. 1Ashows a single load balancer100device. Note, however, that in some implementations a load balanced system that fronts multiple server hosts120may include two or more load balancer100devices. For example, each of two or more load balancers100in such a system may be configured to load balance traffic from client hosts130to a specified subset of the server hosts120, or to load balance traffic for a specified address range. Further note that a load balanced system may include one or more other components than those shown inFIG. 1A. For example, a load balanced system may include one or more routers or other network devices located between load balancer100and client hosts130, and/or a network fabric (e.g., an L3 network) between load balancer100and server hosts120. Note that the other components may be selected to support the bandwidth/throughput of the load balancer100. For example, one or more router(s) between client hosts130and a load balancer100that provides 40 Gbps throughput should also support at least 40 Gbps throughput.

FIG. 1Aillustrates an example load balancer100that acts as a proxy between client hosts130and server hosts120. For a given connection between a client host130and a selected one of the server hosts120, the load balancer100establishes a client connection132to the client host130and a server connection122to the server host122. For example, the load balancer100has established client connection132A to client host120A and server connection122A to server host120A for a connection between client host130A and server host120A. The load balancer100terminates the client connection132A and the server connection122A. The load balancer100receives traffic from the client host130A via the client connection132A and sends the traffic to the selected server host120A via the respective server connection122A.

FIG. 1Aillustrates an example load balancer100that acts as a proxy between client hosts130and server hosts120. However, other load balancers do not act as proxy load balancers and do not terminate connections to the client hosts130and connections to server hosts120as illustrated inFIG. 1A. For example, in some load balancers, in response to a client host120's connection request, a connection (e.g., a Transmission Control Protocol (TCP) connection) is established between a client host130and a selected server host120, the connection passing through the load balancer100. These load balancers may be referred to as pass-through load balancers, as opposed to proxy load balancers as illustrated inFIG. 1A. Instead of receiving packets on one connection and retransmitting the packets on another connection as in the example proxy load balancer100shown inFIG. 1A, a pass-through load balancer100modifies header information (e.g., TCP and IP header information) in packets that pass through the load balancer100on each client/server connection to transparently route traffic between the client hosts130and server hosts120. These pass-through load balancers100may be viewed as serving as routing/network address translation (NAT) firewalls between the client hosts130and server hosts120. In addition to application in load balancers that act as proxies as illustrated inFIG. 1A, embodiments of the multipath load balancing methods may also be applied in these other types of load balancers.

For either type of load balancer100, a connection between a client host130and a selected one of the server hosts120that goes through the load balancer100may be generally referred to herein as a load balancer connection, or LB connection. For example, inFIG. 1A, the connection between client host130A and server host120A is shown as LB connection140A.

FIGS. 1B and 1Cillustrate connections between clients and servers that go through a load balancer in a load balanced system, according to at least some embodiments.FIG. 1Bshows an LB connection140in a load balancer100that acts as a proxy, as illustrated inFIG. 1A.FIG. 1Cshows an LB connection140in a pass-through load balancer as described above. As shown inFIG. 1B, a client connection132is established between an endpoint134of a client and an endpoint114A of the load balancer100. A server connection122is established between an endpoint114B of the load balancer100and an endpoint124of a selected server. Thus, the load balancer100terminates the connections132and122. A connection between the client and the server that goes through the load balancer100via connections132and122as illustrated inFIG. 1Bmay be referred to as a load balancer connection, or LB connection140. As shown inFIG. 1C, a connection is established between an endpoint134of a client and an endpoint124of a selected server that goes through the load balancer100. However, the connection is not terminated at the load balancer; instead, the load balancer100modifies the headers of packets that pass through the load balancer100on the connection so that the packets are delivered to the appropriate client or server endpoint. A connection between the client and the server that goes through the load balancer100as illustrated inFIG. 1Cmay also be referred to as a load balancer connection, or LB connection140.

Note that the endpoints shown inFIGS. 1B and 1Cmay generally be defined by an IP address and a port number, and may also be referred to as sockets.

A conventional load balancer100, for example a load balancer100as illustrated inFIG. 1A, may form a bottleneck for data traffic between the client hosts130and the server hosts120. All traffic between client hosts130and server hosts120passes through the load balancer100on LB connections140. Since there may be hundreds of client hosts130and hundreds of server hosts120in a load balanced system, it is possible for traffic flow to push or exceed the bandwidth of the load balancer100in one or both directions. Note that even with fewer client hosts130and server hosts120, some applications may generate high volumes of traffic in one or both directions that may push or exceed the bandwidth capacity of the load balancer100.

Another potential issue with a conventional load balancer100, for example as illustrated inFIG. 1A, is that in some cases a client host130and a server host120to which the client host130is linked via the load balancer100may be at one location or on one network or network partition, while the load balancer100itself may be at another location, network, or network partition. Traffic between a client host130and a server host120is routed from the client host130to the load balancer100, and then from the load balancer100to the client host130. Response traffic from the server host120is similarly routed through the load balancer. Thus, in a load balanced system as illustrated inFIG. 1A, traffic between a client host130and a server host120generally does not travel over a direct or shortest path between the two hosts, and may even be routed from one location to another and back again. For example, a client host130and a server host120may be located in one data center, while the load balancer100via which the two hosts communicate may be in another data center. In this example, traffic between a client host130and a server host120would be routed from one data center to a data center at which the load balancer100is located, and then back to the first data center. Bandwidth on the interconnecting network infrastructures between the client host130and the load balancer100and between the load balancer100and the server host120is consumed, and transmission time between a client host130and a server host120is greater than it would be on a more direct path between the two hosts. In addition, total response time for requests may be greater than it would be on a more direct path between the two hosts.

A conventional response to the bottleneck issue in load balanced systems is to add additional load balancers100. However, load balancers100that support high throughput (e.g., 40 Gbps or 80 Gbps throughput) may generally be expensive, as are the routers or other network devices that may be needed to support the load balancers100. In addition, adding additional load balancers100may not resolve issues that may result from data flows between client hosts130and server hosts120at two locations being routed through a load balancer100at a third location.

Another response to the bottleneck issue in load balanced systems is a technology referred to as direct server return (DSR). DSR enables at least some server hosts fronted by a load balancer to establish a separate, direct connection from the server host to a client host and to thus return at least some response data directly to a client host without routing the response data through the load balancer. However, traffic on the data flow from the client host to the server host (e.g., service requests) still passes through the load balancer.

FIG. 2illustrates a load balanced system in which direct server return (DSR) is implemented. Load balancer (LB) connections240between client hosts230and server hosts220that go through the load balancer200may be established as previously described. In at least some embodiments, to establish an LB connection240, a client host230establishes a connection (a client connection232) to load balancer200. For example, client host230A may communicate with load balancer200according to TCP to establish a client connection232A. Load balancer200then uses a load balancing technique (e.g., least connections, or least conns) to select a particular server host220from among multiple server hosts220fronted by the load balancer200, and establishes a connection (server connection222) to the selected server host220, for example a TCP connection to an IP address of the selected server host220. In this example, load balancer200has established a server connection222A to selected server host220A. Packets (e.g., TCP segments) may then be sent from the client host230A to host220A over client connection232A, through the load balancer200, and to server host220A via server connection222A.

Using DSR technology, a separate path may be established for an LB connection240A from the server host220A to the client host230A, shown as direct server return242A. The server host220A may then return response traffic to client host230A via the direct server return242path. However, traffic from client230A to server host220A is still routed through the load balancer200via the LB connection240A.

DSR may remove some of the bandwidth from a load balancer in a load balanced system by allowing return traffic from the servers to be directly sent to respective clients. DSR may be effective in relieving the bottleneck issue on load balancers in load balanced systems in which a majority of the traffic on an established data flow between a client and a server is return traffic from the server to the client. For example, DSR may be effective in reducing bandwidth usage on a load balancer in systems or with services in which clients send requests for data to servers via the load balancer, and the servers return relatively large amounts of data to the clients in response to the requests. The load balancer uses a load balancing technique (e.g., least conns) to spread load (data flows) among the servers, the requests from the clients are routed to the selected servers through the load balancer via the client and server connections, and at least some of the response data may be sent to the clients via the DSR paths.

However, DSR may not be as effective in load balanced systems in which clients may send relatively large amounts of data to the servers. For example, DSR may not be as effective in a load balanced system in which the servers implement a storage service, and clients of the service upload large amounts of data to the storage service via the load balancer. In addition, in a load balanced system that uses DSR, all of the data from a client to a server is routed through the load balancer even if the client and server are local to each other while the load balancer is remotely located, and thus issues that may result from the need to route data through the load balancer as previously described may still be present.

Multipath Load Balancing

Embodiments of a multipath load balancing method are described that may be implemented on or by load balancers in load balanced systems. The multipath load balancing method may leverage a multipath protocol to establish multiple paths for at least some connections between client hosts and server hosts in load balanced systems. While any suitable multipath protocol may be used, an example multipath protocol that may be used in at least some embodiments is Multipath Transmission Control Protocol (Multipath TCP, or MPTCP).

In the multipath load balancing method, after establishing a connection from a client host to a server host that passes through the load balancer via client and server connections, a second flow, referred to as a subflow, for the connection between the client and the server may be established on a direct connection between the server host and the client host according to the multipath protocol (e.g., MPTCP). Note that a direct connection as used herein refers to a connection between a client and a server in a load balanced system that does not pass through the load balancer. Data flow on the direct connection between the client and the server may be bi-directional. That is, in addition to or instead of the server sending data to the client via the direct connection, the client may send data to the server via the direct connection.

In at least some embodiments, the initial connection through the load balancer may be persisted after establishing the direct connection so that the connection between the client and the server can be monitored and so that load balancing of the servers (e.g., via a least conns technique) fronted by the load balancer can be properly performed. However, the load balancer may throttle down the amount of data flowing through the load balancer by shrinking or reducing the window size(s) on the initial connection through the load balancer, thus causing more data, a majority of the data, or even all of the data flowing between the respective client and server to pass over the direct connection rather than through the load balancer. Thus, the multipath load balancing method may be effective in addressing issues in load balanced systems in which the clients send relatively large amounts of data to the servers in addition to load balanced systems in which the servers send relatively large amounts of data to the clients.

FIG. 3illustrates a load balanced system in which multiple paths are established for connections between client hosts and server hosts according to embodiments of a multipath load balancing method. A load balancer that implements an embodiment of the multipath load balancing method (shown as multipath load balancer300) fronts multiple server hosts320A,320B . . .320N that host one or more services. Multipath load balancer300may receive connection requests from multiple client hosts330A,330B . . .330M for access to the service(s) provided by the server hosts320fronted by the load balancer300.

As a non-limiting example, multipath load balancer300may be implemented as one or more devices that includes a network interface302, for example implemented as or by one or more network interface controllers (NICs), that handles inbound traffic from/outbound traffic to client hosts330and inbound traffic to/outbound traffic from the server hosts320that are being load balanced. Load balancer300may also include logic310(one or more processors, memory, software, data, drivers, etc.) that implements load balancing functionality including but not limited to a load balancing technique312(e.g., a least conns technique) used to select a particular server host320from among the multiple server hosts320fronted by the load balancer300to receive a given data flow from a client330. Load balancer logic310may also implement multipath functionality314that implements the multipath load balancing method in the load balanced system as described herein.

FIG. 3shows a single load balancer300device. Note, however, that in some implementations a load balanced system may include two or more load balancer300devices. For example, each of two or more load balancers300in such a system may be configured to load balance traffic from client hosts330to a specified subset of the server hosts320, or to load balance traffic for a specified address range. Further note that a load balanced system may include one or more other components than those shown inFIG. 3. For example, a load balanced system may include one or more routers or other network devices located between load balancer300and client hosts330, and/or a network fabric (e.g., an L3 network) between load balancer300and server hosts320.

In at least some embodiments, a client host330A connects to a load balancer300(e.g., to one of one or more Virtual IP (VIP) addresses hosted by the load balancer300) that implements the multipath load balancing method. The connection between the client host330A and the multipath load balancer300may be referred to as a client connection332A. The multipath load balancer300uses a load balancing technique (e.g., least connections, or least conns) to select a particular server host320(e.g., server host320A) from among multiple server hosts320fronted by the multipath load balancer300. Note that other load balancing techniques, such as round robin techniques, may be used to select a server host320for a connection in some embodiments. The multipath load balancer300then establishes a connection to the selected server host320A, for example a connection to an IP address/port published by the server host320A. The connection between the multipath load balancer300and the selected server host320A may be referred to as a server connection322A. Packets (e.g., TCP segments) may then begin to be exchanged between the client host330A and the server host320A via the connections332A and322A through the multipath load balancer300. The load balancer300terminates the connection from the client host330A (client connection332A) and sends the client traffic to the respective server host320A via the server connection322A. Similarly, the load balancer300terminates the connection from the server host320A (server connection322A) and sends the response traffic to the respective client host330A via the client connection332A.

In at least some embodiments, when a client host330communicates with multipath load balancer300to establish a connection to a service hosted by the server hosts320, the load balancer300determines if the client host330supports the multipath protocol (e.g., MPTCP) as part of the connection negotiation process. InFIG. 3, client host330A does support the multipath protocol. For a client host330A that supports the multipath protocol, after establishing a connection between the client host330A and a selected server host320A through multipath load balancer300via connections332A and332B, the multipath load balancer300may facilitate the establishment of a direct connection352A between the client host330A and the server host320A according to the multipath protocol. As used herein, a direct connection352in a load balanced system is a connection between a client host330and a server host320that does not pass through the load balancer. The direct connection352A may serve as another path for the connection between the client host330A and the server host320A. In at least some embodiments, to facilitate the establishment of the direct connection352A, multipath load balancer300may first obtain address/port (e.g., socket) information from server host320A, and then propose to the client host330A establishment of a direct connection to the server host320A. If the client host330A accepts the proposal, the client host330A may then communicate with the server host320A to establish the direct connection352A between the client host330A and the server host320A.

Once the direct connection352A is established, data flowing on the connection between the client host330A and the server host320A can take one of the two paths, with one path passing through multipath load balancer300via connections332A and322A and the other path passing through direct connection352A. These two paths for data flow may be referred to as subflows for the connection between the client host330A and the server host320A.

In at least some embodiments, the multipath protocol may allow an entity on a connection to specify or advertise a window size for the entity as a receiver on the connection. The window size specified by a receiver indicates how much data can be outstanding on the connection for the receiver. The other entity (the sender) will not send more than that amount of data to leave that amount of data outstanding at any time. As the receiver receives and acknowledges receipt of data on the connection, the sender may send more data. Note that both entities on a given connection may establish a window size for receiving data at the entity on the connection.

Referring toFIG. 3, in at least some embodiments, multipath load balancer300may initially advertise a standard or default window size to client host330A for client connection332A, and to server host320A for server connection322A. Thus, initially, the rate of data flow in both directions between the client host330A and the server host320A over connections332A and322A may be controlled or limited by the window size(s) advertised by the load balancer300for the two connections. Note that the advertised window sizes for the two connections may be the same, or may be different. In at least some embodiments, the load balancer300may choose the window size advertised to each sending peer on a connection to restrict the rate at which each peer may send data on the connection.

In at least some embodiments, when the client host330A and the server host320A establish a direct connection352A between the client host330A and the server host320A, each advertises a window size for the direct connection352A to the other. The rate of data flow from the client host330A to the server host320A is controlled by the window size specified by the server host320A, and conversely the rate of data flow from the server host320A to the client host330A is controlled by the window size specified by the client host330A. Note that the window sizes advertised by the client host330A and the server host320A for the direct connection352A may be the same, or may be different. Further, the window sizes advertised by the client host330A and the server host320A for the direct connection352A may be the same as or different than the window sizes advertised by the load balancer for connections332A and322A.

After the direct connection352A between the client host330A and the server host320A is established, data may begin flowing between the client host330A and the server host320A over the two subflows for the connection, with the rate of data flow on each of the subflows controlled or limited by the window size(s) for the connection(s) on the respective subflow. In at least some embodiments, the load balancer300may reduce the window size for one or both of connections322A and332A to move at least some data flow off of the subflow through the load balancer300and onto the subflow over the direct connection352A. Reducing the window size(s) may reduce the rate of data flow through the load balancer300on the connection between the client host330A and the server host320A in one or both directions. Data that would flow through the load balancer300on the connection may instead flow over the direct connection352A. Thus, reducing the window size(s) for the connections322A and332A may increase the data flow rate in one or both directions over the direct connection352A.

In at least some embodiments, the subflow through the load balancer300over connections322A and332A may be persisted after establishing the direct connection352A and reducing the window size(s) so that the connection between the client host330A and the server host320A can be monitored, and so that load balancing of the server hosts320(e.g., via a least conns technique) fronted by the load balancer300can be properly performed. However, in at least some embodiments, the window size for one or both of connections322A and332A may be reduced to the point where the rate of data flow for the connection through the load balancer300is very low compared to the rate of data flow over the direct connection352A. Thus, the majority of data flowing between the client host330A and the server host320A may pass over the direct connection352A, with a small amount of data allowed to pass through the load balancer300so that the load balancer300can monitor the connection between the client host330A and the server host320A.

In some embodiments, for at least some connections through the load balancer300that are established according to the multipath protocol, the load balancer300may choose to close the subflow for the connection through the load balancer300in both directions after a direct connection352between a client host330and a server host320is established. This, of course, results in all data flowing between the client host330and the server host320in both directions to pass over the direct connection352. The LB connection340may be closed by closing the respective connections332and322on the load balancer300. Alternatively, in some embodiments, the window size for both connections332and322may be reduced to zero.

In some embodiments, for at least some connections through the load balancer300that are established according to the multipath protocol, the load balancer300may choose to close the subflow for a connection through the load balancer300in only one direction after a direct connection352between a client host330and a server host320is established. In some embodiments, the subflow may be closed in one direction by reducing the window size for the appropriate connection332or322to zero.

As shown inFIG. 3by direct connection352B between client host330M and server host320N, the multipath load balancer300may establish connections between multiple ones of the client hosts330and selected ones of the server hosts320according to the multipath protocol (e.g., MPTCP), with direct connections352established between respective client hosts330and server hosts320. However, one or more of clients330A,330B . . .330M may not support the multipath protocol, or may reject the proposal to establish a second path to a server320according to the multipath protocol for some reason. In addition, one or more of server hosts320A,320B . . .320N may reject the proposal to establish a second path to a client330according to the multipath protocol. In these cases, as shown inFIG. 3by the connection between client host330B and server host320B through multipath load balancer300via client connection332B and server connection322B, no direct connection352is established between the client host330B and the server host320B, and all data flowing between the client host330B and the server host320B passes through the load balancer300.

FIG. 4is a flowchart of a multipath load balancing method that may be implemented in a load balanced system, according to at least some embodiments. The discussion ofFIG. 4refers toFIGS. 5A through 5E, which graphically illustrate establishing multiple paths for a connection between a client host and a server host in a load balanced system according to embodiments of a multipath load balancing method as illustrated inFIG. 4.

Referring toFIGS. 5A through 5E, a load balancer that implements the multipath load balancing method may be referred to as a multipath load balancer500. While these Figures show only a single server host520and client host530for simplicity, the multipath load balancer500may front tens, hundreds, or thousands of server hosts, and may receive connection requests from multiple client hosts for access to the service(s) provided by the server hosts fronted by the load balancer500. Note that a load balancer500may serve any number (tens, hundreds, thousands, or more) of client hosts. The multipath load balancer500acts to load balance connections from the client hosts to the server hosts according to a load balancing technique, each connection corresponding to a particular data flow between a respective client host530and server host520. In at least some embodiments, the load balancing technique may be a least connections, or least conns, technique. However, other load balancing techniques may be used, for example round robin techniques.

Further note that whileFIG. 4andFIGS. 5A through 5Egenerally describe using the multipath load balancing method in a proxy load balancer as illustrated inFIGS. 1A and 1Bin which an LB connection140includes a client connection132and a server connection122that are terminated at the load balancer100, the multipath load balancing method may also be applied in pass-through load balancers as illustrated inFIG. 1Cin which an LB connection140is established between endpoints at the client and server that goes through but is not terminated at the load balancer100.

The multipath load balancing method implemented by the multipath load balancer500in the load balanced system may leverage a multipath protocol to establish multiple (two or more) paths for at least some connections between the client hosts and the server hosts in the load balanced system. While any suitable multipath protocol may be used, an example multipath protocol that may be used in at least some embodiments is Multipath Transmission Control Protocol (Multipath TCP, or MPTCP). The multipath load balancing method as illustrated inFIG. 4assumes that both the client host530and the selected server host520support the multipath protocol (e.g., MPTCP).

As indicated at400ofFIG. 4and illustrated inFIG. 5A, a client host530communicates with the multipath load balancer500(e.g., to a Virtual IP (VIP) address hosted by the load balancer500) according to a network protocol (e.g., Transmission Control Protocol (TCP)) to request a connection, for example a connection to a service fronted by the load balancer500. In at least some embodiments, to communicate with the multipath load balancer500to request a connection, the client host530may request an IP address of a service hosted by the server hosts520in the load balanced system from another service such as a Domain Name Server (DNS). The DNS returns an IP address of the load balancer500. The client host530then sends an initial connection request to the IP address of the load balancer500according to a network protocol (e.g., TCP). In at least some embodiments, once the client host530requests the connection, the load balancer500may negotiate with the client host530to establish a client connection532to the load balancer500. At400, in the process of communicating with the requesting client host530, the load balancer500may determine if the client host530supports the multipath network protocol (e.g., MPTCP).

As indicated at402ofFIG. 4, after the client host530requests the connection, the load balancer500selects a server host520for the connection request from among the multiple server hosts fronted by the load balancer500according to a load balancing technique. The multipath load balancer500may, for example, use a least connections load balancing technique to select a server host520. However, other load balancing techniques, such as round robin techniques, may be used.

As indicated at404ofFIG. 4and illustrated inFIG. 5B, the load balancer500connects the client host530to the selected server host520, for example to an IP address/port published by the server host520. In at least some embodiments, to connect the client host530to the selected server host520, the load balancer500establishes a connection to the server host520. The connection between the load balancer500and the server host520may be referred to as a server connection522. Note that the load balancer500may open a new server connection522to the server host520or may reuse an existing server connection522to the server host520.

In at least some embodiments, after the client connection532and server connection522are established, packets (e.g., TCP segments) may be exchanged between the client host530and the server host520through the multipath load balancer500via the connections532and522. The load balancer500terminates the connection from the client host530(client connection532) and sends the client traffic to the respective server host520via the server connection522. Similarly, the load balancer500terminates the connection from the server host520(server connection522) and sends the response traffic to the respective client host530via the client connection532.

In at least some embodiments, as part of establishing the connection between the client host530and the server host520that passes through the load balancer500, the multipath load balancer500may advertise a window size for the connection to the client host530and server host520. In at least some embodiments, the load balancer500may initially advertise a standard or default window size to client host530for client connection532, and to server host520for server connection522. Thus, initially, the rate of data flow in both directions between the client host530and the server host520over the connection that passes through the load balancer500may be controlled or limited by the window size(s) advertised by the load balancer500for the two connections.

As indicated at406ofFIG. 4and illustrated inFIG. 5C, the load balancer500proposes an IP address/port (e.g., an endpoint or socket) of the server host520to the client host530for establishing a direct connection552from the client host530to the server host520. Note that a direct connection as used herein refers to a connection between a client and a server in a load balanced system that does not pass through the load balancer. In at least some embodiments, the load balancer500may query the server host520to determine an IP address/port that may be used for a direct connection552to the client host530according to the multipath protocol. The load balancer500may then send one or more messages or packets to the client host530according to the multipath protocol proposing a direct connection552to the server host520, the messages indicating the IP address/port of the server host520. In at least some embodiments, in at least some cases, rather than proposing an endpoint of the server host520to the client host530for establishing a direct connection552, the load balancer500may instead propose an endpoint of the client host530to the server host520for establishing a direct connection552from the server host520to the client host530.

As indicated at408ofFIG. 4and illustrated inFIG. 5D, the client host530opens a subflow for the connection/data flow directly to the server host520at the indicated IP address/port according to the multipath protocol (e.g., MPTCP). The connection between the client host530and the server host520may be referred to as a direct connection552. In at least some embodiments, in response to the proposal received from the load balancer500, the client host530may negotiate directly with the server host520to establish the direct connection552to the IP address/port of the server host520. As part of the negotiation, one or both of the client host530and the server host520may specify or advertise a window size for the direct connection552. The rate of data flow from the client host530to the server host520may be controlled by the window size specified by the server host520, and conversely the rate of data flow from the server host520to the client host530may be controlled by the window size specified by the client host530. Note that the window sizes advertised by the client host530and the server host520for the direct connection552may be the same, or may be different. Further, the window sizes advertised by the client host530and the server host520for the direct connection552may be the same as or different than the window sizes advertised by the load balancer for connections532and522.

After the direct connection552between the client host530and the server host520is established, data may begin flowing between the client host530and the server host520over the two subflows for the connection, one subflow over direct connection552and the other subflow through load balancer500via connections532and522. The rate of data flow on each of the subflows may be controlled or limited by the window size(s) for the connection(s) on the respective subflow.

As indicated at410ofFIG. 4and illustrated inFIG. 5E, after the direct connection552is established, the load balancer500may shrink or reduce the window size for one or both of the client and server connections. In at least some embodiments, the load balancer500may reduce the window size for one or both of connections522and524to move at least some data flow from the subflow that passes through the load balancer500via connections522and524onto the subflow over the direct connection552. Reducing the window size(s) may reduce the rate of data flow through the load balancer500on the connection between the client host530and the server host520in one or both directions; data that would flow on the subflow through connections532and522and thus through the load balancer500may instead flow over the direct connection552without passing through the load balancer500. Thus, reducing the window size(s) for the connections522and532may increase the data flow rate in one or both directions over the direct connection552, and reduce the data flowing through the load balancer500.

In at least some embodiments, the subflow through the load balancer500over connections522and532may be persisted after establishing the direct connection552and reducing the window size(s) so that the connection between the client host530and the server host520can be monitored, and so that load balancing of the server hosts (e.g., via a least conns technique) fronted by the load balancer500can be properly tracked and performed. However, in at least some embodiments, the window size for one or both of connections522and532may be reduced to the point where the rate of data flow for the connection through the load balancer500is very low compared to the rate of data flow over the direct connection552. Thus, the majority of data flowing between the client host530and the server host520may pass over the direct connection552, with a relatively small amount of data allowed to pass through the load balancer500so that the load balancer500can still monitor the connection between the client host530and the server host520, while at the same time reducing the data on the connection that flows through the load balancer500.

In some embodiments, for at least some connections through the load balancer500that are established according to the multipath protocol, the load balancer500may choose to close the subflow for the connection through the load balancer500in both directions after a direct connection552between a client host530and a server host520is established. This, of course, results in all data flowing between the client host530and the server host520in both directions to pass over the direct connection552. The LB connection that passes through the load balancer500may be closed by closing the respective connections532and522on the load balancer500. Alternatively, in some embodiments, the window size for both connections532and522may be reduced to zero. In some embodiments, for at least some connections through the load balancer500that are established according to the multipath protocol, the load balancer500may choose to close the subflow for a connection through the load balancer500in only one direction after a direct connection552between a client host330and a server host520is established. In some embodiments, the subflow may be closed in one direction by reducing the window size for the appropriate connection532or522to zero.

The multipath load balancing method as illustrated inFIG. 4assumes that both the client host530and the selected server host520support the multipath protocol (e.g., MPTCP), and that both hosts accept the request to open a direct connection as a subflow for the connection. If one or both hosts on a load balanced connection do not support the multipath protocol, or if either host chooses not to establish a direct connection for a given connection, then a direct connection is not established between the client host530and server host520, and the data flow for the connection passes through the load balancer500in both directions via the client and server connections.

The multipath load balancing method as illustrated inFIG. 4opens direct connections for subflows of connections between the client hosts and server hosts in a load balanced system according to the multipath protocol and throttles down the traffic that passes through the load balancer500by reducing the window sizes of the connections at the load balancer500. The multipath load balancing method thus reduces the amount of data that flows through the load balancer500on the connections. This helps to address the bottleneck issue of load balancers, as a load balancer of a given bandwidth (e.g., 40 Gigabits per second (Gbps)) can support more connections between client hosts and server hosts, since much of the data flowing on at least some of the connections may be passed over the direct connection rather than through the load balancer. In other words, bandwidth usage for the load balanced system gets moved off of the load balancer and onto the direct connections. Thus, fewer load balancers, or load balancers with fewer NICs, may be needed in a load balanced system. In addition, the multipath load balancing method may allow less expensive load balancers to be used in load balanced systems to support a similar number of connections and/or amount of client/server traffic as could be supported using conventional load balancing techniques and more expensive load balancers. For example, a 10 Gbps load balancer utilizing the multipath load balancing method may be able to support as many connections and/or a similar amount of client/server traffic as could be supported by a 40 or 80 Gbps load balancer using conventional load balancing methods. In addition, fewer and/or less expensive routers or other network devices may be needed between the load balancer(s) and the client hosts in the load balanced system when using the multipath load balancing method.

Establishing a multipath protocol (e.g., MPTCP) connection may typically involve a handshake process that includes a (cryptographic) key exchange, e.g. a 64-bit key exchange. When a multipath protocol connection is established between a client host and a server host through a load balancer in a load balanced system and the load balancer facilitates creation of a new subflow between the client and server according to the multipath protocol, a new connection (the direct connection) is established between the client and server (with the load balancer acting as a go-between). For security purposes, for example to prevent entities from establishing false subflows on a multipath protocol connection to snoop or steal data, the establishment of the direct connection for the additional subflow should be authenticated. However, the load balancer is acting between the server and client. Thus, in at least some embodiments, to authenticate the new subflow, the load balancer must ensure that both the client host and the server host see a consistent handshake with the same keys as if the load balancer were not in the middle. If there is a crypto algorithm exchange between the client and server, the load balancer must also ensure that this is passed unchanged.

In a load balanced system as described herein, the client and server (which may be referred to as peers) on a multipath protocol connection will initially see the other peer's IP address as that of the load balancer. Assuming neither peer has an additional IP address for the connection, then neither peer may have a reason to suggest to the other peer to establish a second direct link for the multipath protocol connection. Solutions for this that may be used in embodiments may include, but are not limited to, the following:The load balancer may inject extra data into the conversation (e.g., a duplicate ACK), which simulates one peer publishing its own IP address to the other peer.At least some servers in the load balanced system may be configured with at least two IP addresses (one for the load balancer, one for the client(s)); the servers publish their client IP addresses automatically, and the clients see the published client IP addresses of the servers and thus can connect directly.At least some servers in the load balanced system may be configured to publish its own single IP address on startup of a multipath protocol subflow; the clients may then connect directly to the published IP addresses.
Throttling the Subflows Through the Load Balancer

While the above discussion describes reducing the window size(s) (or closing) the server and client connections on the load balancer to throttle down the data flowing through the load balancer on a given multipath protocol connection and thus push data onto the direct connection between the client host and server host, there may be other methods for controlling the amount of traffic on the two (or more) subflows of a multipath connection in a load balanced system. Methods for throttling traffic flow through the load balancer may include one or more of, but are not limited to, the following:The initial path through the load balancer may be closed by the load balancer once the direct connection is up and running so that all traffic goes through the direct connection.The load balancer can set the path through the load balancer as a backup path, for example by setting the path to have backup link priority according to MPTCP, to push most or all traffic to the direct connection.As previously described herein, both paths may have the same priority, but the load balancer can reduce the window size(s) on the path that passes through the load balancer (e.g., on the client and server connections) to cause traffic to move to the direct connection.The load balancer may purposefully and negatively affect traffic flowing on the path that passes through the load balancer, for example by intentionally introducing delays, reordering, or packet dropping, to cause the client and/or server to preferably select the direct connection for future traffic. A network process on the client and/or server may detect that quality of data transmission on the path that passes through the load balancer has degraded (e.g., because of dropped packets, delays, or out-of-order packets) and thus push or move at least some of the data flow from the path that passes through the load balancer onto the alternate, direct connection between the client and the server.
Illustrative System

In at least some embodiments, a server that implements a portion or all of the methods and apparatus for load balancing using a multiple path (multipath) protocol as described herein may include a general-purpose computer system or computing device that includes or is configured to access one or more computer-accessible media, such as computer system2000illustrated inFIG. 6. In the illustrated embodiment, computer system2000includes one or more processors2010coupled to a system memory2020via an input/output (I/O) interface2030. Computer system2000further includes a network interface2040coupled to I/O interface2030.

In various embodiments, computer system2000may be a uniprocessor system including one processor2010, or a multiprocessor system including several processors2010(e.g., two, four, eight, or another suitable number). Processors2010may be any suitable processors capable of executing instructions. For example, in various embodiments, processors2010may be general-purpose or embedded processors implementing any of a variety of instruction set architectures (ISAs), such as the x86, PowerPC, SPARC, or MIPS ISAs, or any other suitable ISA. In multiprocessor systems, each of processors2010may commonly, but not necessarily, implement the same ISA.

System memory2020may be configured to store instructions and data accessible by processor(s)2010. In various embodiments, system memory2020may be implemented using any suitable memory technology, such as static random access memory (SRAM), synchronous dynamic RAM (SDRAM), nonvolatile/Flash-type memory, or any other type of memory. In the illustrated embodiment, program instructions and data implementing one or more desired functions, such as those methods, techniques, and data described above for multipath load balancing, are shown stored within system memory2020as code2025and data2026.

In one embodiment, I/O interface2030may be configured to coordinate I/O traffic between processor2010, system memory2020, and any peripheral devices in the device, including network interface2040or other peripheral interfaces. In some embodiments, I/O interface2030may perform any necessary protocol, timing or other data transformations to convert data signals from one component (e.g., system memory2020) into a format suitable for use by another component (e.g., processor2010). In some embodiments, I/O interface2030may include support for devices attached through various types of peripheral buses, such as a variant of the Peripheral Component Interconnect (PCI) bus standard or the Universal Serial Bus (USB) standard, for example. In some embodiments, the function of I/O interface2030may be split into two or more separate components, such as a north bridge and a south bridge, for example. Also, in some embodiments some or all of the functionality of I/O interface2030, such as an interface to system memory2020, may be incorporated directly into processor2010.

Network interface2040may be configured to allow data to be exchanged between computer system2000and other devices2060attached to a network or networks2050, such as other computer systems or devices as illustrated inFIGS. 1 through 5E, for example. In various embodiments, network interface2040may support communication via any suitable wired or wireless general data networks, such as types of Ethernet network, for example. Additionally, network interface2040may support communication via telecommunications/telephony networks such as analog voice networks or digital fiber communications networks, via storage area networks such as Fibre Channel SANs, or via any other suitable type of network and/or protocol.

In some embodiments, system memory2020may be one embodiment of a computer-accessible medium configured to store program instructions and data as described above forFIGS. 1 through 5Efor implementing multipath load balancing in load balanced systems. However, in other embodiments, program instructions and/or data may be received, sent or stored upon different types of computer-accessible media. Generally speaking, a computer-accessible medium may include non-transitory storage media or memory media such as magnetic or optical media, e.g., disk or DVD/CD coupled to computer system2000via I/O interface2030. A non-transitory computer-accessible storage medium may also include any volatile or non-volatile media such as RAM (e.g. SDRAM, DDR SDRAM, RDRAM, SRAM, etc.), ROM, etc, that may be included in some embodiments of computer system2000as system memory2020or another type of memory. Further, a computer-accessible medium may include transmission media or signals such as electrical, electromagnetic, or digital signals, conveyed via a communication medium such as a network and/or a wireless link, such as may be implemented via network interface2040.

CONCLUSION