Giovanni Neglia
email: giovanni.neglia@inria.fr

Damiano Carra
email: damiano.carra@univr.it

Pietro Michiardi
email: pietro.michiardi@eurecom.fr

Cache Policies for Linear Utility Maximization

Keywords: Cache, Cache replacement policy, Content Delivery Network (CDN), Knapsack problem Cache, Politique de remplacement de cache, Réseau de diffusion de contenu, Problème du sac à dos, Recuit simulé

Cache policies to minimize the content retrieval cost have been studied through competitive analysis when the miss costs are additive and the sequence of content requests is arbitrary. More recently, a cache utility maximization problem has been introduced, where contents have stationary popularities and utilities are strictly concave in the hit rates. This paper bridges the two formulations, considering linear costs and content popularities. We show that minimizing the retrieval cost corresponds to solving an online knapsack problem, and we propose new dynamic policies inspired by simulated annealing, including DynqLRU, a variant of qLRU. For such policies we prove asymptotic convergence to the optimum under the characteristic time approximation. In a real scenario, popularities vary over time and their estimation is very difficult. DynqLRU does not require popularity estimation, and our realistic, trace-driven evaluation shows that it significantly outperforms state-of-the-art policies, with up to 45% cost reduction.

Introduction

Cache policies have often been designed with the purpose to maximize the hit rate, but different metrics can be meaningful in different contexts: data rate to be served from the upstream caches/servers, users' delivery time, ISP/AS operational costs [START_REF] Araldo | Cost-aware caching: Caching more (costly items) for less (ISPs operational expenditures)[END_REF][START_REF] Pacifici | Coordinated selfish distributed caching for peering content-centric networks[END_REF], damage to flash memories in hierarchical caches [START_REF] Shukla | On designing optimal memory damage aware caching policies for content-centric networks[END_REF], service time from the HDD [START_REF] Neglia | Access-time aware cache algorithms[END_REF], etc. Performance optimization in all these cases can be abstracted to the same problem: given some cost c i that is paid upon a miss to retrieve content i, minimize the sum of the retrieval costs. We provide a few examples below • c i = 1: minimize the cache miss rate,

• c i = s i , the size of content: minimize the traffic from upstream servers/caches, • c i = τ i , the retrieval time from the server where content i is stored: minimize user's retrieval time.

Our target is to design cache policies that minimize the time-average retrieval cost when content requests exhibit some statistical regularity. When the request process is unpredictable, this problem has been studied under the name of File Caching (FC) problem [START_REF] Young | Encyclopedia of Algorithms[END_REF]. In this case no algorithm can provide absolute worst-case guarantees. Instead there exist algorithms, like GreedyDual-Size (GDS), with a known (and optimal) competitive ratio, i.e. they achieve a cost at most a given factor larger than the cost of the optimal offline algorithm that can view the sequence of requests in advance. We want to go beyond FC, because in many practical cases, some contents can be requested more often than others during relatively long periods of time, so that a caching algorithm can exploit such regularity and perform much better. The Independent Reference Model (IRM) corresponds to the extreme case where content popularities are constant over time and contents requests are drawn independently according to a given probability distribution.

A related problem has been formulated in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF], considering the advantages from hits rather than the disadvantages from misses. In particular the authors have defined the following Cache Utility Maximization (CUM) problem under the IRM and constant content size:

maximize h1,...h N ∈[0,1] N i=1 U i (h i ), subject to N i=1 h i = B, (1)
where B is the cache's size, h i is the stationary hit probability of content i and U i (h i ) is the utility associated to the hit probability. The paper shows how to derive optimal TTL-cache policies [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF] when the functions U i are increasing and strictly concave. The constraint in (1) can be interpreted as an average buffer occupancy constraint.

Our first contribution is to bridge the FC and CUM formulations, by showing that the FC problem under the IRM (our focus) corresponds to a CUM problem where the utility functions U i are linear and the constraint takes into account content sizes. This linear case is then particularly important to study, because most of the usual cache performance metrics are additive over different misses (as shown above). Strictly concavity functions are instead of interest if fairness across contents is an issue, because the optimization of linear utilities can lead to performance dishomogeneity.

The second contribution is the proposal of new dynamic policies to solve the linear utility maximization problem. We leverage the fact that a CUM problem with linear utilities corresponds to a Knapsack Problem (KP). Recognizing this parallelism does not lead to a trivial solution, because the optimal cache policy needs then to solve an online KP under partial information (e.g. the catalogue is not known). We design then two new dynamic algorithms, OSA and DynqLRU, based on simulated annealing ideas, and we prove that they asymptotically store the optimal set of contents under Che's approximation [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF]. As an example of the difficulties indicated above, convergence to the optimum does not follow immediately from known results for simulated annealing. Indeed simulated annealing methods work offline and can freely explore the solution space, while in our online setting the possibility to change the current tentative solution is limited by the request process. Our analysis also leads to a characterization of the convergence sets of simulated annealing methods in terms of a specific potential function, that was not observed before.

As a third contribution, we consider a realistic setting, where popularities keep varying over time. Their estimation is a very difficult task. In particular, we show through some numerical examples that estimation may require a significant amount of memory and estimation errors can jeopardize performance. For these reasons, policies that do not require to estimate popularities, like our DynqLRU, can be more of practical interest. In order to use DynqLRU also in this realistic non-IRM setting, we propose a change detector that resets DynqLRU and restarts its exploration phase when the request process appears to have significantly changed. A simple formula allows us to configure the change detector.

We use request traces from Akamai content delivery network to tune IRM parameters and validate our theoretical results. Moreover, we test the performance of DynqLRU coupled with the change detector under the actual traces and four different realistic retrieval costs: miss ratio, upstream traffic, retrieval time and HDD load. DynqLRU outperforms other policies like LRU or GDS always but in the case of the upstream traffic when LRU performs equally good. Cost reduction can be as high as 45%.

The paper is organized as follows. In Sec. 2 we introduce the FC and CUM problems and other related works. We then formalize the retrieval minimization problem in Sec. 3 and prove that optimal static policies exist and they solve some specific KPs. We discuss how some heuristics for KP lead naturally to cache policies. Then, in Sec. 4 we introduce the policy OSA. After having shown the difficulties to estimate popularities in Sec. 5, we illustrate the policy DynqLRU in Sec. 6 and the change detector in Sec. 7. Simulation results both under IRM and real content request traces are in Sec. 8.

Background and related works

Let N denote the (potentially infinite) catalogue of contents and r L ∈ N L a sequence of L requests for the contents. The File Caching (FC) problem [START_REF] Young | Encyclopedia of Algorithms[END_REF] is formulated as follows: given a cache with integer size B, and files with positive integer sizes and non-negative retrieval costs, maintain in the cache files to minimize the total retrieval cost. We denote by s i and c i respectively the size and the cost of content i ∈ N . The variant with uniform file sizes and uniform costs is called the paging problem and the variant with uniform sizes and heterogeneous costs the weighted paging problem.

Let X(n) ⊆ N denote the state of the cache at time n, i.e. the set of the contents stored in the cache when the n-th request arrives. A possible state x needs to satisfy an instantaneous buffer occupancy constraint, i.e. i∈x s i ≤ B. Then, replacement-policies are required to decide which contents should be evicted to make space for a new content. The retrieval cost experienced by a cache policy π under an arrival sequence r L when the cache has size B is

