Method and apparatus for a minimalist approach to implementing server selection

• US 7,886,023 B1
• Filed: 04/02/2001
• Issued: 02/08/2011
• Est. Priority Date: 01/21/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Johnson, Kirk
• Primary Examiner(s): Bruckart; Benjamin R
• Application Number:
  US09/824,527
• Time in Patent Office: 3,599 Days
• Field of Search: 709217-219, 709223-226, 709/203, 709227-229
• US Class Current: 709/219
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1025 Dynamic adaptation of the criteria on which the server selection is based

Abstract

Server selection is optimized using randomness, feedback, and fanout. A central server maintains a vector of server selection probabilities and provides a subset of candidate servers from the vector for the client in response to receiving from a client a request for a server address to provide substantive service. An interrogating node (i.e., the client or DNS proxy) probes the candidate servers and selects a best server based on at least one criterion. The client accesses the selected server for the substantive data, and the selected server updates a counter used to keep track of the number of times the server is selected. The servers feedback the number of times selected to the central server, which, in turn, updates weightings in the vector of server selection probabilities.

Claims

1. A system for optimizing server selection for clients from among a plurality of servers in a packet communication network, the system comprising:

a plurality of servers for alternatively responding to client requests;

a central server that maintains server selection weights, and, based on the weights, provides in response to a client request a candidate server list of at least two candidate servers to a network node, other than the central server, adapted to interrogate individual servers represented in the candidate server list, the central server receiving feedback from the interrogated individual servers indicating service by the individual servers in response to client requests and modifying the server selection weights based on the feedback, the central server adds to the candidate server list an extra candidate server;

wherein the extra candidate server is randomly selected; and

wherein a number of servers in the candidate server list, including the candidate servers and the extra, randomly selected, candidate server, is a fixed percentage or a fixed number beyond the number of servers selected based on the weights.

2. The system according to claim 1 further comprising a DNS server, the DNS server:

receives the client request from the client; and

based on the client requests, forwards the client requests to the central server.

3. The system according to claim 2, wherein the DNS server interrogates candidate servers in the candidate server list.

4. The system according to claim 3, wherein the DNS server selects a candidate server based on the interrogation.

5. The method according to claim 4, wherein the DNS server:

indicates to the selected candidate server that it has been selected to provide service to the requesting client; and

returns the address of the selected candidate server to the client.

6. The system according to claim 3, wherein the DNS server returns to the requesting client the address of the first server to respond to the interrogation.

7. The system according to claim 6, wherein the DNS server transmits to the client a redirection packet to inform the selected server of being selected.

8. The system according to claim 1, wherein each candidate server in the candidate server list is unique from each other candidate server in the list.

9. The system according to claim 1, wherein the feedback occurs according to at least one of the following:

number of times the respective server is selected, duration from last feedback, time of day, or requested event.

10. The system according to claim 1, wherein the weights are based on bias factors to reduce convergence time, the bias factors including at least one of:

a number of times selected, moving average based on a specified amount of time, historical count information, time of day, time of year, calendar event, or geographical location.

11. The system according to claim 1, wherein the weights sum to one.

12. The system according to claim 1, wherein the central server includes vectors of server selection weights for subsets of clients.

13. The system according to claim 1, wherein the central server includes multiple central servers organized as a distributed system.

14. The system according to claim 1, wherein the client interrogates the candidate servers in the candidate server list to measure at least one of the following:

network performance between the client and candidate server, server congestion, or server load.

15. The system according to claim 1, wherein the candidates represented in the candidate server list are pseudo-randomly selected based on the weights.

16. The system according to claim 1 wherein the network node adapted to interrogate individual servers is a client.

17. The system according to claim 1 wherein the network node adapted to interrogate individual servers is a DNS server.

18. The system according to claim 1 wherein the network node determines from an interrogation of the individual servers, represented in the candidate server list, by the issued probes and the received responses, which of the individual servers is to service the client request.

19. A method for optimizing server selection for clients from among a plurality of servers in a packet communication network, the method comprising:

providing in response to a client request for a server address a candidate server list by a central server to a network node, other than the central server, adapted to interrogate individual servers represented in the candidate server list, the candidate server list including at least two server addresses selected based on weights corresponding to the candidate servers;

selecting a preferred server from candidate server list;

feeding back service metrics to the central server from the interrogated individual servers corresponding to service provided by the respective servers;

updating the weights based on the service metric;

adding to the candidate server list an extra candidate server;

wherein the extra candidate server is randomly selected; and

wherein a number of servers in the candidate server list, including the candidate servers and the extra, randomly selected, candidate server, is a fixed percentage or a fixed number beyond the number of servers selected based on the weights.

