Daniele Astolfi

Romain Postoyan

Nathan Van De Wouw

Emulation-based output regulation of linear networked control systems subject to scheduling and uncertain transmission intervals

We investigate output regulation for linear networked control systems using the emulation approach. We consider a regulator solving the problem for linear systems in the absence of the network, by following the Francis-Wonham framework. Next, the network is taken into consideration, in particular the induced time-varying inter-transmission intervals and scheduling constraints, and we model the overall system dynamics as a hybrid system. We show that only practical regulation can be achieved in general since the steady-state control input steering the output to zero cannot be generated in the networked context (in general). Explicit upper bounds on the output asymptotic gain and on the maximum allowable transmission interval guaranteeing boundedness of the closed-loop trajectories are provided, which are shown to be related.

INTRODUCTION

By output regulation, we refer to the problem in which we aim to control a given output of a plant to asymptotically track a prescribed trajectory and/or to asymptotically reject undesired disturbances, while keeping all the trajectories of the system bounded. In such framework, we suppose to know the model generating the disturbances and references, denoted in the following as exosignals. For linear systems, an elegant solution was proposed by Francis, Wonham, see [START_REF] Francis | The internal model principle of control theory[END_REF] with the clear delineation of the internal model principle. The objective of this work is to investigate whether output regulation can be achieved in the context of linear networked control systems (NCS), namely when the regulator and the linear plant communicate over a multi-purpose network, which may be shared with other tasks. The challenge is that the communication channel induces undesired phenomena, such as uncertain transmission intervals, scheduling, network delays and packet loss, which may destroy the desired regulation properties, if ignored.

To this date, works on NCS mainly focused on modelling, stabilization and observer design (see, e.g., [START_REF] Cloosterman | Controller synthesis for networked control systems[END_REF], [START_REF] Heemels | Networked control systems with communication constraints: Tradeoffs between transmission intervals, delays and performance[END_REF], [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF] [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF], [START_REF] Postoyan | A framework for the observer design for networked control systems[END_REF]), while only few works have considered the out-put regulation problem in the networked context. Some solutions have been proposed to address this problem for discrete-time linear systems and sampled-data linear systems (see, e.g. [START_REF] Sureshbabu | On output regulation for discrete-time nonlinear systems[END_REF], [START_REF] Lawrence | Output regulation for linear systems with sampled measurements[END_REF], [START_REF] Fujioka | Output regulation for sampled-data feedback systems: Internal model principle and h ∞ servo controller synthesis[END_REF], [START_REF] García-Sandoval | Robust tracking for oscillatory chemical reactors[END_REF], [START_REF] Antunes | Output regulation for non-square linear multi-rate systems[END_REF]). These works do not take into account the inter-sampling behavior when the plant has continuous-time dynamics, and are not suited to analyze some network phenomena, such as time-varying sampling, scheduling and packet loss. Other researchers studied the related, though different, problem of output tracking for nonlinear NCSs (see, e.g., [START_REF] Postoyan | Tracking control for nonlinear networked control systems[END_REF], [START_REF] Van De Wouw | Tracking control for sampleddata systems with uncertain time-varying sampling intervals and delays[END_REF], [START_REF] Gao | Network-based H ∞ output tracking control[END_REF]). The problem of output regulation for minimum phase single-input single-output nonlinear systems when only the measurement is sampled has been addressed in [START_REF] Astolfi | Emulation-based semiglobal output regulation of minimum phase nonlinear systems with sampled measurements[END_REF], while in [START_REF] Liu | Event-triggered global robust output regulation for a class of nonlinear systems[END_REF], it is shown that practical output regulation in presence of event-triggered policies can be achieved for the same class of systems. Nevertheless, output regulation of NCS remains a largely open problem, as results adapted to network effects, such as uncertain time-varying sampling, scheduling, network delays, quantization, are missing to the best of our knowledge.

A typical approach for controller design for NCS is using emulation, where the design of the regulator is performed by assuming that the network is absent. As next step, network phenomena are taken into account in the closedloop model and their effects on the stability and perfor-mance of the overall system are analyzed. In this work, we follow this approach to address the output regulation of linear NCS, as we believe that a full understanding of such framework is missing in the literature. The analysis follows the ideas of emulation approach for NCS presented in [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF]; [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF] for point stabilization, by means of the hybrid formalism of [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF]. Note that, the input-to-state stability (ISS) properties of the unperturbed closed-loop systems, see, e.g., [START_REF] Cloosterman | Controller synthesis for networked control systems[END_REF] or [START_REF] Heemels | Networked control systems with communication constraints: Tradeoffs between transmission intervals, delays and performance[END_REF] allow to conclude only boundedness of the closed-loop trajectories in presence of exosignals. Therefore, a thinner analysis is needed to conclude whether asymptotic output regulation can be achieved.

The main contributions of the current paper are as follows. First a hybrid model for the closed-loop regulated system including the effects of time-varying sampling and scheduling is constructed, although we believe that it is possible to include transmission delays in the analysis by suitably combining the presented results with those in [START_REF] Heemels | Networked control systems with communication constraints: Tradeoffs between transmission intervals, delays and performance[END_REF]. Secondly, an explicit bound for the maximum allowable transmission interval (MATI) guaranteeing boundedness of the trajectories of the closed-loop system, in presence of the exosignals, is derived. Next, a performance analysis is provided. We show that, with such architecture, asymptotic output regulation cannot be achieved in general, since the emulated version of the control is not able to generate the right steady-state input able to steer the output error constantly to zero2 . In other words, the internal model property of the regulator is destroyed. The characteristics of the plant, exosignals and the network are related to the ultimate bound of the regulated errors. This bound can be used for both analysis and network design and represents the main novelty of this work. Finally, we highlight two particular situations in which asymptotic output regulation is still preserved, namely the case of constant exosignals and the case in which the plant input is directly connected to the controller (in other words, only the plant output is transmitted over the network, like in [START_REF] Astolfi | Emulation-based semiglobal output regulation of minimum phase nonlinear systems with sampled measurements[END_REF]). This finding is consistent also with the work in [START_REF] Postoyan | Tracking control for nonlinear networked control systems[END_REF] on the tracking control of NCS, and suggests that different architectures need to be used if asymptotic output regulation is sought.

The paper is organized as follows. The problem is formally stated in Section 2. The main results are given in Section 3 and a numerical example is provided in Section 4. Section 5 contains the conclusions. The proofs of the main results are given in the Appendix.

Notation Let R := (-∞, ∞), R ≥0 := [0, ∞), N := {1, 2, . . .}, N 0 := {0} ∪ N.
The notation |x| stands for the standard Euclidean norm of x ∈ R n , and x A := inf a∈A |x-a| denotes the distance from x to a set A ⊆ R n . Given x ∈ R n and y ∈ R m , we denote (x, y) = (x T , y T ) T . We consider hybrid systems of the form [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF]

