Keywords:

The present research forms part of a doctoral dissertation studying the treatment of teenagers by civil and criminal justice from the point of view of gender and the various power relations structuring society (1). It draws on at least three sociological fields: the sociology of deviance, which addresses the relationship between the « norm » and its « deviations »; the sociology of law and justice, which deals with a complex professional field marked by highly codified rationalities; and the sociology of gender, which has long permitted the study of gender-biased treatments and provided us with the tools to give an account of them.

Approached from these different angles, our topic can be summarized in the following questions: « How does an institution, whose first objective is to say and apply the law, deliver sentences ? Are these sentences influenced by norms existing outside the institution but predominant in society, as for example gender norms, which tend to construct differentiated models of adolescent boys and girls and of how they deviate? To what extent does justice make arbitrary judgments on the sole basis of gender ?

Production of gender norms by the judiciary:

An issue of concern

In order to define the problem at hand precisely, one must look at it within the context of current controversies on gender. According to Eleni Varikas, gender can be defined as « a framework, a way of studying the world and politics through the prism of sexual difference » (2). Doing research on gender implies therefore that the research concerns divisions inherent to society, particularly the division of humanity into two genders, distinct and naturalized, i.e., constructed as if they were founded in the nature of human beings -as if, for instance, men could be reduced to their hormones or their anatomy.

As concerns justice and more precisely the judicial treatment of adolescents, the question at hand is that of gender determinants in deviance: do girls behave differently from boys ? Why do boys constitute the overwhelming majority of minors summoned to court ? Are girls « less » delinquent ? Three possible answers to these questions have been identified. The first, though it is no longer held in academia, (2) Eleni Varikas, Penser le sexe et le genre, Paris: Presses universitaires de France, 2006, p.17.

continues to shape common sense and certain forms of discourse: according to this view, observed differences in boys' and girls' deviance are founded in nature. Girls tend to question social and family order (an attitude considered typical of adolescence) through private and legal forms such as rejection of parents or adoption of specific dress codes, while boys express protest more openly and in the public space, notably through robbery or acts of violence that land them in court. These clearly differentiated forms of protest are given a biological, hormonal, explanation. This view has however been seriously challenged by more recent research.

(3)

The second approach posits that these « differences » are a matter of socialization and that male and female deviances actually result from differential socialization.

According to this approach, girls are more trained by parents or school to respect social rules and are generally kept away from the public space and risk behaviorsat least, those leading to criminal prosecution. Boys, on the other hand, enjoy more freedom and are consequently more likely to deviate from social rules.

Some aspects of the socialization approach seem relevant and their value has been solidly demonstrated by scholars. However, it seems interesting to explore a third, often underestimated, way of looking at the issue. According to this view, institutions themselves produce social norms, including those that construct boys' and girls' gender identities. Gender norms and the representation according to which boys and girls deviate from social norms differently are partly produced by social control institutions. This position is borne out by comparison of quantified data: girls account for 17 percent of juvenile arrests. This figure drops to 10 percent for girls actually brought to trial and to 7 percent for those reaching the final stage of the criminal process, deprivation of freedom (4). In other words, even though girls represent nearly one out of five offenders arrested each year, they disappear from the criminal process either because they are released (or not prosecuted) or referred to social services -being thus protected by justice. This shows that institutions do indeed play a role in the treatment of male and female juvenile deviance and therefore in related representations of deviance.

We have investigated this hypothesis further by engaging in an ethnological study of two French juvenile courts. Our inquiry is based on a year's observation of hearings, interviews with justice professionals (mainly magistrates and youth workers), Gender scripts of deviance: Some elements of gender ethnography in a juvenile court

The case files that we have analyzed show recurring statements and interpretations that distinguish girls' files from boys' rather sharply. In female juvenile offenders' files, legal proceedings seem to focus on family relations and privacy. If a girl is arrested after spending two days away from home, police officers and youth workers question her about whether she had sexual relations, whether or not the relations were unprotected, or whether she has relationship problems with her parents. By contrast, analysis of boys' situations shows that attention is focused on acts they may have committed and, as the case may be, on their peers. An adolescent boy is more likely to be asked whether he committed such acts in the past, whether he was incited to by other boys, and his entry into delinquency is duly noted. Thus, while girls are perceived as individuals to be protected, even if it means assigning secondary importance to offenses they may have committed, boys are perceived as offenders or potential offenders. The logic at work here is a sharp differentiation in treatments based on gender norms -whereby girls, and more generally women, are vulnerable and boys are legitimate figures of deviance. Tied in with this is the idea that crime control and the most symbolic place where sentences are served -prison, are considered little appropriate for women but totally acceptable for men.

However, this phenomenon is neither new nor specific to the judiciary: it only comes as confirmation of previous observations of the gendered treatment that is common in society. A long time ago, the sociology of sexuality brought to light the sexual double standard, i.e., the gender-based differentiation of teenage sexuality pervading US and European societies. Social sciences have shed light on the tendency of youth control institutions, including the immediate family circle (parents or close relatives), to tacitly consider girls as being at risk sexually and control them accordingly, but to leave boys free to experiment with sex -which is even viewed as a way for teenage boys to cope with difficulties they may face. The scope of the double standard extends beyond the control of sexual activities via differential socialization norms: girls are less allowed to go out and are less encouraged to choose their own activities (5). The double standard observed within the family is echoed in social control institutions by a differential use of sanctions and protection. In order to understand this phenomenon and its mechanisms better, we suggested the use of yet another concept borrowed from the sociology of gender. John Gagnon has introduced the notion of « sexual scripts » to describe the fact that an individual's sexual conduct is determined by conventional, agreed-upon models -for example, sexual scripts determine the choice of a specific order in the different moments of the sexual act over another (6). As Gagnon's theory leaves room for an enlargement of the concept, we suggest that « gender scripts » be used to refer to the general models guiding the actions of justice professionals. Considering female juvenile delinquency as a psychological problem or as originating in the family and seeing boys as potential delinquents are as many responses to widely shared gender scripts. Behind the notion of « script », therefore, is the idea of a commonly shared and institutionalized subtext underlying human behavior.

Gender, individuals, and institutions

Are we to conclude that judges and youth workers are guided by gender « stereotypes » and influenced by their representations of girls' and boys' deviances when they respectively pronounce judgments and assess the cases of minor offenders ?

It is necessary to understand that these justice professionals operate within institutions and that they formulate their pronouncements of judgments and assessments through these very institutions. Gender is a system organizing representations and shaping institutions. Anthropologist Gayle Rubin has spoken of a « sex/ gender system », a « set of arrangements by which the biological raw material of human sex and procreation is shaped by human, social intervention » (7). In the same vein, Mary Douglas has put forward the need to perceive institutions as being founded in nature and legitimated by actors « steered by institutions » (8).

The production of gender within the judiciary thus obeys to a mechanism revealed by gender studies and anthropology -that of an « institutional thought structure » (9) shared and transmitted more or less consciously by most of the institution's agents in their daily activities. The gender system is a set of practices, discourses, and institutionalized activities: this notably explains its great sociological consistency.

Last, let us note that what is relevant for gender is also relevant for the other power relationships prevalent in society and traceable in case files. Ethno-racial origins, social class, or age also constitute a basis for differentiation within the judiciary institution (10).

( 1 )

 1 « Genre et rapports de pouvoir dans l'institution judiciaire. Enquête sur le traitement institutionnel des déviances adolescentes par la justice civile et pénale dans la France contemporaine », doctoral dissertation, Paris 13 University, IRIS, 2016. Joint dissertation advisors were Bertrand Pulman and Marc Bessin.

( 3 )

 3 See in particular Farzaneh Pahlavan, « Contribution des facteurs biologiques dans les manifestations des comportements d'agression chez les femmes », in: Pierrette Verlaan and Michèle Déry (eds), Les conduites antisociales des filles. Comprendre pour mieux agir, Québec: PUQ, 2006. (4) These data originate from national criminal statistics gathered by the Ministry of Justice and the French National Observatory on Delinquency, from penal responses (Ministry of the Interior), and from the national criminal record register. The figures quoted date from 2011. and qualitative and quantitative analysis of over 200 civil and criminal case files. Our conclusions are described in what follows.

( 6 )

 6 John Gagnon, Sexual Conduct: The Social Sources of Human Sexuality, Chicago: Aldine Transaction, 2nd ed., 2005. (7) Gayle Rubin, «The Traffic in Women: Notes on the 'Political Economy' of Sex », Toward an Anthropology of Women, in: Rayna R. Reiter (ed.), New York: Monthly Review Press, 1975. (8) Mary Douglas, Comment pensent les institutions ? [1999], Paris: La Découverte, 2013. (9) Ibid.

( 9 )

 9 This question, which occupies a major part of our dissertation, has been discussed in an article: Arthur Vuattoux, « Les jeunes Roumaines sont des hommes comme les autres », Plein droit, 104, 2015. TEPSIS PAPER 12 / June 2016 Laboratoire d'Excellence TEPSIS, 190-198 av. de France, 75013 Paris, https://tepsis.fr

Laboratoire d'Excellence TEPSIS, 190-198 av. de France, 75013 Paris, https://tepsis.fr


Nicolas Gast
email: nicolas.gast@inria.fr

Benny Van Houdt
email: benny.vanhoudt@uantwerpen.be

Transient and Steady-state Regime of a Family of List-based Cache Replacement Algorithms

Keywords: Cache Replacement Policies, Independent Reference Model, Storage Management, Self-organizing lists, Miss-ratio

We study the performance of a family of cache replacement algorithms. The cache is decomposed into lists. Some of these lists can be virtual in the sense that only meta-data is stored in those lists. An item enters the cache via the first list and jumps to the next list whenever a hit on it occurs. The classical policies FIFO, RANDOM, CLIMB and its hybrids are obtained as special cases. We present explicit expressions for the cache content distribution and miss probability under the IRM model. We develop an algorithm with a time complexity that is polynomial in the cache size and linear in the number of items to compute the exact miss probability. We introduce lower and upper bounds on the latter that can be computed in a time that is linear in the cache size times the number of items.

We introduce a mean field model to approximate the transient behavior of the miss probability and prove that this model becomes exact as the cache size and number of items go to infinity. We show that the set of ODEs associated to the mean field model has a unique fixed point that can be used to approximate the miss probability in case the exact computation is too time consuming.

Using this approximation, we provide guidelines on how to select a replacement algorithm within the family considered such that a good trade-off is achieved between the cache reactivity and its steady-state hit probability. We simulate these cache replacement algorithms on traces of real data and show that they can outperform LRU. Finally, we also disprove the well-known con-

Introduction

