Achal Agrawal
email: agrawal@lss.supelec.fr

Florian Danard
email: danard@lss.supelec.fr

Benjamin Larrousse
email: larrousse@lss.supelec.fr

Samson Lasaulce
email: lasaulce@lss.supelec.fr

Implicit Coordination in Two-Agent Team Problems with Continuous Action Sets. Application to the Witsenhausen Cost Function

The main contribution of this paper is the characterization of the limiting average performance of a system involving two agents who coordinate their actions which belong to a continuous set. One agent has complete and noncausal knowledge of the sequence of i.i.d. realizations of a random state X0, which is called the system state and affects the common team payoff. For the other agent, two scenarios in terms of observation assumptions are considered: in the first scenario, the other agent has a strictly causal knowledge of the system state while in the second scenario it has no direct knowledge of the state at all. However, in both scenarios, the less informed agent can always observe a noisy and strictly causal version of the actions taken by the (most) informed agent. There exists no dedicated communication channel between the two agents, and thus, the informed agent can only communicate via its actions which in turn affect the common payoff, hence the term implicit communication. Thus, there is a tradeoff to be found for the informed agent between communicating information about the incoming realizations of the system state and maximizing the payoff at the current stage. We use this general framework and apply it to a specific cost function, namely the Witsenhausen cost function. Although the problem tackled differs from the famous Witsenhausen's counterexample, the authors believe interesting new connections which help to understand the corresponding open problem might be established over time. A numerical analysis is conducted to assess the Witsenhausen's cost for two sub-optimal classes of strategies.

I. INTRODUCTION

In this paper, we consider a team with two agents who are trying to maximize their common payoff over a long time period, i.e., composed of many time-slots. At every time-slot or stage i ∈ {1, • • • , T }, Agent k, k ∈ {1, 2} chooses its action x k ∈ X k , where X k is a continuous set. The instantaneous payoff function w(x 0 , x 1 , x 2 ) depends on the realization of the random variable X 0 with realizations x 0 ∈ X 0 . The set X 0 is also continuous and realizations of X 0 are assumed to be i.i.d.. A problem with the same information structure was addressed for the first time in [START_REF] Gossner | Optimal use of communication resources[END_REF]. Therein, the assumptions made are as follows: it is assumed that at any time Agent 1 knows the past, current, and future realizations of X 0 perfectly, whereas Agent 2 only observes the actions of Agent 1 in a strictly causal manner. Such a scenario has been extended in a couple of papers cited further. However, all of them treated the case where the action sets as well as the system state set were discrete and finite, i.e., ∀ k ∈ {0, 1, 2}, |X k | < ∞. Reference [START_REF] Gossner | Optimal use of communication resources[END_REF] treated the case of an information structure in which Agent 2 has perfect observation and showed that the average performance characterization is equivalent to finding the appropriate information constraint. The information constraint basically gives us the limit for the communication that can take place via actions in such a scenario. In [START_REF] Larrousse | Coded power control: Performance analysis[END_REF] this result was generalized to the case where Agent 2 has imperfect observations. While all these contributions assume a strictly causal knowledge of the system state x 0 at Agent 2, the case where this assumption is relaxed was first presented in [START_REF]More about optimal use of communication resources[END_REF] and treated rigorously in [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF]. The main contribution of the present paper is to generalize this approach of finding the limiting performance to the case of continuous action sets, which is an important case for control problems as many designs involve continuous controlers. A second contribution is to consider the Witsenhausen cost function [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF] as a common cost function to be minimized by the 2-agent team under the two mentioned scenarios in terms of information structures; this establishes for the first time a link between [START_REF] Gossner | Optimal use of communication resources[END_REF][2] [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF] and [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF]. Indeed, although the Witsenhausen problem can be seen as a one-shot coordination problem, whereas we consider a long-term coordination problem here, the idea of joint control-communication strategies is present in both formulations. As it will be seen, characterizing the feasible performance of the long-term coordination problems amounts to determining a certain information constraint. Although information constraints normally appear when (large) sequences intervene, it has to been noted that one-shot problems closely related to the Witsenhausen problem have been solved by introducing an information constraint; this is the case, for instance, for the Gaussian Test Channel (GTC) [START_REF] Bansal | Stochastic teams with nonclassical information revisited: When is an affine law optimal?[END_REF]. The approach we adopt has connections with that of [START_REF] Kulkarni | An optimizer's approach to stochastic control problems with nonclassical information structures[END_REF] where probability distributions which minimize the cost function are used. However, in the latter the authors restrict their attention to what modifications render the (one-shot) Witsenhausen problem simpler to solve, and do not tackle the general framework of long-term implicit communication.

The paper is structured as follows. Section II provides the proposed problem formulation. It explains that characterizing the feasible set of expected common payoffs amounts to characterizing implementable joint probability distributions. Section III provides, for the two information structures considered, the two information constraints which allows one to characterize the implementable distributions. The Gaussian case is provided as a special instance, which establishes a connection with the dirty-paper coding problem [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF]. In Section IV-A, we discuss the Witsenhausen cost function in context to our problem. Section IV-B describes the numerical analysis for the special instance of payoff function (which equals minus the Witsenhausen cost function) and provide numerical results. Section V concludes the paper.

II. PROBLEM STATEMENT

Consider two agents, Agent 1 and Agent 2, who want to coordinate through their actions x 1 ∈ X 1 and x 2 ∈ X 2 . The problem is said to be distributed in the sense that each agent can only control one variable of their common payoff function w(x 0 , x 1 , x 2 ). The action set for both agents X 1 , X 2 as well as the set of system states X 0 are continuous sets. The realizations of the system state are assumed to be i.i.d. and generated from a random variable X 0 whose probability density function is denoted by f 0 (x 0 ). We shall use the notation f V (v) or f (v) to refer to the probability density function of the generic continuous random variable V . The control strategies of Agents 1 and 2 are sequences of functions which are respectively defined by:

   u i : X T 0 → X 1 v a i : X i-1 0 × Y i-1 → X 2 v b i : Y i-1 → X 2 (1)
where T ≥ 1 is the total number of stages over which the agents are assumed to interact, Y is the observation set of Agent 2 and the superscripts a or b correspond to the two considered scenarios in terms of observation structure. The control strategy for Agent 1 u i basically means that it knows the realizations of the system state for all T beforehand, and uses that information to choose its actions; note that the methodology used in this paper can also be exploited under less restrictive knowledge assumptions at Agent 1. The merit of the assumptions made for Agent 1 is that it allows one to make progress in the direction of quantifying the relationship between agents' observation capabilities and reachable performance, which is not well understood. Additionally, there already exist applications for which it is relevant: coordination between robots when a leader knows the trajectory in advance; distributed power control in wireless networks; robust image watermarking.

For Agent 2, we consider two different control strategies v a i and v b i . The control strategy of scenario a assumes that Agent 2 observes the past realizations of the system state x 0 (1), ..., x 0 (i -1) as well as y(1), ..., y(i -1). The control strategy of scenario b is only based on the latter sequence and seems to be more in line with a possible information structure of a long-term version of the Witsenhausen problem. In any case, it is less demanding in terms of information assumptions. The observations y(1), ..., y(T ) are assumed to be generated by a memoryless channel whose transition probability is denoted by γ and verifies a Markov condition f Y |X0,X1,X2 (y|x 0 , x 1 , x 2 ) = γ(y|x 1 ). The additive white Gaussian noise channel Y = X 1 + Z is an intensively used model which verifies this condition.

The instantaneous team payoff function is denoted by w(x 0 , x 1 , x 2 ). Since X 0 is not deterministic we shall be considering the expected payoff

E f [w(X)] = x∈X w(x 0 , x 1 , x 2 )f (x 0 , x 1 , x 2 )dx 0 dx 1 dx 2 (2)
where X = (X 0 , X 1 , X 2 ), x = (x 0 , x 1 , x 2 ), and X = X 0 ×X 1 ×X 2 . In the sequel, we will also denote by W (f ) the above expected payoff i.e., W (f ) = E f [w(X)]. What matters for the expected payoff is function f which characterizes the possible correlations among the three random variables X 0 , X 1 , and X 2 . This correlation precisely measures the degree to which the agents can coordinate with each other and the system state. To understand the relationship between the agents strategies (1) and the expected payoff (2), let us define the notion of implementable distributions.

Definition 1 (Implementability): Let s ∈ {a, b} be the assumed information structure. The probability density function f (x 0 , x 1 , x 2 ) is implementable if there exists a pair of control strategies (u i , v s i ) such that as T → +∞, we have for all

