Generation and use of network maps based on race methods

• US 8,578,052 B1
• Filed: 06/25/2009
• Issued: 11/05/2013
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: Liu, Zaide, Day, Richard David, Swildens, Eric Sven-Johan
• Primary Examiner(s): Osman, Ramy M
• Application Number:
  US12/491,798
• Time in Patent Office: 1,594 Days
• Field of Search: 709/203, 709/217, 709/223, 709/224, 709/226, 709/238, 709/241, 709/219, 709/227, 709/245, 718/105
• US Class Current: 709/241
• CPC Class Codes: H04L 2463/101 applying security measures for digital rights management
• CPC Class Codes: H04L 63/102 Entity profiles
• CPC Class Codes: H04L 63/12 Applying verification of the received information cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32

Abstract

Techniques are provided for using the mobility support features of IPv6 to allow client and server nodes to communicate without the continuing intervention of a load-balancing node that selected the server node. A load-balancing node intercepts a TCP SYN packet addressed to a virtual IP address. The load-balancing node selects a server node from among multiple server nodes, and sends the packet toward the server node. The server node sends an IPv6 packet toward the client node. The packet contains a Binding Update option that specifies the virtual IP address as a Home Address. This information causes the client node to replace destination addresses in outgoing IP packets so that packets that the client node would have sent toward the virtual IP address are sent toward the selected server node'"'"'s IP address instead. Consequently, the IP packets are routed toward the selected server node instead of the load-balancing node.

Claims

1. A computer-implemented method, comprising:

generating a network map that reflects latencies between a plurality of clients and a plurality of servers;

receiving, at a load-balancing node, a request from a client;

determining, at the load-balancing node, in response to receiving the request from the client and based at least in part on the network map, that a particular server has less latency to the client than does another server in the plurality of servers; and

the load-balancing node selecting the particular server to handle the request;

wherein generating the network map comprises;

conducting at least one race between two or more servers, in which each of the two or more servers is part of an attempt to establish a connection with a given client at substantially the same time, and as a result of the at least one race, one of the two or more servers establishes a connection with the given client before another, if any, of the two or more servers does so, thereby reflecting relative latency amongst the two or more servers to the given client; and

,

at the one of the two or more servers that first established the connection with the given client, (i) logging information identifying the given client, in response to the establishment of the connection with the given client, and (ii) sending the information identifying the given client from the one of the two or more servers, for use in generating the network map; and

,

generating the network map based at least in part on the information.

2. The method of claim 1, further comprising:

receiving, at the load-balancing node, a request from a second client that is different than the client;

determining, at the load-balancing node, in response to receiving the request from the second client and based at least in part on the network map, that a second particular server has less latency to the second client than does another server in the plurality of servers; and

the load-balancing node selecting the second particular server to handle the request from the second client;

wherein the second particular server is in a different local area network (LAN) from the particular server.

3. The method of claim 1, wherein the network map indicates, for a given client, a server that has a least amount of latency relative to that given client among servers in the plurality of servers, as determined by the at least one race.

4. The method of claim 1, wherein the network map indicates, for a given client subnet, a server that has a least amount of latency relative to that given subnet among servers in the plurality of servers, as determined by the at least one race.

5. The method of claim 1, further comprising:

determining, at the load balancing node, after selecting the particular server to handle the request, that the particular server has stopped operating;

receiving, at the load-balancing node, after determining that the particular server has stopped operating, a second request from the client;

determining, at the load-balancing node, in response to receiving the second request from the client and based at least in part on the network map, that a second particular server, which is different than the particular server, has less latency to the client than does another server in the plurality of servers; and

the load-balancing node selecting the second particular server to handle the second request from the client.

6. The method of claim 1, wherein the information identifying the given client comprises a client IP address.

7. The method of claim 1, wherein establishment of a connection with the given client by a winning one of the two or more servers prevents another of the two or more servers from establishing a connection with the given client.

8. The method of claim 1, wherein the at least one race comprises a plurality of races, and generating the network map comprises:

for a period of time, conducting the plurality of races between the two or more servers;

ending the races after the period of time ends; and

then generating the network map.

9. The method of claim 1, wherein the connection is a TCP connection.

10. An apparatus for enabling communication between nodes, the apparatus comprising one or more computers that have one or more processors and computer memory holding instructions that, upon execution by the one or more processors, cause the apparatus to:

(a) generate a network map that reflects latencies between a plurality of clients and a plurality of servers;

(b) receive a request from a client;

(c) determine, in response to receiving the request from the client, and based at least in part on the network map, that a particular server has less latency to the client than does another server in the plurality of servers; and

