Arrangements and methods for latency-sensitive hashing for...

Details Arrangements and methods for latency-sensitive hashing for... Arrangements and methods for latency-sensitive hashing for...

2000-01-28

2004-11-23

Jaroenchonwanit, Bunjob (Department: 2143)

Electrical computers and digital processing systems: multicomput

Computer network managing

C709S215000

Reexamination Certificate

active

06823377

ABSTRACT:

FIELD OF THE INVENTION
The present invention generally relates to the caching of web objects on network proxy servers located between client machines and content servers.
BACKGROUND OF THE INVENTION
In recent years, the growth of the Internet has exploded, especially with regard to the World Wide Web. As a consequence, user response times for accessing the Web have become increasingly unsatisfactory.
One common conventional approach to improving Web performance is to deploy proxy cache servers between clients and content servers. With proxy caching, most client requests can be serviced by the proxy caches, reducing latency delays. Network traffic on the Internet can also be significantly reduced in this manner, thus greatly reducing network congestion. In fact, many commercial companies are providing hardware and software products and solutions for Web caching, such as IBM, Sun Microsystems, Inktomi, Network Appliance and Akamai. Some of them are using geographically distributed data centers for collaborative web caching. Namely, many geographically distributed proxies are increasingly used to collaborate in web caching.
To collaborate in web caching, a coordinating protocol is generally required. Hash routing is an emerging approach to coordinating a collection of collaborating proxy caches. Examples of hash routing include the “cache array routing protocol” (CARP) and “consistent hashing”. In “Cache Array Routing Protocol, v 1.0,” (Internet Draft, http://www.ircache.net/Cache/ICP/carp.txt, February 1998, V. Valloppillil and K. W. Ross), the draft of CARP is described. In “Hash-Routing for Collections of Shared Web Caches,” (
IEEE Network Magazine
, pp. 37-44, November-December 1997, K. W. Ross), the performance of CARP and other protocols is analyzed. In “Web Caching with Consistent Hashing,” (
Proc. Of
8
th International World Wide Web Conference
, pp. 125-135, 1999, D. Karger et al.), the application of consistent hashing to web caching is described
Basically, hashing partitions the entire URL space among the caches, creating a single logical cache. Each cache is responsible for requests belonging to the assigned partition. Requests are sent to the proper proxy caches based on the hash values of the corresponding URLs. The mapping between hash values and proxy cache IDs can be done either by the browsers or by the domain name servers (DNS).
More and more geographically distributed proxies are used in collaborative web caching. For example, commercial companies, such as Akamai and Inktomi, are using cache servers residing on geographically distributed data centers for web caching. As a result, response times tend to be negatively impacted for those requests hashed into geographically distant proxies or overloaded proxies. Distant proxies tend to incur longer network latency delays. Overloaded proxies can cause significant delays as well, no matter how close they are to the browsers. As a result, a user may experience unpredictably slow response times for certain URL requests that are hashed into far away or overloaded proxy caches.
However, traditional hashing-based approach to collaborative web caching does not deal with network latency. It either avoids hashing into geographically distant proxy caches or hashes to all proxy caches regardless of network latency. For example, in “Web Caching with Consistent Hashing,” (
Proc. Of
8
th International World Wide Web Conference
, pp. 125-135, 1999), a user's geographical region is encoded into the hash value and sent by the browser to a DNS in its geographical region. The DNS then maps the encoded hash value to a proxy cache ID within the same region. Thus, requests are served only by proxies in a geographically close region. It works well if the proxy caches within a region can adequately service all the requests originated within the same region. However, if workloads are skewed among regions, proxies in one region may be overloaded while those in another region are underloaded. As a result, the degree of collaboration among proxies is limited by geographical locations.
On the other hand, one can simply hash requests into all collaborating proxy caches regardless of geographical locations. In this case, load tends to be more balanced among all the geographically distributed cooperating caches. However, it does not take into account network latency delays due to geographical distances. It does not deal with “hot spots”, either. A “hot spot” may be defined as a website or web page that experiences tremendous demand over a very short period of time, or a brief “spike” in the number of users wishing to access the website or web page. In the presence of hot spots, all the references to the hot spots are hashed into the same proxies. As a result, the proxies that handle the hot spots can easily become overloaded.
Therefore, a need has been recognized in connection with attending to the latency issue in hashing-based web caching. More specifically, a need has been recognized in connection with providing a latency-sensitive hashing for collaborative web caching among geographically distributed proxy caches.
SUMMARY OF THE INVENTION
In accordance with the at least one presently preferred embodiment of the present invention, the mentioned latency problems associated with the hashing-based approach to collaborative web caching are solved. Latency-sensitive hashing systems and methods are contemplated herein for collaborative web caching among geographically distributed proxy caches.
In one embodiment of the present invention, URL requests are hashed into all proxies. However, it takes into account latency delays and potential overloaded proxies in choosing the target proxy for a request. In one embodiment of the present invention, a request is first hashed into an anchor hash partition. Each hash partition is mapped to one of the geographically distributed proxies. Secondly, a selection algorithm is used to pick a proxy among a small number of hash partitions adjacent to the anchor hash partition. The selection is based on an objective to reduce network latency and to avoid creating overloaded proxies.
For a better understanding of the present invention, together with other and further features and advantages thereof, reference is made to the following description, taken in conjunction with the accompanying drawings, and the scope of the invention will be pointed out in the appended claims.


REFERENCES:
patent: 5933849 (1999-08-01), Srbljic et al.
patent: 5935207 (1999-08-01), Logue et al.
patent: 6026474 (2000-02-01), Carter et al.
patent: 6070191 (2000-05-01), Narendran et al.
patent: 6167438 (2000-12-01), Yates et al.
patent: 6167446 (2000-12-01), Lister et al.
patent: 6185601 (2001-02-01), Wolff
patent: 6205481 (2001-03-01), Heddaya et al.
patent: 6286084 (2001-09-01), Wexler et al.
patent: 6330561 (2001-12-01), Cohen et al.
patent: 6330605 (2001-12-01), Christensen et al.
patent: 6330606 (2001-12-01), Logue et al.
patent: 6338117 (2002-01-01), Challenger et al.
patent: 6377980 (2002-04-01), Hagersten et al.
patent: 6377991 (2002-04-01), Smith et al.
patent: 6405252 (2002-06-01), Gupta et al.
patent: 6408362 (2002-06-01), Arimilli et al.
patent: 6438652 (2002-08-01), Jordan et al.
patent: 6502175 (2002-12-01), Krishnan et al.
patent: 6532492 (2003-03-01), Presler-Marshall
patent: WO00/22526 (2000-04-01), None
patent: WO00/58871 (2000-10-01), None
Kawai, E. e tal., “An Analysis of the Number of ICP Packets on the Distributed WWW Caching System, International Workshop on Parallel Processing”, pp. 234-239, 1999.*
S. Gadde et al., “Directory Structures for Scalable Intenet Caches”, Department of Computer Science, Duke University, Durham, NC 27708-0129, Nov. 1997, pp. 1-14.*
Heddaya et al, “WebWave: globally load balanced fully distributed caching of hot published documents” 1997, International Conference on Distributed Computing Systems, pp. 160-168.*
Chiang et al., “On Request Forwarding for Dynamic Web Caching Hierachies”, 2000, IEEE, pp. 262-269.*
ASAKA, et al, “Distributed Web Caching using Hash-based Query Caching Method”, 1

Affiliated with

Also associated with

Rating

Arrangements and methods for latency-sensitive hashing for... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arrangements and methods for latency-sensitive hashing for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arrangements and methods for latency-sensitive hashing for... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3315347