ẋ = F (x), x ∈ C, x + = G(x), x ∈ D, where
x ∈ R nx is the state, C is the flow set, F is the flow map, D is the jump set and G is the jump map. We refer to [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF] for the definitions of solutions to the hybrid system, maximal solutions and pre-compact solutions. We say that a compact set A ⊂ R nx is uniformly globally exponentially stable (UGES) for the hybrid system if all maximal solutions are complete and there exist M, λ > 0 such that, for any x(0, 0) ∈ R nx , x(t, j) A ≤ M exp(-λ(t + j)) x(0, 0) A for all (t, j) ∈ dom x.

PROBLEM FORMULATION

Preliminaries on linear output regulation

We recall in this section the basic ingredients of linear output regulation in continuous-time, see [START_REF] Francis | The internal model principle of control theory[END_REF] or (Byrnes et al., 2012, Section 1.3) for more details. Consider a system of the form ẋ

= Ax + Bu + P w y = Cx + Qw, (1)
where x ∈ R nx is the state, u ∈ R nu is the control input and y ∈ R ny is the measured output that we aim to regulate to zero, with n x , n u , n y ∈ N and n u ≥ n y . The exogenous variable w ∈ R 2nω+1 , n ω ∈ N 0 , is assumed to be generated by an exosystem of the form ẇ = Sw, S = blckdiag(S 0 , S 1 , ..., S nω )

where

S 0 = 0, S i = 0 ω i -ω i 0 , ω 1 < . . . < ω nω ∈ R.
Matrix S is neutrally stable by construction. The variable w is not directly measurable for feedback design, but the matrix S is supposed to be perfectly known. We consider the next definition of output regulation. Definition 1. For system (1), the problem of output regulation is solved if there exists a controller processing the regulated output y satisfying the following requirements: (i) Internal stability requirement: when w = 0, any trajectory of the closed-loop system converges exponentially to zero. (ii) Output regulation requirement: when w = 0, the trajectories of the closed-loop are bounded for all t ≥ 0 and the output y asymptotically converges to zero.

As shown in (Byrnes et al., 2012, Section 1.3), the output regulation problem for linear system (1) can be solved if and only if there exist matrices Π, Ψ being the solution to the regulator equations

ΠS = AΠ + BΨ + P 0 = CΠ + Q, (3)
where the matrix Π uniquely defines the state steady-state x = Πw on which the regulated output y is zero, and Ψ defines the input steady-state u = Ψw, denoted in the following as friend (see [START_REF] Isidori | Shifting the internal model from control input to controlled output in nonlinear output regulation[END_REF]), which renders the given manifold x = Πw positively invariant. Equation (3) always admits a solution under the following assumption.

Assumption 1. The pair (A, B) is stabilizable, the pair (A, C) is detectable, and the matrix

A -λI B C
0 is full rank for any λ in the spectrum of S.

Under Assumption 1, the output regulation problem is solved by a controller of the form ξ = F ξ + Gy , u = Kξ , (4) where ξ ∈ R n ξ is the state of the regulator, with n ξ ∈ N, and F, G, K are of the form

F = Φ 0 M N , G = Γ H , K = (K 1 K 2 ) (5)
with (Φ, Γ) being a controllable pair satisfying σ(Φ) = σ(S), and such that the closed-loop matrix

A := A BK GC F (6)
is Hurwitz. In the rest of the paper, we assume that regulator (4) has been designed as described above so that items (i) and (ii) of Definition 1 hold. We refer to [START_REF] Byrnes | Output regulation of uncertain nonlinear systems[END_REF], Section 1.3) for more details.

NCS model

We investigate the scenario where a network is used to ensure the communication between plant (1) and regulator (4), as depicted in Figure 1. In this work, we focus on the effects of sampling and scheduling, and ignore delays, packet loss and quantization. See the remark at the end of this subsection. In particular, we describe the model used to characterize the channel limitations and the transmission protocol by following the framework used in [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF]; [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF]; [START_REF] Heemels | Networked control systems with communication constraints: Tradeoffs between transmission intervals, delays and performance[END_REF]. This framework allows to take into account a large class of network scheduling protocols, such as round robin (RR), try-once-discard (TOD), as well as the simplest case of sampled-data systems. Afterwards, we derive a hybrid model for the resulting NCS.

Transmission over the network occur at times t i , i ∈ Z ≥0 , satisfying 0 < ≤ t i+1 -t i ≤ τ * where τ * is the maximum allowable transmission interval (MATI) and is the lower bound on the minimum achievable transmission interval given by hardware constraints. The inter-transmission intervals t i+1 -t i may be time-varying and uncertain. Note that can be arbitrarily small and prevents Zeno solutions (see [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF]). We model this transmission policy using the variable τ , whose dynamics is given by τ

= 1 τ ∈ [0, τ * ], τ + = 0 τ ∈ [ , τ * ] . (7)
The sensors and actuators are grouped into ∈ N nodes, which are connected to the network. Hence, at each transmission instant a single node is allowed to transmit its data over the channel by the scheduling rule. The networked versions of y and u are denoted respectively as ŷ and û and these correspond to the most recently transmitted output and input values. For sake of simplicity, in this work we suppose that the variables û, ŷ are generated by zeroorder hold devices between two successive transmission instants in (8), though more complex holding functions could be taken into account, see [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF]. The associated dynamics are given by u see, e.g., [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF]; [START_REF] Postoyan | Tracking control for nonlinear networked control systems[END_REF]. We proceed differently here to ensure that κ remains in a compact set, which is useful to endow for the forthcoming stability results with some nominal robustness according to [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF]. The functions h := (h u , h y ) in (8) and p in (9) model the scheduling mechanism, which grants access to the network to a single node at each transmissions instant. Static and dynamic algorithms can be described by appropriate selection of h, p, κ * , in view of [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF]. For instance, in the case of RR protocol, each node transmits in an -cyclic manner. In this case, we select h(κ, e) := (I -∆(κ))e, with ∆(κ) := diag(δ 1 (κ), . . . , δ ne (κ)),

