Giovanni Neglia
email: giovanni.neglia@inria.fr

Damiano Carra
email: damiano.carra@univr.it

Ming Dong Feng
email: mfeng@akamai.com

Vaishnav Janardhan
email: vjanardh@akamai.com

Pietro Michiardi
email: pietro.michiardi@eurecom.fr

Dimitra Tsigkari
email: dimitra.tsigkari@inria.fr

Access-time aware cache algorithms

Keywords: Cache, Cache replacement policy, Caching architecture, Content Delivery Network (CDN), Hard disk access time, Knapsack problem Cache, Politique de remplacement de cache, Architecture de cache, Réseau de diffusion de contenu, Temps d'

Most of the caching algorithms are oblivious to requests' timescale, but caching systems are capacity constrained and, in practical cases, the hit rate may be limited by the cache's impossibility to serve requests fast enough. In particular the hard-disk access time can be the key factor capping cache performances. In this paper, we present a new cache replacement policy that takes advantage of a hierarchical caching architecture, and in particular of access-time difference between memory and disk. Our policy is optimal when requests follow the independent reference model, and significantly reduces the hard-disk load, as shown also by our realistic, trace-driven evaluation.

Introduction

The hit probability is a well-known key metric for caching systems: this is the probability that a generic request for a given content will be served by the cache. Most of the existing literature implicitly assumes that a hit occurs if the content is stored in the cache at the moment of the request. In practice, however, in real caching systems the actual hit rate is often limited by the speed at which the cache can serve requests. In particular, Hard-Disk Drive (HDD) access times can be the key factor capping cache performance.

As an illustrative example, Fig. 1 shows the percentage of CPU and HDD utilization, as reported by the operating system, over two days in the life of a generic caching server. As the amount of requests varies during the day, the resource utilization of the caching server varies as well: during peak hours, HDD utilization can exceed 95%. Such loads may cause the inability to serve a request even if the content is actually cached in the HDD. In case of a pool of cache servers, a solution based on dynamic load balancing may alleviate this problem by offloading the requests to another server. Nevertheless, this solution has its own drawbacks, because the rerouted queries are likely to generate misses at the new cache.

In this paper, we study if and how the RAM can be used to alleviate the HDD load, so that the cache can serve a higher rate of requests before query-rerouting becomes necessary.

The idea to take advantage of the RAM is not groundbreaking. Modern cache servers usually operate as a hierarchical cache, where the most recently requested contents are stored also in the RAM: upon arrival of a new request, content is first looked up in the RAM; if not found, the lookup mechanism targets the HDD. Hence, the RAM "shields" the HDD from most of the requests. The question we ask in this paper is: what is the optimal way to use the RAM? Which content should be duplicated in the RAM to minimize the load on the HDD? We show that, if content popularities are known, the problem can be formulated as a knapsack problem. More importantly, we design a new dynamic replacement policy that, without requiring popularity information to be known, can implicitly solve our minimization problem. Our policy is a variant of q-LRU. In q-LRU after a cache miss, the content is stored in the cache with probability q and, if space is needed, the least recently used contents are evicted. We call our policy q i -LRU, because we use a different probability q i for each content i. The value q i depends on the content size and takes into account the time needed to retrieve contents from the HDD. Simulation results on real content request traces from the Akamai's Content Delivery Network (CDN) [START_REF] Nygren | The Akamai Network: A Platform for Highperformance Internet Applications[END_REF] show that our policy achieves more than 80% load reduction on the HDD with an improvement between 10% and 20% in comparison to standard LRU.

The paper is organized as follows. In Sec. 2 we formalize the problem and illustrate the underlying assumptions. In Sec. 3 we present the policy q i -LRU and prove its asymptotic optimality. We evaluate its performance under real-world traces in Sec. [START_REF] Coffman | Operating Systems Theory[END_REF]. Related works are discussed in Sec. 5.

Model

Hard Disk Service Time

Our study relies on some assumptions about the load imposed on the HDD by a set of requests. Consider a single file-read request for content i with size s i . We call service time the time the HDD works just to provide content i to the operating system. Our first assumption is that the service time is only a function of content size s i . We denote it as T (s i ). 1 The second assumption is that service times are additive, i.e. let A be a set of contents, the total time the HDD works to provide the contents in A is equal to i∈A T (s i ), independently from the specific time instants at which the requests are issued. Note that we are not assuming any specific service discipline for this set of requests: they could be served sequentially (e.g. in a FIFO or LIFO way) or in parallel (e.g. according to a generalized processor sharing). 2 But we are requiring that concurrent object requests do not interfere by increasing (or reducing) the total HDD service time.

The analytical results we provide in Sect. 3, which is the main contribution of our work, do not depend on a particular structure of the function T (s i ). Nevertheless, we describe here a specific form based on past research on HDD I/O throughput [START_REF] Barve | Modeling and Optimizing I/O Throughput of Multiple Disks on a Bus[END_REF][3], and based on our performance study of disk access time observed in caching servers. We will refer to this specific form later to clarify some properties of the optimal policy. Furthermore, we will use it in our experiments in Sec. [START_REF] Coffman | Operating Systems Theory[END_REF].

Considering the mechanical structure of the HDD, every time a new read is done, we need to wait for the reading arm to move across the cylinders, and for the platter to rotate on its axis. We call these two contributions the average seek time and average rotation time, and we denote them by σ and ρ respectively. Each file is divided into blocks, whose size b is a configuration parameter. If we read a file whose size is bigger than a block, then we need to wait for the average seek time and the average rotation time for each block.

Once the reading head has reached the beginning of a block, the time it takes to read the data depends on the transfer speed µ. Moreover, while reading, the reading arm needs to move across tracks and cylinders, so we need to add a contribution due to the seek time for read, σ r , which depends on the size of the file we are reading. As a last contribution, we have a constant delay due to the controller overhead, φ. Overall, the function that estimates the cost of reading a file from the hard disk is given by the following equation (see Table 1 for a summary of the variables used):

T (s i ) = (σ + ρ) s i b + 1 µ + σ r s i + φ. (1)
Based on our experience on real-life production systems, the last column of Table 1 shows the values of the different variables for a 10'000 RPM hard drive.

We have validated Eq. 1 through an extensive measurement campaign for two different hard disk drives (10'000 RPM and 7'200 RPM). The results are shown in Fig. 2. In the figure, we actually plot the quantity T (s i )/s i : in Sect. 3 we will illustrate the key role played by this ratio. The estimated value of T (s i )/s i has discontinuity points at multiples of the block size b: in fact, as soon as the size of an object exceeds one of such values, the service time increases by an additional average seek time and an additional average rotation time. The points in the figures represent the output of our measurement campaign for a representative subset of sizes (in particular, for sizes close to the multiples of block size b, where the discontinuities occur). Each point is the average value for a given size over multiple reads. From the experiments, we conclude that the function T (s i ) shown in Eq. 1 is able to accurately estimate the cost of reading a file from the HDD.

Query Request Process

Let N = {1, 2, . . . N } denote the set of contents. For mathematical tractability, as done in most of the works in the literature (see Sec. 5), we assume that the requests follow the popular Independent Reference Model (IRM), where contents requests are independently drawn according to constant probabilities (see for example [START_REF] Coffman | Operating Systems Theory[END_REF]). In particular we consider the time-continuous version of the IRM: requests for content i ∈ N arrive according to a Poisson process with rate λ i and the Poisson processes for different contents are independent. While the optimality results for our policy q i -LRU are derived under such assumption, significant performance improvements are obtained also considering real request traces (see Sec. 4).

Problem Formulation

In general, the optimal operation of a hierarchical cache system would require to jointly manage the different storage units, and in particular to avoid to duplicate contents across multiple units. On the contrary, in the case of a RAM-HDD system, the problem is usually decoupled: the HDD caching policy is selected in order to maximize the main cache performance metric (e.g. hit ratio/rate), while a subset of the contents stored in the HDD can be duplicated in the RAM to optimize some other performance metric (e.g. the response time). contents in the RAM is twofold. First, contents present only in the RAM would be lost if the caching server is rebooted. Second, the global cache hit ratio/rate would not be significantly improved because the RAM accounts for a small percentage of the total storage available at the server. A consequence of such decoupling is that, at any time, the RAM stores a subset (M R ) of the contents stored in the HDD (M H ). 3 In our work we consider the same decoupling principle. As a consequence, our policy is agnostic to the replacement policy implemented at the HDD (LRU, FIFO, Random, . . . ).

We now look at how the RAM reduces the HDD load. An incoming request can be for a content not present in the HDD (nor in the RAM because we consider M R ⊂ M H ). In this case the content will be retrieved by some other server in the CDN or by the authoritative content provider, and then stored or not in the HDD depending on the specific HDD cache policy. Note that the choice of the contents to be duplicated in the RAM plays no role here. Read/write operations can occur (e.g. to store the new content in the HDD), but they are not affected by the RAM replacement policy, that is the focus of this paper. We ignore then the corresponding costs. On the contrary, if an incoming request is for a content present in the HDD, the expected HDD service time depends on the set of contents M R stored in the RAM. It is indeed equal to

