Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1997-12-30
2003-06-10
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
Reexamination Certificate
active
06578113
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed to a method and apparatus for validating resources in a cache memory.
Networks for providing access to data from a plurality of sources are well known. One example of such a network configuration, commonly referred to as the Internet, provides access to a plurality of data sources collectively known as the World Wide Web. The sources can make available many different types of data, that is data that reflects many different types of information such as audio information, video information or text information. In the context of the Internet and the World Wide Web, these data sources are commonly referred to as web sites. A person accessing the network can request a download of data from one or more of the sources or web sites.
An example of such a network is shown in block diagram form in FIG.
1
. In particular, a subscriber using a computer device such as a personal computer
101
gains access to the network via a local service provider (LSP)
102
by well known means. The local service provider then provides the subscriber with a connection into the data network, here shown as cloud
103
. Within the data network there are a plurality of sources or servers, for example, s
1
through s
3
.
As the subscriber operates within the network she may seek access to a particular source and call for a download of a data resource such as a document or page of information or other type of data. It is well known in the art to provide an intermediate storage mechanism which acts as a cache for resources retrieved from various ones of the servers or web sites. The network could contain a plurality of such caches. In fact, such a cache, referred to as a proxy cache
110
could be associated with the local service provider. The cache is a proxy in that if possible it acts in the place of the server that is the source of a particular resource. For instance, when the subscriber sends a request for accessing or downloading a particular page in the network, say a page residing at source s
2
, the LSP first checks in the proxy cache to determine whether the requested resource is available from the cache without having to transfer the request through the network to the server which is typically more remote. If the resource is available at the cache, the local service provider can transmit the resource back to the requester without the need of forwarding a request through the network to the server s
2
. This avoids unnecessary time delay in processing the subscriber's request.
In the context of the Internet and the World Wide Web, a proxy cache is a machine that acts as an intermediary between potentially hundreds of clients and remote web servers by funneling requests from clients to various servers. In the process, the proxy cache is frequently requesting pages to avoid contacting the server repeatedly for the same page.
A problem can arise in keeping track of whether the cached resource, page or document is still current. In one example the cache may associate an expiration time with the stored document. For example, if the stored document related to a daily newspaper generated at a particular time of day each day, a cached copy of the document would be fresh until the next occurrence of the expiration time. Upon receipt of a request for that resource the proxy cache would compare the resource's expiration time and the current time to determine whether the resource is still current or valid. If so the cached resource should be transferred to a requester in lieu of forwarding a request to a data source. Unfortunately, it is very common that the resource that is made available and stored in cache does not have a clear expiration time. It may change in five minutes or it may remain unchanged for a long time.
The prior art has provided two proposals for dealing with expiration time uncertainty.
A first approach is two provide strong cache consistency. This can be done in a number of different ways. For example, the proxy may treat the cached resource as potentially out of date on each access and send a message to the source of the data asking for an updated version of the data only if the data has been modified since the cache last downloaded the resource from the server. A problem with this technique is that it will generate a tremendous amount of messaging traffic of little value, between the cache and the server when a frequently requested resource does not change often. Another technique for providing strong cache consistency places a heavier amount of responsibility on the data sources or servers. In particular, the server would be responsible for keeping track of all of the clients who have earlier asked for downloading of the particular resource. This technique becomes unwieldy for a server when the number of clients is large. In addition, the list of clients can become out of date and as a consequence, the server could waste time and network resources sending invalidation messages to clients who are no longer caching the resource.
In a second approach for dealing with uncertain expiration times weak cache consistency is provided. This approach seeks to minimize the proxy validation and server invalidation messages by using a heuristic or a pre-defined value as an artificial expiration time on a cache resource. Unfortunately, if the protocol or estimation for the value of the artificial expiration time is incorrect then it can leave periods where the cached resource is potentially stale.
It would be beneficial to provide a stronger cache coherency with a reduction in the number of validation request messages and responses that must be sent to maintain that coherency.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for improving the operation by which the contents of the cache are validated. In accordance with an embodiment of the present invention when a proxy cache has a reason to communicate with a server with regard to a particular resource, the cache piggybacks a list of one or more of the other resources in the cache that are from the same server for which the expiration time is unknown. Thus, the proxy cache requests validation for the first resource as well as for one or more additional resources which are accessible from the very same server. The server handles the request and indicates which of the cache resources on the list are stale, if any. The proxy can then take appropriate actions to update the cache.
As a result, the proxy cache can be better assured of having more up-to-date information from the various servers with which it has been in communication. It does so without having to generate a validation request very time it receives a request for a particular cached resource. Thus, a stronger cache coherency can be achieved without the overhead cost typically attributable to such coherency.
REFERENCES:
patent: 5448726 (1995-09-01), Cramsie et al.
patent: 5465359 (1995-11-01), Allen et al.
patent: 5577251 (1996-11-01), Hamilton et al.
patent: 5581704 (1996-12-01), Barbara et al.
patent: 5611049 (1997-03-01), Pitts
Krishnamurthy Balachander
Wills Craig Ellis
Chace C. P.
Kim Matthew
LandOfFree
Method for cache validation for proxy caches does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for cache validation for proxy caches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for cache validation for proxy caches will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3100980