E Nardon

H Heumann

J F Artaud

J Bucalossi

D Douai

N Fedorczak

T Loarer

P Moreau

R Nouailletas

C Reux

F Saint-Laurent

P Tamain

Magnetic configuration and plasma start-up in the WEST tokamak

Introduction

This paper describes experimental findings regarding plasma inductive start-up [1] [2] in the first year of operation of the WEST tokamak [3]. The results are interpreted with the help of modelling and compared to criteria for a successful start-up from the literature [1] [4]. The focus here is on magnetic configuration aspects. Other aspects, in particular burn-through and runaway electron production, will be discussed in a future paper.

Magnetic field requirements for a successful inductive start-up

A successful inductive start-up begins with a breakdown followed by a rise of the plasma current I p . For this to happen, the poloidal magnetic field B p needs to fulfill a number of conditions [1] [4]. First, the breakdown requires a region of low B p (a 'field null region') in order for electrons to be accelerated by the toroidal electric field E for many turns before hitting the wall. A quantitative criterion established across many tokamaks is EL e f f > 70V [4], where L e f f = 0.25a e f f B t / < B p > is the effective field line connection length, with a e f f the minor radius of the field-null region and < B p > the averaged poloidal field at the null region boundary.

Then, the parallel current density j generated by the breakdown should be sufficient to create closed flux surfaces. Finally, plasma radial force balance requires the vertical field B Z to be ramped up in proportion to I p , and plasma positional stability requires the vertical field decay index n ≡ -(R/B Z )∂ B Z /∂ R to be both > 0 for vertical stability and < 3/2 for radial stability [5].

The route to a successful start-up in WEST WEST [3] is a modification of the Tore Supra tokamak based on adding two in-vessel coils (in red in Figure 1) in order to allow diverted configurations, and changing all plasma facing components from carbon to tungsten (W), including actively cooled W monoblocs for the divertor target in order to test the technology to be used in ITER. The divertor coils are inserted inside thick casings (in yellow in Figure 1) which constitute axisymmetric passive conducting structures (∼ 0.3mΩ each). In addition, two copper stabilizing "plates" (∼ 0.1mΩ each, in blue in Figure 1) were added in the upper and lower region of the vessel to increase the accessible elongation range. It is important to mention that start-up issues were most likely not due to bad settings but really to machine configuration. Indeed, start-up settings were carefully optimized with the FEEQS.M freeboundary equilibrium code [START_REF] Blum | Automating the design of tokamak experiment scenarios[END_REF] in "plasma-less, inverse time evolution" mode (accounting for the effect of the iron core).

Interpretative modelling method

In order to interprete experimental results, we reconstruct the magnetic field map with two different approaches: direct time evolution of Maxwell's equations with the above-mentioned FEEQS.M code [START_REF] Blum | Automating the design of tokamak experiment scenarios[END_REF], or identification based on magnetic mea-surements with the FREEBIE-ID code [START_REF] Artaud | [END_REF]. The two methods give results consistent with each other as well as with fast visible tangential camera images, as illustrated in Figure 2. FREEBIE-ID has the advantage of identifying the plasma current.

Analysis of experimental cases

We now analyze one case from each phase of operation, namely shots 50433 (2 plates), 50874

(1 plate) and 51898 (0 plate). In each case, a successful plasma breakdown was obtained and maintained for 50ms or more, but only in the last case did I p really take off. In the first two cases, over most of the plasma duration, the light pattern on fast camera images does not show signs of closed flux surfaces. Only for a very brief period of the order of 1ms are closed flux surfaces visible, and they seem to be lost due to a positional instability. According to the modelling, the breakdown criterion EL e f f > 70V [4] is fulfilled in all cases (although not with much margin for the 1 and 2 plates cases), consistently with experimental observations. The parallel current density j generated by the breakdown, as identified by FREEBIE-ID, is ∼ 10kA/m 2 . The magnetic field created by this j appears marginal to close flux surfaces in the 1 and 2 plates cases, again in agreement with observations (here it is worth mentioning that it took many shotto-shot adjustments to produce closed flux surfaces in the 1 and 2 plates cases). Finally, positional stability is addressed by Figure 3, which presents, for the three cases, the ∂ B Z /∂ R profile at the vessel midplane calculated by FEEQS.M near the time when closed flux surfaces are visible (plain lines). For the 2 plates case (black), a ∂ B Z /∂ R profile is also shown 20ms later (dashed line) to stress the fast temporal evolution for this case (the other two cases evolve much more slowly). Inserting an estimate of the necessary B Z for radial force balance [1] at I p = 10kA (which is an upper bound according to FREEBIE-ID), the above-mentioned stability criterion becomes -1mT/m < ∂ B Z /∂ R < 0, which is indicated by the green band in Figure 3. Clearly, only the 0 plate case (blue) fulfills this criterion over a significant region. Once again, this is consistent with fast camera observations of positional instabilities in the 1 and 2 plates cases. We note that KSTAR reported positional stability issues at start-up [START_REF] Kim | [END_REF].

Figure 1 :

 1 Figure 1: WEST vacuum vessel configuration

Figure 2 :

 2 Figure 2: FEEQS.M magnetic flux contours (white dashed lines) overlayed on a fast camera image for a start-up attempt in the 2 plates configuration (initial currents have been tweaked by ±100A in four of the coils in FEEQS.M to improve the match).

Figure 3 :

 3 Figure 3: Profile of ∂ B Z /∂ R at the vessel midplane for 3 start-up attempts (see text for details). The green band indicates roughly the positional stability window.

th EPS Conference on Plasma Physics O3.110

Discussion and conclusion

In conclusion, inductive start-up in WEST was hindered by the presence of toroidally continuous copper stabilizing plates inside the vessel. One message of this paper is therefore that the insertion of such structures in future machines should be considered with great caution.

As we saw, the plates did not prevent plasma breakdown but made the closure of flux surfaces difficult, and positional stability apparently impossible. It therefore seems that there was an increasing level of difficulty in meeting the breakdown, flux surface closure, and positional stability conditions. Simple estimates may "explain" this observation. A comparison between the three conditions can indeed be made by rewriting each of them in the form < B p > /a e f f < X.

The EL e f f > 70V breakdown condition implies < B p > /a e f f < 3 • 10 -3 EB t ≈ 11mT/m (for typical WEST values E = 1V/m and B t = 3.6T). Flux surfaces may close if the poloidal magnetic field generated by the plasma, ∼ µ 0 • j • a e f f /2, is larger than the vacuum field < B p >, i.e. if < B p > /a e f f < µ 0 • j/2 ≈ 6mT/m (taking j = 10kA/m 2 as suggested by FREEBIE-ID). Finally, if we consider that |∂ B Z /∂ R| ∼< B p > /a e f f , the stability condition at I p = 10kA implies

This hierarchy, although it is clear in WEST, is not universal but depends on the values of E, B t and j. Of these three quantities, j is obviously the most difficult one to estimate for future devices. During the first year of operation of WEST, j seemed to saturate during the breakdown phase at lower values than those stated in [1][2]. This may be related to poor machine conditioning. Future experiments (with improving machine conditions) and analysis may confirm this hypothesis.


Sharing Cache Resources among Content Providers:

A Utility-Based Approach Mostafa Dehghan, Weibo Chu, Philippe Nain, Don Towsley, Fellow, IEEE, and Zhi-Li Zhang, Fellow, IEEE Abstract-In this paper, we consider the problem of allocating cache resources among multiple content providers. The cache can be partitioned into slices and each partition can be dedicated to a particular content provider, or shared among a number of them. It is assumed that each partition employs the LRU policy for managing content. We propose utility-driven partitioning, where we associate with each content provider a utility that is a function of the hit rate observed by the content provider. We consider two scenarios: i) content providers serve disjoint sets of files, ii) there is some overlap in the content served by multiple content providers. In the first case, we prove that cache partitioning outperforms cache sharing as cache size and numbers of contents served by providers go to infinity. In the second case, it can be beneficial to have separate partitions for overlapped content. In the case of two providers it is usually always beneficial to allocate a cache partition to serve all overlapped content and separate partitions to serve the non-overlapped contents of both providers. We establish conditions when this is true asymptotically but also present an example where it is not true asymptotically. We develop online algorithms that dynamically adjust partition sizes in order to maximize the overall utility and prove that they converge to optimal solutions, and through numerical evaluations we show they are effective.

Index Terms-content providers, cache sharing, cache partitioning, utility-driven, online partitioning.

I. INTRODUCTION

T HE Internet has become a global information depository and content distribution platform, where various types of information or content are stored in the "cloud", hosted by a wide array of content providers, and delivered or "streamed" on demand. The (nearly) "anytime, anywhere access" of online information or content -especially multimedia content -has precipitated rapid growth in Internet data traffic in recent years, both in wired and wireless (cellular) networks. It is estimated [START_REF]Cisco visual networking index: Forecast and methodology[END_REF] that the global Internet traffic in 2019 will reach 64 times its entire volume in 2005. A primary contributor to this rapid growth in data traffic comes from online video streaming services such as Netflix, Hulu, YouTube and Amazon Video, just to name a few. It was reported [START_REF] Sandvine | Global internet phenomena report[END_REF] that Netflix alone consumed nearly a third of the peak downstream traffic in North America in 2012, and it is predicted [START_REF]Cisco visual networking index: Forecast and methodology[END_REF] that nearly 90% Mostafa Deghgan is with Google Inc., Cambridge, USA (e-mail: mdehghan@google.com).