= 0 ẏ = 0 τ ∈ [0, τ * ], û+ = u + h u (κ, e u , e y ) ŷ+ = y + h y (κ, e u , e y ) τ ∈ [ , τ * ], (
δ i (κ) := 1, if i = κ 0, otherwise, p(κ) = κ + 1, if κ < κ * 0, otherwise, (10
) and κ * = -1, see [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF]. Another example is the TOD protocol, which grants access to the node with the biggest local network-induced error, see [START_REF] Walsh | Stability analysis of networked control systems[END_REF]; [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF]. In this case, we select h(e) = (I -Υ(e))e, Υ(e) := diag(ψ 1 (e), . . . , ψ ne (e)),

ψ i (e) := 1, if i = min(arg max i |e i |) 0, otherwise,
and κ * = 0, p = 0. The simple case in which inputs and outputs values are simultaneously transmitted at each transmission instant, namely the case of sampled-data systems, is described by p = 0, h = 0 and κ * = 0. Now, the dynamics of the plant in (1), with u replaced by its networked version û, is described by

ẋ = Ax + B û + P w τ ∈ [0, τ * ], x + = x τ ∈ [ , τ * ].
(11) Similarly, controller (4) no longer receives y but its networked version ŷ. As a consequence, we study the interconnection of system (11) with the following emulated regulator

ξ = F ξ + Gŷ τ ∈ [0, τ * ], ξ + = ξ τ ∈ [ , τ * ], u = Kξ. ( 12
)
By denoting χ := (x, ξ) ∈ R nχ , with n χ = n x + n ξ , we derive the following hybrid model of the overall NCS closed-loop system

ẇ = Sw χ = Aχ + Be + Pw ė = Mχ + Ne + Rw κ = 0 τ = 1          q ∈ C, w + = w χ + = χ e + = h(e, κ) κ + = p(κ) τ + = 0          q ∈ D, y = Cχ + Qw (13) where q := (χ, e, κ, τ ), C := R nχ × R ne × [0, κ * ] × [0, τ * ], D := R nχ × R ne × [0, κ * ] × [ , τ * ]
, the matrix A is defined in (6), C := (C 0), Q := Q, and the matrices B, M, N, P, R are given by

B := 0 B G 0 , P := P GQ , M := -C 0 0 -K A, N := -C 0 0 -K B, R := -CP -QS -KGQ (14)
Remark. Delays and packet loss effects can be similarly handled in the hybrid context by following Heemels et al.

(2010), [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF].

Problem Statement

The objective of this work is to investigate whether it is possible to preserve both requirements of Definition 1 for system (13), namely internal stability and output regulation, under suitable conditions on the network. As far as the first requirement is concerned, note that without appropriate conditions on the scheduling protocol and on τ * , Assumption 1 is not sufficient, in general, to guarantee the stability of the trajectories of closed-loop system (13) (see for instance [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF] in case of asymptotic stabilization). Concerning the second requirement, we will show that asymptotic output regulation can be preserved only in some particular cases. As a consequence, in all those cases in which we are not able to guarantee convergence to zero of the output, we aim to provide an error bound, depending on plant, controller and network properties.

STABILITY AND PERFORMANCE GUARANTEES

We present now the main results of this paper. First, we formulate an assumption on the scheduling protocol. Then, we derive the main theorems and we analyse a certain number of special cases where asymptotic output regulation can be achieved. Finally, we briefly discuss how the main result can be used to compute bounds on the MATI and on the asymptotic gain of the output.

Assumption on the scheduling protocol

We adopt the following assumption on the scheduling protocol, similar to [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF]; [START_REF] Heemels | Networked control systems with communication constraints: Tradeoffs between transmission intervals, delays and performance[END_REF]. Assumption 2. The function h is continuous and there exist W : Assumption 2 mainly states that the protocol ( 8), ( 9) is UGES, see [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF]. Examples of protocols verifying Assumption 2 are the RR protocol, TOD protocol. We refer to [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF] for more details.

N 0 × R ne → R ≥0 that is locally Lipschitz in its second argument, λ ∈ [0, 1), a, ā, b > 0 such that a|e| ≤ W (κ, e) ≤ ā|e|, W (p(κ), h(κ, e)) ≤ λW (κ,

Main Result

Before introducing the main result of this paper, we state the following supporting lemma. Lemma 1. There exist X = X T > 0 and ρ, c > 0 satisfying

  A T X + XA + 2ρ 2 X + 2 b2 c 2 M T M XB B T X -c 2 a 2 I   < 0 . ( 15
)
We impose that the maximum allowed transmission interval (MATI) τ * is less than T (c, ρ, λ), where

T (c, ρ, λ) :=              1 Lr arctan r(1 -λ) 2 λ 1+λ ( γ L -1) + 1 + λ γ > L 1 L 1 -λ 1 + λ γ = L 1 Lr arctanh r(1 -λ) 2 λ 1+λ ( γ L -1) + 1 + λ γ < L (16) with r := γ L 2 -1 , γ := c 2 , L := |N| b/a + ρ 2 , with
c, ρ satisfying Lemma 1 and λ satisfying Assumption 2.

We are now ready to state the main result.

Theorem 1. Suppose that Assumptions 1 and 2 are verified with λ ∈ (0, 1) and moreover τ * < T (c, ρ, λ), with T defined in (16). Then, the following properties hold:

(1) Consider system (13) with flow set characterized by (w, q) ∈ {0} × C and jump set (w, q) ∈ {0} × D. Then, the set

{0} × {0} × {0} × [0, κ * ] × [0, τ * ] is UGES.
(2) Consider system (13) with flow set W × C and jump set W × D, for some given compact set W ⊂ R nw . Then, all the maximal solutions q to (13) are precompact and lim t+j→∞ q(t, j) A = 0 where A := {q : |y| ≤ θ w} with w := max v∈W |v| and θ := b|ΨS| µ ρ c , where Ψ is defined in (3) and µ > 0 is the largest real number satisfying µ 2 C T C ≤ X.

Item 1) of Theorem 1 ensures that the internal stability requirement of Definition 1 is guaranteed, namely that the origin of the closed-loop system is exponentially stable when w = 0, even in presence of sampling and scheduling. This result is a consequence of the fact that, in this case, output regulation reduces to a stabilization problem via emulation approaches, thus boiling down in the framework considered for instance in [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF].

Item 2) of Theorem 1 states that, when w = 0, the trajectories of the resulting NCS closed-loop system are bounded, but in general, the output y is not asymptotically converging to zero, namely the output regulation requirement in Definition 1 is not ensured. This comes from the fact that, in steady-state, the networked version of u is not able to provide the right friend Ψw, but only an approximation of it. As a consequence, the steady-state behaviour of the x-component in (13) will not coincide exactly with Πw defined in (3), and y cannot converge to zero. In Section 3.4, however, we discuss some special cases where asymptotic regulation can still be achieved. Note that this analysis is consistent with [START_REF] Postoyan | Tracking control for nonlinear networked control systems[END_REF], where it is shown that asymptotic tracking control is in general not achievable in presence of network phenomena, due to the sampling and hold of the feedforward action.