i∈M H \M R λ i j∈N λ j T (s i ) = i∈M H λ i j∈N λ j T (s i ) - i∈M R λ i j∈N λ j T (s i ), (2)
because, under IRM, λ i / j∈N λ j is the probability that the next request is for content i, and the request will be served by the HDD only if content i is not duplicated in the RAM, i.e. only if i / ∈ M R .

Our purpose is to minimize the HDD service time under the constraint on the RAM size. This is equivalent to maximize the second term in Eq. [START_REF] Barve | Modeling and Optimizing I/O Throughput of Multiple Disks on a Bus[END_REF]. By removing the constant j∈N λ j , we obtain then that the optimal possible choice for the subset M R is the solution of the following maximization problem:

maximize M R ⊂N i∈M R λ i T (s i ) (3) subject to i∈M R s i ≤ C.
This is a knapsack problem, where λ i T (s i ) is the value of content/item i and s i its weight. The knapsack problem is NP-hard. A natural, and historically the first, relaxation of the knapsack problem is the fractional knapsack problem (also called continuous knapsack problem). In this case, we accept fractional amounts of the contents to be stored in the RAM. Let h i ∈ [0, 1] be the fraction of content i to be put in the RAM, the fractional problem corresponding to Problem (3) is:

maximize h1,...h N N i=1 λ i h i T (s i ) (4) subject to N i=1 h i s i = C.
From an algorithmic point of view, the following greedy algorithm is optimal for the fractional knapsack problem. Assume that all the items are sorted in decreasing order with respect to the profit per unit of size (i.e. λ i T (s i )/s i ≥ λ j T (s j )/s j for i ≤ j). The algorithm finds the biggest index c for which the sum c i=1 s i does not exceed the memory capacity. Finally, it stores the first c contents in the knapsack (in the RAM) as well as a fractional part of the content c + 1 so that the RAM is filled up to its capacity. A simple variant of this greedy algorithm guarantees a 1 2 -approximation factor for the original knapsack problem [5, Theorem 2.5.4], but the greedy algorithm itself is a very good approximation algorithm for common instances of knapsack problems, as it can be justified by its good expected performance under random inputs [START_REF] Kellerer | Knapsack problems[END_REF]Sec. 14.4].

From a networking point of view, if we interpret h i as the probability that content i is in the RAM, 4 then we recognize that the constraint in Problem (4) corresponds to the usual constraint considered under Che's approximation for cache networks [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF], where the effect of the finite cache size is taken into account by imposing the expected cache occupancy for an unbounded TTLcache [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF] to have the form:

N i=1 h i s i = C. (5)
The last remark connects our problem to the recent work in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF], where the authors use Che's approximation to find optimal cache policies to solve the following problem:

maximize h1,...h N N i=1 U i (h i ) (6) subject to N i=1 h i s i = C,
where each U i (h i ) quantifies the utility of a cache hit for content i. 5 Results in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF] do not help us solve our Problem (4) because their approach requires the functions U i (h i ) to be (i) known and (ii) strictly concave in h i . On the contrary, in our case, content popularities (λ i ) are unknown and, even if they were known, the functions U i (h i ) would be λ i h i T (s i ) and then linear in h i .

Besides deriving the cache policy that solves a given optimization problem, [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF] also "reverseengineers" existing policies (like LRU) to find which optimization problem they are implicitly solving. In Sec. 3 we use a similar approach to study our policy.

After this general analysis of the problem, we are ready to introduce in the next section a new caching policy q i -LRU that aims to solve Problem (4), i.e. to store in the RAM the contents with the largest values λ i T (s i )/s i without the knowledge of content popularities λ i , for i = 1, . . . N .

The q i -LRU policy

We start introducing our policy as a heuristic justified by an analogy with LRU.

Under IRM and Che's approximation, if popularities λ i are known, minimizing the miss throughput at a cache with capacity C corresponds to solving the following problem:

maximize h1,...h N N i=1 λ i h i s i (7) subject to N i=1 h i s i = C
The optimal solution is analogous to what discussed for Problem (4): set hit probabilities to one for the k most popular contents, a hit probability smaller than one for the (k + 1)-th most popular content, and hit probabilities to zero for all the other contents. The value of k is determined by the RAM size. Now, it is well known that, from a practical perspective, the traditional LRU policy behaves extremely well, despite content popularity dynamics. LRU is a good heuristic for Problem [START_REF] Fofack | Performance evaluation of hierarchical TTL-based cache networks[END_REF]: it implicitly selects and stores in the cache the contents with the largest values of λ i , even when popularities λ i are actually unknown.

Recall that our purpose is to store the contents with the largest values λ i T (s i )/s i : then, the analogy between the two problems suggests us to bias LRU in order to store more often the contents with the largest values of T (s i )/s i . Intuitively, upon a cache miss, the newly requested content i is cached with probability q i , which is an increasing function in T (s i )/s i . Specifically, we define q i as follows:

q i = e -β s i T (s i ) , i ∈ N , (8)
where β > 0 is a constant parameter. 6 In practical cases, as discussed in section 4, we set β such that q i ≥ q min for every i ∈ N , so that any content is likely to be stored in the cache after 1/q min queries on average. Our policy has then the same behaviour of the q-LRU policy, but the probability q is not fixed, it is instead chosen depending on the size of the content as indicated in Eq. [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF]. For this reason, we denote our policy by q i -LRU.

With reference to Fig. 2, the policy q i -LRU would store with higher probability the smallest contents as well as the contents whose size is slightly larger than a multiple of the block size b. Note that the policy q i -LRU does not depend on the model described above for the HDD service time, but it requires the ratio T (s)/s to exhibit some variability (otherwise we would have the usual q-LRU).

Until now we have provided some intuitive justification for the policy q i -LRU. This reasoning reflects how we historically conceived it. The reader may now want more theoretically grounded support to our claim that q i -LRU is a good heuristic for Problem [START_REF] Coffman | Operating Systems Theory[END_REF]. In what follows we show that q i -LRU is asymptotically optimal when β diverges in two different ways. We first prove in Sec. 3.1 that q i -LRU asymptotically stores in a cache the contents with the largest values λ i T (s i )/s i , as the optimal greedy algorithm for Problem (4) does. This would be sufficient to our purpose, but we find interesting to establish a connection between q i -LRU and the cache utility maximization problem introduced in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF]. For this reason, in Sec. 3.2, we reverse-engineer the policy q i -LRU and derive the utility function it is implicitly maximizing as a function of β. We then let again β diverge and show that the utility maximization problem converges to a problem whose optimal solution corresponds to store the contents with the largest values λ i T (s i )/s i .

Asymptotic q i -LRU hit probabilities

In [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] it is proven that under the assumptions of the IRM traffic model, the usual q-LRU policy tends to the policy that statically stores in the cache the most popular contents when q converges to 0. We generalize their approach to study the q i -LRU policy when β diverges (and then q i converges to 0, for all i). In doing so, we address some technical details that are missing in the proof in [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF]. 7Let us sort contents in a decreasing order of λiT (si) si assuming, in addition, that λiT (si) si = λj T (sj ) sj

for every i = j. Note that the hit probability h i associated to the content i for the q i -LRU policy is given by the following formula (see [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF])

h i (β, τ c ) = q i (β)(1 -e -λiτc ) e -λiτc + q i (β)(1 -e -λiτc ) , (9)
where τ c is the eviction time that, under Che's approximation [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF], is assumed to be a constant independent of the selected content i. Now, by exploiting the constraint:

C = i s i h i (β, τ c ) (10)
it is possible to express τ c as an increasing function of β and prove that lim β→∞ τ c (β) = ∞. This result follows [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF], but, for the sake of completeness, we present it extensively in Appendix A. We can now replace

q i = e -β s i
T (s i ) in Eq. ( 9) and express the hit probability as a function of β only as follows:

h i (β) = 1 -e λiτc(β) e τc(β) s i T (s i ) β τc (β) -λi T (s i ) s i + 1 -e -λiτc(β) . ( 11
)
Let us imagine to start filling the cache with contents sorted as defined above. Let c denote the last content we can put in the cache before the capacity constraint is violated 8 i.e.

c = max k k i=1 s i ≤ C .
We distinguish two cases: the first c contents fill exactly the cache (i.e. c i=1 s i = C), or they leave some spare capacity, but not enough to fit content c + 1. Next, we prove that q i -LRU is asymptotically optimal in the second case. The first case requires a more complex machinery that we develop in Appendix B.

Consider then that

c i=1 s i < C < c+1 i=1 s i .
As an intermediate step we are going to prove by contradiction that

lim β→∞ β τ c (β) = λ c+1 T (s c+1 ) s c+1 . ( 12
)
Suppose that this is not the case. Then, there exists a sequence β n that diverges and a number > 0 such that ∀n ∈ N

