# An Optimal Low-Complexity Policy for Cache-Aided Computation Offloading

Nicola Di Pietro, Emilio Calvanese Strinati

<figure><img src="image_1.png" /></figure>

To cite this version:

Nicola Di Pietro, Emilio Calvanese Strinati. An Optimal Low-Complexity Policy for Cache-Aided Computation Offloading. IEEE Access, 2019, 7, pp.182499-182514. 10.1109/access.2019.2959986. cea-04780525

HAL Id: cea-04780525

https://cea.hal.science/cea-04780525v1

Submitted on 13 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Received November 12, 2019, accepted December 12, 2019, date of publication December 16, 2019, date of current version December 26, 2019.

Digital Object Identifier 10.1109/ACCESS.2019.2959986

# An Optimal Low-Complexity Policy for Cache-Aided Computation Offloading

NICOLA DI PIETRO<sup>©</sup> AND EMILIO CALVANESE STRINATI<sup>©</sup>, (Member, IEEE)

CEA-Leti, 38054 Grenoble, France

Corresponding author: Nicola di Pietro (nicola.dipietro@cea.fr)

This work was jointly supported by the European Commission H2020 and the Ministry of Internal Affairs and Communications of Japan, under EU Contract EUJ-01-2016-723171 5G-MiEdge.

**ABSTRACT** Computation caching is a novel strategy to improve the performance of computation offloading in wireless networks endowed with edge cloud or fog computing capabilities. It consists in preemptively storing in caches located at the edge of the network the results of computations that users offload to the edge cloud. The goal is to avoid redundant and repetitive processing of the same tasks, thus streamlining the offloading process and improving the exploitation of both the users' and the network's resources. In this paper, a novel computation caching policy is defined, investigated, and benchmarked against state-of-the-art solutions. The proposed new policy is built on three characterizing parameters of offloadable computational tasks: popularity, input size, and output size. This work proves the crucial importance of including these parameters altogether in the design of efficient policies. Our proposed policy has low computational complexity and is numerically shown to achieve optimality for several performance indicators and to yield significantly better results compared to the other analyzed policies. This is shown in both a single- and a multi-cell scenario, where a serving small cell has access to its neighboring cells' caches via backhaul. In this paper, the benefits of computation caching are highlighted and estimated through extensive numerical simulations in terms of reduction of uplink traffic, communication and computation costs, offloading delay, and computational resource outage.

**INDEX TERMS** Computation caching, 5G, multi-access edge computing, MEC, fog computing, computation offloading, small cell, energy efficiency.

## I. INTRODUCTION

The future of mobile communications will be characterized by ubiquitous connection availability, very dense networks, ultra-low latency, energy efficiency, and an extremely fast and copious exchange of data and information. A game-changing idea for the 5G revolution consists in empowering network mobile terminals with data elaboration and storage capabilities, thus bringing cloud support the closest possible to users. This paradigm is called Multi-access Edge Computing (MEC) [22], [23], [39], also known as mobile edge cloud or computing. A rich research current focuses on the allocation and clever exploitation of MEC resources, often divided into three categories: communication, computing, and caching [37], [39], sometimes referred to as C3, 3C, or C³, and extensible to C⁴ with the addition of control [26],

The associate editor coordinating the review of this manuscript and approving it for publication was Cunhua Pan<sup>©</sup>.

indicated as a key feature for future 6G delay-critical applications [6]. Numerous results show the importance of developing techniques for a joint management and allocation of these resources, capturing in one single optimization framework all the characterizing aspects of MEC [2], [3], [30], [31], [35].

In MEC networks, Serving Small Cells (SSCs) are endowed with radio access technology, computing units, and local cache memories. SSCs can be entrusted by a User Equipment (UE) with computational assignments to run on its behalf through a procedure called *task* or *computation offloading* [2], [3], [35], [38]. This revolutionizes the classical interaction between UEs and network access points, allowing UEs to both save energy and meet the tight latency constraints that will characterize many 5G services and use cases.

Moreover, the role of caching in 5G networks [1], [4], [14], [39] is critically important to satisfy the always growing demand for downloadable multimedia content and to face the consequent increase of data traffic through the network.
In the context of task offloading, a new form of caching was recently introduced, after noticing the pointlessness of repeating many times the same computation for the same reiterated offloading request. This paradigm is called *computation* (or *task*) *caching* [7], [8], [27], [29]. It suggests to exploit small cells' caches to store the results of offloadable computations, so that the latter can be simply retrieved each time they are requested, instead of being recomputed [10], [11], [13], [23], [26]. Computation caching applies to MEC a concept already proposed in other fields of computer science and mathematics [9], [33], [34], [40]. Its goal is to decimate redundant and repetitive processing, making results available before users' offloading requests arrive. In this, computation caching shares the rationale of (and can be combined with) *proactive computing* [12] and *data prefetching* [17], [18], as evoked in [11].

Caching computation results entails several advantages, e.g., drastically reducing the computation time and saving energy for both UEs and SSCs, preventing uplink bottlenecks [28], freeing network resources, decreasing SSCs' workload, diminishing the number of virtual machine instantiations and migrations (for instance, in mobility scenarios as in [32]). The consequent resource gains may be reinvested to optimize the network's or the UEs' performance and increase users' satisfaction.

Applications of computation caching are conceivable in several contexts. Promising scenarios combine images or videos with heavy computational tasks: video rendering based on users' action and movement prediction for mobile gaming, as envisioned in [12], [20]; scene rendering in virtual or augmented reality environments, as mentioned in [11]; object detection and recognition for vehicle navigation [13], processing for object recognition in videos, 360-degree image or video reconstruction from agglomeration of partial data. These applications have one thing in common: they entail resource demanding computational processing and the output data (or an ample part of it) is useful to many different users. For example, all the players of an online interactive game need the same elements of the game's environment to be processed in the same way; all the avatars in a virtual reality world need the same rendering of the same objects; all the autonomous cars in a given region of the space need some common processing of the same data carried out by a local server or a small cell. In specific but not rare cases, these applications may simultaneously i) be handled by (clusters of) small cells at the edge of the network; ii) require frequent new processing and updating, which may not be entirely feasible “on-the-fly”; iii) be characterized by a considerable volume of cacheable results, among which a decision on what to cache needs to be taken; iv) include (sub)tasks which are independent from users' very specific data and are indeed executed in a repetitive manner. In such cases, the exploitation of computation caching at the edge cloud is envisaged and beneficial.

In this paper, we focus on the interaction among UEs, their SSC, and other collaborating small cells. The latter make

available the content of their caches to the SSC, in addition to serve their own UEs. Our goal is to investigate and quantify the benefits of computation caching, depending on different caching policies. We will formally define, evaluate, and compare three different low-complexity computation caching policies, including one newly proposed by us. We show that the latter performs optimally in several senses, significantly extending some initial results presented in [8] and clearly outperforming other state-of-the-art solutions. The proposed policies are enablers for *proactive* computation caching, intended as the strategy of adapting over time the content of small cell's cache memories, based on continuous learning of task popularity and other statistics.

To design efficient and effective computation caching policies, the importance of taking into account the popularity of offloadable tasks is motivated by the same arguments applicable in the context of classical content caching [14]. In addition, in this paper, we insist on the necessity to consider two more variables: the size of offloadable computations' *inputs* and the size of their *results* (or *outputs*). Depending on the application scenario, inputs and results may have significantly varying sizes. This implies that, during the computation offloading procedure, the quantity of cacheable data to download from the SSC (the results) can be substantially different from the quantity of data to upload from the UE to the SSC (the inputs). This marks a sharp difference with classical content caching, in which there are no such inputs to elaborate. Our most important novelty, introduced in [8] and further developed and investigated here, is the definition of a policy induced by a *caching metric* simultaneously based on offloadable tasks' popularity, size of input, and size of output. In particular, the combination of all the three variables into a single metric differentiates our work from that of other authors [10], [11], [13], [26]. Including the size of tasks' inputs in a computation caching metric is justified because, whenever an already cached task's result does not need to be computed, the associated communication costs (for uploading the input) and computational costs (for processing the input) are zeroed; hence, the gains yielded by computation caching (in terms of decreased latencies, energy saving, reduction of the SSC's computational workload, etc.) grow as an increasing function of the sizes of the inputs of offloadable computations themselves. Furthermore and not less importantly, caches concretely store the results of offloadable tasks, therefore the decision on which results to store in a finite (and possibly not capaciuos) small cell's cache also needs to be based on this variable.

This paper is structured as follows: in Section II, we present the system model, fix some notation, and describe the computation offloading procedure in a scenario with several small cells endowed with cache memories dedicated to computation caching. In Section III, we formalize a quantification of the costs associated with the offloading procedure, depending on the content of the caches of the involved small cells. Section IV contains the definition of the three caching metrics and induced policies that we investigate in this paper.
<figure><img src="image_3.png" /><figcaption>FIGURE 1. System model.</figcaption></figure>

Moreover, in Lemma 1, we mathematically characterize the optimal caching policy in a scenario with one small cell, when the costs of uploading and elaborating a task's input are proportional to its size and all results of tasks have the same standard size. Section V is dedicated to the numerical comparison of the proposed caching metrics. Therein, we focus on the interaction between one small cell and its users. We numerically evaluate several figures of merit to prove the goodness of the computation caching paradigm and, in some cases, to show the optimality of our novel caching metric. In Section VI, we propose a federation technique that provides a SSC with access to its neighboring small cells' cache memories (connected via backhaul) to retrieve task results that are not cached locally. We also propose a cooperative computing scheme in which neighboring small cells assist the SSC in the computation of non-cached task results. Some final remarks conclude the paper in Section VII.

## II. SYSTEM MODEL

Our system model, sketched in Fig. 1, includes UEs and small cells. The latter are nodes of the edge cloud through which UEs access the network and MEC services. We consider a set $S = \{s_1, \dots, s_N\}$ of $N$ small cells and we assume that each small cell serves a set of UEs and treats their computation offloading requests in a MEC framework [3], [22], [23], [35], [39]. This means that UEs can ask their SSC to run

computational tasks on their behalf. In such a case, the tasks' inputs are uploaded by the UE to the SSC, which executes the computational tasks, obtains the tasks' results, and sends them back to the UEs.

In our model, the communication rates between a UE and its SSC are denoted $R_{UL}$ in uplink and $R_{DL}$ in downlink and are measured in bit/s. Each small cell has a computational capacity of $f$ CPU cycles per second and is endowed with a cache memory entirely dedicated to computation caching, whose size is $m$ bits. We also suppose that small cells can communicate with each other via backhaul; the cell-to-cell communication rate is denoted $R_{BH}$ bit/s.

We call *offloadable tasks* the computational tasks that UEs can offload to their SSC. We consider a set of offloadable tasks $C = \{c_1, \dots, c_K\}$, called the *catalogue* of computations, with $|C| = K$. We suppose that the results of tasks in $C$ are *cacheable*, i.e., they can be cached in small cells' memories to be retrieved in a second time, whenever needed. A task $c_k \in C$ is modeled as a triplet $c_k = (W_k, e_k, W'_k)$, where $W_k$ is the task's input data (a sequence of bits) to be processed, $e_k$ is the number of CPU cycles per bit needed to elaborate the data, and $W'_k$ is the computation's result (another sequence of bits). We denote $|W_k|$ and $|W'_k|$ the sizes in bits of $W_k$ and $W'_k$.