Caches are omnipresent in modern day computer systems to improve system performance. A plethora of cache replacement algorithms has been studied by various authors over the past few decades. Nevertheless, explicit expressions for the cache content distribution and miss probability under the well-known Independent Reference Model (IRM) are only available for a limited number of replacement algorithms such as FIFO, RANDOM, LRU, CLIMB and some simple hybrids thereof. Further, these results are of little practical use due to the curse of dimensionality (except for FIFO and RANDOM). As such many approximation methods have been proposed for single caches [START_REF] Dan | An approximate analysis of the LRU and FIFO buffer replacement schemes[END_REF][START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF][START_REF] Fricker | A versatile and accurate approximation for lru cache performance[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Berger | Exact analysis of TTL cache networks[END_REF] as well as for networks of caches [START_REF] Laoutaris | The LCD interconnection of LRU caches and its analysis[END_REF][START_REF] Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Rosensweig | Approximate models for general cache networks[END_REF][START_REF] Gallo | Performance evaluation of the random replacement policy for networks of caches[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Berger | Exact analysis of TTL cache networks[END_REF]. While these approximations have often been shown to result in highly accurate predictions for the miss probability (under the IRM model), their theoretical support is most often rather limited. Further, these prior studies typically focus on the long term (steady state) behavior only, while the transient behavior of the miss probability is also of interest under more dynamic request patterns.

In this paper we study two broad classes of cache replacement algorithms that both organize the cache content in a number of lists (with a fixed size). Items enter the cache via the first list and are promoted to the next list whenever a hit occurs at the expense of demoting another item. Some of these lists can be virtual, meaning that only meta-data is stored for the items in those lists. The difference between the two classes of replacement algorithms exists in the manner in which the demoted item is selected. These two classes of cache replacement algorithms contain the well-known RANDOM, FIFO and CLIMB algorithm as well as some more advanced algorithms introduced in [START_REF] Aven | Stochastic Analysis of Computer Storage[END_REF] as special cases.

The main contributions of the paper are as follows:

1. We show that both classes of algorithms perform alike under the IRM model by deriving an explicit expression for the steady-state cache content distribution and miss probability that is valid in both classes. We subsequently exploit this expression to devise fast algorithms to compute the exact overall and per-item miss probability, thereby avoiding the traditional curse of dimensionality. The time complexity to compute the overall miss probability is linear in the number of items and polynomial in the cache size (where the degree is equal to the number of lists used). We also derive upper and lower bounds on the miss probability that can be computed in a time that is linear in the cache size. 2. We introduce a mean field model (for one of the two classes of replacement algorithms) that can be used to approximate the transient behavior of the miss probability under the IRM model and show that this model becomes exact as the number of items and cache size becomes infinitely large (under some mild conditions). We prove that the set of ODEs that characterizes the mean field model has a unique fixed point and demonstrate that this point can be used to get a highly accurate approximation of the miss probability whenever the exact computation becomes too time consuming. 3. We provide a number of guidelines on how to select the number of lists and list sizes by relying on various experiments using both the IRM model and trace-based simulations. These experiments demonstrate that the algorithms considered in this paper can outperform LRU. We also show that the wellknown conjecture [2, page 135] that the CLIMB algorithm is the optimal finite-memory demand replacement algorithm under the IRM model is false.

The paper is structured as follows. We describe related work in Section 2. In Section 3, we describe the two classes of replacement algorithms. We derive the exact steady-state probabilities and miss probabilities as well as upper and lower bounds in Section 4. We develop our mean-field approximation and show its validity in Section 5. Finally, we provide empirical evidence on how the list sizes should be chosen in Section 6. We conclude in Section 7.

Related Work

Cache replacement algorithms have been analyzed by various authors mostly under the well-known IRM model. While this model is not very suitable in the context of secondary memory management, it is argued by many authors to be a reasonable model in a web caching context. For instance, as stated in [START_REF] Breslau | Web caching and Zipf-like distributions: Evidence and implications[END_REF], for some purposes, one might model web accesses by a simple model that assumes independent references following a Zipf-like distribution and no correlation between request frequency and item size.

Explicit results under the IRM model for the cache content distribution and miss probability have been derived for FIFO and LRU [START_REF] King | Analysis of demand paging algorithms[END_REF][START_REF] Aven | Stochastic Analysis of Computer Storage[END_REF], RANDOM [START_REF] Gelenbe | A unified approach to the evaluation of a class of replacement algorithms[END_REF] and some simple hybrids thereof [START_REF] Aven | Some results on distribution-free analysis of paging algorithms[END_REF][START_REF] Babaoglu | Two-level replacement decisions in paging stores[END_REF]. LRU is shown to outperform FIFO in [START_REF] Van Den Berg | LRU is better than FIFO under the independent reference model[END_REF], while FIFO and RANDOM perform identical [START_REF] Gelenbe | A unified approach to the evaluation of a class of replacement algorithms[END_REF]. These expressions however can only be used directly to compute the miss probability of very small caches (e.g., 20 items). For FIFO, an algorithm to compute the exact miss probability in O(mn) time is given in [START_REF] Fagin | Efficient calculation of expected miss ratios in the independent reference model[END_REF], where n is the number of items and m the cache size.

A number of approximations have been proposed to analyze caches of reasonable size (they are fast to compute and can be used for cache sizes of more than millions of items). In [START_REF] Dan | An approximate analysis of the LRU and FIFO buffer replacement schemes[END_REF] a fast iterative scheme is proposed for FIFO that coincides with the iterative algorithm proposed in [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] for RANDOM. For LRU the author of [START_REF] Dan | An approximate analysis of the LRU and FIFO buffer replacement schemes[END_REF] introduce an O(mn) time approximation, which is of limited use since the introduction of what is now called the Che-approximation [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF], for which theoretical support is provided in [START_REF] Fricker | A versatile and accurate approximation for lru cache performance[END_REF].

Recently, the idea of the Che-approximation was generalized to capture a broader class of replacement algorithms, under the IRM model, in case of a renewal model [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] and for general MAP arrivals [START_REF] Gast | Asymptotically Exact TTL-Approximations of the Cache Replacement Algorithms LRU(m) and h-LRU[END_REF]. While [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] also considers replacement policies that make use of multiple lists, all but one of these lists are assumed to be virtual lists that only store the meta-data and not the actual items. Further, the algorithms are approximations, but no proof of accuracy is provided. The analysis of [START_REF] Gast | Asymptotically Exact TTL-Approximations of the Cache Replacement Algorithms LRU(m) and h-LRU[END_REF] complements our paper and provides an approximation that is asymptotically exact (as opposed to the one of [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF]). Renewal models were also considered in [START_REF] Jung | Modeling TTL-based internet caches[END_REF][START_REF] Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Berger | Exact analysis of TTL cache networks[END_REF] for time-to-live caches which, in light of the Che-approximation, can be used to approximate capacity-driven replacement polices. Another line of work is to consider that the popularities of items vary over time. As shown in [START_REF] Traverso | Temporal locality in today's content caching: why it matters and how to model it[END_REF], this can be modeled by a shot-noise model that describes the temporal locality between consecutive requests. Che-like approximation for such models are developed in [START_REF] Leonardi | Least recently used caches under the shot noise model[END_REF].

More practically oriented simulation based studies have also been performed and we do not attempt to provide an overview here. We would like to indicate that the idea of using multiple lists has been explored before, e.g., the 2Q and LIRS policies both combat the poor performance of LRU on scan sequences and typical database access patterns [START_REF] Johnson | 2Q: A low overhead high performance buffer management replacement algorithm[END_REF][START_REF] Jiang | LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance[END_REF].

Considerable efforts have also been made to develop approximation methods to analyze networks of caches [START_REF] Laoutaris | The LCD interconnection of LRU caches and its analysis[END_REF][START_REF] Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Rosensweig | Approximate models for general cache networks[END_REF][START_REF] Gallo | Performance evaluation of the random replacement policy for networks of caches[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Berger | Exact analysis of TTL cache networks[END_REF]. Some of these methods are iterative in nature and require the repeated solution of isolated caches, [START_REF] Rosensweig | Approximate models for general cache networks[END_REF]. Hence, studying isolated caches is useful in the study of networks of caches.

Fluid limits for the miss probability have been derived for LRU [START_REF] Jelenkovic | Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities[END_REF], 2Q [START_REF] Hirade | Analysis of page replacement policies in the fluid limit[END_REF] and RANDOM [START_REF] Tsukada | Fluid limit analysis of FIFO and RR caching for independent reference models[END_REF]. Our mean field result is more general compared to [START_REF] Hirade | Analysis of page replacement policies in the fluid limit[END_REF][START_REF] Tsukada | Fluid limit analysis of FIFO and RR caching for independent reference models[END_REF]. These papers consider a system with n classes of items and N items per class. The items within a class are indistinguishable (they all have the same popularity). They show that their approximation is correct as N goes to infinity. Our approach is more general since we do not assume that items are clustered into a finite number of classes. Rather, our bound in Theorem 6 depends directly on the popularity of the most popular objects p i and not on the number of objects.

Replacements algorithms

In this section we introduce two families of replacement algorithms that are obtained by slightly modifying a family of replacement algorithms introduced in [START_REF] Aven | Stochastic Analysis of Computer Storage[END_REF]. We denote the members of these families as FIFO(m, v) and RAND(m, v), respectively, where m = (m 1 , m 2 , . . . , m h ) is a tuple of integers with m i ≥ 1 (for i = 1, . . . , h) and v < h.

The FIFO(m, v) replacement algorithm: The FIFO(m, v) algorithm makes use of h > v lists, labeled 1 to h. Only the items present in list v + 1 to h are stored in the cache, while for the items in lists 1 to v only meta-data is stored. As in [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF], we say that lists 1 to v are virtual lists. The length of list i is equal to m i , for i = 1, . . . , h, and the total cache size is equal to m = h i=v+1 m i . Items enter the set of lists via list 1 and whenever requested while being part of list i they move up one list. More specifically, one of the following four events occurs when an item, say item k, is requested at some point in time:

1. Item k was not in any of the lists (miss) -in this case item k is inserted in position 1 of list 1. The remaining items in list 1 move back one position, while the item that was in the last position of list 1, that is, in position m 1 , is removed from the cache. 2. Item k was in position j of list i ≤ v (miss) -in this case item k moves to position 1 of list i + 1, all the items in list i + 1 move back one position, the item that was in position m i+1 of list i + 1 takes the former position of item k, that is, position j in list i. 3. Item k was in position j of list v < i < h (hit) -this case is identical to the previous except that there is a hit. 4. Item k was part of list h (hit) -in this case no changes are made.

The RAND(m, v) replacement algorithm: The RAND(m, v) algorithm operates in a manner similar to the FIFO(m, v) algorithm, except for two changes. First, when the requested item is not part of any list, it is inserted in a random position in list 1 (as opposed to position 1) and the item that was in this randomly selected position is removed from the cache. Second, when a request occurs for an item part of list i < h, say in position j, the item is inserted in a random position in list i + 1, while the item that was in this randomly selected position moves to position j of list i. In other words, only two items change position in case a hit in list i < h occurs.

We will show that the FIFO(m, v) and RAND(m, v) algorithm have the same steady state distribution for the cache content under the IRM model, which is a generalization of the well-known fact that FIFO and RANDOM perform alike under the IRM model [START_REF] Gelenbe | A unified approach to the evaluation of a class of replacement algorithms[END_REF]. In fact, one can even show that the steady state probabilities of FIFO(m, v) remain the same if we do not update the lists when an item part of some lists is requested unless the item is in the first position of some list i, for i = 1, . . . , h -1.

A natural extension of these policies is to consider the two following variants: strict FIFO(m, v) and LRU(m, v):

strict FIFO(m, v) -The only difference between FIFO(m,v) and strict FIFO(m, v) is when a request occurs for an item that is in position j of a list i < h. As before, item k moves to position 1 of list i + 1 and all the items in list i + 1 move back one position. The difference is that the item that was in position m i+1 of list i + 1 moves to position 1 of list i and the items that were in position 1 to j -1 of list i move back one position. -LRU(m, v) -The difference between LRU(m, v) and strict FIFO(m, v) is when a hit occurs in position j of list h. In this case, this item is moved to the first position of list h and all the items in the positions 1 to j -1 of list h move back one position.

The strict FIFO(m, 0) algorithm corresponds to the policy A h m h (m h , . . . , m 1 ) of [START_REF] Aven | Stochastic Analysis of Computer Storage[END_REF], while the LRU(m, 0) algorithm is denoted as A h 1 (m h , . . . , m 1 ) in [START_REF] Aven | Stochastic Analysis of Computer Storage[END_REF]. Note that the lists in [START_REF] Aven | Stochastic Analysis of Computer Storage[END_REF] are labeled in the opposite order. The FIFO(m, v) and the strict FIFO(m, v) algorithms operate identical when m 1 = . . . = m h-1 = 1. For this special case, closed-form results for the steady-state probabilities for FIFO(m, 0) algorithm under the IRM model were also derived in [START_REF] Aven | Stochastic Analysis of Computer Storage[END_REF].

Although these algorithms are close to our definition of FIFO(m, v), simple closed-form expressions for the cache content distribution and miss probabilities do not appear to exist. In Section 6, we compare all these policies us-ing trace-based simulation. We demonstrate that the hit probabilities of strict FIFO(m, 0) and FIFO(m, 0) are close to each other (unless m 1 is close to m), while LRU(m, 0) outperforms these policies only marginally (at the expense of slightly more work).

Steady state probabilities

In this section, we compute the stationary measure of the policies FIFO(m, v) and RAND(m, v) under the independent reference model (IRM). Under the IRM model the sequence of request ids is a sequence of i.i.d. random variables. We denote by p i the probability that the id of a requested item is i.

The product-form stationary measure

Let Y i,j (t), with (i, j) ∈ I(m) {(i, j)|i = 1, . . . , h, j = 1, . . . , m i }, be the id of the item in position j of list i at time t, where we observe the set of lists whenever a request arrives. Let C n (m) consists of all the sequences (c 1 , . . . , c m ) of m distinct integers taken from the set {1, . . . , n}. Under the IRM model the process Y = {(Y i,j (t), (i, j) ∈ I(m)), t ≥ 0} is clearly a Markov chain on the state space C n (m) for the FIFO(m, v) and RAND(m, v) algorithms. Denote π A (c), with c = (c 1 , . . . , c m ), as the steady state probability of state c, where A = FIFO(m, v) or RAND(m, v) denotes the replacement algorithm used. Note that the evolution of the Markov chain does not depend on the parameter v.

To ease the notation denote c i-1 s=1 ms+j as c(i, j) for (i, j) ∈ I(m), where we can think of c(i, j) as the id of the item in position j at list i. The next theorem shows that the steady state probabilities of this Markov chain have a simple closed form for the FIFO(m,v) or RAND(m,v) algorithm:

Theorem 1 The steady state probabilities π RAND(m,v) (c) and π FIFO(m,v) (c), with c ∈ C n (m), can be written as

π FIFO(m,v) (c) = π RAND(m,v) (c) = π(c) 1 Z(m) h i=1   mi j=1 p c(i,j)   i , (1)
where

Z(m) = c∈Cn(m) h i=1 mi j=1 p c(i,j) i .
Proof The proof consists in verifying the balance equations. We start with the RAND(m, v) algorithm. Denote c (i,j)↔(i ,j ) as the vector c with c(i, j) and c(i , j ) exchanged and c k→(i,j) as the vector c with entry c(i, j) replaced by k. We can express the global balance equation of state c as

π RAND(m,v) (c)   1 - m h j=1 p c(h,j)   = k =c1,...,cm m1 u=1 π RAND(m,v) (c k→(1,u) ) p c(1,u) m 1 + h-1 i=1 mi u=1 mi+1 w=1 π RAND(m,v) (c (i,u)↔(i+1,w) ) p c(i+1,w) m i+1 ,
as we exit state c unless there is a hit on one of the entries in list h, while we can enter state c because there is a miss (and some item is inserted in a random position in list 1) or there is a request for an item in list i that moves up to a random position at list i + 1. Implicitly plugging in [START_REF] Aven | Some results on distribution-free analysis of paging algorithms[END_REF] and noting that π(c (i,u)↔(i+1,v) )/π(c) = p c(i,u) /p c(i+1,v) and π(c k→(1,u) )/π(c) = p k /p c(1,u) holds for (1), yields 1 -

m h j=1 p c(h,j) = k =c1,...,cm p k + h-1 i=1 mi u=1 p c(i,u) ,
which clearly holds as n i=1 p i = 1. For FIFO(m, v), let the vector c miss(k) be identical to c except that the entries (c miss(k) (1, 1), . . . , c miss(k) (1, m 1 )) are equal to (c(1, 2), . . . , c(1, m 1 ), k) and denote c hit(i,j) as the vector c except that (c hit(i,j) (i + 1, 1), . . . , c hit(i,j) (i + 1, m i+1 )) = (c(i + 1, 2), . . . , c(i + 1, m 1 ), c(i, j)) and c hit(i,j) (i, j) = c(i + 1, 1).

π FIFO(m,v) (c)   1 - m h j=1 p c(h,j)   = k =c1,...,cm π FIFO(m,v) (c miss(k) )p c(1,1) + h-1 i=1 mi j=1 π FIFO(m,v) (c hit(i,j) )p c(i+1,1) .
The result follows by noting that π(c miss(k) )/π(c) = p k /p c(1,1) and π(c hit(i,j) )/ π(c) = p c(i,j) /p c(i+1,1) holds for [START_REF] Aven | Some results on distribution-free analysis of paging algorithms[END_REF].

When h = 1, v = 0 and c = (c 1 , . . . , c m ) we get

π(c) = 1 Z(m) m j=1 p cj .
These are the well-known steady state probabilities for the FIFO and RANDOM algorithm [START_REF] King | Analysis of demand paging algorithms[END_REF][START_REF] Gelenbe | A unified approach to the evaluation of a class of replacement algorithms[END_REF]. When h = m, meaning m i =1 for all i, the RAND(m, 0) algorithm coincides with the so-called TRANSPOSITION rule or CLIMB algorithm [START_REF] Starobinski | Probabilistic methods for web caching[END_REF][START_REF] Hester | Self-organizing linear search[END_REF]. In this case the above theorem reduces to

π(c) = 1 Z(m) m j=1 p j cj ,
which are the steady state probabilities of the CLIMB algorithm as reported in [START_REF] Aven | Stochastic Analysis of Computer Storage[END_REF]Section 4.2]. Theorem 1 also generalizes the results for the second family of replacement algorithms studied in [START_REF] Aven | Some results on distribution-free analysis of paging algorithms[END_REF] which corresponds to m 1 = . . . =m h-1 =1 and v = 0

π(c) = 1 Z(m) m j=1 p min(j,h) cj .
Due to Theorem 1 it is easy to check that the following corollary holds:

Corollary 1 For the RAND(m, v) replacement algorithm the Markov chain Y is reversible, i.e., π(c)P[Y (t+1) = c |Y (t)=c] = π(c )P[Y (t+1) = c|Y (t)=c ],
for any c, c ∈ C n (m).

Denote the hit probability of the RAND(m, v) and FIFO(m, v) algorithms as H(m, v) and let M (m, v) = 1 -H(m, v) be the miss probability under the IRM model. Clearly, one can express the miss probability via the steady state probabilities

M (m, v) = c∈Cn(m)   1 - h i=v+1 mi j=1 p c(i,j)   π(c).
(

) 2
This formula is however not very useful to compute M (m, v), unless m is very small, as the number of terms is exponential in m. In the next two sections we indicate how to compute the overall and per item miss probability in a more efficient manner.

Exact overall miss probability

In this section we introduce Algorithm 1 that computes the steady-state miss probability in a time that is polynomial in the cache size m, where the degree of the polynomial is equal to h. This algorithm is a generalization of the methodology introduced in [START_REF] Fagin | Efficient calculation of expected miss ratios in the independent reference model[END_REF] for the FIFO algorithm (which corresponds to the case with h = 1). It uses a dynamic programming approach: to compute M (m, v), for v < h, we compute M (m , v) for all m ≤ m (component-wise). In other words, the quantities M (m , v) are obtained as by-products of the computation of M (m, v). Obtaining these quantities is useful when studying optimal list sizes. More precisely, define a first set of list sizes

V ≤m h = (m 1 . . . m k ) k ≤ h, k i=1 m i ≤ m ,
and a second set of list sizes

V m1...m h h = {(m 1 . . . m k ) | k ≤ h, m i ≤ m i } .
Our algorithm computes the miss probabilities

M (m, v) for all m ∈ V ≤m h in O(nh 2 m h /h!) time and for m ∈ V m1...m h h in O(nh 2 h i=1 (m i + 1
)) time. In the next section, we show how to compute the corresponding per item hit probabilities in O(n 3/2 h 2 m h /h!) and O(n 3/2 h 2 h i=1 (m i +1)) time, respectively. Let p 1 , . . . , p n be a fixed but arbitrary ordering of the request probabilities and r = (r 1 , . . . , r h ) with r i integer for all i and r = i r i . Let e j be the j-th row of the size h identity matrix. Define E(0, k) = 1, E(r, k) = 0 if i r i > k or r j < 0 for some j and

E(r, k) = c∈C k (r) h i=1   ri j=1 p c(i,j)   i . (3)
By noting that the probability that the requested item is in position j of list i is the same for any j ≤ m i and using [START_REF] Aven | Stochastic Analysis of Computer Storage[END_REF] we can express M (m, v) via E(r, k):

M (m, v) = c∈Cn(m)   k ∈c p k + v i=1 mi j=1 p c(i,j)   π(c) = E(m + e 1 , n) + v i=1 m i E(m + e i+1 -e i , n) E(m, n) .
Further, we have the following recursion for E(r, k) by noting that item k appears at most once in c:

E(r, k) = E(r, k -1) + h j=1 r j p j k E(r -e j , k -1). (4)
In principle we can use this recursion with E(e j , 1) = p j 1 to compute the miss probabilities. However, E(r, k) decreases quickly in i r i and can easily cause underflows even for m values below 100 (as in [START_REF] Fagin | Efficient calculation of expected miss ratios in the independent reference model[END_REF] for the FIFO replacement policy). To avoid this problem, we define for i = 1, . . . , h:

F i (r, k) = E(r, k) E(r -e i , k) , (5)
for r = (r 1 , . . . , r h ) with r j ≥ 0 for j = i and r i ≥ 1. Let F i (r, k) = 0 if i r i > k or r j < 0 for some j or r i ≤ 0. Note as

E(m + e i+1 -e i , n) E(m, n) = E(m + e i+1 -e i , n) E(m -e i , n) E(m -e i , n) E(m, n) , the miss probability M (m, v) equals M (m, v) = F 1 (m + e 1 , n) + v i=1 m i F i+1 (m + e i+1 -e i , n) F i (m, n) .
The next theorem establishes a recursive relationship for the F i (r, k) values that allows us to compute the miss probabilities without causing underflows.

Theorem 2

The miss probability, given by

M (m, v) = F 1 (m + e 1 , n) + v i=1 m i F i+1 (m + e i+1 -e i , n) F i (m, n) ,
and the quantities F i (r, k), for i = 1, . . . , h, r = (r 1 , . . . , r h ) with r j ≥ 0 for j = i and r i ≥ 1, obey the following recursion

F i (r, k) = F i (r, k -1) + h j=1,j =i p j k r j Fi(r-ej ,k-1) Fj (r-ei,k-1) + p i k r i 1 + h j=1,j =i p j k rj Fj (r-ei,k-1) + p i k (ri-1)1 {r i >1} Fi(r-ei,k-1) , (6)
and

F i (e i , 1) = p i 1 .
Proof By applying (4) on the numerator and denominator of (5) we get that F i (r, k) can be written1 as

E(r, k -1) + h j=1 p j k r j E(r -e j , k -1) E(r -e i , k -1) + h j=1 p j k (r j -1 {i=j} )E(r -e i -e j , k -1)
.

By dividing the numerator and denominator by E(r -e i , k -1) (which is well defined as r i > 0 and differs from zero as s r s -1 ≤ k -1), we find

F i (r, k) = F i (r, k -1) + h j=1,j =i p j k r j E(r-ej ,k-1) E(r-ei,k-1) + p i k r i 1 + h j=1,j =i p j k rj Fj (r-ei,k-1) + p i k (ri-1)1 {r i >1} Fi(r-ei,k-1)
.

The result follows by noting that E(r -e j , k -1)/E(r -e i , k -1) can be written as

F i (r -e j , k -1)/F j (r -e i , k -1) when r j > 0. Denote R k,h as the set {(r 1 , . . . , r h )|r i ∈ {0, . . . , k}, 1 ≤ h i=1 r i ≤ k}.
Algorithm 1 indicates how to use the above theorem to compute the values of

F i (r, k) for i = 1, . . . , h, k ≤ n and r ∈ R k in O(nh 2 |R m+1,h |) time with |R m+1,h | = O(m h /h!).
In other words we can determine the set of miss probabilities M (m, v) for m ∈ V ≤m h in O(nh 2 m h /h!) time, where n is the number of items. Similarly, one can compute the set of miss probabilities M (m, v) for any m ∈ V m1,...,m h h in O(nh 2 h i=1 (m i + 1)) time. For the CLIMB algorithm we have m 1 = . . . = m h = 1 and h=m, meaning the miss probability can be computed in O(nm 2 2 m ) time, which is still exponential in m, but clearly a significant gain over directly relying on (2).

Per item miss probabilities

In this section we focus on the hit probability of item k, denoted as

H (k) (m, v), for k = 1, . . . , n. We first show how to express M (k) (m, v) = 1 -H (k) (m, v) in terms of F i (m, n-1)
. Recall that the items p 1 , . . . , p n in the previous subsection were ordered in an arbitrary, but fixed order. To express M (k) (m, v) in terms of F i (m, n -1), we order the items such that item k, with request probability p k , is the last item. Thus, we need to recompute the F i (m, n -1) values for each item k and we denote these values as F (k) i (m, n -1). A direct application of this result would therefore leads to an algorithm with a time complexity O(n 2 ). We further indicate how to reduce this to an algorithm in O(n 3/2 ).

Input: The vectors p and m Output:

M (m, v) for m ∈ V ≤m h 1 for i, j = 1 to h do 2 F j (e i , 1) = 1 {i=j} p i 1 ; 3 end 4 for k = 1 to n do 5 for r ∈ R min(k,m+1),h do 6 for i = 1 to h do 7 compute F i (r, k) via (6); 8 end 9 end 10 end 11 for m = (m 1 , . . . , m k ) ∈ V ≤m h do 12 M (m, 0) = F 1 (m + e 1 , n); 13 for v = 1 to k -1 do 14 M (m, v) = M (m, v -1) + mv F v+1 (m+e v+1 -ev ,n) Fv (m,n) ; 15 end 16 end Algorithm 1: Overall miss probabilities M (m, v) for all m ∈ V ≤m h . Theorem 3 The item k miss probability M (k) (m, v) is M (k) (m, v) = 1 + v i=1 p i k mi F (k) i (m,n-1) 1 + h i=1 p i k mi F (k) i (m,n-1) , if h i=v+1 m i < n and M (k) (m, v) = 0 otherwise.
Proof The hit probability of item k is identical to the steady state probability that item k is in some list i > v:

M (k) (m, v) = 1 - h i=v+1 mi j=1 c∈Cn(m),c(i,j)=k π(c).
Let E (k) (r, k) be defined as E(r, k) with the requirement that the items are ordered such that item k is in the last position. By (1), ( 3) and ( 4), we find

M (k) (m, v) = 1 - h i=v+1 p i k m i E (k) (m -e i , n -1) E(m, n) (7) = E (k) (m, n -1) + v i=1 p i k m i E (k) (m -e i , n -1) E (k) (m, n -1) + h i=1 p i k m i E (k) (m -e i , n -1)
.

If h i=v+1 m i ≥ n, E (k) (m, n -1)
and M (k) (m, v) = 0 (as all items fit in the cache), otherwise E (k) (m, n -1) differs from zero and the result follows from dividing the numerator and denominator by E (k) (m, n -1).

Note that p k has to be the last item in the order when computing the F (k) i (r, n-1) values based on Theorem 2, thus for each k we must use a different order. However, it is also clear that if we only change the order of the last s items, the values of F i (r, n -s) do not change.

To take advantage of this observation, we partition the set {1, . . . , n} of items into √ n sets S 1 , . . . , S √ n each holding √ n items (for ease of presentation we assume that n is a square). To compute the hitting probabilities of the item k belonging to set S j , we fix the order such that all the items not belonging to S j appear first (in an arbitrary fixed order), followed by an arbitrary order of items of S j with k as the last item. Thus, the computation of the F i (r, n -√ n) values, with r i ∈ {0, 1, . . . , m} and i r i ≤ m, is identical for all the items belonging to S j and takes O(nh 2 m h /h!) time, while computing the

F i (m, n -1) values from the F i (r, n - √ n) values takes O( √ nh 2 m h /h!)
time for each item in S j . This results in an overall time complexity of

√ n • O( nh 2 m h h! ) + √ n • O( √ nh 2 m h h! ) = O( n 3/2 h 2 m h h! ),
which is a significant gain over O(n 2 h 2 m h /h!) if the number of items n is large.

For h = 1 we have

H (k) (m, 0) = p k m/(p k m + F (k)
1 (m, n -1)) and the above algorithm to compute the per item hit probabilities has a time complexity of O(mn 3/2 ). An efficient algorithm to compute the per item hit probabilities of the RANDOM and FIFO scheme appears to be novel as [START_REF] Fagin | Efficient calculation of expected miss ratios in the independent reference model[END_REF] only considered the overall hit probabilities.

Theorem 4 For any m, under the algorithms FIFO(m, v) and RAND(m, v), p k > p implies that M (k) (m, v) < M ( ) (m, v), that is, more popular items have lower miss probabilities.

Proof The proof is a generalization of [37, Lemma 5] which established the same result for the CLIMB algorithm, that is, when m 1 = . . . = m h = 1 and v = 0. Due to [START_REF] Breslau | Web caching and Zipf-like distributions: Evidence and implications[END_REF],

M (k) (m) < M ( ) (m) is equivalent to h i=v+1 p i m i E ( ) (m -e i , n -1) - h i=v+1 p i k m i E (k) (m -e i , n -1) < 0,
If we order the first n -1 entries in both cases such that items k and are in the last two positions and we use Equation ( 4), the above rewrites as

h i=v+1 p i m i E(m -e i , n -2) + h j=1 p j k (m j -1 {i=j} )E(m -e i -e j , n -2) - h i=v+1 p i k m i E(m -e i , n -2) + h j=1 p j (m j -1 {i=j} )E(m -e i -e j , n -2) = h i=v+1 (p i -p i k )m i E(m -e i , n -2),
which is negative as p k > p .

Upper and lower bounds on the overall miss probability

In the previous subsections we developed fast algorithms to compute the overall and per item miss probabilities of the FIFO(m, v) and RAND(m, v) algorithm.

In this section we present a lower and upper bound on the overall miss probability when v = 0. Compared to Algorithm 1, that leads to an algorithm that is exponential in h, these bounds can be computed in a O(mn) time (linear in the number of items times the cache size). The upper bound coincides with the miss probability of the original FIFO and RANDOM schemes. This means that using two or more lists always decrease the steady-state miss probability compared to using only one list (i.e., RANDOM or FIFO).

Theorem 5

The miss ratio M (m, 0) of the FIFO(m, 0) and RAND(m, 0) algorithm is upper bounded by

M (m, 0) ≤ F 1 ((m + 1)e 1 , n) = M FIFO (m),
and lower bounded by

F 1 (e 1 +me h , n) = x∈Cn(m) m j=1 p h xj (1 - m j=1 p xj ) x∈Cn(m) m j=1 p h xj with m = h i=1 m i .
These bounds can be computed in O(mn) time.

To establish the lower and upper bounds in Theorem 5 we rely on a Lemma of [START_REF] Van Den Berg | LRU is better than FIFO under the independent reference model[END_REF] based on the FKG inequality [START_REF] Fortuin | Correlation inequalities on some partially ordered sets[END_REF].

We order the items such that f ) is increasing. Further, we state that f is permutation invariant if its value is independent of the order of its arguments x 1 , . . . , x m .

p 1 ≤ p 2 ≤ . . . ≤ p n . For x, y ∈ C n (m) let µ(x) = p x1 p x2 . . . p xm > 0 and define x y if x i ≤ y i for i = 1, . . . , m. A function f from C n (m) to R is increasing if x y implies that f (x) ≤ f (y), f is decreasing if (-
Lemma 1 (Lemma of [START_REF] Van Den Berg | LRU is better than FIFO under the independent reference model[END_REF]) Let g be decreasing and permutation invariant on

C n (m). If f is increasing on C n (m), then x∈Cn(m) µ(x)f (x)g(x) y∈Cn(m) µ(y) ≤ x∈Cn(m) µ(x)f (x) y∈Cn(m) µ(y)g(y). If f is decreasing on C n (m), then x∈Cn(m) µ(x)f (x)g(x) y∈Cn(m) µ(y) ≥ x∈Cn(m) µ(x)f (x) y∈Cn(m) µ(y)g(y).
Proof (of Theorem 5) We start with the upper bound. Define the function g on C n (m) as

g(x) = 1 -p x1 -p x2 -. . . -p xm .
The function g is clearly decreasing and permutation invariant on C n (m). Let f (x) be defined as

f (x) = h i=1   mi j=1 p x(i,j)   i-1
.

where x(i, j) = x i-1 s=1 ms+j . Due to (1) and ( 2) we have

x∈Cn(m) µ(x)f (x)g(x) = Z(m)M (m), x∈Cn(m) µ(x)f (x) = Z(m), while y∈Cn(m) µ(y)g(y) = Z(m)M F IF O (m) = Z(m)F 1 ((m + 1)e 1 , n)
and

y∈Cn(m) µ(y) = Z(m).
As f is increasing, the upper bound therefore follows from the first inequality of Lemma 1.

For the lower bound define μ(x) = µ(x) h ≥ 0 and let x ∧ y = (min(x 1 , y 1 ), . . . , min(x m , y m )) and x∨y = (max(x 1 , y 1 ), . . . , max(x m , y m )), then μ(x)μ(y) = μ(x∧y)μ(x∨y) and μ is permutation invariant on C n (m). As a result, the proof of the Lemma in [START_REF] Van Den Berg | LRU is better than FIFO under the independent reference model[END_REF] can be repeated to show that Lemma 1 remains valid if µ is replaced by μ. The result now follows from the second inequality of Lemma 1 (with µ replaced by μ) by setting

f (x) = h i=1   mi j=1 p x(i,j)   i-h
, which is a decreasing function on C n (m) and noting that y∈Cn(m) μ(y)g(y)

y∈Cn(m) μ(y) = F 1 (e 1 + me h , n).

Theorem 2 implies that

F h (r h e h , k) = F h (r h e h , k -1) + p h k r h 1 + p h k (r h -1)1 {r h >1} F h ((r h -1)e h ,k-1)
, and

F 1 (e 1 + r h e h , k) = F 1 (e 1 + r h e h , k -1) + p h k r h F1(e1+(r h -1)e h ,k-1) F h (r h e h ,k-1) + p k 1 + p h k r h F h (r h e h ,k-1)
. This shows that the quantities F h and F 1 can be computed by induction on k and m.

CLIMB is not optimal

Theorem 5 shows that the RANDOM algorithm achieves the worst performance (i.e., the highest miss rate) for the class of RAND(m, 0) algorithms with i m i = m under the IRM model. Hence, it is tempting to conjecture that separating a list into two smaller lists improves the performance and that the CLIMB algorithm, that is, having m lists of size 1, achieves the lowest miss rate within this class. In [2, p135] an even stronger conjecture is presented that states that CLIMB is optimal under the IRM model for all finite-memory demand replacement algorithms. Table 1 shows that both conjectures are false. The popularity distribution is p = (49, 49, 49, 49, 7, 1, 1)/205 and the cache has a size i m i = 6. Table 1 lists the ten vectors m with i m i = 6 that achieve the lowest miss probability M (m, 0), together with their corresponding M (m, 0) value. For comparison, we also show the performance of RANDOM and LRU. This shows that CLIMB is not optimal. It further indicates that when fixing the number of lists h, the optimal choice for the length of each list is not necessarily setting m 1 = . . . = m h-1 = 1: for instance, m = (1, 1, 3, 1) is better than m = (1, 1, 1, 3). This demonstrates that another of the natural conjectures formulated in [2, p135] is also false.

Adding virtual lists does not always improve performance

As we will demonstrate in Section 6, separating a list into smaller lists or adding virtual lists that only store meta-data usually improve the hit rate under the IRM model. The previous example (Table 1) shows that separating a list into smaller lists does not always improve the performance. In Table 2, we also show that adding virtual lists can also decrease performance. We make use of the same popularity distribution p = (49, 49, 49, 49, 7, 1, 1)/205 and consider a cache of size i m i = 6. We compare the RANDOM policy (and CLIMB) with RANDOM plus one virtual list of size 1, one virtual list of size 2 and two virtual lists of size 1. In both cases, adding one virtual list decreases the miss probability but increasing the size of the first virtual list or adding a second virtual list increases the miss probability. Note that the increase of miss probability is very small and really depends on this specific example.

policy m M (m, v) RANDOM RAND((4), v = 0), 0.14094006 RAND((1,4), v = 1) 0.11139402 RAND((2,4), v = 1) 0.12823856 RAND((1,1,4), v = 2) 0.11389801 CLIMB RAND((1,1,1,1), v = 0), 0.08041107 RAND((1,1,1,1,1), v = 1) 0.06924691 RAND((2,1,1,1,1), v = 1) 0.07576347 RAND((1,1,1,1,1,1), v = 2) 0.07063632

Miss probability is not Schur concave

A related question is whether the miss probability is a Schur-concave2 function of the popularity distribution p = (p 1 , . . . , p n ) for the class of algorithms RAND(m, v). If the miss probability were Schur-concave, it would imply that putting more weight on the most popular items decreases the miss probability. The authors of [START_REF] Van Den Berg | Properties of the miss ratio for a 2-level storage model with LRU or FIFO replacement strategy and independent references[END_REF] proved that the miss probability of the RANDOM algorithm, i.e., when h = 1 and v = 0, is Schur-concave, which is almost immediate from [27, p80].

It is shown in the more recent paper [START_REF] Vanichpun | Comparing strength of locality of reference -popularity, majorization, and some folk theorems[END_REF] that the miss probability of the CLIMB algorithm is not a Schur-concave function of p by providing a simple counter-example with m = 3. We make use of the same example to demonstrate that a counter-example also exist for RAND(m, 0) with h = 2. We consider the popularity distributions p 1 = (0.45, 0.45, 0.05, 0.05) and p 2 = (.75, .15, 0.05, 0.05) (p(x 1 ) is majorized by p(x 2 )). For p 1 , the miss probability is M (1, 2) = 0.05835 while it is M (1, 2) = 0.05994 for p 2 . This implies that M (1, 2) is not a Schur-concave function of p.

Mean field approximation

In this section we develop an ODE approximation for the RAND(m, v) policy. We show that this approximation becomes exact as the number of items and the cache size tends to infinity. This approximation allows us to study fast and accurately the transient behavior of the RAND(m, v) algorithm. We use it to compute the time to fill an empty cache in Section 6. It can also be used to obtain a fast approximation of the steady-state miss probability, when the cache size or the number of lists make Algorithm 1 too time consuming.

k H 0 (t) m 1 p k H 1 (t) m 2 p k H 2 (t) m 3 p k H h-1 (t) m h
Fig. 1 Evolution of the list in which item k is. When p k is small and the m i s are large, the state of one item becomes independent of the hit rate in each box and its behavior can be approximated by a time-inhomogeneous continuous-time Markov chain. This is the mean-field approximation.

Derivation of the equations and intuition

At a given time step t, item k is either part of some list i ∈ {1, . . . , h} or is not in any of the h lists. If an item is not in any of the h lists, we say that it is part of list 0. For an item k ∈ {1 . . . n} and a list i ∈ {0 . . . h}, we define the random variables X k,i (t), where X k,i (t) equals 1 if the item k is part of list i at time t and 0 otherwise. The probability that item k is in list i at time

t is E [X k,i (t)].
Our mean-field approximation of the RAND(m, v) algorithm boils down to assuming that the evolution of two items is independent of each other. We approximate E [X k,i (t)] by a deterministic quantity x k,i (t). The initial conditions of the ODE are x k,i (0) = 1 if the item k is in the ith list of the cache at time t = 0 and 0 otherwise. Let (x k,i (t)) k,i be the unique3 solution of the following set of ODEs, for k ∈ {1 . . . n}, i ∈ {1 . . . h}:

ẋk,i (t) = p k x k,i-1 (t) - j p j x j,i-1 (t) x k,i (t) m i + 1 {i<h} j p j x j,i (t) x k,i+1 (t) m i+1 -p k x k,i (t) , (8)
where 1 {i<h} is equal to 1 if i < h and 0 otherwise. This equation can be understood as follows. Assume that item k is in list i ∈ {0 . . . h -1} at time t. With probability p k , item k is requested and moves to list i + 1. With probability H i-1 (t) = j p j X j,i-1 (t), an item from list i -1 is requested and is exchanged with an item picked at random from list i. This item is item k with probability 1/m i . Hence, with probability H i-1 (t)/m i , item k moves to list i -1. If the list in which item k is and the variables H i (t) were independent, the behavior of item k would be described by a Markov chain whose transition matrix is represented in Figure 1.

If the probability p k is small and the list sizes m i , for i = 1, . . . , h, are large, this Markov chain is well approximated by a continuous time Markov chain. If all items evolve independently, this leads to our mean-field approximation given by Equation [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF].

In the next section, we establish a bound -Theorem 6 -that guarantees that, as the cache size grows, the transient hit probability can indeed be described by the ODE [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF]. This bound is valid regardless of the probability distribution (p i ). A more classical approach to obtain a convergence result would be to assume that items can be clustered into a finite number of classes and to let the number of items per class go to infinity. One could then use classical mean-field results to prove convergence [START_REF] Benaïm | A class of mean field interaction models for computer and communication systems[END_REF][START_REF] Kurtz | Approximation of population processes[END_REF][START_REF] Boudec | The stationary behaviour of fluid limits of reversible processes is concentrated on stationary points[END_REF]. This is the approach taken in [START_REF] Tsukada | Fluid limit analysis of FIFO and RR caching for independent reference models[END_REF]. Our approach is to relax the assumption of a finite number of classes with an infinite number of items per class. A drawback of our approach is that we can no longer rely on classical mean-field results and a new proof is therefore required. Yet, we believe that the cluster assumption is not a natural assumption for many mean-field models. Our approach shows that it is possible to obtain convergence results without assuming that clusters exist, which makes the results more widely applicable. It could be generalized to other mean-field models for which the cluster assumption is not realistic.

Proof of the validity of the approximation

Let H i (t) = n k=1 p k X k,i (t) be the sum of the popularities of the items that are part of the ith list of the cache at time t and H 0 (t) = 1 -h i=1 H i (t) be the miss probability at time t when v = 0. Let δ i (t) = k p k x k,i (t), where x k,i (t) is the unique solution of ODE ( 8), with initial conditions x k,i (0) = X k,i (0). Theorem 6 For any T > 0, there exists a constant C > 0 that depends on T such that, for any probability distribution over n items and list sizes m 1 . . . m h , we have:

E sup t∈{0...τ },i∈{0...h} |H i (t)-δ i (t)| ≤ C max 1≤k≤1 p k + max 0≤i≤h 1 m i ,
where τ := T /(max n k=1 p k + max h i=0 1 mi ) . In particular, Theorem 6 implies that the ODE approximation becomes exact as the cache size goes to infinity and the probability of each item goes to 0. This results can be seen as a generalization of [START_REF] Tsukada | Fluid limit analysis of FIFO and RR caching for independent reference models[END_REF] for two reasons. First, [START_REF] Tsukada | Fluid limit analysis of FIFO and RR caching for independent reference models[END_REF] only considers the RANDOM policy, that is, RAND(m, v) with h = 1. More importantly, [START_REF] Tsukada | Fluid limit analysis of FIFO and RR caching for independent reference models[END_REF] assumed that there were a finite number of classes of items with an infinite number of items per class. Our results is more general as we assume any distribution for p.

In fact, we believe that this result can also be extended to show that the ODE approximation becomes exact as the caches size goes to infinity, even if the probability of some items do not go to 0 (as it is the case for a Zipf distribution with α > 1). Assume that item k has a probability p k 1/m h . In such a case, as shown of Figure 1, the item k will quickly enter list h by having been hit multiple times, but will only exit list h with probability O(1/m h ) p k . We believe a result similar to Theorem 6 can therefore be obtained by separating the behavior of the popular and non-popular items.

Proof Let a = max k p k and b = max i 1/m i . Recall that X k,i (t) is equal to 1 if item k is in the ith list of the cache at time t and 0 otherwise. For any α ∈ Z + , and i ∈ {0 . . . h}, we define

H i,α (t) = a 1-α k (p k ) α X k,i (t).
Let H be the set of infinite vectors (δ i,α ) i∈{0...h},α∈{1,2... } where δ

i,α = a 1-α k (p k ) α x k,i for some (x k,i ) k,i such that sup i,k |x k,i | < ∞.
We equip H with the ∞ norm: h ∞ = sup i,α |h| and define H ≤1 the set of h∈H such that h ∞ ≤1.

We define the function f : H → H by, for all δ ∈ H:

f i,α (δ) = aδ i-1,α+1 (t) - δ i-1,1 (t)δ i,α (t) m i (9) + 1 {i<h} δ i,1 (t)δ i+1,α (t) m i+1 -aδ i,α+1 (t) ,
where 1 {i<h} equals 1 if i < h and 0 otherwise.

To prove the result we rely on the following lemma, the proof of which is postponed to Appendix A.

Lemma 2 Let (F t ) be the filtration associated with process of the (X k,i (t)) k,i , then:

(i) f (H(t)) is the average variation of H(t): E [H(t + 1) -H(t)|F t ] = f (H(t)) ( 10
)
(ii) the second moment is bounded:

E H(t + 1) -H(t) 2 ∞ |F t ≤ 2a 2
(iii) there exists a constant L independent of the p k s and the m i s such that the function f is Lipschitz-continuous of constant L(a + b) on H ≤1 , where a = max k p k and b = max i 1/m i . (iv) If x k,i (t) is the unique solution of ODE [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF], with initial conditions x k,i (0) = X k,i (0), then the infinite vector δ, defined by δ i,α (t) = a 1-α k (p k ) α x k,i (t) is the unique solution of δ = f (δ), that is:

δ(t) = H(0) + t 0 f (δ(s))ds.
Let H denote the continuous function equal to H(t) when t ∈ Z + and linear between t and t + 1. A straightforward computation shows that for all t ∈ Z + : H(t) ∈ H ≤1 and that H ≤1 is convex. Hence, for all t > 0:

H(t) ∈ H ≤1 . Let M (t) := t-1 s=0 H(s + 1) -H(s) -f (H(s)).
We have

H(t) = H(0) + t-1 s=0 f (H(s)) + M (t) = H(0) + t s=0 f (H( s ))ds + M (t) = H(0) + t s=0 f ( H(s))ds + M (t) + t 0 f (H( s )) -f ( H(s)) ds. ( 11
)
Equation ( 9) implies that for h ∈ H ≤1 , f (h) ∞ ≤ 2(a + b). As a result we get

H( s ) -H(s) ∞ ≤ 2(a + b)( s -s), which by Lemma 2(iii) implies that t s=0 f (H( s )) -f ( H(s)) ∞ ds ≤ tL(a + b) 1 0 2(a + b)sds = L(a + b) 2 t.
Combined with [START_REF] Fofack | Analysis of TTL-based cache networks[END_REF] and Lemma 2(iv), for t < τ , this shows that H(t) -δ(t) ∞ is less than

t 0 f ( H(s))-f (δ(s)) ∞ ds + L(a + b) 2 t + sup t≤τ M (t) ∞ ,
which, by Lemma 2(iii) and Grönwall's lemma implies that sup t≤τ H(t) -δ(t) ∞ is less than

L(a + b) 2 τ + sup t≤τ M (t) ∞ exp(L(a + b)τ ) (12)
Moreover, by Lemma 2(ii), we have E M (τ )

2 ∞ ≤ 2a 2 τ . By Lemma 2(i), M (t) is a martingale. Therefore, this implies that E sup t≤τ M (t) ∞ ≤ a √ 2τ ≤ (a + b) √ 2τ .
Replacing τ by T /(a + b), Equation ( 12) is smaller than:

(LT (a + b) + √ a + b √ 2T exp(LT ). By construction, a + b ≤ 2, which implies that a + b ≤ √ 2 √ a + b. Thus, setting C = √ 2(LT + √ T ) exp(LT )
gives the result.

Steady-state behavior

Theorem 6 justifies the fact that the ODE is an approximation of the transient behavior of the hit probability of the original system. We now use this approximation to obtain a fixed-point equation for the steady-state hit probabilities. When h = 1 this equation is identical to the one introduced in [START_REF] Dan | An approximate analysis of the LRU and FIFO buffer replacement schemes[END_REF] for FIFO and used in [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] for the RANDOM algorithm.

The next theorem shows that the mean field approximation of our system, given by the ODE (8) has a unique fixed point. As indicated by [START_REF] Benaïm | A class of mean field interaction models for computer and communication systems[END_REF], having a unique fixed-point is not, in general, a sufficient condition to show that the steady-state of the stochastic system concentrates on this point. In our case due to Corollary 1 the stochastic process of RAND(m, v) is reversible and for reversible processes that converge to an ODE [START_REF] Boudec | The stationary behaviour of fluid limits of reversible processes is concentrated on stationary points[END_REF] showed that the stationary measure of a reversible process concentrates on the fixed point of the ODE. Although we cannot directly apply the result of [START_REF] Boudec | The stationary behaviour of fluid limits of reversible processes is concentrated on stationary points[END_REF] to our setting, we expect that a similar argument can be used. As RAND(m, v) and FIFO(m, v) have the same steady-state hit probability, this fixed-point provides a very efficient numerical method to compute the steady-state performance of both policies.

Theorem 7

The mean-field model (8) has a unique fixed point. For this fixed point, the probability that item k is part of list i, for k = 1, . . . , n and i = 0, . . . , h, is given by

x k,i = p i k z i 1 + h j=1 p j k z j
, where z = (z 1 , . . . , z h ) is the unique solution of the equation

n k=1 p i k z i 1 + h j=1 p j k z j = m i . (13)
Proof Let (x k,i ) k,i be a fixed point of the ODE [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF] and let H i-1 = n j=1 p j x j,i-1 be the corresponding hit probability in box i -1. The fixed-point equations are:

p k x k,i-1 - H i-1 m i x k,i + 1 {i<h} H i m i+1 x k,i+1 -p k x k,i = 0
As these equations correspond to the fixed-point equation of the birth-and-death process described in Figure 1, we have

x k,i = p i k m 1 . . . m i H 0 . . . H i-1 x k,0 Let z i = i-1 j=0 m j+1 /H j for i ∈ {1 . . . h}. By using that h i=0 x k,i = 1, this implies that x k,i = p i k z i /(1 + h j=1 p j k z j ). By using that n k=1 x k,i = m i , this yields m i = n k=1 x k,i = n k=1 p i k z i 1 + h j=1 p j k z j (14)
We now show that Equation ( 14) has a unique solution. For a vector z = (z 1 . . . z h ) ∈ (R + ) h , we define D i (z), for i = 1, . . . , h, by

D i (z) = n k=1 p i k z i 1 + h j=1 p j k z j = n k=1 p i k 1/z i + h j=1 p j k z j /z i
The function D i (z) is increasing in z i and decreasing in z j for j = i. For a vector z = (z 1 , . . . , z h ), i ∈ {1, . . . , h} and y > 0, we denote z -i (y) the vector whose coordinates are all equal to the ones of z except for the ith one which is equal to y. D i (z -i (y)) is increasing in y. Hence, the equation D i (z -i (y)) = m i has a unique solution that we denote G i (z) (it should be clear that, by definition, G i (z) does not depend on z i ). Moreover, as D j (z) is decreasing in z j for j = i, G i (z) is increasing in z j , for all j = i. This shows that G is increasing (componentwise) in z: if for all i, z i ≤ z i , then for all i:

G i (z) ≤ G i (z ).
We define the sequence z t by z 0 = (0, . . . , 0) and z t+1 = G(z t ) for t ≥ 0. As G(z) is componentwise increasing in z, the sequence z t is increasing. Moreover, by using that z = z t -i (z t i ) and

m i = D i (z t -i (z t+1 i
)), we have:

D i (z t ) = D i (z t -i (z t i )) ≤ D i (z t -i (z t+1 i )) = m i
where the inequality from the fact that z t i is increasing in t and D i (z) is increasing in z i . This shows for all t:

n - h i=1 m i ≤ n - h i=1 D i (z t ) = n k=1 1 1 + h j=1 p j k z t j ,
which implies that the sequence z t is bounded. As this sequence is increasing, it converges to a fixed point of G. We now prove the uniqueness. Let λ > 1. If we multiply all coordinates of z by λ, the D(λz) becomes:

D i (λz) = n k=1 p i k z i λ (1 + h j=1 p j k z j λ) = n k=1 p i k z i (1/λ + h j=1 p j k z j ) > D i (z).
This implies that G i (λz) < λG i (z). The function G satisfies the assumptions of a standard interference function I of [START_REF] Yates | A framework for uplink power control in cellular radio systems. Selected Areas in Communications[END_REF], which means that it is positive, monotone and sub-homogeneous. By [START_REF] Yates | A framework for uplink power control in cellular radio systems. Selected Areas in Communications[END_REF]Theorem 2], this implies that the fixed point of G is unique and that the iterations z t+1 = G(z t ) converge, regardless of z 0 . This results can be proven by showing that x → G(exp(x)) is a contraction.

Numerical algorithm and validation

The proof of Theorem 7 is based on the construction of an iterative scheme z t+1 = G(z t ) that converges to the unique fixed point given by Equation [START_REF] Fricker | A versatile and accurate approximation for lru cache performance[END_REF]. This iteration provides an efficient method to compute the fixed-point, as it converges exponentially fast to the fixed point and each iteration takes O(nh) time, that is, is linear in the number of items times the number of lists. This is clearly a significant improvement over the O(nhm h /h!) time complexity of Algorithm 1, used to compute exact hit probabilities, especially for large cache size and/or a large number of lists.

In Tables 3 and4, we compare the steady-state miss probabilities given by the mean-field approximation with the exact values given by Algorithm 1 when v = 0. The popularity distribution follows a Zipf-like distribution of parameter 0.8 or 1.1. These tables contain the results for various values of m. We observe that, in all cases, the approximation is within 1% of the exact value. This holds even when the lists are small or with highly non-uniform distributions (Zipf with α > 1).

When the number of lists exceeds five, the execution time of Algorithm 1 becomes prohibitive (it grows as m h ). We therefore compare the mean-field model with values obtained by simulation for h = 10 and v ≥ 0 in Table 5. We show the results for various popularity models (Zipf 0.5 to Zipf 1.4) and diverse lists sizes: all lists have the same size (m i = 30), increasing sizes (m i = 10i or m = (10, . . . , 10, 50, . . . , 50)), varying (m i = 30 -(i -5) 2 ), decreasing sizes (m i 8(11 -i)) or alternating (m = (80, 8, 80, 8 . . . )). In all cases, the mean-field approximation was computed almost instantaneously on a regular laptop while the time to obtain our simulation results was several hours. The accuracy of the transient behavior of the ODE approximation is discussed in Section 6.1.

Numerical results and guidelines

In this section, we wish to formulate some guidelines on how to select the number of lists and the list sizes m 1 to m h . We first focus on the IRM model and study the trade-off between time to fill the cache and miss probability. We then explore traces of real data. distribution with α = 0.8, that is, p i = A/i α , where A is the normalizing constant. Furthermore, we also plotted the miss probability M(m, 0) of the RAND(m, 0) algorithm when m 1 = . . . = m h-1 = 1. The main conclusions are first that having more lists generally improves the performance4 . Second, these lower bounds appear to be very sharp under a Zipf-like workload (with α = 0.8 and n = 3000 items). Third, the figure demonstrates that there is little room for further reducing the miss probability by using more than h = 10 lists. Most of the gain can be obtained by implementing a limited number of lists. This observation will be confirmed further on using trace-based simulations.

In Figure 3 we study the impact of the size m 1 of the first list on the miss probability when h = 2, m = 300, n = 1000 and the popularity distribution p follows a Zipf-like distribution with α ranging from 0.5 to 1. As reported in [START_REF] Breslau | Web caching and Zipf-like distributions: Evidence and implications[END_REF], many traces corresponds to Zipf-like distribution with parameters α ∈ [.6, .9]. Our range of values α correspond to a super-set of these values. The figure indicates that there is no need to make the size m 1 of the first list extremely small in order to have a miss probability that is close to the lower bound. This is important as we will show next that small m 1 values make it harder for items that suddenly become popular to enter the cache.

Influence of the first list size

To this end, we study the transient behavior of the hit probability under the IRM model starting from an empty cache by making use of the mean field model (with H 0 (t) = 1). We also validate the accuracy of the mean field model to capture the transient regime by plotting the corresponding simulation results (averaged over 5 or 25 runs to reduce the noise). Figure 4 shows the transient behavior of the hit probability as a function of the number of requests received under the IRM model with a Zipf-like popularity distribution with parameters 5 α = 0.5 for h = 2 lists, m = 200, n = 1000 and various values for the size of the first list m 1 . The figure indicates that the mean field model and the simulation based results are in perfect agreement. Further, as expected, it demonstrates that while decreasing m 1 improves the steady state hit probability (which is in agreement with Figure 3), the time to reach the steady state increases as a function of m 1 . Our conclusion is that the time to fill the cache depends mainly on the size of the first list. Assigning a sufficient portion of the overall cache size, to the first list gives a significant increase in the hit probability while having a limited impact on the cache reactivity.

To obtain more insights on the time to fill the cache, let us focus on the case when p is a uniform distribution. In this case, the mean-field approximation [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF] simplifies to

ẋi (t) = x i-1 (t) n - x i-1 (t)x i (t) m i + 1 {i<h} x i (t)x i+1 (t) m i+1 - x i (t) n .
When m 1 n, items enter the first list at rate 1/n and leave it at rate 1/m 1 . This leads to x 1 (t) ≈ (m 1 /n)(1 -exp(-t/m 1 )): the time to fill the first list is proportional to m 1 . When list i contains x ≈ m 1 items, these items jump to the next list at rate x/n ≈ m 1 /n. This suggests that the time to fill the lists 2 to h 5 The choice of α = 0.5 is arbitrary and similar results can be observed with larger α.

is of the order

n(m 2 /m 1 + m 3 /m 2 + • • • + m h /m h-1 ). Hence, a natural choice is to set m 1 = m 2 = • • • = m h , which results in a total time to fill the cache of m 1 + n(m -m 1 )/m 1 .
Although this analysis only works for a uniform distribution, we show in Figure 5 that the impact of the parameter α of the Zipf-like popularity distribution p on time to reach the steady state hit probability is limited. This figure shows the hit probability as a function of the number of requests for n = 1000 items and m = (50, 150). Similarly, we depict the transient hit probability when m 1 = 40 for h = 2, 3 and 4 lists Figure 6. The main message of this figure is that the time to reach the steady state hit probability does not depend much on the list sizes m 2 to m h . Hence, instead of working with just two lists, one can improve the steady state hit probability by relying on multiple lists without affecting the reactivity of the cache when the size of each of the lists is at least as large as the first one.

Influence of the presence of meta-data lists

Let us now study the impact of adding additional lists that only store meta data to a cache. For this purpose consider the case where n = 1000, α = 0.5 and m i = 40 for all i. Figure 7 demonstrates what happens to the time to fill the cache when h = 5 + v, for v = 0, . . . , 3, meaning the cache can store 200 items in all cases and increasing v by one adds another list of size 50 that contains meta data only. This example demonstrates that adding extra lists with meta data to a cache typically improves the long run hit probability under the IRM model and the additional gain obtained from adding another list decreases as more lists are added. However increasing v also an increases in the time needed to fill the cache. As such it seems best not to add too many lists with meta data as this makes the cache replacement policy very inflexible when faced with dynamic workloads.

In the previous example all lists were of size 40. As storing only meta data requires less storage capacity than storing the actual items, one can easily make use of larger m 1 to m v values at limited cost. Figure 8 considers the same example as before with v = 1 and studies the impact of m 1 , the size of the list with meta data only. It illustrates that increasing m 1 typically increases the time to fill the cache while it reduces the long run hit probability (by a very small fraction for small m 1 values).

Our conclusion is that the addition of meta-data lists leads to better performance but slower reactivity. A good balance between the long run hit probability and the cache responsiveness therefore appears to exist in setting the meta data lists sizes equal to the size of the lists that contain the items stored in the cache. There is one meta-data list of size m 1 ∈ {20 . . . 640}. Simulation is based on 25 runs.

Trace-driven simulations

To validate the insights obtained by studying the IRM model, we perform tracebased simulations using a publicly available YouTube trace that was collected at a campus network during a 14 day period in 2008 [START_REF] Zink | Characteristics of YouTube network traffic at a campus network -measurements, models, and implications[END_REF]Trace T5]. This trace contains a total of 611,968 requests for 303,331 different videos, meaning that, if we start with an initially empty cache, the miss probability is at least 303, 331/611, 968 ≈ 0.496 even if the cache has infinite capacity. Further, about 65.9% of these videos were requested only once during the trace, meaning the request pattern is quite different from the IRM model. We selected this particular trace among the ones discussed in [START_REF] Zink | Characteristics of YouTube network traffic at a campus network -measurements, models, and implications[END_REF] as it is by far the longest one.

We developed a simulation program for the FIFO(m, 0), RAND(m, 0), strict FIFO(m, 0) and LRU(m, 0) algorithms discussed in Section 3, for the scenario move away from the back of the cache. RAND(m, 0) does not exhibit such a behavior as being at the front or back in the first list makes no difference.

Conclusion

In this paper, we studied a family of cache replacement algorithms FIFO(m, v) and RAND(m, v). We provided close-form results for the steady-state probabilities under the IRM model, as well as a polynomial algorithm to compute the steady-state miss probabilities. We further developed a mean-field approximation that provides a fast and accurate method for approximating the miss probabilities. We used this approximation to study the transient behavior of the cache and to provide guidelines of how to tune the number of lists and the list sizes. This suggests that the first few lists should be large enough and have equal sizes. By using these insights, we verify on real traces of cache requests that these policies perform well and can outperform other classical heuristics such as FIFO or LRU. We also studied the used of virtual lists, suggested in [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] and that only store meta-data. We found that the number of virtual lists should be limited (one or two) and that these virutal lists should be similar in size to the lists containing the actual items. Our trace-based experiments also show that when many items are requested a small number of times, having virtual lists is detrimental.

A direct extension of this work would be to consider a network of caches, by using the model of [START_REF] Berger | Exact analysis of TTL cache networks[END_REF][START_REF] Fofack | Analysis of TTL-based cache networks[END_REF]. We also aim at obtaining close-form expression for the steady-state probabilities or the time to fill the cache when the distribution is Zipf(α) or develop an approximation for studying the transient behavior of FIFO(m, v). Considering more general request models than IRM like MAP arrival or shot-noise is also important. For MAP arrivals, the steady-state results for LRU(m, v) obtained in [START_REF] Gast | Asymptotically Exact TTL-Approximations of the Cache Replacement Algorithms LRU(m) and h-LRU[END_REF] could be generalized to the case of RAND(m, v) and FIFO(m, v).

Acknowledgment

This work is partially supported by the EU project QUANTICOL, 600708.

A Proof of Lemma 2

Let α ∈ Z + and i ∈ {1 . . . h}. Two types of events can modify the value of H i,α (t):

-If at time t, the item k is requested and is in list i -1, then, it is exchanged with another item j that is chosen uniformly at random from list i. This occurs with probability X k,i-1 (t)X j,i (t)p k /m i and modifies H i,α (t) in H i,α (t) + a 1-α (p α k -p α j ).

The average variation of H i,α due to these events is:

k,j
X k,i-1 (t)X j,i (t)a 1-α (p α k -p α j ) where the last line comes from the fact that j X j,i (t) = m i and k p k X k,i-1 (t) = H i-1,1 (t).

p k m i = k X k,i-1 (t)a
-If i < h and if at time t, the item k is in cache i and is hit, then, it is exchanged with another item j that is chosen uniformly at random from cache i + 1. This occurs with probability X k,i (t)X j,i+1 (t)p k /m i+1 and modify H i,α (t) in H i,α (t) + a 1-α (-p α k + p α j ). This second type of events leads to an average variation of aH i,α+1 (t)+(H i,1 (t)H i+1,α (t))/m i+1 if i < h.

Summing the two terms implies (i): for all i, α, we have E [H i,α (t + 1) -H i,α (t)|Ft] = f i,α (H(t)).

We now show that the second moment of the variation of H is bounded. For all k, j 0 ≤ p k , p j ≤ a, which implies a 2-2α (p α k -p α j ) 2 ≤ a 2 . Therefore, by using the same two types of events as for the proof of (i), we have The points (iii) and (iv) are easier as f is a sum of two terms: the first one is Lipschitzcontinuous of constant a and the second is a second order polynomial function of h divided by m i , which is therefore Lipschitz-continuous of constant C/m i on all bounded sub-space of H. Moreover, by plugging (8) into [START_REF] Fagin | Efficient calculation of expected miss ratios in the independent reference model[END_REF], we find that δ is the solution of δ = f (δ).

E sup α (H i,α (t+1)-H i,α (t)) 2 |Ft = k,j X k,i-1 (t)X j,i (t) sup α a 2-2α (p α k -p α j ) 2 p k m i + k,j X k,i (t)X j,i+1 (

  p

Fig. 2

 2 Fig. 2 Lower bounds for h = 2, 3, 5, 10 and ∞ and the miss rate M(m, 0) with m 1 = . . . = m h-1 = 1 for h = 2, 3, 5 and 10 as a function of the cache size m, with v = 0, n = 3000 and α = 0.8.

Figure 2

 2 Figure2depicts the lower bounds established in Theorem 5 for various h values as a function of the cache size m when n = 3000 and p follows a Zipf-like distribution with α = 0.8, that is, p i = A/i α , where A is the normalizing constant. Furthermore, we also plotted the miss probability M(m, 0) of the RAND(m, 0) algorithm when m 1 = . . . = m h-1 = 1. The main conclusions are first that having more lists generally improves the performance 4 . Second, these lower bounds appear to be very sharp under a Zipf-like workload (with α = 0.8 and n = 3000 items). Third, the figure demonstrates that there is little room for further reducing the miss probability by using more than h = 10 lists. Most of the gain can be obtained by implementing a limited number of lists. This observation will be confirmed further on using trace-based simulations.

Fig. 3

 3 Fig. 3 Impact of parameter α of the Zipf-like distribution on the miss probability M (m 1 , m 2 ), with v = 0, n = 1000 and m = 300.

Fig. 4

 4 Fig.4Evolution of the hit probability starting from an empty cache with v = 0, n = 1000 and α = 0.5. Simulation is based on 25 runs.

Fig. 5

 5 Fig.5Evolution of the hit probability starting from empty cache with v = 0, n = 1000 and m = (50, 150). Simulation is based on 5 runs.

Fig. 6

 6 Fig.6Evolution of the hit probability starting from empty cache with v = 0, n = 1000 and α = 0.5. Simulation is based on 25 runs.

Fig. 7

 7 Fig. 7 Evolution of the hit probability starting from empty cache with h = v + 5, n = 1000 and α = 0.5. Simulation is based on 25 runs.

Fig. 8

 8 Fig.8Evolution of the hit probability starting from empty cache with n = 1000 and α = 0.5. There is one meta-data list of size m 1 ∈ {20 . . . 640}. Simulation is based on 25 runs.

Fig. 9 Fig. 10

 910 Fig.9Trace-based hit probability of RAND(m, 0) with m i = (m-m 1 )/(h-1) for i = 2, . . . , h and i m i = 5000.

Fig. 11

 11 Fig.11Trace-based hit probability of FIFO(m, 0) and LRU(m, 0) with m i = (m -m 1 )/(h -1) for i = 2, . . . , h and i m i = 5000.

Table 1

 1 CLIMB is not optimal for IRM model with v = 0: p = (49, 49, 49, 49, 7, 1, 1)/205 and m = 6.

	policy	m	M (m, 0) lower bound
	Optimal	RAND(1,1,4)	0.005284 0.004925
		RAND(1,1,3,1)	0.005299 0.004884
		RAND(1,1,2,2)	0.005317 0.004884
		RAND(1,1,2,1,1)	0.005321 0.004879
		RAND(1,1,1,3)	0.005338 0.004884
		RAND(1,1,1,2,1)	0.005343 0.004879
		RAND(1,1,1,1,2)	0.005347 0.004879
	CLIMB	RAND(1,1,1,1,1,1) 0.005348 0.004878
		RAND(1,2,3)	0.005428 0.004925
		RAND(1,2,2,1)	0.005439 0.004884
	LRU	LRU(6)	0.005880	-
	RANDOM RAND(6)	0.015350 0.015350

Table 2

 2 Adding virtual lists does not always improve performance for the IRM model with p = (49, 49, 49, 49, 7, 1, 1)/205) and m = 4.

Table 3

 3 Mean field model validation of the long run miss probability for v = 0 and h = 2 with Zipf-like popularity distributions.

	α	n	m 1	m 2	exact	mean field
	0.8	300	2	98	0.3466	0.3470
			30	70	0.3608	0.3612
			98	2	0.4239	0.4245
	0.8 3000	20	980 0.3034	0.3035
			300 700 0.3159	0.3160
			980	20	0.3723	0.3724
	1.1	300	2	98	0.1719	0.1722
			30	70	0.1832	0.1835
			98	2	0.2362	0.2367
	1.1 3000	20	980 0.1110	0.1110
			300 700 0.1183	0.1183
			980	20	0.1531	0.1531

Table 4

 4 Mean field model validation of the long run miss probability for v = 0, h = 3 and h = 4 with n = 300 and a Zipf-like popularity distribution with α = 0.8.

		m 1	m 2	m 3	m 4	exact	mean field
		2	2	96	-	0.3166	0.3169
		10	30	60	-	0.3296	0.3299
		20	2	78	-	0.3273	0.3276
		90	8	2	-	0.4094	0.4100
		1	4	10	85	0.3039	0.3041
		5	15	25	55	0.3136	0.3139
		25	25	25	25	0.3345	0.3348
		60	2	2	36	0.3514	0.3517
	α		m i		v	simul	mean field
	0.5		30		0	.50113 ± .00011	.50116
					3	.57850 ± .00008	.57848
	0.75	10 + 40 • 1 {i>5}	0	.32307 ± .00002	.32310
					6	.41049 ± .00005	.41053
	0.8		10i		0	.15836 ± .00003	.15838
					1	.16209 ± .00003	.16212
	0.9	30 -(i -5) 2	0	.29437 ± .00003	.29439
					2	.31541 ± .00003	.31546
	1.1		8(11 -i)		0	.09412 ± .00007	.09417
					7	.35301 ± .00008	.35351
	1.4	8 + 72 • 1 {i is odd}	0	.02504 ± .00001	.02504
					4	.04057 ± .00001	.04057

Table 5

 5 Mean field model validation of the long run miss probability for h = 10 lists with n = 1000 and a Zipf-like popularity distribution based on 5 simulation runs.

  t) sup

				α	a 2-2α (p α j -p α k ) 2 p k m i+1
	≤	k,j	X k,i-1 (t)X j,i (t)a 2 p k m i	+	k,j	X k,i (t)X j,i+1 (t)	a 2 p k m i+1