In item 2) of Theorem 1, we also provide an explicit expression of the asymptotic gain θ relating the impact of w on y. The parameter θ is directly proportional to the norm of the friend Ψ and to the frequencies of the exosignal w (namely to S), and inversely proportional to the parameters ρ, c which uniquely define the MATI τ * via (16). Further comments about the relation between θ and τ * are given in Section 3.5.

Sampled-data case

Theorem 1 requires that λ ∈ (0, 1) in Assumption 2. When λ = 0, which corresponds to the sampled-data case (or in other words, in absence of scheduling), the analysis needs to be slightly modified. First, we revisit Lemma 1 as follows. Lemma 2. There exist X = X T > 0, H = H T > 0 and ρ, c > 0 satisfying

A T X + XA + 2ρ 2 X + 2 c 2 M T HM XB B T X -c 2 H < 0 . ( 17
)
We have the next result for the sampled-data case, the proof of which is given in the Appendix. Proposition 1. Suppose Assumption 1 is verified and τ * < T (c, ρ, 0), with T defined in (16) where γ := c 2 and L > 0 is the smallest real number satisfying (L -ρ 2 )H ≥ H|N|, with ρ, c and H according to Lemma 2. Then, items 1) and 2) of Theorem 1 hold for system (13) with p = 0, h = 0 and κ * = 0, where in particular θ := √ |S T Ψ T HΨS| µρc .

Asymptotic regulation

We discuss here two particular cases in which the exact output regulation requirement of Definition 1 can be still achieved for the NCS system (13).

Constant exosignals. When w is constant signal, i.e. S = S 0 = 0 in (2), then θ = 0 in Theorem 1 and Proposition 1 and the output regulation requirement of Definition 1 holds. In other words, the internal model property of the integral action (see [START_REF] Francis | The internal model principle of control theory[END_REF]; [START_REF] Byrnes | Output regulation of uncertain nonlinear systems[END_REF]) is preserved in case of zero-sampling holder and scheduling of the measured output and the control input. We expect that similar results may hold also for general classes of nonlinear systems, see [START_REF] Astolfi | Integral action in output feedback for multi-input multi-output nonlinear systems[END_REF]; [START_REF] Astolfi | Emulation-based semiglobal output regulation of minimum phase nonlinear systems with sampled measurements[END_REF].

No network between the controller and the actuators.

When only the output y is transmitted over the network, namely when we interconnect the system (1) with the regulator (12), system (13) is defined with e := e y , B := (0, G T ) T , M := -CA, N := -CB, R := -CP -QS.

The following result can be stated. Proposition 2. Suppose Assumptions 1 and 2 are verified with λ ∈ (0, 1). Let τ * < T (c, 0, λ), with T defined as in Theorem 1, with c coming from Lemma 1. Then item 1) and 2) of Theorem 1 are verified where in particular A := {q : y = 0}, hence items 1) and 2) of Definition 1 hold.

Remark. The emulation approach considered in this work is different from the approach followed in many other papers, such as [START_REF] Lawrence | Output regulation for linear systems with sampled measurements[END_REF]; [START_REF] García-Sandoval | Robust tracking for oscillatory chemical reactors[END_REF] and references therein, where ripplefree regulators composed by a discrete-time regulator and a continuous-time modulator are used to asymptotically guarantee zero inter-sampling behaviour. Most likely, the approach followed in [START_REF] Lawrence | Output regulation for linear systems with sampled measurements[END_REF], [START_REF] García-Sandoval | Robust tracking for oscillatory chemical reactors[END_REF], allows to design a regulator with larger MATI, though its use is limited to the case of periodic sampling, namely when = τ * , with no scheduling.

Network design for practical regulation

A consequence of Theorem 1 (and Proposition 1) is that, in general, asymptotic regulation cannot be guaranteed. Therefore, a question of particular interest is how to design the communication network in order to guarantee given performance in terms of the asymptotic regulated output bound θ. To this end, we can exploit Theorem 1 as follows.

Suppose, in particular, that we want to ensure θ < θ max in Theorem 1 for some fixed θ max > 0. By recalling that µ 2 C T C ≤ X, compute c * > 0 as the smallest value for c satisfying    16), which is the maximum allowable transmission interval for which, given the plant dynamics and emulated regulator, the maximum gain θ max from w to y is satisfied. The same reasoning can be followed in the case λ = 0 where, in place of (15), we use (17). In view of the proposed procedure, performances in terms of θ can be improved by choosing a smaller MATI τ * . This is confirmed in Section 4 via a numerical example. In conclusion, the result of Theorem 1 can be used as a design tool (with potentially some conservatism) to select the communication network parameter MATI with a performance based design trade-off.

A T X + XA + 2 b2 c 2 |ΨS| 2 θ 2 max C T C + M T M XB B T X -c 2 a 2 I    < 0 (18) and select ρ(c) = b|ΨS|/(µc θ max ). Finally, compute τ * max = T * (c, ρ(c), λ) with (

NUMERICAL EXAMPLE

Consider the output regulation problem described in Section 2.1 with

n x = 3, n u = 2, n y = 1, n ω = 1, A = 0.1 0 1 0 -1 0 0 1 -1 B = 1 0 0 1 0 0 P = -1 0 0 0 0 1 C = (1 0 0), Q = (1 0), S is of the form (2)
with ω 1 = 0.1 and S 0 is not present and therefore no integral action is needed. We design controller (4) with ( 5), and we compute Ψ solution to (3). We select

n ξ = 5, Φ = S, Γ = (0 , 1) T , H = (1 , 0.1 , 0.1) T , M = 0 -0.2 0 -0.2 0 0 N = -1.9 0 0 -0.1 -1.1 0 -0.1 1 -1 K 1 = 0 -0.2 0 -0.2 K 2 = -1 0 -1 0 -0.1 0 Ψ = -0.193 0.901 1.580 -1.733 .
It can be verified that the matrix A is Hurwitz. Finally, we suppose that the exogenous signal w ranges in the compact set W = {w ∈ R 2 : |w| ≤ w}, with w = 1. We consider, in this numerical example, the case in which there are = 3 nodes corresponding to the 2 inputs and the output, respectively, with the RR protocol (10) and with aperiodic sampling with = τ * /2. From [START_REF] Nešić | Input-output stability properties of networked control systems[END_REF], we know that Assumption 2 is satisfied with λ = ( -1)/ , ā = b = √ , a = 1. By following Section 3.5, we derive the MATI τ * to satisfy given gain θ max for the regulated output. We used the inequality (18) to obtain c, ρ and the definition (16) to compute τ * . We compare those value by running a simulation in Matlab/Simulink for the same values of MATI τ * . It can be also verified that values of τ * larger than 0.35 leads to instability. The asymptotic bounds of the output found in the simulations, denoted as θ sim , are given in Table 1. As expected by the discussion in Section 3.5, performances in terms of output bounds can be improved by choosing a smaller MATI. On the other hand, the specifications on the network can be less stringent if the performance specification is loosened.

CONCLUSION

We investigated the problem of output regulation for linear NCSs in presence of uncertain transmission intervals and scheduling between the plant, sensors, actuators and controller. We have shown that in general internal stability and boundedness of the regulated output error is guaranteed, provided that the network and the scheduling protocol satisfy certain properties. In other words, the presence of network effects may destroy the internal model property of the regulator. Specific cases where asymptotic output regulation is achieved are discussed, namely when the regulator is directly connected with the actuators, or when the exogenous signals are constants. For the general case we have provided a performance analysis in which an expression for the gain from external disturbances to output error is given. Future works include the analysis of other network phenomena (such as delay or quantization) and the set up of new control strategies able to guarantee asymptotic regulation in such framework by means of smart actuators.

  8)where e := (e y , e u ) ∈ R ne , n e = n y + n u , e y := ŷ -y, e u := û -u, and where κ ∈ N 0 is a counter variable needed to keep track of the number of transmissions, whose dynamics is given by κ= 0 τ ∈ [0, τ * ], κ + = p(κ) τ ∈ [ , τ * ].(9) We suppose that κ lives in a given compact set [0, κ * ], for some κ * ∈ N 0 , hence p(κ) ∈ [0, κ * ], for all κ ∈ N 0 . Note that usually the jump map of κ is taken as κ + 1, Output regulation for NCS.

  e) and ∂W (κ,e) ∂e ≤ b for all κ ∈ [0, κ * ] and almost all e ∈ R ne .