Weibo Chu is with Northwestern Polytechnical University, Xi'an, China (e-mail: wbchu@nwpu.edu.cn).

Philippe Nain is with Inria, France (e-mail: philippe.nain@inria.fr). Don Towsley is with University of Massachusetts, Amherst, USA (e-mail: towsley@cs.umass.edu).

Zhi-Li Zhang is with University of Minnesota, Minneapolis, USA (e-mail: zhzhang@cs.umn.edu). of all data traffic will come from video content distributors in the near future.

Massive data traffic generated by large-scale online information access -especially, "over-the-top" video deliveryimposes an enormous burden on the Internet and poses many challenging issues. Storing, serving, and delivering videos to a large number of geographically dispersed users in particular require a vast and sophisticated infrastructure with huge computing, storage and network capacities. The challenges in developing and operating large-scale video streaming services in today's Internet [3]- [START_REF] Adhikari | A tale of three CDNs: An active measurement study of Hulu and its CDNs[END_REF] to handle user demands and meet user desired quality-of-experience also highlight some of the key limitations of today's Internet architecture. This has led to a call for alternate Internet architectures that connect people to content rather than servers (see [START_REF] Ahlgren | A survey of information-centric networking[END_REF] for a survey of representative architecture proposals). The basic premise of these content-oriented architectures is that storage is an integral part of the network substrate where content can be cached on-the-fly, or prefetched or "staged" a priori.

While there has been a flurry of recent research studies in the design of caching mechanisms [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF]- [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF], relatively little attention has been paid to the problem of storage or cache resource allocation among multiple content providers. In this paper, we address a fundamental research question that is pertinent to all architecture designs: how to share or allocate the cache resource within a single network forwarding element and across various network forwarding elements among multiple content providers so as to maximize the cache resource utilization or provide best utilities to content providers?

This question was addressed in [START_REF] Chu | On allocating cache resources to content providers[END_REF] in an informal and heuristic manner. It proposed a utility maximization framework, which we adopt, to address the aforementioned fundamental problem. We consider a scenario where there are multiple content providers offering the same type of content, e.g., videos; the content objects offered by the content providers can be all distinct or there may be common objects owned by different content providers. Due to disparate user bases, the access probabilities of these content objects may vary across the CPs. Our analysis and results are predicated on the use of Least Recently Used (LRU) cache replacement; however, we believe that they apply to other policies as well. [START_REF] Chu | On allocating cache resources to content providers[END_REF] argued that, if all CPs offer distinct content objects, partitioning the cache into slices of appropriate sizes, one slice per CP, yields the best cache allocation strategy as it maximizes the sum of CP utilities. [START_REF] Chu | On allocating cache resources to content providers[END_REF] also considered the case where CPs serve common content and argued that placing common content into a single LRU cache and non-common content in separate LRU caches usually provides the best per-formance. We make more precise statements to support these observations. In the case that common content are requested according to the same popularity distributions, regardless of provider, in the limit aggregate hit rate is maximized when three LRU partitions are established, one for the overlapped content and the other two for the non-overlap content. We also provide a counterexample that shows that such a strategy is not always optimal. However, the conclusion is that partitioning is usually best.

The above results are based on the work of Fagin [START_REF] Fagin | Asymptotic miss ratios over independent references[END_REF], who characterized the asymptotic behavior of LRU for a rich class of content popularity distributions that include the Zipf distribution.

In the last part of the paper, we develop decentralized algorithms to implement utility-driven cache partitioning. These algorithms adapt to changes in system parameters by dynamically adjusting the partition sizes, and are theoretically proven to be stable and converge to the optimal solution.

Our results illustrate the importance of considering the cache allocation problem among multiple CPs and has implications in architectural designs: from the perspective of cache resource efficiency or utility maximization of CPs, cache partitioning (among CPs) should be a basic principle for cache resource allocation; it also suggests alternate content-oriented architectures which explicitly account for the role of CPs [START_REF] Ramadan | CONIA: Content (provider)-oriented, namespace-independent architecture for multimedia information delivery[END_REF].

Cache partitioning also provides a natural means to effectively handle heterogeneous types of content with different traffic or access characteristics, and offer differentiated services for content delivery [START_REF] Zhang | Caching in information centric networking: A survey[END_REF], [START_REF] Kelly | Biased replacement policies for web caches: Differential quality-of-service and aggregate user value[END_REF]- [START_REF] Lu | Design, implementation, and evaluation of differentiated caching services[END_REF]. In the future Internet where network cache elements will likely be provided by various entities [START_REF] Zhang | Feel free to cache: Towards an open CDN architecture for cloud-based content distribution[END_REF], our framework also facilitates the design of distributed pricing and control mechanisms, and allows for the establishment of a viable cache market economic model.

The main contributions of this paper can be summarized as follows:

• We establish the connection between Fagin's asymptotic results on the LRU cache and the characteristic time (CT) approximation introduced in [START_REF] Che | Analysis and design of hierarchical web caching systems[END_REF], providing a stronger theoretical underpinning for the latter than previously known. Moreover, we extend Fagin's results and therefore theoretical justification of the CT approximation to a larger class of workloads that include those coming from independent content providers. • Using Fagin's asymptotic framework we show that partitioning is the best strategy for sharing a cache when content providers do not have any content in common.

On the other hand when content providers serve the same content, it can be beneficial for content providers to share a cache to serve their overlapped content. We establish this to be true for a class of popularity distributions. We also present an example where placing common content in a shared cache is not optimal. • We develop online algorithms for managing cache partitions, and prove the convergence of these algorithms to the optimal solution using Lyapunov functions. • We show that our framework can be used in revenue based models where content providers react to prices set by (cache) service providers without revealing their utility functions.

• We perform numerical studies and simulations to show the efficacy of cache partitioning and also the convergence of our online algorithms using different utility functions with different fairness implications.

The remainder of this paper is organized as follows. We present the problem setting and basic model in Section II where we make the connection between Fagin's asymptotic results and the CT approximation. We describe the cache allocation problem via the utility maximization framework in Section III. In Section IV, we develop online algorithms for implementing utility-maximizing cache partitioning. Numerical and simulation results are presented in Section V. In Section VI, we explore the implications of our results, and discuss future research directions and related work. Section VII concludes the paper.

II. PROBLEM SETTING & BASIC MODEL

Consider a network as shown in Figure 1, where users access content, e.g., videos, from K content providers (CPs). CP k (k = 1, . . . , K) serves a set S k of n k unit size files where n k = |S k |; we will usually label these files i = 1, . . . , n k . All CPs share a content cache, supplied by a third-party network provider, referred to as a service provider hereafter. Content providers have business relations with the service provider and pay for cache resources. There are two possible scenarios: i) the content objects offered by the CPs are all distinct; and ii) some common objects are provided by different CPs. Due to disparate user bases, the access patterns of these content objects may vary across the CPs.

We assume that requests are described by a Poisson process with request rate for file i of CP k being λ k,i = λ k p k,i , i ∈ S k , k = 1, . . . , K, where λ k denotes the aggregate request rate for contents from CP k, and p k,i is the probability that a request to CP k is for content i. Associated with each CP k is a utility U k (h k ) that is an increasing and concave function of the hit rate h k over all its files. In its most general form, the service provider wishes to maximize the sum of utilities over all content providers, k U k (h k ), through a proper allocation of cache space to the CPs. In the simple case where U k (h k ) = h k , the objective becomes that of maximizing the overall cache hit rate, which provides a measure of the overall cache utilization efficiency. Cache Partitioning: When the cache is shared among the CPs, content objects offered by all CPs compete for the storage space based on their access patterns. To restrict cache contention to smaller sets of content, the service provider can form content groups from files served by a CP or multiple CPs, and partition the cache into slices and dedicate a partition to each content group. Let P denote the number of content groups/cache partitions. Also, let V p and C p , p = 1, . . . , P denote the content groups and partition sizes, respectively. Note that P = 1 implies that the cache is shared as a whole, while P > 1 means it is partitioned.

The first question to ask is: what is the optimal number of partitions and how should files be grouped? To determine the number of slices and that what files should be requested from which partition, the service provider proceeds as follows. Files are first grouped into disjoint sets according to which content providers serve them. The service provider then decides how many partitions to create, and whether to dedicate a separate partition for each set of files, or have multiple sets of files share a partition. In the next section, we explain what could change if the cache manager made partitioning decisions on a per file basis rather than sets of files.

Assuming the answer to the first question, the second question is: how should the partitions be sized? Let C = (C 1 , C 2 , . . . , C P ) denote the vector of partition sizes. For each content provider k, hit rate is a function of the partition sizes h k (C). For a cache of size C, we formulate this question as the following optimization problem:

maximize K k=1 U k h k (C) such that P p=1 C p ≤ C C p = 0, 1, 2, . . . ; p = 1, 2, . . . , P.
Note that the above formulation is an integer programming problem that is typically hard to solve. However, in practice caches are large and therefore we assume C p can take any real value, as the rounding error will be negligible. Cache Characteristic Time: Assume a cache of size C serving n contents with popularity distribution p i , i = 1, . . . , n . Under the independent reference model (requests are i.i.d.), Fagin [START_REF] Fagin | Asymptotic miss ratios over independent references[END_REF] introduced the notion of a window size T that satisfies

