System and method for locating a closest server in response to a client domain name request

• US 20020038360A1
• Filed: 11/29/2000
• Published: 03/28/2002
• Est. Priority Date: 05/31/2000
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Hofmann, Markus, Srinivasan, Aravind, Shepherd, Bruce, Andrews, Matthew, Winkler, Peter, Zane, Francis
• Granted Patent: US 7,020,698 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 41/509 wherein the managed service relates to media content delivery, e.g. audio, video or TV
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1006 with static server selection, e.g. the same server being selected for a specific client
• 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

Abstract

A scalable system and method for locating a closest server in response to a client request via an interactive distribution network, such as the Internet, are provided. A closest content server is defined as having the least round trip time for responding to a client request. The system including a plurality of content servers; and a local server in communication with a plurality of clients, the local server acting as a proxy for communicating client requests from clients to a redirection server. Client network distance and load information is periodically collected at each content server in the network from clients communicating with each of the respective content servers. The redirection server periodically aggregates the network distance and load information from each content server to create client clusters from both current and previously aggregated network distance and load information. Each client cluster represents a division or partition of the total IP address space. Each client cluster is then mapped (paired) to one or more content servers in the network. The mapping or pairing is then utilized to respond to client DN requests received from any client in the network. Another aspect of the invention involves considering the respective capacities of the content servers in the network. A selection probability is assigned to each content server/domain index pair to prevent the repeated selection of the content server having lowest round trip time thereby overloading that server'"'"'s service capacity. The selection probabilities assigned to each content server effect a load balancing to prevent overloading. Another aspect of the invention involves collecting the distance and load information without incurring any overhead cost by passively collecting TCP information as it is transmitted from clients in communication with content servers in the course of normal communications.

Claims

1. A method for determining at least one best-performing content server in response to a request in a network including a plurality of content servers, at least one redirection server, and a plurality of clients, the method comprising the steps of:

creating a plurality of client clusters, wherein each of said plurality of client clusters includes one or more clients having similar network distance properties;

identifying said at least one best-performing content server for each of said plurality of client clusters by determining network distances between each of said plurality of client clusters and each of said plurality of content servers and selecting at least one content server for each of said plurality of client clusters having a minimum network distance therebetween; and

mapping each of said plurality of client clusters to a corresponding said at least one identified best-performing content server.

2. The method of claim 1, wherein the redirection server is an authoritative domain name (DN) server which receives said requests from a plurality of local DNS servers.

3. The method of claim 2, wherein the request is a domain name (DN) request.

4. The method of claim 1, further including the step of assigning a selection probability to each of said at least one identified best-performing content server, wherein said selection probability ensures that a maximum service capacity of each of said at least one identified best-performing content server is never exceeded.

5. The method of claim 1, wherein the step of creating said plurality of client clusters includes the step of obtaining distance and load information from each of said plurality of content servers.

6. The method of claim 5, wherein the step of obtaining distance information includes the steps of:

collecting at said plurality of content servers a plurality of distance tuples wherein each distance tuple comprises one or more of the following;

a network distance, a content server identifier, a time-stamp, and a client internet protocol (IP) address; and

collecting at said plurality of content servers a plurality of load tuples wherein each load tuple comprises one or more of the following;

a time-stamp, a content-server ID, a client IP address, a number of hits, and a domain index.

7. The method of claim 5, further comprising the step of pulling said plurality of distance and load tuples from each of said plurality of content servers at successive data acquisition intervals and storing the plurality of distance and load tuples at said at least one redirection server.

8. The method of claim 6, further comprising the step of multiplying certain data values of said plurality of distance and load tuples by a weighting factor in each of said successive data acquisition intervals.

9. The method of claim 6, wherein said network distance is computed as one of a round trip time, jitter, bandwidth and packet loss.

10. The method of claim 9, wherein said round trip time is computed by monitoring all data packets transmitted and received by one of said plurality of content servers.

11. The method of claim 1, wherein the step of creating said plurality of client clusters further comprises the steps of:

grouping distance tuples according to content server ID and CIDR prefix similarity to obtain data values for each grouping;

storing said data values at respective leaf nodes of a hierarchical tree structure wherein said hierarchical tree structure includes connected nodes including a root node and a plurality of interior and leaf nodes such that an entire CIDR address space is represented by said root node; and

pruning said hierarchical tree structure to determine said plurality of client clusters.

12. The method of claim 11, wherein said data values stored at each of said respective leaf nodes include for at least one of said plurality of content servers;

a sum of network distances, a sum of the squares of network distances, and a total number of received tuples.

13. The method of claim 11, wherein the pruning step further comprises the steps of:

comparing sibling leaf nodes in said tree structure to determine whether there is sufficient similarity;

combining said sibling leaf nodes into a parent node if sufficient similarity exists;

repeating the comparing and combining steps if sufficient similarity exists; and

identifying remaining leaf nodes as said client clusters if sufficient similarity does not exist.

14. The method of claim 1, wherein the step of mapping each of said plurality of client clusters with the corresponding said at least one the identified best-performing content server comprises the step of assigning an assignment probability to each of said at least one identified best-performing content server.

15. The method of claim 13, wherein said assignment probabilities for each of said at least one identified best-performing content server is obtained from a flow map characterizing data flow in the network.

17. The system of claim 16, further including means for assigning a selection probability to each of said at least one identified best-performing content server, wherein said selection probability ensures that a maximum service capacity of each of said at least one identified best-performing content server is never exceeded.

18. The system of claim 16, wherein said means for creating further comprises means for creating said plurality of client clusters further includes means for obtaining distance and load information from each of said plurality of content servers.

19. The system of claim 18, wherein said means for obtaining distance and load information further includes:

means for collecting at said plurality of content servers a plurality of distance tuples wherein each distance tuple comprises one or more of the following;

a network distance, a content server identifier, a time-stamp, and a client IP address; and

means for collecting at said plurality of content servers a plurality of load tuples wherein each load tuple comprises one or more of the following;

a time-stamp, content-server ID, a client IP address, a number of hits, and a domain index.

20. The system of claim 16, wherein said identifying means further includes:

means for modifying said determined network distance according to the number of distance tuples received.

21. The system of claim 16, wherein said identifying means further includes:

means for maintaining said identification of said at least one identified best-performing content server for an amount of time determined by a confidence level calculation.

16. A system for determining at least one best-performing content server in response to a client request in a network including a plurality of content servers, at least one redirection server, and a plurality of clients, the system comprising:

means for creating a plurality of client clusters, wherein each of said plurality of client clusters includes one or more clients having IP addresses having similar network distance properties;

means for identifying said at least one best-performing content server for each of said plurality of client clusters by determining network distances between each of said plurality of client clusters and each of said plurality of content servers and selecting at least one content server for each of said plurality of client clusters having a minimum network distance therebetween; and

means for mapping each of said plurality of client clusters with a corresponding said at least one identified best-performing content server.