Table 1 .

 1 Given bound of θmax and bound θ sim obtained from simulation.

	θmax	c	ρ	τ * (•10 -2 )	θ sim (•10 -4 )
	1	2.581 0.182	2.25	3.47
	0.5	2.676 0.336	2.11	3.31
	0.1	4.337 0.667	0.94	0.86
	0.05	6.039 0.668	0.51	0.44

This project work has been partially prepared when the first author was at Université de Lorraine, CNRS, CRAN, Nancy, France, and was partially founded by the "Région Grand-Est" of France.

This is derived from the regulator equations, see[START_REF] Francis | The internal model principle of control theory[END_REF].

Appendix A. PROOFS

A.1 Proof of Lemma 1

Since A is Hurwitz, there always exist a symmetric and positive definite matrix X and a sufficiently small ρ > 0 such that A T X + XA + 2ρ 2 X < 0. The desired result is obtained by the Schur's complement of (15) and by selecting c > 0 large enough.

A.2 Proof of Lemma 2

Since A is Hurwitz, there always exist a symmetric and positive definite matrix X and a sufficiently small ρ > 0 such that A T X + XA + 2ρ 2 X < 0. The desired result is obtained by the Schur's complement of (15) and by selecting any H = H T > 0 and c > 0 large enough. Note that when H = I, inequality (17) coincides with (15), with a = b = 1.

A.3 Proof of Theorem 1

The proof of this theorem follows the main arguments used in the proof of Theorem 1 in [START_REF] Postoyan | Tracking control for nonlinear networked control systems[END_REF], though three main points characterize the framework considered here: the definition of a change of coordinates for system (13) where the regulated output does not depend on the exogenous signal w; the definition of a Lyapunov function which is slightly different from the one proposed in [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF], since it is adapted for the use of inequality (15); the use of the regulator equations (3) to give an explicit expression of the asymptotic bound θ showing its explicit dependency on the MATI via the parameters c, ρ > 0, on the properties of the network via b coming from Assumption 2, on the friend Ψ, and on the frequency of w contained in S.

First, let Π Π Π = (Π Π Π x , Π Π Π ξ ) ∈ R nχ be computed as the unique solution 3 to the Sylvester equation Π Π ΠS = AΠ Π Π + P. Standard results in output regulation theory 4 can be used to show that Π Π Π x = Π, with Π defined in (3), and, moreover, KΠ Π Π ξ = Ψ. Consider the change of coordinates χ = χ -Π Π Πw by which system (13) is transformed into

. The last equality is a direct consequence of the definitions of the 3 Uniqueness of Π Π Π is a direct consequence of the fact that the matrix A defined in ( 6) is Hurwitz and therefore σ(A) ∩ σ(S) = ∅.

4 See (Byrnes et al., 2012, Section 1.3).

matrices M, R and Π Π Π ξ . We write system (A.1) in the compact form ẇ=Sw η=F(η, w)

where η := ( χ, e, κ, τ ). Note that in view of (Goebel et al., 2012, Theorem 6.30), of Assumption 2, and of the definition of C η , D η , system (A.2) is well-posed.

Let φ : [0, T ] → R, with T defined in ( 16), be the solution to φ = -2Lφ -γ(φ 2 + 1)

3) where λ ∈ (0, 1) is defined in Assumption 2, and γ = c 2 . We have the following result according to [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF].

Consider now the following function as also employed in [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF]:

(A.4) where V (z) := χT X χ, with X satisfying (15), and W defined in Assumption 2. By definition of V, W , and as a consequence of Claim 1, there exist ¯ , > 0 such that

(A.5) for any η ∈ C η ∪ D η . Let η ∈ C η . By using Assumption 2, Claim 1 and the definition of G according to (A.1) and (A.2), we have that

for all (w, η) ∈ W ×D η . Hence, we have shown that U does not increase at jumps. Next, by using the definitions of F according to (A.1) and (A.3), we compute U • (η, F(η, w)) = χT (XA + A T X) χ + χT XBe + e T B T X χ +2φ(τ )W (κ, e) ∂W (κ, e) ∂e M χ + Ne + Lw -[2Lφ(τ ) + γ(φ 2 (τ ) + 1)]W 2 (κ, e) (A.7) for all (w, η) ∈ W × C η . By using Young's inequality and Assumption 2, we have

in view of Assumption 2. As a consequence, by definition of L and γ, and by using the first inequality in Assumption 2, we derive from (A.7)

) for all (w, η) ∈ W × C η . Therefore, by applying (15) to (A.8), and by recalling the definition of U in (A.4), we directly obtain

for all (w, η) ∈ W × C η .

When w = 0, inequality (A.9) reads

(A.10) As a consequence, item (1) of Theorem 1 holds in view of (A.5), (A.6), (A.10), and by invoking the same arguments as in the proof of Theorem 1 in [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF]. Note that maximal solutions are complete as all the conditions of (Goebel et al., 2012, Proposition 6.10) are verified.

When w = 0 and w ∈ W ⊂ R nw , we may upper bound the term in (A.9) w T L T Lw ≤ sup w∈W |w| 2 |ΨS| 2 , where we used the definition of L in (A.1). As a consequence, inequalities (A.6) and (A.9) give