C = n i=1 (1 -(1 -p i ) T ).
The miss probability associated with a window of size T is defined as

m(T ) = n i=1 p i (1 -p i ) T .
Fagin introduced a cumulative probability distribution, F , that is continuously differentiable in (0, 1) with F (0) = 0 and F (1) = 1. The right-derivative of F at 0, denoted by F (0), may be infinite. This will allow us to account for Zipf-like distributions. Define

p (n) i = F (i/n) -F ((i -1)/n), i = 1, . . . , n
the probability that page i is requested. Hereafter, we will refer to F as the popularity distribution. If C/n = β then T /n → τ 0 where (see [START_REF] Fagin | Asymptotic miss ratios over independent references[END_REF])

β = 1 0 (1 -e -F (x)τ0 )dx (1)
and m(T ) → µ where

µ = 1 0 F (x)e -F (x)τ0 dx. (2)
Moreover, µ is the limiting miss probability under LRU when n → ∞.

Suppose that requests arrive according to a Poisson process with rate λ. Express β as

β = 1 0 P (X(x) < τ 0 /λ)dx
where X(x) is an exponential random variable with intensity λF (x). X(x) is the inter-arrival time of two requests for content of type x. If this time is less than τ 0 /λ, then the request is served from the cache, otherwise it is not. In practice, as n is finite, this is approximated by

C = βn = n i=1 (1 -e -λp (n) i Tc ) (3)
where T c is the Characteristic Time (CT) for the finite content cache [START_REF] Che | Analysis and design of hierarchical web caching systems[END_REF]. The aggregate miss probability is approximated by

m(T c ) = 1 - n i=1 p (n) i 1 -e -λp (n) i Tc . (4)
Fagin's results suffice to show that as n → ∞, the r.h.s. of (4) converges to the LRU miss probability.

In the context of K providers, let

n k = b k n, n, b k ∈ N, k = 1, . . . , K. Denote B k := k j=1 b j with B 0 =
0 by convention. It helps also to denote B K by B. Let F 1 , F 2 , . . . , F K be continuous uniformly differentiable CDFs in (0, 1). F k (0) may be infinite for k = 1, . . . K. If each provider has a cache that can store a fraction β k of its contents, then the earlier described CT approximation, (3), (4), applies with

p (n) k,i = F k i b k n -F k i -1 b k n , i = 1, . . . , b k n. (5)
We denote the asymptotic miss probabilities for the K caches, each using LRU, by

µ (p) k = 1 0 F k (x)e -F k (x)τ k dx, k = 1, . . . , K (6)
where τ k is the solution of (1) with β replaced by β k . Assume that the providers share a cache of size C. Let

β (s) = (1/B) K k=1 b k β k be
the fraction of the total number of documents that the shared cache can store. With this definition, observe that the size of the shared cache, given by nBβ (s) , and the size of the partitioned cache, given We introduce µ (s) and τ 0 through the following two equations,

µ (s) = K k=1 a k 1 0 F k (x)e -a k F k (x)τ0B/b k dx, (7)
β (s) = 1 - K k=1 b k B 1 0 e -a k F k (x)τ0B/b k dx (8)
where

a k := λ k /λ, k = 1, . . . , K.
Theorem 1. Assume that we have K providers with popularity distributions F 1 , . . . , F K as defined above, with numbers of contents given by b k n and request rates λ k , k = 1, . . . , K.

Construct the sequence of popularity probabilities {p [START_REF] Adhikari | A tale of three CDNs: An active measurement study of Hulu and its CDNs[END_REF] and cache sizes C (n) such that C (n) /(Bn) = β. Then, the aggregate miss probability under LRU converges to µ (s) given in [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF], where τ 0 is the unique solution of (8).

(n) k,i }, n = 1, . . . defined in

Proof. See Appendix B.

Remark. This extends Fagin's results to include any asymptotic popularity CDF F that is continuously differentiable in (0, 1) except at a countable number of points.

To help the reader with notation, a glossary of the main symbols used in this paper is given in Table I.

III. CACHE RESOURCE ALLOCATION AMONG CONTENT PROVIDERS

In this section, we formulate cache management as a utility maximization problem. We introduce two formulations, one for the case where content providers serve distinct contents, and another one for the case where some contents are served by multiple providers.

A. Content Providers with Distinct Objects

Consider the case of K providers with n k = b k n contents each where b k , n ∈ N and k = 1, . . . , K. Also, let B = K k=1 b k . Assume that requests to CP k is characterized by a Poisson process with rate λ k .

We ask the question whether the cache should be shared or partitioned between CPs under the LRU policy. It is easy to construct cases where sharing the cache is beneficial. However these arise when the cache size and the number of contents per CP are small. Evidence suggests that partitioning provides a larger aggregate utility than sharing as cache size and number of contents grow. In fact, the following theorem shows that asymptotically, under the assumptions of Theorem 1, in the limit as n → ∞, the sum of utilities under LRU when the cache is partitioned, is at least as large as it is under LRU when the CPs share the cache. To do this, we formulate the following optimization problem: namely to partition the cache among the providers so as to maximize the sum of utilities: 9) is the hit rate of documents of CP k, where µ k (β k ) is given by ( 6).

max β k U (p) := K k=1 U k (λ k (1 -µ k (β k ))) (9)
s.t. β = K k=1 b k B β k , β k ≥ 0, k = 1, 2, . . . , K. Observe that λ k (1-µ k (β k )) in (
Here, µ k is the asymptotic miss probability for content served by CP k, β is the cache size constraint expressed in terms of the fraction of the aggregate content that can be cached, b k /B is the fraction of content belonging to provider k, and β k is the fraction of CP k content that is permitted in CP k's partition. The direct dependence of β k on µ k is difficult to capture. Hence, we use ( 1) and ( 2), to transform the above problem into:

max τ k U (p) := K k=1 U k λ k 1 - 1 0 F k (x)e -F k (x)τ k dx (10) s.t. β = 1 - K k=1 b k B 1 0 e -F k (x)τ k dx, τ k ≥ 0, k = 1, 2, . . . , K.
Theorem 2. Assume K providers with popularity distributions constructed from distributions F 1 , . . . , F K using (5) with number of contents b k n and request rates λ k , k = 1, . . . , K sharing a cache of size C (n) such that C (n) /(Bn) = β. Then, as n → ∞ the sum of utilities under partitioning is at least as large as that under sharing.

Proof. The sum of utilities for the shared case is

U (s) = K k=1 U k λ k 1 - 1 0 F k (x)e -a k F k (x)τ0B/b k dx
where τ 0 is the unique solution to

β = 1 - K k=1 b k B 1 0 e -a k F k (x)τ0B/b k dx. When we set τ k = a k τ 0 B/b k in U (p) then U (p) = U (s)
, proving the theorem.

Based on the above theorem, we focus solely on partitioned caches and use the CT approximation to formulate the utilitymaximizing resource allocation problem for content providers with distinct files as follows:

maximize K k=1 U k h k (C k ) (11)
such that

K k=1 C k ≤ C, C k ≥ 0, k = 1, 2, . . . , K.
In our formulation, we assume that each partition employs LRU for managing the content. Therefore, we can compute the hit rate for content provider k as

h k (C k ) = λ k n k i=1 p k,i 1 -e -λ k p k,i T k (C k ) , (12)
where T k (C k ) denotes the characteristic time of the partition with size C k dedicated to content provider k. T k (C k ) is the unique solution to the equation

C k = n k i=1 (1 -e -λ k p k,i T k ). (13)
The following theorem establishes that resource allocation problem [START_REF] Chu | On allocating cache resources to content providers[END_REF] has a unique optimal solution: Theorem 3. Given strictly concave utility functions, resource allocation problem (11) has a unique optimal solution.

Proof. In Appendix A, we show that h k (C k ) is an increasing concave function of C k . Since U k is assumed to be an increasing and strictly concave function of the cache hit rate h k , it follows that U k is an increasing and strictly concave function of C k . The objective function in [START_REF] Chu | On allocating cache resources to content providers[END_REF] is a linear combination of strictly concave functions, and hence is concave. Meanwhile, as the feasible solution set is convex, a unique maximizer called the optimal solution, exists.

Last, it is straightforward to show that partitioning is at least as good as sharing, for finite size systems using the CT approximation.

B. Content Providers with Common Objects

Here, we first assume there are only two content providers in the network and then consider the general case. There are three sets of content, S 0 of size n 0 served by both providers, and S 1 and S 2 , sizes n 1 and n 2 served separately by each of the providers. Requests are made to S 0 at rate λ 0,k from provider k and to S k at rate λ k . Given a request is made to S 0 from provider k, it is for content i with probability p 0,k,i . Similarly, if the request is for content in S k , k = 1, 2, it is for content i with probability p k,i .

We have two conceivable cases for the files in S 0 : 1) each content provider needs to maintain its own copy of the content, e.g., due to security reasons, or 2) one copy can be kept in cache to serve requests to either of the content providers. The first case can be treated as if there is no common content between the two content providers, and hence can be cast as problem [START_REF] Chu | On allocating cache resources to content providers[END_REF]. For the second case, we consider three strategies for managing the cache:

• Strategy 1 (S1): sharing the whole cache as one large partition, • Strategy 2 (S2): partitioning into two dedicated slices, one for each CP, • Strategy 3 (S3): partitioning into three slices, one shared partition for the set of common contents, and two other partitions for the remaining files of each CP, as shown in Figure 2.

