Distributed computing system and method for distributing user requests to replicated network servers
View Patent ↗Routing requests for data objects from clients includes receiving a request for a data object from a client, providing content servers capable of serving data objects, determining a server from the content servers, and informing the client of an address associated with the determined server accessible by the selected route. Determining a server includes, for each content server, identifying routes between the content server and the client, determining traversal times for the routes, and selecting a route from among the routes based on the traversal times.
1. A method of routing requests for data objects from clients comprising:
receiving a request for a data object from a client;
providing content servers capable of serving data objects;
determining a best server from the content servers to serve said data object to said client, the determining including
for each content server, identifying routes between the content server and the client,
determining traversal times for the routes,
ranking the routes according to the traversal times,
determining, based on the ranked routes, a set of candidate servers associated with routes having associated traversal times within a predetermined range of the traversal time of a top ranked route, the set of candidate servers including a candidate server associated with the top ranked route and at least one other candidate server associated with another of the ranked routes, and
iterating through the candidate servers to select the best server, the iterating including incrementing a running total of candidate server load based on respective server loads of the candidate servers, and identifying the best server when at least one of: (a) the running total of candidate server load exceeds a randomly determined amount of server load and (b) the last candidate server is reached; and
informing the client of an address associated with the determined best server accessible by the selected route.
2. A method as recited in claim 1 , further comprising:
identifying current load on each content server; and
using the determined current load of each content server as the respective server loads when incrementing the running total of candidate server load.
3. A method as recited in claim 1 , further comprising determining a best network border associated with the determined best server.
4. A method as recited in claim 3 , wherein the best network border is a router.
5. A method as recited in claim 3 , further comprising determining the best network border as being the network border that is geographically closest to the determined best server.
6. A method as recited in claim 1 , further comprising removing at least a first candidate server from the set of candidate servers prior to selecting the best server, upon determining that the first candidate server is in a same geographic region as a second server included in the set of candidate servers.
7. A method as recited in claim 1 , wherein the predetermined range is a predetermined percentage of the traversal time associated with the routes.
8. A method as recited in claim 1 , further comprising determining the randomly determined amount of server load as a random number within a range of one to the total load capacity of the content servers.
9. A system for routing requests for data objects from clients comprising:
content servers configured to serve the data objects; and
a director component configured to select a content server from the content servers, the director component including:
an identification component configured to identify, for each content server, routes between the content server and a requesting client;
a determination component configured to determine traversal times for the routes; and
a route selection component configured to:
rank the routes according to the traversal times,
determine, based on the ranked routes, a set of candidate servers associated with routes having associated traversal times within a predetermined range of the traversal time of a top ranked route, the set of candidate servers including a candidate server associated with the top ranked route and at least one other candidate server associated with another of the ranked routes,
iterate through the candidate servers to select a best server from the set of candidate servers to serve said data object to said client, the iterating including to increment a running total of candidate server load based on respective server loads of the candidate servers, and identifying the best server when at least one of: (a) the running total of candidate server load exceeds a randomly determined amount of server load and (b) the last candidate server is reached,
and
identify an address associated with the selected best server accessible by the selected route.
10. A system as recited in claim 9 , the director component further comprising:
a second determination component configured to determine current load on each content server; and
the route selection component further configured to use the determined current load of each content server as the respective server loads when incrementing the running total of candidate server load.
11. A system as recited in claim 9 , wherein the route selection component is further configured to determine a best network border associated with the selected best server.
12. A system as recited in claim 11 , wherein the best network border is a router.
13. A system as recited in claim 11 , wherein the route selection component is further configured to determine the best network border as being the network border that is geographically closest to the selected best server.
14. A system as recited in claim 9 , wherein the route selection component is further configured to remove at least a first candidate server from the set of candidate servers prior to selecting the best server, upon determining that the first candidate server is in a same geographic region as a second server in the set of candidate servers.
15. A system as recited in claim 9 , wherein the predetermined range is a predetermined percentage of the traversal time associated with the routes.
16. A system as recited in claim 9 , wherein the route selection component is further configured to determine the randomly determined amount of server load as a random number within a range of one to the total load capacity of the content servers.
17. A computer program product residing on a non-transitory computer readable medium for routing requests for data objects by a client of content servers configured to serve the data objects, comprising instructions for causing a computer to:
receive a request for a data object from the client;
for each content server, identify routes between the content server and the client;
determine traversal times for the routes;
rank the routes according to the traversal times;
determine, based on the ranked routes, a set of candidate servers associated with routes having associated traversal times within a predetermined range of the traversal time of a top ranked route, the set of candidate servers including a candidate server associated with the top ranked route and at least one other candidate server associated with another of the ranked routes;
iterate through the candidate servers to select a best server from the set of candidate servers to serve said data object to said client, the iterating including to increment a running total of candidate server load based on respective server loads of the candidate servers, and identifying the best server when at least one of: (a) the running total of candidate server load exceeds a randomly determined amount of server load and (b) the last candidate server is reached;
and
inform the client of an address associated with the selected best server.
18. A computer program product as recited in claim 17 , further comprising instructions for causing the computer to:
determine current load of each content server; and
use the determined current load of each content server as the respective server loads when incrementing the running total of candidate server load.
19. A computer program product as recited in claim 17 , further comprising instructions for causing the computer to determine a best router associated with the selected best server.
20. A computer program product as recited in claim 19 , further comprising instructions for causing the computer to determine the best router as being the router that is geographically closest to the selected best server.
21. A computer program product as recited in claim 17 , further comprising instructions for causing the computer to remove at least a first candidate server from the set of candidate servers prior to selecting the best server, upon determining that the first candidate server is in a same geographic region as a second server included in the set of candidate servers.
22. A computer program product as recited in claim 17 , wherein the predetermined range is a predetermined percentage of the traversal time associated with the routes.
23. A computer program product as recited in claim 17 , further comprising instructions for causing the computer to determine the randomly determined amount of server load as a random number within a range of one to the total load capacity of the content servers.