C(π, B, r L ) = L n=1 c r L (n) 1(r L (n) / ∈ X(n)) . (2)
It is always possible to find a specific sequence of content requests such that any cache policy Inria performs arbitrarily bad. It is then standard to perform a competitive analysis [START_REF] Fiat | Competitive paging algorithms[END_REF][START_REF] Buchbinder | Online primal-dual algorithms for covering and packing problems[END_REF][START_REF] Albers | Competitive online algorithms[END_REF][START_REF] Naor | Primal-dual algorithms for online optimization: Lecture 3[END_REF]. Let π id denote the ideal optimal policy that knows in advance the sequence of requests. A policy π is said to be f (B , B)-competitive if on any sequence the total retrieval cost incurred by π with a cache of size B is at most f (B , B) times the cost obtained by π id with a cache of size B ≤ B, i.e.

max r L C(π, B, r L ) C(π id , B , r L ) ≤ f (B , B), ∀L.
It is possible to prove that the best possible competitive ratio for any deterministic online algorithm (i.e. an algorithm that does not know the future requests) is B/(B-B +1) [START_REF] Young | On-line file caching[END_REF]. In [START_REF] Cao | Cost-aware www proxy caching algorithms[END_REF] the algorithm GDS was proven to be B-competitive1 and then optimal. This algorithm will be used later for comparison and is shown in Alg. 1. The result was generalized in [START_REF] Young | On-line file caching[END_REF]: the optimal B/(B -B + 1) competitive ratio was proven for the class of algorithms called Landlord, that includes GDS. It should be observed that in many applications the cache size B may be huge, and then this approximation factor is of limited interest. Nevertheless, the performance of these algorithms degrades in practice much slower than linearly with the cache size B.

Algorithm 1 GDS algorithm

Input: Sequence content requests r W ← 0 while n ≤ |r| do i ← r(n) if i ∈ X(n) then H(i) ← W + c i /s i else while s i + j∈X(n) s j > B do not enough space for content i W ← min l∈X(n) H(l) arbitrarily select j|H(j) = W X(n) ← X(n) -{j} end while X(n) ← X(n) ∪ {i} H(i) ← W + c i /s i end if n ← n+1 end while
Differently from replacement-policies, TTL-policies associate a timer to each content and the content is evicted only when the timer expires. As a consequence, TTL-caches ideally operate with an infinite cache size and impose only an average constraint on the buffer occupancy, that should be equal to a given value. We denote also this value as B. 2 The timer of a given content may or may not be renewed upon a hit. TTL-policies were first proposed as a modeling tool to study existing replacement-policies starting from the seminal work on LRU from Che et al. [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF]. In this paper we use the expression Che's approximation to denote the possibility to approximate a replacement policy with an opportunely tuned TTL-policy. This approach has been shown to be very accurate [START_REF] Fricker | A versatile and accurate approximation for LRU cache performance[END_REF][START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF]. More recently, the practical use of TTL-policies has been advocated because of their flexibility [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF][START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF]. In particular, as we mentioned in the introduction, [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF] derives TTL-policies that can solve the CUM problem (1) when the utility functions U i are strictly concave. The framework considers a finite catalogue N and requests arriving according to the (continuous-time) IRM: the request process is a Poisson process and a request is for content i with probability p i (called the content popularity) independently from previous requests.

Many papers consider cache policies minimizing specific retrieval costs (e.g. [START_REF] Araldo | Cost-aware caching: Caching more (costly items) for less (ISPs operational expenditures)[END_REF][START_REF] Pacifici | Coordinated selfish distributed caching for peering content-centric networks[END_REF][START_REF] Shukla | On designing optimal memory damage aware caching policies for content-centric networks[END_REF][START_REF] Neglia | Access-time aware cache algorithms[END_REF] mentioned in the introduction). None of them tries to address the general problem we target in this paper, but we rely on two results from [START_REF] Neglia | Access-time aware cache algorithms[END_REF] that do not actually depend on the specific cost considered there. The authors study which set of contents M * should be duplicated in the RAM in order to reduce the (one-step lookahead) expected HDD workload and they prove that M * is the solution of the following problem: maximize

M⊆N i∈M p i c i , subject to i∈M s i ≤ B, (3)
i.e. minimizing the expected retrieval cost is equivalent to maximizing the objective function in (3), i.e. the utility from storing the contents M in the cache. We formally define the utility U of a set of contents M as U(M)

i∈M p i c i . (4)
Problem (3), as already observed in [START_REF] Neglia | Access-time aware cache algorithms[END_REF], is a KP where the knapsack has capacity B and objects have value p i c i and weight s i . We extend their result by showing that minimizing the one-step lookahead expected retrieval cost (and then problem (3)) is actually equivalent to minimizing the time-average retrieval cost. We show a similar result when TTL-policies with average occupancy constraints are considered as in the original CUM problem. Our DynqLRU, to be described in Sec. 6, can be considered a dynamic version of the policy q i -LRU, proposed in [START_REF] Neglia | Access-time aware cache algorithms[END_REF], according to which a new content i is introduced in the cache upon a miss with a probability that depends on the ratio c i /s i . The idea to probabilistically differentiate content management according to the ratio c i /s i had already been considered in [START_REF] Jelenkovic | Optimizing LRU Caching for Variable Document Sizes[END_REF], where, upon a hit, content i is moved to the front of the queue with some probability qi . Under Zipf's law for popularities, the authors prove that the asymptotic hit ratio is optimized when the probabilities qi are chosen to be inversely proportional to document sizes. The interactions of caches at different ASs has been investigated through game theory in [START_REF] Pacifici | Coordinated selfish distributed caching for peering content-centric networks[END_REF], where a stochastic potential "à la Young" [START_REF] Young | The Evolution of Conventions[END_REF] (as we do in Sec. 4) is introduced to study Nash equilibria stability. While our caching algorithms are randomized by choice (to explore the solution space), in [START_REF] Pacifici | Coordinated selfish distributed caching for peering content-centric networks[END_REF] randomization is rather a collateral effect of noisy popularity estimates. Moreover, [START_REF] Pacifici | Coordinated selfish distributed caching for peering content-centric networks[END_REF] does not consider the non-homogeneous dynamics rising when the noise "converges" to zero as time goes on, whereas we do.

Finally, we observe that, once the analogy between KP and caching is clearly identified, it may appear natural to explore approaches like simulated annealing to design caching policies, but, to the best of our knowledge, this was never done before. The annealed Gibbs sampler was instead used in [START_REF] Kauffmann | Measurement-based self organization of interfering 802.11 wireless access networks[END_REF] to jointly solve the AP channel selection problem and the users association problem. Moreover, we are aware that there exists a rich literature on online KP where a sequence of objects arrive over time (see e.g. [START_REF] Böckenhauer | The online knapsack problem: Advice and randomization[END_REF] and references therein), but i) it relies on some assumptions that do not suit a caching application (e.g. contents cannot be removed from the knapsack once stored), and ii) the focus is on a competitive analysis as for the FC problem.

Retrieval cost minimization under IRM

We want to minimize the retrieval cost under the assumptions that i) the total cost is the sum of the retrieval costs due to each miss (as in FC) and ii) contents have different popularities Inria and in particular requests follow the IRM (as in CUM). The catalogue N is then finite with size N = |N |. We are interested in replacement-policies and TTL-policies that are optimal for long content request sequences. Given an infinite request sequence r = (r(1), r(2), . . . ), we denote by r n its subsequence containing the first n elements. It seems natural to define the cost of a policy π to be the time-average retrieval cost