The following theorem states that S3 performs at least as well as S1 in an asymptotic sense.

Theorem 4. Assume that we have two providers with a set of shared files S 0 , and sets of non-shared files , S 1 , S 2 with numbers of files

n k = b k n, b k , n ∈ N, and k = 0, 1, 2.
Assume that requests to these sets occur with rates λ 0,k and λ k and content popularities are described by asymptotic popularity distributions F 0,k , and F k . Construct the sequence of popularity probabilities {p

(n) k,i }, n = 1, . . . similar to (5) and cache sizes C (n) such that C (n) /(Bn) = β.
Then, the asymptotic aggregate LRU miss probability is at least as small under S3 as under S1.

The proof is similar to the proof of Theorem 2. Neither S2 nor S3 outperforms the other for all problem instances, even asymptotically. However, we present a class of workloads for which asymptotically S3 outperforms S2 and then follow it with an example where S2 outperforms S3.

Consider the following workload where the asymptotic popularity distributions of requests to the two providers for the shared content are identical, F 0,1 = F 0,2 .

Theorem 5. Assume that we have two providers with a set of shared files S 0 and sets of non-shared files, S 1 , S 2 with numbers of files n k = b k n, b k ∈ N, n = 1, . . . , and k = 0, 1, 2. Assume that requests are described by Poisson processes with rates λ 0,k and λ k , k = 1, 2, and content popularities are described by asymptotic popularity distributions F 0,1 = F 0,2 , and F 1 , F 2 . Construct the sequence of popularity probabilities {p [START_REF] Adhikari | A tale of three CDNs: An active measurement study of Hulu and its CDNs[END_REF] and cache sizes C (n) such that C (n) /(Bn) = β. Then the asymptotic aggregate hit probability under LRU is at least as large under S3 as under S2.

(n) k,i }, n = 1, . . . similar to
The proof is found in Appendix C Below is an example where S2 outperforms S3. The asymptotic popularity distributions for the shared content are given by

F 0,1 (x) = 2x/11 0 < x ≤ 1/2 (20x -9)/11 1/2 < x < 1
Algorithm 1 Partitioning a cache serving K content providers with possibility of common files among some content providers.

1: S ← S 1 ∪ S 2 ∪ . . . ∪ S K . 2: P ← Ø. 3: for f ∈ S do 4: M f ← {k : Content provider k serves files f }. 5: if Exists (V, M ) ∈ P such that M = M f then 6: V ← V ∪ {f }.
P ← P ∪ {({f }, M f )}. and F 0,2 (x) = 300x/151 0 < x ≤ 1/2 (2x + 149)/151 1/2 < x < 1
with request rates λ 0,1 = 1.1 and λ 0,2 = 15.1. The asymptotic popularities of the non-shared contents are F 1 (x) = F 2 (x) = x with request rates λ 1 = 20 and λ 2 = 30. Last, there are equal numbers of content in each of these sets, n 0 = n 1 = n 2 . If we set β = 2/3, then the aggregate hit probability under S3 with optimal partitioning is .804, which is slightly lower than the aggregate hit probability, .816, under S2 with optimal partitioning.

The above examples show that the workloads of the content providers can affect which strategy is optimal. However, we argue that partitioning into three slices should provide the best performance in most practical situations, where content providers have similar popularity patterns for the contents they commonly serve. This is unlike the second example where the two content providers have disparate rates for the common contents they serve. In Section V, we will show that even if two content providers have dissimilar request rates for their common contents, partitioning into three slices does better.

Based on the above argument for the performance of partitioning into three slices in the case of two content providers, for K content providers with common files, one should create a partition for each set of files that are served by a number of content providers. A procedure for creating the optimal set of partitions P with the files routed to each partition is given in Algorithm 1. Algorithm 1 runs in O(|S| 2 ) where S denotes the set of all files served by all content providers. Note that the number of partitions can grow exponentially with the number of content providers.

Once the set of partitions P and the set of files corresponding to each partition is determined, the optimal partition sizes can be computed through the following optimization problem:

maximize k U k (h k ) (14)
such that

|P| p=1 C p ≤ C C p ≥ 0, p = 1, 2, . . . , |P|,
where hit rate for CP k is computed as

h k = |P| p=1 λ k i∈Vp p k,i 1 -e -λip k,i Tp(Cp)
where V p denotes the set of files requested from partition p, and λ i k λ k,i denotes the aggregate request rate for content i through all content providers, and T p denotes the characteristic time of partition p. Theorem 6. Given strictly concave utility functions, resource allocation problem (14) has a unique optimal solution.

Proof. In Appendix D, we show that the optimization problem ( 14) has a concave objective function. Since the feasible solution set is convex, a unique maximizer exists.

C. Implications

Cache Partitioning: Number of Slices, Management Complexity and Static Caching. In our utility maximization formulations ( 11) and ( 14) and their solution, the cache is only partitioned and allocated per CP for a set of distinct content objects owned by the CP; a cache slice is allocated and shared among several CPs only for a set of common content objects belonging to these CPs. This is justified by cache management complexity considerations, as further partitioning of a slice allocated to a CP to be exclusively utilized by the same CP simply incurs additional management complexity. In addition, it is not hard to show that partitioning a cache slice into smaller slices and probabilistically routing requests to content objects of a CP is sub-optimal.

As an alternative to CP-oriented cache allocation and partitioning approach, one could adopt a per-object cache allocation and partitioning approach (regardless of the CP or CPs which own the objects). Under such an approach, it is not hard to show that the optimal per-object cache allocation strategy that maximizes the overall cache hit rate is equivalent to the static caching policy [START_REF] Liu | Static caching of web servers[END_REF]: the cache is only allocated to the C most popular objects among all content providers. Alternatively, such a solution can also be obtained using the same CP-oriented, utility maximization cache allocation framework where only the most popular content from each provider is cached. Utility Functions and Fairness. Different utility functions in problems [START_REF] Chu | On allocating cache resources to content providers[END_REF] and ( 14) yield different partition sizes for content providers. In this sense, each utility function defines a notion of fairness in allocating storage resources to different content providers. The family of α-fair utility functions expressed as

U (x) =    x 1-α -1 1-α α ≥ 0, α = 1; log x α = 1,
unifies different notions of fairness in resource allocation [START_REF] Srikant | Communication Networks: An Optimization, Control, and Stochastic Networks Perspective[END_REF]. Some choices of α lead to especially interesting utility functions. Table II gives a brief summary of these functions. We will use these utilities in Section V to understand the effect of particular choices for utility functions, and in evaluating our proposed algorithms.

α U k (h k ) implication 0 h k hit rate 1 log h k proportional fairness 2 -1/h k potential delay ∞ lim α→∞ h 1-α k -1 1-α max-min fairness
IV. ONLINE ALGORITHMS In the previous section, we formulated cache partitioning as a convex optimization problem. However, it is not feasible to solve the optimization problem offline and then implement the optimal strategy. Moreover, system parameters can change over time. Therefore, we need algorithms that can implement the optimal strategy and adapt to changes in the system by collecting limited information. In this section, we develop such algorithms.

A. Content Providers with Distinct Contents

The formulation in [START_REF] Chu | On allocating cache resources to content providers[END_REF] assumes a hard constraint on the cache capacity. In some circumstances it may be appropriate for the cache manager to increase the available storage at some cost to provide additional resources for the content providers. One way of doing this is to turn cache storage disks on and off based on demand [START_REF] Sundarrajan | Energy-efficient disk caching for content delivery[END_REF]. In this case, the cache capacity constraint can be replaced with a penalty function P (•) denoting the cost for the extra cache storage. Here, P (•) is assumed to be convex and increasing. We can now write the utility and cost driven caching formulation as

maximize k U k (h k (C k )) -P ( k C k -C) such that C k ≥ 0, k = 1, . . . , K. (15)
Let W (C) denote the objective function in (15) defined as

W (C) = k U k (h k (C k )) -P ( k C k -C).
A natural approach to obtaining the maximum value for W (C) is to use a gradient ascent algorithm. The basic idea behind a gradient ascent algorithm is to move the variables C k in the direction of the gradient,

∂W ∂C k = ∂U k ∂C k -P ( k C k -C), = U k (h k ) ∂h k ∂C k -P ( k C k -C).
Note that since h k is an increasing function of C k , moving C k in the direction of the gradient also moves h k in that direction. By gradient ascent, partition sizes should be updated according to

C k ← max 0, C k + γ k U k (h k ) ∂h k ∂C k -P ( k C k -C) ,
where γ k is a step-size parameter.

Theorem 7. The above gradient ascent algorithm converges to the optimal solution.

Algorithm 2 Online algorithm for updating the partition sizes.

1: Start with an initial partitioning C 0 ← (C 1 ∪ C 2 ∪ . . . ∪ C K ).
2: Estimate hit rates for each partition by counting the number of hit requests h 0 ← (h 1 , . . . , h K ). 3: Make arbitrary changes to the partition sizes ∆ 0 , such that k ∆ 0 k = 0, C 1 ← C 0 + ∆ 0 . 4: Estimate the hit rates h 1 for the new partition sizes. 5: t ← 1.

6: δ t k ← U k (h t k ) -U k (h t-1 k ) / C t k -C t-1 k . 7: η t ← k δ t k /K. 8: if max k {δ t k -η t } > then 9: ∆ t k = γ(δ t k -η t ).
10:

C t+1 ← C t + ∆ t .
11:

