Optimized network resource location

• US 6,185,598 B1
• Filed: 02/10/1998
• Issued: 02/06/2001
• Est. Priority Date: 02/10/1998
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Digital Impact Incorporated (Liberty Latin America Ltd.)
• Inventors: Greer, Richard E., Farber, David A., Swart, Andrew D., Balter, James A.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): YUAN, ALMARI ROMERO
• Application Number:
  US09/021,506
• Time in Patent Office: 1,092 Days
• Field of Search: 709/200, 709/203, 709/223, 709/224, 709/226, 709/233, 709/234, 709/235, 709/238, 709/239, 709/240, 709/241
• US Class Current: 709/200
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: G06F 2209/509 Offload
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 43/065 related to network devices
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 61/30 Managing network names, e.g. use of aliases or nicknames name-to-address mapping H04L61/45
• CPC Class Codes: H04L 61/301 Name conversion
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• 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
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1025 : Dynamic adaptation of the criteria on which the server selection is based
• CPC Class Codes: H04L 67/1036 : Load balancing of requests to servers for services different from user content provisioning, e.g. load balancing across domain name servers
• CPC Class Codes: H04L 67/1095 : Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/125 : involving control of end-device applications over a network
• CPC Class Codes: H04L 67/2895 : Intermediate processing functionally located close to the data provider application, e.g. reverse proxies
• CPC Class Codes: H04L 67/56 : Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/561 : Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 67/563 : Data redirection of data network streams
• CPC Class Codes: H04L 67/564 : Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/568 : Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5682 : Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 67/61 : taking into account QoS or priority requirements
• CPC Class Codes: H04L 9/40 : Network security protocols

Abstract

Resource requests made by clients of origin servers in a network are intercepted by reflector mechanisms and selectively reflected to other servers called repeaters. The reflectors select a best repeater from a set of possible repeaters and redirect the client to the selected best repeater. The client then makes the request of the selected best repeater. The resource is possibly rewritten to replace at least some of the resource identifiers contained therein with modified resource identifiers designating the repeater instead of the origin server.

Claims

1. A method of processing resource requests in a computer network, the method comprising,

(i) by a client:

(A) making a request for a particular resource from an origin server, the request including a resource identifier for the particular resource;

(ii) by a reflector;

(B) intercepting the request from the client to the origin server;

(C) selecting a repeater to process the request, wherein the repeater is selected based on a predicted cost or speed of transmission between the repeater and the client;

(D) providing to the client a modified resource identifier designating the repeater;

(iii) by the client;

(E) receiving the modified resource identifier from the reflector; and

(F) making a request for the particular resource from the repeater designated in the modified resource identifier;

(iv) by the repeater;

(G) receiving the request from the client; and

(H) returning the requested resource to the client.

2. A method as in claim 1 further comprising, by the repeater:

(I) making a request for the resource from the origin server; and

(J) receiving the resource from the origin server.

3. A method as in claim 1 wherein the selecting of a repeater by the reflector comprises:

(C1) partitioning the network into groups;

(C2) determining which group the client is in;

(C3) selecting, from a plurality of repeaters in the network, a set of repeaters having a lowest cost relative to the group which the client is in; and

(C4) selecting as the repeater a member of the selected set of repeaters.

4. A method as in claim 3, wherein the cost of a repeater is a value based on that repeater'"'"'s current load and a maximum load for that repeater.

5. A method as in claim 3, wherein the cost of a repeater is a value based on a predicted cost or speed of transmission between the repeater and a client in the group.

6. A method as in claim 1 wherein the particular resource itself contains at least one other resource identifier of at least one other resource, the method further comprising:

rewriting the particular resource to replace at least some of the resource identifiers contained therein with modified resource identifiers designating a repeater instead of the origin server.

7. A method as in claim 6 wherein the rewriting is performed by one of the repeater, the reflector or another repeater.

14. A method as in any one of claims 1-12 wherein the network is the Internet and wherein the resource identifier is a uniform resource locator (URL) for designating resources on the Internet, and wherein the modified resource identifier is a URL designating the repeater and indicating the reflector or origin server, and wherein the modified resource identifier is provided to the client using a REDIRECT message.

8. A method of processing resource requests in a computer network, the method comprising,

(i) by a client:

(A) making a request for a particular resource from an origin server, the request including a resource identifier for the particular resource;

(ii) by a reflector;

(B) intercepting the request from the client to the origin server;

(C) determining whether to reflect the request to a repeater;

(D) when the reflector determines not to reflect the request, forwarding the request to the origin server, otherwise

(D1) selecting a repeater to process the request, wherein the repeater is selected based on a predicted cost or speed of transmission between the repeater and the client;

(D2) providing to the client a modified resource identifier designating the repeater.

9. A method as in claim 8, further comprising, when the reflector determines to reflect the request,

(iii) by the client:

(E) receiving the modified resource identifier from the reflector; and

(F) making a request for the particular resource from the repeater designated in the modified resource identifier;

(iv) by the repeater;

(G) receiving the request from the client; and

(H) returning the requested resource to the client.

