Phased learning approach to determining closest content serving sites

• US 6,920,498 B1
• Filed: 08/31/2000
• Issued: 07/19/2005
• Est. Priority Date: 08/31/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Gourlay, Douglas, Aviani, James
• Primary Examiner(s): Follansbee, John
• Assistant Examiner(s): LEE, PHILIP C
• Application Number:
  US09/652,766
• Time in Patent Office: 1,783 Days
• Field of Search: 709/200, 709/241, 709/228, 709/203, 709/26, 709/251, 709/224, 709/223
• US Class Current: 709/227
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/14 Session management for real-time applications in data packet communications networks H04L65/1066

Abstract

In order to direct content requests to an appropriate content serving site in a computer network, a phased learning approach is utilized to ensure that, as best as possible, the request is made to content serving site with the shortest delay. In a setup phase, an indirect path return geographic sever load balancer times sends transit time requests to all of the individual content serving sites so that the transit requests all arrive at the content serving sites at the same time. Therefore, when the requesting fixed location receives communications from the content serving sites, it can easily tell which content serving site has the least delay by an established race condition. The winner of the race may then be relayed to the indirect path return geographic server load balancer for later usage. In an execution mode, only the m fastest content serving sites and n other sites (used to test random and new sites) are sent a transit time request when a DNS request arrives from the requesting fixed location. The particular m fastest content serving sites and n other sites may be dynamically updated so as to ensure the most reliable directing of requests. This solution provides a very efficient and effective means by which to determining closest content serving sites while keeping load balancer-created traffic at a minimum.

Claims

1. A method for using a phased learning approach for determining closest of s multiple content serving sites to a client Domain Name System (DNS) server in a computer network in including:

in a setup phase;

storing data as to the transit times of each of the content serving sites in a table;

in an execution phase;

determining a response time each of n fastest content serving sites and m other content serving sites, said n fastest content serving sites chosen by using said data and choosing the n content serving sites with the lowest transit times, said m other content serving sites chosen by selecting new content serving sites as well as randomly selecting old content serving sites, wherein n is less than s and greater than zero;

sending transit time requests to each of the n fastest content serving sites and m other content serving sites, timing said transit times requests so that they arrive at each of the n fastest content serving sites and m other content serving sites at the same time by using said response time for each of the n fastest content serving sites and m other content serving sites;

receiving data from said client DNS server as to the transit times of each of the n fastest content serving sites and m other content serving sites; and

storing said data in said table.

2. The method of claim 1, wherein said setup phase includes:

determining a response time for each of the content serving sites;

sending transit time requests to each of the content serving sites, timing said transit time requests so that they arrive at each of the content serving sites at the same time by using said response time for each of the content serving sites;

receiving data from said client DNS server as to the transit times of each of the content serving sites;

storing said data in a table.

3. The method of claim 2, wherein said determining the response time for each of the content serving sites includes:

pinging each of the content serving sites;

receiving a reply from each of the content serving sites; and

determining the response time for each of the content serving sites by computing the difference in time from said pinging to said receiving a reply for each of the content serving sites.

4. The method of claim 1, wherein said determining the response time for each of n fastest content serving sites and m other content serving sites includes:

pinging each of n fastest content serving sites and m other content serving sites;

receiving a reply from each of n fastest content serving sites and m other content serving sites; and

determining the response time for each of n fastest content serving sites and m other content serving sites by computing the difference in time from said pinging to said receiving a reply for each of said n fastest content serving sites and m other content serving sites.

5. The method of claim 1, wherein transit time is the time it takes a content serving site to send a packet to said client DNS server after receiving a transit time request.

6. The method of claim 1, wherein said data includes at least one record, said record including a transit time, a network address for said client DNS server, and a network address for a content serving site, said transit time being the transit time between said client DNS server and said content serving site.

7. The method of claim 2, wherein said sending transit time requests to each of the content serving sites includes:

sending transit time requests to each of the content serving sites in order of their response times, longest response time first, setting a delay for a transit time request for a particular content serving site from a time of the transit time request to the content serving site with the longest response time as one half of said particular content serving site'"'"'s response time.

8. The method of claim 1, wherein said sending queries to each of the n fastest content serving sites and m other content serving sites includes:

sending transit time requests to each of said content serving sites n fastest content serving sites and m other content serving sites in order of their response times, longest response time first, setting a delay for a transit time request for a particular content serving site from the time the transit time request to said n fastest content serving site or m other content serving site with the longest response time as one half of said particular content serving site'"'"'s response time.

9. The method of claim 1, wherein n is 3 and m is 2.

10. The method of claim 1, wherein n may be varied based on stability of the computer network.

11. The method of claim 1, wherein n may be varied based on a rate of change of said content serving sites making up n content serving sites.

12. The method of claim 1, wherein said setup phase occurs when the computer network is first set up.

13. The method of claim 1, wherein said execution phase occurs when the computer network is operating normally.

14. An apparatus for using a phased learning approach for determining closest of s multiple content serving sites to a client DNS server in a computer network including:

a Domain Name System (DNS) request receiver coupled to the client DNS server,