20. The method according to claim 19 further including the step of forwarding the client request to the central server by a DNS server.

21. The method according to claim 20, wherein the step of selecting a preferred server is executed by the DNS server.

22. The method according to claim 21, further including, by the DNS server, the steps of:

informing the selected server that it has been selected to provide service to the requesting client; and

returning the address of the selected server to the client.

23. The method according to claim 21, further including, by the DNS server, the step of returning to the requesting client the address of the first server from which the probe is returned.

24. The method according to claim 23, wherein the DNS server transmits to the requesting client a redirection packet to cause the selected server to modify its respective service metric.

25. The method according to claim 19, wherein each server represented in the candidate server selection list is unique from each other server represented in the list.

26. The method according to claim 19 wherein the feedback occurs according to at least one of the following:

number of times selected, duration from last feedback, time of day, or requested event.

27. The method according to claim 19 wherein the weights are based on bias factors to reduce convergence time, the bias factors including at least one of:

number of times selected, moving average based on length of recording time, historical count information, time of day, time of year, calendar event, or geographical location.

28. The method according to claim 19 wherein the weights sum to one.

29. The method according to claim 19 wherein the central server includes unique vectors of server selection weights for subsets of clients.

30. The method according to claim 19 wherein the central server includes multiple central servers organized as a distributed system.

31. The method according to claim 19 wherein selecting the preferred server comprises interrogating the servers to measure at least one of the following:

network performance between client and server, server congestion, or server load.

32. The method according to claim 19 wherein the network node adapted to interrogate individual servers is a client.

33. The system according to claim 19 wherein the network node adapted to interrogate individual servers is a DNS server.

34. The method according to claim 19 wherein selecting the preferred server from the candidate server list includes determining from an interrogation of the individual servers, represented in the candidate server list, by the issued probes and the received responses, which of the individual servers is to service the client request.

35. The method according to claim 19, wherein the adding includes adding the extra candidate server without altering the weights of the candidate servers.

36. By a central server in a packet communication network, a method for providing a client with a list of possible optimal servers from among a plurality of servers also on the network, comprising:

maintaining weights corresponding to a plurality of servers;

in response to receiving a client request from a client, selecting a candidate server list of at least two candidate servers from among the servers represented by the weights;

providing the candidate server list to a network node, other than a network node selecting the candidate server list, adapted to interrogate individual servers represented in the candidate server list;

receiving feedback from the interrogated individual servers related to service by the servers for maintaining the weights; and

adding to the candidate server list an extra candidate server;

wherein the extra candidate server is randomly selected; and

wherein a number of servers in the candidate server list, including the candidate servers and the extra, randomly selected, candidate server, is a fixed percentage or a fixed number beyond the number of servers selected based on the weights.

37. The method according to claim 36 further including:

establishing a relationship with a DNS server to have the DNS server pass to the central server requests from clients for a server known by the central server.

38. The method according to claim 36 wherein the extra candidate server is randomly selected.

39. The method according to claim 36 wherein the weights are based on bias factors to reduce convergence time, the bias factors including at least one of:

number of times selected, moving average based on length of recording time, historical count information, time of day, time of year, calendar event, or geographical location.

40. The method according to claim 36 wherein the central server includes unique vectors of weights for subsets of clients.

41. The method according to claim 36 wherein the network node adapted to interrogate individual servers is a client.

42. The system according to claim 36 wherein the network node adapted to interrogate individual servers is a DNS server.

43. The method according to claim 36 further comprising determining from an interrogation of the individual servers, represented in the candidate server list, by the issued probes and the received responses, which of the individual servers is to service the client request.

44. A computer program product comprising:

a non-transitory computer readable medium for storing data; and

a set of computer program instructions embodied on the computer readable medium, including instructions to;

maintain weights related to service provided by servers;

in response to receiving a request from a client, select a candidate server list of at least two candidate servers from among the servers represented by the weights based on the weights;

provide the candidate server selection list to a network node, other than a network node executing the instructions to select the candidate server list, adapted to interrogate individual servers represented in the candidate server list;

receive feedback from the interrogated individual servers to maintain the weights; and

add to the candidate server list an extra candidate server;

wherein the extra candidate server is randomly selected; and

wherein a number of servers in the candidate server list, including the candidate servers and the extra, randomly selected, candidate server, is a fixed percentage or a fixed number beyond the number of servers selected based on the weights.

45. The computer program product according to claim 44 further including instructions to:

establish a relationship with a DNS server to have the DNS server pass to the central server client requests for a server known by the central server.

46. The computer program product according to claim 44 wherein the probabilities are based on bias factors to reduce conversion time, including at least one of:

number of times selected, moving average based on length of recording time, historical count information, time of day, time of year, calendar event, or geographical location.