(x 0 , x 1 , x 2 ) ∈ X 0 × X 1 × X 2 , 1 T T i=1 y∈Y f X0X1X2Y,i (x 0 , x 1 , x 2 , y) → f (x 0 , x 1 , x 2 ) (3) where f X0X1X2Y,i = γ × f X1,X2|X0,i × f 0 is the joint distribution induced by (u i , v s i ) at stage i.
Note that since the expectation value of the payoff is a linear operator with respect to the distribution f , the time averaged expected payoff W is reachable if and only if the corresponding distribution f is implementable. In Section III, we shall characterize the set of reachable or feasible average payoffs under the information structure given by [START_REF] Gossner | Optimal use of communication resources[END_REF], which is equivalent to characterizing the set of implementable distributions.

III. PERFORMANCE ANALYSIS: LIMITING PERFORMANCE CHARACTERIZATION

A. General case

In the case of finite alphabets |X i | < ∞, i ∈ {0, 1, 2}, it has been shown in the cases which have been treated so far [START_REF] Gossner | Optimal use of communication resources[END_REF], [START_REF] Larrousse | Coded power control: Performance analysis[END_REF], [START_REF]More about optimal use of communication resources[END_REF], [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF] that characterizing the set of implementable (mass) probability distributions amounts to determining a certain information constraint. For instance in the case of discrete sets and perfect observation of [START_REF] Gossner | Optimal use of communication resources[END_REF] (Y = X 1 ), the necessary and sufficient condition for a joint probability mass distribution Q(x 0 , x 1 , x 2 ) to be implementable is that

H Q (X 0 ) + H Q (X 2 ) -H Q (X 0 , X 1 , X 2 ) ≤ 0 (4)
where H Q is the discrete entropy function under a fixed joint distribution (see Section [START_REF] Cover | Elements of information theory[END_REF] for the different expressions of the entropy used in this section). A well-known reasoning in information theory [START_REF] Cover | Elements of information theory[END_REF], and intensively used in control when communication problems are involved, is to use the information constraint derived in the discrete case and just replace the discrete entropy function with the differential entropy. It can be proved that this reasoning is perfectly valid if considered continuous variables are Gaussian (see e.g., [START_REF] Gamal | Network information theory[END_REF] for a recent reference). For coordination problems such as the one under investigation, imposing the agents' actions to be Gaussian is generally suboptimal. Elaborating further, if we replace the discrete entropy function with the differential entropy we obtain

h f (X 0 ) + h f (X 2 ) -h f (X 0 , X 1 , X 2 ) ≤ 0 (5)
where h f is the differential entropy under the fixed joint distribution f . It turns out that this condition can be shown to be non-necessary in general, indicating that the transition from the discrete case to the continuous case needs some special care in the problem under investigation. To convince the reader, let us recall one of the Cantor's theorems (see e.g., [START_REF] Steen | Counterexamples in Topology[END_REF]). There exists a bijective map from R T to R. Therefore, a possible control strategy for Agent 1 might be as follows.

On the first stage, Agent 1 maps or encodes the whole sequence of states

(x 0 (1), • • • , x 0 (T )) ∈ R T into a single action x 1 (1) ∈ R.
Since Agent 2 observes this action perfectly, it can decode it perfectly and is thus informed of the sequence of states as well. This would mean that from stage i = 2, the two agents can correlate their actions in a arbitrary manner with the system state; in particular they can choose the pair (or one of the pairs) which maximizes w at a given stage i ≥ 2. This means that any probability density function f X0X1X2 can be implemented (asymptotically), contradicting the fact that any implementable distribution has necessarily to verify the continuous counterpart of (4) which is (5). This apparent contradiction comes from the fact that expressing (4) in the continuous case with differential entropies relies on assumptions which need to be specified rigorously for the problem. Indeed, the information constraint can be shown to be necessary and sufficient for implementability within some classes of random variables. One of the broadest classes which is known is provided in [START_REF] Gray | Probability, Random Processes, and Ergodic Properties[END_REF]. It turns out that if one wants to define a probability measure on the Cantor set, one does not fall into this broad class which is specified below. Let's first give the definition of a field in probability theory. Definition 2 (field): Let (Ω, B) be a measurable space. We call field F a collection of subset of Ω such that :

Ω ∈ F if F ∈ F then F c ∈ F F is stable under f inite union A set A of
a field F is called an atom if and only if the only subsets which are also member of the field are the set itself and the empty set.

Definition 3 (base): A sequence of finite field

F n ; n = 0, 1, ... is called a basis of a field F if F n ↑ F and if G n is a sequence of atoms of F n such that G n ∈ F n and G n+1 ⊂ G n , n = 0, 1, 2, ... then ∩ ∞ n=1 G n = ∅. A sequence F n ; n = 0, 1, ... is called a basis of a measurable space (Ω, B) if F n
are a basis of a field F which generates B : B = σ(F). A field F is called standard if it has a basis. A measurable space (Ω, B) is called standard if it can be generated by a standard field i.e. B has a basis. We can now define the mutual information in a standard space provided by [START_REF] Wyner | A definition of conditionnal mutual information for arbitrary ensemble[END_REF].

Definition 4 (Mutual Information): Let (Ω, F, P ) be a standard probability space and X ∈ R, Y ∈ R two generic random variables: X

: Ω → A X , Y : Ω → A Y with (A X , B X ), (A Y , B Y ) two measurable spaces. Let F X = X -1 (A X ) and F Y = Y -1 (A Y ) the sub-σ-algebra of F induced by X and Y . Let P X = {A j } N X j=1 ⊂ F X and P Y = {B j } N Y j=1 ⊂ F Y (6)
be finite partitions of Ω. With these partitions we associate the following random variables:

X(ω) = j for ω ∈ A j with 1 ≤ j ≤ N X Y (ω) = j for ω ∈ B j with 1 ≤ j ≤ N Y . (7)
The mutual information between X ∈ R and Y ∈ R is then defined by: i(X; Y ) = sup

P X ,P Y I( X; Y ) ( 8
)
where I is the classical mutual information between two discrete random variables [START_REF] Cover | Elements of Information Theory[END_REF]. Similarly, the conditional mutual information is defined by

i(X; Y |Z) = i(X; Y, Z) -i(X; Z). (9)
The above framework is exploited to prove the following two theorems.

Theorem 1 (Scenario a): Assume that all random variables under use are defined on a standard probability space. Consider a joint probability density distribution f

(x 0 , x 1 , x 2 ) such that ∀x 0 ∈ X 0 , x1,x2 f (x 0 , x 1 , x 2 )dx 1 dx 2 = f 0 (x 0 ).
Then, the distribution f is implementable if and only if f (x 0 , x 1 , x 2 , y) verifies the following information constraint:

i f (X 0 ; X 2 ) ≤ i f (X 1 ; Y |X 0 , X 2 ) ( 10
)
where the arguments of the mutual information i f (.) are defined from f and f (x 0 , x 1 , x 2 , y) = f (x 0 , x 1 , x 2 )γ(y|x 1 ).

Theorem 2 (Scenario b): Assume that all random variables under use are defined on a standard probability space. Consider a joint probability density distribution f

(x 0 , x 1 , x 2 ) such that ∀x 0 ∈ X 0 , x1,x2 f (x 0 , x 1 , x 2 )dx 1 dx 2 = f 0 (x 0 ).
Then, the distribution f is implementable if and only if f (x 0 , x 1 , x 2 , y, x 1 ) verifies the following information constraint:

i f (X 0 ; X 2 ) ≤ i f (X 1 ; Y, X 2 ) -i f (X 1 ; X 0 , X 2 ) ( 11
)
with f (x0,x1,x2,y,x 1 )=f X 1 |X 0 X 1 X 2 (x 1 |x0,x1,x2)γ(y|x1)f (x0,x1,x2).
X 1 is an auxilary variable which helps us exploit the joint typicality between X 1 and X 1 as well as X 1 and X 2 to create coding and decoding schemes.

We see that the first theorem provides a full characterization of implementable densities in scenario a. The second theorem, which relies in part on Gel'fand and Pinsker coding [START_REF] Gel'fand | Coding for channel with random parameters[END_REF], provides a sufficient condition for implementability in scenario b; note that, as originally done in [START_REF] Gel'fand | Coding for channel with random parameters[END_REF], we introduce an auxiliary random variable X 1 to describe the information constraint. These theorems therefore allow one to know to what extent a team can coordinate under the assumed information structure. In general, to determine the ultimate performance in terms of average payoff, an optimization problem for the functional W (f ) has to be solved. The constraints are that: f has to be a density function; its marginal over (x 1 , x 2 ) has to be f 0 ; the density f as defined through the considered theorem has to meet the information constraint. In the next subsection, we apply the derived general result to a special case of probability distributions namely, Gaussian probability density functions. This allows one to exhibit a case where the information constraints can be quite easily expressed and to establish an interesting link with the work by Costa on dirty-paper coding [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF].

B. Gaussian case