lim n→∞ C(π, B, r n ) n = lim n→∞ 1 n n k=1 c r(k) 1(r(k) / ∈ X(k)) , (5)
but one may (rightly) wonder if the cost in (5) is well defined, i.e. if this limit always exists. It is indeed possible to build policies for which the average would keep oscillating. 3 The main result of this section is that TTL or replacement policies minimizing the one-step lookahead expected cost also minimize the time average cost defined above and that they implicitly solve two related Knapsack Problems (KPs).

We first consider classic replacement-policies that satisfy the instantaneous occupancy constraint. We say that a replacement-policy π * rep is expected-cost optimal, if it guarantees that after a finite number of requests a set of contents M * , solution of problem (3), is stored in the cache almost surely (a.s.). For example, a policy that "waits" for the contents in a given M * to be requested, and then stores them forever is expected-cost optimal, because any content is asked by a finite time a.s. and the set M * is finite. We prove now that any of such policies π * is optimal in the average-cost sense. 4Proposition 3.1. For any replacement-policy π rep , any expected-cost optimal policy π * rep , and an IRM sequence of content requests R it holds

lim inf n→∞ C(π rep , B, R n ) n ≥ lim n→∞ C(π * rep , B, R n ) n a.s. ( 6
)
The proof is in Appendix A.

We consider now TTL-policies with an infinite buffer size and a constraint on the average buffer occupancy, i.e., i∈N h i s i = B. A TTL-policy (π T T L ) is identified by the timers it associates to each content. The following results are valid both if timers are renewed or not upon a hit. We want to find the hit probabilities h * i that maximize the one-step lookahead expected retrieval cost for a given request. They are the solution of the following problem:

maximize h1,...h N ∈[0,1] i∈N p i h i c i , subject to i∈N h i s i = B. (7)
We denote by π * T T L a TTL-policy whose timers have been selected so that the corresponding hit probability for any content i is h * i and we call it an expected-cost optimal policy. The following proposition is the analogue of Prop. 3.1 for the case of TTL policies. Proposition 3.2. For any TTL-policy π T T L , any expected-cost optimal policy π * T T L , and an IRM sequence of content requests R it holds

lim n→∞ C(π T T L , B, R n ) n ≥ lim n→∞ C(π * T T L , B, R n ) n a.s. ( 8
)
The proof is in Appendix B.

We have then shown that, both under instantaneous and average buffer occupancy constraints, the policy that minimizes the corresponding one-step lookahead expected retrieval cost also minimizes the time-average retrieval cost. An optimal replacement-policy stores, after some finite time, the set of contents that solves the knapsack problem ( 3). An optimal TTL-policy stores each content i in the cache a fraction h * i of time, where h * i are solutions of problem [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF]. Problem ( 7) is an instance of the CUM problem [START_REF] Araldo | Cost-aware caching: Caching more (costly items) for less (ISPs operational expenditures)[END_REF], where utilities are proportional to the hit probabilities U i = p i c i h i . 5 The two problems are strongly related because [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF] is the fractional knapsack problem corresponding to a relaxation of (3). This was already observed in [START_REF] Neglia | Access-time aware cache algorithms[END_REF], where [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF] was introduced as a way to find an approximate solution for (3).

In the rest of this paper, we focus on replacement-cache policies. Nevertheless, Che's approximation and the fractional KP [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF] will still make their appearance as approximate solutions. Our purpose is to design expected-cost optimal policies or good heuristics. We already mentioned a possible implementation if an optimal solution M * of problem ( 3) is known: store forever the contents in M * as soon as they are retrieved. This policy is not practical because it would require to solve the NP-hard problem (3). An additional difficulty is that in general the set of contents and their popularities p i are not known, but we assume for the moment that this is the case and we postpone this issue until Sec. 5.

Possible inspiration for policies can originate from usual heuristics to solve a KP. For example we call VGreedy a policy that keeps contents ordered according to their expected value p i c i and removes the contents with smallest values when space is needed. Instead, the policy DGreedy is a policy that keeps contents ordered according to their density p i c i /s i , i.e. the expected value per byte occupied in the cache. None of these policies is guaranteed to converge to a global optimum as we show in the following example.

Example 1 (DGreedy and VGreedy may not converge to the optimum). Let s 1 = 51, s 2 = 100, s 3 = s 4 = 50, p 1 = 0.26, p 2 = 0.27, p 3 = p 4 = 0.235 and unitary costs c i = 1 for i = 1, 2, 3, 4 and B = 100. As soon as content 1 with value 0.26 is required, DGreedy would store it and would never evict it. Similarly, VGreedy would get stuck with content 2 with value 0.27. The optimal policy should instead store contents 3 and 4 with a utility U({3, 4}) = 0.47.

In the next section, we investigate if approaches based on simulated annealing can converge to the optimal solution.

A simulated annealing approach

In this section we show a new approach based on simulated annealing to design an optimal cache policy. Simulated annealing [START_REF] Laarhoven | Simulated Annealing: Theory and Applications[END_REF] is based on the idea of exploring in a random way the neighbourhood of a potential solution accepting occasional changes that may worsen the solution with a probability that decreases over time. The application of simulated annealing to caching is, to the best of our knowledge, new. As it will be evident from the discussion below, convergence to the optimal solution does not follow directly from standard results for simulated annealing because in this online setting we do not have the possibility to design the neighbourhood structure. The analysis is then more involved.

The algorithm

We start describing our policy that we call Online Simulated Annealing (OSA). Upon a miss for content i at time n, we select a set v of contents potentially to be evicted to free space for content i as follows. The set v is initially empty. We draw at random a content j among those stored in the cache and we put it in v. If removing the contents in v frees enough space to store content i, we are done, otherwise we keep selecting at random other contents from the cache (without resampling) until this condition is not satisfied. 6 Now, we actually evict the contents in v to store i with probability p(i, v)

p(i, v) = 1 if U({i}) ≥ U(v) e U ({i})-U (v) T (n) otherwise, (9)
where T (n) > 0 is a parameter decreasing to 0 over time and U() is defined in Eq. ( 4). Let X be the set of all the possible sets of contents that can be stored at the cache, i.e. if x ∈ X , then i∈x s i ≤ B. If the state of the cache at time n is x (X(n) = x) and the object required is i (r(n) = i), it is possible that the state stays unchanged for example if the content i was already in the cache, or that it changes to some other state z = y ∪ {i} where x = y ∪ v , and v and then y are determined by the eviction algorithm described above. We define the neighbourhood of state x as all the possible states that are reachable from x as a consequence of the following request and we denote it by I(x). It is evident that the policy OSA implicitly defines a non-homogeneous Markov Chain (MC) over the set X , whose probability transition matrices we denote by {P (n)} n∈N . When we talk about the MC P (n) we refer instead to the homogeneous MC that at any step use the transition probability matrix P (n). As in simulated annealing, a matrix element P x,z (n) can be expressed as product of a time-invariant probability Q x,z to select z as potential successor of the current state x, and a time-variant probability t x,z (n) to accept a given transition. In particular, Q x,z can be calculated from p i and the probability that the specific set v is selected to make space for object i. Once z is selected, the transition is accepted according to Eq. ( 9), that leads to the following expression for t x,z (n)