for all (w, η) ∈ W × C η and (w, η) ∈ W × D η respectively, with θ, µ and w defined in the statement of the theorem. Let (w, η) be a solution to system (A.2). By definition of the Clarkes derivative (see Section II) and page 100 in Teel and Praly (2000), it holds that, for all j and for almost all t ∈ I j (where

≤ -2ρ 2 (U (η(t, j)) as η(t, j) ∈ C η for all (t, j) ∈ dom (w, η). From previous inequality, and by recalling that for all j ∈ J (where J = {j : (t, j) ∈ dom (w, η)}) the second inequality (A.11) holds, we obtain U (η(t, j)) ≤ exp(-2ρ 2 t)U (η(0, 0)) + µ 2 θ 2 w 2 , (A.12) for (t, j) ∈ dom (w, η). As a consequence, since system (A.2) is well-posed (Goebel et al., 2012, Theorem 6.8), we can apply (Goebel et al., 2012, Proposition 6.10) to conclude that all maximal solutions are complete. Therefore, in view of (A.12) and (A.5) are compact and converge to the set A q := {(w, η) : U (η) ≤ µ 2 θ 2 w 2 }. Since y = C χ, by using the inequality µ 2 y T C T Cy ≤ χT X χ ≤ U (η) we have that A ⊇ A q concluding the proof.

A.4 Sketch of the proof of Proposition 1

First of all, note that when h = 0, p = 0, κ * = 0, Assumption 2 is verified with W (κ, e) := √ e T He and λ = 0. As a consequence, the proof follows the same arguments of the proof of Theorem 1, which are here omitted for sake of brevity, where in particular we use the inequality (17) instead of (15). Note that by taking H = I, we obtain a = ā = b = 1 in Assumption 2, and the inequality (17) reduces to (15).

A.5 Sketch of the proof of Proposition 2

By applying the change of coordinates χ = χ -Π Π Πw we obtain system (A.1) where in particular L := 0 (this can be easily shown by removing the last n u rows from the definition of L in (A.1)). As a consequence, since the ( χ, e)flow map and jump maps are independent of w, the proof reduces to show UGAS of the set W × {0} × {0} × [0, κ * ] × [0, τ * ] of system (A.1). This can be shown by using the inequality (15) with ρ = 0 and by following the same arguments of the proof of Theorem 1 in [START_REF] Carnevale | A lyapunov proof of an improved maximum allowable transfer interval for networked control systems[END_REF] and by properly recalling the definition of γ = c 2 . The proof concludes by noting that solutions in that set satisfy y = 0 in view of the definition of system (A.1).


Vladyslav Fedchenko
email: vladfedchenko@gmail.com

Giovanni Neglia
email: giovanni.neglia@inria.fr

Bruno Ribeiro
email: ribeiro@cs.purdue.edu

Feedforward Neural Networks for Caching: Enough or Too Much?

We propose a caching policy that uses a feedforward neural network (FNN) to predict content popularity. Our scheme outperforms popular eviction policies like LRU or ARC, but also a new policy relying on the more complex recurrent neural networks. At the same time, replacing the FNN predictor with a naive linear estimator does not degrade caching performance significantly, questioning then the role of neural networks for these applications.

Introduction

Caching is doubly beneficial: it reduces data retrieval time by storing a copy at a closer/faster-accessible location and, at the same time, decreases the load on the remote system where the original version is located. For this reason, caches are ubiquitous in IT systems, ranging from L2 caches built into the CPU to in-memory page caches managed by the operating systems, from local web proxy caches to Internet-wide Content Delivery Networks (CDNs) and cloud-based in-memory key-value stores like Amazon's ElastiCache.

It is difficult to decide which contents should be stored in the cache and which ones should be evicted. Even when the sequence of future requests is known in advance, maximizing the hit ratio is in general a strongly NPcomplete problem [START_REF] Chrobak | Caching is hard-even in the fault model[END_REF]. Moreover, in most cases of practical interest, future requests are unknown and a caching policy may only try to guess what will happen. To this purpose, the policy usually looks at the past sequence of requests to exploit possible elements of predictability, like the fact that future requests are often more likely to be for recently referenced contents (temporal locality) or for related ones (spatial locality). But additional information could be beneficial. For example, in a CDN the time of the day, users' profiles, and information about what is happening at close-by caches are likely to be correlated with future requests.

The first paper to propose the idea to use machine learning to learn caching rules from available rich data was probably [START_REF] Baştug | Big data meets telcos: A proactive caching perspective[END_REF]. Nevertheless, the only practical example considered there was collaborative filtering to estimate content popularities at some locations from measurements at other locations. Surprisingly, the idea to use neural networks (NNs) for caching purposes was only explored during the last year in [START_REF] Zeng | Long short term memory based hardware prefetcher: A case study[END_REF][START_REF] Hashemi | Learning memory access patterns[END_REF][START_REF] Tsai | Caching for mobile social networks with deep learning: Twitter analysis for 2016 u.s. election[END_REF][START_REF] Narayanan | Deepcache: A deep learning based framework for content caching[END_REF][START_REF] Zhang | Using grouped linear prediction and accelerated reinforcement learning for online content caching[END_REF]. All these papers (described in Sect. 2) adopt recurrent neural networks with long short-term memory units (LSTM in what follows), motivated by the fact that LSTM have proved to be very effective to address sequence prediction problems such as those found in natural language processing.

LSTM neural networks (LSTM-NNs), as all recurrent networks, have feedback loops which give them some kind of memory. They are then more complex (and more difficult to train) than the classic feed-forward NNs (FNNs) where signals can only travel one way from the input layer to the output one. The question at the origin of our work was then if the simpler FNNs could also perform well for caching purposes. Answering this simple question has lead us to unexpected conclusions.

The paper is organized as follows. After an overview of the related work in Sect. 2, we describe our caching policy and its FNN predictor for content popularity in Sect. 3. In Sect. 4 we present our performance evaluation results on real traces from Akamai CDN. Sect. 5 concludes the paper.

Related work

Papers [START_REF] Zeng | Long short term memory based hardware prefetcher: A case study[END_REF][START_REF] Hashemi | Learning memory access patterns[END_REF] propose two different LSTM-NNs for prefetching inside a processor. Instead, in our paper, we focus on internet applications like web proxies, or content delivery networks (CDNs), and we consider reactive caching, i.e. contents can be retrieved only once they are requested. Moreover, [START_REF] Zeng | Long short term memory based hardware prefetcher: A case study[END_REF][START_REF] Hashemi | Learning memory access patterns[END_REF] evaluate the quality of their solutions only in terms of prediction accuracy and not of the final data retrieval time or other system metrics prefetching should improve. In this paper we conclude that the relation between prediction accuracy and final performance of the caching system may be weaker than one would expect.

The authors of [START_REF] Tsai | Caching for mobile social networks with deep learning: Twitter analysis for 2016 u.s. election[END_REF] study caching at the base stations of a cellular network. In their case the LSTM-NN is used to perform a sentiment analysis of mobile users' traffic to detect their interests and prefetch contents they may like.

Reference [START_REF] Narayanan | Deepcache: A deep learning based framework for content caching[END_REF] proposes to use an LSTM-NN as an additional module to be integrated with an existing baseline caching policy like LRU. The LSTM-NN generates fake requests that are added to the real request stream. These additional requests push the baseline caching policy to prefetch or maintain in the cache contents that are likely to be used in the future.

Finally, [START_REF] Pang | Toward smart and cooperative edge caching for 5g networks: A deep learning based approach[END_REF] is the closest paper to ours, because it uses an LSTM-NN as a popularity predictor and then manages the cache as a priority queue where, upon a miss, contents with the smallest predicted popularity are evicted. We have implemented the caching policy in [START_REF] Pang | Toward smart and cooperative edge caching for 5g networks: A deep learning based approach[END_REF] and compared it with ours in Sect. 4.

Another set of papers like [START_REF] Zhong | A deep reinforcement learning-based framework for content caching[END_REF][START_REF] Rezaei | Multi-agent learning for cooperative large-scale caching networks[END_REF] use reinforcement learning to adapt dynamically the caching policy. A reinforcement learning algorithm tries to learn directly the best action to pursue, often by a trial-and-error approach. For this reason, training a reinforcement learning algorithm is often more complex than learning the parameters of a neural network, and results may be unstable [START_REF] Henderson | Deep reinforcement learning that matters[END_REF].

Caching policy

The core idea of our policy is simple and was naturally adopted by previous works like [START_REF] Li | Popularity-driven content caching[END_REF] and [START_REF] Pang | Toward smart and cooperative edge caching for 5g networks: A deep learning based approach[END_REF]: we keep in the cache the contents with the largest estimated popularities. The popularity of a content is defined as the fraction of requests for that content over a meaningful time horizon. When contents have the same size (as we assume) this strategy should lead to maximize the cache hit ratio.

Components

In detail, our caching system is composed by a feature database, a popularity predictor, and a content storage element.

The content storage is managed through a min-heap data structure with the estimated popularities as keys. In this way, it is possible to retrieve fast a pointer to the content with the minimum estimated popularity.

The feature database contains the current feature vector for each of the contents in the catalogue. 1 The feature vector has K elements: it contains the fractions of requests (popularities) for content i during the previous K -1 epochs (p -(K-1),i , . . . p -1,i ) and during the current one (p 0,i ). Each epoch has the same duration T . We remark that, during a given epoch, past popularities do not change, but current popularity does. Table 1 lists the main parameters of our caching policy together with their typical values used for the experiments in Sect. [START_REF] Hashemi | Learning memory access patterns[END_REF].

The popularity predictor receives as input 1) the feature vector of a content and 2) how much time t has passed since the beginning of the current epoch (0 ≤ t ≤ T ). It outputs the popularity estimation for the current epoch. 2 The prediction algorithm is based on an FNN. It is the focus of this paper and is described in detail in Sect. 3.3.