Here, we assume that all variables which intervene in the information constraints are Gaussian. Agent 2 is assumed to observe the actions of Agent 1 through an additive white Gaussian noise channel: Y = X 1 + Z with Z ∼ N (0, 1). Let σ 2 0 , σ 2 1 , and σ 2 2 respectively denote the variances of X 0 , X 1 , and X 2 . The correlation coefficient between X i and X j , i = j is denoted by ρ ij . Using these notations and specializing [START_REF] Gamal | Network information theory[END_REF] and [START_REF] Steen | Counterexamples in Topology[END_REF] in the Gaussian case the following results can be proved; proofs are omitted here for obvious space limitations.

Proposition 3 (Information constraint in scenario a): Fix σ 2 0 . A necessary and sufficient condition for a joint probability density function f X0X1X2 to be implementable is that the variances and correlation coefficients verify the following inequality:

-(σ 2 2 ρ 2 01 -2ρ 01 ρ 02 ρ 12 + σ 2 1 ρ 2 02 + σ 2 0 ρ 2 12 -σ 2 0 σ 2 1 σ 2 2 ) × (σ 2 2 ρ 2 01 -2ρ 01 ρ 02 ρ 12 + σ 2 1 ρ 2 02 + σ 2 0 ρ 2 12 -σ 2 0 σ 2 1 σ 2 2 + ρ 2 02 ) ≤ 0.
Proposition 4 (Information constraint in scenario b): Fix σ 2 0 . Let α 2 ∈ R. A sufficient condition for a joint probability density function f X0X1X2 to be implementable is that the variances and correlation coefficients verify the following inequality:

(-ρ 2 01 + σ 2 0 + σ 2 0 σ 2 1 ) × (σ 2 2 ρ 2 01 - 2ρ 01 + 2α 2 ρ 12 + σ 2 1 ρ 2 02 + σ 2 0 ρ 2 12 -σ 2 0 σ 2 1 σ 2 2 ) -σ 2 0 σ 2 2 (ρ 2 01 - σ 2 0 σ 2 1 + α 2 2 ρ 2 02 -α 2 2 σ 2 0 σ 2 2 + α 2 2 σ 2 1 ρ 2 02 + α 2 2 σ 2 2 ρ 2 01 + α 2 2 σ 2 0 ρ 2 12 - 2α 2 σ 2 0 ρ 12 + 2α 2 ρ 01 ρ 02 -α 2 2 σ 2 0 σ 2 1 σ 2 2 -2α 2 2 ρ 01 ρ 02 ρ 12 ) ≤ 0.
For finding the information constraint for scenario b, we have assumed that X 1 = X 1 + α 0 X 0 + α 2 X 2 . This choice is inspired by the Costa's dirty paper coding scheme [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF]. The parameter α 2 is related to the choice we made for the auxiliary variable in Theorem 2 .

As seen through Proposition 4, the value of the parameter α 0 does not play any role in the constraint, showing that only the correlation level between the agents' actions X 1 and X 2 has to be tuned properly. The inequality constraint function of Proposition 4 can be shown to be strictly convex w.r.t. α 2 and the optimum point α 2 is given by:

α 2 = σ 2 0 ρ12-ρ01ρ02 ρ 2 02 -σ 2 0 (σ 2 2 -ρ 2 12 +σ 2 1 σ 2 2 )+σ 2 1 ρ 2 02 +σ 2 2 ρ 2 01 -2ρ01ρ02ρ12 . (12) When the communication signal-to-noise ratio SNR = E(X 2 1 ) E(Z 2 ) = σ 2 1 → ∞, it is seen that α 2 → 0 and the choice X 1 = X 1 is optimal. When SNR → 0, we see that α 2 → σ 2 0 ρ12-ρ01ρ02 (ρ 2 02 -σ 2 0 σ 2 2 )+σ 2 0 ρ 2 12 +σ 2 2 ρ 2 01 -2ρ01ρ02ρ12 .

IV. APPLICATION TO THE WITSENHAUSEN COST FUNCTION

A. The Witsenhausen cost function. Discussion

Taking the Witsenhausen cost (times minus one) as the payoff function to be minimized over a large number of stages and reducing it to a convex optimization problem, we find the limiting performance in terms of coordination for the two-agent team. However, note that this is significantly different from the original Witsenhausen's counterexample [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF] as we optimize over many stages. Witsenhausen's counterexample is also a two-agent team problem, where one of the agents can see the system state perfectly, whereas the second agent only sees a noisy version of the first agent's action. The aim for the team is to have control strategies for each agent which will minimize the expectation value of the cost. The original counterexample has only one stage and has been of great interest since it was proposed in 1968, especially because it was one of the first examples where actions played a dual role of communicating as well as optimizing, rendering the solution of the optimization problem non trivial. The specific payoff function function we consider in this section equals minus the Witsenhausen cost function that is,

w(x 0 , x 1 , x 2 ) = -k(x 0 -x 1 ) 2 + (x 1 -x 2 ) 2 , k ≥ 0.
(13) Note that the notations used here differ from those used in [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF].

Although this cost function is inspired by Witsenhausen's Counterexample, there are a few very important differences between the application of our theory to the Witsenhausen's Cost function and the Witsenhausen's counterexample. First, we optimise the average cost over a large time period, unlike in Witsenhausen's Counterexample where the one shot expectation value for the cost is minimised. Second, we assume strictly causal knowledge at Agent 2, whereas this is not the case in the original counterexample. To apply our approach to the original problem, albeit in the repeated case, one will need to consider a new scenario with the causality condition relaxed.

B. Numerical analysis

While the optimization problem is well defined, finding the joint distribution f X0X1X2Y = γ(y|x 1 ) * f X1X2|X0 * f 0 is not a trivial task. Eventhough f 0 is defined by the problem and γ(y|x 1 ) can be generated given the noise model, we still need to find f X1X2|X0 , and since the search space is over all possible distributions, the computational complexity of such a search is very high. Therefore, in this section we restrict ourselves to two cases which are simpler to handle, complexity wise, but might be sub-optimal.

Both the cases use the results proven in previous sections for the continuous variables. However for the first case, we use a quantizer to discretise (X 0 , X 1 , X 2 , Y) and optimise over them. This approach is inspired by the success of quantizers in finding better solutions for the original Witsenhausen Counterexample. To compare with a strategy most resembling a 'linear control' strategy, we choose the case where all variables are supposed to be gaussian, for which we had simplified the information constraint in terms of variances and covariances in section III-B. Clearly, it would be interesting to compare the two strategies, to see whether like for Witsenhausen Counterexample, non linear (discretisation) strategies outperform 'linear' (and thus continuous) strategies. This argument is used to motivate our choices of simulations, but the similarities are not so straightforward.

The following parameters are taken to be given for the problem: k = 1, σ 2 0 = 25, and Ez 2 = 1 and are common for both simulations (unless specified otherwise). Also, the information constraint considered is for scenario a.

Discrete case : we quantize all random variables to take nine values:

X 0 = X 1 = X 2 = Y = {-24
7 σ 0 , -16 7 σ 0 , -8 7 σ 0 , -3 7 σ 0 , 0, 3 7 σ 0 , 8 7 σ 0 , 16 7 σ 0 , 24 7 σ 0 }, with σ 0 = 5. Indeed, as we consider the continuous random variable X0 ∼ N (0, σ 2 ), we partition uniformly the continuous space that X0 is defined over, so that 99.99 % of the probability mass function lies in the chosen interval. It is well known that considering the interval [-4σ, 4σ] achieves this. We then calculate the transition probabilities P (Y |X 1 ) where Ỹ = X 1 + Z, Z is supposed to be a Gaussian random variable: Z ∼ N (0, 1), and Y is the discrete random variable that corresponds to Ỹ . This problem is computationally simpler as it is easy to calculate entropies for discrete random variables. The optimization problem can be solved using convex optimization algorithms. We search for the joint distribution over X 0 ×X 1 ×X 2 which minimizes the expectation of the Witsenhausen cost function. This approach is similar to the one used in [START_REF] Larrousse | Implicit coordination in 2-agent team problems. application to distributed power allocation[END_REF], except for the cost function and the information constraint which takes into account the observation noise for Agent 2. It gives us an approximation to the continuous case and valuable ideas as we will explain now.

Results : In Fig 1, for low SNR (-10dB), the probability is almost 1 for X 1 = 0. This is logical as σ 2 1 = 0.1 and thus Agent 1 does not have too much of a choice. For medium SNR (10 dB), we see the probabilities diverging slightly and resembling a Gaussian distribution. The same distribution is observed from SNR = 14 dB onwards as this leads to minimum cost. This can be seen from the graph of expected payoff vs SNR, Fig 2 . At 40 dB, one sees a distribution with higher variance but whether it can be a gaussian is tough to speculate given the lack of points. The salient feature of this approach is that it does not suppose any distribution for the variables a priori, and thus finds the optimal distribution, which is not necessarily Gaussian. However, it only searches for finite action alphabets, thus not attaining optimality in the general continuous case.