47. The computer program product according to claim 44 wherein the central server includes unique vectors of weights for subsets of clients.

48. The computer program product according to claim 44 wherein the network node adapted to interrogate individual servers is a client.

49. The computer program product according to claim 44 wherein the network node adapted to interrogate individual servers is a DNS server.

50. The computer program product according to claim 44 further including instructions to determine from an interrogation of the individual servers represented in the candidate server list by the issued probes and the received responses, which of the individual servers is to service the client request.

51. An apparatus for providing a client with a list of possible optimal servers from among a plurality of servers also on the network, the apparatus comprising:

means for maintaining weights based on service by servers;

means for receiving a request from a client;

means for selecting a candidate server selection list of at least two candidate servers based on the weights from among the servers represented by the weights; and

means for providing the candidate server selection list to a network node other than a network node including the means for selecting the candidate server selection list, adapted to interrogate individual servers represented in the candidate server list;

means for receiving feedback from the interrogated individual servers; and

means for adding to the candidate server list an extra candidate server;

wherein the extra candidate server is randomly selected; and

wherein a number of servers in the candidate server list, including the candidate servers and the extra, randomly selected, candidate server, is a fixed percentage or a fixed number beyond the number of servers selected based on the weights.

52. The apparatus according to claim 51 further comprising means for establishing a relationship with a DNS server to have the DNS server pass requests from clients for a server to the means for receiving a request from a client.

53. The apparatus according to claim 51 wherein the network node adapted to interrogate individual servers is a client.

54. The apparatus according to claim 51 wherein the network node adapted to interrogate individual servers is a DNS server.

55. The apparatus according to claim 51 further comprising means for determining from an interrogation of the individual servers represented in the candidate server list by the issued probes and the received responses, which of the individual servers is to service the client request.

56. An apparatus for providing a client with a list of possible optimal servers from among a plurality of servers also on the network, the apparatus comprising:

one or more processors coupled to memory storing weights related to service provided by a plurality of servers, said one or more processors executing a computer program to;

maintain the weights;

receive a request from a client;

in response to the request, select a candidate server list of at least two candidate servers from among the servers represented by the weights;

add to the candidate server list an extra candidate server;

an interface coupled to the one or more processors and the network (i) to provide the candidate server list to a network node, other than a network node with the computer program to select a candidate server list, adapted to interrogate individual servers represented in the candidate server list and (ii) to receive feedback from the interrogated individual servers;

wherein the extra candidate server is randomly selected; and

wherein a number of servers in the candidate server list, including the candidate servers and the extra, randomly selected, candidate server, is a fixed percentage or a fixed number beyond the number of servers selected based on the weights.

57. The apparatus according to claim 56 wherein the one or more processors establishes a relationship with a DNS server to have the DNS server pass to the one or more processors requests from clients for a server known by the one or more processors.

58. The apparatus according to claim 56 wherein the probabilities are based on bias factors to reduce convergence time, including at least one of:

number of times selected, moving average based on length of recording time, historical count information, time of day, time of year, calendar event, or geographical location.

59. The apparatus according to claim 56 wherein the memory includes unique vectors of weights for subsets of clients.

60. The apparatus according to claim 56 wherein the network node adapted to interrogate individual servers is a client.

61. The apparatus according to claim 56 wherein the network node adapted to interrogate individual servers is a DNS server.

62. The apparatus according to claim 56 wherein the extra candidate server is randomly selected.

63. The apparatus according to claim 56 wherein each candidate server in the candidate server list is unique from each other candidate server in the list.

64. The apparatus according to claim 56 wherein a feedback occurs according to at least one of the following:

number of times the respective server is selected, duration from last feedback, time of day, or requested event.

65. The apparatus according to claim 56 wherein the weights are based on bias factors to reduce convergence time, the bias factors including at least one of:

a number of times selected, moving average based on a specified amount of time, historical count information, time of day, time of year, calendar event, or geographical location.

66. The apparatus according to claim 56 wherein the weights sum to one.

67. The apparatus according to claim 56 wherein the servers includes vectors of server selection weights for subsets of clients.

68. The apparatus according to claim 56 wherein the servers includes multiple servers organized as a distributed system.

69. The apparatus according to claim 56 wherein the client interrogates the candidate servers in the candidate server list to measure at least one of the following:

network performance between the client and candidate server, server congestion, or server load.

70. The apparatus according to claim 56 wherein the candidates represented in the candidate server list are pseudo-randomly selected based on the weights.

71. The apparatus according to claim 56 wherein the one or more processors determines from an interrogation of the individual servers represented in the candidate server list by the issued probes and the received responses, which of the individual servers is to service the client request.