t x,z = 1 if U(z) ≥ U(x) e U (z)-U (x) T (n) otherwise.
The new state is always accepted if U({i}) ≥ U(v), and then if U(z) = U(y) + U({i}) ≥ U(y) + U(v) = U(x), i.e. if the utility of the state z is higher than the utility of the current state x. If this is not the case, the cache can still move to the new state with a probability exponentially decreasing in the utility loss (0

> U({i}) -U(v) = U(z) -U(x)).
Because the parameter T (n) is decreasing over time, the algorithm will explore more the solution space at the beginning and will become more and more "greedy" as time goes on. The MC is then characterized by a nonhomogeneous probability transition matrix P (n) with elements

P x,z (n) = Q x,z t x,z (n).
We have put our algorithm in the framework of simulated annealing. The acceptance probability t x,z has the same expression. While the neighbour selection probability Q x,z can be arbitrarily chosen in the offline simulated annealing, here we cannot completely control it, because it depends on the request sequence. We will come back later to the consequences of such difference.

Convergence

As we discussed in Sec. 3, we look for policies that asymptotically store a set of contents M * that is solution of problem [START_REF] Shukla | On designing optimal memory damage aware caching policies for content-centric networks[END_REF]. Note that the objective function of problem (3) is U(M) (by definition ( 4)), hence we would like OSA to asymptotically store a set of contents that is a global maximizer of U(). The average utility (or the average retrieval cost) achieved by OSA does not change if the cache state keeps changing over time, but only a vanishing fraction of time is spent in states that are not global optimizers of U(). These observations motivate us to study which states have an asymptotical non-zero probability to be visited by the MC {P (n)} n∈N . We call such states stochastically stable.

The following theorem 4.1 provides a sufficient condition for the existence of a stationary distribution for the non-homogeneous MC {P (n)} n∈N , and then shows that stochastically stable sets are well defined. Moreover, the theorem relates the stationary distribution of this nonhomogeneous MC to the stationary distributions of the sequence of homogeneous MCs each with (constant) probability matrix P (n). Observe that for a given n, the matrix P (n) identifies a homogeneous finite state MC, that is irreducible and aperiodic. Indeed, given two states x and y, y is reachable from x in at most |y| transitions corresponding to a sequence of requests for each of the contents in |y|. The chain is aperiodic because self-transitions are possible. It follows that there exists a stationary probability µ(n).

Let P (n, k) denote the product P (n)P (n + 1) . . . P (n + k), ∆U max the maximum absolute difference of utilities between two neighbouring states and b the maximum number of contents that may be stored in the cache (b depends on B and the content sizes). Proposition 4.1. If T (n) = ∆U max b/ log(n), the non-homogeneous Markov Chain with transitions matrices {P (n)} n∈N is strongly ergodic, i.e. it exists a probability vector µ such that lim k→∞ P x,y (n, k) = µ y for all x, y ∈ X . Moreover, µ is the limit of the stationary distributions µ(n) of the Markov Chains P (n), i.e. lim n→∞ µ(n) = µ.

The stochastically stable sets are the states y for which µ y > 0. The proof is in Appendix C and it follows from standard results for simulated annealing (see e.g. [START_REF] Anily | Simulated Annealing method with general acceptance probabilities[END_REF]).

The next step in the analysis of simulated annealing algorithms is to prove that all the stochastically stable states are global maximizers of the optimization problem considered, and then only the states with maximum utility have a positive probability to be selected by the algorithm asymptotically. This result is usually achieved by a proper design of the neighbour selection probabilities. If such probabilities guarantee that each homogeneous MC P (n) is reversible, then the stationary probability µ(n) can be easily calculated. A usual expression for the stationary probability is the following:

µ x (n) = e -U (x) T (n) y∈X e -U (x) T (n)
, for which it is immediate to verify that lim n→∞ µ x (n) = 0 if x is not a global maximizer.

In our online algorithm, we do not have the full control of the matrices Q(n). In particular, the neighbourhood set is not symmetric, i.e. z ∈ I(x) does not imply x ∈ I(z). For example, if introducing object i requires to evict two objects from the cache, then it will not be possible to go back from z to x with a single transition. As a consequence the MC cannot be made reversible.

A few convergence results are known for simulated annealing in the non-reversible case. In [START_REF] Hajek | Cooling schedules for optimal annealing[END_REF] convergence to the optimum is proven under a weak reversibility condition. Weak reversibility requires that for any pair of states x and y, if there is a path from x to y (i.e. a sequence of states x = x 1 , x 2 , . . . x p = y such that for each n = 1, . . . p -1, x n+1 ∈ I(x n )) along which the Inria utility does not go below a level L, then there is a path from y to x for which this is also true. Unfortunately this is not the case in our problem, as the following example shows.

Example 2 (Weak reversibility does not hold). Let s 1 = s 2 = 1 and s 3 = 2, p 1 c 1 = p 2 c 2 = 4, p 3 c 3 = 7, B = 2. Consider the two states x = {1, 2} and y = {3}. The only way to move from x to y is directly (y ∈ I(x)), once a request for 3 occurs. Along this path the utility decreases from U(x) = 8 to U(y) = 7. There are two possible ways to move from y to x, corresponding to two requests for contents 1 and 2. In both cases, the system passes through an intermediate state z with utility U(z) = 4 < 7.

A generalization of the weak reversibility condition is in [START_REF] Tsitsiklis | Markov chains with rare transitions and simulated annealing[END_REF], but the condition for convergence to the global maximum is implicit, because it requires to run an algorithm on the matrix embedding all the possible transitions, produce a specific set of states and check that this is a subset of the set of optimal solutions. The approach is computationally unfeasible in our problem. Moreover, the same author doubts that the condition he found can be satisfied "without some form of reversibility."

In what follows we provide an alternative characterization of the states to which our algorithm converges. To the best of our knowledge, this result was never observed in the simulated annealing community. We prove that the stochastically stable sets are the global minimizers of a potential function V (x), that is defined below. Our analysis follows the regular perturbation approach made popular by Young to study the stochastically stable equilibria in games with trembling hands [START_REF] Young | The Evolution of Conventions[END_REF].

Let denote e -1/T and P ( ) be the extension of P (n) obtained by replacing e -1/T (n) by . Observe that P ( ) is continuous in 0, i.e.. lim →0 P ( ) = lim n→∞ P (n) = P (0). Moreover, for each pair x, y, such that P x,y ( ) > 0, there exists a non negative real number w x,y such that 0 < lim →0 P x,y ( )/ wx,y < ∞. Under these properties P ( ) is called a regular perturbation of P (0) [START_REF] Young | Individual Strategy and Social Structure: An Evolutionary Theory of Institutions[END_REF].

In our setting w(x, y) is equal to

w x,y = 0 if U(y) ≥ U(x) U(x) -U(y) otherwise.
It is called the resistance of the system to move from x to y. There is no resistance if the state y has larger utility. Otherwise, the resistance is equal to the immediate loss of utility. Let G be the graph corresponding to the possible transitions of P ( ) for > 0, whose links have weight equal to the corresponding resistance of the transition. The graph G for Example 1 is in Fig. 1.

We say that x is a local maximizer of the function U() (with respect to the neighborhood relation defined above), if U(x) ≥ U(z) for all z ∈ I(x).

In the limit for → 0, only the transitions with null resistance are possible, and these are the transitions possible in the matrix P (0). The recurrent communicating classes of P 0 are the local maximizers of the function U(). More precisely, the recurrent communicating classes contain only the local maximizers. Let B(x) be the recurrent communicating class containing the local maximizer x. If all the states y ∈ I(x) have smaller utility than z, then B(x) = {x}, i.e. the class reduces to the single point x. Instead, if there is a state z ∈ I(x) such that U(z) = U(x), then B(x) = B(z), i.e. both states belong to the same class.