Gaussian Case : Guessing the optimal distributions to be Gaussian, we find a feasible set of variances and covariances which satisfy the information constraint calculated in Section 3. The feasible set is found by quantizing the search space for all the parameters. The search space are as follows:

σ 2 1 σ 2 z ∈ (-10, 40) dB , σ 2 2 σ 2 z
∈ (-20, 13) dB , and ρ 01 , ρ 12 , ρ 02 ∈ (0, (σ 0 σ 1 , σ 1 σ 2 , σ 2 σ 0 )). The other constraints of the optimization problem are trivially satisfied since we are taking all distributions to be probability distributions from the beginning.

For a given set of variance and covariance values which satisfy the information constraint, we find the expected payoff by evaluating the integral x∈{X0×X1×X2} f (x)w(x)dx. We do so using Monte Carlo simulations by randomly generating x 0 , x 1 and x 2 (100000 draws) which follow the joint distribution f (x) and averaging over the cost for the randomly generated triplets. We search over all the elements of the feasible set exhaustively to find the optimal joint Gaussian distribution which optimizes the Witsenhausen cost function.

Results : In Fig (which could be looked at as Signal to Noise Ratio (SNR)) increases, the expected cost reduces initially and then becomes constant. This is because on the x-axis, we are considering the maximum SNR available, and in both the cases, one sees that after a certain SNR*, the payoff remains constant as the agents choose strategies with SNR*.

We notice that the discrete strategy does better than the continuous gaussian strategy and while this is not conclusive proof, it leads us to suspect that discretisation does better One sees that the discrete strategy quickly beats the all-gaussian strategy, and achieves a much lower optimal cost than continuous alphabets, which would be similar to the original Witsenhausen problem where discrete Non-Linear strategies were shown to outperform the best affine strategies. Although this might just be an artefact of gaussian variables being sub-optimal distributions for our problem. For the Gaussian case, the optimal (σ * , ρ * ) = (σ * 1 , σ * 2 , ρ * 01 , ρ * 02 , ρ * 12 ) was found to be (4.6, 5.3, 4.8, 5.1, 4.9) and the optimal expected cost E(w) * associated with it to be 18.64. The information constraint is numerically found to be saturated for the optimal point. Note that the optimal correlations ρ * are not at their maximum values, given by σ i σ j ≥ ρ ij . This is precisely the information constraint which prevents the correlations to be at their maximum values, thus penalising future communication by Agent 1 and preventing the agents to coordinate better.

Ideally one should be able to do more extensive simulations for the discrete case, so as to get a better idea of the optimal distribution which could then be tackled using an approach similar to the gaussian case. However, the computational complexity prevents us from doing so currently.

V. CONCLUSIONS

We generalized the information constraint for the scenarios discussed in the article from a discrete case to a continuous case, showing equivalence between implementable distributions and reachable payoffs. This result is independent of the cost function, but it depends on the strategies and information structures. Thus we created a general framework for tackling problems with similar information structures, as well as showed a method of generalizing information constraint found for discrete cases to continuous ones. We also found an interesting link between scenario b and [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF] which needs to be further explored. Since Witsenhausen cost function is an important area for research, we applied our framework to optimize this cost function in our scenario.

While we could not provide simulations which solved the general optimization problem described in the article, we did gain some insights by simplifying the problem and reducing the computational complexity.

Further possibilities of exploration include better simulations with other types of distributions to see if they do better than Gaussian distributions, quantizing the alphabets with more points so as to approach continuity, as well as proving our results for other type of strategies and information structures. To compare a repeated version of Witsenhausen counterexample, one would need performance limit characterisation with a different Information structure, similar to ones discussed in [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF].

Fig. 1 .

 1 Fig. 1. Optimal probability distribution of X 1 at different maximum SNRs. SNR=40 dB is the optimal distribution globally

1 Fig. 2 .

 12 Fig.2. Scenario a; Plot of Expected payoff vs SNR for both the cases. One sees that the discrete strategy quickly beats the all-gaussian strategy, and achieves a much lower optimal cost

  2, we see that as E

	σ 2 1
	σ 2 z

ACKNOWLEDGMENT

Authors of this paper and particularly A. Agrawal would like to thank project LIMICOS -ANR-12-BS03-0005 for financing the project. We would also like to thank Pierre Gerold for his help in making our simulations faster.


N Choungmo Fofack

M Dehghan
email: mdehghan@cs.umass.edu

D Towsley
email: towsley@cs.umass.edu

M Badov
email: mbadov@cs.umass.edu

D L Goeckel
email: goeckel@ecs.umass.edu

On the Performance of General Cache Networks

Keywords: H.4 [Content-oriented Networking]: Cache Networks-Performance, Algorithms, LRU, FIFO, Random, TTL

. We then derive an analytical framework and a polynomial-time algorithm that approximate accurately performance metrics of arbitrary graph-based and heterogeneous TTL-based cache networks. Simulations show that our simplified methodology may accurately predict metrics of interest on networks of caches running popular replacement algorithms (e.g. LRU, FIFO, or Random) without restricting its scope of application to this interesting use case. Unlike existing approaches, ours scales as network and content catalog sizes increase.

INTRODUCTION

Over the past years, isolated data repositories running popular cache replacement algorithms have received significant attention. Nowadays, interest has shifted from caching systems in isolation to interconnected caches. The benefits of the latter approach come from storing contents in caches that are universally deployed or distributed across the network. This trend is mostly driven by the recent development of content-oriented technologies [START_REF] Ahlgren | A survey of information-centric networking[END_REF][START_REF] Kurose | Information-centric networking: The evolution from circuits to packets to content[END_REF]. The purpose is to adapt the network architecture to accommodate the current content usage patterns (Video-on-Demand, User-generated contents, etc.) with the potential to reduce congestion, improve content delivery speed as networks increase in size.

Network performance goals can be achieved in different ways. We focus on content distribution technologies [START_REF] Ahlgren | A survey of information-centric networking[END_REF] which allow on-demand caching through deployment of caches at various locations. Briefly speaking, when a data item is first requested, it is temporarily stored at some nodes and subsequent requests are served directly from these local copies. Therefore, users may experience a better quality of service. Obviously, the benefits of such in-network caching choices are highly tied to the performance of the underlying cache networks. These performance metrics can be significantly challenging to predict since the multi-cache systems that arise from content-oriented architectures are more complex, irregular, and heterogeneous. More precisely, these networks may have arbitrary topologies and their nodes may show different features (policies, capacities, routing tables, etc.).

When requests of all files share the same routing topology with content custodians of all files located at the same root nodes, bidirectional flows as described in Fig. 1 cannot occur. In this very specific case, requests flow in the same direction from child nodes to parents towards the root(s) and the network topology reduces to all nodes belonging to this routing topology or directed acyclic graph. We refer to this case as the unique routing topology model. Instances of this routing model have been studied in the literature on networks with linear [START_REF] Melazzi | A general, tractable and accurate model for a cascade of LRU caches[END_REF], tree [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF], polytree [START_REF] Choungmo Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Fofack | Modeling modern DNS caches[END_REF], feedforward topologies [START_REF] Berger | Exact analysis of {TTL} cache networks[END_REF][START_REF] Fofack | On models for performance analysis of a core cache network and power save of a wireless access network[END_REF][START_REF] Fofack | Approximate models for cache analysis with correlated requests[END_REF]. However, their approaches rely heavily on the unique routing topology model which is here a tree/hierarchical structure and the one-way child-to-parent forwarding schema of the network. This strong requirement makes their models not applicable to more general cases. Unlike, Algorithm 1 presented in Section 4 do not suffer from this limitations.

As reported in [START_REF] Kurose | Information-centric networking: The evolution from circuits to packets to content[END_REF], only a-NET model, introduced in [START_REF] Rosensweig | Approximate models for general cache networks[END_REF], addressed so far the performance of the tandem of two caches shown in Fig. 1 where requests are routed in opposite directions. This basic network is the atom of arbitrary interconnected caches. Unfortunately, [START_REF] Rosensweig | Approximate models for general cache networks[END_REF][START_REF] Kurose | Information-centric networking: The evolution from circuits to packets to content[END_REF] report relative errors of 15% and find that the violation of the Independent Reference Model (a.k.a. IRM or Poisson assumption) on miss streams of caches and aggregated request processes in the network is the major source of inaccuracy.

In this paper, we develop an analytical framework to assess performance metrics of cache networks by leveraging the concept of Time-To-Live (TTL)-based models recently introduced in [START_REF] Fofack | On models for performance analysis of a core cache network and power save of a wireless access network[END_REF] on the one hand. On the other hand, we apply two-moment matching techniques to fit hyper/shifted exponential renewal processes to general request processes [START_REF] Whitt | Approximating a point process by a renewal process, I: Two basic methods[END_REF]. Our main results are • an analytical and extensible framework that provides computationally efficient two-moment approximations of filtered, split, and merged request streams in the network; • a polynomial-time algorithm to approximate metrics of interest on large and heterogeneous graph-based networks; • Little's Law for caching systems and bounds of the TTLbased cache characteristic time are derived;