= (H

i-1,1 (t) + H i,1 (t))a 2

This shows that

E H(t + 1) -H(t) 2 ∞ |Ft = E sup i,α (H i,α (t + 1) -H i,α (t)) 2 |Ft ≤ E i sup α (H i,α (t + 1) -H i,α (t)) 2 |Ft ≤ i (H i-1,1 (t) + H i,1 (t))a 2 ≤ 2a 2 .

We use the notation 1 {i=j} equals 1 if i = j and 0 otherwise.

A function is Schur-concave if p majorizes p , implies that the miss probability is lower for p than for p .

It should be clear that this ODE is Lipschitz-continuous and hence has a unique solution. Moreover, with the initial conditions indicated, the solution of the ODE satisfy that, for all time t: n k=1 x k,i (t) = m i and h i=0 x k,i (t) = 1.

Although adding too many lists can be detrimental for the performance for some very specific and skewed popularity distribution (as shown in Section 4.5).

where the campus network relies on a single proxy cache. As only HTML-based control messages are available for trace T5, we have no information on the size of the requested videos. We therefore assumed (for all the policies) that the cache size is expressed in the number of videos m that can be stored in the proxy cache (the average size of a video should be a few Mbyte). This should not impact the results much if the correlation between video popularity and video size is small.

In all figures of this section, we only report results for v = 0. The reason is that, for this particular trace, the performance when v ≥ 1 is worse. Indeed, for this particular trace, only 200k items were requested twice, 160k three times and 130k four times. This shows that by having a v = 1, 2 or 3, one cannot achieve a hit rate above 0.3354, 0.2580 and 0.2122, as the first v + 1 requests for any video cause a miss even if all the lists have infinite capacity. Just to state one number for v = 1: the LRU(m, 1) algorithm with h = 6, v = 1, m 1 = ∞ and m i = 1000 for i > 1, achieves a hit rate of 0.2329 which is well below the hit rates reported further on for v = 0.