either β n τ c (β n ) ≤ λ c+1 T (s c+1 ) s c+1 - (13)
or

β n τ c (β n ) ≥ λ c+1 T (s c+1 ) s c+1 + . (14)
If inequality (13) holds, then ∀i ≤ c + 1

β n τ c (β n ) - λ i T (s i ) s i ≤ β n τ c (β n ) - λ c+1 T (s c+1 ) s c+1 ≤ -
From Eq. ( 11) it follows immediately that

lim βn→∞ h i (β n ) = 1 ∀i ≤ c + 1,
but then it would be

lim n→∞ c+1 i=1 h i (β n )s i = c+1 i=1 s i > C
contradicting the constraint [START_REF] Traverso | Temporal Locality in Today's Content Caching: Why It Matters and How to Model It[END_REF]. In a similar way it is possible to show that inequality ( 14) leads also to a contradiction and then Eq. ( 12) holds.

Because of the limit in Eq. ( 12) and of Eq. ( 11), we can immediately conclude that, when β diverges, h i (β) converges to 1, for i ≤ c, and to 0, for i > c + 1. Because of the constraint [START_REF] Traverso | Temporal Locality in Today's Content Caching: Why It Matters and How to Model It[END_REF] it holds that:

lim β→∞ h c+1 (β) = C -lim β→∞ i =c+1 h i s i s c+1 = C -i≤c s i s c+1 .
The same asymptotic behavior for the hit probabilities holds when c i=1 s i = C, as it is proven in Appendix B. 9 We can then conclude that: 8 We consider the practical case when

s 1 < C < N i=1 s i . 9 When c i=1 s i = C, h c+1 (β) converges to (C - c i=1 s i )/s c+1 = 0. Inria Proposition 3.1.
When the parameter β diverges the hit probabilities for the q i -LRU policy converge to the solution of the fractional knapsack problem (4), i.e.

lim β→∞ h i (β) =      1, for i ≤ c, (C - c i=1 s i )/s c+1 , for i = c + 1, 0, for i > c + 1.
Then the q i -LRU policy asymptotically minimizes the load on the hard-disk.

Reverse-Engineering q i -LRU

In [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF], the authors show that existing policies can be thought as implicitly solving the utility maximization problem (6) for a particular choice of the utility functions U i (h i ). In particular they show which utility functions correspond to traditional policy like LRU and FIFO. In what follows, we "reverse-engineer" the q i -LRU policy and we show in a different way that it solves the fractional knapsack problem. We proceed similarly to what done in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF], extending their approach to the case where content sizes are heterogeneous (see Appendix C). We show that the utility function for content i is

U i (h i ) = -λ i s i 1-hi 0 dx ln 1 + 1-x qix , (15)
that is defined for h i ∈ (0, 1] and q i = 0. Each function U i (.) is increasing and concave. Moreover,

U i (h i ) < 0 for h i ∈ (0, 1), U i (1) = 0 and lim hi→0 U i (h i ) = -∞.
We are interested now in studying the asymptotic behavior of the utility functions U i (h i ) when β diverges, and then q i converges to zero. First, we note that the following inequalities are true for every δ > 0 such that q δ i < 1 -h i :

1-hi 0 dx ln 1 + 1-x qix ≥ 1-hi q δ i dx ln 1 + 1-x qix ≥ 1 -h i -q δ i ln 1 + 1-q δ i q δ+1 i , (16)
where the last inequality follows from the fact that the integrand is an increasing function of x.

Similarly, it holds

1-hi 0 dx ln 1 + 1-x qix ≤ 1 -h i ln 1 + hi qi(1-hi) ≤ 1 -h i ln 1 + 1 qi . (17)
Asymptotically, when q i converges to zero, the lower bound in Eq. ( 16) is equivalent to

1-hi (1+δ) ln(1/qi)
, and the upper bound in ( 17) is equivalent to 1-hi ln(1/qi) . 10 We obtain the following (asymptotic) inequalities when q i converges to 0

1 -h i (1 + δ) ln(1/q i ) ≤ 1-hi 0 dx ln 1 + 1-x qix ≤ 1 -h i ln(1/q i ) , (18)
for every δ > 0 (when q converges to 0, q δ i < 1 -h i asymptotically). Thus, when q i converges to 0, we get

1-hi 0 dx ln 1 + 1-x qix ∼ 1 -h i ln(1/q i ) ,
since, otherwise, we could find an ε > 0 and a sequence q i,n converging to 0 such that for large n

1-hi 0 dx ln 1 + 1-x qi,nx ≤ (1 -ε) 1 -h i ln(1/q i,n ) .
But, this would contradict the left-hand inequality in [START_REF] Thomson | Elementary Real Analysis[END_REF] which is valid for every δ > 0. We conclude that, when q i converges to 0,

U i (h i ) = -λ i s i 1-hi 0 dx ln 1 + 1-x qix ∼ - λ i s i (1 -h i ) ln(1/q i ) .
Next, we consider q i = e -β s i T (s i ) and we can write

U i (h i ) ∼ - λ i T (s i )(1 -h i ) β , when β → ∞.
Note that the maximization problem ( 6) is over the hit probabilities h i and the solution of the problem will be the same even if the functions U i (.) are multiplied by a positive constant. We conclude that, when β diverges, the problem (6) can be formulated as follows

maximize h N i=1 λ i h i T (s i ) (19) subject to N i=1 h i s i = C
which is exactly the formulation of the fractional knapsack problem.

Experiments

In this section we evaluate the performance of our q i -LRU policy. Here we take a numerical perspective, and design a trace-driven simulator that can reproduce the behavior of several caching policies, which we compare against q i -LRU. We have used both synthetic traces generated according to the IRM and real traces collected at two vantage points of the Akamai network [START_REF] Nygren | The Akamai Network: A Platform for Highperformance Internet Applications[END_REF].

We proved that q i -LRU is optimal under the IRM and indeed our experiments confirm it and show significant improvement in comparison to other replacement policies. For this reason, in this section we focus mainly on the results obtained with real traces. In the following, we describe our experimental methodology, show the characteristics of the real traces we use, and present the results of our evaluation.

Inria

Methodology and Performance indexes

The comparative analysis of different caching policies requires an environment where it is possible to reproduce exactly the same conditions for all the different policies. To do so, we adopt a tracedriven simulation approach, 11 which allows us to control the initial conditions of the system, explore the parameter space and perform a sensitivity analysis, for all eviction policies. Our simulator reproduces two memory types: the main memory (RAM) and the hard disk (HDD). Each object is stored in the HDD according to the LRU policy. For the RAM we consider 3 different policies: LRU, SIZE and q i -LRU. They all evict the least recently requested content, if space is needed. They differ in the criterium to decide if storing the most recently requested content:

• LRU always stores it;

• SIZE stores it if 1) its size is below a given threshold T , or 2) it has been requested at least N times, including once during the previous M hours;

• q i -LRU stores it with probability q i , as explained in the previous sections.

So, in addition to comparing q i -LRU to the traditional LRU policy, we also consider the SIZE policy since small objects are the ones that have a bigger impact on the HDD, in terms of their service time T (s i ) (see also Fig. 2). We therefore prioritize small objects, and we store objects bigger than the threshold T only after they have been requested for at least N times. The SIZE policy can thus be seen as a first attempt to decrease the impact of small objects on the HDD, and ultimately reduce the strain on HDD resources. With the q i -LRU policy, we aim at the same goal, but modulate the probability to store an object in RAM as a function of its size, and thus service time.

Note that the hit ratio of the whole cache depends only on the size of the HDD and its replacement policy (LRU). The RAM replacement policy does not affect the global hit ratio. In what follows we focus rather on the number of requests served by RAM and by disk. More precisely, we consider the total disk service time: this is the sum of the T (s i ) of all the objects served by the HDD. Smaller disk service times indicate lower pressure on the disk.

We show the results for a system with 4 GB RAM and 3 TB HDD. We have tried many different values for the RAM size up to 30 GB, and the qualitative results are similar (not shown here for space constraints). For the SIZE policy, we have extensively explored the parameter space (threshold T , number of requests N , and number of hours M ) finding similar qualitative results. 12For the q i -LRU policy, the default value of the constant β is chosen such that min i∈N q i = 0.1 (see Eq. ( 8)).

Trace characteristics

We consider two traces with different durations and collected from two different vantage points. The first trace has been collected for 30 days in May 2015, while the second trace for 5 days at the beginning of November 2015. Table 2 shows the basic characteristics of the traces.

Fig. 3 shows the number of requests for each object, sorted by rank (in terms of popularity), for both traces. For the 30-day trace, there are 25-30 highly requested objects (almost 25% of the requests are for those few objects), but the cumulative size of these objects is less than 8 MB. Since they are extremely popular objects, any policy we consider stores them in RAM, so they are not responsible for the different performance we observe for the different policies.

Inria