• event-driven simulation results showing that our framework is more accurate than the existing model [START_REF] Rosensweig | Approximate models for general cache networks[END_REF]. This paper is organized as follows. In Section 2, we describe the system under analysis and state our problem. In Section 3, we derive a Little's Law-like and characteristic equations enabling caching systems to be described via TTLbased models. We then present our algorithm to calculate characteristic times of isolated caches and our two-moment matching techniques to characterize filtered, split, and aggregated request streams. We describe our polynomial-time algorithm for network analysis in Section 4, show its accuracy in Section 5, and summarize our findings in Section 6.

MODEL

In this section, we state our problem on our toy network (Fig. 1). Then, we introduce the notation and assumptions that are used in our cache network model.

Problem formulation

Two sets of files are requested on the tandem of two caches of Fig. 1. User un requests the Kn files stored permanently at server sn. User u1's missed requests at cache 2 are routed towards server s1 through cache 1. The overall request arrival process at cache 1 is formed by (well-known) exogenous requests coming from user u2 and unknown miss processes of cache 2 and vice versa. Consequently, states of both caches become dependent. This would not occur if both servers were located at cache 2 as considered in [START_REF] Berger | Exact analysis of {TTL} cache networks[END_REF][START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF][START_REF] Choungmo Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Melazzi | A general, tractable and accurate model for a cascade of LRU caches[END_REF][START_REF] Fofack | Modeling modern DNS caches[END_REF]. Therefore, these existing models are limited since overall request processes at both caches are unknown and the strong assumptions (i.e. tree-based structure with content custodians at located at the root and the one-way child-to-parent request forwarding schema in the network) required by their cache-by-cache iterative models do not hold.

Network model

Let G = (V, E) be the graph representing a general and heterogeneous cache network, V = {v1, . . . , vN } the set of caches, and E ⊆ V × V the set of connections between caches. Additionally, the file catalog is denoted by F = {f1, . . . , fK }. Each file is stored permanently at one or more public servers attached to nodes in the network and there is at least one path between each pair of cache-server. Requests arrive exogenously and directly from users to some of the nodes {vn ∈ V } in this system. When a request for file fi arrives at a cache, it generates a cache hit if the file is located in the cache and a miss otherwise. In the latter case, the request is forwarded to other caches in the network based on the routing table at each cache, until the file is located in a cache or at the server storing the file. Then the file is forwarded along the reverse path taken by the request, and stored at each cache along the way. If the cache is full when a miss occurs, one of the files in the cache is selected based on an eviction policy to make room for the new file.

Workload model

We denote by Rn,i = {t k (n, i)} k≥0 the overall request process of file fi at cache vn where t k (n, i) is the arrival instant of the k+1-th request. Rn,i is formed by the superposition of an exogenous request process En,i (generated by local users of cache n), if any, and the endogenous request processes (generated by misses of other caches connected to cache n). Let λn,i be the rate of exogenous arrivals at cache vn, if any, and Λn,i the intensity of Rn,i. In this paper, we assume that Assumption 1 (Renewal). Exogenous request processes {En,i, ∀n, i} are renewal processes. Moreover, {En,i, ∀i} are independent at cache n.

At cache vn and for file fi, we denote by Xn,i the generic inter-arrival time of request in the process Rn,i, Fn,i(t) = P (Xn,i < t) its Cumulative Distribution Function (CDF), Fn,i(t) the CDF of its survival time, Nn,i(t) the counting process, Rn,i(t) = E[Nn,i(t)] the Renewal Function associated to Fn,i(t), and F * n,i (s) = E[e -sX n,i ] its Laplace-Stieltjes Transform (LST) for all t ≥ 0 and s ≥ 0.

Cache model

In this work, nodes of our network are endowed with a cache running a replacement algorithm that can be described with Renewing or Non-renewing TTL-based models introduced in [START_REF] Choungmo Fofack | Analysis of TTL-based cache networks[END_REF] and [START_REF] Fofack | Modeling modern DNS caches[END_REF] respectively. The renewing TTL-based model assigns a random value to the timer T1 of a file at cache miss instant t0 and later redraws this timer T k at each cache hit instant t k-1 as shown in Fig. 2(a). The non-renewing TTLbased model sets a random value to the timer T1 only at cache miss instant t0 as shown in Fig. 2(b). TTL-based models are used to describe space-driven policies (like LRU as shown in Fig. 2(a), FIFO/RND as shown in Fig. 2(b) [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]), time-based policies (like DNS [START_REF] Jung | Modeling TTL-based internet caches[END_REF], modern-DNS [START_REF] Fofack | Modeling modern DNS caches[END_REF]), and space-time policies (like Pra-TTL caches [START_REF] Choungmo Fofack | Analysis of TTL-based cache networks[END_REF], Amazon ElastiCache and Squid web cache [START_REF] Berger | Exact analysis of {TTL} cache networks[END_REF]).

Other considerations

As previous work, we are interested by the hit probability Hn,i (resp. the occupancy On,i), defined as the probability that file fi is in cache vn at request instants {t k (n, i)} k≥0 (resp. at any time instant t). The global (or average) hit probability Hn and the Miss Probability Ratio MPRn between predictions of our approximation and simulation results at cache vn are also calculated [START_REF] Rosensweig | Approximate models for general cache networks[END_REF].

Q = T2 sojourn time Q = T1 X1 X Z X Z+1 m0
We assume that all files have the same size [START_REF] Rosensweig | Approximate models for general cache networks[END_REF] or can be divided in small chunks of identical size [START_REF] Fricker | A versatile and accurate approximation for lru cache performance[END_REF]. Hence we express the cache size in terms of the number of files/chunks it can hold at any given moment. We also assume that files become available at cache vn once at miss instants {m n,l , l ≥ 0}.

SINGLE CACHE FRAMEWORK

In this section, we derive new exact results on caches. We then revisit the notion of characteristic time, generalize the concept to caching systems described by TTL-based models, and address operations that modify request streams.

On the steady state of isolated caches

For readability, we omit the subscript n that refers to the cache label. Let Ii(t) be a binary random variable indicating that file fi is in the cache at time t. Assume the limit Ii = lim t↑∞ Ii(t) exists. Since there is a copy of fi or not in the cache at any time depending on whether Ii = 1 or 0, the occupancy of file fi in the cache is calculated as it follows Oi = P (Ii = 1) = E[Ii]. Note that Oi denotes the expected number of copies of file i in the cache. Let I = K i=1 Ii be the total number of files in the cache at any time and Qi the sojourn time of file fi. For all caching systems, metrics of interest are related to the sojourn time of the file in the cache as follows.

Lemma 1 (Little's Law). For caching systems, the metrics of interest and expected sojourn time are related by

Oi = Λi(1 -Hi) × E[Qi], ∀ fi. (1)
Proof. By applying Little's law, (1) is established as follows. First, we note that the expected number of copies for file fi in a cache is Oi. Second, the rate at which file fi enters the cache is the miss rate Λi × (1 -Hi). Third, the expected time that file fi spends in the cache is E[Qi].

Unlike capacity-driven policies, the number of files cached using expiration-based policies is not bounded in principle. However, practical considerations require to not exceed a certain memory occupation level C. The following result provides conditions for the latter to hold.

Lemma 2 (Characteristic Equations). For caching systems, the total number of files in the cache at steady state I equals the cache capacity C almost surely if and only if

K i=1 O p i = C, p = 1, 2. (2)
Proof. Assuming (2), we show that

E[I] = C by noting that K i=1 Oi = K i=1 E[Ii] = E[I]. Then, Var[I] = 0 since Var[I] = K i=1 Var[Ii] = K i=1 Oi -K i=1 O 2 i . It follows that P |I -E[I]| ≥ η 2 ≤ Var[I] η 2 = 0, ∀η > 0, thanks to Chebychev's inequality. Now if I = C almost surely, then P (|I -C| ≥ η) = 0, ∀η > 0.
By calculating the first two moments of I with the condition {|I -C| ≥ η}, one can easily show that (2) holds necessarily .

Remark 1 (Che approximation [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF]). For capacitydriven policies (such as FIFO, LRU, RND, and variants [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF]), the total number of files in the cache at steady state is constant I = C and K i=1 Oi = C is necessary and sufficient.

For general TTL models, there are several ways to choose per-file timer distributions {Ti(t) = P (Ti < t), ∀fi} such that (2) holds. Here are three possible choices:

• Cache Characteristic Distribution. Here, files have the same TTL distribution Ti(t) = T (t), ∀fi characterized its mean T = E[Ti], ∀fi solution of (2) with p = 1.

Our cache characteristic distribution for general TTL-based models is consistent with Che's approximation [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] for capacity-driven policies where all files in the cache have (approximately) the same TTL distribution T (t) which depends on its mean only. [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] showed ingeniously that T (t) is approximately deterministic for LRU/FIFO caches (i.e. Ti ≈ E[Ti] ≈ T, ∀fi) and exponential for RND caches (i.e. Ti is exponentially distributed with mean E[Ti] ≈ 1/T, ∀fi).

• Cache Characteristic Moments. In this case, per-file TTL distributions are no more identical as in the previous case, but they have identical first two moments E[Ti] = T and Var[Ti] = σ 2 , ∀fi solutions of (2) with p = 1 and 2.

• Cache Characteristic Time. This case is stated as Assumption 2 (Characteristic Time). TTLs have the same mean E[Ti] = T , ∀fi and (2) holds with p = 1.

Assumption 2 allows two different files, say i and j, to be cached using two different TTL distributions Ti(t) and Tj(t). Given that only E[Ti] = T for all files fi, per-file optimal TTL distributions can be set according to per-file request processes as proved in [START_REF] Fofack | Performance evaluation of hierarchical ttl-based cache networks[END_REF]Prop. 3.4] and [START_REF] Fofack | Modeling modern DNS caches[END_REF]Prop. 4]. Assumption 2 is more general than Che's approximation (which is only a particular capacity-constrained TTL-based model with identically distributed file TTLs). In general, the characteristic time T in TTL-based cache models may be defined even with different per-file TTL distributions {Ti(t), ∀fi}. Its value T is bounded as follows.