We are going to prove that the lim →0 µ( ) exists and it is obviously equal to µ. Only the states in the recurrent communicating classes can be stochastically stable, but not all of them are so. We introduce a new directed graph G , whose nodes are the recurrent communicating classes of P (0), denoted by B 1 , B 2 , . . . B l . The graph is full meshed and the link from B a to B b has weight equal to the resistance of the minimum-resistance path between any state x ∈ B a and y ∈ B b in the graph G. 7 We denote such weight as w Ba,B b . Fig. 1, also shows the graph G for Example 1, using two particular states to identify the corresponding communicating classes. Given a class B a we define its potential V (B a ) to be the resistance of the minimum-resistance spanning tree in G , where from any node there is a path to B a . The potential V (B a ) can be then considered as a global measure of the difficulty to reach a state in B a from the other classes. With some abuse of notation we can define the stochastic potential of a local maximizer x of U() to be the potential of the class it belongs to, i.e. V (x) = V (B(x)). The interpretation is the same: states with lower potential are easier to reach. The following result formalizes this intuition and is an immediate consequence of [26, Chapter 3, Theorem 3.1]. Proposition 4.2. A cache state x is stochastically stable (µ x > 0) if and only if x is a global minimizer for V ().

A consequence of the discussion above is that all the nodes of G correspond to local maximizers of U(), and then only the local maximizers of U() may be stochastically stable (as it was intuitively expected). More importantly, the proposition indicates which of these local maximizers the policy OSA will converge to.

In Example 1, potentials are V ({3, 4}) = 0.035 and V ({2}) = 0.2. The state {3, 4} is the unique global minimizer for the function V (), and by Prop. 4.2 is the only stochastically stable cache state for OSA. In this case OSA converges to state {3, 4} that is the optimal solution of problem (3). Figures 1 shows caches dynamics over time in terms of the utility of the current states for VGreedy, DGreedy and OSA and confirms that they respectively converge to the states {2}, {1} and {3, 4} (we simulated 10 8 request, but there is no change after the first hundred requests).

Unfortunately the following example shows that OSA does not always converge to the optimum.

Example 3 (Convergence to the optimum may fail). Let s 1 = s 2 = 1 and s 3 = 2, p 1 c 1 = p 2 c 2 = 4, p 3 c 3 = 7, B = 2. The system has four possible states: x = {1, 2}, y = {3}, z 1 = {1}, z 2 = {2}. Among those states, only x and y are points of local maximum of U() and x is the point of global maximum. Resistances have the following values: w x,y = 1, w y,x = 3. It follows that there is a unique minimum-resistance spanning tree in G and it is routed in y. OSA converges to y and not to the point of global maximum.

It is definitely interesting to study under which conditions (if any) the minimum-resistance spanning trees are rooted at global maximizers of U() and then optimality of OSA follows. For example, we expect it to be the case under the conditions identified in [START_REF] Hajek | Cooling schedules for optimal annealing[END_REF][START_REF] Tsitsiklis | Markov chains with rare transitions and simulated annealing[END_REF] and we hope that our characterization may allow us to further extend such conditions. Moreover, even when the convergence to the optimum cannot be guaranteed, if the difference between the utility of the global minimizers of V () and the maximum utility can be bounded, then it is possible to guarantee approximation factors for OSA. We leave this investigation for future research and we move now to more practical considerations for our original problem.

Quasi Weak Reversibility

Although our system is not weakly reversible in general, in typical scenarios we expect its dynamics to be close to those of a weakly reversible system and then in particular we expect OSA to converge to the global optimum of the problem or to a close point.

Our support to the previous claim originates from the success of Che's approximation discussed in Sec. 2. If we consider a TTL-policy mimicking OSA (as it has been done successfully for LRU, FIFO, Random, qLRU. . . , see e.g. [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF]), then the corresponding system is weakly reversible. This follows immediately from the fact that for any path from x to y, e.g. x = x 1 , x 2 , . . . x p = y with x n+1 ∈ I(x n ) for n = 1, . . . p -1, the reverted sequence of states is now a possible path from y to x.

Interlude: estimation of content popularity

All the policies described in Sections 3 and 4 require to know content popularities p i . A possibility is to let the policies unchanged, but replace popularities with their estimates. Unfortunately, making timely estimates of varying content popularity is a difficult task. Classic approaches essentially use compact data structures to perform autoregressive moving averages of the current number or requests for each content [START_REF] Broder | Network applications of bloom filters: A survey[END_REF]. Results are far from being satisfactory and popularity estimation is still an open research topic itself (see for example the recent papers [START_REF] Li | Popularity-driven content caching[END_REF][START_REF] Leconte | Placing dynamic content in caches with small population[END_REF]). This is one of the reasons for which simple policies like LRU are a de facto standard, even when content sizes are uniform and the key performance metric is the hit ratio.

Here, we show that popularity estimation can be tricky even under the simple IRM. In such case the asymptotically optimal estimator for the content request rate is simply the total number of requests divided by the observation period. If the memory available for estimation is of the order of the catalogue size (Θ(N )), then it is possible to track the popularity of each content and, after some time, the estimates are precise enough for the policies to run as in the exactknowledge case. If memory is more limited, then performance rapidly degrades. For example Fig. 2 shows the performance of DGreedy and OSA under IRM (details in Sec. 8) when the number of contents tracked are the W most recently requested where W = 5 × 10 4 , 10 5 and 10 6 , i.e. roughly 2, 4 and 40 times more than the average number of objects stored in the cache (the catalogue has 110 millions objects). A similar observation for the case when Bloom counting filters are used is also in [START_REF] Bianchi | Modeling conservative updates in multihash approximate count sketches[END_REF]: the counting error floor (due to false positives) does not allow to evaluate correctly the popularity but for the most popular m contents, where m is the number of counters used. Given the difficulty to estimate content popularities, we would like to design a policy, that does not rely on popularity estimation, but can still asymptotically store the optimal set of contents. The next section shows that this goal is feasible.

How to avoid popularity estimation: DynqLRU

The new policy we propose here is a variant of qLRU including the dynamics of OSA. This policy, that we call DynqLRU is almost as simple to implement as qLRU, but inherits the convergence properties of OSA, without the need to explicitly estimate online popularities. DynqLRU works as follows. Contents are stored in a queue ordered from the most recently requested to the least recently requested object. It is more convenient in this case to consider the cache state to be this sequence. With some abuse of notation, we will still write i ∈ X(n) to indicate that content i is stored in the cache at the time of the n-th request. If the n-th request generates a miss, the content, say i, is retrieved and inserted at the head of the queue with probability

q(n, i) = 1 n αdmin s i c i , (10)
where α > 0 is an adimensional parameter and d min = min i∈N c i /s i is the minimum density across all the catalogue. 8 If space is needed to store the new content, objects are removed from the tail. Upon a hit, the content is served and moved to the front of the queue. We observe that the policy q i -LRU proposed in [START_REF] Neglia | Access-time aware cache algorithms[END_REF] stores a content in the cache upon a miss with probability q i = exp -β si ci (in that paper c i is the content retrieval time from the HDD).