Next, we study the relation between the size and the number of requests of each object. In Fig. 4, for each object, we plot a point that corresponds to its size (y-axis) and the number of requests (x-axis). For the 30-day trace, the plot does not include the 30 most popular objects. We notice that the 5-day trace does not contain objects smaller than 1 kB. For ease of representation, we consider the objects with at least 1000 requests (for the 30-day trace, we do not include the 30 most popular objects). This is also shown in Fig. 5, where we plot the empirical Cumulative Distribution Function (CDF) for the size of the requested objects (without aggregating requests for the same object). The 30-day trace contains a lot of requests for small objects, while the 5-day trace contains requests for larger objects (e.g., see the 90-th percentile). In the 30-day trace we have then a larger variability of the ratio T (s)/s (see Fig. 2) and we expect q i -LRU to be able to differentiate more among the different contents and then achieve more significant improvement, as it is confirmed by our results below.

Comparative analysis of the eviction policies

Tables 3 and4 summarize the aggregate results for the two traces we consider in our study. For the hit ratio, we see that the q i -LRU policy can serve more requests from the RAM. On the other hand, the overall number of bytes served by RAM is smaller: this means that the RAM is biased towards storing small, very popular objects, as expected. The last column shows the gain, in percentage, in disk service time between each policy and LRU, which we take as a defacto reference (e.g., -10% for policy "x" means that its disk service time is 10% smaller than for LRU). This is the main performance metric we are interested in. For the 30-day trace, the q i -LRU policy improves by 23% the disk service time, over the LRU policy. For the 5-day trace, the improvement of q i -LRU over LRU is smaller, topping at a bit more than 7%. The reason behind this result relates to the object size distribution in the trace: as shown in Fig. 5, the trace contains objects starting from 1 kB, while, for the 30-day trace, 20% of the requests are for objects smaller than 1 kB. The impact of these objects on the overall T (s i ) is significant.

Next, we take a closer look at our policy, q i -LRU, in comparison to the reference LRU policy. We now consider the contribution to the overall hit ratio of each object, to understand their importance to cache performance. For the 5-day trace, we sorted the objects according to their rank (in term of popularity) and their size, and plot the difference between LRU hit ratio and Inria q i -LRU hit ratio. Fig. 6 shows that both policies store the same 1000 most popular objects; then, the q i -LRU policy gains in hit ratio for medium-popular objects. Switching now to object size, both policies store the same set of small objects, while q i -LRU gains hit ratio with the medium-size objects.

- Fig. 7 considers the contribution to the disk service time of each object (ordered by rank or by size) and shows the difference between q i -LRU and LRU. Clearly, medium popular objects and medium size objects contribute the most to the savings in the service time that our policy achieves.

Sensitivity analysis

Next, we study the behavior of q i -LRU as a function of the parameter β, but we plot the results for the parameter q min = min i∈N q i , that is easier to interpret, being the minimum probability according to which a content is stored in the RAM.

Figure 8 provides two different views. On the left-hand side, it shows the percentage of HDD service time offloaded to the RAM by q i -LRU, both under the 30-day trace and a synthetic IRM trace generated using the same empirical distributions for object size and popularity as in the 30-day trace. As expected, under IRM, the improvement from q i -LRU increases as q min decreases, i.e. as β increases. Interestingly, the HDD benefits even more under the 30-day trace, with more than 80% of the service offloaded to the RAM. This is due to the temporal locality effect (see e.g. [START_REF] Traverso | Temporal Locality in Today's Content Caching: Why It Matters and How to Model It[END_REF]), i.e. to the fact that requests typically occur in bursts and then the RAM is more likely to be able to serve the content for a new request than it would be under the IRM model. We observe also that the performance of q i -LRU are not very sensitive to the parameter q min (and then to β), a feature very desirable for practical purposes. The right-hand side of Fig. 8 shows the relative improvement of q i -LRU in comparison to LRU (calculated as difference of the HDD service time under LRU and under q i -LRU, divided by the HDD service time under LRU). While q i -LRU performs better and better as q min decreases with the IRM request pattern, the gain reduces when q min approaches 0 (β diverges) with the 30-day trace. This is due also to temporal locality: when the probabilities q i are very small, many contents with limited lifetime have no chance to be stored in the RAM by q i -LRU and they need to be served by the HDD. Despite this effect, q i -LRU policy still outperforms LRU over a large set of parameter values and obtain improvements larger than 20% for 0.02 < q min < 0.4. Cache replacement policies have been the subject of many studies, both theoretical and experimental. We focus here on the more analytical studies, which are closer to our contribution in this paper. Moreover, our policy is explicitly designed to mitigate the burden on the HDD, a goal not considered in most previous experimental works, despite its practical importance. Most of the theoretical work in the past has focused on the characterization of the performance of LRU, RANDOM, and FIFO [6][11][9] [START_REF] Bianchi | Check before storing: What is the performance price of content integrity verification in LRU caching?[END_REF]. All these works do not assume different levels of caches, where one level replicates the content stored in the other level to decrease the overall response delay.

The work in [START_REF] Rossini | Multi-Terabyte and multi-Gbps information centric routers[END_REF], instead, considers a 2-level hierarchy, with the content stored in the SSD and DRAM. They design a policy which decreases the response time by pre-fetching the content from SSD to DRAM. To this aim, they focus on a specific type of content, videos divided into chunks, for which the requests are strongly correlated, and a request for a chunk can be used to foresee future requests for other chunks of the same content. In our work, instead, we provide a model for the q i -LRU policy which does not assume any correlation on the requests arrivals, but prioritize the content that imposes a high burden on the HDD.

A different approach is taken in [START_REF] Araldo | Cost-aware caching: Caching more (costly items) for less (isps operational expenditures)[END_REF]. The authors consider that caching policies could be designed with other purposes than maximizing the local hit probability. For example, they propose a heuristic that takes into account the cost to retrieve the contents from expensive interdomain links. Cost-aware caches have been the subject of many experimental studies [START_REF] Bahat | Optimal replacement policies for non-uniform cache objects with optional eviction[END_REF][16] [START_REF] Starobinski | Probabilistic methods for web caching[END_REF]. While these studies are similar in spirit, none of them considers cost functions analogous to the HDD service time that is the focus of this paper. Moreover, they did not prove the optimality of the replacement policies proposed.

The most related work to ours is the cache optimization framework in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF], that we have widely discussed through the paper. We stress again here, that they assume content popularities to be known (or to be explicitly estimated) and the utility functions to be strictly concave, and this is not the case in our problem.

Conclusion

Caches represent a crucial component of the Internet architecture: decreasing the response time is one of the primary objectives of the providers operating such caches. This objective can be pursued by exploiting the RAM of the cache server, while keeping most of the content on the HDD.

In this paper we presented a new cache replacement policy that takes advantage of the accesstime difference in the RAM and in the HDD to reduce the load on the HDD, so that to improve the overall cache efficiency for a capacity constrained storage systems. Our policy, called q i -LRU, is a variant of q-LRU, where we assign a different probability q i to each content based on its size.

We proved that q i -LRU is asymptotically optimal, and we provided an extensive trace-driven evaluation that shown between 10% and 20% reduction on the load of the HDD with respect to the LRU policy.

A Proof of lim β→∞ τ C (β) = ∞

We define the function f as follows

f (τ C , β) = i s i h i = i s i (e λiτ C -1) e β s i T (s i ) + e λiτ C -1 , (20)
as we discussed in Sec. 3.1, Che's approximation implies that f (τ C , β) = C. We will prove that lim β→∞ τ C = +∞. We differentiate the formula (20) with respect to β and τ C and we obtain

∂f ∂τ C = i s i λ i e λiτ C +β s i T (s i ) (e β s i T (s i ) + e λiτ C -1) 2 ∂f ∂β = i -s 2 i e β s i T (s i ) (e λiτ C -1)
T (s i )(e

β s i T (s i ) + e λiτ C -1) 2 .
The first partial derivative is strictly positive while the second is negative for all the values β > 0 and τ C > 0 and, therefore, by the implicit function theorem τ C can be expressed locally as a C 1 function of β and

∂τ C ∂β = - ∂f /∂β ∂f /∂τ C > 0. (21)
This is true in some open set (whose existence is assured by the theorem) containing the points (τ C , β) that verify f (τ C , β) = C. So, τ C is an increasing function with respect to β and the limit lim β→∞ τ C (β) exists. We prove by contradiction that the limit is equal to +∞. Suppose that lim β→∞ τ C (β) < ∞, then, by (20), we get lim β→∞ f (τ C (β), β) = 0. This would contradict the fact that f (τ C , β) = C and therefore we conclude that lim β→∞ τ C = +∞.

B When contents fill exactly the cache

In this section we study the case where is smaller than y (or N + 1 if all the values are larger), i.e. we have