Operation

The caching policy works as follows. When a request for content i arrives, the feature vector of content i is updated and provided as input to the popularity predictor together with the time t. The predictor estimates then the current popularity of content i (p 0,i ).

If content i is present in the cache (a hit occurs), it is served and its popularity key is updated in the heap. If it is not stored locally (a miss occurs), it is retrieved from the authoritative server or from a higher-level cache and served. Moreover, the policy decides if storing it locally. To this purpose, the policy compares the popularity estimate p0,i with the minimum popularity of the contents currently in the cache. If p0,i is larger, then content i replaces the least popular content, otherwise, it is discarded.

Moreover, upon a request, a few contents in the cache are randomly selected and their popularity is re-evaluated through the predictor. This prevents old contents, which are no more requested, but whose popularity was overestimated in the past, from staying forever in the cache.

At the end of each epoch, the predictor is updated through a new training phase, described below.

Popularity predictor

The core of the predictor is a Feedforward Neural Network (FNN). The FNN has K + 1 input values and one output value. The input values are the time t since the beginning of the current epoch and a mapping of the feature vector of K popularities (x -l,i = F (p -l,i )), where F (p) = -log(p + c) and c > 0 is a small constant. This transformation makes the input vector more homogeneous (popularities differ by many order of magnitudes). The output y i of the FNN is interpreted as the mapping of the current popularity. The final predicted popularity is then obtained through the inverse transformation p0,i = F -1 (y i ).

Internally, the FNN has 2 fully connected hidden layers, each with 128 neurons. Each neuron uses a rectified linear unit (ReLU) as activation function (a(x)), and in particular a Leaky ReLU to overcome the "dying ReLU" problem [START_REF] Lau | Investigation of activation functions in deep belief network[END_REF]. Then a(x) = x, if x ≥ 0, and a(x) = αx otherwise, where α is a small constant. In our experiments, Leaky ReLU provides better results than the usual sigmoid.

The FNN is trained at the end of each epoch using the contents requested during the epoch. The prediction quality is evaluated through the squared difference (y i -F (p 0,i )) 2 (note that at the end of one epoch p 0,i is the correct popularity of content i). The loss function is then the classic mean squared error (MSE). FNN weights are updated through the usual backpropagation mechanism with learning rate η.

Moreover, the training datasets for the previous H epochs are reused, but with a discounted learning rate γ i η for the ith epoch farthest in the past. This is a standard technique to prevent the problem of catastrophic forgetting [START_REF] French | Catastrophic forgetting in connectionist networks[END_REF][START_REF] Kirkpatricka | Overcoming catastrophic forgetting in neural networks[END_REF] that may occur when the training uses only the most recent data. In this case, the neural network can indeed forget the information about some underlying relations between input and output learned in the past, even though they still may be relevant for predictions.

Performance Evaluation

We have evaluated the performance of our caching policy both on synthetic and on real traces.

In the synthetic trace, requests for contents arrive according to a Poisson process.

Each request is for content i with probability π i independently from previous requests. The catalogue includes 10 thousand contents, divided in two equally-sized classes. Contents in the first class have constant probabilities π i following a Zipf's law with exponent 0.8. The same holds for the contents in the second class during one epoch, but at each epoch the probabilities are permuted uniformly at random. Two request traces have been collected from two different vantage points of the Akamai CDN. The first one spans over 5 days with 4 × 10 8 requests for 13×10 6 unique contents. The second one spans over 30 days with 2×10 9 requests for 113 × 10 6 unique contents. Detailed information about these traces is available in [START_REF] Neglia | Access-time-aware cache algorithms[END_REF]. Both for synthetic and real traces, we considered the contents of equal size (even if information about the real size is available).