DynqLRU can be considered as a version of q i -LRU where the parameter β changes over time according to β(n) = ln(n)αd min . As for OSA, X(n) can be modeled as a non-homogeneous MC with transition probability matrices {P (n)} n∈N . The following proposition corresponds to Prop. 4.1 for OSA, even if the proof does not follow exactly the same steps. Proposition 6.1. If α ≤ 1/b, the non-homogeneous Markov Chain with transitions matrices {P (n)} n∈N is (strongly) ergodic, i.e. it exists a probability vector µ such that lim k→∞ P x,y (n, k) = µ y for all x, y ∈ X . Moreover, µ is the limit of the stationary distributions of the Markov Chains P (n), i.e. lim n→∞ µ(n) = µ.

The proof is in Appendix D. Now, as in Sec. 4, we should characterize the stochastically stable states of the MC. The following result shows that under Che's approximation, DynqLRU with α ≤ 1/b converges to the solution of the fractional knapsack problem [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF]. Proposition 6.2. Under Che's approximation, when α ≤ 1/b, the stochastically stable sets of DynqLRU store all and only the contents that are included in the solution of the fractional knapsack problem [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF].

Proof. Without loss of generality we assume that contents are ordered so that λ i c i /s i > λ j c j /s j for i < j. Moreover, let b be the largest index value such that b-1

i=1 s i ≤ B and b+1 i=1 s i > C.
Let A * be the set of stochastically stable states of DynqLRU. The probability h i to find content i asymptotically in the cache is

h i = x∈X |i∈x µ x = x∈A * |i∈x µ x .
It follows that 1) if i has null hit probability, all the states x containing i have zero probability and then they are not stochastically stable, and 2) if i has positive hit probability, it needs to belong to at least one stochastically stable state. Then, the stochastically stable states contain all and only the contents that have a positive hit probability asymptotically.

Let β(n) = ln(n)αd min , when n diverges, β diverges and it has been proved in [START_REF] Neglia | Access-time aware cache algorithms[END_REF] that, under Che's approximation, the hit probabilities converge to the solution of the fractional knapsack problem (7)

lim n→∞ h * i =        1 if i < b 0 if i > b C-b-1 i=1 si s b for i = b
Combining the two remarks the thesis follows.

This result corresponds to the weak-reversibility condition in Sec. 4.

Learning in a non-stationary setting

In the discussion above we considered a stationary content request process. Here we discuss how the policies can be adapted in a setting where content popularities vary over time. Policies like LRU or GDS are intrinsically robust to such changes. For the policies that require to know popularities, like DGreedy, VGreedy and OSA, the most natural approach is to keep dynamic estimates of popularities, for example using moving-average or autoregressive filters. This approach requires to tune the filters by estimating the timescale over which popularities may be considered constant. Moreover, the simulated annealing approaches explores the solution space less and less over time. The risk is to maintain stale cache states. A standard approach is to stop decreasing the parameters T (n) or q(n, i) when they reach a given (small) positive value, in order that some exploration is still possible. But in this case we lose the advantage of the fast initial exploration phase. Moreover, the final value has to be carefully selected for the policy to be able to follow popularity changes.

In this section we propose a different solution that leads to a more adaptive and simpler to configure approach. The idea is to couple the system with a change detector to decide when to "reset" the policies, bringing them back to the initial high temperature/high q phase where they explore more. Our solution is based on the standard CUSUM sequential analysis technique to detect online changes of a system parameter [START_REF] Page | Continuous Inspection Schemes[END_REF][START_REF] Granjon | The CUSUM algorithm a small review[END_REF]. CUSUM computes cumulative sums of the deviation of some process samples from their expected value and it declares that a change has happened when this sum exceeds a given value. In [START_REF] Bianchi | Kalman filter estimation of the number of competing terminals in an IEEE 802.11 network[END_REF] a CUSUM filter was coupled with a Kalman filter to estimate the number of competing terminals in a WiFi network. In our case we use CUSUM to detect increases in the expected miss cost, that may suggest that popularities have changed and a new optimal set of contents to be stored need to be found.

Let R(n) be the content requested by the n-th request and C(n) be the corresponding cost. Hence,

C(n) = 0 if R(n) is stored in the cache and C(n) = c R(n) otherwise.
Until no change occurs the costs C(n) are assumed to be i.i.d. random variables with expected value µ C and variance σ 2 C . We implement a one-sided CUSUM filter to detect an increase of the average cost of relative amplitude f . Algorithm 2 describes the pseudo-code. The expected value µ C and the variance σ 2 C are not known and are estimated through a sample average (the maximum likelihood estimator). Costs of value larger than μC (1 + f /2) (then µ C f /2 larger than the expected value) contribute to increase the cumulative sum S. When S is larger than the threshold h, it is assumed that a change has happened and both the dynamic policy and the CUSUM filter are reset.

Algorithm 2 CUSUM change detector

Input: Sequence of costs (C(1), C(2), . . . ), relative change to detect (f ), threshold (h) n ← 1 while true do k ← 1 requests since last reset μC ← 0 estimate current expected cost σ2 C ← 0 estimate current cost variance S ← 0 while S ≤ h do S ← S + μC f /σ 2 C (C(n) -μC (1 + f /2)) + μC ← (μ C (k -1) + C(n))/k σ2 C ← σ2 C (k -1) + (C(n) -μC ) 2 /k k ← k + 1 n ← n + 1 end while reset cache policy end while
The CUSUM filter requires to select two parameters f and h. As we said f corresponds to the minimum level of change in the expected cost that we want to detect. Below we consider f ∈ [0.1, 0.2]. The threshold h allows us to trade off false positive versus false negative rates. It is usual to express the performance of CUSUM filters in terms of the Average Run Length (ARL), i.e. the expected number of requests before a reset. In particular, one distinguishes the ARL under the hypothesis that no change happened (ARL 0 ) or that a change happened (ARL 1 ). ARL 0 quantifies how often false positives occur, while ARL 1 corresponds to the delay before a change is detected. Ideally we would like ARL 0 to be large and ARL 1 to be small, but the two goals are conflicting. The threshold h allows us to trade off the two conflicting issues. In our Inria case we want ARL 0 to be longer than a characteristic timescale of the exploration process of the dynamic policy to avoid false positive to reset the policy when it is still in the exploration phase. We can define such timescale as the number of requests required for the policy to reduce the probability values of a factor 10 θ for the contents with the smallest density c i /s i . A typical value for θ may be 2. Then the characteristic exploration timescale of DynqLRU is 10 θ/α . We want to select h so that ARL 0 ≥ 10 θ/α . The exact expression of ARL 0 requires to solve some complex integral equations [START_REF] Page | Continuous Inspection Schemes[END_REF]. Here we adopt the Wald's approximation [34, Chapter 5, eq. (5.2.44)]:

ARL 0 (h) ≈ 1 I E[∆S] h + e -ω0h ω 0 - 1 ω 0 , where ∆S = μC f /σ 2 C (C(n) -μC (1 + f /2)
) and ω 0 is the unique non-zero solution of I E[e -ω0∆S = 1]. Approximating C(n) with a gaussian variable, we obtain

I E[e -ω0∆S ] = exp -ω 0 I E[∆S] + ω 0 Var(∆S) 2 .
It holds

I E[∆S] = 1 2 µ C f σ C 2 and Var(∆S) = µ C f σ C 2
. Then the unique non-zero solution of

I E[e -ω0∆S = 1] is ω 0 = -1.
Imposing ARL 0 (h) ≥ 10 θ/α , we obtain

e h -h -1 ≥ 1 2 µ C f σ C 2 10 θ/α .
In practical settings content retrieval costs exhibit high variability so that µ C /σ C << 1, and we can consider the simpler inequality:

e h -h -1 ≥ 10 θ/α ,
from which h can be easily be determined.