Proposition 1 (Bounds). Under Assumption 2, the characteristic time T = E[Ti], ∀fi is bounded by

Tmin = C Λ ≤ T ≤ Tmax = C Λ × M (3)
where

M = K i=1 Λ i (1-H i ) Λ
is the average miss probability and Λ = K i=1 Λi is the total rate on the cache.

Proof. From their definitions, Qi and Ti are stochastically ordered as follows Qi ≥ Ti. By taking the expectation on the latter inequality and then replacing E[Ti] by the same constant T , we obtain E[Qi] ≥ T, ∀fi. Using the latter inequality in Lemma 1, we obtain Oi ≥ Λi(1 -Hi)T, ∀fi. Since ΛiE [Ti] is the expected number of copies of file fi requested within the time interval E[Ti] = T and Oi is the expected number of copies of file fi in the cache, it follows that Oi ≤ ΛiT, ∀fi. Applying (2) in Lemma 2 with p = 1, bounds of T are obtained as in (3).

Remark 2 (Stationary requests). Proofs of Lemmas 1 and 2 and Proposition 1 do not require Assumption 1, but stationarity and ergodicity of request processes only.

Metrics of interest and characteristic time

In this section, we present metrics of interest and our characteristic time approximation (CTA) on isolated caches. We consider that request streams are described by hyper or shifted-exponential renewal processes based on the value of the square coefficient of variation (c 2 v ) of inter-request times [START_REF] Whitt | Approximating a point process by a renewal process, I: Two basic methods[END_REF]. When

c 2 v,i ≥ 1, Fi(t) is a hyper-exponential CDF i.e. Fi(t) = 1 -(p1e -θ 1 t + p2e -θ 2 t ), p1 + p2 = 1, t ≥ 0, p1θ -1 1 = p2θ -1 2 ; otherwise, it is a shifted exponential CDF i.e. Fi(t) = 1 -e -θ(t-τ ) , t ≥ τ .
It is known from [START_REF] Choungmo Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Fofack | Modeling modern DNS caches[END_REF] that metrics of interest of file fi in non-renewing (resp. renewing) TTL-based cache models are given by Hi

= E[R i (T i )] 1+E[R i (T i )] (resp. Hi = E [Fi(Ti)] ) and Oi = Λ i E[T i ] 1+E[R i (T i )]
(resp. Oi = E Fi(Ti) ). We derive explicit formulas for hyper/shifted-exponential renewal request processes in our technical report [START_REF] Choungmo Fofack | An approximate analysis of heterogeneous and general cache networks[END_REF]Sect.4].

The value of T is approximated using a novel technique described in Algorithm 1. Its convergence on isolated caches is studied as follows. Thanks to Lemma 2, the characteristic time T = E[Ti], ∀fi and TTLs {Ti} satisfy

C = K i=1 ΛiE[Ti] 1 + E [Ri(Ti)] and C = K i=1 E Fi(Ti) (4)
for non-renewing and renewing TTL-based models respectively. Under Assumption 2, we apply Jensen's inequality and show that

K i=1 Oi ≥ K i=1 Λ i T 1+R i (T )
for non-renewing TTL models since Ri(t) is a concave function when Fi(t) is concave. It is easy to check that the hyper/shifted-exponential CDFs are indeed concave functions. Since (4) holds, it follows that

K i=1 Λ i T 1+R i (T ) ≤ C.
For renewing TTL-based models, we rely on similar arguments. Thanks to Assumption 2 and Jensen's inequality, K i=1 Oi ≤ K i=1 Fi(T ) since Fi(t) is a concave function. However, it follows from (4) that

K i=1 Fi(T ) ≥ C. Let us denote by φ(T ) = C-K i=1 Λ i T 1+R i (T ) (resp. φ(T ) = C -K i=1 Fi(T )
) in the case of non-renewing (resp. renewing) TTL based models. The function φ(T ) is strictly decreasing, twice continuously differentiable, and the root is unique and simple (multiplicity is one). Thanks to Proposition 1, the zero of φ(T ) belongs to [ C Λ ; ∞). Algorithm 1 implements the secant method to approximate the zero of φ(T ) with the sequence:

∀I ≥ 0, T (0) = C
Λ and T (I+1) = T (I) + T (I) -0 φ(T (I) )-φ(0) φ(T (I) ). Since T (0) is tight lower bound (and thus a good estimate of T ) and φ(T ) is strictly decreasing (and not wiggly) in [T (0) ; ∞), it is known that the convergence of the secant method (and thus Algorithm 1) is superlinear with an order of convergence equal to the golden ratio 1+ √ 5

2 .

Remark 3 (Quadratic convergence). Algorithm 1 converges quadratically if Newton's method is implemented. This result holds also for general and concave CDF Fi(t).

Cache network operations

Exact characterizations of miss, split, and aggregated request processes exist, but they are too complex and computationally expensive for practical interest [START_REF] Berger | Exact analysis of {TTL} cache networks[END_REF][START_REF] Fofack | On models for performance analysis of a core cache network and power save of a wireless access network[END_REF][START_REF] Choungmo Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Melazzi | A general, tractable and accurate model for a cascade of LRU caches[END_REF][START_REF] Fofack | Modeling modern DNS caches[END_REF]. Hence, for each cache operation we calculate only the first two moments of inter-request times in the resulting process and we use a two-moment matching technique to fit them to hyper/shifted-exponential renewal processes [START_REF] Whitt | Approximating a point process by a renewal process, I: Two basic methods[END_REF].

Filtered request streams (Miss process)

For non-renewing (resp. renewing) TTL-based cache models, the two first moments of inter-miss times of file fi are

E[Yi] = E[X i ] (1+L * i (0)) -1 and E[Y 2 i ] = E[X 2 i ] (1+L * i (0)) -1 -2E[Xi](L * i ) (0) (resp. E[Yi] = E[X i ] (1-L * i (0)) and E[Y 2 i ] = E[X 2 i ] (1-L * i (0)) - 2E[X i ](L * i ) (0) (1-L * i (0)) 2 ) where explicit formulas of L * i (s) = ∞ 0 e -st (1 -Ti(t))dRi(t) (resp. L * i (s) = ∞ 0 e -st (1 -Ti(t))dFi(t)
.) The LSTs L * i (s) take simple expressions when requests are described by hyper/shifted exponential renewal processes previously introduced. One can easily check that our closed-form expressions of E[Yi] and E[Y 2 i ] are consistent with the formulas derived by Melazzi et al. [START_REF] Melazzi | A general, tractable and accurate model for a cascade of LRU caches[END_REF] in the specific case of where TTLs are constant (and not random variables as generally assumed in this paper) and always redrawn at cache hit (and thus limited to the model described in Fig. 2(a).)

Split request streams (Routing departures)