a response time determiner coupled to said DNS request receiver and coupled to the content serving sites, said response time determiner configured to determine a response time for each of n fastest content serving sites and m other content serving sites, said n fasters content serving sites chosen by using transit times of each of the content serving sites and choosing the n content serving sites with lowest transit times, said m other content serving sites chosen by selecting new content serving sites as well as randomly selecting old content serving sites, wherein n is less than s and greater than zero;

a transit time request sender coupled to said response time determiner and coupled to the content serving sites;

a data receiver coupled to the client DNS server;

a memory coupled to said sender; and

a data storer coupled to said data receiver and coupled to said memory.

15. The apparatus of claim 14, wherein said response time determiner includes an n fastest content serving site chooser and an m other content serving site chooser.

16. The apparatus of claim 14, wherein said transit time request sender includes a transit time request timer.

17. The apparatus of claim 14, wherein said response time determiner includes a pinger and a reply receiver.

18. The apparatus of claim 14, wherein said transit time request sender includes a response time orderer.

19. The apparatus of claim 14, further including a phase determiner coupled to said response time determiner, said transit time request sender, and said data receiver.

20. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for using a phased learning approach for determining closest of s multiple content serving sites to a client DNS server in a computer network, the method including:

in a setup phase;

storing data as to transit times of each of the content serving sites in a table;

in an execution phase;

determining a response time for each of n fastest content serving sites and m other content serving sites, said n fastest content serving sites chosen by using said data and choosing the n content serving sites with lowest transit times, said m other content serving sites chosen by selecting new content serving sites as well as randomly selecting old content serving sites, wherein n is less than s and greater than zero;

sending transit time requests to each of the n fastest content serving sites and m other content serving sites, timing said transit time requests so that they arrive at each of the n fastest content serving sites and m other content serving sites at the same time by using said response time for each of the n fastest content serving sites and m other content serving sites;

receiving data from said client DNS server as to the transit times of each of the n fastest content serving sites and m other content serving sites; and

storing said data in said table.

21. An apparatus for using a phased learning approach for determining closest of s multiple content serving sites to a client DNS server location in a computer network including:

means for storing data as to transit times of each of the content serving sites in a table in a setup phase;

means for determining a response time for each of n fastest content serving sites and m other content serving sites, said n fastest content serving sites chosen by using said data and choosing the n content serving sites with lowest transit times, said m other content serving sites chosen by selecting new content serving sites as well as randomly selecting old content serving sites in an execution phase, wherein n is less than s and greater than zero;

means for sending transit time requests to each of the n fastest content serving sites and m other content serving sites, timing said queries so that they arrive at each of the n fastest content serving sites and m other content serving sites at the same time by using said response time for each of the n fastest content serving sites and m other content serving sites in an execution phase;

means for receiving data from said client DNS server as to the transit times of each of the n fastest content serving sites and m other content serving sites in an execution phase; and

means for storing said data in said table in an execution phase.

22. The apparatus of claim 21, further including:

means for determining a response time for each of the content serving sites;

means for sending transit time requests to each of the content serving sites, timing said transit time requests so that they arrive at each of the content serving sites at the same time by using said response time for each of the content serving sites;

means for receiving data from said client DNS server as to the transit times of each of the content serving sites;

storing said data in a table.

23. The apparatus of claim 22, wherein said means for determining the response time for each of the content serving sites includes:

means for pinging each of the content serving sites;

means for receiving a reply from each of the content serving sites; and

means for determining the response time for each of the content serving sites by computing the difference in time from said pinging to said receiving a reply for each of the content serving sites.

24. The apparatus of claim 21, wherein said means for determining the response time for each of n fastest content serving sites and m other content serving sites includes:

means for pinging each of n fastest content serving sites and m other content serving sites;

means for receiving a reply from each of n fastest content serving sites and m other content serving sites; and

means for determining the response time for each of n fastest content serving sites and m other content serving sites by computing the difference in time from said pinging to said receiving a reply for each of said n fastest content serving sites and m other content serving sites.

25. The apparatus of claim 21, wherein transit time is the time it takes a content serving site to send a packet to said client DNS server after receiving a transit time request.

26. The apparatus of claim 21, wherein said data includes at least one record, said record including a transit time, a network address for said client DNS server, and a network addrss for a content serving site, said transit time being the transit time between said client DNS server and said content serving site.

27. The apparatus of claim 22, wherein said means for sending queries to each of the content serving sites includes:

means for sending transit time requests to each of the content serving sites in order of their response times, longest response time first, setting a delay for a query for a particular content serving site from a time of the transit time request to the content serving site with the longest response time as one half of said particular content serving site'"'"'s response time.

28. The apparatus of claim 21, wherein said means for sending queries to each of the n fastest content serving sites and m other content serving sites includes:

means for sending transit time requests to each of said content serving sites n fastest content serving sites and m other content serving sites in order of their response times, longest response time first, setting a delay for a query for a particular content serving site from the time the transit time request to said n fastest content serving site or m other content serving site with the longest response time as one half of said particular content serving site'"'"'s response time.

29. The apparatus of claim 21, wherein n is 3 and m is 2.

30. The apparatus of claim 21, wherein n may be varied based on stability of the computer network.

31. The apparatus of claim 21, wherein n may be varied based on a rate of change of said content serving sites making up n content serving sites.

32. The apparatus of claim 21, wherein said setup phase occurs when the computer network is first set up.

33. The apparatus of claim 21, wherein said execution phase occurs when the computer network is operating normally.