Simulation results

In this section we evaluate the performance of the different policies using an anonymized, aggregated set of requests for objects collected over 30 days from Akamai. The actual identity of the requested objects was obfuscated, but the size of the object was known. The trace contains 2•10 9 requests for 110 millions contents, whose size varies from few bytes to tens of MB. The empirical Cumulative Distribution Functions (CDF) of popularities and sizes are shown in Appendix E. We use the trace directly (reading the request arrival times from the trace itself), and also to tune the parameters of IRM from the empirical joint content-size distribution.

In the previous sections we have proved that OSA and DynqLRU asymptotically store the optimal set of contents under Che's approximation and provided that the parameters T (n) and q(n, i) decrease slow enough. In many applications the sufficient conditions for convergence can be of low practical interest. For example for DynqLRU if the cache can store b = 10 6 contents, we would require α ≤ 10 -6 and q(n, i) would decrease of a factor ten only after 10 10 6 requests! We need to evaluate how our policies perform under practical settings. In what follows we consider T (n) = 0.001 Ûmax / log n, where Ûmax is the maximum content utility seen until the current time. DynqLRU is configured with α = 10, and d min is set similarly to the minimum density value seen.

We start evaluating the performance of the different policies under the trace-tuned IRM, considering as target the minimization of the miss ratio, i.e. c i = 1. For each policy, we evaluated its performance on 100 IRM request traces generated with different seeds. Each IRM trace has 10 8 requests, the miss ratio is calculated over the last 10 6 requests because we are interested in their convergence properties. We consider the ideal estimators that track the cumulative number of requests for each content ever seen.

We present results for cache sizes B = 1KB and B = 1GB (respectively in the top and bottom row of Fig. 3). When B = 1KB, only requests for the about 30 thousand contents with size between 1 and 10 bytes are considered. This particular scenario allow us to study a small cache for which the settings considered for OSA and DynqLRU are closer to those that would guarantee convergence to the optimum. The left-hand side of Fig. 3 shows the empirical CDF of the miss ratio for the policies that require to estimate popularity. DGreedy achieves a small miss ratio. Indeed when objects have relatively small size in comparison to the knapsack size, the policy that greedily stores the objects with largest density is known to lead to very good approximations. OSA succeeds to find a slightly better set of contents, even if the parametrization does not allow it to consistently converge to them. The right-hand side of Fig. 3 shows the results for the policies that do not require the knowledge of popularities, DynqLRU, GDS, and LRU, as well as the DGreedy as a reference. DynqLRU has a behaviour similar to OSA (not appreciable at this scale), while the policies GDS and LRU perform significantly worse.

When the cache has size 1GB9 and all the content requests are considered, DGreedy achieves the lowest miss ratio as shown in the bottom row of Fig. 3. The OSA policy does not perform equally well: the temperature does not decrease slow enough to reach the optimal allocation and the policy gets stuck in some local minimizer of the miss ratio. We tried temperatures up to 100 times larger, but there was no significant improvement. On the contrary, for the largest temperature values the transient becomes so long, that performance can actually worsen: OSA is still randomly exploring the solution space at the end of the simulation. Despite of this OSA still outperforms VGreedy policy that easily gets stuck in local minima for the miss ratio.

DynqLRU shows performance similar to OSA, but with less variability and less sensitivity to parameter setting. The gap with DGreedy has the same explanation. On the other hand, DynqLRU outperforms both GDS and LRU, whose miss ratios are respectively between 40% and 60% and between 75% and 100% larger than those of DynqLRU.

From now on, we compare the policies using directly the actual trace. We illustrated in Sec. 5 the difficulty to estimate popularities online. Here we provide an additional experiment, comparing the performance of DGreedy, the "winner" under IRM, with those of DynqLRU coupled with a CUSUM (configured as described in Sec. 7 with f = 0.1 and θ = 2). For DGreedy the average request rate of each content ever seen is maintained. Note that a comparison of popularities would require ideally to update all the estimated request rates at the arrival of each request, that may not be feasible. Figure 4 shows the miss ratio over time for two different DGreedy settings. In the first one, the request rate for a content is updated only at the arrival of a request for that content. In the second one, all the estimates are also updated every 10 7 requests, i.e. every 6 hours. The corresponding plots are respectively labeled without/with updates. The experiment shows that even when memory for estimation is not a concern, computation constraints may affect the popularity estimation quality, to the point that the result in Fig. 3 may be reversed and DynqLRU may perform better than DGreedy.

In the following we show the results for the DynqLRU, GDS, and LRU policies and four different retrieval costs: the miss ratio, the upstream traffic, the retrieval time from the server, and the HDD load. The upstream traffic is the amount of data to be retrieved by parent caches or the authoritative content servers, it corresponds to setting c i = s i . For the retrieval time, the cost c i is the average retrieval time for content i as measured in Akamai network we consider. Finally for the HDD load, the cost of i is the work imposed to the HDD to retrieve content i. We have estimated it as a function of the content size and HDD characteristics using the empirical formula proposed in [START_REF] Neglia | Access-time aware cache algorithms[END_REF]. All the metrics have been normalized to 1, by dividing them from the cost that would be incurred if the cache were not present. Results in Fig. 5 show significant improvement from DynqLRU, but for the upstream traffic, for which all the policies have almost the same performance. Average cost reductions in comparison to the second best policy range from 15% for the HDD load up to 30% for the retrieval time and 45% for the miss ratio.

Conclusions and future works

In this paper we have bridged the two cache utility maximization frameworks proposed until now and proved that when costs are linear over the misses and requests follow the IRM, an optimal policy solves online a knapsack problem. We have proposed two new policies based on simulated annealing that are optimal under Che's approximation. Experiments on real traces show that DynqLRU outperforms both LRU and the competitive-ratio-optimal GDS. In the future we will investigate if the potential defined in Sec. 4 can be used to provide strong performance guarantee, as well as perform an extended sensitivity analysis for the configuration of our policies. We are now ready to prove Eq. ( 11) by contradiction. If Eq. ( 11) were not true, there would exist a diverging sequence n m such that

lim m→∞ 1 n m nm k=1 c r(k) 1(r(k)∈X(k)) > U(M * ) a.s. (13)
It holds:

lim m→∞ 1 n m nm k=1 c r(k) 1(r(k)∈X(k)) = lim m→∞ 1 n m nm k=1 U(X(k)) ≤ lim m→∞ 1 n m nm k=1 U(M * ) = U(M * ) (14)
where the first equality follows from Eq. ( 12) and the inequality from M * being the solution of Problem (3). Equation ( 14) contradicts ( 13) and then the thesis follows.

B Proof of Proposition 3.2

Proof. The proof is simpler than that of Prop. where h i is the occupancy/hit probability for content i. The second equality follows from standard renewal arguments and the inequality from h * i being a solution of [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF].

C Proof of Proposition 4.1

