Implementing history-based connection-server affinity on a network load balancer

Patent metadata

Field	Value
Publication number	US-11019137-B2
Application number	US-201916294829-A
Country	US
Kind code	B2
Filing date	Mar 6, 2019
Priority date	Mar 6, 2019
Publication date	May 25, 2021
Grant date	May 25, 2021

Abstract

Techniques for implementing history-based connection-server affinity on a network load balancer are provided. In one set of embodiments, the network load balancer can receive a network packet destined for a service, where the service is associated with a plurality of servers, and where the packet is part of a network connection between a client device and one of the plurality of servers. The network load balancer can further compute, using a portion of the packet, a bucket identifier of a bucket for the network connection, identify a first server in the plurality of servers that is currently mapped to the bucket identifier in a hash table, and send the packet to the first server. If the network load balancer receives the packet back from the first server, the network load balancer can determine, based on local history information, a second server that was previously mapped to the bucket identifier in the hash table and send the packet to that second server.

First claim

What is claimed is:

1. A method comprising:
receiving, by a network load balancer, a network packet destined for a service, the service being associated with a plurality of servers, the network packet being part of a network connection between a client device and one of the plurality of servers;
computing, by the network load balancer using a portion of the network packet, a bucket identifier of a bucket for the network connection;
identifying, by the network load balancer, a first server in the plurality of servers that is currently mapped to the bucket identifier in a hash table of the network load balancer, wherein the hash table is populated with mappings between bucket identifiers and each of the active servers and inactive servers, a mapping of a specific bucket identifier to an inactive server is subsequently removed from the hash table, and the specific bucket identifier is remapped to an active server of the active servers;
sending, by the network load balancer, the network packet to the first server;
receiving, by the network load balancer, the network packet back from the first server; and
in response to receiving the network packet back from the first server:
determining, by the network load balancer, a second server in the plurality of servers that was previously mapped to the bucket identifier in an earlier mapping not present in the hash table, the determining being based on history information maintained on the network load balancer; and
sending, by the network load balancer, the network packet to the second server.

2. The method of claim 1 wherein the receiving of the network packet back from the first server indicates that the first server does not recognize the network connection.

3. The method of claim 1 further comprising:
receiving the network packet back from the second server;
determining, based on the history information, that a third server in the plurality of servers was mapped to the bucket identifier in the hash table prior to the second server; and
transmitting the packet to the third server.

4. The method of claim 1 further comprising:
receiving the network packet back from the second server;
determining, based on the history information, that no other server in the plurality of servers was mapped to the bucket identifier in the hash table prior to the second server; and
transmitting a reset packet to the client device.

5. The method of claim 1 wherein the history information includes a plurality of history entries, each history entry corresponding to a mapping between a particular bucket identifier from a prior hash table and a list of one or more servers in the plurality of servers that were previously mapped to the particular bucket identifier in the prior hash table.

6. The method of claim 5 wherein the one or more servers in the list are temporally ordered according to when each of the one or more servers was previously mapped to the particular bucket identifier in the prior hash table.

7. The method of claim 5 wherein the load balancer adds a new history entry to the history information when a bucket identifier in the hash table is remapped from a current server to a new server, the new history entry identifying the remapped bucket identifier and the current server.

8. The method of claim 5 wherein the load balancer updates an existing history entry in the history information when a bucket identifier in the hash table is remapped from a current server to a new server, wherein updating the existing history entry comprises adding the current server to the existing history entry's list of one or more servers.

9. The method of claim 1 wherein determining the second server comprises:
re-computing the bucket identifier using a portion of the network packet returned to the network load balancer;
identifying an entry in the history information that includes the bucket identifier; and
selecting a server that is identified in the entry.

10. A network load balancer comprising:
a processor configured to:
receive a network packet destined for a service, the service being associated with a plurality of servers, the network packet being part of a network connection between a client device and one of the plurality of servers;
compute, using a portion of the network packet, a bucket identifier of a bucket for the network connection;
identify a first server in the plurality of servers that is currently mapped to the bucket identifier in a hash table of the network load balancer, wherein the hash table is populated with mappings between bucket identifiers and each of the active servers and inactive servers, a mapping of a specific bucket identifier to an inactive server is subsequently removed from the hash table, and the specific bucket identifier is remapped to an active server of the active servers;
send the network packet to the first server;
receive the network packet back from the first server; and
in response to receiving the network packet back from the first server:
determine a second server in the plurality of servers that was previously mapped to the bucket identifier in an earlier mapping not present in the hash table, the determining being based on history information maintained on the network load balancer; and
send the network packet to the second server.

11. The network load balancer of claim 10 wherein the processor comprises an application-specific integrated circuit (ASIC).

12. The network load balancer of claim 10 wherein the processor comprises a general purpose central processing unit (CPU).

13. The network load balancer of claim 10 wherein the bucket identifier is computed by applying at least two hash functions to the portion of the network packet.

14. The network load balancer of claim 10 wherein the hash table includes a compressed partition and an uncompressed partition.

15. The network load balancer of claim 10 wherein the processor determines the second server by:
extracting, from the network packet returned from the first server, a version identifier;
performing a lookup into the history information using the extracted version identifier, the history information including a plurality of mappings between version identifiers and server identifiers; and
identifying a match between the extracted version identifier and a mapping in the plurality of mappings; and
determining a server identified by the matched mapping.

16. A non-transitory computer readable storage medium have stored thereon program code executable by a network load balancer, the program code comprising:
code that causes the network load balancer to receive a network packet destined for a service, the service being associated with a plurality of servers, the network packet being part of a network connection between a client device and one of the plurality of servers;
code that causes the network load balancer to compute, using a portion of the network packet, a bucket identifier of a bucket for the network connection;
code that causes the network load balancer to identify a first server in the plurality of servers that is currently mapped to the bucket identifier in a hash table of the network load balancer, wherein the hash table is populated with mappings between bucket identifiers and each of the active servers and inactive servers, a mapping of a specific bucket identifier to an inactive server is subsequently removed from the hash table, and the specific bucket identifier is remapped to an active server of the active servers;
code that causes the network load balancer to send the network packet to the first server;
code that cau

Assignees

• Arista Networks Inc

Inventors

• Capper Simon
• Kraiser Tula
• Krishnamurthy Prashanth
• Lam Peter

Classifications

• H04L67/1034

  Reaction to server failures by a load balancer · CPC title

• H04L67/1029

  using data related to the state of servers by a load balancer · CPC title

• H04L67/1023 Primary

  based on a hash applied to IP addresses or costs · CPC title

• H04L67/1012 Primary

  based on compliance of requirements or conditions with available server resources · CPC title

• H04L67/01

  Protocols · CPC title