Estimate hit rates h t+1 .

12:

t ← t + 1.

13: goto 6.

Proof. Let C * denote the optimal solution to [START_REF] Ko | Scalable service differentiation in a shared storage cache[END_REF]. We show in Appendix E that W (C * )-W (C) is a Lyapunov function, and the above algorithm converges to the optimal solution.

1) Algorithm Implementation: In implementing the gradient ascent algorithm, we restrict ourselves to the case where the total cache size is C. Defining η P (0), we can re-write the gradient ascent algorithm as

C k ← max 0, C k + γ k U k (h k ) ∂h k ∂C k -η .
In order to update C k then, the cache manager needs to estimate

∂U k ∂C k = U k (h k ) ∂h k
∂C k by gathering hit rate information for each content provider. Instead of computing U k (h k ) and ∂h k /∂C k separately, however, we suggest using

∂U k ∂C k ≈ ∆U k ∆C k = U k (h t k ) -U k (h t-1 k ) C t k -C t-1 k ,
where the superscripts t and t -1 denote the iteration steps.

We then use ∆U k ∆C k as an estimate of U k (h k ) ∂h k ∂C k to determine the value of C k at the next iteration.

Moreover, since we impose the constraint that k C k = C, we let η take the mean of the ∆U k ∆C k values. The algorithm reaches a stable point once the ∆U k ∆C k s are equal or very close to each other. Algorithm 2 shows the rules for updating the partition sizes.

B. Content Providers with Common Content

We now focus on the case where some contents can be served by multiple content providers. Algorithm 1 computes the optimal number of partitions for this case. Let P and C = (C 1 , . . . , C |P| ) denote the set of partitions and the vector of partition sizes, respectively. The hit rate for content provider k can be written as

h k (C) = |P| p=1 i∈Vp λ ik (1 -e -λiTp ),
Algorithm 3 Online algorithm for updating the partition sizes. 4: Make arbitrary changes to the partition sizes ∆ 0 , such that p ∆ 0 p = 0, C 1 ← C 0 + ∆ 0 . 5: Estimate the hit rates H 1 for the new partition sizes. 6: t ← 1. ∆ t p = γ(δ t p -η t ).

7: δ t p ← k U k (h t-1 k )(h t kp -h t-1 kp )/(C t p -C t
11:

C t+1 ← C t + ∆ t .
12:

Estimate hit rates H t+1 .

13:

t ← t + 1.

14: goto 6.

where V p denotes the set of files requested from partition p, and λ i denotes the aggregate request rate at partition p for file i.

Similar to [START_REF] Ko | Scalable service differentiation in a shared storage cache[END_REF], we consider a penalty function for violating the cache size constraint and rewrite the optimization problem in [START_REF] Kelly | Biased replacement policies for web caches: Differential quality-of-service and aggregate user value[END_REF] as

maximize k U k (h k (C)) -P ( p C p -C) such that C p ≥ 0, p = 1, . . . , |P|. (16)
Let W (C) denote the objective function in the above problem.

Taking the derivative of W with respect to C p yields

∂W ∂C p = k U k (h k ) ∂h k ∂C p -P ( p C p -C).
Following a similar argument as in the previous section, we can show that a gradient ascent algorithm converges to the optimal solution.

1) Algorithm Implementation: The implementation of the gradient ascent algorithm in this case is similar to the one in Section IV-A1. However, we need to keep track of hit rates for content provider k from all partitions that store its files. This can be done by counting the number of hit requests for each content provider and each partition through a K × |P| matrix, as shown in Algorithm 3. Also, we propose estimating ∂W/∂C p as

∂W ∂C p ≈ k U k (h k ) ∆h kp ∆C p ,
where ∆h kp denotes the change in aggregate hit rate for content provider k from partition p resulted from changing the size of partition p by ∆C p .

V. EVALUATION

In this section, we perform numerical simulations, first to understand the efficacy of cache partitioning on the hit rate and utility observed by content providers, and second to evaluate the performance of our proposed online algorithms.

A. Hit Rate Improvement

To show hit rate improvement, we consider a caching system where there are two content providers competing for a shared LRU cache with size C = 1000. The two content providers serve n 1 = n 2 = 10000 content objects (so that 5% of content can be held in cache), and requests for these files arrive according to Poisson processes with rates λ 1 = λ 2 = 100. We assume that content popularity of both providers follow a Zipf's law, i.e., p i ∝ 1/i z , with skewness parameters z 1 and z 2 , respectively.

We compare the observed aggregate hit rate of the system under both cache partitioning and sharing (non-partitioning) for a variety of content popularity pattern combinations, i.e., by varying z 2 while fixing z 1 and keeping all other parameters unchanged. The results are shown in Figure 3, where the y axis gives the difference of the observed aggregate hit rate for the two policies, i.e., ∆h = hit partitioning -hit sharing . Obviously we can see that: 1) in all four different content popularity pattern combinations, cache partitioning outperforms cache sharing, thus verifying our theoretical result; 2) as compared with Zipf distributions, the hit rate difference is even larger when content popularity of one provider follows a uniform distribution (see Figure 3(d) vs Figure 3(a), 3(b), 3(c)), which indicates that the more difference of traffic distributions of content providers, the more hit rate gains.

To understand how cache partitioning improves system performance, we plot the hit probabilities of content object for the two providers under both schemes, where z 1 = 0.9, z 2 = 1.2. It can be seen from Figure 4 that cache partitioning improves hit probabilities of content object for CP 2 by allocating to it more cache resources, while it decreases that for CP 1. This phenomenon is in accordance with our intuition that when two content providers differing only in their content popularities compete for the scarce cache resource, more resources should be allocated to the provider with a more skewed content popularity distribution for maximizing the overall system performance. This case study thus illustrates that cache partitioning is able to adjust cache resource allocation among CPs according to their traffic distribution patterns.

Figure 5 gives how the hit rate improvement varies when the cache size grows under three different settings. The first one represents two request flows (each for a content provider) with equal number of content objects and requests rates, but different content popularities. The second one represents two flows where only their requests rates are different, and the third one represents two flows where they only differ in the number of content objects. From Figure 5 we observe hit rate gains under all three different settings. Moreover, comparing Figure 5(a) to Figure 5(b) and Figure 5(c), it is clear that the hit rate improvement shows different trends as the cache size grows. We note that for a caching service provider, fully understanding these phenomena is of particular importance as it provides engineering insights in, e.g., how to provision cache resources for certain hit rate gains, how to balance the tradeoff between caching cost and hit rate gains, etc. While this is not the focus of this paper, some interpretations can be found in [START_REF] Tan | On resource pooling and separation for lru caching[END_REF].

B. Utility-based Cache Partitioning

For understanding the efficacy of utility-based cache partitioning, we setup a base case where an LRU cache of size C = 10 4 is shared by two content providers that serve n 1 = 10 4 and n 2 = 2 × 10 4 contents. The content popularities follow Zipf distributions with parameters z 1 = 0.6 and z 2 = 0.8, respectively. Requests for the files from them arrive as Poisson processes with rates λ 1 = 15 and λ 2 = 10. The utilities of the two content providers are U 1 (h 1 ) = w 1 log h 1 and U 2 (h 2 ) = h 2 . Unless otherwise specified, we let w 1 = 1 so that the two content providers are equally important to the service provider.

We consider two scenarios here. In the first scenario, the two content providers serve completely separate files. In the second scenario, files S 0 = {1, 4, 7, . . . , 10 4 }, are served by both providers. For each scenario the appropriate optimization formulation is chosen.

We first look at solutions of optimization problems ( 11) and [START_REF] Kelly | Biased replacement policies for web caches: Differential quality-of-service and aggregate user value[END_REF]. Here, we measure the gain in total utility through partitioning the cache by computing the utility obtained by sharing the cache between the content providers and the utility obtained by partitioning the cache. Figure 6 shows the utility gain when content providers serve distinct files.

In this example, the aggregate utility increases by 10% from partitioning the cache.

Figure 7 shows the utilities for the case when files in S 0 = {1, 4, 7, . . . , 10 4 } are served by both content providers. Two cases are considered here: a) request rates for the common content are similar for two content providers. This is done by letting p k,1 > p k,2 > . . . > p k,n0 for both providers. b) Requests rates from the two content providers for the common files are set to be dissimilar. This is done by setting the file popularities for the second CP as p 2,1 < p 2,2 < . . . < p 2,n0 . In both cases partitioning the cache into three slices shows the best performance.

We next look at the effect of various parameters on cache partitioning, when CPs serve distinct contents and when they serve some common content with similar popularities. We fix the parameters of the second content provider, and study the effect of changing weight parameter w 1 and aggregate request rate λ 1 of the first content provider. We also change the Zipfian file popularity distribution parameter z 1 . To study the effect of the utility function, we take it to be the α-fair utility function and vary α for the first content provider, α 1 .

Figure 8 shows how hit rates and partition sizes of the two content providers vary as functions of w 1 , λ 1 , z 1 and α 1 . As expected, by increasing the weight w 1 , content provider one gets a larger share of the cache, and hence a higher hit rate. Increasing λ 1 has no effect on the partition sizes. This is because the first content provider uses the log utility function, and it is easy to see that the derivative U 1 (h 1 )∂h 1 /∂C p does not depend on the aggregate rate. In our example, changing the aggregate request rate for the second content provider with U 2 (h 2 ) = h 2 results in different partition sizes. As the popularity distribution for contents from the first content provider becomes more skewed, i.e., as z 1 increases, the set of popular files decreases in size. Consequently, the dedicated partition size for content provider one decreases as z 1 increases. Increasing α 1 changes the notion of fairness between the two content providers in favor of the second content provider, and the size of the partition allocated to the first content provider and its hit rate decreases as α 1 increases.