r(y) = max 0 ∪ k = 1, . . . N λ k T (s k ) s k > y , l(y) = min N + 1 ∪ k = 1, . . . N λ k T (s k ) s k < y .
We recall here the definition of a cluster value [START_REF] Thomson | Elementary Real Analysis[END_REF]Exercise 5.10.11], that allows us to express more synthetically some of the following results. 13Definition B.1. Given a function f : A → R, where A ⊂ R, and x 0 ∈ [-∞, +∞] an accumulation point of A, we say that y * ∈ R is a cluster value of f (x) at x 0 if it exists a sequence x n ∈ A -{x 0 } such that lim n→∞ x n = x 0 and lim n→∞ f (x n ) = y * . We also say that f (x) has a cluster value y * at x 0 .

In what follows we only consider cluster values at +∞. For the sake of coinciseness, we will omit to specify "at +∞."

We start establishing some connections between the asymptotic behaviour of β τc(β) and h i (β) in terms of their cluster values.

Lemma B.1. If y * is a cluster value of β τc(β) , then it exists a diverging sequence β n such that, for all i ≤ r(y * ), h i (β n ) converges to 1 and, for all j ≥ l(y * ), h j (β n ) converges to 0.

Proof. From the definition of a cluster value it exists a diverging sequence β n such that lim n→∞ β n /τ c (β n ) = y * . For each i ≤ r(y * ), it holds

lim n→∞ β n τ c (β n ) -λ i T (s i ) s i = y * -λ i T (s i ) s i < 0. Since lim β→∞ τ c (β) = ∞, it holds lim n→∞ τ c (β n ) β n τ c (β n ) -λ i T (s i ) s i = -∞.
From Eq. ( 11), it follows that lim

n→∞ h i (β n ) = 1.
The reasoning for j ≥ l(y * ) is analogous.

A consequence of Lemma B.1 is that if y * is a cluster value of β/τ c (β), then 1 is a cluster value of h j (β) for all j ≤ r(y * ) and 0 is a cluster value of h j (β) for all j ≥ l(y * ).

We can derive results about the convergence of the hit probabilities if we know bounds for the cluster values of β/τ c (β). Proof. For all > 0, it exists a β such that, for all β > β ,

β τ c (β) < b + and β τ c (β) -λ i T (s i ) s i < b -λ i T (s i ) s i + .
For i < r(b), it is λ i T (s i )/s i > b and we can choose sufficiently small so that the left term is bounded away from 0 by a negative constant for large

β β τ c (β) -λ i T (s i ) s i < -δ < 0.
From Eq. ( 11), it follows that, for large β,

1 ≥ h i (β) ≥ 1 -e λiτc(β) e -τc(β) s i T (s i ) δ + 1 -e -λiτc(β)
and then h i (β) converges to 1 when β diverges.

The other result can be proven following a similar reasoning.

The constraint on the expected cache's occupancy under the Che's model leads to the following result:

Lemma B.3. If y * is a cluster value of β τc(β) , then r(y * ) i=1 s i ≤ C ≤ l(y * )-1 i=1 s i .
Proof. Consider the following inequalities that are true for any value of β:

r(y * ) i=1 h i s i ≤ N i=1 h i s i ≤ l(y * )-1 i=1 s i + N i=l(y * ) h i s i .
Because of Eq. ( 5), the middle term is equal to C for all β, then:

r(y * ) i=1 h i s i ≤ C ≤ l(y * )-1 i=1 s i + N i=l(y * ) h i s i .
Finally, Lemma B.1 leads to conclude that the terms h i in the left (resp. right) sum can be made simultaneously arbitrarily close to 1 (resp. 0).

From now on we consider that

λ c+1 T (s c+1 ) s c+1 , λ c T (s c ) s c .
Proof. We prove it by contradiction. Let y * be a cluster value of β τc(β) and assume that y * < λ c+1 T (s c+1 )/s c+1 . Then, it would be r(y * ) ≥ c + 1, leading to

C < c+1 i=1 s i ≤ r(y * ) i=1 s i ≤ C,
where the first inequality follows from the definition of c and the second inequality from Lemma B.3.

If we assume that y * > λ c T (s c )/s c we arrive also to a contradiction.

Proposition B.5. If c i=1 s i = C, then lim β→∞ h i (β) = 1, for i ≤ c, 0, for i > c + 1.
Proof. We first observe that from Lemma B.2 and Lemma B.4 it immediately follows that h i (β) converges to 1 for i < c and to 0 for i > c + 1. We need to consider only i = c and i = c + 1.

We prove that h c+1 (β) converges to 0. Let us assume that it is not the case, then h c+1 (β) has a cluster value h * > 0. Because of Lemmas B.2 and B.4 this implies that β/τ c (β) has a cluster value in λ c+1 T (s c+1 )/s c+1 . But from Lemma B.1 it follows that it exists a diverging sequence β n such that lim n→∞ h i (β n ) = 1, for all i ≤ c. Then, for each > 0, it exists an n , such that for n ≥ n ,

C = N i=1 h i (β n )s i ≥ c+1 i=1 h i (β n )s i ≥ C + h * s c+1 -,
leading to a contradiction.

We have shown that h c+1 (β) converges to 0. Because

C The Langrange method for the utility maximization problem

In this appendix we study q i -LRU in the cache utility maximization framework introduced in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF].

We derive the corresponding utility functions that appear in the maximization problem [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF]. We look for increasing, continuously differentiable, and strictly concave functions U i (.). Moreover, we look for the following functional dependency

U i (h i ) = λ i s i U 0 (h i , q i ), (22)
where U 0 is increasing and concave in h i . In what follows we will consider s i , λ i and q i to be constant parameters, so that U i and U 0 (h i , q i ) are only functions of h i . The Lagrange function associated to problem [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF] is

L(h, α) = N i=1 U i (h i ) -αh i s i + αC,

Inria

where α is the Lagrange multiplier associated to the constraint. Under q i -LRU (for finite β > 0) the hit probabilities h i are in (0, 1), because every content has some chance to be stored and no content is guaranteed to be stored. Then, if the hit probabilities of q i -LRU are the solutions of problem (6) for a given choice of the functions U i (.), they belong to the interior part of the definition set of the concave problem [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF]. The hit probabilities can then be obtained by equating to 0 the Lagrangian derivatives:

∂L ∂h i = dU i dh i -αs i = 0.
Therefore, from the above equation we get14

h i = U -1 i (αs i ). ( 23
)
Taking into account the specific functional dependency in Eq. ( 22), it holds:

h i = U -1 0 α λ i , q i . ( 24
)
We equate the expression above to that in Eq. ( 9) and obtain

1 -e -λiτ C 1 qi e -λiτ C + 1 -e -λiτ C = U -1 0 α λ i , q i .
The expressions on the LHS and the RHS depend on λ i respectively through the products λ i τ C and λ i /α. It follows that we should consider α proportional to 1/τ C , in particular we choose:

α = 1 τ C .
By substituting the above equation into the formula of h i (as given in ( 9)), we obtain h i = q i (1 -e -λ i α ) e -λ i α + q i (1 -e -λ i α )

.

Next, we solve (25) with respect to α and we get α = λ i ln 1 + hi qi (1-hi) .

(26)

Finally, by replacing this expression for α in U i (h i ) = αs i

U i (h i ) = λ i s i ln 1 + hi qi(1-hi) . ( 27
)
By integrating (27) we obtain for h i ∈ (0, 1]

U i (h i ) = -λ i s i 1 hi dx ln 1 + x qi(1-x) = -λ i s i 1-hi 0 dx ln 1 + 1-x qix . ( 28
)
The function is well defined for h i ∈ (0, 1], since

1 hi dx ln 1 + x qi(1-x) ≤ 1 hi dx ln 1 + x qi ≤ q i 1+ 1 q i 1+ h i q i dy ln y < ∞.
For h i → 0 + , the integral diverges.

Figure 1 :

 1 Figure 1: Graph showing the CPU and HDD utilization percentage of a generic caching server.

Figure 2 :

 2 Figure 2: Graph of the function T (s i )/s i .

Figure 3 :

 3 Figure 3: Number of requests per object (ordered by rank).

Figure 4 :

 4 Figure4: Size vs Number of requests. For ease of representation, we consider the objects with at least 1000 requests (for the 30-day trace, we do not include the 30 most popular objects).

Figure 5 :

 5 Figure5: Given an object size, the CDF shows the cumulative fraction of the requests up to that object size (for the 30-day trace, we do not include the 30 most popular objects).

Figure 6 :

 6 Figure 6: Difference between hit ratios when objects are ordered by popularity (left) and by size (right) for the 30-day trace.

Figure 7 :

 7 Figure 7: Difference between service time (served by the RAM) when objects are ordered by rank (left) and by size (right) for the 30-day trace.

Figure 8 :

 8 Figure 8: Sensitivity analysis to the value of q min .

c

  i=1 s i = C. Note that the results up to Lemma B.3 (included) are general, i.e, they do make any assumption on c i=1 s i , while the rest of the section focuses on the case c i=1 s i = C. We start introducing some additional notation. Remember that contents are labeled according to the reverse order of the values λ i T (si) si . Given a point y, we denote by r(y) the largest index RR n°8886 such that λ i T (si) si is larger than y (or 0 if all the values are smaller), and by l(y) the smallest index such that λ i T (si) si

