Refreshment policies for web content caches.
Web content caches are often placed between end users and origin servers as a mean to reduce server load, network usage, and ultimately, user-perceived latency. Cached objects typically have associated expiration times, after which they are considered stale and must be validated with a remote server (origin or another cache) before they can be sent to a client. A considerable fraction of cache "hits" involve stale copies that turned out to be current. These validations of current objects have small message size, but nonetheless, often induce latency comparable to full-fledged cache misses. Thus, the functionality of caches as a latency-reducing mechanism highly depends not only on content availability but also on its freshness. We propose policies for caches to proactively validate selected objects as they become stale, and thus allow for more client requests to be processed locally. Our policies operate within the existing protocols and exploit natural properties of request patterns such as frequency and recency. We evaluated and compared different policies using trace-based simulations.
INTRODUCTION
Caches are often placed between end-users and origin servers
as a mean to reduce user-perceived latency, server load, and
network usage (see Figure 1). Among these dierent performance
objectives of caches, improving end-user Web experience
is gradually becoming the most pronounced. Many
organizations are deploying caching servers in front of their
LANs, mainly as a way to speed up users Web access. Gen-
erally, available bandwidth between end-users and their Internet
Service Providers (ISPs) is increasing and is complemented
by short round trip times. Thus, the latency bottleneck
is shifting from being between end-users and cache
to being between cache and origin servers. From the view-point
of Web sites and Content Distribution Networks (like
decreasing costs of server-machines and back-
An earlier version of the paper appeared in the Proceedings
of Infocom '01 [1].
bone connectivity bandwidth along with increasing use of
the Web for commercial purposes imply that server and net-work
load are gradually becoming a lesser issue relative to
end-user quality of service. At the limit, these trends indicate
that communication time between local caches and
remote servers increasingly dominates cache service-times
and user-perceived latency, and that technologies which provide
tradeos between tra-c-increase and latency-decrease
would become increasingly worthwhile for both Web sites
and ISPs.
Servicing of a request by a cache involves remote communication
if the requested object is not cached (in which case
the request constitutes a content miss). Remote communication
is also required if the cache contains a copy of the
object, but the copy is stale, that is, its freshness lifetime
had expired and it must be validated (by the origin server
or a cache with a fresh copy) prior to being served. If the
cached copy turns out to be modied, the request constitutes
a content miss. Otherwise, the cached copy is valid and we
refer to the request as a freshness miss. Validation requests
that turn out as freshness misses typically have small-size
responses but due to communication overhead with remote
servers, often their contribution to user-perceived latency is
comparable to that of full-edged
content misses.
Thus, cache service times can be improved by reducing both
content and freshness misses. The content hit rate is measured
per object or per byte and sometimes weighted by
estimated object fetching cost. It is dictated by the available
cache storage and the replacement policy used. Replacement
policies for Web caches were extensively studied
(e.g. [3, 4, 5, 6, 7, 8, 9, 10]). Policies that seem to perform
well are Least Recently Used (lru, which evicts the
least recently requested object when the cache is full), Least
Frequently Used (lfu, which evicts the least-frequently requested
object), and Greedy-Dual-Size (which accounts for
varying object sizes and fetching costs). Squid [11], a popular
caching server software, implements the lru policy. Under
these replacement policies, however, and due to decreasing
storage cost, cache hit rate is already at a level where
it would not signicantly improve even if unbounded storage
is made available. Content availability can be improved
by prefetching [12, 13], but prefetching of content involves
more involved predictions and induces signicant bandwidth
overhead. The freshness hit rate of a cache is not directly
addressed by replacement policies or captured by the content
hit rate metric.
clients origin servers
cache

Figure

1: Schematic conguration of Cache, clients,
and origin servers
The expiration time of each object is determined when it
is brought into the cache, according to attached HTTP response
headers provided by the origin server. Expired content
must be validated before being served. Most current
caching platforms validate their content passively i.e. only
when a client request arrives and the cached copy of the object
is stale. They perform validation via a conditional GET
request (typically this is an If-Modified-Since (IMS) Get
request). This means that validation requests are always
performed \online," while the end-user is waiting. Here we
promote proactive refreshment where the cache initiates unsolicited
validation requests for selected content. Such \of-
ine" validations extend freshness time of cached objects
and more client requests can be served directly from the
cache. Our motivation is that the most signicant cost issue
associated with freshness misses is their direct eect on
user-perceived latency rather than their eect on server and
network load, and thus it is worth performing more than
one \oine" validation in order to avoid one performed \on-
line." We formalize a cost model for proactive refreshment,
where overhead cost of additional validation requests to origin
servers is balanced against the increase in freshness hits.
We propose and evaluate refreshment policies, which extend
freshness periods of selected cached objects. The
decision of which objects to renew upon expiration varies
between policies and is guided by natural properties of the
request history of each object such as time-to-live (TTL)
values, popularity, and recency of previous requests. Refreshment
policies can also be viewed as prefetching fresh-
ness. Their methodology and implementation, however, is
closer to replacement policies than object prefetching al-
gorithms. Our refreshment policies resemble common replacement
policies (such as lru and lfu) in the way objects
are prioritized. First, policies prefer renewing recently-
or frequently-requested objects. Second, implementation is
similar since object value is determined only by the request-
history of the object rather than by considering request
history of related objects. Another dierence of refreshment
and document prefetching is that validations typically
have considerably smaller response-sizes than complete doc-
uments, but due to communication overhead, the latency
gap is not nearly as pronounced. Hence, refreshment potentially
provides considerably better tradeos of bandwidth
vs. reduced latency compared to object prefetching.
Our experimental study indicates that the best among the
refreshment policies we have studied can eliminate about
half of the freshness misses at a cost of 2 additional validation
requests per eliminated freshness miss. Freshness
themselves constitute a large fraction (30%-50%) of
cache hits in a typical cache today. Therefore we conclude
that one can considerably improve cache performance by
incorporating a refreshment policy in it.

Overview

The paper proceeds as follows. We discuss related work
in Section 2. We then provide a brief overview of HTTP
freshness control in Section 3. In Section 4 we discuss and
analyze our log data. In Section 5 we present the dierent
refreshment policies. In Section 6 we describe our methodology
for trace-based simulations and the simulation results
for the performance of the dierent policies. We conclude in
Section 7 with a summary and future research directions.
2. RELATED WORK
Recent work addressed validation latency incurred on freshness
misses, including transferring stale cached data from
the cache to the client's browser while the data validity is being
veried [14] or while the modied portion (the \delta")
is being computed [15]. These schemes, however, may require
browser support and are eective only when there is
limited bandwidth between end-user and cache (such as with
modem users).
Some or all freshness misses can be eliminated via stronger
cache consistency. Cache consistency architectures include:
server-driven mechanisms where clients are notied by the
server when objects are modied (e.g. [16, 17]); client-driven
mechanisms, where the cache validates with the server objects
with a stale cached copy; and hybrid approaches where
validations are initiated either at the server or the client.
Hybrid approaches include the server piggybacking validations
on responses to requests for related objects [18, 19, 20],
which are used by the cache to update the freshness status
of its content. Another hybrid approach is leases where the
server commits to notify a cache of modication, but only for
a limited pre-agreed period [21, 22, 23, 24]. Server-driven
mechanisms provide strong consistency and can eliminate
all freshness misses. Hybrid approaches can provide a good
balance of validation overhead and reduced validation traf-
c. None of these mechanisms, however, is deployed or even
standardized. Implementation requires protocol enhancements
and software changes not only at the cache, but at
all participating Web servers, and may also require Web
servers to maintain per-client state. Hence, it is unlikely
they become widely deployed in the near future. Mean-
while, except for some proprietary coherence mechanisms
deployed for hosted or mirrored content [2, 25] (which require
control of both endpoints), the only coherence mechanism
currently widely deployed and supported by HTTP/1.1
is client-driven based on TTL (time-to-live). Our refreshment
approach utilizes this mechanism.
We considered refreshment policies similar to the ones proposed
here in [26] for caches of Domain Name System (DNS)
servers. Each resource record (RR) in the domain name system
has a TTL value initially set by its authoritative server.
A cached RR becomes stale when its TTL expires. Client
queries can be answered much faster when the information
is available in the cache, and hence, refreshment policies
which renew cached RRs oine increase the cache hit rate
and decrease user-perceived latency.
Although not yet supported by some widely deployed Web
caching platforms (e.g., Squid [11]), proactive refreshment is
oered by some cache vendors [27, 28]. Such products allow
refreshment selections to be congured manually by the administrator
or integrate policies based on object popularity.
Our work formalizes the issues and policies and systematically
evaluates them.
3. FRESHNESS CONTROL
We provide a simplied overview of the freshness control
mechanism specied by HTTP and supported by compliant
caches. For further details see [29, 30, 11, 31, 32]. Caches
compute for each object a time-to-live (TTL) value during
which it is considered fresh and beyond which it becomes
stale. When a request arrives for a stale object, the cache
must validate it before serving it, by communication either
with an entity with a fresh copy (such as another cache) or
with the origin server. The cachability and TTL computation
is performed using directives and values found in the
object's HTTP response headers.
When the cache receives a client request for an object then
it acts as follows:
If the object is cached and fresh, the request constitutes
content and freshness hit (chit and fhit respec-
tively) and the cached copy is immediately returned
to the client.
If the object is cached, but stale, the cache issues a
conditional HTTP GET request to the origin server
(or another appropriately-selected cache). The conditional
GET uses the entity tag of the cached copy
(with HTTP/1.1 and if an E-tag value was provided
with the response) or it issues an If-Modified-Since
request with the Last-Modified response header
value (indicating last modication time of the object).
If the source response is Not-Modified then the request
constitutes a content hit (chit) but a freshness
miss (fmiss). If the object was modied, the request
is a content miss (cmiss-r).
If the item is not found in the cache, then it is fetched
from the origin (or another cache) and the request constitutes
a content miss (cmiss-d).
If the request arrives from the client with a no-cache
header then the cache forwards it to the origin server.
The cache must forward the request even if it has a
fresh copy. The cache uses the response to replace or
refresh its older copy of the object. We refer to such
requests as no-cache requests.
The TTL calculation for a cachable object as specied by
HTTP/1.1 compares the age of the object with its freshness
lifetime. If the age is smaller than the freshness lifetime
the object is considered fresh and otherwise it is considered
stale. The TTL is the freshness lifetime minus the age (or
zero if negative).
The age of an object is the dierence between the current
time (according to the cache's own clock) and the timestamp
specied by the object's Date response header (which is
supposed to indicate when the response was generated at
the origin). If an age header is present, the age is taken to
be the maximum of the above and what is implied by the
age header.
Freshness lifetime calculation then proceeds as follows. First,
if a max-age directive is present, the value is taken to be the
freshness lifetime. Otherwise, if Expires header (indicating
absolute expiration time) is present, the freshness lifetime
is the dierence between the time specied by the Expires
header and the time specied by the Date header (zero if
this dierence is negative). Thus, the TTL is the dierence
between the value of the Expires header and the current
time (as specied by the cache's clock). Otherwise, no explicit
freshness lifetime is provided by the origin server and
a heuristic is used: The freshness lifetime is assigned to be
a fraction (HTTP/1.1 mentions 10% as an example) of the
time dierence between the timestamp at the Date header
and the time specied by the Last-Modified header, subject
to a maximum allowed value (usually 24 hours, since
HTTP/1.1 requires that the cache must attach a warning if
heuristic expiration is used and the object's age exceeds 24
hours).
Before concluding this overview, we point on two qualitative
issues with the actual use of freshness control and their
relation to our refreshment approach. In [33] we analyze
the distribution of dierent freshness control mechanisms
for objects in the traces we used and it shows that the large
majority of cachable objects do not have explicit directives.
For these objects, the heuristic calculation is used to determine
the freshness lifetime, and thus, tradeos between
freshness and coherence can be controlled by tuning parameter
values and URL lters [31]. Our refreshment policies
are applied on top of this heuristic, take it as a given, and
attempt to reduce freshness misses without further compromising
coherence. Another important issue suggested by
recent studies is that cache control directives and response
header timestamp values are often not set carefully or ac-
curately. These practices may skew freshness calculations
away from the original intent [32, 34, 33]. This issue is also
orthogonal to our approach since our policies, like caches,
take these settings at face value.
4.
We used two 6 days NLANR cache traces [35] collected from
the UC and SD caches from January 20th till January 25th,
2000. The NLANR caches run Squid [11] which logs and
labels each request with several attributes such as the request
time, service time, cache action taken, the response
code returned to the client, and the response size.
The data analysis below considered all HTTP GET requests
such that a 200 or 304 response codes (OK or Not-Modified)
were returned to the client. We classied each of these requests
as fhit, fmiss, cmiss-r, cmiss-d, or no-cache using the
Squid logging labels as follows.
Content hits:
{ fhit: (freshness hit) the cache had a fresh cached
copy. Squid labels TCP HIT, TCP MEM HIT,
{ fmiss: (freshness miss) the cache had a stale cached
copy and validated it. Squid label TCP REFRESH HIT.
Content misses:
{ cmiss-r: the cache had a stale cached copy, issued
an IMS request, and got a new copy with a Modied
response. Squid label TCP REFRESH MISS.
{ cmiss-d: there was no cached copy of the object.
Squid label TCP MISS.
no-cache: the request arrived with a no-cache request
header. Squid label TCP CLIENT REFRESH MISS.
The table of Figure 2 shows the fraction of requests of each
type.
Requests classied as fmisses, cmisses, or no-cache involve
communication with the origin server or another cache. Freshness
misses, targeted by refreshment policies, constitute 13%
(UC) and 19% (SD) of all such requests. Moreover, it is evident
that freshness misses constitute 31% (UC) and 43%
(SD) of all content hits (requests classied as fmisses or
fhits). These NLANR caches directed most validation requests
(fmisses and cmisses-r) to the origin server (100% in
the UC cache and 99.3% in the SD cache). It is also apparent
that the vast majority (90% for UC and 95% for SD)
of validation requests return Not-Modified (are classied as
fmisses).
The NLANR traces also recorded the service time of each
request. That is, the time from when the HTTP request
is received to when the last byte of the response is written
to the client's socket. Note that this is usually one Round
Trip Time (RTT) less than from the client's viewpoint. Figure
3 plots the Cumulative Distribution Function (CDF)
of service time of requests, broken down by the cache ac-
tion. The gap between freshness misses to freshness hits
indicates the potential benet, in terms of latency, of eliminating
fmisses. The gap between freshness misses and content
misses is in part due to the additional time required to
transfer a larger-size response. Another explaining factor is
that content misses exhibit less locality of reference in the
sense that the elapsed time since the preceding request to
the server is more likely to be longer. The decreased locality
implies longer DNS resolutions of the server's hostname,
since the required DNS records are less likely to be cached,
and longer response time for the HTTP request, since the
origin server is more likely to be \cold" with respect to the
cache 1 . The similar service time distribution for no-cache
and freshness misses suggests that most no-cache requests
are made to popular cached content.

Figure

4 plots the CDF of service times on freshness misses
and freshness hits, further broken down by the response code
that the cache returned to the client. HTTP response code
200 indicates that content was returned whereas response
code 304 (Not-Modified) indicates that the client issued
an IMS GET request and that its copy was validated by the
cache. Responses with code 304 are typically smaller-size
than responses with code 200. We can see that freshness
hits with a 304 response to the client had minimal service
time whereas freshness hits with 200 responses re
ect RTTs
Our study in [36] indicates that a rst HTTP request to
a server in a time period is more likely to take longer than
subsequent ones.
between the cache and its clients and additional processing.
The gap for freshness misses between 200 and 304 responses
is also similar and re
ects the additional communication between
cache and clients due to the larger transmitted response
size.
5. REFRESHMENT POLICIES
Refreshment policies associate with every cached object a
renewal credit (a nonnegative integer). When a cached copy
is about to expire (according to its respective TTL interval),
and it has nonzero renewal credit, a renewal request is sent
to the respective authoritative server, and the renewal credit
is decremented.
The association of renewal credits to objects is governed by
the particular policy. The policies we consider may increment
the renewal credit only upon a client request. Renewal
scheduling can be implemented via a priority queue,
grouping together objects with close-together expiration, or
possibly by an event-triggered process.
We discuss two types of renewal requests:
1. Conditional fetch: The cache noties the server of
last modication times or entity tag(s) of cached ver-
sion(s) of the object, and requests either a validation
of its current version or a new valid version. (This
is supported by HTTP/1.0 by an If-Modified-Since
GET request)
2. Pure validation request: Test whether the cached
version of the object is valid, without requesting a valid
copy if it is no longer valid. (Under HTTP/1.0 this
is performed by issuing an If-Modified-Since HEAD
request. HTTP/1.1 provides additional mechanisms,
e.g., range requests.) Policies that use pure validation
requests stop renewing a copy once it is invalidated,
even if its renewal credit is positive.
Pure validation renewals generally use less bandwidth than
conditional fetches, since if the object was modied, only the
object header is transmitted. On the other hand, conditional
fetches result in a fresh cached copy even when the object
was modied. Thus, policies that only perform pure validation
renewals target only freshness misses whereas policies
that allow conditional fetches also address some content
misses (cmisses-r). For small-size objects that can t on a
single packet, however, the overhead of pure validations is
similar to that of conditional fetches so conditional fetches
would be more eective. Ultimately, the type of renewal
request can be determined by the policy on a per-request
or per-object basis, according to (previous) content length
and modication patterns. The data analysis in Section 4
shows that only a small fraction (5%-10%) of IMS requests
result in invalidations and content transmission. This suggests
that the additional overhead of performing conditional
fetches over pure validations is typically amortized over 10-
renewals. Therefore, for moderate size objects, the total
bandwidth usage is similar under both choices of renewal
actions. For the sake of simplicity, we evaluated only policies
with pure validation renewals. Since the likelihood of
modication is low, pure validation renewals capture most
trace total req. 200+304 req. fhits fmisses cmisses-d cmisses-r no-cache
UC 7.5M 6.3M 23% 10% 56% 1% 10%
SD 5.6M 4.4M 19% 15% 56% 3% 7%

Figure

2: Classication of the requests in the UC and SD traces.0.10.30.50.70.90 500 1000 1500 2000 2500 3000 3500 4000
fraction
below
x
milliseconds
UC: CDF of request service times
fhits
no-cache
cmisses-r
cmisses-d0.10.30.50.70.90 500 1000 1500 2000 2500 3000 3500 4000
fraction
below
x
milliseconds
SD: CDF of request service times
fhits
no-cache
cmisses-r
cmisses-d

Figure

3: CDF of the service times, broken down by cache action
of the potential of refreshments and provide a good indication
for the full potential. We believe, however, that the
incorporation of conditional fetches in the policies deserves
further study.
Another design issue that may require explaining is that
we chose not to consider predictive policies which renew
or prefetch long-expired objects. Predictive renewals and
document prefetching are typically eective if activity is
traced at a per-user basis, where future requests are predicted
according to current requests made by the same user
to related objects. Our refreshment approach diers from
predictive-renewal in that we consider the aggregate behavior
across users on each object. Our policies use minimal
book-keeping, simple implementation, and do not require
Web server support. Ultimately, it may be eective for refreshment
policies to co-exist with predictive renewals and
content prefetching, but we believe that the basic dierences
between these techniques call for separate initial evaluations.
One last important point that we would like to make explicit
is that our policies were designed (and evaluated) for
caches that forward requests to origin servers. For exam-
ple, top-level caches in a hierarchy and caches that are not
attached to a hierarchy. Directing renewal requests to an
authoritative source assures a maximum freshness time for
the response. Caches that are congured to forward requests
to a parent cache may also benet from deploying a refreshment
policy. The potential gain, however, is limited since
renewals would often obtain aged responses (i.e. objects that
have already been cached for a time period at the higher level
cache). We studied age eects on performance of cascaded
caches in [37, 38].
We proceed by describing the dierent policies. An illustrated
example is provided in Figure 5. In the next section
we evaluate and compare their performance using trace-based
simulations.
Policies
passive: passive validation, objects are validated only
as a result of a freshness miss i.e. when a request arrives
and there is a stale cached copy. This is the way most
caches work today.
opt(i): An approximation to the optimal omniscient
oine policy. 2 This policy assumes knowledge of the
time of the subsequent request for the object and whether
the object copy would still be valid then. If the subsequent
request is such that the current copy remains
valid and it is issued within c  i freshness-lifetime-
durations after the expiration of the current copy, then
the renewal credit is set to c. Otherwise, no renewals
are performed.
recency(k): The renewal credit is reset to k following
any request for the object, including no-cache requests.
recency(k), similarly to the cache replacement policy
lru, exploits the recency property of request se-
quences, which states that future requests are more
likely to be issued to recently-requested objects.
recency  (k): A variant of recency(k) that resets
the renewal credit to be k following any request for
the object, except for no-cache requests.
increment the renewal credit by j for any
request that would have been a freshness miss under
passive. In other words, we add j to the renewal credit
We specify optimal oine algorithm in [26].
fraction
below
x
milliseconds
UC: CDF of request service times
304 fhits
200 fhits
200 fmisses0.10.30.50.70.90 500 1000 1500 2000 2500 3000 3500 4000
fraction
below
x
milliseconds
SD: CDF of request service times
304 fhits
200 fhits
200 fmisses

Figure

4: CDF of the service times for content-hits, broken down by response code to the client
recency(2)
time
request no-cache request refresh miss hit
m2.501.671.80overhead
passive

Figure

5: Behavior of dierent refreshment policies on an example sequence of 9 requests. The time line is
in units of freshness-lifetime durations. All policies incur at least two misses: The rst request is a cold-start
miss and the 8th request, which has a no-cache request header, is always a miss. The gure also summarizes
the number of misses and renewals performed by each policy. passive, for example, incurs 7 misses and
performs no renewals, while th-freq(0:5; incurs only 2 misses and performs 13 renewals. The policy opt(1)
is the most e-cient in the following sense: it performs the least renewals among all policies that incur
at most 4 misses (e.g., recency(1) and freq(1; 0)). This example illustrates how the coverage (fraction of
misses eliminated) of the policies recency(i) and freq(i) increases with i. The overhead (number of \extra"
requests per eliminated miss), however, typically (but not always) increases as well. For example, recency(1)
eliminates 3 misses with respect to passive but performs 8 renewals. Thus, it issues 8+4
(renewals and misses) than passive and has overhead of 5=3  1:67. Similarly, recency(2) eliminates 4 misses
while issuing 3 than passive, and thus, has overhead of
upon any request which is issued more than freshness-
lifetime-duration units of time after a previous request
that caused the passive policy to contact the origin
server. In addition, upon any request (except for no-cache
requests) the renewal credit is set to m if it is less
than m. With policy freq(j; purely exploits
the frequency property that states that objects
that were frequently requested in the past are more
likely to be requested soon. replacement policy
that exploits the frequency property is lfu.) For
the policy freq(j; m) is a hybrid of freq(j;
and recency(m).
th-freq(th; m) keep renewing objects until the ratio
of would-have been passive freshness misses to number
of freshness-lifetime-durations since beginning of
log drops below a threshold. In other words, upon
each request which would have been a freshness miss
for passive we increment the renewal credit such that
we would keep renewing until the ratio drops below
a threshold. In addition, upon any request (except
for no-cache requests) the renewal credit is increased
to m if it was less than m. This policy exploits the
frequency property, and normalizes it by freshness-
lifetime-duration. It also naturally provides a more
continuous range of tradeos, since th is not necessarily
an integer. With the policy is purely
frequency-based whereas higher values of m correspond
to hybrids with recency(m) policy.
6. EXPERIMENTAL EVALUATION
We conducted trace-based simulations in order to evaluate
cache performance under the dierent refreshment policies.
We outline our methodology and then proceed to present
and discuss the simulation results.
6.1 Methodology
The traces included the cache action taken on each request
for the currently-implemented passive refreshment. In order
to simulate other policies, however, we had to obtain
response header values or TTL values for requested objects.
Unfortunately, this data is not available in the recorded
trace. We therefore separately issued GET requests for the
URLs in the trace shortly after downloading it. We processed
the response headers and extracted cache directives
and values of relevant header elds. For cachable objects
(objects without a no-cache directive in the response header),
we applied the Squid object freshness model [11] (HTTP/1.1
compliant) described in Section 3 to calculate TTLs using
the values extracted above. When an explicit freshness-
lifetime duration was not provided by an Expires or max-age
header, we applied Squid's heuristic. We used 10% of
the time dierence between the time specied by the Date
header and the time specied by the Last-Modified header
subject to a maximum value of one day.
We issued more than a single GET for a sample of the objects
and repeated the TTL calculation. We found that cache control
directives and freshness-lifetime values do not change
frequently. This indicated that our estimates re
ected reasonably
well values that would have been obtained from the
origin server at the time requests were logged.
We then ran simulations using the original sequence of requests
and the extracted TTL values. To put all policies on
equal ground and eliminate the eect of boundary conditions
we also simulated passive, so the performance gures provided
later correspond to the simulated passive rather than
the one re
ected by the original labels (given in Section 4).
We rst discarded all requests that were not labeled as
HTTP GET. The simulation was only applied to requests
for URLs on which we obtained a 200 (OK) response on our
separately-issued requests. Note that 302 responses (HTTP
redirect) are not cachable and hence requests of URLs for
which we obtained such a response were discarded. The
simulation then utilized the logged information in the following
way: (i) All logged requests for each considered URL
were used along with the request time to determine the status
of the object in the simulated cache and the resulting
cache actions, (ii) the original cache-action label was used
to identify requests which arrived with a no-cache header
(our simulation accounted for such requests by resetting the
TTL to the freshness-lifetime duration even if a fresh copy
was present in the simulated cache), and (iii) the original
labels were also used in a heuristic that estimated at which
points objects were modied.
The modication heuristic considered various recorded labels
of the requests. Clearly, when a successful request was
classied by the labels in the trace as a cmiss-r (i.e. labeled
TCP REFRESH MISS in the trace, see Section contents
had changed. For requests labeled cmisses-d we did
not have an explicit indication whether content had changed
so we used a heuristic based on the logged size of the response
to the client. In order to simulate performance of
refreshment policies, we also had to estimate at which point
in the interval between requests the modication had actually
occurred (since refreshment policies stop refreshing once
the server invalidates the object). The simulation assumed
that when a modication had occurred between two consecutive
requests (and therefore incur a content miss on the
later it happened at the midpoint of the time interval
between the two requests. If more modications had
happened, it is likely that the rst one occurred earlier in
the interval, and hence our assumption means that more unproductive
renewals occur in the simulation than in reality,
and thus, the simulated policies would exhibit somewhat
worse tradeos. Since the majority of validations return
not-modied, however, this assumption could not have had
a signicant eect on our results.
Since we could not issue GET requests for all the URLs present
in the trace in a reasonable time without adversely aect-
ing our environment, we selected a subset and then scaled
the results up to factor out the sampling. We applied non-uniform
sampling with denser samples from more frequently-
requested URLs. In particular, we included all URLs that
were requested more than 12 times. In total we fetched
about 224K distinct URLs. The reason for non-uniform
sampling is the Zipf-low relation between requests and URLs
where many requests are issued to a small set of popular
URLs. The original logs had about 5 million dierent
URLs, most of them requested only once. Thus, a same-size
sample obtained through uniform sampling over URLs
would have yielded lower-condence estimates than the non-uniform
sample we used. The sampling bias was factored out
by scaling each frequency group individually.
The simulations assumed innite cache storage capacity. This
is consistent both with current industry trends and with the
actual traces we used, since objects requested twice or more
in the 6 day period were not likely to be discarded by the
replacement policy used in Squid.
In the performance metric used in the simulations we counted
all requests that constituted content hits. Content hits that
occurred more than a freshness-lifetime duration past the
previous (simulated) server contact were counted as freshness
misses and requests occurring within the duration were
counted as freshness hits. Content hits exclude requests to
explicit noncachable objects, requests with no-cache request
headers, and requests when the content had changed. Since
we had no information on such requests, we did not classify
the rst request of each object. Appropriate requests for objects
with freshness-lifetime-duration of 0 were counted as
content hits, but were all considered freshness misses. Note
that renewals are not performed on such objects and hence,
the number of freshness misses incurred on these objects is
not reduced by refreshment policies.
6.2 Simulation results
Under the simulated baseline policy passive (where objects
are refreshed only as a result of client requests), 48% of
content hits constituted freshness misses on the UC trace,
and 53% were freshness misses on the SD trace. We recall
that the respective numbers according to labels on the
recorded trace provided in Section 4 are 31% and 43%. The
gap is mainly due to simulating a shorter trace, dierent
boundary conditions, and the conservative heuristic used to
identify content hits. These factors should aect all policies
in a similar manner. So in order to put passive on equal
grounds with all other policies we chose to simulate it rather
than using the labels of the trace.
We evaluated the performance of the dierent refreshment
policies by the tradeo of overhead vs. coverage. The coverage
(reduction in freshness-misses) is calculated as the fraction
of the number of freshness misses according to passive
that are eliminated by the respective policy. More precisely,
if x denotes the number of freshness misses of passive, and
y the number of freshness misses of a policy P then the
coverage of P is the fraction (x y)=x.
We calculated the overhead of policy P as the dierence
between the number of validation requests issued by P and
the number of validation requests issued by passive. Recall
that the cache issues a validation request for each freshness
miss. Hence, the request overhead is the total number of
renewals performed minus the number of freshness misses
eliminated (converted to freshness hits). We normalize the
overhead by dividing it with the total number of freshness
misses that were converted to freshness hits.
To obtain the coverage/overhead tradeo for each type of
policy, we swept the value of its respective parameter. For
example, the points on the curve of recency correspond
to runs with recency(1); recency(2);
the points for freq were obtained on runs with freq(1;
. Note that opt(0), recency(0), recency  (0),
are in fact passive. 3 These
tradeos are shown in Figure 6.
The performance of recency and recency  policies was almost
identical, hence we omitted the recency  curve. This
similarity shows that requests without a no-cache header are
about as likely to follow a request with a no-cache header
as one without a no-cache header.
Under all types of policies, the coverage peaks at about 63%-
67%. The remaining 33%-37% of freshness misses mostly
occur on objects with freshness-lifetime-duration of 0, on
which refreshment is not eective. The opt policies eliminates
all \addressable" freshness misses with overhead of
about 1.3 requests per miss, and eliminates the bulk of these
misses with an overhead of 0.5. These numbers bound the
potential of refreshment policies. They also indicate on the
performance loss by the restriction to the refreshment frame-
work. 4
The simulation results for opt and recency show the locality
eect, where most freshness misses that can be eliminated
occur within a small number of freshness-lifetime-
durations after a previous request. The left-most point on
the curves of recency and opt, which correspond to recency(1)
and opt(1), show that about 30% of freshness misses occur
within one freshness-lifetime-duration after the expiration of
the cached copy. The second points on the left correspond
to recency(2) and opt(2) and indicate that about additional
15% of freshness misses occur between one and two
freshness-lifetime durations passed the expiration. We note
that the observed fact that a very small number of freshness
occur more than 10 freshness-lifetime-durations
passed the expiration is not only due to locality but also
re
ects the interaction of the log duration of 6 days and the
most common freshness-lifetime-duration of 24 hours [33].
The fact that coverage of recency and the frequency-based
policies peaks at about the same place indicates that a very
small fraction of freshness misses are incurred on very infrequently
requested objects (since the frequency-based policies
do not perform any renewals on the rst request and
thus can not eliminate misses incurred on the second re-
quest. The correspondence in peak coverage of opt and
other policy-types is due to a \threshold phenomenon" where
most freshness misses occur on objects with a freshness-
lifetime-duration of 0 or occur within a small number of
freshness-lifetime-durations following a previous request.
The frequency-based policies freq(j; 0) and th-freq(th;
signicantly outperformed recency(k). This re
ects the
fact that the vast majority of freshness misses which can
be eliminated occur on the more popular URLs. The gap is
caused by the very large number of cachable URLs that were
3 We remark that these policies are able to achieve \contin-
uous" tradeos by mixing two consecutive integral values of
the respective parameter, for example, applying recency(1)
on some URLs and recency(2) on others.
4 Recall that under the refreshment framework, objects must
be kept fresh continuously till the following \hit." The optimal
unrestricted policy, which validates objects just before
they are requested, incurs no overhead.
request-overhead
per
eliminated
fmiss
fraction of fmisses eliminated
UC trace: performance of refreshment policies
OPT
RECENCY
request-overhead
per
eliminated
fmiss
fraction of fmisses eliminated
SD trace: performance of refreshment policies
OPT
RECENCY

Figure

Performance of the dierent refreshment policies when simulated on the UC and SD traces
requested only once. The recency(k) policy performed up
to k unproductive renewals 5 on each such request. The hybrid
policies freq and th-freq with m > 0 performed considerably
worse than the pure frequency-based policies (that
correspond to hence only results for are
shown. This behavior is not surprising given that recency
yielded much worse tradeos. Overall, the results indicate
that frequency-based object prioritization is more eective
than recency-based prioritization.
The domination of frequency-based policies is also consistent
with studies of cache replacement policies for Web contents
[8, 7], since dierent URLs tend to have a wide range of
characteristic popularities, a property that is captured better
by frequency-based policies. It is interesting to contrast
these results with a related study of refreshment policies that
we performed for DNS records. In contrast with our nd-
ings here, for DNS caches the recency and frequency-based
policies exhibited similar performance [26]. Our explanation
is that at the hostname level, there is signicantly smaller
fraction of \objects" that are resolved only once.
The performance of freq and th-freq is similar, although
th-freq, which normalizes the frequency by freshness-lifetime-
duration, performed somewhat better. The similarity is
mostly explained by the fact that the large majority of freshness-
lifetime-durations are of the same length (one day) and also
because for shorter durations, frequency of requests is correlated
with the duration. The policy th-freq provides a
spectrum of tradeos and better performance, particularly
in the low-overhead range. th-freq, however, may require
more book-keeping than freq. The particular tradeos obtained
by the frequency-based policies shows that signi-
cant improvements can be obtained with fairly low overhead.
About 10% of freshness misses can be eliminated with the
overhead of half of a validation request per eliminated freshness
miss; 25% of freshness misses can be eliminated with
overhead of a single request per eliminated miss; 50% can
be eliminated with overhead of two; and 65% of freshness
misses can be eliminated with overhead of three.
5 It could be less than k since we did not perform renewals
passed the termination time of the log.
7. CONCLUSION
A large fraction (30%-50%) of cache hits constitute freshness
misses, that is, the cached copy was not fresh, but
turned out to be valid after communication with the origin
server. Validations are performed prior to sending responses
to users, and signicantly extend cache service time. There-
fore, freshness misses impede the cache ability to speed-up
Web access.
An emerging challenge for Web content caches is to reduce
the number of freshness misses by proactively maintaining
fresher content. It seems that some cache vendors had already
implemented ad-hoc refreshment mechanisms. Our
proposed refreshment policies are a relatively low-overhead
systematic solution. Refreshment policies extend freshness
lifetime by selectively validating cached objects upon their
expiration. Since cache freshness is increased, requested objects
are more likely to be fresh and thereby are serviced
faster. We demonstrated that a good refreshment policy can
eliminate about 25% of freshness misses with an overhead of
a single validation requests per eliminated miss, that is, two
\oine" validation requests replace one \online" request.
For future work, we propose ways to further reduce renewal
overhead. We rst propose that renewals of objects located
at the same host are batched together, and thus, decrease
overhead by sharing the same persistent connection. Batching
can be natural as co-located objects often share the same
cache-control mechanism and subsets of such objects (that
are embedded on the same page or related pages) are often
requested together. A second proposal is to perform
renewals at o-peak hours. The most common freshness-
lifetime duration of 24 hours provides su-cient scheduling
exibility to do so (e.g., performing renewals due at 10am
EST at the signicantly less-busy time of 7am EST).
As a next step in the evaluation of the eectiveness of a
refreshment policy we hope to incorporate one such policy
in a popular caching server software such as Squid. Our
results indicate that the integration of refreshment would
not impose a signicant computational overhead, and would
boost performance in terms of user-perceived latency.

Acknowledgment

Our experiments would not have been possible without the
collection and timely availability of the NLANR cache traces.
We thank Duane Wessels for answering questions with regard
to a Squid logging bug.
8.



--R







































--TR
Scale and performance in a distributed file system
Leases: an efficient fault-tolerant mechanism for distributed file cache consistency
Web cache coherence
Removal policies in network caches for World-Wide Web documents
Improving end-to-end performance of the Web using server volumes and proxy filters
Exploiting regularities in Web traffic patterns for cache replacement
On-line file caching
Aging through cascaded caches
Volume Leases for Consistency in Large-Scale Systems
Image-based Rendering with Controllable Illumination
Evaluating Server-Assisted Cache Replacement in the Web
Proactive Caching of DNS Records
Application-level document caching in the Internet
Maintaining Strong Cache Consistency in the World-Wide Web

--CTR
Edith Cohen , Haim Kaplan, Proactive caching of DNS records: addressing a performance bottleneck, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.6, p.707-726, 22 April
Timo Koskela , Jukka Heikkonen , Kimmo Kaski, Web cache optimization with nonlinear model using object features, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.6, p.805-817, 20 December
validation requests;HTTP;web caching;user-perceived latency;refreshment policies