Figure 9 repeats the same experiment for the case when some common content is served by both content providers. The cache is partitioned into three slices in this case, one of them storing common content. Very similar behavior as in Figure 8 is observed here.

To understand the fairness notion of the α-fair utility functions, we next use the same utility function for both of the content providers, and vary the value of α to see how the hit rates and partition sizes change. Figure 10 shows the effect of α on hit rates and partition sizes for the case when content providers serve distinct files. As α increases, partition sizes change so that hit rates become closer to each other. This is expected since the α-fair utility function realizes the max-min notion of fairness as α → ∞.

Figure 11 shows the changes in resource allocation based on the α-fair notion of fairness when common content is served by the content providers.

C. Online Algorithms

Here, we evaluate the online algorithms presented in Section IV through numerical simulations. Requests are generated according to the parameters presented in the beginning of the above section, and the service provider adjusts partition sizes based on the number of hits between iterations. The service provider is assumed to know the utility functions of the content providers. The utility function of the first content provider is fixed to be U 1 (h 1 ) = log h 1 . We consider three utility functions for the second content provider, namely

U 2 (h 2 ) = h 2 , U 2 (h 2 ) = log h 2 and U 2 (h 2 ) = -1/h 2 .
The sampling probabilities (which also denotes the length of sampling intervals given the aggregate request rate) for the online algorithms are set as 10 -6 per request.

We first consider the case where content providers serve distinct files. We initially partition the cache into two equal size slices C 1 = C 2 = 5000 and use Algorithm 2 to obtain the optimal partition sizes. Figure 12 shows how the partition sizes for the two content providers change at each iteration of the algorithm and that they converge to the optimal values computed from [START_REF] Chu | On allocating cache resources to content providers[END_REF], marked with dashed lines.

Next, we consider the case where some content is served by both content providers. We first partition the cache into three slices of sizes C 1 = C 2 = 4000 and C 3 = 2000, where slice 3 serves the common content, and use Algorithm 3 to obtain the optimal partitioning. Figure 13 shows the changes in the three partitions as the algorithm converges to a stable point. For each partition the optimal size computed by ( 14) is shown by dashed lines.

D. Performance Over Real World Traces

We also conduct a trace-based simulation to investigate the performance of our online algorithm over real-world traffic. The trace consists of 8626163 requests accessing 142040 content objects, with a time duration of 268 minutes 20 seconds. The cache size is set as 500 and the sampling interval of the online algorithm is 5 minutes. In the first experiment we randomly partition the content into two disjoint sets with the same sizes and allocate them to CP 1 and CP 2 respectively. Figure 14 shows how partition sizes evolve as time goes on. Clearly we can see that even for the non-stationary real traffic our algorithm quickly converges. In the second experiment 30% of the content objects are selected as the shared content Fig. 9: Effect of the parameters on hit rates and partition sizes when some content is served by both content providers. among the two providers. CP 1 accounts for 40% of the requests for these shared content while CP 2 accounts for 60%. The performance in this case is given in Figure 15. Again we observe our algorithm quickly converges. Figure 16 gives utilities of the caching system under both cache sharing and cache partitioning when the two content providers serve distinct objects. Due to non-stationary traffic pattern, it is observed from Figure 16(a) that there's no hit rate gains of cache partitioning. However, cache partitioning outperforms when the utility functions are chosen different from hit rate, i.e., U 2 (h 2 ) = log h 2 as shown in Figure 16(b). Similar results are obtained when content providers serve some common objects. These results indicate that in practice, our algorithm can be adopted by cache providers for managing their cache resources for general network utilities.

VI. DISCUSSIONS AND RELATED WORK

In this section, we explore the implications of utility-driven cache partitioning on monetizing caching service and present some future research directions. We end with a brief discussion of the related work. Decomposition. The formulation of the problem in Section III assumes that the utility functions U k (•) are known to the system. In reality the content providers may not want to reveal their utility functions to the service provider. To handle this case, we decompose optimization problem [START_REF] Chu | On allocating cache resources to content providers[END_REF] into two simpler problems.

Suppose that cache storage is offered as a service and the service provider charges content providers at a constant rate r for storage space. Hence, a content provider needs to pay an amount of w k = rh k to obtain hit rate h k . The utility maximization problem for content provider k can be written as

maximize U k ( w k r ) -w k (17)
such that w k ≥ 0

Now, assuming that the service provider knows the vector w, for a proportionally fair resource allocation, the hit rates should be set according to maximize

K k=1 w k log (h k ) (18) such that p C p = C.
It was shown in [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF] that there always exist vectors w and h, such that w solves (17) and h solves (18); furthermore, the vector h is the unique optimal solution. Nonequal-Size Files. Following the common practice, we assume files are of equal sizes in our model. However, files can be of variable sizes in real networks. One possible solution in this case is that we divide each file into a number of small fixed-size chunks, and still treat these chunks as if they were independent files in large-scale caching systems, i.e., when the number of users accessing them is large enough. Nevertheless, this assumption needs to be carefully validated and its impact precisely measured. Actual Simulations. In Section V we adopted numerical studies and trace-based simulaiton to validate our mechanism. To comprehensively understand the efficacy and benefits of cache partitioning, it is essential to evaluate the mechanism through actual simulations that will relax more theoretical assumptions. To achieve this, the simulator needs to support the following two functions: 1) dynamically changing cache sizes as the simulation process goes on; 2) measuring the hit rates for a particular set of files requested in simulation. We note that both functions are not well supported by existing caching simulators, e.g., Icarus [START_REF] Saino | Icarus: a caching simulator for information centric networking (icn)[END_REF], SocialCCNSim [START_REF] Din | Socialccnsim: A simulator for caching strategies in information-centric networking[END_REF], ndnSim [START_REF] Afanasyev | ndnsim: Ndn simulator for ns-3[END_REF]. It is our future work that we implement these functions and evaluate our cache management algorithms based on these open-source simulators. Cost of Adjusting Cache Partitions. We did not consider the cost of adjusting cache partitions in our model. In real practice, frequently adjusting cache partitions would unavoidably incur some management cost and hence there is a trade-off between adjusting cost and system performance. Systematically investigating this trade-off and determing the optimal adjusting frequency thus becomes an important research problem that should be addressed before we apply our mechanism into real networks.

Cost and Utility Functions. In Section IV, we defined a penalty function denoting the cost of using additional storage space. One might also define cost functions based on the consumed network bandwidth. This is especially interesting in modeling in-network caches with network links that are likely to be congested.

Optimization problems [START_REF] Chu | On allocating cache resources to content providers[END_REF] and ( 14) use utility functions defined as functions of the hit rate. It is reasonable to define utility as a function of the hit probability. Whether this significantly changes the problem, e.g., in the notion of fairness, is a question that requires further investigation. One argument in support of utilities as functions of hit rates is that a service provider might prefer pricing based on request rate rather than the cache occupancy. Moreover, in designing hierarchical caches a service provider's objective could be to minimize the internal bandwidth cost. This can be achieved by defining the utility functions as U k = -P k (m k ) where P k (m k ) denotes the cost associated with miss rate m k for content provider k. Related Work. Internet cache management issues have been extensively studied in the context of web caching (e.g., see [START_REF] Che | Analysis and design of hierarchical web caching systems[END_REF], [START_REF] Feldman | Service differentiation in web caching and content distribution[END_REF] and references therein). In this context, biased replacement policies for different kinds of content classes [START_REF] Kelly | Biased replacement policies for web caches: Differential quality-of-service and aggregate user value[END_REF] and differentiated caching services via cache partitioning [START_REF] Ko | Scalable service differentiation in a shared storage cache[END_REF], [START_REF] Lu | Design, implementation, and evaluation of differentiated caching services[END_REF] have been proposed and studied. None of these studies explicitly deal with the cache allocation problem among multiple content providers. The emergence of content-oriented networking has renewed research interests in cache management issues for content delivery, especially in the design of cache replacement policies for the content-oriented architecture [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF]- [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF]. The cache allocation problem among content providers has attracted relatively little attention. Perhaps most closely related to our work is the study in [START_REF] Hoteit | On fair network cache allocation to content providers[END_REF] where a game-theoretic cache allocation approach is developed. This approach requires the content providers to report the true demands from their content access. In contrast, we develop a general utility maximization framework for studying the cache allocation problem. Since its first proposal by Kelly et al. [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF], the network utility maximization framework has been applied to a variety of networking problems from stability analysis of queues [START_REF] Eryilmaz | Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control[END_REF] to the study of fairness in network resource allocation [START_REF] Neely | Stochastic Network Optimization with Application to Communication and Queueing Systems[END_REF]. A utility maximization framework for caching policies was developed in [START_REF] Dehghan | A utility optimization approach to network cache design[END_REF] to provide differentiated services to content. This framework was adopted by [START_REF] Chu | On allocating cache resources to content providers[END_REF] to study the cache resource allocation problem in an informal and heuristic manner. We make precise statements to support the observations in [START_REF] Chu | On allocating cache resources to content providers[END_REF]. In this respect, our contribution lies in establishing the key properties of CP utilities as a function of cache sizes and in postulating cache partitioning as a basic principle for cache sharing among content providers. Furthermore, we develop decentralized algorithms to implement utility-driven cache partitioning, and prove that they converge to the optimal solution.