Lemma B. 2 .

 2 If the set of cluster values of β/τ c (β) is a subset of the interval [a, b], then, when β diverges, h i (β) converges to 1, for i < r(b), and to 0, for i > l(a).

c

  i=1 s i = C. Bounds for the cluster values of β/τ c (β) easily follow from Lemma B.3. Lemma B.4. All the cluster values of β τc(β) are in the interval

N i=1 h i

  s i = C, it follows that h c (β) = Ci =c h i (β)s i s cconverges to 1.

5 3 3 . 1 A

 531 Disk Service Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Query Request Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The q i -LRU policy 8 Asymptotic q i -LRU hit probabilities . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Reverse-Engineering q i -LRU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4 Experiments 12 4.1 Methodology and Performance indexes . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Trace characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.3 Comparative analysis of the eviction policies . . . . . . . . . . . . . . . . . . . . . 15 4.4 Sensitivity analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Proof of lim β→∞ τ C (β) = ∞ 21 B When contents fill exactly the cache 21 C The Langrange method for the utility maximization problem 24 RR n°8886 RESEARCH CENTRE SOPHIA ANTIPOLIS -MÉDITERRANÉE 2004 route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr

Table 1 :

 1 Summary of the variables used for T (s i ).

	Variable	Meaning	Typical Value
	s i	Size of object i	-
	σ	Average seek time	3.7•10 -3 s
	ρ	Average rotation time	3.0•10 -3 s
	b	Block size	2.0 MB
	σ r	Seek time for read	3.14•10 -9 s/MB
	µ	Transfer bandwidth	157 MB/s
	φ	Controller Overhead	0.5•10 -3 s

Table 2 :

 2

	Traces: basic information. 30 days	5 days
	Number of requests received 2.22 • 10 9 4.17 • 10 8
	Number of distinct objects	113.15 M		13.27 M
	Cumulative size	59.45 TB	2.53 TB
	Cumulative size of objects
	requested at least twice	20.36 TB	1.50 TB

Table 3 :

 3 Results for the 30-day trace with 4 GB RAM.

				bytes	service	∆ (%)
			% reqs served	time	w.r.t. LRU
	LRU	RAM	73.06	509 TB 4907 h	-
		HDD	26.94	157 TB 1663 h	-
	SIZE	RAM	76.38	512 TB 5055 h	+ 3.02%
		HDD	23.62	154 TB 1515 h	-8.90%
	q i -LRU RAM	84.27	489 TB 5294 h	+7.89%
		HDD	15.73	177 TB 1276 h	-23.27%

Table 4 :

 4 Results for the 5-day trace with 4 GB RAM.

				bytes	service	∆ (%)
			% reqs served	time	w.r.t. LRU
	LRU	RAM	79.61	159 TB 1058 h	-
		HDD	20.39	23 TB	219 h	-
	SIZE	RAM	80.31	160 TB 1064 h	+ 0.57%
		HDD	19.69	22 TB	213 h	-2.74%
	q i -LRU RAM	84.72	149 TB 1074 h	+1.51%
		HDD	15.28	33 TB	203 h	-7.31%

RR n°8886

If the service time is affected by significant random effects, then T (s i ) can be interpreted as the expected service time for a content with size s i .

The specific service discipline would clearly have an effect on the time needed to retrieve a specific content.Inria

Although it is theoretically possible that a content stored in the RAM and in the HDD may be evicted by the HDD earlier than by the RAM, these events can be neglected in practical settings. For example in the scenario considered in Sec.

typical cache eviction times are a few minutes for the RAM and a few days for the HDD for all the cache policies considered.Inria

Since the PASTA property holds under the IRM model, then h i is also the RAM hit probability.RR n°8886

The work in[START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF] actually assumes that all the contents have the same size, but their analysis can be easily extended to heterogenous sizes, as we do in Sec. 3.2.

The reader may wonder why we have chosen this particular relation and not simply q i proportional to T (s i )/s i . The choice was originally motivated by the fact that proportionality leads to very small q i values for some contents. Our analysis below shows that Eq. (8) is a sensible choice.Inria

What is actually proven in[START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] is that there exist two constants k 1 and k 2 with k 1 ≤ k 2 such that the most popular k 1 contents are stored with probability one and the least popular N -k 2 contents with probability 0. The two constants are not estimated and it is unknown what is the asymptotic behaviour of the hit probabilities for the k 2 -k 1 contents with intermediate popularity.RR n°8886

We say that f (x) is equivalent to g(x) when x converges to 0 if lim x→0 f (x)/g(x) = 1, and we write f (x) ∼ g(x).RR n°8886

As a future work, we plan to deploy our policy in a real production system. In this case, the methodology to perform a comparative analysis is substantially different.

As a representative set of results, we show here the case with T = 256 KB, N = 5 and M = 1 hour. RR n°8886

It is also referred to as a cluster point or a limit point (in analogy to the corresponding concept for a sequence).Inria

The existence of the inverse functions of U i (•) follows from the assumption that U i (•) are strictly concave.RR n°8886

Acknowledgment

The authors would like to thank Bodossaki Foundation for supporting Dimitra Tsigkari's internship at Inria.


Dominique Efros

FROM WORKING ON VALUES TO TRANSFORMING SOCIAL ACTIVITIES: HOW TO UPDATE THE PRINCIPLE OF "BY AND FOR ALL"?

Introduction

Problems relating to the collective organisation of work and the occupational lives of employees working at firms in what has come to be known as "the social and solidarity-based economy" are nothing new. It is necessary for these firms to adopt a specific legal status to be able to function on "participative democracy" lines, but it is not sufficient [START_REF] Chanial | Economie sociale et solidaire: le modèle français, Projet de cooperation franco-québécois en économie sociale et solidaire[END_REF]. It is worth noting that the very terms "democracy" and "participation" are highly ambiguous when used in connection with work performed in exchange for wages [START_REF] Efros | La participation salariée à une entreprise : entre technique de gestion, utopie et engagement de soi[END_REF]. The aim of the present contribution is to discuss an idea which seems to be a basic axiom: that it is possible to invent another form of economic action only if other ways of working are also invented at the same time; it can also be said that it is only possible to test other ways of working if the main persons involved are included in the process.

The following general question will be taken here as a starting-point: "How is it possible to involve employees in planning, organising and managing their own work to enable them to work differently?". Planning work is far from being a purely technical affair, as can be seen whenever workers resist the principles of work organisation set up by F.W. Taylor. Work is a human activity which mobilises everything that goes to make up human beings. The way the concept of activity is defined in the fields of anthropology and philosophy stresses the fact that activity in the living reign is a constant struggle against "inertia and indifference" (Canguilhem, 1966). It is a tense dynamic process which involves dealing with the limitations imposed by standardization of all kinds and grasping various opportunities for living, despite all forms of rigid heterodetermination (Schwartz, 2006). There will always be a gap between prescribed work, the formulation of a goal, and the real or actual work involved in reaching that goal. Whether or not the firms in question belong to the profit-making sector, this also means that the ethical values and ideals proclaimed when political goals are launched have to be reworked when it comes to putting them into practice, and the ways they are implemented may even run contrary to the goals initially set.

In other words, working is never very straightforward. It is therefore necessary to analyse occupational activities to understand what the work involved consists of, and to design tools that could be used to manage and organize the activities and situations of the workers at social enterprises differently. To address this question, it is proposed to present a case study on a trade union establishment of a special kind, at which many social innovations have been introduced in terms of the conditions of work and the employees' membership of the wageearners' community. The term "social innovation" is used here as a practical approach designed to improve social situations or solve social problems, which has proved its social relevance [START_REF] Lévesque | L'innovation dans le développement économique et le développement social[END_REF].

After describing the history of this experiment and the huge social challenge it involved, it is proposed to examine how this organisation views the transformations it is about to introduce, and how the employees were called upon to think about these transformations. As we will see, when employees are invited to participate in designing changes, standard methods of staff consultation do not suffice to incite them to express themselves: it is necessary to create a space where they can think about and discuss their problems and learn to voice their personal opinions.

A multi-facet experiment in trade union action

The history of trade unionism in the French gas and electricity industries began in 1890 with the demand for gas supplies to be handled municipally and for all the employees working in this sector to be given an equal status. The legislation passed in 1946 met this demand, since it nationalized the private firms and combined them into two public companies, "Electricité de France" (EDF) and "Gaz de France" (GDF). The trade unions then continued to thrive for many decades and to fight many battles, stressing the need to either produce an economic supply of energy or provide a public service.