10. A method as in claim 8 wherein the reflector determines whether to reflect a request by comparing the resource identifier with regular expression patterns of repeatable resources.

11. A method as in claim 8, wherein the reflector has a threshold aggregate information rate (TAIR) associated therewith, and wherein the determining of whether to reflect the request to a repeater comprises:

determining whether the TAIR of the reflector is exceeded by a measured aggregate information rate (MAIR) for the reflector, wherein the reflector determines not to reflect the request when the MAIR exceeds the TAIR for the reflector.

12. A method as in claim 8, wherein the reflector has a threshold aggregate information rate (TAIR) associated therewith, and wherein the determining of whether to reflect the request to a repeater comprises:

probabilistically determining whether the TAIR of the reflector is exceeded by a measured aggregate information rate (MAIR) for the reflector, wherein the reflector determines not to reflect the request as an exponential function of the difference between the MAIR and the TAIR.

13. A method as in any of claims 11-12, wherein the MAIR is obtained from repeaters according to the rate at which they have transmitted data on behalf of the reflector during a given time interval.

15. In a computer network wherein clients request resources from origin servers, a method comprising:

providing at least one repeater;

providing reflectors at some of the origin servers, each reflector intercepting client resource requests made to its respective origin server; and

each reflector selectively redirecting client resource requests for certain resources to one of the repeaters, wherein a reflector determines whether or not to redirect a client resource to a repeater based on a predicted cost or speed of transmission between the repeater and the client making the resource request.

16. A method as in claim 15 further comprising, by repeaters in the network:

servicing redirected client resource requests; and

selectively maintaining copies of requested resources,

whereby resources corresponding to redirected resource requests are selectively migrated from their origin servers to one or more repeaters.

17. A computer network comprising:

a plurality of origin servers, at least some of the origin servers having reflectors associated therewith;

a plurality of repeaters; and

a plurality of clients,

wherein each reflector is adapted to intercept resource requests made to its respective origin server and to selectively redirect the resource requests to a dynamically selected repeater, wherein a repeater is selected based on a predicted cost or speed of transmission between the repeater and the client making the resource request.

18. In a computer network wherein clients request resources from origin servers, a reflector mechanism associated with an origin server, the reflector mechanism comprising:

means for intercepting a resource request made by client of an origin server;

means for analyzing the resource request to determine whether to service the request locally at the origin server;

means for determining a best repeater in the network to service the request when the analyzing means determines that the request should not be serviced locally; and

means for redirecting the client to the best repeater, wherein a repeater is selected based on a predicted cost or speed of transmission between the repeater and the client making the resource request.

19. A reflector mechanism as in claim 18 wherein the network is partitioned into groups and the means for determining the best repeater comprises:

means for determining which group the client is in;

means for selecting, from a plurality of repeaters in the network, a set of repeaters having a lowest cost relative to the group the client is in; and

means for selecting as the best repeater a member of the set of repeaters.

20. A reflector mechanism as in claim 19, wherein the cost of a repeater is a value based on a predicted cost or speed of transmission between the repeater and a client in the group.

21. A mechanism as in claim 19, wherein the cost of a repeater is a value based on that repeaters current load and a maximum load for that repeater.

22. A reflector as in claim 18 wherein the resource itself contains resource identifiers, the repeater further comprising:

means for rewriting the resource to replace at least some of the resource identifiers contained therein with modified resource identifiers designating the repeater instead of the origin server.

23. A reflector as in claim 18 wherein the resource itself contains resource identifiers, the reflector further comprising:

means for rewriting the resource to replace at least some of the resource identifiers contained therein with modified resource identifiers designating the best repeater instead of the origin server.

24. In a computer network wherein clients request resources from origin servers, a repeater mechanism comprising:

means for receiving a resource request from a client;

means for determining whether the resource is available locally;

means for, when it is determined that the resource is not available locally, obtaining the resource from an origin server, wherein the origin server is selected based on a predicted cost or speed of transmission between the origin server and the client; and

means for providing the resource to the client.

25. A method of processing resource requests in a computer network, the method comprising,

by a client, making a request for a particular resource from an origin server, the request including a resource identifier for the particular resource, and wherein the particular resource itself contains at least one other resource identifier of at least one other resource;

a reflector intercepting the request from the client to the origin server;

selecting a repeater to process the request, wherein the repeater is selected based on a predicted cost or speed of transmission between the repeater and the client;

rewriting the particular resource to replace at least some of the resource identifiers contained therein with modified resource identifiers designating a repeater instead of the origin server;

providing to the client a modified resource identifier designating the repeater;

the client receiving the modified resource identifier from the reflector; and

making a request for the particular resource from the repeater designated in the modified resource identifier;

the repeater receiving the request from the client; and

returning the requested resource to the client.

26. A method as in claim 25 wherein the rewriting is performed by one of the repeater, the reflector or another repeater.

27. A method as in any one of claims 25-26 wherein the network is the Internet and wherein the resource identifier is a uniform resource locator (URL) for designating resources on the Internet, and wherein the modified resource identifier is a URL designating the repeater and indicating the reflector or origin server, and wherein the modified resource identifier is provided to the client using a REDIRECT message.