Computation offloading is based on the assumption that, for a UE, transmitting the task's input to the SSC and downloading the task's result can cost less than locally and autonomously elaborating the result. This cost can be measured in time or energy, for instance, and an offloading request is typically sent whenever a UE estimates that its SSC can be helpful in increasing the UE's computation performance. Moreover, a computation offloading request may not be accepted by the SSC, depending on the availability of its resources, its workload, its capability to meet possible performance constraints imposed by the UE.

In this paper, we focus on the possibility to improve computation offloading (speed it up, make it less energy-demanding or cheaper, etc.) through computation caching. This paradigm consists in making available at small cells' caches the results of offloadable tasks, ready for downloading, thus bypassing the execution of the task itself, which is run once and for all in advance. In practice, we propose that, after the reception of an offloading request of a task $c_k \in C$ and before starting the computation, the SSC looks for $W'_k$ in its cache or in the caches of the small cells with which it shares a backhaul connection. If $W'_k$ is found (and if the retrieval costs are less than the computation costs), the SSC does not need to run the execution of $c_k$ and directly sends $W'_k$ to the UE that requested it.

Now, let $C_n$ represent the (content of the) cache of $s_n \in S$. To identify $C_n$ and, more generally, the union of caches of different small cells, we give the following definitions:

**Definition 1 (Cache Indicator):** $C_n$ is characterized by a cache indicator vector $\sigma^n = (\sigma_1^n, \dots, \sigma_K^n) \in \{0, 1\}^K$, such that $\sigma_k^n = 1$ if and only if the result of $c_k \in C$ is stored in the cache memory of $s_n$, i.e., $W'_k \in C_n$.
Definition 2 (Cumulative Cache Indicator): For a subset of small cells $\mathcal{T} \subseteq S$, we define the cumulative cache indicator $\sigma^{\mathcal{T}} = (\sigma_1^{\mathcal{T}}, \dots, \sigma_K^{\mathcal{T}}) \in \{0, 1\}^K$ as

$$ \sigma_k^{\mathcal{T}} := \begin{cases} 1, & \text{if } \sigma_k^n = 1, \exists n \text{ such that } s_n \in \mathcal{T} \\ 0, & \text{otherwise.} \end{cases} \qquad (1) $$

Cache indicators fully identify the content of caches. Since the cache size is limited to $m$ bits, in general not all vectors in $\{0, 1\}^K$ correspond to a feasible configuration of a cache $C_n$.

Definition 3 (Feasible Cache Indicators): We define the set of feasible cache indicators as follows:

$$ \mathcal{I} := \left\{ \sigma \in \{0, 1\}^K : \sum_{k=1}^{K} \sigma_k |W'_k| \leq m \right\}. $$

Let $s_n$ be the SSC of some UEs and let the small cells of $\mathcal{F} \subseteq S$ be its neighbors, i.e., they are connected to $s_n$ via backhaul, as in Fig. 1. Including computation caching, computation offloading occurs as follows:

1. A UE sends to the SSC $s_n$ a request that specifies the task to run and a latency constraint within which the result needs to be downloaded. Such an offloading request is denoted $r = (k, t)$, meaning that the UE asks for the execution of $c_k \in \mathcal{C}$ and to receive $W'_k$ within $t$ seconds.

2. **if $W'_k \in C_n$, then**

3. the request is accepted, $W'_k$ is directly sent back to the UE, and the procedure is concluded.

4. **else**

5. **if** retrieving $W'_k$ from a neighboring cell's cache costs more than computing it at the SSC, **then**

6. **if** $s_n$ has enough available resources to compute $W'_k$ and meet the latency constraint, **then**

7. the offloading request is accepted.

8. **else**

9. it is denied.

10. **end if**

11. **else**

12. $s_n$ sends a request for $W'_k$ to all $s_{n'} \in \mathcal{F}$.

13. **if $W'_k \in C_{n'}$, $\exists s_{n'} \in \mathcal{F}$, then**

14. $s_n$ downloads $W'_k$ from a neighbor, forwards it to the UE, and the procedure is concluded.

15. **else**

16. **if** $s_n$ has enough available resources to compute $W'_k$ and meet the latency constraint, **then**
17. the offloading request is accepted.

18. **else**

19. it is denied.

20. **end if**

21. **end if**

22. **end if**

23. **end if**

24. **if** the request is accepted but $W'_k$ was not found in any caches (line 7 or 17), **then**

25. $s_n$ asks to the UE to upload $W_k$, then computes $W'_k$, and finally sends it back to the UE.

26. **end if**

This procedure can be extended to include cooperative computing by letting the SSC offload the computation of non-cached task results to its neighbors [29]. We will propose a strategy to do so in Section VI-A.

### III. COST OF COMPUTATION OFFLOADING

The total cost of computation offloading is made of several independent contributions, among which we identify two main components, induced by line 25 of the offloading procedure detailed above:

i) the cost of uploading $W_k$ from the UE to the SSC;

ii) the cost of running the computation at the SSC.

Depending on the application, the word “cost” may indicate energy consumptions, time delays, or any other metric that quantifies an expense or the quality of a service. Nonetheless, in all scenarios, there are evident benefits in keeping available at small cells’ cache memories the results of offloadable tasks, before they are requested by the UE: indeed, whenever $W'_k \in C_n$ or $W'_k \in C_{n'}$ for some $s_{n'} \in \mathcal{F}$, the task $c_k$ does not need to be executed, $W_k$ does not need to be uploaded, and $W'_k$ can be straightforwardly sent to the UE. The most important consequence is that the two cost components i) and ii) are zeroed.

Now, let us formally express the cost of computation offloading. At first, let us consider a scenario with only one small cell ($s_n$) and its served UEs, without neighboring small cells ($\mathcal{F} = \emptyset$). Notice that, in this case, line 5 and lines 11 to 22 are not really executed during the computation offloading procedure of Section II. Then, the total cost of offloading $c_k \in \mathcal{C}$ (assuming that the offloading request is accepted by the SSC) can be essentially represented as:

$$ \Gamma_{\text{tot}}(c_k) = \Gamma_{\text{req}}(c_k) + (1 - \sigma_k^n) (\Gamma_{\text{UL}}(c_k) + \Gamma_{\text{comp}}(c_k)) + \Gamma_{\text{DL}}(c_k) + \gamma(c_k), \quad (2) $$