The goals of the French electricity and gas workers' trade unions have also been quite specifically designed. The aim of the "multi-base trade unionism" which developed in the late 20s at the instigation of the minority "unitary" faction after the schism undergone by the trade union know as the "Confédération Générale du Travail" improved employees' lives both at work and in society [START_REF] Dreyfus | L'autre exception française", Les Cahiers de l'IFOREP[END_REF]. Trade unions were expected to defend workers' interests in terms of their wages and working conditions, as well as providing support in case of accidents, illness and death and promoting "Popular Education". This was a mixture between trade unions acting as representatives to defend workers' rights and trades unions providing services by catering for the social requirements of those in working spheres. In practical terms, this led to the trade unions investing in fields of action for which mutual societies and employers' social departments had previously catered, while continuing their traditional efforts to improve "Popular Education". This approach to trade unionism was incorporated into the 1946 legislation on nationalisation, which defined the nation-wide status of workers in the French electricity and gas industries: this was quite an innovative status from the wage-earners' point of view. It proved them with job security and solidarity, including paid maternity leave and paid longterm medical leave, and the principles on which retirement pensions were based shifted from a system of accumulated rights to one whereby people at retirement were awarded 75% of their previous earnings. A mandatory bargaining process was also introduced: employees' representatives were henceforth allowed to attend company board meetings and those of various commissions. Wage differentials were reduced by introducing a single wage scale based on a basic wage on which agreements had to be signed between the management and trade unions; the Ministry in charge could be consulted if any long-term conflicts and disagreements arose. "Mixed production committees" were appointed so that decisions about the content of the work and the organization of the departments could be taken near the actual production sites. In addition, the unions were to become officially responsible for providing employees with cultural, sport and leisure activities as well as holidays. All the work involved in providing employees with social protection and handling the activities mentioned above was to be funded by the company EDF-GDF and administered by a board composed entirely of employees' trade union representatives 1 .

Trade unionists in this branch have therefore acquired a great deal of experience. Some of the practices involved are fairly classical, since they were designed to create a balance of power by defending workers' financial interests and improve their working conditions; however, the fact that workers are responsible for managing their own social action is extremely original, since this means acquiring various skills, such as the ability to define social policies with humanly emancipating objectives and handling the economic and organisational aspects of the structures designed to implement these policies.

A gigantic social undertaking

It was decreed by law that in order to provide these services, the administrators of the "central social activities fund" (CCAS) would receive a budget amounting to 1% of the EDF-GDF company's sales. Indexing this budget on the company's sales in this way amounts to recognizing the efforts made by all the employees. At the same time, it serves as an incitement to make further efforts to develop the supply network and give all French citizens equal access to these facilities. The French legislation defined the conditions ensuring that the CCAS would serve truly social ends: its statutes prevent the unions' activities from being dictated by the company's capital holders and proclaim that the budget of the CCAS is intended for the development and use of a "tool by and for human beings" [START_REF] Jantet | L'économie sociale, Coopérative d'information et d'édition mutualiste[END_REF]. This motto, "by and for all", which was inscribed in the French law of 1946, has resulted in the beneficiaries of the company's social policies, the employees, being also the policy-makers as well as being involved in the implementation of these policies 2 . It is frequently referred to in the discourse of the employees working at the CCAS and applied in relation to topics such as equal working conditions, solidarity, prevention of occupational accidents and diseases, healthcare. The main efforts made in 2006 to improve employees' individual and collective quality of life focused on access to holidays and culture, promoting artistic expression and sport, and the social integration of disabled persons. In terms of their commitment to "macrosocial" issues, policies have been adopted promoting sustainable development, fair trade and international solidarity with the victims of natural disasters.

During the year 2006-7, the potential direct beneficiaries of the services proposed by the CCAS numbered 660,000, including 150,000 employees in activity, 145,000 not in activity and 365,000 spouses and children 3 . Apart from dealing with social protection and insurance, the CCAS organizes family holidays and arranged for 420 000 persons to stay at holiday centres that year. The real estate owned by the CCAS includes 215 holiday centres and 27 jointly owned apartment buildings. The demand is nevertheless greater than the capacity. Leisure and socio-cultural activities are still mostly organized by and for the workers of electricity and gas industries, although some of the products on offer are sub-contracted 1 A hard battle was fought between 1946 and 1964 to maintain this principle of self-management. 2 In 2006 and 2007, a conflict about criteria was waged with the Public Audit Office, which objected to the fact that the CCAS had opted for a system of self-management, i.e., activities produced by and for the employees, because this system was said to increase the running and production costs. This was probably more of a battle about economic criteria than anything else. 3 CCAS, the Annual activity report for 2006-2007. elsewhere. The term "gigantic" applied to these social activities is certainly justified in view of the fact that the CCAS is the main purveyor of social tourism, the main producer of shows (it organizes travelling performances and supports local cultural initiatives), as well as being the largest non-profit provider of collective meals in France. In 2006, the 125 midday canteens set up near the group's workplaces produced as many as 6 million meals. These activities have naturally had beneficial effects on the economic and social life of the places where the CCAS has set up its canteens and holiday centres.

The CCAS has to deal with several problems, however. Some of them are encountered by all social organisations of this kind: for example, whether or not to adopt the more individual forms of retribution for employees (by regularly distributing restaurant coupons and cinema coupons and proposing holiday packages) or how to professionalise volunteers. Other problems are more specific to the CCAS because of the turbulent history of the relations between public authorities, companies belonging to gas and electricity sector and employees' trade unions [START_REF] Wieviorka | Le modèle EDF[END_REF][START_REF] Béroud | Les Robins des bois de l'énergie[END_REF] 4 .

The budgetary resources available to finance all these social activities amounted in December 2006 to 497,585 million euros, and the CCAS had 3440 employees on its payroll that year. One third of these employees are over 46 years of age and 53% of them are women. These employees do not all have the same status: some of them have steady jobs, while others work only occasionally or at certain times of year. Some of those with steady jobs are employed by the energy-producing companies in the group, but have been transferred from their previous employment on the production side to deal with social activities, whereas others are engaged directly by the CCAS. The members of the Board of Administration, who are elected by all the employees of the electricity and gas industries, therefore have the status of employers with respect to the workers employed by the CCAS.

Setting up a project

Among the many changes in the management and organization of the social activities introduced by the Board of Administration of the CCAS in response to the changes in the environment which have occurred during the last twenty years or so, especially since the turn of the century, recent events focusing on the midday canteens constitute a particularly sensitive issue involving several aspects5 .

Canteen meals constitute a strategic branch of trade union activity, since the group's canteens form a network of local structures which come into contact every day with the electricity and gas workers, in addition to the special events and exhibitions held on their premises. This is also a sector of activity where the accountancy is a highly complex and demanding task: it occupies one third of all the permanent employees, who numbered 1015 in 2006-2007; if one includes the seasonal and occasional workers, the canteen accounts for 42% of all the staff expenditure at the CCAS. The employees of the CCAS have their own trade union system and their own collective agreement.

The aims for which these changes were introduced at the group's canteens were two-fold. First, they were intended to improve social efficiency by reducing the numbers of electricity and gas industries employees having no access to canteens and distributing their services more evenly over the country; by carrying out awareness campaigns about the effects of food on health; and by using fair trade products and combating the predominance of the food processing industries by adopting specific purchasing policies. The other aim was to boost productivity by re-designing practices and structures; by giving all the links in the chain of actors greater levels of responsibility; by reducing the production costs via new purchasing policies; and by adapting the numbers of employees to match the real needs and making employees more professional. The aims pursued were therefore social efficiency and productivity.

A "project for the development of the occupations involved in the work of the canteens" was therefore set up by a team composed of members of the general management of the CCAS in charge of canteen activities and members of the "operational hierarchy" assisted by a group of consultants specialised in human resource management 6 . In order to transform these occupations, it was proposed to draw up a system of occupational classification based on the set of competences required rather than on an exhaustive list of necessary functions. This led to a proposal for a new occupational nomenclature in which the number of jobs was reduced from twenty to eight. These jobs were subdivided into two categories: production staff and kitchen management staff. Each category is defined by the set of gradually acquired skills and competences required to produce and distribute meals, depending on the size of the canteen in question.

This transformation involves stakes such as the need to define and recognize qualifications, career paths and vocational training paths as well as issues focusing on the organisation of work and job contents. The fact that the job of " dish washer" no longer exists, for example, means that the head cook must arrange for the various canteen workers to deal with dish washing operations in turn. The question of associating the canteen staff in designing the project arose and it was decided that consultations would be held and action plans developed. As "local community managers", the head cooks were asked to present the project to the members of staff working at their canteen and to record the opinions expressed. Although they did not refuse to take charge of implementing these changes, some of them did not wish to present the project themselves to the canteen staff and expressed the need for methodological assistance with organising this consultation and collecting the opinions expressed by the members of staff.

Employees regain the Right of Speech

Our research group was therefore requested by one of the eleven regions to help set up this consultation with the canteen staff 7 . The management of the CCAS wanted each member of staff to "understand the significance of the project and measure its consequences for themselves and the team to which they belonged, which would possibly have some influence on its future development". We were therefore asked to analyse the occupational activities conducted at the various canteens and draw up a kind of inventory which would shed light on the context in which these changes were occurring, as well as to provide the heads of the kitchen staff with assistance prior to and during the consultation. In the first place, this request had to be analysed in order to define its limits and its content.