In this section, we consider that a cache may route its missed requests towards J possible caches or destinations. Our aim is to describe (i.e. calculated the two first moments of) the sequence of requests that are forwarded to the jth destination. Existing works [START_REF] Rosensweig | Approximate models for general cache networks[END_REF][START_REF] Fofack | Performance evaluation of hierarchical ttl-based cache networks[END_REF][START_REF] Fofack | Modeling modern DNS caches[END_REF][START_REF] Berger | Exact analysis of {TTL} cache networks[END_REF] consider that this request forwarding operation is memoryless and they model the splitting process by a Bernoulli process. However, several destinations are often allowed within more realistic networks to enable load balancing or congestion awareness based on a recent history. We therefore propose to model this request splitting operation by using a discrete time Markov chain process {ξm l , l ≥ 0} on a state space {1, 2, . . . , J} such that requests occurring at miss instants {m l , l ≥ 0} are sent to the j-th destination if ξm l = j. Further, we assume that the Markov chain {ξm l , l ≥ 0} is lumpable and without loss of generality we characterize the process described requests sent to destination (or next-cache) labelled 1. First, the J states of {ξm l , l ≥ 0} are lumped into two states I = {1} and O = {2, . . . , J}. Second, we consider the resulting two-state Markov chain {ξm l = I or O, l ≥ 0} and its transition probabilities rI,I = P (ξm l+1 = I|ξm l = I) and rO,I = P (ξm l+1 = I|ξm l = O)). Its stationary distribution is rI = P (ξm l = I) = r O,I 1+r O,I -r I,I . The first two moments of inter-request times Yi→1 of file fi at destination 1 are related to those of the original process.

E [Yi→1] = E[Y i ] r I and E Y 2 i→1 = E[Y 2 i ] r I + 2(1-r I )E[Y i ] 2 r I r O,I .

Aggregated request streams (Routing arrivals)

In this section, we consider that a cache may be fed by requests originating from several sources (e.g. exogenous requests sent by its local users, and the endogenous missed requests forwarded by other caches). Our goal is to characterize the two first moments of inter-request times in the overall arrival process. It is known from [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF][START_REF] Choungmo Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Fofack | Modeling modern DNS caches[END_REF][START_REF] Berger | Exact analysis of {TTL} cache networks[END_REF] that the exact characterization of this aggregated process may be significantly complex and [START_REF] Rosensweig | Approximate models for general cache networks[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] showed that the Poisson assumption is source of inaccuracy. Hereafter, we describe a computationally-efficient and accurate methodology to approximate this superposed process. Without loss of generality, we consider that requests arrive at a cache from J sources labelled j = 1, 2, . . . , J. Let E[Xi,j] and E X 2 i,j be the first and second moment of inter-request times of source j. If the calculation of the first moment of interarrival times E[Xi] of requests for file fi is straightforward

E[Xi] = J j=1 E[Xi,j] -1 -1
, we propose a new formula to

approximate the second moment E[X 2 i ] in the aggregated process. E[X 2 i ] = 1 + c 2 i E[Xi] 2 where c 2 i = wic 2 a + (1 -wi)c 2 p , c 2 a = J j=1 E[X i ] E[X i,j ] c 2 i,j , c 2 p = 1, (5)
c 2 i,j = E X 2 i,j /E[Xi,j] 2 -1
, and the per-file weight wi is

w -1 i = 1 + 1 -C×E[X i ] -1 K i=1 E[X i ] -1 2 J j=1 E[X i ] E[X i,j ] 2 -1 (6)
Theoretical details of our aggregated process approximation are provided in our technical report [START_REF] Choungmo Fofack | An approximate analysis of heterogeneous and general cache networks[END_REF]Sect.5.1.3].

CACHE NETWORK APPROXIMATION

In this section, we extend our single cache framework to approximate performance metrics of heterogeneous cache networks with arbitrary topology. First, we define the notion of routing topology. We then describe our cache network algorithm (CNA) to handle general networks where bidirectional flows may occur in presence of multiple routing topologies.

Case of multiple routing topologies

The routing topology of a file refers to the subset of nodes that receive/exchange requests of that file. In this paper, we consider that requests of each file are routed as a Directed Acyclic Graph (DAG) built on top of the arbitrary network topology. In the following, the terms DAG and routing topology are used equivalently.

In Fig. 3 for instance, two classes F1 and F2 of content items are shown in green and blue respectively. Content items of F1 are stored permanently at the server connected to node v5 and their requests are routed on the tree (displayed in blue) while those of class F2 are permanently available at two different servers and their requests are routed on the polytree (displayed in green). Requests of items of classes F1 and F2 are moving in opposite directions (or equivalently it exists a bidirectional flow) between nodes v3 and v4. Hence, states of caches 3 and 4 are dependent. Their TTLs T3 and T4 are coupled and solutions of a system of equations (Cf. Lemma 2). Instances of such systems of equations are available in our technical report [7, Eq.( 15)] for more details.

Our algorithm to tackle this issue is described as follows.

• Y,n,i } at each cache vn ∈ V . • Procedure: Algorithm 1 starts with an initialization step where all caches are assumed to have miss probabilities of one. The consequence is that the miss process of a node is initialized by its aggregated arrival processes. Then the characteristic times are also initialized to their lower bound. After, this initialization step, Algorithm 1 updates the miss processes of the caches using the initial value of the TTLs. Then it recalculates the aggregated streams; finally, it updates the TTL values at each cache. Algorithm 1 halts when all TTL values at all nodes of the network have converged.

Input: network topology G(V, E) of size N = |V | , cache neighbours N (n) ⊆ V ,

Practical concerns on Algorithm 1

In this section, we show the convergence of our cache network algorithm, its polynomial-time complexity, and its properties for large scale implementations. On the convergence. Intuitively, Algorithm 1 converges since sequences of TTL values are increasing and bounded (see Proposition 1). More formally, Algorithm 1 finds the root T = (T1, . . . , TN ) of the system of equations Φ ( τ ) = (Φ1 ( τ ) , . . . , ΦN ( τ )) = 0, where Φ(.) : R N → R N , τ = (τ1, . . . , τN ) is the characteristic time vector, and Φn( τ

) = Cn -K i=1 Λ n,i τn 1+R n,i (τn) (resp. Cn -K
i=1 Fn,i(τn)) for non-renewing (resp. renewing) TTL based models. Note that the dependence of Φn( τ ) on the characteristic times τm, (m = n, vm ∈ V ) is strongly embedded in the aggregated request arrival process at cache vn via the CDFs {Fn,i(.)}. Since ∇Φn( τ ) < 0 at ∀ τ > 0 and ∂ 2 Φn( τ )

n ← K i=1 Λ (1)
n,i ; T (1) n ← Cn/Λ (1)
n ; 16 end 17 while vn by using the secant method i.e. approximating the slope with Φn( T (I-1) )-Φn( 0)

1 N N n=1 (T (I) n -T (I-1) n ) 2 > do 18 I ← I + 1;
T (I-1) n
where T (I-1) is the characteristic vector at the previous iteration. Hence, Algorithm 1 converges superlinearly in each component Φn( τ ). The convergence is quadratic if Newton's method is used instead. On the complexity. Instructions in bold font are basic operations of Algorithm 1. Its complexity is of order of O(N IK) where I the total number of iterations is bounded by I ≤ ∆ 2 G with ∆G the diameter of the network topology. The equality holds i.e. I = N 2 in the (worst) case of the tandem network of N nodes (similar to Fig. 1) with bidirectional flows through all nodes. In the case of unique routing topology model which is widely studied in the literature (e.g. networks with linear [START_REF] Melazzi | A general, tractable and accurate model for a cascade of LRU caches[END_REF], tree [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF], polytree [START_REF] Choungmo Fofack | Analysis of TTL-based cache networks[END_REF][START_REF] Fofack | Modeling modern DNS caches[END_REF], feed-forward topologies [START_REF] Berger | Exact analysis of {TTL} cache networks[END_REF]), Algorithm 1 needs only I = ∆G iterations. On the implementation. Approximations [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF][START_REF] Melazzi | A general, tractable and accurate model for a cascade of LRU caches[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Rosensweig | Approximate models for general cache networks[END_REF] are limited by the size and tree-based topology of networks. Unlike, Algorithm 1 scales easily as the network and catalog sizes increase. It can be implemented in distributed MapReduce jobs of Apache Giraph software [START_REF]Apache Giraph[END_REF]. During the initialization phase, each job associated to a node reads the network and routing configurations. It then stores labels of its neighbours and identifiers of files it may receive. During each super-step, each job executes once the while-loop of Algorithm 1 and exchanges parameters of its node request streams and characteristic time at the end. All jobs halt if the root mean squared error of TTLs is less than a given threshold.

EVALUATION RESULTS

In this section, we evaluate the accuracy of our model by comparing its predictions of per-file hit probabilities on networks where caches are running space-driven policies like Least Recently Used (LRU), Random replacement (RND), and First-In-First-Out (FIFO). Indeed, the existence of deterministic (resp. exponentially distributed) characteristic times for LRU and FIFO (resp. RND) policies (see [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] and [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] for more details) allows us to describe them with TTL-based models as shown in Figure 2. We consider as "exact" the metrics of interest obtained via long event-driven simulations (≈ 16.77 × 10 6 events generated). Files exogenous requests arrive at some nodes of the network with rate Λ = 1 and Zipf popularity of parameter α = 0.7.