VII. CONCLUSION

We proposed utility-based partitioning of a cache among content providers, and formulated it as an optimization problem with constraints on the service provider's cache storage size. Utility-driven cache partitioning provides a general framework for managing a cache with considerations of fairness among different content providers, and has implications on market economy for service providers and content distributors. We considered two scenarios where 1) content providers served disjoint sets of files, or 2) some content was served by multiple content providers. Using Fagin's asympototic framework we showed that caching performance can be imporved by partitioning the cache. We then developed decentralized algorithms for each scenario to implement utility-driven cache partitioning in an online fashion. These algorithms adapt to changes in request rates of content providers by dynamically adjusting the partition sizes. We theoretically proved that these algorithms are globally stable and converge to the optimal solution, and through numerical evaluations illustrated their efficiency.

APPENDIX D PROOF OF THEOREM 6

Proof. Let P and C = (C 1 , . . . , C P ) denote the number of partitions and the vector of partition sizes, respectively. The hit rate for content provider k in this case can be written as where V p denotes the set of files requested from partition p, and λ i = k λ ik denotes the aggregate request rate for file i.

We can re-write the expression for h k as the sum of the hit rates from each partition, since distinct files are requested from different partitions. We have For ḣk we have ḣk = ∂h k ∂C k Ċk .

From the controller for C k we have

Ċk = γ k U k (h k ) ∂h k ∂C k -P ( k C k -C) .
Since ∂h k ∂C k ≥ 0, we get

V (C) = - k γ k ∂h k ∂C k U k (h k ) -P ( k C k -C) ∂C k ∂h k 2 ≤ 0.
Therefore, V (•) is a Lyapunov function, and the system state will converge to C * starting from any initial condition. A description of Lyapunov functions and their applications can be found in [START_REF] Srikant | Communication Networks: An Optimization, Control, and Stochastic Networks Perspective[END_REF].

Mostafa Dehghan received his Ph.D. degree from the College of Information and Computer Sciences at the University of Massachusetts Amherst. He was advised by Prof. Don Towsley, and worked on modeling and performance evaluation of contentcentric networks. Cache management, routing in cache networks, and analysis of CCN data structures are some of the problems he has worked on. Before joining UMass, Mostafa received a master's degree from University of Calgary, where he developed distributed routing algorithms in cooperative networks. Mostafa is with Google now.

Fig. 1 :

 1 Fig. 1: Network Model.

Fig. 2 :

 2 Fig. 2: Partitioning cache into three slices. One partition for the set of common files, S0, and two other partitions, one for the remaining files from each content provider, S k .

1 Fig. 3 : 2 Fig. 4 :

 1324 Fig. 3: Observed aggregate hit rate gains under different combinations of content popularity pattern.

Fig. 5 :Fig. 6 :Fig. 7 :

 567 Fig. 5: Observed aggregate hit rate gains under different cache sizes.

Fig. 8 :

 8 Fig.8: Effect of the parameters on hit rates and partition sizes when content providers serve distinct files.

Fig. 10 :

 10 Fig. 10: α-fair resource allocation for content providers serving distinct content. U k (h k ) = h 1-α k /(1 -α).

Fig. 11 :

 11 Fig. 11: α-fair resource allocation when some content is served by both content providers. U k (h k ) = h 1-α k /(1 -α).

  U2(h2) = h2.

  U2(h2) = log h2.

  U2(h2) = -1/h2.

Fig. 12 :

 12 Fig. 12: Convergence of the online algorithm when content providers serve distinct files. U1(h1) = log h1.

  (a) U2(h2) = h2.

  U2(h2) = -1/h2.

Fig. 13 :

 13 Fig.13: Convergence of the online algorithm when some content is served by both content providers. U1(h1) = log h1.

  U2(h2) = log h2.

Fig. 14 :

 14 Fig.14: Performance of the online algorithm over real-world trace when content providers serve disjoint content. U1(h1) = h1.

  U2(h2) = log h2.

Fig. 15 :

 15 Fig. 15: Performance of the online algorithm over real-world trace with some content served by both providers. U1(h1) = h1.

  U2(h2) = log h2.

Fig. 16 :

 16 Fig.16: Utilities over real-world trace when content providers serve distinct content. U1(h1) = h1.

  ik (1 -e -λiTp ),

hV

  kp (C p ),where h kp (C p ) denotes the hit rate for files requested from partition p from content provider k. Since h kp is assumed to be a concave increasing function of C p , h k is sum of concave functions and hence is also concave.APPENDIX E PROOF OF THEOREM 7Proof. We first note that since W (C) is a strictly concave function, it has a unique maximizerC * . Moreover V (C) = W (C * ) -W (C)is a non-negative function and equals zero only at C = C * . Differentiating V (•) with respect to time we obtain h k ) -P ( k C k -C) ∂C k ∂h k ḣk .

TABLE I :

 I Glossary of notations. S k set of files served by content provider k p i probability that file i is requested λ k,i request rate for file i of CP k λ k total request rate for CP k contents F (•) file popularity CDF β k , are the same, which will allow for a fair comparion between both schemes.

		h k	hit rate of CP k
		C p	capacity of partition p
		n	number of files
		β	normalized capacity
		µ	limiting miss probability
	by	K k=1 nb

k

TABLE II :

 II α-fair utility functions

1 :

 1 Compute the number of partitions P using Algorithm 1. ← (C 1 ∪ C 2 ∪ . . . ∪ C P ).

	2: Start		with		an	initial	partitioning
	C 0 3: Estimate hit rates for each provider/partition pair
			h 11 . . . h 1P	
	H 0 ←	 	. . .	. . .	. . .	 .
			h K1 . . . h KP

APPENDIX A HIT RATE IS A CONCAVE AND INCREASING FUNCTION OF CACHE SIZE

Lemma A.1. The hit rate h k is a concave and strictly increasing function of C k .

Proof. Differentiating [START_REF] Fagin | Asymptotic miss ratios over independent references[END_REF] and ( 13) w.r.t. C k gives

The latter equation implies that dT k (C k )/dC k > 0, which in turn implies from the former that dh k (C k )/dC k > 0. This proves that h k (C k ) is strictly increasing in C k . Differentiating now the above equations w.r.t. C k yields

with [START_REF] Liu | Static caching of web servers[END_REF] implies that there exists 1 ≤ l ≤ n k such that g k,i ≥ 0 for i = 1, . . . , l and g k,i ≤ 0 for i = l + 1, . . . , n k .

Hence,

APPENDIX B PROOF OF THEOREM 1

Proof. We first construct a CDF F from the CP specific CDFs, {F k }. When the providers share a single cache, documents are labelled 1, . . . , Bn, so that documents

Let

It is easy to see that

Note that F may not be differentiable at x ∈ {B 1 /B, B 2 /B, . . . B K-1 /B} and, hence, we cannot apply the result of [12, Theorem 1] directly to our problem. Let

be the fraction of documents in the cache. Here, Bnτ 0 corresponds to the window size in [START_REF] Fagin | Asymptotic miss ratios over independent references[END_REF].

We have

We are interested in β (s) = lim n→∞ β (s) (n, τ 0 ).

By applying the result in [12, Theorem 1], we find that

for k = 1, . . . , K, so that

Equation ( 7) is derived in the same way.

Last, it follows from Theorems 2 and 4 in [START_REF] Fagin | Asymptotic miss ratios over independent references[END_REF] that µ (s) is the limiting aggregate miss probability under LRU as n → ∞.

APPENDIX C PROOF OF THEOREM 5

Proof. The optimization problems under strategies 2 and 3 are

where λ 0 = λ 0,1 + λ 0,2 , a 0,k = λ 0,k / 2 k=0 λ k , and

We make the following observation:

Let µ (s2) * denote the minimum miss probability under strategy 2, which is achieved with τ * 1 and τ * 2 . Let µ (s3) (τ 1 , τ 2 , τ 3 ) denote the miss probability under strategy 3 where τ k , k = 0, 1, 2 satisfy [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF]. Set τ k = a 0,k (b0+b k ) (a 0,k +a k )b0 τ * k , k = 1, 2 for strategy 3 and allocate provider k a cache of size β (s2) k under strategy 3 for its non-shared content. The aggregate miss probability for non-shared content is then the same under the two strategies and given by µ

We allocate a cache of that size to the shared content under strategy 3 and without loss of generality assume that µ

). The miss probability over all shared content under strategy 2 is Note that strategy 3 requires only a cache of size β (s2) 0,2 < β - to achieve a smaller miss probability for the shared content than strategy 2 can realize. Adding additional storage to the shared partition can only decrease the hit probability further, thus proving the theorem.


Yu-Sheng Lin

Sung Tsang

Sakina Bensalem

Filipa Lopes

Chen-Li Sun

Bruno Le Pioufle

Hsiang-Yu Wang

USING DIELECTROPHORESIS AND ELECTROROTATION TECHNIQUES TO ASSESS THE DIELECTRIC PROPERTIES OF SCENEDESMUS ABUNDANS AT DIFFERENT GROWTH STATES

Keywords: Microalgae, Dielectrophoresis, Electrorotation, Single Cell Analysis

