Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-07-31
2002-07-30
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S124000, C707S793000, C709S218000, C709S219000, C709S232000, C709S252000
Reexamination Certificate
active
06427187
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to caches.
2. Related Art
In a computer system in which client devices request information from one or more server devices, it is sometimes desirable to provide a cache; that is, a device that maintains copies of requested information so multiple requests for the same information can be satisfied at the cache. When requests for information are satisfied at the cache, the server devices need not receive the requests, process them, and retransmit the same information over a communication channel that links the client devices and the server devices. For example, the server devices can be web servers, the client devices can be web clients, the communication channel can be an IP network such as the Internet, and the requested information can be web objects.
Some information requested from the server devices is considered not cacheable, for one or more of several reasons. As examples, the server can refuse to allow the information to be cached, or the information can be a result of a dynamic process that can provide differing results for the same request (so caching would obviate the operation of that dynamic process). An example of dynamically processed information could include advertisements, database searches, or output from CGI scripts.
However, it often occurs that non-cacheable information is requested a second time without having changed, so the second request to the server results in identical information being returned. In a system with multiple communicating caches, transmitting the same information from a first cache to a second cache (when each already has a copy) is an inefficient use of communication resources.
Accordingly, it would be desirable to provide a method and system for operating a set of multiple communicating caches, in which transmission of repeated information is substantially reduced or eliminated. A first aspect of the invention is to maintain information at each cache to improve the collective operation of multiple communicating caches. A second aspect of the invention is to substantially reduce the amount of information transmitted between multiple communicating caches. A third aspect of the invention is to refrain from unnecessarily transmitting the same data from a first cache to a second cache when the latter already has a copy.
SUMMARY OF THE INVENTION
The invention provides a method and system for operating a set of multiple communicating caches. Between caches, unnecessary transmission of repeated information is substantially reduced.
In a first aspect of the invention, each cache maintains information to improve the collective operation of the system of multiple communicating caches. This can include information about the likely contents of each other cache, or about the behavior of client devices or server devices coupled to other caches in the system.
In a second aspect of the invention, pairs of communicating caches substantially compress transmitted information. This includes both compression in which the receiving cache can reliably identify the compressed information in response to the message, and compression in which the receiving cache will sometimes be unable to identify the compressed information.
In a third aspect of the invention, a first cache refrains from unnecessarily transmitting the same information to a second cache when each already has a copy. This includes both maintaining a record at a first cache of information likely to be stored at a second cache, and transmitting a relatively short identifier for that information in place of the information itself.
In a preferred embodiment, a set of caches are disposed in a directed graph. structure, with a set of root caches disposed for coupling to server devices and a set of leaf caches disposed for coupling to client devices. Both root caches and leaf caches store non-cacheable objects beyond their initial use, along with relatively short identifiers for the non-cacheable objects. When a server device returns identical information to a root cache in response to a request for a non-cacheable object, that root cache transmits only the identifier of the non-cacheable object to the requesting leaf cache, avoiding re-transmitting the entire object if the leaf cache still has the object.
REFERENCES:
patent: 5696932 (1997-12-01), Smith
patent: 5696948 (1997-12-01), Cruz et al.
patent: 5737635 (1998-04-01), Daines et al.
patent: 5778168 (1998-07-01), Fuller
patent: 5787470 (1998-07-01), DeSimone et al.
patent: 5802292 (1998-09-01), Mogul
patent: 5822539 (1998-10-01), Van Hoff
patent: 5870769 (1999-02-01), Freund
patent: 5918013 (1999-06-01), Mighdoll et al.
patent: 5931904 (1999-08-01), Banga et al.
patent: 5933849 (1999-08-01), Dutta et al.
patent: 5935213 (1999-08-01), Rananand et al.
patent: 5978848 (1999-11-01), Maddalozzo Jr., et al.
patent: 6009466 (1999-12-01), Axberg et al.
patent: 6012126 (2000-01-01), Aggarwal et al.
patent: 6016512 (2000-01-01), Huitema
patent: 6026474 (2000-02-01), Carter et al.
patent: 6061715 (2000-05-01), Hawes
patent: 6094662 (2000-07-01), Hawes
patent: 6289358 (2001-09-01), Mattis et al.
patent: 0 836 145 (1998-04-01), None
patent: WO 97 30539 (1997-08-01), None
Michael Baentsch, et al.: “World Wide Web Caching: The Application-Level View of The Internet”, IEEE Communications Magazine, pp. 170-178, Jun. 1997.
Syam Gadde, et al.: “Reduce, Reuse, Recycle: An Approach to Building Large Internet Caches”, pp. 93-98, May 1997.
A. Ortega, et al., Soft Caching: Web Cache Management Techniques for Images, Multimedia Signal Processing, pp. 475-480, Jun. 1997.
Banga, G. et al.: “Optimistic deltas for WWW latency reduction” Proceedings of The Usenix 1997 Annual Technical Conference, Proceedings of Usenix 1997 Annual Technical Conference, Anaheim, CA, USA, Jan. 6-10, 1997, pp. 289-303.
Yu, P. S., et al.: “Performance Study of a Collaborative Method for Hierarchical Caching In Proxy Servers” Computer Networks and ISDN Systems, NL, North Holland Publishing. Amsterdam. vol. 30, No. 1-7, Apr. 1 1998, pp. 215-224.
Zheng Wang & Jon Crowcroft, “Prefetching In World Wide Web”, Department of Computer Science, University College London WC1E 6BT, United Kingdom, 1996.
Ken-ichi Chinen, et al., “An Interactive Prefetching Proxy Server for Improvement of WWW Latency”, Nara Institute of Science and Technology, Japan.
Alonso, et al, “Dynamic Hierarchical Caching in Large-Scale Distributed File Systems”, Department of Computer Science, Princeton University, Princeton, NJ, 1992.
Azer Bestavros, “WWW Traffic Reduction and Load Balancing Through Server-Based Caching”, Boston University, 1997.
Carlos R. Cunha and Carlos F. B. Jaccoud. “Determining WWW User's Next Access and Its Application to Pre-fetching”. 1997 IEEE.
Ari Luotonen and Kevin Altis. “World-Wide Web Proxies”. Apr. 1994.
Donna Mecozzi and James Minton. “Design for a Transparent, Distributed File System”. Lawrence Livermore National Laboratory. Livermore, California. 1991 IEEE.
Anderson Matthew D.
Cache Flow, Inc.
Kim Matthew
Swernofsky Law Group PC
LandOfFree
Multiple cache communication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple cache communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple cache communication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2846316