Analysing the occupational activities carried out at many very different canteens is a timeconsuming task and the deadlines were rather short. Secondly, even if we attended these consultations as simple observers, we were liable to be unjustly suspected of supporting the project. We therefore proposed to organise discussion groups with the canteen staff upstream of the actual consultation, to discuss the content of the work and what the project was going to change and to encourage the workers to think about it and express their opinions.

Groups were set up for this purpose on the basis of three main principles: they should consist of specific categories of employees (canteen workers, cooks, and head cooks) in order to prevent self-censoring processes, they should include people from different canteens in order to dynamise the process of elucidation by making comparisons, and all the participants should cooperate of their own free will. Because of the short deadlines, each group could hold only four meetings. In order to root the discussions firmly in reality and formulate questions based on concrete situations, we adopted an alternating approach consisting in leading discussion groups outside the occupational context as well as going round four canteens on two occasions, observing how the activities were being carried out, once at the beginning of the operation and again in the middle 8 . A concluding report was presented, in which the common problems, the comments made about the present distribution of the work, the questions and opinions about the future canteen-workers' occupations and the criteria for defining career paths were listed. The flood of words triggered at these meetings shows that there was a real need for discussions of this kind and that some worries were felt about how these occupations were likely to evolve: was the project going to improve or degrade people's occupational situations? The humanist values defended by the CCAS did not seem to provide a sufficiently strong guarantee. These hesitations reflecting the "occupational activity point of view" are understandable if we examine what working really means. Generally speaking, occupational activities require arbitration and micro-decision-making to reduce the gap between work as it is planned and prescribed and work as it is actually carried out under the conditions pertaining at the moment with the people present [START_REF] Schwartz | Le paradigme ergologique ou un métier de philosophe[END_REF]. These arrangements are made by juggling 7 Since 1982, our group has developed a special approach to analysing occupational activities and situations. The idea is to set up dialogues between professionals in various branches of the human and social sciences and professional representatives of various occupations and hierarchical levels who are familiar with these situations. Our approach is based on training, research and action projects carried out in work environments. In this particular case, three specialists were involved: a sociologist, an ergonomist and a philosopher. 8 There were twelve of these meetings in all, each lasting 2 ½ hours, eight one-day tours of canteens, two 3-hour meetings with head cooks, heads of operational sectors and regional managers to link up our action plan with the modes whereby the consultation was to be carried out, and two follow-up meetings with regional managers' and national managers' representatives. Our final report on all these discussions was widely distributed so that it could be consulted by all. All these activities were accomplished within three months (from 16th. April to 13th. July 2007).

with various objectives, such as safety/productivity, speed/quality, health/performances, individual economy/collective well-being, etc. They are made at various levels, ranging from the more or less unconscious movements made by the body to save energy to applying social and cultural ideas. Working means assessing and weighing up standards and values which can be contradictory, and therefore make it necessary to take decisions before acting.

Encouraging employees to start speaking up brought these various tensions to light. In order to promote public health, for example, the CCAS puts up posters at its canteens informing employees about the risks associated with poor eating habits; its menus are drawn up on the basis of food programmes established with the help of qualified nutritionists. However, the type of activities carried out at canteens depends directly on the type of produce used. The term "assembly cooking" has been coined to denote the use of pre-cooked products which are ready to use or serve [START_REF] Mériot | Le cuisinier nostalgique, entre restauration et cantine[END_REF]. The use of these effort-saving and time-saving products makes it possible to cope with various problems, such as late delivery by a supplier, or many deliveries occurring on the same day, which disturbs the routine work, or the absence of a member of the team. These products are more expensive than fresh, preserved or deep-frozen products, however, and they have a high salt and sugar content. They all tend to have rather a neutral taste. So, the more fresh products a cook uses, the more he will therefore feel he is providing a quality service, whereas the more ready-processed products he uses, the more he will feel he is not doing his job properly and not promoting good health principles. The decisions he will have to take every day are always rather double-edged: using ready-made products to prepare the first course can save him enough time to be able to prepare homemade desserts.

As the above example shows, similar decisions to those taken at policy-making level are enacted at the "micro" level during occupational activities. Despite the local aspects of the viewpoints discussed in the context of the workplace, these discussions have much in common with the public debates which take place at a higher level. This example also shows how greatly the question of economic efficiency pervades the question of social efficiency in occupational activities, raising problems which people at work have to solve. The question of the "significance" of a project therefore becomes: how can one comply with general objectives when they have nothing to do with what occurs in actual workplace situations? Work is not just work: it always requires weighing up the values underlying the design of technical devices and the way work and social relations are organized.

How could changes "by and for all" be designed?

These discussion groups yielded some very specific questions about occupational gestures, definition of occupations and organization of multi-task work, continuing vocational training and possibility of improving one's qualifications by replacing somebody doing more highly skilled work. These discussion also showed that the very principle of staff consultations was misunderstood, if not overtly criticized. What is the point of asking those who do the work to give their opinion when the concrete modes whereby their occupational situation is going to be transformed have already been designed by others? The principle of "by and for all" did not seem to be at all relevant here. This raises the basic problem of "driving" or "accompanying" change when it comes to designing and implementing the transformation of occupational situations and the lives of employees. What can be done to make the "by" become a concrete reality? At what stage should the staff be directly associated in the decisionmaking process, and what exactly does "to associate" mean?

The "ergonomics of activity" approach made it possible to diagnose the situation, thanks to the experience previously acquired in various occupational settings. Designers all too often ignore practical reality and the unexpected factors with which operators have to constantly juggle. Now if the activity in question is not first analysed in detail with the help of those who actually carry out the work, "meetings between designers and operators at which the former ask the latter to give their opinion about the projects drawn up generally give extremely disappointing results" [START_REF] Daniellou | L'ergonomie, l'activité et la parole des travailleurs[END_REF][START_REF] Bellemare | Action ergonomique et projets industriels : de la coopération dans le travail à la coopération pour la transformation du travail[END_REF]. Lack of awareness of what an occupational situation actually involves can only lead to problems in the future if the changes proposed have not been preceded by discussions at which various points of view are presented: this enriches the design process even if the arguments presented are contradictory.

Analysing occupational activities has led to developing what ergonomists have called "the occupational activity point of view" [START_REF] Duraffourg | Le travail et le point de vue de l'activité[END_REF]. Developing this point of view is not simply a question of expressing what one has experienced at work, since there are two main problems to be overcome: acquiring the ability to look at experience from a distance so as to be able to move from feelings to analysis, and acquiring the ability to appropriate suitable means of expression. Teamwork helps to find significance as long as everyone gets a hearing, since people do not all master the art of putting reality into words to an equal extent [START_REF] Faïta | Le questionnement parmi les ressources de l'analyse du travail[END_REF].

As the example of the CCAS shows, the ability to formulate an opinion at an organised consultation can be improved by introducing a preparatory stage. It also shows that the difference between undergoing and mastering a situation depends closely on the moment at which employees become involved in the design process, since this moment directly determines the importance given to knowledge acquired by experience in the definition of objectives and modes of transformation.

In conclusion, let us say that the use of standardised human resource management methods, which are impregnated with market economy management criteria, cannot but run contrary to the real "human management" of occupational situations. Nor do there exist any universal democratising procedures which can be simply applied with varying degrees of humanity. Cobuilding knowledge and dialogue between designers and operatives in a common quest for the meaning of "working", or in other words, finding means of updating/implementing the principle of "by and for all" can only be done in the framework of an experimental approach. Operational and social efficiency both depend on drawing on the employees' knowledge and experience and discussing the values involved in performing workplace activities. Practical experiments in which the transformation of workplace situations is jointly approached are essential: the challenge is in terms of occupational health and occupational relations.

As far as trade unionism and the question of work are concerned, the way the know-how of unionists is acquired and the way they take action and side with employees are questions of great importance [START_REF] Di Ruzza | De l'activité militante à l'élaboration de savoirs[END_REF]. The slogan "working differently" is not just a potentially mobilising formula, but corresponds to a fundamental truth: in line with the distinction made in the field of ergonomics between work as it prescribe and work effectively done, even working as one is told will also, always, mean "working differently". How then can

The European energy production market has meanwhile been privatised: the two establishments have been separated and have become limited liability trading companies. The integration of the CCAS into the framework of common law would mean that representatives of the heads of firms would be present on the Board of Administration and that the budget allocated to social activities would probably be decreased.

A distinction is made between the works canteens (known as "restauration méridienne") and the canteens serving meals at leisure and holiday centres. The former serve midday meals from Mondays to Fridays.

The elected members of the Board of Administration define general policy orientations which are translated at the three "operational" levels of the CCAS (the general management, the regional management and the operational sectors) into concrete objectives.

we discover all the possibilities suggested by "working differently", from changing the smallest technical details to finding organizational alternatives and possible ways of "living and producing together", both at work and in our social lives?