Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1997-12-30
2004-08-31
Hudspeth, David (Department: 2651)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S148000
Reexamination Certificate
active
06785784
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of computer networking, and in particular to a method for maintaining cache storage which relieves the cache of unnecessarily high volume and cost resulting from cache object replacements due to requests from so-called “auto-fetch” utilities.
2. Related Art
In network devices equipped with cache storage, it is common to implement a cache replacement policy based on an LRU (Least-Recently Used) technique. That is, the least recently referenced objects (or pages) in the cache are removed from storage for replacement. Some existing LRU-based policies use semantics of object sizes and types for further optimization.
Recently, so-called “auto-fetch” utilities have gained popularity with users who routinely browse the World Wide Web (“the Web”). These utilities are designed for off-line browsing, retrieving predetermined Web objects of particular interest to the user during off-line times, thereby reducing the user's on-line browsing time by ensuring the objects are already available when the user logs on. Where the user accesses the Web through a network proxy, however, auto-fetch utilities tend to have an undesirable adverse effect on a proxy cache that uses a conventional LRU-based replacement policy. Since the auto-fetch utility can continuously generate arbitrarily large numbers of requests for Web objects to the network proxy, popular objects (or pages) for the majority of so-called “normal” users (that is, those not using auto-fetch utilities) are replaced by those objects requested by auto-fetch utilities. As a result, normal users may experience longer visible latencies than they otherwise would, due solely to the abnormally large volumes of cache objects attributable to auto-fetch requests. Moreover, the problem is not limited to network proxies. The same problem can arise on a network server, such as a content server, which serves large numbers of users. Again, so-called “normal” users may experience degraded performance when accessing such a server due to inordinate resource demands of auto-fetching utilities.
In view of the increased popularity of auto-fetch utilities, there is a need for a method of ensuring that users of such utilities do not unfairly monopolize shared cache resources to the detriment of other users.
SUMMARY OF THE INVENTION
According to an embodiment of the present invention, a method for maintaining a common resource shared by a plurality of entities, wherein the common resource contains a plurality of entries, each of which is associated with one of the plurality of entities, includes determining an amount of the common resource occupied by entries associated with a given one of the plurality of entities. A number of the associated entries are removed from the common resource to reduce the occupied amount if the occupied amount exceeds a predetermined threshold.
According to another embodiment of the present invention, a method for maintaining a cache storage resident in a network device coupled to a plurality of client devices, wherein the cache storage contains a plurality of cached objects, includes determining an amount of cache resource occupied by cached objects associated with a given client device. A number of those cached objects are removed from the cache storage to reduce the amount of occupied cache resource if the amount exceeds a predetermined threshold.
REFERENCES:
patent: 4969088 (1990-11-01), McAuliffe et al.
patent: 5237673 (1993-08-01), Orbits et al.
patent: 5373375 (1994-12-01), Weldy
patent: 5517612 (1996-05-01), Dwin et al.
patent: 5544320 (1996-08-01), Konrad
patent: 5673322 (1997-09-01), Pepe et al.
patent: 5684969 (1997-11-01), Ishida
patent: 5701451 (1997-12-01), Rogers et al.
patent: 5706434 (1998-01-01), Kremen et al.
patent: 5724556 (1998-03-01), Souder et al.
patent: 5727159 (1998-03-01), Kikinis
patent: 5742905 (1998-04-01), Pepe et al.
patent: 5758183 (1998-05-01), Scales
patent: 5761729 (1998-06-01), Scales
patent: 5768510 (1998-06-01), Gish
patent: 5802585 (1998-09-01), Scales et al.
patent: 5805735 (1998-09-01), Chen et al.
patent: 5872972 (1999-02-01), Boland et al.
Armando Fox and Eric A. Brewer, “Reducing WWW Latency and Bandwidth Requirements by Real-Time Distillation,” Fifth International World Wide Web Conference, May 6-10, 1996.
Armando Fox et al., Adapting to Network and Client Variability via On-Demand Dynamic Distillation, University of Cal. at Berkeley, Sep. 1996.
Jing Jin
Man-Hak Tso Michael
Hudspeth David
Intel Corporation
Tzeng Fred F.
LandOfFree
Method for protective cache replacement 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 protective cache replacement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for protective cache replacement will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3305567