Characteristic time approximation (cta)

TTL models of isolated LRU, FIFO, and RND caches produce accurate predictions of per-file hit probabilities [START_REF] Che | Hierarchical web caching systems: modeling, design and experimental results[END_REF][START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF][START_REF] Melazzi | A general, tractable and accurate model for a cascade of LRU caches[END_REF]. Hence, our goal here is to validate the accuracy of Algorithm 1 when approximating cache characteristic times. We consider caches of size C = 100, a catalogue of size K = 10 5 , and Poisson request traffic with total request rate Λ = 1. The characteristic times or TTLs T cta POLICY where POLICY is either LRU, RND or FIFO are calculated by solving [START_REF]Apache Giraph[END_REF] with p = 1 of Lemma 2. Meanwhile, their approximate values T

(n)

POLICY are given by Algorithm 1. Figure 4 shows that our algorithm converges after one iteration starting from the lower bound T (0) = C/Λ to the cache characteristic times. This convergence was also observed with Interrupted Poisson Processes (IPPs) of same rate Λ = 1 and scv of inter-request times c 2 v = 1.5.

Thanks to these preliminary experiments, we made two interesting observations not yet reported in the literature.

For both Poisson and IPP request models, we observed that characteristic times of FIFO and RND caches are approximatively equal. Moreover, miss streams of FIFO (resp. RND) caches fed by Poisson traffic are accurately described by shifted-exponential renewal processes.

Performance metrics on cache networks

In this section, exogenous request streams are still described by Poisson processes. Moreover, we call Poisson approximation the specialization of Algorithm 1 when considering the first moment of inter-request times only (and setting wi = 0, ∀fi in ( 5)). Another specialization, that we call the Whitt approximation, is obtained when wi = 1, ∀fi in [START_REF] Fofack | On models for performance analysis of a core cache network and power save of a wireless access network[END_REF]. Finally, our general methodology when wi ∈ [0, 1] in (5) as calculated in (6) will be the Hybrid approximation. These approximations were evaluated extensively under various network configurations used for a-NET model [START_REF] Rosensweig | Approximate models for general cache networks[END_REF] and our Hybrid approximation show better accuracy than others. Due to lack of space, we only report part of results for some metrics of interest. Additional numerical results can be found in our technical report [7, Sect.6.2 & 6.3].

Poisson approximation and a-NET model

The Poisson approximation and IRM traffic model used by a-NET model [START_REF] Rosensweig | Approximate models for general cache networks[END_REF] can be seen as assuming that all request streams are described by Poisson processes at each node of the network. We evaluate our Poisson approximation and a-NET model on linear, binary tree, and random (i.e links are drawn uniformly at random) networks of LRU caches. For these experiments, we consider that Poisson requests arrive exogenously at each cache. Due to lack of space we only report per-file hit probabilities for the random network at the node directly connected to the servers. On all simulated cache networks (Cf. [7, Sect.6.1]) and in particular for the random network (see Fig. 5), we observed that the Poisson approximation is as accurate as a-NET model [START_REF] Rosensweig | Approximate models for general cache networks[END_REF]. Hence, only Poisson approximation is used later in this section on other network configurations for comparison purposes.

Accuracy of our Hybrid approximation

Large tree networks. We compare the Poisson, Whitt, and Hybrid approximations on homogeneous and heterogeneous tree cache networks where requests occur on leaf nodes only. In the former case, we consider a ternary tree network of depth seven having 1093 LRU caches; and, a 4-ary tree of depth five having 341 caches with capacities chosen uniformly at random within the interval [50, 150] and replacement policies are selected among the FIFO, RND, and LRU policies in the latter case. The catalogue size is K = 10 4 . In both cases (see Figs 6 and7), Poisson approximation overestimates the metrics of interest while Whitt approximation underestimates them. However, the Hybrid approximation outperforms others for predicting per-file hit probabilities and produces miss probability ratios close to one. Other network settings such as random networks where requests arrive on edge nodes only can be found in [START_REF] Choungmo Fofack | An approximate analysis of heterogeneous and general cache networks[END_REF].

Large random networks. Finally, we consider a large random network of 100 LRU caches with capacities Cn ∈ [50, 150] and a catalogue of size K = 10 4 . We consider exogenous Poisson request streams at all caches. As shown in Fig. 8, our Hybrid approximation is still accurate.

CONCLUSION

Performance analysis of general and heterogeneous cache networks was the main goal of this work. Relying on TTLbased models, we developed an analytical framework and an accurate polynomial-time algorithm to address this problem in a quite general scope since existing models were limited either by the IRM assumption, tree topology, one-way child-to-parent forwarding schema, homogeneous nodes, etc. Moreover, we showed the existence of Little's Law-like and we defined new characteristic features (Characteristic Equations/Moments/Distribution/Time) for caching systems behaving as generally distributed TTL-based models under stationary and ergodic request processes. Finally, simulations showed that our (Hybrid) approximation is more accurate than the existing models which addressed arbitrary cache networks since our approach captures content popularity, temporal locality, and basic cache operations on request streams in a better way by relying on hyper/shiftedexponential renewal processes. As future work, we plan to weaken our renewal assumption and to extend our framework to cache networks under correlated requests.

Figure 1 :

 1 Figure 1: Tandem of two caches with bidirectional flows

Figure 2 :

 2 Figure 2: Behaviour of a file in the cache.

Figure 3 :

 3 Figure 3: Two routing topologies and bidirectional flows.

∂τ 2 nAlgorithm 1 : 2 7 Set aggregate streams to exogenous process 8 else 9 Merge 11 Set miss streams to aggregated processes 12 Split

 2127891112 > 0, Algorithm 1 calculates updates of the characteristic time T (I) n at cache CNA on arbitrary graph G(V, E) for each node vn ∈ V do 3 Initialize per-file miss probabilities to one 4 Initialize per-file miss and aggregate processes 5 for each file fi ∈ F such that vn ∈ DAGi do 6 if vn is an edge of DAGi then the file request streams (Sect. 3.3.3) if multiple sources: ∀v l ∈ DAGi & vn ∈ N (l) 10 end the file miss process (Sect. 3.3.2) if multiple destinations: ∀vm ∈ DAGi ∩ N (n)

M

  19 for each node vn ∈ V do 20 Update per-file miss and aggregate processes 21 for each file fi ∈ F such that vn ∈ DAGi do 22 Calculate the file miss process (Sect. 3.3.1) 23 Split the file miss process (Sect. 3.3.2) if multiple destinations: ∀vm ∈ DAGi ∩ N (n) 24 Merge the file request streams (Sect. 3.3.3) if multiple sources: ∀v l ∈ DAGi & vn ∈ N (l) 25 Calculate per-file CDFs (Appendix. A) and metrics of interest (Sect. 3.2) 26 end 27 Update the characteristic time (Sect. 3.2) 28 if cache policy Pn is Non-renewing TTL then 29

Figure 4 :

 4 Figure 4: Approximations of TTLs T cta POLICY for LRU, RND and FIFO policies with Algorithm 1. Poisson arrivals (Λ = 1) and Zipf popularity (α = 0.7). C = 100, K = 10 5 .

Figure 5 :

 5 Figure 5: Simulations (Poisson arrivals Λ = 1 and Zipf popularity α = 0.7), Poisson approximation, and a-NET model on 10 caches random network. K = 100, C = 5.

Figure 6 :

 6 Figure 6: Simulations (Poisson arrivals on leaves and Zipf popularity). Poisson, Whitt, and Hybrid approximations. Ternary tree of LRU caches, Depth 7, K = 10 3 , C = 100.

Figure 7 :

 7 Figure 7: Simulations (Poisson arrivals on leaves, Zipf popularity). Poisson, Whitt, and Hybrid approximations. Heterogeneous ternary tree, depth 5, K = 10 4 , C ∈ [50, 150].

Figure 8 :

 8 Figure 8: Hybrid approximation on a large random network of N = 10 2 caches, K = 10 4 , C ∈ [50, 150].

  policies Pn and sizes Cn, file catalogue F of size K = |F|, routing topologies {DAGi, fi ∈ F }, exogenous requests {rate λn,i and scv c 2 n,i , vn ∈ V , fi ∈ F }. • Output: characteristic time Tn, average miss probability M n, per-file metrics of interest {hit probability Hn,i and occupancy On,i}, per-file aggregated request process {rate Λn,i and scv c 2 X,n,i }, per-file miss request process {rate νn,i and scv c 2

ACKNOWLEDGMENTS

The authors are deeply grateful to Christian Tanguy (Colleague at Orange Labs, Issy-Les-Moulineaux) for its comments and stimulating discussions on this work.