(d) select the particular server to handle the request;

(e) wherein generating the network map comprises;

(i) conducting at least one race between two or more servers, in which each of the two or more servers is part of an attempt to establish a connection with a given client at substantially the same time, and as a result of the at least one race, one of the two or more servers establishes a connection with the given client before another, if any, of the two or more servers does so, thereby reflecting relative latency amongst the two or more servers to the given client; and

,

(ii) receiving information identifying the given client sent from the one of the two or more servers for use in generating the network map, the information having been logged by the one of the two or more servers that first established the connection with the given client in response to the establishment of the connection with the given client; and

,

(iii) generating the network map based at least in part on the information.

11. The apparatus of claim 10 wherein upon execution by the one or more processors, the instructions further cause the apparatus to:

receive a request from a second client that is different than the client;

determine, in response to receiving the request from the second client, and based at least in part on the network map, that a second particular server has a less latency to the second client than does another server in the plurality of servers; and

select the second particular server to handle the request from the second client;

wherein the second particular server is in a different local area network (LAN) from the particular server.

12. The apparatus of claim 10, wherein the information identifying the given client comprises a client IP address.

13. The apparatus of claim 10, wherein establishment of a connection with the given client by a winning one of the two or more servers prevents another of the two or more servers from establishing a connection with the given client.

14. The apparatus of claim 10, wherein the at least one race comprises a plurality of races, and generating the network map comprises:

for a period of time, conducting the plurality of races between the two or more servers;

ending the races after the period of time ends; and

then generating the network map.

15. The apparatus of claim 10, wherein the connection is a TCP connection.

16. The apparatus of claim 10, wherein the network map indicates, for a given client, a server that has a least amount of latency relative to that given client among servers in the plurality of servers, as determined by the at least one race.

17. The apparatus of claim 10, wherein the network map indicates, for a given client subnet, a server that has a least amount of latency relative to that given subnet among servers in the plurality of servers, as determined by the at least one race.

18. A non-transitory machine-readable medium storing one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors causes one or more computing machines to perform steps comprising:

generating a network map that reflects latencies between a plurality of clients and a plurality of servers;

receiving a request from a client;

in response to receiving the request from the client, and based at least in part on the network map, determining that a particular server has less latency to the client than does another server in the plurality of servers; and

selecting the particular server to handle the request;

wherein generating the network map comprises;

conducting at least one race between two or more servers, in which each of the two or more servers is part of an attempt to establish a connection with a given client at substantially the same time, and as a result of the at least one race, one of the two or more servers establishes a connection with the given client before another, if any, of the two or more servers does so, thereby reflecting relative latency amongst the two or more servers to the given client; and

,

at the one of the two or more servers that first established the connection with the given client, (i) logging information identifying the given client, in response to the establishment of the connection with the given client, and (ii) sending the information identifying the given client from the one of the two or more servers for use in generating the network map; and

,

generating the network map based at least in part on the information.

19. The machine-readable medium of claim 18, wherein the steps further comprise:

receiving a request from a second client that is different than the first client;

determining, in response to receiving the request from the second client and based at least in part on the network map, that a second particular server has less latency to the second client than does another server in the plurality of servers; and

selecting the second particular server to handle the request from the second client;

wherein the second particular server is in a different local area network (LAN) from the particular server.

20. The machine-readable medium of claim 18, wherein the network map indicates, for a given client, a server that has a least amount of latency relative to that given client among servers in the plurality of servers, as determined by the at least one race.

21. The machine-readable medium of claim 18, wherein the network map indicates, for a given client subnet, a server that has a least amount of latency relative to that given subnet among servers in the plurality of servers, as determined by the at least one race.

22. The machine-readable medium of claim 18, wherein the steps further comprise:

determining after selecting the particular server to handle the request, that the particular server has stopped operating;

receiving after determining that the particular server has stopped operating, a second request from the client;

determining, in response to receiving the second request from the client and based at least in part on the network map, that a second particular server, which is different than the particular server, has less latency to the client than does another server in the plurality of servers; and

selecting the second particular server to handle the second request from the client.

23. The machine-readable medium of claim 18, wherein the information identifying the given client comprises a client IP address.

24. The machine-readable medium of claim 18, wherein establishment of a connection with the given client by a winning one of the two or more servers prevents another of the two or more servers from establishing a connection with the given client.

25. The machine-readable medium of claim 18, wherein the at least one race comprises a plurality of races, and generating the network map comprises:

for a period of time, conducting the plurality of races between the two or more servers;

ending the races after the period of time ends; and

then generating the network map.

26. The machine-readable medium of claim 18, wherein the connection is a TCP connection.