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

• US 7,020,698 B2
• Filed: 11/29/2000
• Issued: 03/28/2006
• Est. Priority Date: 05/31/2000
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Hofmann, Markus, Srinivasan, Aravind, Shepherd, Bruce, Andrews, Matthew, Winkler, Peter, Zane, Francis
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): JACOBS, LASHONDA T
• Application Number:
  US09/726,192
• Publication Number:
  US 20020038360A1
• Time in Patent Office: 1,945 Days
• Field of Search: 709/217, 709/219, 709223-226, 709/105, 709/203, 718/105
• 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 selecting a content server in a network including a plurality of content servers and at least one redirection server, comprising:

(a) creating client clusters using the steps of;

(a1) identifying clients having similar network distance proterties;

(a2) grouping distance tuples using content server ID and classless inter-domain routing address (CIDR) prefix similarity to define grouping data values, a distance tuple comprising at least one of a network distance, a content server identifier, a time-stamp, and a client internet protocol (IP) address;

(a3) storing the data values at leaf nodes of a hierarchical tree structure having a root node representing CIDR space and a plurallty of interior and leaf nodes, said data values including load information, network distances, and a number of the tuples; and

(a4) defining the client clusters by combining leaf nodes having sufficient similarity into parent nodes and identifying remaining leaf nodes as the client clusters;

(b) identifying at least one best-performing content server for each of said client clusters by selecting at least one content server having a minimal network distance to the client cluster; and

(c) mapping the client clusters with the at least one best-performing content server.

2. The method of claim 1, wherein the at least one redirection server is an authoritative domain name (DN) server coupled to a plurality of local DNS servers.

3. The method of claim 1, wherein the step (c) further comprises:

assigning selection probability to the at least one best-performing content server to ensure that maximum service capacity of the server is not exceeded.

4. The method of claim 1, wherein the step (a3) further comprises:

collecting at said content servers load tuples, wherein each load tuple comprises at least one of a time-stamp, a content-server ID, a client IP address, a number of hits, and a domain index.

5. The method of claim 4, further comprising:

pulling the distance and load tuples at successive data acquisition intervals; and

storing the distance and load tuples at said at least one redirection server.

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

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

8. The method of claim 7, wherein said round trip time is computed by monitoring data packets transmitted and received by the content servers.

9. The method of claim 1, wherein the step (c) further comprises:

assigning an assignment probability to the at least one best-performing content server.

10. The method of claim 9, wherein said assignment probabilities are obtained from a flow map characterizing data flow in the network.

11. A system for selecting a content server in a network including a plurality of content servers and at least one redirection server, comprising:

a first means creating client clusters using the steps of;

(a1) identifying clients having similar network distance properties;

(a2) grouping distance tuples using content server ID and classless inter-domain routing address (CIDR) prefix similarity to define arouning data values, a distance tuple comprising at least one of a network distance, a content server identifier, a time-stamp, and a client internet protocol (IP) address;

(a3) storing the data values at leaf nodes of a hierarchical tree structure having a root node representing CIDR space and a plurality of interior and leaf nodes, said data values including load information, network distances, and a number of the tuples; and

(a4) defining the client clusters by combining leaf nodes having sufficient similarity into parent nodes and identifying remaining leaf nodes as the client clusters;

a second means identifying at least one best-performing content server for each of said client clusters by selecting at least one content server having a minimum network distance to the client cluster; and

a third means mapping the client clusters with the at least one best-performing content server.

12. The system of claim 11, further including a forth means for assigning selection probability to the at least one best-performing content server to ensure that maximum service capacity of the server is not exceeded.

13. The system of claim 11, wherein the first means further includes:

a fourth means collecting at said content servers load tuples, wherein each load tuple comprises at least one of a time-stamp, a content-server ID, a client IP address, a number of hits, and a domain index.

14. The system of claim 11, wherein the first means further includes:

a fifth means modifying the network distance based upon a number of distance tuples received.

15. The system of claim 11, wherein the first means further includes:

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