All caching policies tested have been implemented in an ad-hoc Python simulator using the PyTorch library for feedforward and LSTM networks. The values of all parameters are those in Table 1.

Popularity estimation

We first evaluate FNN ability to predict content popularities. Figure 1 shows the training and validation error versus the number of iterations, where one iteration corresponds to processing 8 requests. The FNN learns quite fast and after about 400 iterations (i.e. 3200 requests), both the training and the evaluation errors reach a plateau (left plot). At this stage, the FNN predicts reasonably well content popularities (right plot). In the We compare the prediction quality for three different predictors: 1) FNN, 2) empirical average over the past K popularities (AVG), and 3) linear regression estimator over the K past popularities (LR). 3 Table 2 shows the MSE for the transformed popularities for the three predictors. Both for the synthetic and Akamai 30-day trace FNN significantly outperforms the other two.

Comparison with other caching policies

We compare our FNN-based caching policy with two popular eviction policies: LRU and ARC.

LRU maintains a priority queue ordered according to the content last access time. Upon a hit, the content is moved to the front of the queue. Upon a miss, the new content is inserted in the cache and the Least Recently Used one is evicted from it. LRU has low-complexity and does not require any configuration. It has shown good performance across a variety of request patterns. For this reason it is one of the most used caching policies.

Adaptive Replacement Cache (ARC) [START_REF] Megiddo | Outperforming lru with an adaptive replacement cache algorithm[END_REF] is a caching policy introduced by IBM in 2004. It uses two priority queues to combine information about how recently a content has been required (like LRU does) and how frequently (like another policy, LFU, does). The size of the two queues is dynamically adapted to the specific request pattern. ARC is slightly more complex than LRU, but, in our experience, it is very difficult to beat.

We wanted also to compare FNN-caching with more complex NN-based policies. We have considered the DLSTM scheme presented in [START_REF] Pang | Toward smart and cooperative edge caching for 5g networks: A deep learning based approach[END_REF]. We were not able to get the code or the traces from the authors. So, we have implemented it in the same simulator and tried to select all parameters according to the suggestions in [START_REF] Pang | Toward smart and cooperative edge caching for 5g networks: A deep learning based approach[END_REF].

Figure 2(a) shows the hit rate the different policies achieve over Akamai 5-day trace. FNN-caching performs significantly better than ARC and LRU. DLSTM does not appear in the figure, because its hit rate was constantly below 1%. We suspected the poor performance of DLSTM was due to its large number of parameters. In fact, the one-hot encoding used by DLSTM requires a number of weights that grows linearly with the number of contents in the catalogue. As an example, for 10 5 contents the DLSTM needs to learn more than 10 6 weights. Our solution instead has about 10 4 weights independently from the number of contents. To test this hypothesis, we filtered the trace considering only the requests for the first 1000 contents appearing in it. Figure 2(b) supports our hypothesis: the performance of DLSTM keeps improving over time, but, after more than one day, it still lags behind the other policies. Over the 5 days (results not shown here), DLSTM manages to outperform LRU, but neither ARC nor our policy. And, on a larger catalogue, DLSTM is definitely too slow to be competitive. FNN-caching achieves a higher hit ratio than classic policies like LRU and ARC as well as the new DLSTM. The same conclusion holds also for the 30-day trace and the synthetic one. But, as the attentive reader may have already remarked, this is not the end of the story. In fact, we have also tested some caching policies where the FNN popularity predictor is replaced by the LR predictor or by the AVG predictor. 4 The corresponding curves are also in Fig. 2(a) and are almost indistinguishable from the one of FNN-caching! The hit rate is at most 1% less for AVG-caching than for FNN-caching and LR-caching has intermediate performance. Hence, while the FNN predictor is significantly better than the other two (see Table 2), for caching decision the less precise estimates of LR and AVG are equally good. Moreover, LR has much less parameters to learn (K + 2) and both LR and AVG are computationally less expensive than FNN.

Discussion and Conclusions

Our current results suggest that, for caching purposes, neural network predictors do not have an edge on simpler linear estimators. Moreover, experiments not shown here indicate that considering additional information as input, like the time of the day or the size of the content, does not improve the performance of FNN-caching.

At the same time, in this paper we assume that past popularities of all contents are known. In reality, this information may be available only for a subset of the contents or may have been lossy compressed (as in [START_REF] Li | Popularity-driven content caching[END_REF]). It is possible that an NN would work better than a linear predictor with incomplete/noisy inputs.

Moreover, while the LSTM-NN we tested performed poorly, [START_REF] Hashemi | Learning memory access patterns[END_REF] shows that it may be more advantageous to frame the prediction problem as a classification rather than as a regression (as done in all other works [START_REF] Pang | Toward smart and cooperative edge caching for 5g networks: A deep learning based approach[END_REF][START_REF] Zeng | Long short term memory based hardware prefetcher: A case study[END_REF][START_REF] Narayanan | Deepcache: A deep learning based framework for content caching[END_REF]), because the extreme variability of content popularities "means that the effective vocabulary size can actually be manageable for RNN [LSTM] models."

We plan to explore these directions in our future work.

Figure 1 :

 1 Figure 1: Popularity estimation: (a) training and validation errors over the epochs, (b) predicted vs real popularities. Synthetic trace.

Figure 2 :

 2 Figure 2: (a) Hit rate for different cache sizes, Akamai 5-day trace. (b) Cumulative hit rate vs number of requests, Akamai filtered 5-day trace (only 1000 contents).

Table 1 :

 1 Notation and typical values.

	Symbol Meaning	Typical Value
	T	epoch duration	200 s
	K	# of epochs	4
	c	constant in the logarithmic	10 -15
		mapping
	α	leaky ReLU coefficient	10 -2
	η	learning rate	10 -4
	γ	learning rate discount	0.5
	H	# of old epochs used for	9
		training

This solution has clearly a large memory footprint, but in this paper we want first to evaluate the potentialities of NN-based caching.

It could be more useful to estimate the popularity during a time interval of duration T in the future, but this choice simplifies the learning phase.

The linear regression model has been obtained at runtime training an NN without non-linearities (we removed the activation functions).

The two resulting caching policies belong to the family of Least Recently/Frequently Used (LRFU) policies where the requests numbers during past epochs are weighted with different coefficients[START_REF] Lee | Lrfu: A spectrum of policies that subsumes the least recently used and least frequently used policies[END_REF].