Arrangements and methods for latency-sensitive hashing for collaborative web caching

• US 6,823,377 B1
• Filed: 01/28/2000
• Issued: 11/23/2004
• Est. Priority Date: 01/28/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip Shi-lung, Wu, Kun-Lung
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US09/493,904
• Time in Patent Office: 1,761 Days
• Field of Search: 709/214-215, 709/224, 710/118, 710/129
• US Class Current: 709/223
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/289 Intermediate processing functionally located close to the data consumer application, e.g. in same machine, in same home or in same sub-network
• 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/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Systems and methods for collaborative web caching among geographically distributed cache servers, particularly, latency-sensitive hashing systems and methods for collaborative web caching among geographically distributed proxy caches. Network latency delays as well as proxy load conditions are taking into consideration during hashing. As a result, requests can be hashed into geographically closer proxy caches if the load conditions permit. Otherwise, requests will be hashed into geographically distant proxy caches to better balance the load among the caches.

Claims

1. Method of selecting a proxy cache, said method comprising the steps of:

defining a plurality of proxy caches into which a URL is capable of being hashed;

identifying a candidate set of proxy caches, wherein said identifying comprises;

hashing the URL into an anchor hash partition in a hashing space;

forming a candidate set of hash partitions by including one or more nearby partitions in the hashing space into said anchor hash partition;

mapping each partition to a proxy cache; and

selecting a proxy cache from the candidate set at least on the basis of latency.

2. The method according to claim 1, wherein said selecting step comprises selecting a proxy cache from the candidate set at least on the basis of latency and load condition.

3. The method according to claim 1, wherein said selecting step comprises selecting a proxy cache from the candidate set of proxies based at least on minimum response time.

4. The method according to claim 1, wherein said selecting step comprises selecting a proxy cache from the candidate set of proxies based at least on discounted response time that prefers the anchor proxy cache unless the response time is better by a predetermined amount.

5. The method according to claim 1, wherein said selecting step comprises selecting a proxy cache from the candidate set of proxies based at least on the condition that a proxy cache server is not overloaded.

6. The method according to claim 1, wherein the nearby partitions comprise partitions with hash values greater than that of the anchor partition.

7. The method according to claim 1, wherein the partitions comprise partitions with hash values less than that of the anchor partition.

8. The method according to claim 1, wherein the nearby partitions comprise partition with hash values both greater and less than that of the anchor partition.

9. The method according to claim 1, wherein said mapping step comprises hashing each hash partition into a number between 1 and P, wherein P represents the total number of proxies.

10. The method according to claim 1, wherein said mapping step further comprising

for each proxy, generating N/P random numbers between 0 and 1, N represents the total number of hash partition and # represents the total number of proxies;

generating a prosy list by sorting the corresponding N random number generated; and

assigning each hash partition to one proxy based on the sorted proxy list.

11. Method of selecting a proxy cache, said method comprising the steps of:

defining a plurality of proxy caches into which a URL is capable of being hashed;

creating an indirect mapping of hash partitions to a proxy ID array;

hashing the URL into an anchor hash partition in a hashing space;

finding the corresponding anchor proxy cache;

forming a candidate set of proxy caches by including one or more nearby proxy caches from the proxy ID array into the anchor proxy cache; and

selecting a proxy cache from the candidate set at least on the basis of latency.

12. The method according to claim 11, wherein the step of creating an indirect mapping of hash partitions to a proxy ID array further comprises:

forming a proxy ID array with collaborative proxy caches;

creating a hash partition segment that maps each hash partition to the index of the proxy ID array; and

replicating the hash partition segment for a predetermined number of times.

13. System for selecting a proxy cache, said system comprising:

defining a plurality of proxy caches into which a URL is capable of being hashed;

an identifier adapted to;

hash the URL into an anchor hash partition in a hashing space;

form a candidate set of hash partitions by including one or more nearby partitions in the hashing space into said anchor hash partition; and

map each partition to a proxy cache; and

a selector for selecting a proxy cache form the candidate set at least on the basis of latency.

14. The system according to claim 13, wherein said selector is adapted to select a proxy cache from the candidate set at least on the basis of latency and load condition.

15. The system according to claim 13, wherein said identifier is further adapted to:

create an indirect mapping of harsh partition to a proxy ID array;

hash the URL into an anchor hash partition;

find the corresponding anchor proxy cache; and

form a candidate set of proxy caches by including one or more nearby proxy caches from the proxy ID array into the anchor proxy cache.

16. The system according to claim 15, wherein said identifier, in creating an indirect mapping, of hash partitions to a proxy ID array, is adapted to:

form a proxy ID array with collaborative proxy caches;

create a hash partition segment that maps each hash partition to the index of the proxy ID array; and

replicate the hash partition segment for a predetermined number of times.

17. The system according to claim 13, wherein said selector is adapted to select a proxy cache from the candidate set of proxies based at least on minimum response time.

18. The system according to claim 13, wherein said selector is adapted to select a proxy cache from the candidate set of proxies based at least on discounted response time that prefers the anchor proxy cache unless the response time is better by a predetermined amount.

19. The system according to claim 13, wherein said selector is adapted to select a proxy cache from the candidate set of proxies based at least on the condition that a proxy cache server is not overloaded.

20. The system according to claim 13, wherein the nearby partitions comprise partitions with hash values greater than that of the anchor partition.

21. The system according to claim 13, wherein the nearby partitions comprise partitions with hash values less than that of the anchor partition.

22. The system according to claim 13, wherein the nearby partitions comprise partitions with hash values both greater and less than that of the anchor partition.

23. The system according to claim 13, wherein said identifier is adapted to map each hash partition into a number between 1 and P, wherein P represents the total number of proxies.

24. The system according to claim 13, wherein said identifier, in mapping, is adapted to:

for each proxy, generate N/P random numbers between 0 and 1, wherein N represents the total number of hash partitions and P represents the total number of proxies;

generate a proxy list by sorting the corresponding N random numbers generated; and

assign each hash partition to one proxy based on the sorted proxy list.

25. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for selecting a proxy cache, said method steps comprising:

defining a plurality of proxy caches into which a URL is capable of being hashed;

identifying a candidate set of proxy caches, wherein said identifying comprises;

hashing the URL into an anchor hash partition in a hashing space;

forming a candidate set of hash partitions by including one or more nearby partitions in the hashing space into said anchor hash partition;

mapping each partition to a proxy cache; and

selecting a proxy cache from the candidate set at least on the basis of latency.