When comparing the different replacement policies, we varied the size of the first list m 1 and divided the remaining cache capacity equally among the remaining h -1 lists. Figures 9 to 11 depict the hit probability as a function of the cache capacity assigned to list 2 to h when the total cache capacity is m = 5000 videos and we make use of h = 2, 3 or 5 lists. The following insights are provided by these figures. While the FIFO(m, 0) and RAND(m, 0) algorithm perform alike under the IRM model, RAND(m, 0) results in a lower hit probability when using real data, as expected. The strict FIFO(m, 0) and FIFO(m, 0) algorithm do however perform very similar, especially if enough capacity is assigned to list 2 to h. The LRU(m, 0) algorithm does outperform FIFO(m, 0) when using two or three lists, but the gain becomes very limited when using h = 5 lists. We also note that FIFO(m, 0) clearly outperforms a pure LRU cache.

In all cases, the hit probability is maximal when about 30 to 60% of the cache capacity is assigned to the first list. It quickly deteriorates as the size of the first list becomes small. This observation is in line with the earlier observation that the time to fill the cache is larger for small values of m 1 , that make it harder to insert new items into the cache.

The increase in the hit probability as a function of the number of lists is the most pronounced when h is small, which is in agreement with earlier observations under IRM. In fact, further increasing the number of lists beyond 10 causes a decrease in the hit probability, mostly because the sizes of the lists 2 to h become small, making it harder to insert new items in the cache.

Both strict FIFO(m, 0) and FIFO(m, 0) exhibit a jump in the hit probability as soon as we add a second list, even if this list can only store a single item. For strict FIFO(m, 0) this can be easily understood as the second list allows an item that is hit repeatedly to move to the front of the cache. In particular, strict FIFO(m -1, 1, 0) behaves very similar to a pure LRU, that is known to outperform pure FIFO [START_REF] Van Den Berg | LRU is better than FIFO under the independent reference model[END_REF]. The same happens to a lesser extent for FIFO(m, 0), but items now move to a random position in the first list when being demoted. Still, on average it allows popular items that are in the back of the cache to