Proof. The acceptance probabilities t x,y (n) can be lower bounded as follows Proof. We first prove that the MC is weakly ergodic. Let y i denote the i-th element of the sequence y. Given two states x and y, it is always possible to move from x to y in at most b steps. for example if the following sequence of content requests occurs: y |y| , y |y|-1 , . . . , y 1 and all these contents are stored in the cache (if not already present), followed by b -|y| further requests for content y 1 . The probability that a given content in the cache is requested at time n and it is then stored in the cache is at least p min 1/n α , where p min = min i∈N {p i } is the minimum popularity. Then the probability to move from state x to state y between step nb and step (n + 1)b is bounded as follows (

t x,y (n) ≥ t(n) = e -∆Umax T (n) ∀x, y ∈ X ,
) 15
Remember that the Dobrushin's index of a (finite) transition matrix A with state space X is defined as follows δ(A) = 1min We now move to prove strong ergodicity. We consider that costs c i can be expressed by integer values, and we let γ denote the least common multiple of the set of costs γ = LCM {c i , i ∈ N }. Consider that the variable n can assume any positive real number value and define the matrix function over (0, 1] as follows P (a) = P 1 a γ d min α . P (a) is a regular extension of the matrix P (n) [START_REF] Anily | Ergodicity in parametric non stationary Markov chains: An application to simulated annealing methods[END_REF]Def. 1]. Moreover it can be checked that it is polynomial in the variable a and then all its entries belong to a closed class of asymptotically monotone functions (CAM) [START_REF] Anily | Ergodicity in parametric non stationary Markov chains: An application to simulated annealing methods[END_REF]Def. 3]. These properties of the regular extension P (a), together with the weak ergodicity of the MC {P(n)} imply strong ergodicity of the MC [START_REF] Anily | Ergodicity in parametric non stationary Markov chains: An application to simulated annealing methods[END_REF]Th. 2]. Moreover, for n large enough there is a unique stationary distribution µ(n) of the homogeneous MC P (n), and lim n→∞ µ(n) = µ. Along with each object, the traces report an additional parameter called retrieval time, which is the time needed to fetch the object either from the original server, the cache hierarchy, the disk or the memory, along with the necessary computation (e.g., unzipping or encoding the content). Considering the objects retrieved from the original server and the cache hierarchy, their retrieval times are an effective measure of the pressure on back-end servers each object impose, as computed by the content delivery network management system.

E Additional information on simulations

Thus, in some of our experiments, we use as cost this retrieval time. Due to internal Akamai confidentiality policies, this cost has been re-normalized to an integer between 1 and 10'000.

It is important to note that the retrieval time is not necessarily correlated to object sizes: Fig. 7 shows the relation between the object size and its cost (each point represents an object). We have also computed the correlation coefficient between the size and the cost, obtaining a value equal to 0.013, which indicates no correlation.

Figure 1 :

 1 Figure 1: Example 1: a) Resistance graphs to calculate the potentials (dashed lines indicates transitions with null resistance), b) Utility over time for different policies.

Figure 2 :

 2 Figure 2: Miss ratio over time for the DGreedy (left) and the OSA (right) policies with estimated popularity: impact of the number of objects for which we maintain popularity estimates.

Figure 3 :Figure 4 :

 34 Figure3: Miss ratio over time for B=1KB (top) and B=1GB (bottom), policies with known object popularity (left) and unknown object popularity (right). In both cases we use DGreedy as a reference, which requires the popularity to be known.

Figure 5 :

 5 Figure 5: Miss ratio (top-left), upstream traffic (top-right), retrieval time from origin (bottomleft) and HDD load (bottom-right).

3 . 1

 31 because in this case contents management at the cache are decoupled. It holdslim n→∞ C(π T T L , B, R n ) * T T L , B, R n ) n

  The result follows from[START_REF] Anily | Ergodicity in parametric non stationary Markov chains: An application to simulated annealing methods[END_REF] Theorem 2].RR n°9010D Proof of Prop. 6.1

P

  x,y (nb, (n + 1)b) ≥ p min 1 ((n + 1)b) α b .

( 1

 1 x,y∈X k∈X min(A x,k , A y,k )Then from bound[START_REF] Fricker | A versatile and accurate approximation for LRU cache performance[END_REF], it followsδ(P (nb, (n + 1)b)) ≤ 1 -|X | p b δ(P (nb, (n + 1)b))) ≥ |X | p b 1) αb ,but this series is divergent whenever αb ≤ 1. It follows form the block criterion [37, Ch. 6, Th. 8.2] that the MC is weakly ergodic whenever α ≤ 1/b.

Figure 6 (

 6 Figure 6 (left-hand side) shows the number of requests for each object, sorted by rank (in terms of popularity). The right-hand side shows the empirical Cumulative Distribution Function (CDF) for the size of the requested objects (without aggregating requests for the same object).

Inria

Figure 6 :

 6 Figure 6: Number of requests per object, ordered by rank (left), and cumulative fraction of the requests for objects up to a given size (right).

Figure 7 :

 7 Figure 7: Relation between object size and cost. Each point represents an object.

RR n°9010

When dependance on B is omitted, it means that the two caches have the same size, i.e. B = B.

A practical implementation will require a buffer only slightly larger than B, see[START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF].RR n°9010

In order to prevent these issues, stochastic dynamic programming usually defines directly the utility to be the lim sup or lim inf of the expected average reward (see e.g.[START_REF] Ross | Introduction to Stochastic Dynamic Programming: Probability and Mathematical[END_REF] Ch. 5].

To stress that the request sequence is a sequence of random variables, we denote it by using capital letters.RR n°9010

Additionally, different sizes are taken into account in[START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF], but the CUM framework developed in[START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF] can be immediately extended to consider such case considering the same equality constraint as in[START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF]. Inria

The random selection process can be arbitrary as far as any content currently in the cache has a positive probability to be selected. Selection probabilities can be for example function of content cost, content size or of the time of the last content request. The asymptotic results in this section do not depend on such probabilities but the transient behavior of OSA can depend on them.RR n°9010

The resistance of a path is defined as the sum of the resistances of each link in the path. It is immediate to check that the resistance of the minimum-resistance path does not depend on the specific states x and y chosen in the two classes.Inria

In a practical implementation, it can simply be replaced with the minimum density value seen until now. Note also the difference with the expected density p i c i /s i used by DGreedy.Inria

Depending on the metric and the policy considered, this cache stores on average between 2'000 and 20'000 contents.Inria

A Proof of Proposition 3.1

We first prove that the LHS and the RHS are well defined. The limit inferior in the LHS always exists because C(π, B, R n )/n ≥ 0. For the limit in the RHS, observe that with probability 1 there is a request m such that X(n) = M * for n ≥ m. The status of the cache in the first m -1 timeslots does not affect the limit, we can simply consider that the cache always stored the contents in M * . By the strong law of large it follows then that

We observe that

and similarly

The first term converges by the strong law of large numbers to the expected cost per request, i.e. to U(N ). If follows then that ( 6) is equivalent to

If the states X(n) were independent from the request sequence, the result would follow immediately by the strong law of large numbers for independent r.v.s and the fact that M * is a solution of problem (3), but this is not the case. We are going to define some auxiliary supermartingales.

, where c max max i∈N {c i }. The stochastic process defined by M 0 = 0 and M n+1 = M n + Y n+1 is a martingale relative to the filtration {F n , n = 1, 2, . . . } induced by the request process. In fact

Because of the Pythagoras's theorem for martingales [START_REF] Williams | Probability with Martingales[END_REF]Sec. 12.1], it holds I E[M 2 n ] ≤ nc 2 max . We consider now the stochastic process S n = M n /n. From what we proved for the process M n , it follows that I E[S n ] = 0 and it variance converges to 0 because Var(S n ) ≤ c 2 max /n. The process S n can also been written recursively as

and then S n is a supermartingale. Moreover,

Doob's convergence theorem [START_REF] Williams | Probability with Martingales[END_REF]Th. 11.5] guarantees that, almost surely lim n→∞ S n exists and is finite. We denote by S ∞ the limit r.

Inria