where $\Gamma_{\text{req}}(c_k)$ is the cost of sending $r = (k, t)$, the offloading request for the remote execution of $c_k$ (which does not include the transmission of the input $W_k$); $\sigma_k^n$ is the k-th entry of the SSC's cache indicator; $\Gamma_{\text{UL}}(c_k)$ is the cost of uploading $W_k$; $\Gamma_{\text{comp}}(c_k)$ is the cost of computing $W'_k$ (assuming, for simplicity, that the CPU state does not vary in time and the computation cost only depends on the task's parameters); $\Gamma_{\text{DL}}(c_k)$ is the cost of sending the result $W'_k$ back to the UE; and $\gamma(c)$ models any other fixed cost that does not directly depend on $c_k$, e.g., any constant processing cost at SSC's level or the cost of maintaining active the SSC's hardware, including the cache memory. The cost of reading a task's result from the cache is considered negligible.

Now, let $\mathcal{F} \neq \emptyset$. The SSC $s_n$ can retrieve task results via backhaul from its neighbors in $\mathcal{F}$. Supposing that $W'_k \in C_{n'}$ for some $s_{n'} \in \mathcal{F}$, let us call $\Gamma_{\text{BH}}(c_k)$ the cost of transmitting $W'_k$ from $s_{n'}$ to $s_n$. Let us also set

$$ \Lambda(c_k) := \Gamma_{\text{UL}}(c_k) + \Gamma_{\text{comp}}(c_k) \quad (3) $$
and

$$ \delta_k := \begin{cases} 0, & \text{if } \Lambda(c_k) > \Gamma_{\text{BH}}(c_k) \\ 1, & \text{otherwise.} \end{cases} \quad (4) $$

Then, (2) can be generalized to

$$ \Gamma_{\text{tot}}(c_k) = \Gamma_{\text{req}}(c_k) + (1 - \sigma_k^n) \left( \delta_k \Lambda(c_k) + (1 - \delta_k) \left( \Gamma_{\text{req}}^{\text{BH}}(c_k) + (1 - \Pi_k) \Gamma_{\text{BH}}(c_k) + \Pi_k \Lambda(c_k) \right) \right) + \Gamma_{\text{DL}}(c_k) + \gamma(c_k), \quad (5) $$

where $\Gamma_{\text{req}}^{\text{BH}}(c_k)$ represents the cost of forwarding the request for $W'_k$ from the SSC to its neighbors and

$$ \Pi_k := \prod_{n':s_{n'} \in \mathcal{F}} (1 - \sigma_k^{n'}) = \begin{cases} 0, & \text{if } \sigma_k^{n'} = 1, \exists s_{n'} \in \mathcal{F} \\ 1, & \text{otherwise.} \end{cases} \quad (6) $$

## IV. POLICIES FOR COMPUTATION CACHING

The previous considerations lead to the main question of this work: given the finite sizes of caches, how to choose which results of tasks to store at each small cell, with the goal of minimizing the overall costs? In other words, how to find the optimal feasible cache indicators? To answer, let us consider R offloading requests $r_1, \dots, r_R$, received by an SSC during a serving period, sent by its served UEs. By definition, every request uniquely corresponds to a task: for every $i = 1, \dots, R$, we have $r_i = (k, t)$, for some $k \in \{1, \dots, K\}$ identifying a task in $C$ and some latency constraint $t > 0$. Thus, setting $\Gamma_{\text{tot}}(c_{r_i}) = \Gamma_{\text{tot}}(c_k)$, we define the cost over the whole serving period as

$$ \Gamma(\sigma^1, \dots, \sigma^N) := \sum_{i=1}^{R} \Gamma_{\text{tot}}(c_{r_i}). \quad (7) $$

This cumulative cost depends on the content of each small cell's cache $C_n$ (identified by the cache indicators), as it is clear from (5) and (6). For our analysis, let us start by optimizing the cache indicators for a system with only one small cell. Such an assumption accurately represents also a scenario in which each small cell fills its cache independently from the others, without knowledge of the content of the other cells' caches, exclusively based on the R requests received from the UEs it is serving; in a second time, after a cache filling phase, small cells may decide to federate with each other to increase the effectiveness of computation caching. We will present in Section VI an algorithm for small cell federation. For now, let us focus on the interaction between a single small cell $s_n$ and its served UEs. The computation offloading cost over the whole serving period (7) reduces to

$$ \Gamma(\sigma^n) = \sum_{i=1}^{R} \Gamma_{\text{tot}}(c_{r_i}), \quad (8) $$

with $\Gamma_{\text{tot}}(c_{r_i}) = \Gamma_{\text{tot}}(c_k)$ as in (2). Our goal is to find the feasible cache indicator that minimizes (8):

$$ \sigma_{\text{opt}} := \arg \min_{\sigma \in \mathcal{I}} \Gamma(\sigma) = \arg \min_{\sigma \in \mathcal{I}} \left( \sum_{i=1}^{R} \Gamma_{\text{tot}}(c_{r_i}) \right). $$

For $r_i = (k, t)$, let $\sigma_{r_i} = \sigma_k$ and $\Lambda(c_{r_i}) = \Lambda(c_k)$. Then, since the addends in (2) that do not depend on $\sigma_k^n$ do not influence the minimization above, we have:

$$ \sigma_{\text{opt}} = \arg \max_{\sigma \in \mathcal{I}} \left( \sum_{i=1}^{R} \sigma_{r_i} \Lambda(c_{r_i}) \right). \quad (9) $$

Ideally, if $\sigma_{\text{opt}}$ is known, the SSC guarantees an optimal cost minimization by storing the $W'_k$ for which $(\sigma_{\text{opt}})_k = 1$, i.e., imposing $\sigma^n = \sigma_{\text{opt}}$. Since the number of cache indicators grows exponentially with $K = |C|$, it is in general not algorithmically possible to exhaustively determine $\sigma_{\text{opt}}$. A scope of this paper is to propose and evaluate low-complexity strategies to find feasible cache indicators with close-to-optimal associated performance. A natural approach is to hierarchically classify tasks and to fill the cache with the results of the tasks that maximize the chosen priority metric. More formally:

**Definition 4 (Caching Metric and Policy):** A caching metric $\lambda: C \to \mathbb{R}^+$ assigns to each task a "caching priority". The caching policy associated with metric $\lambda$ is the application of the following algorithm that caches tasks' results in descending order of priority, until $C_n$ is full:

1. Let $\phi: \{1, \dots, K\} \to \{1, \dots, K\}$ be a permutation such that $\lambda(c_{\phi(1)}) \ge \dots \ge \lambda(c_{\phi(K)})$.

2. Set $\sigma^n \leftarrow (0, 0, \dots, 0)$ and $s \leftarrow 0$.

3. **for** $k = 1, \dots, K$ **do**

4. **if** $s + |W'_{\phi(k)}| \le m$, **then**

5. set $\sigma_{\phi(k)}^n \leftarrow 1$ and $s \leftarrow s + |W'_{\phi(k)}|$.

6. **end if**

7. **end for**

8. Fill $C_n$ according to $\sigma^n$.

We denote $\sigma(\lambda)$ the indicator yielded by the previous algorithm.

Notice that the complexity of this algorithm is $O(K \log K)$: the complexity of computing $\lambda(c_k)$ for every $k$ is $O(K)$ and the complexity of sorting them is $O(K \log K)$.

Clearly, a caching policy for the SSC is based on a well-designed metric if $\Gamma(\sigma(\lambda))$ is close to $\Gamma(\sigma_{\text{opt}})$. A spontaneous observation, common to the context of content caching [14], [15], [21], [24], [36], is that a good caching policy needs to depend on the popularity of a task, intended as the frequency with which the task is requested with respect to the other tasks. Indeed, to reduce costs, we want to avoid to repeatedly and redundantly process frequently requested tasks. Thus, with every small cell $s_n \in S$ we associate a popularity vector $p^n \in [0, 1]^K$. Each $p_k^n$ represents the popularity of task $c_k$ as measured, learned, known, or estimated by $s_n$. In practice, $p_k^n$ represents the probability that the computation
offloading of $c_k$ is requested to the n-th small cell by the UEs that it is serving. In general, $p^n$ and $p^{n'}$ are different for $n \neq n'$, because the users associated with different small cells do not necessarily request the execution of the same tasks with the same probability. In our setting (and, in general, whenever the offloading requests are pairwise independent and if their total number $R$ is big enough), we can write:

$$p_k^n := \frac{|\{i : r_i = (k, t), \exists t > 0\}|}{R}. \quad (10)$$

We are ready to define three different caching metrics, which will induce three different caching policies, and which we will evaluate in the next sections.

**Definition 5:** *Simply based on task popularity, we define:*

$$\lambda_1(c_k) := p_k^n, \quad \forall k \in \{1, \dots, K\}.$$

$\lambda_1$ is essentially the computation caching metric used in [10], [11], [26] and corresponds to the policy of maximizing the cache hit ratio. We stress the point that, in the context of computation offloading, more effective metrics can be designed. For instance, a better choice comes from the observation that caching the result of a very popular task with low input uploading and computation cost $\Lambda(c_k)$ can be less advantageous than caching the result of a less popular task with a much higher cost. The latter directly depends on the size of the task's input $W_k$, denoted $|W_k|$. Therefore, we are led to the following:

**Definition 6:** *Based on popularity and input data size, let*

$$\lambda_2(c_k) := p_k^n |W_k|, \quad \forall k \in \{1, \dots, K\}.$$

In some specific cases, but not always, the caching policy induced by $\lambda_2$ is optimal:

**Lemma 1:** *Let us suppose that, for every $k \in \{1, \dots, K\}$,*

$$\Gamma_{\text{UL}}(c_k) = a|W_k| \quad \text{and} \quad \Gamma_{\text{comp}}(c_k) = b|W_k|, \quad (11)$$

for some constants $a, b > 0$. Let us also suppose that the results of tasks have all constant output size, i.e., $|W'_k| = w$ for every $k \in \{1, \dots, K\}$. Then, $\sigma(\lambda_2) = \sigma_{\text{opt}}$.

*Proof:* Let us call $\rho_k := |\{i : r_i = (k, t), \exists t > 0\}|$. Hence, by (9) and (10), we have

$$\begin{align*}
\sigma_{\text{opt}} &= \arg\max_{\sigma \in \mathcal{I}} \left( \sum_{i=1}^{R} \sigma_{r_i} \Lambda(c_{r_i}) \right) \\
&= \arg\max_{\sigma \in \mathcal{I}} \left( \sum_{k=1}^{K} \rho_k \sigma_k \Lambda(c_k) \right) \\
&= \arg\max_{\sigma \in \mathcal{I}} R \left( \sum_{k=1}^{K} p_k^n \sigma_k \Lambda(c_k) \right).
\end{align*}$$

Thanks to (11) and (3), we obtain

$$\sigma_{\text{opt}} = \arg\max_{\sigma \in \mathcal{I}} \left( \sum_{k=1}^{K} p_k^n \sigma_k |W_k| \right). \quad (12)$$

When $|W'_k| = w$, the cache can store at most $\lfloor m/w \rfloor$ computation results, independently from $k$. So,

$$\mathcal{I} = \left\{ \sigma \in \{0, 1\}^K : \sum_{k=1}^{K} \sigma_k \le \lfloor \frac{m}{w} \rfloor \right\}.$$

Consequently, the summation in (12) is maximized when $\sigma_k = 1$ for the $\lfloor m/w \rfloor$ tasks with the highest $p_k^n |W_k| = \lambda_2(c_k)$. This is equivalent to filling the cache according to the caching policy induced by $\lambda_2$, i.e., $\sigma(\lambda_2) = \sigma_{\text{opt}}$. ■

In this context, $\lambda_2$ corresponds to the metric used in [29], where it was already highlighted the need for a policy that takes into account both task popularity and input data size.

Now, the hypothesis that all $|W'_k|$ have standard constant size is not realistic for all applications. The novel metric that we propose is based on the observation that caching results of tasks whose size is small allows to store more of them. Hence, it may be more convenient to cache a high number of small-size results, even if their popularity and input size do not maximize $\lambda_2$.

**Definition 7 (Novel Caching Metric):** To increase the caching priority of tasks with small $|W'_k|$, we define:

$$\lambda_3(c_k) = \frac{p_k^n |W_k|}{|W'_k|}, \quad \forall k \in \{1, \dots, K\}.$$

Notice that in a scenario with one small cell, the research for $\sigma_{\text{opt}}$ among all feasible cache indicators turns out to be an instance of the “knapsack problem” and $\lambda_3$ is a known greedy heuristic for its solution [16]. We will show in Section V and VI that $\lambda_3$ is the most gainful metric of the three from several points of view, both in the single- and the multi-cell scenarios.

Notice also that the caching policies that we are considering do not take into account the latency constraints of computation tasks, because we assume that these are not constant for a given task. Indeed, the same cacheable task may be offloaded with different latency constraints by different UEs or by the same UE at different time intervals, depending on the instantaneous resource availability, workload, and performance requirements.

## V. NUMERICAL RESULTS WITH ONE SMALL CELL

In this section, we numerically evaluate the metrics defined in Section IV in a scenario with one small cell $s_n$ (the SSC). In our simulations, $|W_k|$ and $|W'_k|$ are chosen independently at random for every $k$ as follows: let $y, Y \in \mathbb{N}$ satisfy $y \le Y$ and let $x, X \in \mathbb{R}$ be two real numbers in $[1, 10]$ (with $x \le X$ if $y = Y$). When we say that $|W_k|$ belongs to $[xey : XeY[$, we mean that $x \cdot 10^y \le |W_k| < X \cdot 10^Y$ and $|W_k| = u \cdot 10^v$, with $u$ and $v$ randomly fixed as follows: first, $v$ is chosen uniformly in $\{y, y+1, \dots, Y\}$; then, $u$ is chosen uniformly either in $[x, 10[$ (if $v = y$) or in $[1, 10[$ (if $y < v < Y$) or in $[1, X[$ (if $v = Y$). The same rule is used for $|W'_k|$, independently from $|W_k|$. With this strategy, there is no privileged order of magnitude among the values taken by $|W_k|$ and $|W'_k|$, even when the maximum possible value is much bigger than the minimum.
<table><caption>TABLE 1. Main parameters for numerical simulations.</caption><thead><tr><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th></tr></thead><tbody><tr><td>R<sub>UL</sub></td><td>U(100, 500) Mbit/s</td><td>K</td><td>50000</td></tr><tr><td>R<sub>DL</sub></td><td>U(400, 600) Mbit/s</td><td>|W<sub>k</sub>|</td><td>[1e6 : 1e9 bit]</td></tr><tr><td>α (Zipf)</td><td>0.6</td><td>|W'<sub>k</sub>|</td><td>[1e3 : 1e9 bit]</td></tr><tr><td>μ (Poisson)</td><td>5</td><td>T</td><td>10<sup>7</sup></td></tr><tr><td>e<sub>k</sub>/f</td><td>10<sup>-8</sup> s/bit</td><td>R</td><td>10<sup>7</sup></td></tr></tbody></table>

In the figures whose abscissae represent the SSC's cache size, 0% means that $m = 0$ bits and 100% that $m = \sum_{k=1}^{K} |W'_{k}|$ bits. In all simulations, given a fixed cache size, the investigated figures of merit are numerically estimated after filling the SSC's cache according to one of the policies defined in Section IV, i.e., imposing $\sigma^n = \sigma(\lambda_j)$ for $j = 1, 2, 3$ (recall that $\sigma(\lambda)$ denotes the cache indicator induced by $\lambda$, as in Definition 4). Moreover, whenever possible, the performance of the three policies is compared to that of the optimal cache indicator $\sigma_{opt}$, obtained by solving (9) via the intlinprog function of MathWorks's MATLAB [25]. It is indispensable to notice that this function, which exploits branch and bound techniques to solve mixed-integer linear programming problems, has an exponential complexity in $K$ in worst-case scenarios, highly exceeding $O(K \log K)$, the complexity of the caching algorithms of Definition 4. The most important result of this section is to numerically show, whenever the comparison is possible, that our novel policy based on $\lambda_3$ achieves optimal performance with much lower complexity with respect to the caching strategy based on the explicit calculation of $\sigma_{opt}$. The other metrics of the state of the art, $\lambda_1$ and $\lambda_2$, have the advantage of low complexity too, but perform worse.

Unless stated otherwise, all the figures are obtained with the simulation parameters specified in Table 1. In particular, the uplink and downlink communication rates between the UEs and the SSC are independent instances of uniform random variables at every request or time interval. The baseline term of comparison of our work is a MEC network where computation offloading is performed without computation caching (i.e., cache size of 0%). The literature on computation offloading is ample and it also includes techniques to manage interference (e.g. [38] and references therein). Our analysis and simulation results are proposed “on top of” the computation offloading framework and suppose that state-of-the-art solutions are implicitly employed against interference. The variations of the quality of communications channels, modeled by the random physical data rates $R_{UL}$ and $R_{DL}$, allow us to abstract from the explicit definition of the radio channel model and interference. The addition of computation caching to the offloading scheme does not require an increase of radio communications with respect to the baseline computation offloading scenario. Therefore, in particular, it does not entail a worsening of the interference effects. For these

<figure><img src="image_4.png" /><figcaption>FIGURE 2. Uplink traffic reduction.</figcaption></figure>

reasons, an analysis of the inter-user or inter-cell interference is not proposed here.

As in analogous contexts [4], [5], [10], [11], we suppose that the popularity of offloading requests obeys Zipf's law:

$$p_k^n = \frac{A}{k^\alpha}, \quad (13)$$

for constant $\alpha$ and $A = (\sum_{k=1}^{K} k^{-\alpha})^{-1}$. Notice that, without loss of generality, tasks can be assumed to be sorted in the catalogue by descending popularity: the most popular task is $c_1$, the second-most popular is $c_2$, and so on.

Fig. 2 shows, as a function of the cache size, the percentage of task input data that do not need to be uploaded nor processed, because the corresponding results are already cached in $C_n$ and available for downloading. This quantity is called reduction of uplink input traffic but also straightforwardly entails a reduction of computational workload for the SSC. It is a very meaningful measure of the reduction of costs induced by computation caching, because it is directly associated with the cost denoted $\Lambda(c_k)$ in (3), which is zeroed for the tasks whose $W'_k$ is cached. In particular, whenever $\Gamma_{UL}(c_k)$ and $\Gamma_{UL}(c_k)$ are linear in $|W_k|$, the reduction of uplink input traffic is equal to the reduction of $\Lambda(c_k)$. Mathematically, Fig. 2 represents the following quantity, for $\sigma^n = \sigma(\lambda_1), \sigma(\lambda_2), \sigma(\lambda_3), \sigma_{opt}$:

$$\frac{\sum_{i=1}^{R} \sigma_{ri}^{n} |W_{ri}|}{\sum_{i=1}^{R} |W_{ri}|} = \frac{\sum_{k=1}^{K} p_{k}^{n} \sigma_{k}^{n} |W_{k}|}{\sum_{k=1}^{K} p_{k}^{n} |W_{k}|}, \quad (14)$$

where $\sigma_{ri}^n$ and $|W_{ri}|$ are respectively equal to $\sigma_k^n$ and $|W_k|$ for a request $r_i$ for the offloading of task $c_k$. Measuring (14) is an effective approach to evaluate the goodness of the caching policies: the higher (14), the higher the corresponding saving in energy, time, or any other cost metric, both for the UE and for the SSC. Fig. 2 suggests two main considerations: first, as already anticipated, that the performance associated with metric $\lambda_3$ is essentially superimposed to the optimal; second, that $\lambda_1$ and $\lambda_2$ are clearly outperformed, especially for cache sizes between 0% and 40%. These are the sizes which interest us the most, because an effective caching
<figure><img src="image_5.png" /><figcaption>FIGURE 3. Uplink input traffic reduction gain between $\lambda_3$ and $\lambda_1$ as a function of the Zipf parameter.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>FIGURE 4. Uplink input traffic reduction gain between $\lambda_3$ and $\lambda_2$ as a function of the Zipf parameter.</figcaption></figure>

strategy needs to achieve a good performance with a cache as small as possible. Remarkably, for a cache only as big as 2% of the total size and with a corresponding computational complexity way lower than that required to obtain $\sigma_{opt}$, our metric $\lambda_3$ allows to reduce the uplink input traffic (and the associated communication and computation costs) by more than 80%, whereas $\lambda_1$ and $\lambda_2$ respectively achieve around 20% and 30%.

Notice that quantitatively the better effectiveness of $\lambda_3$ with respect to the other two metrics depends, among other things, on the parameter $\alpha$ that characterizes Zipf's distribution of the offloading requests. Fig. 3 and Fig. 4 depict the gain in reduction of uplink input traffic between $\lambda_3$ and respectively $\lambda_1$ and $\lambda_2$, as a function of $\alpha$ and for different fixed cache sizes. This gain can be written as

$$ \frac{\sum_{i=1}^{R} \sigma(\lambda_3)_{r_i} |W_{r_i}|}{\sum_{i=1}^{R} \sigma(\lambda_j)_{r_i} |W_{r_i}|} = \frac{\sum_{k=1}^{K} p_k^n \sigma(\lambda_3)_k |W_k|}{\sum_{k=1}^{K} p_k^n \sigma(\lambda_j)_k |W_k|}, $$

with $j = 1$ for Fig. 3 and $j = 2$ for Fig. 4. The gain of $\lambda_3$ over the two other metrics is more pronounced for small $\alpha$.

Fig. 5 compares the caching metrics in terms of cache hit ratio. By definition, this is the number of times that the results

<figure><img src="image_7.png" /><figcaption>FIGURE 5. Cache hit ratio.</figcaption></figure>

of the offloading requests are found in the cache, divided by the total number of requests:

$$ \frac{1}{R} \sum_{i=1}^{R} \sigma_{r_i}^{n} = \sum_{k=1}^{K} p_k^n \sigma_k^n, $$

for $\sigma^n = \sigma(\lambda_1), \sigma(\lambda_2), \sigma(\lambda_3), \sigma_{opt}$. Notice that in the context of computation caching, the cache hit ratio is not the most relevant figure of merit to evaluate the performance of the system. Indeed, maximizing the cache hit ratio is equivalent to applying the caching policy based on $\lambda_1$, which is not optimal in a computation offloading scenario, as mentioned after Definition 5 and as confirmed by Lemma 1 and the numerical simulations of this section. The reason is that the offloading costs do not exclusively depend on task popularity, but also (and crucially) on the amount of data to transmit and process. Having said this, the analysis of the cache hit ratio depicted in Fig. 5 leads to two observations: first, weighting the task popularity by the task's input size to define $\lambda_2$ causes a loss in the cache hit ratio performance; this is obvious, because $\lambda_1$ is by design a metric aimed at maximizing the cache hit ratio. Second, more importantly, this loss is completely recovered and even outdone by $\lambda_3$, which promotes for being cached the tasks with small-size results. This endorses the intuition on which $\lambda_3$ is built: storing more results, even if they do not correspond to the most popular and costly tasks in absolute, contributes to yield considerable gains.

To draw Fig. 6, we consider the whole offloading operation, made of four main serial steps: offloading request, input data uploading, task computation, result downloading. If the results of the computation are found in the SSC's cache, data uploading and task computation are skipped and the results directly sent to the UE. In this case, we assume that a new offloading request is sent instantaneously after the results of the previous one are downloaded. We also assume that the latency constraint is satisfied for every offloading request; this is equivalent to supposing that the communication rates and the SSC's computational capacity are high enough and do not influence the comparison of the caching metrics. The time needed to treat an offloading request whose result is cached
<figure><img src="image_8.png" /><figcaption>FIGURE 6. Gain in served offloading requests per minute.</figcaption></figure>

is clearly less than the time needed in absence of caching. Therefore, Fig. 6 shows the number of computation offloading requests treated per minute, as a function of the cache size, divided by the number of treated requests in absence of caching. Measuring this gain involves the computation of the offloading time for every request. In the notation of (2), where in this case $\Gamma_{\text{tot}}(c_k)$ indicates the total offloading time for $c_k = (W_k, e_k, W'_k)$, we have $\Gamma_{\text{req}}(c_k) = 128 \text{ bits}/R_{\text{UL}}$ (where we suppose that a request $r_i = (k, t)$ has a standard size $|r_i|$ of 16 bytes), $\Gamma_{\text{UL}}(c_k) = |W_k|/R_{\text{UL}}$, $\Gamma_{\text{comp}}(c_k) = e_k|W_k|/f$, and $\Gamma_{\text{DL}}(c_k) = |W'_k|/R_{\text{DL}}$. We also add to the previous terms a latency of 0.1 ms, corresponding to $\gamma(c_k)$. Fig. 6 reasserts the optimality of $\lambda_3$, which allows gains of a factor 9 for cache sizes of less than 20%, whereas the gains yielded by the other metrics do not go beyond a factor 4. Practically, these gains translate into reduced uplink transmissions and SSC's computational workload, facilitating the prevention of uplink bottlenecks.

From Fig. 7 to Fig. 12, given a cache size and after filling the SSC's cache, we consider $T$ successive time intervals, each of duration $\Delta$ seconds. During each time interval $\tau$, for $\tau = 1, \dots, T$, the SSC receives and treats a random number of offloading requests $R_\tau$, modeled as a Poisson random variable with mean $\mu$ (i.i.d. over the $T$ intervals). For each $\tau$, the $R_\tau$ requests correspond to computational tasks chosen at random, independently for every request, respecting Zipf's distribution of tasks' popularity.

The average computational delay depicted in Fig. 7 represents the time needed to compute the results of the $R_\tau$ offloading requests received at time interval $\tau$, averaged over the total number of time intervals $T$. Here, we are considering the purely computational delay: if $D_r$ is the computational delay corresponding to the execution of task $c_k$ solicited via request $r$, we have

$$D_r := (1 - \sigma_k^n) \frac{e_k |W_k|}{f}, \quad (15)$$

for $\sigma^n = \sigma(\lambda_1), \sigma(\lambda_2), \sigma(\lambda_3), \sigma_{\text{opt}}$. Hence, Fig. 7 depicts $\frac{1}{T} \sum_{\tau=1}^{T} \sum_{i=1}^{R_\tau} D_{r_i}$. Notice that (15) equals 0 when a task's result is cached ($\sigma_k^n = 1$), causing the computational delay

<figure><img src="image_9.png" /><figcaption>FIGURE 7. Average computational delay per time interval.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>FIGURE 8. Probability of computational resource outage.</figcaption></figure>

to tend to 0 when the cache size increases. $\lambda_3$ proves to be optimal also in this case. It yields a gain of a factor almost 10 for a cache size fixed to 5%, with respect to the system in absence of computation caching (cache size of 0%).

Now, let us call $D_\tau$ the computational delay needed by the SSC to compute all the $R_\tau$ computation offloading results requested at time interval $\tau$, i.e., $D_\tau = \sum_{i=1}^{R_\tau} D_{r_i}$. For our simulation purposes, we consider that a computational resource outage occurs if $D_\tau > \Delta$, i.e., if the computation of the tasks' results requested at time interval $\tau$ is not complete within the end of the interval itself. Measuring this outage provides a first evaluation of the capacity of the system to withstand the simulated workload. Indeed, computational resource outages correspond to delays in the treatment of task offloading requests, eventually leading to buffer overflows in real-life systems and high denial rates for incoming offloading requests. Hence, a system with a high computational resource outage probability is poorly dimensioned. For $\Delta = 1$ s, Fig. 8 shows the measured computational resource outage probability as a function of the cache size. Fig. 9, instead, shows the computational resource outage probability for a cache size fixed to 5%, as a function of the average number of offloading requests per time interval $\mu$. Furthermore, Fig. 10 depicts the computational resource outage probability
<figure><img src="image_11.png" /><figcaption>FIGURE 9. Probability of computational resource outage for $m = 5\%$, as a function of the average number of requests per time interval $\mu$.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>FIGURE 10. Probability of computational resource outage for $m = 5\%$, as a function of the SSC's computational capacity.</figcaption></figure>

as a function of the SSC's computational capacity. The three figures highlight once again that $\lambda_3$ is significantly better suited with respect to $\lambda_1$ and $\lambda_2$: for the same cache size, average number of requests per time interval, or SSC's computational capacity, $\lambda_3$ induces lower outage probabilities, thus guaranteeing an overall better quality of service. Fig. 10 also shows that, for a targeted computational outage probability, systems relying on computation caching with metric $\lambda_3$ require less computational capacity with respect to $\lambda_2$ and $\lambda_1$.

In this context, we call required computational capacity the computational capacity (in processed input bits per second) that the SSC needs to incur a computational resource outage at time interval $\tau$ with probability not higher than $10^{-3}$. Fig. 11 compares the required computational capacities in scenarios with and without computation caching and depending on the different caching metrics, as a function of $\mu$ and for a fixed cache size of 5%. The comparison is made in terms of a gain factor: if the gain of $\lambda_j$ versus $\lambda_i$ is $x$, it means that a SSC using the caching policy induced by $\lambda_j$ has a required computational capacity $x$ times smaller than that of a SSC that bases its caching decisions on $\lambda_i$. One can notice how these gains increase with $\mu$.

<figure><img src="image_13.png" /><figcaption>FIGURE 11. Gain in required computational capacity to guarantee a computational resource outage probability smaller than $10^{-3}$.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>FIGURE 12. UE's energy consumption per task input bit to be offloaded or locally elaborated, averaged over time.</figcaption></figure>

In Fig. 12, we provide an estimation of the benefits that a UE perceives in terms of consumed energy per task input bit to be either offloaded or locally elaborated, when computation caching is performed at the SSC. More precisely, we consider that, at the beginning of each time interval $\tau$, a UE sends to the SSC $R_{\tau}$ computation offloading requests. Based on its computational capacity, on the knowledge of the instantaneous communication rates, and on the parameters that characterize each task $c_k = (W_k, e_k, W'_k)$, the SSC accepts only the first $\ell$ offloading requests that can be treated without leading to a computational resource outage: if $D_r$ is the computational delay (15) corresponding to the execution of the task associated with request $r$, then

$$ \ell := \max \left\{ l \in \{0, \dots, R_{\tau}\} : \sum_{i=1}^{l} D_{r_i} \le \Delta \right\}. $$

Thus, at each time interval $\tau$, the first $\ell$ requests are treated by the SSC and the last $R_{\tau} - \ell$ by the UE itself, which needs to locally compute the associated results. In such a simulation, we fixed $\Delta = \mu \sum_{k=1}^{K} p_k^n |W_k| e_k / f_{UE}$, the average computational delay per time interval without caching, where $f_{UE}$ is the computational capacity of the UE, $e_k / f_{UE} = 10^{-6}$ s/bit. The energetic cost for the UE at each time interval $\tau$ can be
written as follows:

$$E_{\tau} := \sum_{i=1}^{\ell} \left( (1 - \sigma_{r_i}^n) P_{UL} \frac{|W_{r_i}|}{R_{UL}} + P_{DL} \frac{|W'_{r_i}|}{R_{DL}} \right) + \sum_{i=\ell+1}^{R_{\tau}} P_{\text{comp}} \frac{|W_{r_i}| e_{r_i}}{f_{\text{UE}}},$$

where $P_{\text{comp}} = 5$ W is the power that the UE consumes for computing, whereas $P_{UL}$ and $P_{DL}$ are the powers it consumes for uplink and downlink communication at rates $R_{UL}$ and $R_{DL}$. More precisely, $P_{UL}$ and $P_{DL}$ are computed according to the empirical model presented in [19]. They are both the sum of three elements: a signal processing component ($P_{\text{TxBB}}$ and $P_{\text{RxBB}}$, respectively), a radio component ($P_{\text{TxRF}}$ and $P_{\text{RxRF}}$, respectively), and a circuitry consumption component ($P_{\text{TxON}}$ and $P_{\text{RxON}}$, respectively). Hence, the power consumption for uplink communication equals

$$P_{UL} = P_{\text{TxON}} + P_{\text{TxRF}} + P_{\text{TxBB}} \quad [\text{mW}],$$

where $P_{\text{TxON}} = 29.9$ mW, $P_{\text{TxBB}} = 0.62$ mW, and $P_{\text{TxRF}}$ (measured in mW) depends on the UE's transmission power $P_{\text{Tx}}$ (expressed in dBm) as follows:

$$P_{\text{TxRF}} = \begin{cases} 0.78P_{\text{Tx}} + 23.6 & P_{\text{Tx}} \le 0.2 \\ 17P_{\text{Tx}} + 45.4 & 0.2 < P_{\text{Tx}} \le 11.4 \\ 5.9P_{\text{Tx}}^2 - 118P_{\text{Tx}} + 1195 & 11.4 < P_{\text{Tx}} \end{cases}$$

By Friis equation and Shannon capacity formula, the UE's transmission power is computed as

$$P_{\text{Tx}} = (2^{R_{\text{UL}}/B} - 1)\sigma^2 \left( \frac{4\pi d}{l\sqrt{G_{\text{Tx}}G_{\text{Rx}}}} \right)^2,$$

where $B = 20$ MHz is the bandwidth of the signal, $\sigma^2 = N_0B$ is the power of the Gaussian noise with spectral density $N_0 = -174$ dBm, $d = 200$ m is the distance between the UE and the SSC, $l = 10$ cm is the wavelength of the signal, and $G_{\text{Tx}} = 2$ dB and $G_{\text{Rx}} = 10$ dB are the antenna gains at the UE and at the SSC respectively.

The power consumption at the UE for downlink communications, instead, is computed as

$$P_{DL} = P_{\text{RxON}} + P_{\text{RxRF}} + P_{\text{RxBB}} \quad [\text{mW}],$$

with $P_{\text{RxON}} = 25.1$ mW,

$$P_{\text{RxBB}} = 0.97 R_{\text{DL}} + 8.16 \quad [\text{mW}],$$

with $R_{\text{DL}}$ expressed in Mbit/s, and

$$P_{\text{RxRF}} = \begin{cases} -0.04P_{\text{Rx}} + 24.8 & P_{\text{Rx}} \le -52.5 \\ -0.1P_{\text{Rx}} + 7.86 & P_{\text{Rx}} > -52.5 \end{cases}$$

where $P_{\text{Rx}}$ is the power received at the UE:

$$P_{\text{Rx}} = (2^{R_{\text{DL}}/B} - 1)\sigma^2,$$

with $B = 10$ MHz.

Fig. 12 depicts, for the different caching metrics, the UE's energetic costs per offloaded or computed task input bit, averaged over the $T$ time intervals:

$$\frac{1}{T} \sum_{\tau=1}^{T} \frac{E_{\tau}}{\sum_{i=1}^{R_{\tau}} |W_{r_i}|}.$$

Notice how for a cache size of 5%, the caching policy based on $\lambda_3$ allows an energy reduction of a factor almost 3 with respect to the system in absence of caching (cache size of 0%), at least twice better than the gains yielded by the other policies.

## VI. A TECHNIQUE FOR SMALL CELL FEDERATION

In this section, we investigate a scenario where several federated small cells cooperate with the SSC. We will provide an answer to the following questions: how does the possibility to share cached results via backhaul connections improve the computation offloading performance? Moreover, given all the small cells of the system, how can the SSC choose which ones to federate with? We will start by addressing the latter question, then we will provide some numerical simulations to answer the former. Finally, in the second part of the section, we will investigate a scenario where neighboring small cells can help the SSC in computing non-cached task results.

First and foremost, we would like to define a criterion that the SSC can apply to select a subset of its neighboring cells with which to collaborate during the offloading procedure. The reason to restrict the set of collaborators to a “small enough” set of small cells can be motivated by several factors, e.g., the necessity to limit the overhead communications for cluster management to avoid backhaul congestion. The federation technique that we are about to describe is “ad hoc” for each small cell, in the sense that each $s_n$ can apply it to create its own cluster of cooperating neighbors and all clusters will be generally different. Such technique can be either applied by each small cell on its own or managed by an overarching orchestrator that handles the cluster configuration. The only requirement is that all the cache indicators $\sigma^n$ are known. Practically, we can assume that caches are first filled independently, each small cell according to the need of its served UEs, as in Section V. Then, cache indicators are shared among all the small cells of the system or with the overarching orchestrator and clusters of small cells are created. This procedure can be repeated whenever an update is needed, but we consider here that the parameters that influence the caching decisions are stable over “long enough” coherence times.

In general, the federation with a neighbor $s_{n'}$ is beneficial to the SSC $s_n$ if two conditions are met: if the cache $C_{n'}$ of $s_{n'}$ contains results which are not available in $C_n$; and if the cost of retrieving those results via backhaul is less than the cost spent by $s_n$ to compute them, i.e., $\delta_k = 0$ in (4).

**Definition 8 (Federation Reward Per Task):** Inspired by the second condition, we define the reward perceived by $s_n$ when it can retrieve from a neighboring cell a result $W'_k \notin C_n$
as:

$$g_k := (1 - \delta_k) p_k^n (\Lambda(c_k) - \Gamma_{BH}(c_k)),$$

where $\delta_k$, $\Lambda(c_k)$ and $\Gamma_{BH}(c_k)$ are defined as in (4).

This reward represents, for every $c_k$, the cost reduction (weighted by the task's popularity) induced by the possibility of retrieving $W'_k$ from a neighbor.

**Definition 9 (Absolute Preference):** We define the preference of the SSC $s_n$ for a neighbor $s_{n'}$ as

$$\pi_{n'}^n := \sum_{k=1}^{K} \sigma_k^{n'} (1 - \sigma_k^n) g_k.$$

$\pi_{n'}^n$ is a preference metric that $s_n$ can use to measure the utility of federating with another small cell. This preference quantifies the total reward obtained by the SSC when it has access to $C_{n'}$. Only task results which belong to $C_{n'}$ but not to $C_n$ contribute to the total reward, as ensured by the product $\sigma_k^{n'} (1 - \sigma_k^n)$. More generally:

**Definition 10 (Conditioned Preference):** If $\mathcal{F} \subseteq \mathcal{S}$ is a set of small cells federated with the SSC and $\mathcal{T} = \{s_n\} \cup \mathcal{F}$, then the preference that the SSC has for adding $s_{n'} \notin \mathcal{T}$ to the federated cluster, conditioned to the already existing cluster, is

$$\pi_{n'}^{\mathcal{T}} := \sum_{k=1}^{K} \sigma_k^{n'} (1 - \sigma_k^{\mathcal{T}}) g_k,$$

where $\sigma^{\mathcal{T}}$ is the cumulative cache indicator of $\mathcal{T}$ (1).

This allows us to develop the following clustering algorithm to build $\mathcal{T}$:

1. Set $\mathcal{T} \leftarrow \{s_n\}$ and $\mathcal{F} \leftarrow \emptyset$.

2. repeat

3. Find

$$\hat{n} := \arg \max_{n' : s_{n'} \notin \mathcal{T}} \pi_{n'}^{\mathcal{T}}.$$

4. Set $\mathcal{T} \leftarrow \mathcal{T} \cup \{s_{\hat{n}}\}$ and $\mathcal{F} \leftarrow \mathcal{F} \cup \{s_{\hat{n}}\}$.

5. **until** a desired stopping criterion is reached.

Stopping criteria can be, for instance, the maximum size of a small cell cluster or a targeted cumulative cache size. Once $\mathcal{F}$ is established, the computation offloading procedure occurs as described at the end of Section II.

From Fig. 13 to Fig. 16, we show the numerically evaluated performance of computation offloading with small cell federation and computation caching carried out via the policies defined in Section IV. Like in Section V, the main simulation parameters are those of Table 1. The backhaul data rate $R_{BH}$ between the SSC $s_n$ and each one of its federated neighbors in $\mathcal{F}$ is considered equal to 10 Gbit/s. The popularity of offloading requests obeys Zipf's law. For $s_n$, we fix $p_k^n = Ak^{-\alpha}$, as in (13). Instead, for all the other small cells, let $\phi_{n'}: \{1, \dots, K\} \to \{1, \dots, K\}$ be a random permutation of K elements (i.e., of the K tasks); then, to represent the different popularity patterns of the different groups of UEs served by different small cells, we suppose that $p_k^{n'} = p_{\phi_{n'}(k)}^n$. In practice, the set of popularity values taken by tasks is the same, but with shuffled order.

<figure><img src="image_15.png" /><figcaption>FIGURE 13. Uplink traffic reduction as a function of the number of federated neighbors.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>FIGURE 14. Gain in served offloading requests per minute as a function of the number of federated neighbors.</figcaption></figure>

The figures of merit depicted from Fig. 13 to Fig. 16 are the uplink traffic reduction, the gain in the number of treated offloading requests per minute, the probability of computational resource outage, and the average computational delay, all defined as in Section V with respect to the computation offloading requests received by the SSC, for a fixed cache size of 5% for every small cell. All caches are filled at the beginning of the simulation, following one of the three caching policies of Section IV. Recall that $C_n \neq C_{n'}$ for $n \neq n'$, due to the different popularity patterns “perceived” by different small cells. For Fig. 14, $\gamma(c_k) = 0.1$ ms and $|r_i| = 16$ bytes, as for Fig. 6. The figures are plotted this time as a function of the number of neighbors with which the SSC federates, using the clustering algorithm presented above. In particular, 0 federated neighbors means that the SSC operates on its own.

In addition, Fig. 13, 14, and 16 show an upper (UB) or lower bound (LB) to the optimal performance. These bounds can be traced because they depend on the knowledge of the optimal cache indicator in the single-small-cell case for the corresponding performance metrics. More precisely, these bounds are achieved when the whole network operates to maximally improve the SSC's performance and the SSC's
<figure><img src="image_17.png" /><figcaption>**FIGURE 15.** Probability of computational resource outage as a function of the number of federated neighbors.</figcaption></figure>

neighbors fill their caches as if they were an “extension” of the SSC’s cache, neglecting their users’ interests and popularity of requests. Namely, the bounds are obtained with non-overlapping caches (orthogonal cache indicators) and, given a cluster of $|T|$ federated small cells including the SSC, by letting coincide the cumulative cache indicator (1) with the optimal cache indicator of the single-small-cell case with a cache size $|T|$ times bigger than the cache size of one small cell. Notice that, albeit formally achievable by the SSC’s performance, these bounds capture an “unbalanced” network behavior, where the SSC is favored to the detriment of the other cells.

The numerical simulations show, first of all, that $\lambda_3$ induces better results than $\lambda_2$ and $\lambda_1$ also in this multi-cell scenario for all the studied figures of merit. More importantly, in our setup, the system yields a better performance when the SSC is alone (i.e., with 0 federated neighbors) and bases its caching decisions on $\lambda_3$, rather than in presence of up to 19 neighbors but using $\lambda_1$ or $\lambda_2$. This means that $\lambda_3$ is a strong caching metric, which in our simulated scenario boosts the performance of computation caching independently from the presence of neighboring cells that assist the SSC. We conclude that small cell clustering becomes progressively more and more effective when $|W'_k|$ changes from spanning through several orders of magnitude to tending to a constant. Indeed, in this case, the performance related to $\lambda_3$ gradually tends to that of $\lambda_2$, for which the effect of cache federation is instead not negligible.

## A. COOPERATIVE COMPUTING OF TASK RESULTS

Our work draws attention to the importance of choosing the right policy for computation caching. One of the main messages of the paper is that a good policy can, by itself, drastically improve the computation caching performance. To be able to focus on a “pure” comparison of policies and quantify their performance differences, we need to decouple the effects of the choice of the policy from other performance improving factors. For this reason, in the first part of this section we allowed neighboring small cell to share among themselves

<figure><img src="image_18.png" /><figcaption>**FIGURE 16.** Average computational delay per time interval as a function of the number of federated neighbors.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>**FIGURE 17.** Gain in served offloading requests per minute as a function of the number of federated neighbors, with and without cooperative computing (denoted “c.c.”).</figcaption></figure>

the content of their caches, but not their computational power. In this subsection, we make a step further and investigate the computation offloading performance induced by computation caching policies in a scenario where the SSC can share its computational workload with its neighbors.

Let us suppose that the SSC $s_n$ receives $R_\tau$ offloading requests at every time instant $\tau \in \{1, \dots, T\}$, with $E[R_\tau] = \mu = 20$. As before, the SSC is federated with its neighbors $\mathcal{F}$ and each small cell’s cache is filled according to the strategy presented before. At every time interval $\tau$, in addition to sharing its cache’s content, each neighbor makes available part of its computational resources to the SSC. Thus, the computation of the requested task results that are cached neither by the SSC nor by its neighbors, can be carried out by any small cell in $T$, not only by $s_n$. In Fig. 17, we evaluate how collaborative computing improves the gain in the number of treated requests per minute (the same figure of merit of Fig. 6 and 14). The improvement comes from the fact that the offloading requests can be treated in parallel by more than one small cell at the same time. In our numerical simulation, we suppose that each neighbor of $s_n$ makes available a computational power between $10^{-7}$ and $10^{-8}$ s/bit, chosen uniformly at random at each time interval $\tau$. The $R_\tau$
offloading requests are assigned one by one to the small cell in $\mathcal{T}$ that minimizes the overall offloading time, including backhaul communications when the task request is treated by one of the neighbors of the SSC; the assignment is performed in order of arrival and taking into account for request $r_i$ the delays induced by previous assignments $r_1, r_2, \dots, r_{i-1}$. More precisely, let us call $s(r)$ the small cell of $\mathcal{T}$ appointed with treating offloading request $r$. The choice of $s(r)$ for every $r$ is made according to the following algorithm, conceived to balance the overall workload and leverage parallel computation of results:

1. **for all** $s \in \mathcal{T} = \{s_n\} \cup \mathcal{F}$ **do**

2. Set $\Gamma_s \leftarrow 0$.

3. **end for**

4. **for** $i = 1, 2, \dots, R_\tau$ **do**

5. **if** $\sigma_{r_i}^n = 1$ **then**

6. Set $s(r_i) \leftarrow s_n$.

7. **else**

8. Set $\theta(s_n) \leftarrow \Gamma_{s_n} + \Lambda(c_{r_i})$.

9. **for all** $s_{n'} \in \mathcal{F}$ **do**

10. Set $\theta(s_{n'}) \leftarrow \Gamma_{s_{n'}} + \Gamma_{\text{req}}^{\text{BH}}(c_{r_i}) + \Gamma_{\text{BH}}(c_{r_i}) + (1 - \sigma_{r_i}^{n'})(\Gamma_{\text{BH}}^{\text{UL}}(c_{r_i}) + \Lambda(c_{r_i}))$.

11. **end for**

12. Find $\hat{s} := \arg \min_{s \in \mathcal{T}} \theta(s)$.

13. Set $s(r_i) \leftarrow \hat{s}$ and $\Gamma_{s(r_i)} \leftarrow \theta(\hat{s})$.

14. **end if**

15. **end for**

The costs that appear in the previous algorithm are those defined in (5), with the addition of $\Gamma_{\text{BH}}^{\text{UL}}(c_{r_i}) = |W_{r_i}|/R_{\text{BH}}$ and $\Gamma_s$. The former represents the time required to send the task input via backhaul from the SSC $s_n$ to a neighbor; $\Gamma_s$, instead, represents the cost associated with small cell $s$ that depends on the cache indicators and the task assignment strategy. It is computed inside the algorithm and takes into account all the task request assigned to a small cell $s$. Finally, the $\theta(s)$ are auxiliary parameters used for intermediate calculations.

With this procedure, the total offloading time of the $R_\tau$ requests received at time $\tau$ by the SSC and handled through cooperative computing by the whole ad hoc cluster, is

$$ \sum_{i=1}^{R_\tau} \Gamma_{\text{tot}}(c_{r_i}) = \Gamma' + \max_{s \in \mathcal{T}} \Gamma_s, $$

where

$$ \Gamma' := \sum_{i=1}^{R_\tau} (\Gamma_{\text{req}}(c_{r_i}) + \Gamma_{\text{DL}}(c_{r_i}) + \gamma(c_{r_i})) $$

is the part of the overall cost that does not depend neither on cooperative computing nor on computation caching.

In Fig. 17, for each computation caching metric, the gain in the number of treated requests per minutes is compared between the case when cooperative computing is performed and when it is not. The former is indicated with the acronym “c.c.” in the figure’s legend; the latter coincides with the results plotted in Fig. 14. Clearly, collaborative computing improves the overall network performance. Once again,

the best performance is yielded by $\lambda_3$, whereas the most tangible improvement is obtained when the small cells fill their cache according to $\sigma(\lambda_2)$. Intuitively, this behavior is justified because, by design, $\lambda_2$ promotes caching less task results with respect to $\lambda_3$ (for a given cache size); this leaves more room for a performance improvement through cooperative computing to the system based on $\lambda_2$. With respect to $\lambda_1$, instead, $\lambda_2$ promotes caching of more computationally costly task outputs, leaving out computational tasks which are usually faster to run. This implies that in general more requests are treated through cooperative computing by a system exploiting $\lambda_2$ rather than $\lambda_1$.

## VII. CONCLUSION AND FUTURE WORK

In this paper, we studied computation caching, which combines caching with the problem of dealing with the costs of producing the data to cache. Tying these two aspects together into the framework of computation caching is the key to exploit caching in a novel way for the new use cases of the 5G revolution. We focused on the study, evaluation, and benchmarking of policies for proactive computation caching. We proved the crucial importance of including the size of offloadable tasks’ results in the design of well-performing caching policies. In particular, we measured the effectiveness of our proposed caching metric via several performance indicators, both in a single- and a multi-cell scenario. In addition, we showed that our novel metric yields very good results in the single-cell scenario, in some cases achieving optimality and outdoing the other main metrics adopted in the literature. This result is achieved at low computational complexity.

The benefits of computation caching are shown in terms of reduction of uplink traffic from UEs to SSCs, reduction of communication and computation costs for both the UEs and the SSCs, increased number of computation offloading requests treatable for a fixed SSC’s capacity, diminished offloading latencies and computational resource outages. Interestingly, our numerical simulations in the multi-cell scenario suggest that the choice of the appropriate caching policy can improve the performance of computation caching even more tellingly than small-cell federation and cooperation. This means that, in some implementation cases, optimizing the computation caching policy may be more effective than complexifying the network topology and the interaction among small cells. For the other cases, in our future work we will investigate the design of jointly optimal caching policies for small cells that do not fill their caches independently, taking into account all the cache indicators altogether. Iterative strategies to gradually reach a globally optimal configuration of the caches can be envisaged.

Finally, our results show that computation caching helps to reduce the amount of (uplink) radio communications and, when the caching policy is chosen accurately, of backhaul communications, because less inter-cell exchange of data is required. Therefore, computation caching turns out to be an overall interference reducing factor. We reserve to future
work a more detailed analysis and quantification of these
beneficial effects.

REFERENCES

[1] A. Abouaomar, A. Filali, and A. Kobbane, "Caching, device-to-device and fog computing in 5th cellular networks generation: Survey," in *Proc. WIN-COM*, Rabat, Morocco, 2017, pp. 1-6.

[2] S. Barbarossa, E. Ceci, M. Merluzzi, and E. C. Strinati, "Enabling effective mobile edge computing using millimeter wave links," in *Proc. IEEE ICC Workshops*, Paris, France, 2017, pp. 367-372.

[3] S. Barbarossa, S. Sardellitti, and P. D. Lorenzo, "Communicating while computing: Distributed mobile cloud computing over 5G heterogeneous networks," *IEEE Signal Process. Mag.*, vol. 31, no. 6, pp. 45-55, Nov. 2014.

[4] E. Bastug, M. Bennis, and M. Debbah, "Living on the edge: The role of proactive caching in 5G wireless networks," *IEEE Commun. Mag.*, vol. 52, no. 8, pp. 82-89, Aug. 2014.

[5] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, "Web caching and Zipf-like distributions: Evidence and implications," in *Proc. IEEE INFOCOM*, New York, NY, USA, Mar. 1999, vol. 1, pp. 126-134.

[6] E. C. Strinati, S. Barbarossa, J. L. Gonzalez-Jimenez, D. Ktenas, N. Cassiau, L. Maret, and C. Dehos, "6G: The next frontier: From holographic messaging to artificial intelligence using subterahertz and visible light communication," *IEEE Veh. Technol. Mag.*, vol. 14, no. 3, Sept. 2019.

[7] E. C. Strinati and J. Oueis, "Procédé et dispositifs associés de formation d'un nuage informatique stockant le résultat de l'exécution déportée d'une tâche informatique," French Patent 1 562 546 A, Dec. 16, 2015.

[8] N. di Pietro and E. C. Strinati, "Proactive computation caching policies for 5G-and-beyond mobile edge cloud networks," in *Proc. EUSIPCO*, Rome, Italy, 2018, pp. 792-796.

[9] E. Edi, D. Trystram, and J. M. Vincent, "A new cache approach based on graph for Web servers," in *Proc. ENC*, Colima, Mexico, 2004, pp. 1-6.

[10] M. S. Elbamby, M. Bennis, and W. Saad, "Proactive edge computing in latency-constrained fog networks," in *Proc. EuCNC*, Oulu, Finland, 2017, pp. 1-6.

[11] M. S. Elbamby, M. Bennis, W. Saad, M. Latva-Aho, and C. S. Hong, "Proactive edge computing in fog networks with latency and reliability guarantees," *EURASIP J. Wireless Commun. Netw.*, vol. 2018, no. 1, p. 209, Aug. 2018.

[12] M. S. Elbamby, C. Perfecto, M. Bennis, and K. Doppler, "Toward low-latency and ultra-reliable virtual reality," *IEEE Netw.*, vol. 32, no. 2, pp. 78-84, Mar./Apr. 2018.

[13] Y. Hao, M. Chen, L. Hu, M. S. Hossain, and A. Ghoneim, "Energy efficient task caching and offloading for mobile edge computing," *IEEE Access*, vol. 6, pp. 11365-11373, 2018.

[14] A. Ioannou and S. Weber, "A survey of caching policies and forwarding mechanisms in information-centric networking," *IEEE Commun. Surveys Tuts.*, vol. 18, no. 4, pp. 2847-2886, 4th Quart., 2016.

[15] Y. Jiang, M. Ma, M. Bennis, F. Zheng, and X. You, "A novel caching policy with content popularity prediction and user preference learning in fog-RAN," in *Proc. IEEE GC Workshops*, Singapore, Dec. 2017, pp. 1-6.

[16] H. Kellerer, U. Pferschy, and D. Pisinger, *Knapsack Problems*. Berlin, Germany: Springer-Verlag, 2004.

[17] S.-W. Ko, K. Huang, S.-L. Kim, and H. Chae, "Live prefetching for mobile computation offloading," *IEEE Trans. Wireless Commun.*, vol. 16, no. 5, pp. 3057-3071, May 2017.

[18] S.-W. Ko, K. Huang, S.-L. Kim, and H. Chae, "Energy efficient mobile computation offloading via online prefetching," in *Proc. IEEE ICC*, Paris, France, May 2017, pp. 1-6.

[19] M. Lauridsen, L. Noël, T. B. Sørensen, and P. Mogensen, "An empirical LTE smartphone power model with a view to energy efficiency evolution," *Int. Technol. J.*, vol. 18, no. 1, pp. 172-193, 2014.

[20] K. Lee, "Outatime: Using speculation to enable low-latency continuous interaction for mobile cloud gaming," in *Proc. MobiSys*, Florence, Italy, 2015, pp. 151-165.

[21] S. Li, J. Xu, M. van der Schaar, and W. Li, "Popularity-driven content caching," in *Proc. IEEE INFOCOM*, San Francisco, CA, USA, Apr. 2016, pp. 1-9.

[22] H. Liu, F. Eldarrat, H. Alqahtani, A. Reznik, X. de Foy, and Y. Zhang, "Mobile edge cloud system: Architectures, challenges, and approaches," *IEEE Syst. J.*, vol. 12, no. 3, pp. 2495-2508, Sep. 2018.

[23] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, "A survey on mobile edge computing: The communication perspective," *IEEE Commun. Surveys Tuts.*, vol. 19, no. 4, pp. 2322-2358, 4th Quart., 2017.

[24] N. M. Markovich and U. R. Krieger, "A caching policy driven by clusters of high popularity," in *Proc. IWCMC*, Paphos, Cyprus, 2016, pp. 363-368.

[25] MathWorks. MATLAB. Accessed: Dec. 18, 2019. [Online]. Available: https://www.mathworks.com/help/optim/ug/intlinprog.html

[26] A. Ndikumana, N. H. Tran, T. M. Ho, Z. Han, W. Saad, D. Niyato, and C. S. Hong, "Joint communication, computation, caching, and control in big data multi-access edge computing," *IEEE Trans. Mobile Comput.*, to be published.

[27] J. Oueis, "Joint communication and computation resources allocation for cloud-empowered future wireless networks," Ph.D. dissertation, CEA-Leti Lab. D'Informatique Grenoble, Univ. Grenoble Alpes, Grenoble, France, 2016.

[28] J. Oueis and E. C. Strinati, "Uplink traffic in future mobile networks: Pulling the alarm," in *Proc. EAI CROWNCOM*, Grenoble, France, 2016, pp. 583-593.

[29] J. Oueis and E. C. Strinati, "Computation caching for local cloud computing," presented at the IEEE WCNC, 5G TACNET Workshops, San Francisco, CA, USA, 2017.

[30] J. Oueis, E. C. Strinati, and S. Barbarossa, "The fog balancing: Load distribution for small cell cloud computing," in *Proc. IEEE VTC Spring, Glasgow, U.K.*, May 2015, pp. 1-6.

[31] J. Oueis, E. C. Strinati, S. Sardellitti, and S. Barbarossa, "Small cell clustering for efficient distributed fog computing: A multi-user case," in *Proc. IEEE VTC Fall*, Boston, MA, USA, Sep. 2015, pp. 1-5.

[32] J. Plachy, Z. Becvar, and E. C. Strinati, "Dynamic resource allocation exploiting mobility prediction in mobile edge computing," in *Proc. IEEE PIMRC*, Valencia, Spain, Sep. 2016, pp. 1-6.

[33] W. Pugh and T. Teitelbaum, "Incremental computation via function caching," in *Proc. ACM POPL*, Austin, TX, USA, 1989, pp. 315-328.

[34] S. E. Richardson, "Exploiting trivial and redundant computation," in *Proc. IEEE ARITH*, Windsor, ON, Canada, Jun./Jul. 1993, pp. 220-227.

[35] S. Sardellitti, G. Scutari, and S. Barbarossa, "Joint optimization of radio and computational resources for multicell mobile-edge computing," *IEEE Trans. Signal Inf. Process. Netw.*, vol. 1, no. 2, pp. 89-103, Jun. 2015.

[36] K. Suksomboon, "PopCache: Cache more or less based on content popularity for information-centric networking," in *Proc. IEEE LCN*, Sydney, NSW, Australia, Oct. 2013, pp. 236-243.

[37] C. Wang, C. Liang, F. R. Yu, Q. Chen, and L. Tang, "Computation offloading and resource allocation in wireless cellular networks with mobile edge computing," *IEEE Trans. Wireless Commun.*, vol. 16, no. 8, pp. 4924-4938, Aug. 2017.

[38] C. Wang, F. R. Yu, C. Liang, Q. Chen, and L. Tang, "Joint computation offloading and interference management in wireless cellular networks with mobile edge computing," *IEEE Trans. Veh. Technol.*, vol. 66, no. 8, pp. 7432-7445, Aug. 2017.

[39] S. Wang, X. Zhang, Y. Zhang, L. Wang, J. Yang, and W. Wang, "A survey on mobile edge networks: Convergence of computing, caching and communications," *IEEE Access*, vol. 5, pp. 6757-6779, 2017.

[40] A. Waterland, "Computational caches," in *Proc. ACM SYSTOR*, Haifa, Israel, 2013, pp. 1-7.

<figure><img src="image_20.png" /></figure>

NICOLA DI PIETRO received the B.S. degree in mathematics from the University of Padua, Italy, in 2008, the M.S. degree in mathematics jointly from the University of Padua and the University of Bordeaux, France, in 2010, within the framework of the international ALGANT program, and the Ph.D. degree in mathematics from the University of Bordeaux, in 2014.

During the years of his Ph.D. studies, he was a Research Engineer with the European R&D Center of Mitsubishi Electric, Rennes, France. From 2014 to 2016, he was an Associate Postdoctoral Fellow with Texas A&M University at Qatar. He is currently a Research Engineer with CEA-LETI, Grenoble, France. His research interests are coding theory, information theory, lattice error-correcting codes, caching, and edge computing for 5G networks.
<figure><img src="image_21.png" /></figure>

**EMILIO CALVANESE STRINATI** received the M.E. degree from the University of Rome “La Sapienza”, in 2001, and the Ph.D. degree in engineering science, in 2005, with the focus on radio link control for improving the QoS of wireless packet transmission.

He then started working with Motorola Labs, Paris, in 2002. In 2006, he joined CEA-LETI as a Research Engineer. Since 2007, he has been a Ph.D. Supervisor. From 2010 to 2012, he was the Co-Chair of the Wireless Working Group, GreenTouch Initiative, which deals with the design of future energy efficient communication networks. From 2011 to 2016, he was the Smart Devices & Telecommunications European collaborative strategic programs Director. In December 2013, he was elected as one of the five representatives of academia and research center in the Net!Works 5G PPP ETP. Since December 2016, he has also been the Smart

Devices & Telecommunications Scientific and Innovation Director. From 2016 to 2018, he was the Co-Ordinator of the H2020 joint Europe and South Korea 5GCHAMPION project. From 2017 to 2018, he was one of the three moderators of the 5G future network expert group. Since July 2018, he has also been the Coordinator of the H2020 joint Europe and South Korea 5GAllStar project. Since 2018, he has held the French Research Director Habilitation (HDR). He has published around 100 articles in international conferences, journals, and book chapters, given more than 70 international invited talks and keynotes and is the main inventor or co-inventor of more than 60 patents. He has organized more than 70 international conferences, workshops, panels and special sessions on green communications, heterogeneous networks and cloud computing, hosted in international conferences as the IEEE GLOBECOM, the IEEE PIMRC, the IEEE WCNC, the IEEE VTC, EuCnC, IFIP, EUCnC, and European Wireless.

...