Microalgae cellular contents are affected by various factors such as temperature, carbon dioxide, light intensity and so on. This study finds that microalgae cells were heterogeneous in terms of dielectric properties although their growth curves and nutrient consumption rates were similar. The shifting of dielectrophoresis direction between different culture generations of microalgae showed the gradual change of cell wall structure and compositions along the cultivation. Additionally, electrorotation spectra of microalgae cells behaving the same in dielectrophoresis were different. Two groups of cells were found in the log phase while the spectra of cells in the stationary phase were relatively uniform, indicating cellular contents were diverse in the log phase but similar in the stationary phase among individual cells. These results show that dielectrophoresis and electrorotation are informative and rapid technologies for analyzing microalgae cellular compositions with single cell resolutions.

INTRODUCTION

Microalgae are photosynthetic microorganisms that convert carbon dioxide into lipids, high-value proteins, pigments and carbohydrates and they are well known for carbon neutrality. Previously, lots of efforts have been made to study the effects of various cultivation strategies on the enhancement of microalgal products. However, the cultivation strategies are species and strain dependent and conventional analysis are time consuming, resulting in the slow progress of advances. In this study, dielectrophoresis and electrorotation techniques were applied to rapidly monitor the changes in dielectric properties of single microalgae cell at different growth phases. Compared with other electrical characterization techniques such as impedance spectroscopy [START_REF] Gawad | Micromachined impedance spectroscopy flow cytometer for cell analysis and particle sizing[END_REF], dielectrophoresis and electrorotation do not require high concentration of cells to perform the measurement. Additionally, they are single cell measurement techniques, being insensitive to the volume factor [START_REF] Français | Single Cell Electrical Characterization Techniques[END_REF].

THEORY

The dielectrophoresis (DEP) force, which expression is shown in equation ( 1), drives the cell to the highest (positive DEP) or lowest (negative DEP) electric field regions, depending on the polarizability of the cell compared to the polarizability of the suspending medium. The direction of the DEP force, linked to the real part of the Clausius Mossotti factor, also depends on the frequency of the electrical field that is applied:

𝐹 ⃗ 𝐷𝐸𝑃 = 2𝜋𝑅 𝑐𝑒𝑙𝑙 3 𝜀 0 𝜀 𝑚 𝑅𝑒[𝑓 𝐶𝑀 (𝜔)]∇ ⃗ ⃗⃗ 𝐸 𝑅𝑀𝑆 2 (1)
where 𝜀 0 and 𝜀 𝑚 respectively stand for the permittivities of the vacuum and the external medium, 𝑅 𝑐𝑒𝑙𝑙 is the radius of the cell, 𝑅𝑒[𝑓 𝐶𝑀 (𝜔)] is the real part of the Clausius-Mossotti factor and 𝐸 is the electric field.

During electrorotation experiments, the rotational speed, which is shown in equation [START_REF] Français | Single Cell Electrical Characterization Techniques[END_REF], is proportional to the electric field and the imaginary part of the Clausius Mossotti factor.

Ω 𝑐𝑒𝑙𝑙 = 𝜀 0 𝜀 𝑚𝑒𝑑𝑖𝑢𝑚 𝐸 2 2𝜂 𝐼𝑚(𝑓 𝐶𝑀 (𝜀 𝑐𝑒𝑙𝑙 * , 𝜀 𝑚𝑒𝑑𝑖𝑢𝑚 * )) (2)
where η is the dynamic viscosity of the medium, 𝐼𝑚(𝑓 𝐶𝑀 (𝜀 𝑐𝑒𝑙𝑙 * , 𝜀 𝑚𝑒𝑑𝑖𝑢𝑚 *

)) is the imaginary part of the Clausius-Mossotti factor which is affected by cellular compositions such as lipids, carbohydrates, proteins.

EXPERIMENTAL SETUP

Microalgae cells at different growth states were monitored using dielectrophoresis, electrorotation, and optical density. Growth curve of S. abundans and nitrate concentration were measured by UV/Visible spectrophotometer (Biochrom Ltd.) with different wavelengths. The amount of chlorophyll was measured at 682 nm which was also proportional to the amount of cell amount in the log phase. For the nitrate quantification, the supernatant of sample setup is shown in Figure 1b. The conventional dielectrophoresis signals (3 Vpp,35 kHz) were applied to drive the cell to the highest and lowest electric field regions which was the positive and negative dielectrophoresis, respectively. The behavior of dielectrophoresis depended on the polarizability of the cell component compared to the polarizability of external medium. If microalgae were less polarizable than the medium (negative dielectrophoresis) which was trapped at the center of the four-electrodes set (Figure 1a). After single cell was trapped, the rotating electric field (3 Vpp, 37 kHz to 25 MHz) was then applied to rotate the microalgae to obtain the electrorotation spectrum.

RESULTS AND DISCUSSION

To understand the growth of microalgae, their growth curve and nitrate amount were monitored by spectrophotometer as shown in Figure 2. Growth curve of S. abundans were in the log phase in the first 4 days and entered the stationary phase between day 4 and 6. The optical density was doubled in 0.5 day ~ 0.75 day for all batches and an optical density higher than 10 can be reached in 3 days. The rapidly decreasing amounts in nitrate (OD220) also indicates the highly thriving culture. Although the growth curve and nitrate consumption rate were similar between all batches, the dielectrophoretic properties were various as shown in Table 1. In batch 1 generation Batch1 -G5 0 100

Batch2 -G3 0 100 *All the data were obtained from ten cells except Batch1 -G2

CONCLUSION

Even though the growth curve and nitrate consumption were similar in different batches and generations, microalgae cells still had differences in dielectric properties, which depends on cellular structure and compositions.

The change of cell wall structure and compositions of S. abundans cells was successfully observed using the dielectrophoresis at relatively low alternating frequency of the electric field. Additionally, the variation of electrorotation spectra of S. abundans cells in the log phase show the change of cellular compositions including not only cell wall but also lipids, protein,…etc. The similar electrorotation spectra of different cells in the stationary phase indicate these cells had similar cellular compositions. Therefore, dielectrophoresis and electrorotation are innovative and informative technologies for monitoring the change of cellular compositions of microalgae during the cultivation.

  was collected by centrifugation (9000 rpm, 3 minutes) and measured at 220 nm. The sample was diluted to an OD less than one and the actual OD value was obtained by multiplying the measured value by the dilution factor. All OD measurement were carried out in duplicates. Four planar parabolic electrodes with a 75 µm gap (Figure 1a) on the quartz wafer were fabricated based on conventional photolithography technology. Microalgae samples were rinsed three times and resuspended in BG-11 medium with 0.02 S/m conductivity. Microalgae sample of 15 µl with a cell concentration of 5 × 10 5 cells/ml was infused between a glass slide and the quartz wafer separated by the 3M tape with a thickness about 50 µm. The electrodes were then connected with a Printed Circuit Board (PCB) which synthesized electric signals for single cell trapping (conventional dielectrophoresis, DEP), and electrorotation experiment (ROT) [3]. The

Figure 1 (

 1 Figure 1 (a) Single microalgae trapped at the center of the fourelectrode set; (b) Experimental setup; 1. DEP generator; 2. ROT generator; 3. Fast camera; 4. PCB; 5. Computer.

  2, 100 % of cells experienced positive dielectrophoresis; however, in batch 1 generation 5, 100 % of cells experienced negative dielectrophoresis. As the generation increased from 2 to 5, the percentage of S. abundans cells experienced negative dielectrophoresis increased proportionally. The change of cell wall composition and its surface properties is the probable cause of this phenomenon since the dielectrophoresis was conducted under relatively low frequency, making cell wall the most sensible cellular part toward the electric field. Additionally, even though all cells experienced negative dielectrophoresis in one batch, their electrorotation spectra were different. In batch 2 generation 3, all cells experienced negative dielectrophoresis and their electrorotation spectra were shown in Figure 3. In log phase, 80 % of the cells had a maximum rotational of 40 rps while 20 % of cells had 10 rps. As the duration of incubation increased, the percentage of cells having maximum rotational speed over 30 rps increased from 20 % to 50 %. Unlike dielectrophoresis, the electrorotation was conducted under a wide range of alternating frequency of electric field and the spectrum not only shows the change of cell wall but also other cellular compositions such as proteins, carbohydrates, and lipids. Therefore, these results indicate that no only the composition of cell wall but also other cell

Figure 2 .

 2 Figure 2. Growth curve of S. abundans and the nitrate consumption rate. OD682 indicates the amount of Chlorophyll and is usually proportional to the cell number before entering stationary phase. OD220 indicates the amount of nitrate in the medium.

Figure 3 .

 3 Figure 3. Electrorotation spectra of S. abundans at different growth phases. (a)1 day after reinoculation, log phase; (b) 2 days after reinoculation, log phase; (c) 4 days after reinoculation, log phase; (d) 8 days after reinoculation, stationary phase.

Table 1 .

 1 Dielectrophoresis behavior of different batches and generations

		Positive dielectrophoresis [%]	Negative dielectrophoresis [%]
	Batch1 -G2 *	100	0
	Batch1 -G3	60	40
	Batch1 -G4	42	58

ACKNOWLEDGEMENTS

This study is supported by the Ministry of Science and Technology of Taiwan under grant number MOST 106-2911-I-007-519, and LabeX LaSIPS project MES-ALG and ALGUIMPACT (ANR-10-LABX-0040-LaSIPS).