# JCSP: Joint Caching and Service Placement for Edge Computing Systems
††thanks: The work of Yicheng Gao has been supported by a China Scholarship
Council-Imperial Scholarship.  ††thanks: 978-1-6654-6824-4/22/$31.00 ©2022
IEEE

Yicheng Gao, Giuliano Casale  Department of Computing, Imperial College
London, London, UK
Emails: {y.gao20<EMAIL_ADDRESS>
###### Abstract

With constrained resources, what, where, and how to cache at the edge is one
of the key challenges for edge computing systems. The cached items include not
only the application data contents but also the local caching of edge services
that handle incoming requests. However, current systems separate the contents
and services without considering the latency interplay of caching and
queueing. Therefore, in this paper, we propose a novel class of stochastic
models that enable the optimization of content caching and service placement
decisions jointly. We first explain how to apply layered queueing networks
(LQNs) models for edge service placement and show that combining this with
genetic algorithms provides higher accuracy in resource allocation than an
established baseline. Next, we extend LQNs with caching components to
establish a joint modeling method for content caching and service placement
(JCSP) and present analytical methods to analyze the resulting model. Finally,
we simulate real-world Azure traces to evaluate the JCSP method and find that
JCSP achieves up to 35% improvement in response time and 500MB reduction in
memory usage than baseline heuristics for edge caching resource allocation.

###### Index Terms:

Caching, service placement, queueing modeling, edge computing

##  I Introduction

Many types of smart applications for end users, such as virtual reality,
interactive gaming, and face recognition, have rapidly evolved over the past
decade [1]. Such compute-intensive applications are constantly expected to
fulfill high data rates and meet quality of service (QoS) requirements arising
from ever-increasing user demands. However, the efficiency and reliability of
these applications are both constrained by the terminal devices in terms of
storage, battery life, and computation capability [2]. Thus, to avoid high
latency when processing incoming tasks, computationally-demanding jobs are
typically offloaded to cloud data center back-ends for faster executions.

However, this approach is faced with the issue of high response time, as the
transmission distance from the end user to the data center can be significant
[3]. This is problematic for latency-sensitive applications, such as
autonomous driving and real-time video. In this context, a paradigm shift has
taken place naturally from centralized cloud computing toward distributed edge
computing [4]. Edge computing configures computation, storage, and bandwidth
resources at network edges, _e.g.,_ base stations and access points, close to
end subscribers. Through these means, edge computing offers a dramatic
reduction in latency.

In this paper, we focus on edge caching strategies, _i.e.,_ what, where, and
how to cache at the edge with limited resources to satisfy user demands, which
are one of the key enabling technologies of edge computing. Traditional caches
store copies of items, such as images, files, and scripts, at proxy servers or
servers close to end users [5]. Different from traditional caching, edge
caching stores items at proximal network edges, such as small cell base
stations (SBSs) and vehicles. Moreover, the cached items are no longer limited
to data contents but may also be seen as encompassing the decision of which
services are deployed for execution at a particular edge resource.
Specifically, content caching is proposed to tackle the issues of content
placement and delivery [6]. While service placement refers to the deployment
of services and their correlative databases at edge servers to execute tasks
offloaded from end users [7].

In existing studies, edge content caching specializes in data caching without
considering queueing contention at the services that are placed to process it.
In a similar manner, edge service placement typically overlooks the role
content caching plays in the service execution latency. To tackle both issues,
we propose a joint caching and queueing methodology consisting of a novel
class of models and a resulting resource allocation approach. The unique
feature of the models is the ability to stochastically model the latency
interplay of queueing for service access and cache hits/misses. To implement
this novel class of stochastic models, we generalize a class of models, called
layered queueing networks (LQNs) [8], which are used in the performance
engineering of layered service architectures. Our extension integrates for the
first time caching characteristics in these models, thus developing a novel
tool for stochastic scheduling in edge systems. In details, our main
contributions are as follows:

  * •

We first model the basic job scheduling and service placement processes
(ignoring caching) by LQNs. As applied to stochastic workloads, we find an
average gain of 16$\%$ for system response time in our experiments compared to
the deterministic scheduling method in [9]. This illustrates the benefit of
adapting an LQN formalism to deal with stochastic scheduling.

  * •

We generalize LQN models with caching components, which establishes a joint
modeling method for edge content caching and service placement (JCSP), and
present the analytical algorithm to analyze the generalized model numerically.

  * •

We simulate an advanced Queueing Petri Net (QPN) based model to validate the
accuracy of the proposed class of integrated LQN-caching models111The
validation datasets are available at https://doi.org/10.5281/zenodo.6491327
and implement the generalized LQN model within the LINE222The LINE tool is
available at http://line-solver.sourceforge.net/ tool [10].

  * •

Extensive simulations based on real-world Azure traces are conducted to
evaluate the applicability of our proposed JCSP method. Results show that the
JCSP method can find a better trade-off between system response time and
memory consumption under a wide range of situations than the baselines.

The paper is organized as follows. In Section II, we present related works and
state the limitations. The methodology is developed in Section III. We design
the generalized model containing caching and present the analytical methods in
Section IV. The model validation and experimental evaluation are given in
Section V. Finally, Section VI concludes the paper.

##  II Related Work

Current research has investigated edge caching from two perspectives, _i.e.,_
content caching and service placement, as shown in Table I. The basic issue
for edge content caching is optimizing what to cache and how, based on the
architectural features of the edge computing system under study. With respect
to what to cache, most studies center on the characteristics of content
popularity profile, which can be grouped into known [11], unknown but static
[12], and unknown and time-varying [13, 14]. With regard to how to cache
instead, policies differ in the setting of network topologies. When employing
traditional two-tier hierarchical networks, the key issue is to make a trade-
off between the edge node and the centralized node under certain resource
constraints [15]. When adopting the user-centric structures, how to
collaborate within a cluster of edge nodes, such as SBSs or vehicles, is
crucial [16, 17]. The aforementioned studies on caching contents at edge nodes
ignore the services that are placed to process such contents.

TABLE I: Comparison of related works with different parameters

Ref. | Objective items |  Replacement policies | Job scheduling |  Job precedences
---|---|---|---|---
|  content |  service |  |  deterministic |  stochastic |
[11, 12, 13, 14] |  $\surd$ |  |  |  |  |
[15],[17] |  $\surd$ |  |  $\surd$ |  |  |
[18, 19, 20] |  |  $\surd$ |  |  |  |
[21] |  |  $\surd$ |  |  $\surd$ |  |
[22, 23] |  |  $\surd$ |  |  |  $\surd$ |
[24, 9] |  |  $\surd$ |  |  $\surd$ |  |  $\surd$
JCSP |  $\surd$ |  $\surd$ |  $\surd$ |  |  $\surd$ |  $\surd$

For edge service placement, existing studies center on optimizing the system
performance [18, 19, 20] , _e.g.,_ response time, energy efficiency, or cost,
due to the constrained edge resources. Further, many studies jointly optimize
service placement with job scheduling processes [21, 22, 23]. The two
procedures are interactive, as the placed services determine how to schedule
the jobs and the scheduling strategy impacts the performance of the placement
policy. To jointly model the two procedures, most techniques take advantage of
queueing theory, such as $M/G/1$[22] and $M/M/1$[23]. However, these models
typically do not reflect the precedences between jobs. If considering the
precedence constraints, most approaches adopt directed acyclic graphs (DAG)
[24, 9], the optimal scheduling of which is typically NP-hard except with
specific graph topologies (_e.g.,_ in-trees, out-trees).

Figure 1: A use case of video content delivery chain

In the above-mentioned research, there are two primary limitations. First, for
edge service placement, DAGs are efficient to model the jobs with precedences.
However, a DAG fails to illustrate the dependencies of underlying resources
invoked by jobs, because it does not encompass scheduling strategies and
resource contention. Therefore, we propose to jointly model the dependent job
scheduling and service placement processes by LQNs. LQNs have been extensively
used to model distributed computing systems with complex characteristics, such
as fork/join interactions and multiple tiers of services [26]. An LQN
distributes software and hardware resources into multiple layers, according to
their functionality and request types. When there are requests need to possess
simultaneous resources [8], LQNs can explicitly represent the dependencies by
describing the interaction between clients and servers in each layer. Each
layer is then automatically translated into a Markovian queueing network
model, which is analyzed in isolation, prior to aggregating the results to
produce end-to-end latency estimates. Thus, if applying LQNs to layered edge
computing systems, each edge node can either act as a client or as a server to
request or provide services, which makes it easy to model and trace nested
dependencies.

Next, the edge content caching and service placement processes are studied
separately. However, in practice, the processing of many applications requires
both computation and data. For example, in video analytics [25], the request
is first forwarded to the content caching function to retrieve the cached
contents. After the identification, the request is routed to video compression
and video analytics services for further processing, as shown in Fig. 1.
Therefore, we propose to establish a unified resource allocation approach for
both contents and services. As we define caching and LQNs to model processing
for contents and services respectively, the key challenge is how to establish
and analyze integrated caching and queueing network models.

##  III Methodology

###  III-A System Model

We consider a cluster of $M$ edge nodes connecting $N$ users in the edge
computing system, as shown in Fig. 2. Each edge node provides multiple
services in edge servers co-located with the SBSs. Each user offloads several
jobs to the connected edge node to be served. The offloaded jobs may have
precedences that must be processed in order. For example, a face recognition
application [27] can be regarded as consisting of five successive jobs,
_i.e.,_ object acquisition, face detection, pre-processing, feature
extraction, and classification. Each job can be operated solely at the edge
node that provides corresponding services. When the requested services are not
provided in the connected edge node, the jobs need to be forwarded to other
edge nodes that satisfy the requirements. Furthermore, different types of jobs
at the same node also obey the sequential processing.

We assume the total number of jobs is $K$, which request a total number of $C$
possible services. For job $k$ at node $m$, $k=1,2,...,K,m=1,2,...,M$, we
define two parameters as follows:

  * •

_Service Placement Decision_ $p_{mk}$. If node $m$ provisions the service
requested by job $k$, $p_{mk}=1$. Otherwise, $p_{mk}=0$. The set of all nodes
that provision the service for job $k$ is denoted as
$\bm{F}_{k}=\left\\{m|p_{mk}=1,m=1,2,...,M\right\\}$.

  * •

_Mean service time_ $t_{mk}$. This is the amount of computational processing
requested by job $k$ upon visiting node $m$. Different jobs may request
different mean service time.

Figure 2: Edge computing system model containing $N$ users

We then use an LQN to model the job scheduling and service placement problem,
as presented in Fig. 3. Each edge node $m$ is composed of 4 components as
follows:

  * •

_Processor_ : The SBS is modeled as a processor $P_{m}$, shown as a circle. It
obeys the processor-sharing scheduling policy, which is a mathematical
abstraction of time-sharing scheduling with an infinitesimally small quantum
of time.

  * •

_Task_ : The co-located edge server is modeled as a set of tasks $T_{mc}$,
shown as the larger parallelograms, each of which represents service $c$
running on processor $P_{m}$. Each task has a queue to model first-come first-
served (FCFS) admission control and the service time follows a phase-type
distribution, _e.g.,_ exponential, Erlang, or hyper-exponential.

  * •

_Entry_ : Each task publishes at least one entry $E_{mcj},1\leq j\leq J$,
shown as a small parallelogram, which represents the end point for calls to
service $c$. In general, a service with $k$ possible endpoints is modeled as a
task with $k$ entries.

  * •

_Activity_ : Each entry invokes a sequence of activities $A_{mci}$, where
$i=1,\ldots,I_{c}$ and $I_{c}$ is the number of activities for service c.
Activities are shown as a series of rectangles under the entries, to represent
independent or dependent executions. That is, upon invoking an entry
$E_{mcj}$, it will lead to a chain of individual activities being carried out
on the underpinning processor. In LQNs, such activities can be organized in
form of a DAG called the activity graph and detailed later. Note that each
activity may be reached by calling different entries.

The clients are modeled in the LQN formalism as _reference tasks_ running on a
_pseudo-processor_ $P_{0}$. A pseudo-processor is a modeling abstraction
similar to a processor but without a physical reality in the edge system and
used to keep a conceptually similar description of all tasks in the model. The
pseudo-processor in LQNs is also suitable to describe user think times. Each
client has different probabilities of requesting different workflows. The user
workflows are also DAGs to represent the precedence between the jobs and
modeled as special activity graphs within the pseudo-processor $P_{w}$. The
mean queue length of the infinite server on $P_{w}$ is defined as the
multiplicity of the workflow. If dependent jobs are executed at different
nodes, the activity graph will feature special activities that issue
synchronous calls to different nodes, such as $A_{w-2-1}$ and $A_{w-2-2}$.
Therefore, DAGs are present both in the reference processor to describe user
workflows and bound to entries of the services to describe the activities
launched by each entry. The latter is also in general DAGs that may include
synchronous or asynchronous calls to other tasks and entries.

Figure 3: LQN-based model for job scheduling and service placement processes

###  III-B Problem Formulation

The LQN models we have described above allow to obtain analytical estimates of
throughputs, response times (_i.e.,_ latency per unit invocation), mean queue-
lengths (_i.e.,_ backlogs), and utilizations for each component type. We focus
on response time throughout the rest of the paper, but other reference metrics
may be easily generated from the models. Our optimization objective is to
minimize the end-to-end total response time $R$ of the LQN-based model, which
is expressed as

$R=\sum_{i=1}^{C}{\frac{X_{i}}{X}}{R_{i}},$ (1)

where ${X_{i}}$, ${{R_{i}}}$, and ${X}$ are the throughput of job class $i$,
the response time of job class $i$, and the total throughput summed over all
service classes, respectively. The ratio $X_{i}/X$ may be seen as related to
the probability at steady-state where an arrival is of class $i$. Thus, the
problem of dependent job scheduling and service placement is formulated as

$\begin{split}\min_{\bm{x}}\quad\quad&R(\bm{x}),\\\
\emph{s.t.}\quad\quad&\sum\limits_{m\in\bm{F}_{k}}x_{mk}=1,\\\
&x_{mk}\in\\{0,1\\},\end{split}$ (2)

where $x_{mk}$ denotes the scheduling decision for job $k$ at node $m$. The
vector $\bm{x}=[x_{11},...,x_{mk},...,x_{MK}]$ represents the set of
scheduling decisions for all jobs and $R(\bm{x})$ is the corresponding system
response time with decision vector $\bm{x}$. The first constraint guarantees
that job $k$ is solely served at one (and only one) feasible edge node
provisioning the requested services. The second constraint ensures that if job
$k$ is scheduled to be served at node $m$, then $x_{mk}=1$, or $x_{mk}=0$
otherwise.

##  IV Generalized LQN Model Design

###  IV-A New Design Formalism

To extend LQN models to include caching components, we first define two novel
components as follows:

  * •

_cache-task_ : Each caching node is defined as a cache-task in the LQN model.
Each cache-task offers the ability to access a collection of items through a
cache, such as a key-value store. Cache-tasks have the basic properties of
tasks, but add four specific properties for caching: the total number of
items, the cache capacity, the cache partitioning into lists, and the cache
replacement policy, _e.g.,_ least recently used (LRU), least frequently used
(LFU), first-in first-out (FIFO), and random replacement (RR).

  * •

_item-entry_ : The services provided by the caching module are defined as
item-entries in the LQN model. Each item-entry represents a collection of
items accessible through the cache-task. Item-entries are similar to standard
entries, but add the property of the popularity of the items, _e.g.,_ Zipf or
custom distribution.

Upon issuing a call to an item-entry exposed by a cache-task, a client obtains
the requested object either after a cache hit or a cache miss. The hit/miss
selection depends on the cached contents and reflects as a choice of a
different branch in the DAG bound to the item-entry. This is modeled through a
novel precedence relationship, _i.e.,_ an activity graph edge. We name this
precedence relationship as _cache-access_ for the cache hit and miss
activities under each item-entry, which can be used to specify the branching
in the activity graph. The _cache-access_ transforms an incoming job into a
hit or miss job, sending out the transformed job to the corresponding outgoing
link with a certain probability.

The cache replacement policy of each cache-task adopts by default the RR
policy, which randomly selects a candidate item to replace when a cache miss
occurs. The RR policy can offer the same steady-state performance of the time-
to-live (TTL) mechanism [28] with exponential timers. Hence it is a reasonable
approximation of the real-world TTL with better analytical tractability. Other
policies, such as LRU or CLIMB, can be obtained as simple extensions of our
basic framework.

Figure 4: An example of a LQN model containing one cache-task

Based on such extensions, we generalize the LQN model by enabling caching.
Fig. 4 presents an example of an LQN model containing one cache-task. The top-
right symbol in the task parallelogram distinguishes a cache-task from an
ordinary task. When an item request arrives, we model the probability that the
item is in the cache with $p_{hit}$ and out of cache with
$p_{miss}=1-p_{hit}$. The generated architecture allows joint modeling of
caching and queueing into the same LQN model. It is important to note that
$p_{hit}$ and $p_{miss}$ need not be specified by the end user. They are
automatically determined through the solution of the stochastic models
underpinning the LQNs with caching, which also relies on a stochastic
equilibrium analysis of the cache replacement policy, as we describe in the
next section.

###  IV-B Analysis of LQN Models with Caching

To solve the LQN model containing caching modules, the first step is to
decompose the entire model into a group of sub-models. Each sub-model may be
seen as a mixed queueing network that contains clients and servers. The term
mixed refers to the simultaneous presence of open and closed service classes.
The former represent asynchronous requests from clients, while the latter
represent synchronous ones (_i.e.,_ closed since issued from a finite
connection pool). In particular, when a queueing network contains the cache
module, the workload is synchronous, which means the issue of the next request
to the cache is required to take place after the reply of the last request
issued to the cache. To model this dynamics, we additionally divide the
caching sub-model into two sub-models, as shown in Fig. 5. In the upper sub-
model, the cache module is isolated in an open queueing network with
asynchronous Poisson streams. While in the lower sub-model, the delay and the
queueing station are contained in a closed queueing network.

Figure 5: Decomposition of the caching sub-model in the LQN model

To solve the caching sub-model, we generalize the analytical method for non-
layered queueing networks from [29] to the multi-layer setting of LQNs. The
expressions we give for the method focus for simplicity on a single class of
jobs, but our implementation applies similar formulas developed in [29] for
the multi-class case.

Cache requests arrive in the upper sub-model as a single-class Poisson stream
with rate $\lambda=\sum_{r}\lambda_{r}$. With an initial guess of the arrival
rate $\lambda$, the hit and miss rates of the cache node, _i.e.,_
$p_{miss}^{(t)}$ and $p_{hit}^{(t)}$, are approximated iteratively via a
fixed-point iteration (FPI) scheme. The obtained values in each iteration are
leveraged in [29] to calculate the next arrival rate $\lambda^{(t+1)}$ by the
following application of Little’s law:

$\lambda^{(t+1)}=\frac{s\lambda^{(t)}}{\lambda^{(t)}\theta_{t}+p_{miss}^{(t)}\theta_{m}+p_{hit}^{(t)}\theta_{h}},$
(3)

where $\theta_{t},\theta_{m},\theta_{h}$ are the mean think time, and the mean
delay to due miss and item fetch respectively. Here, $s$ is the maximum number
of pending requests to the cache, _i.e.,_ the total population of jobs in the
caching sub-model. The iteration process continues until the value of
$\lambda$ converges.

The hit and miss rates at each iteration are used to parameterize the queueing
network of the _lower_ sub-model as routing probabilities. That is, jobs
representing calls that experience cache hits will dynamically switch after
visiting the cache to a hit service class, which will be processed by the
queueing station according to the activities specified in the activity graph
for hits. Similarly, calls that experience misses will switch to a miss
service class representing the workflow in the activity graph for misses. This
class-switching based separation of the hit and miss calls enables the
modeling of the different response times experienced by the two classes of
requests, which depend on whether the items they accessed were cached or not.
At the end of the chain of operations that follow hit/miss, both classes of
jobs will be merged back into the original class and return to the user as a
response for that class.

The solution to the upper sub-model is reconciled with the lower sub-model
iteratively by means of the following scheme:

  * •

Guess $\lambda^{0}$ with a random value.

  * •

Solve the upper sub-model with approximation methods, _e.g.,_ FPI, to obtain
the hit and miss probabilities, _i.e.,_ $p_{hit}$ and $p_{miss}$.

  * •

Pass $p_{hit}$ and $p_{miss}$ to the lower sub-model to set the routing
matrix.

  * •

Solve the lower sub-model with a queueing network solver method $f(s)$,
_e.g.,_ approximate mean value analysis (AMVA) [30], to obtain the mean
throughput $X$.

  * •

Pass $X$ to the upper sub-model as the next arrival rate $\lambda^{n}$.

  * •

Update until $||\lambda^{n+1}-\lambda^{n}||<\delta$.

We have never observed situations where the above iteration fails to converge.
Based on this solution to the caching sub-model, the entire procedure to solve
the LQN model containing cache-tasks is presented in Algorithm 1, where
$f(\cdot)$ is the customized solver for the sub-model $s$ that returns
throughputs, queue-lengths, response times, and utilizations.

Algorithm 1 Solution algorithm for LQNs with caching

Input: LQN model with cache-tasks, Sub-model solution algorithm $f(\cdot)$

1: Decompose $S$ sub-models based on layers

2: while not converged or not reached iteration limit do

3: for $s\leftarrow 1$ to $S$ do

4: if $s\leftrightarrow$ caching sub-model then

5: Decompose sub-model $s$ into two sub-models.

6: Initialize $\lambda$ in the upper sub-model.

7: while $||\lambda^{n+1}-\lambda^{n}||\geq\delta$ do

8: Solve the upper sub-model with (3) for $\lambda$.

9: Obtain $p_{hit}$ and $p_{miss}$ using the FPI method.

10: Pass $p_{hit}$ and $p_{miss}$ to the lower sub-model.

11: Solve the lower sub-model with AMVA.

12: Return the throughput $X$ to the upper sub-model as the next arrival rate
$\lambda^{n}$.

13: end while

14: else

15: Solve sub-model $s$ by $f(s)$.

16: Set waiting time for sub-model $s$.

17: Set think time for sub-model $(s+1)$.

18: end if

19: end for

20: end while

Output: layer response times, residence times, throughputs, and utilizations.

###  IV-C Cache parameters and Markov process

The caching model mentioned above for analyzing cache hit and miss
probabilities applies list-based caches [29, 31]. The list-based cache
consists of $h$ lists formed in a tree topology, each of which has a capacity
of $m_{l}$ items, $l=1,2,...,h$. The total cache capacity is
$m=\sum_{l=1}^{h}m_{l}$, which does not exceed the total number of items $n$.
The items that are not cached are arranged in a virtual list with $l=0$, with
a capacity of $m_{0}=n-m$. The request rate $\lambda_{vk}(l)\geq 0$ issued by
stream $v$ for item $k$ in list $l$ follows a Poisson arrival process, where
$v=1,2,...,u$, $k=1,2,...,n$.

Each list can only have one parent list $p(l)$ to exchange the items,
satisfying $p(p(\cdot\cdot\cdot p(l)\cdot\cdot\cdot))=0$, but has no
constraint to the number of children lists. Lists without children are known
as leaf lists. The probability of item $k$ shifting from current list $l$ to
the list $j$ after a cache hit is non-uniform and defined as the access
probability $c_{vk}(l,j)$. The analytical model for such list-based caches is
based on a Markov process. In each list, the state vector
$\bm{s}=[s(i,j)]\in[1,n]$ represents the item cached in position $i$ of list
$j$. The applied replacement policies are modeled as a continuous-time Markov
chain (CTMC) with an equilibrium probability $\pi(\bm{s})$. The product-form
solution to $\pi(\bm{s})$ is presented as

$\pi(\bm{s})=\frac{\prod\limits_{j=0}^{h}\prod\limits_{i=1}^{m_{j}}\gamma_{s(i,j)j}}{E(\bm{m})},$
(4)

where ${E(\bm{m})}$ is the normalizing constant and $\gamma_{ij}$ denotes the
access factor of item $i$ to access list $j$, satisfying

$\gamma_{ij}=\gamma_{ip(j)}\sum\limits_{v=1}^{u}\lambda_{vi}(p(j))c_{vi}(p(j),j).$
(5)

The performance measure for the Markovian analytical model is defined based on
the marginal probability of item $k$ in list $j$ as

$\pi_{kl}(\bm{m})=m_{l}\gamma_{kl}\frac{E_{k}(\bm{m}-1_{l})}{E(\bm{m})}.$ (6)

$\pi_{k0}(\bm{m})$ represents the miss ratio for item $k$, satisfying
$\pi_{k0}(\bm{m})=E_{k}(\bm{m})/E(\bm{m})$, in which $E_{k}(\bm{m})$ is the
normalizing constant when item $k$ is not in the model. From the marginal
probabilities, the miss rate for requesting item $k$ from stream $v$ can be
denoted as $M_{vk}(\bm{m})=\lambda_{vk}(0)\pi_{k0}(\bm{m})(1-c_{vk}(0,0))$.
Thus, the total cache miss rate is $M(\bm{m})=\sum_{v,k}M_{vk}(\bm{m})$.
Throughout, we focus on single-list caches, _i.e.,_ $h=1$, as they are more
widespread, but our implementation also supports $h>1$ through the formulas
above.

##  V Experimental Evaluation

In this section, we first evaluate the merits of utilizing LQNs to model the
job scheduling and service placement problem. Then we simulate a QPN-based
model with Java Modeling Tools (JMT) [32] to validate the accuracy of the
generalized LQN model. Finally, we conduct extensive simulations of real-world
Azure traces to measure the performance of the generalized LQN model.

###  V-A Evaluation of LQNs for Edge Service Placement

We begin by comparing our proposed scheme with the method in [9], which
formulates an offloading dependent tasks with service caching (ODT-SC)
problem. The ODT-SC problem considers deterministic scheduling with
deterministic service time, while our scheme focuses on stochastic scheduling
with random service time. Moreover, the optimization goal of the ODT-SC
problem is to minimize the maximum makespan, _i.e.,_ the sum of the start time
of a job and its execution time, while our goal is to minimize the total
response time. Despite the differences in the assumptions, we regard this
baseline as a suitable comparison to just the benefits of stochastic LQN-based
modeling of complex edge workflows.

For comparison, we set the mean service time for each job in our LQN-based
model equal to the execution time in [9]. The optimization goal of the ODT-SC
problem is reset to minimize the total completion time, which is the sum of
the makespan of each job. Moreover, the method in [9] reformulates the ODT-SC
problem into a convex programming to get feasible solutions. To be more
general, we solve the ODT-SC problem by genetic algorithm (GA) without the
need to relax the constraints. An overview of the comparative procedure of the
two schemes is presented in Fig. 6.

Figure 6: An overview of the comparative procedure between the LQN-based model
and the method in [9]

We first leverage the GA to address the ODT-SC issue, obtaining the optimal
scheduling strategy $\bm{x^{\prime}}$of each job. Then the strategy is
transformed into an LQN model to calculate the total response time
$R(\bm{x^{\prime}})$. The response time corresponding to the minimum
completion time in each iteration is selected as the comparative object.
Meanwhile, we equally exploit the GA to solve the proposed LQN-based model to
search for the minimum total response time. Finally, we compare the two
response times to observe the average gain $g$ of the proposed method, which
is expressed as

$g=\frac{1}{I}\sum_{i=1}^{I}\frac{\parallel
R_{i}(\bm{x^{\prime}})-{{R_{i}(\bm{x})}}\parallel}{{R_{i}(\bm{x^{\prime}})}},$
(7)

where $I$ is the total iterations.

In each iteration $i=1,\ldots,I$, to reduce the estimation error, we run $Q$
replications of the GA solver to search for the optimal solutions. In each
replication of the GA solver, the number of generations is denoted by $G$. The
dimension of the design variable for the ODT-SC problem is $2K$, of which the
first and second $K$ elements are the start times and scheduling decisions of
each job respectively. The service time is deterministic but varying in
different kinds of services. While for the LQN-based model, the dimension of
the design variable is the $K$ scheduling decisions of each job. The service
time of each job class is set to be exponentially distributed or hyper-
exponentially distributed, of which the mean value is equal to the one in the
ODT-SC problem.

A set of experiments are conducted to analyze the performance under different
conditions. The setting of different parameters are shown in Table II. The
distribution of service time is assumed as exponential or hyper-exponential.
For simplicity, the user workflow adopts chain structures for multiple
services in the experiments, but it is easily extended to cases with parallel
structures by LQNs.

TABLE II: Parameter settings for the comparative experiments Definition | Parameter | Range of Value
---|---|---
number of edge nodes | $M$ | $2,5$
number of users | $N$ | $8,20$
number of services | $C$ | $3,9,15$
number of iterations / replications |  $I$ / $Q$ | $30$
number of generations | $G$ | $1000$

(a) Exponential Service Time (b) Hyper-exponential Service Time

Figure 7: Average gain of response time of the LQN-based model compared to the
method in [9] ($M=2$)

(a) Exponential Service Time (b) Hyper-exponential Service Time

Figure 8: Average gain of response time of the LQN-based model compared to the
method in [9] ($M=5$)

The experimental results are presented in Fig. 7 and 8, which can be seen that
using LQN models yields a better average performance than the method in [9].
When $M=2$, the gain of total response time is a minimum of 7%, an average of
12%, and a maximum of 17%. When $M=5$, the gain of total response time is a
minimum of 7%, an average of 16%, and a maximum of 28%. As a whole, the
average gain improves with the increase of the number of edge nodes. Our
results show that it is beneficial to apply LQNs to stochastic scheduling as
opposed to heuristically apply a deterministic scheduling, _i.e.,_ the
solution to the ODT-SC problem. Therefore, it is meaningful to use the LQN
model for further performance analysis of edge caching systems.

###  V-B Generalized LQN Model Validation

We validate the generalized LQN model by JMT, which supports the simulation of
queueing networks and Petri nets with a graphical user interface. Petri nets
allow us to model the replacement policies in caches as synchronized
transitions that alter the cache slots. Thus, by simulating a QPN-based model,
we can get an accurate estimate of the expected performance of an LQN with
caching, against which we compare our FPI-based implementation described in
Algorithm 1.

We consider a validation model containing the upper two layers of the model
shown in Fig. 4. In the upper layer, the underlying processor $P_{1}$ adopts
the processor sharing strategy and the number of users is represented by the
multiplicity of the reference task $RT_{1}$. In the lower layer, the capacity
of the cache-task is set as 1 with a total number of 3 items. All the items
obey discrete uniform distribution and take the RR strategy. The underlying
processor $P_{c}$ also employs the processor sharing strategy and the number
of tokens in this layer is denoted by the multiplicity of the cache-task.

The validation model is transformed into a joint framework of queueing
networks and Petri nets in JMT, as presented in Fig. 9. The jobs first
originate from the delay node and are stored at the place of _upperlayer_.
Then, utilizing Petri net transition, _i.e._ , waiting for the tokens to be
available in the inbound places and firing a given number of tokens in the
output, we enable the transition 2 by 1 job from the upper layer and 1 token,
to fire 1 job into the lower layer. To determine a cache hit or miss in the
lower layer, we regard the cached items as different job classes. Thus, the
fired job class can switch into any of the items at the _ClassSwitch 1_ node
according to the probability distribution. Based on the state of the stored
items in _Cache_ and _OutOfCache_ places, the transition 1 determines whether
to fire a hit or miss job class into the queue. After different services for
the hit or miss job at the queue node, the job transforms back to the original
job class at the _ClassSwitch 2_ node and enables the transition 3. Finally,
the transition 3 fires 1 job to the place of _Access Tokens_ and 1 job to the
delay node to execute iteratively.

Figure 9: A queueing Petri net used for validation via JMT

We simulate the QPN-based model with JMT to validate the analytical model. The
performance metric we select is the residence time, which includes the visit
ratio compared to the response time. The results indicate the differences
between the analytical and simulated model under different combinations of
numbers of users and tokens, as shown in Fig. 10. It shows that the
differences are negligible in all cases, which proves the high accuracy of the
generalized LQN model.

Figure 10: Comparison of residence time between analytical and simulated
methods

###  V-C Evaluation of the JCSP Method

To evaluate the JCSP method to real workloads, we perform a trace-driven
simulation to demonstrate the system applicability in principle to production
systems. The trace is collected from a subset of applications running on Azure
Functions in 2019 [33]. We focus on a random subset of the trace, which
contains 34385 application ids and the corresponding serverless function ids
belonging to the same application. The invocation rate and the distribution of
execution time for each function as well as the distribution of memory usage
for each application are also given in the trace.

Fig. 11(a) shows the cumulative distribution of the minimum, average, and
maximum execution time for all functions. We can see that 50% of the functions
have average and maximum execution time less than $0.7s$ and $3s$. 90% of the
functions execute at most $50s$ and 95% of the functions take less than $50s$
on average. Fig. 11(b) presents the cumulative distribution of the 1st
percentile, average, and maximum virtual memory reserved for all applications.
Each application calls for one or more functions. We can observe that 99% of
the applications consume no more than 400MB on average and 99% of the
applications are allocated at most 1000MB.

(a) CDF of Execution Time (b) CDF of Allocated Memory

Figure 11: Properties of the selected subset of the real-world Azure traces

To simulate the trace-driven data, we implement the LQN with caching by LINE
[10] to facilitate the JCSP method. An example of the generalized LQN model
generated by LINE is shown in Fig. 12. The dark hexagram, pink triangle, red
square, and yellow triangle represent the processor, task, entry, and
reference task, respectively. Edges represent client-server relationships.
Dots whose name contain _C_ and _cloud_ belong to the cache and the origin
server. Indexes _h_ and _m_ refer to cache hit and cache miss. The index _i-j_
for the non-reference dots denotes service _j_ on node _i_.

The parameter settings that consider the characteristics of caching are
presented in Table III. The cache capacity $m$ for each node is configured
according to a standard Redis caching package offered by Microsoft Azure [34].
Corresponding cached items obey the Zipf distribution with parameter $\eta$
and are assumed of identical size, the total size $n$ of which is proportional
to the node cache capacity. These cache-related parameters shown in Table III
are chosen as in earlier works [31, 29]. Compared to Table II, the number of
edge nodes $d$ and number of services $s$ scales up to 16 and 40 respectively.
The distribution of service time is assumed as exponential with a mean value
same to the average execution time collected from the Azure trace. The number
of users is configured considering the capacity of SBSs [35]. For each user,
the probability to request for a certain service is determined by the
invocation rate of the service.

Figure 12:  An example of the generalized LQN model generated by LINE  TABLE III: Parameter settings for the JCSP method evaluation Definition | Parameter | Range of Value
---|---|---
number of edge nodes | $M$ | $2,4,8,16$
number of users | $N$ | $5,15,25$
number of services | $C$ | $10,20,40$
node cache capacity (MB) | $q$ | $250,750,1024$
average total size of items (GB) | $p$ | $0.5,1,2,4,8$
Zipf parameter | $\eta$ | $0.6,1.0,1.4$

For each combination of the parameters, we generate 30 models with different
random seeds. In each model, different services on each node are added with
cache-tasks that specify the size of total items and the allocated cache
capacity for each service. The sum of service capacities is equal to the node
cache capacity, which guarantees the maximum utilization of the constrained
storage for each edge node. We employ the total system response time as the
performance measure and compare our JCSP method to the case of _no cache_ and
_prefetch all_. The _no cache_ scheme deploys no caching module that all the
jobs need to wait for the requested contents from origin servers before being
processed locally. While the _prefetch all_ scheme indicates each edge node
caches all the items with a full utilization of the local memory.

From Fig. 13 (a) and (b), we can see that the total response time increases
with the growth of the number of users under same conditions, which attributes
to the cumulative queueing time. With same number of users, _no cache_ scheme
as the baseline exhibits the highest response time, because jobs need to
obtain required contents from the origin server. Conversely, _prefetch all_
scheme exhibits the lowest response time but ignoring the large memory
consumption. Compared to the _prefetch all_ scheme, although our proposed JCSP
method shows an increase of the response time at most 35% and 30%, but reduces
the memory usage by 500MB and 250MB respectively. This is because our proposed
system optimizes the allocation of the cache capacity for each service based
on the job scheduling and service placement strategies on different edge
nodes, which achieves to maximize the utilization of limited edge resources.
Overall, the total response time declines significantly when the number of
nodes rises, which is benefit from more concurrent servers that bring down the
waiting time.

(a) $M=2,C/M=5,\eta=1$ (b) $M=4,C/M=5,\eta=1$

Figure 13: Total response time with respect to the increase of the number of
users $N$ (Azure dataset)

From Fig. 14 (a) and (b), we can see that the total response time decreases
with the growth of the number of services, but tends to be stable after $C$
reaches 20. The decreasing trend in the first stage is the case when the
number of services is less than the number of users. Under the circumstances,
the possibility of users to request for the same service is higher, which
results in the longer queueing time for the same server. As the number of
services grows to equal to or larger than the number of users, the possibility
of calling the same service reduces, thus leading to the flat trend in the
later stages. With same number of services, our proposed JCSP method only sees
an increase of the response time at most 24% and 14%, but with a less memory
usage of 500MB and 250MB compared to the _prefetch all_ scheme.

(a) $M=4,N=25,\eta=1.4$ (b) $M=8,N=25,\eta=1.4$

Figure 14: Total response time with respect to the increase of the number of
services $C$ (Azure dataset)

Further, we analyze the sensitivity to $p/q$ and $C/M$ ratio on these
experiments. We focus on the miss ratio and define the performance metric as

$\epsilon^{\pi}_{mape}=\frac{1}{Q}\frac{1}{M}\frac{1}{C}\sum_{k=1}^{Q}\sum_{j=1}^{M}\sum_{i=1}^{C}\left|1-\frac{\hat{\pi}_{i,j}}{\pi_{i,j}}\right|,$
(8)

where $\hat{\pi}_{i,j}$ is the estimated miss ratio for service $i$ at node
$j$. The services that are not requested by users on each node are not
included. From Fig. 15 (a), we can see that the average percentage error
$\epsilon^{\pi}_{mape}$ for $p/q$ ratio approximately ranges between $0.1$ and
$0.2$. When the node cache capacity is high, the error metric decreases with
the size of total items increases. From Fig. 15 (b), we can observe that the
average percentage error $\epsilon^{\pi}_{mape}$ for $C/M$ ratio approximately
ranges between $0.05$ and $0.15$.

(a) $M=8,N=25,C=40$ (b) $N=25,p=0.5,q=250$

Figure 15: Sensitivity to $p/q$ and $C/M$ ratio with $\eta=1$ (Azure dataset)

###  V-D Summary of Experimental Results

Overall, with the increase of the number of users, the JCSP method indicates
an increase of the response time at most 35% and 30%, but reduces the memory
usage by 500MB and 250MB, compared to the _prefetch all_ scheme. With the
increase of the number of services, the JCSP method shows an increase of the
response time at most 24% and 14%, but a less memory usage of 500MB and 250MB,
compared to the _prefetch all_ scheme. This proves our proposed JCSP method is
better than simpler heuristics for edge caching resource allocation.

Concerning time and space requirements for the execution of the JCSP method,
the above experiments are conducted on an AMD EPYC 7302P 16-Core Processor.
For each replication, the estimate of memory usage and execution time are no
more than 4.45MB and $0.2s$, which reflects our proposed JCSP method is
scalable for multiple workloads.

##  VI Conclusions and Future Work

In this paper, we present a novel method to jointly analyze edge content
caching and service placement. We have first jointly modeled the job
scheduling and service placement processes with LQNs. The LQN-based model is
compared to the method in [9] and shows an average gain of 16% with respect to
the response time. Then we have extended the LQN model with caching components
to facilitate the JCSP method. An analytical model is given to analyze the
generalized LQN model numerically. We further have validated the generalized
LQN model by a QPN-based model with JMT and have implemented the proposed
class of integrated caching-queueing models within the LINE tool. Finally, we
have conducted extensive trace-driven simulations to evaluate the performance
of our proposed JCSP method for a real-world dataset, which show a better
trade-off between the response time and memory consumption.

Future work may extend the validation to general phase-type distributions or
those involving burstiness (_e.g.,_ Markovian arrival processes). Although our
implementation supports them, the JCSP method could be further used to
understand the impact of splitting a cache into lists on end-to-end edge
workflow latency.

## References

  * [1] T. Taleb, K. Samdanis, B. Mada, and _et al._ , “On Multi-Access Edge Computing: A Survey of the Emerging 5G Network Edge Cloud Architecture and Orchestration,” _IEEE Commun. Surveys $\&$ Tuts._, vol. 19, no. 3, pp. 1657-1681, May 2017.
  * [2] L. Lin, X. Liao, H. Jin, and _et al._ , “Computation Offloading Toward Edge Computing,” _Proc. IEEE_ , vol. 107, no. 8, pp. 1584-1607, Aug. 2019.
  * [3] Y. Mao, C. You, J. Zhang, and _et al._ , “A Survey on Mobile Edge Computing: The Communication Perspective,” _IEEE Commun. Surveys $\&$ Tuts._, vol. 19, no. 4, pp. 2322-2358, Aug. 2017.
  * [4] M. Satyanarayanan, “The Emergence of Edge Computing,” _Computer_ , vol. 50, no. 1, pp. 30-39, Jan. 2017.
  * [5] M. A. Maddah-Ali and U. Niesen, “Fundamental Limits of Caching,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 5, pp. 2856-2867, May 2014.
  * [6] S. Wang, X. Zhang, Y. Zhang, and _et al._ , “A Survey on Mobile Edge Networks: Convergence of Computing, Caching and Communications,” _IEEE Access_ , vol. 5, pp. 6757-6779, Mar. 2017.
  * [7] J. Xu, L. Chen and P. Zhou, “Joint Service Caching and Task Offloading for Mobile Edge Computing in Dense Networks,” in _Proc. of IEEE INFOCOM_ , Honolulu, HI, Apr. 2018, pp. 207-215.
  * [8] G. Franks, T. Al-Omari, M. Woodside, and _et al._ , “Enhanced Modeling and Solution of Layered Queueing Networks,” _IEEE Trans. Softw. Eng._ , vol. 35, no. 2, pp. 148-161, Mar.-Apr. 2009.
  * [9] G. Zhao, H. Xu, Y. Zhao, and _et al._ , “Offloading Dependent Tasks in Mobile Edge Computing with Service Caching,” in _Proc. of IEEE INFOCOM_ , Toronto, ON, Canada, Jul. 2020, pp. 1997-2006.
  * [10] G. Casale, “Integrated Performance Evaluation of Extended Queueing Network Models with LINE,” in _Proc. of WSC_ , 2020, pp. 2377–2388.
  * [11] K. Shanmugam, N. Golrezaei, A. G. Dimakis, and _et al._ , “FemtoCaching: Wireless Content Delivery Through Distributed Caching Helpers,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 12, pp. 8402-8413, Dec. 2013.
  * [12] B. N. Bharath, K. G. Nagananda and H. V. Poor, “A Learning-Based Approach to Caching in Heterogenous Small Cell Networks,” _IEEE Trans. Commun._ , vol. 64, no. 4, pp. 1674-1686, Apr. 2016.
  * [13] A. Sengupta, S. Amuru, R. Tandon, and _et al._ , “Learning Distributed Caching Strategies in Small Cell Networks,” in _Proc. of ISWCS_ , Barcelona, Spain, Aug. 2014, pp. 917-921.
  * [14] P. Yang, N. Zhang, S. Zhang, and _et al._ , “Content Popularity Prediction Towards Location-Aware Mobile Edge Caching,” _IEEE Trans. Multimedia_ , vol. 21, no. 4, pp. 915-929, Apr. 2019.
  * [15] Z. Xie and W. Chen, “Storage Efficient Edge Caching with Time Domain Buffer Sharing at Base Stations,” in _Proc. of IEEE ICC_ , Shanghai, China, May 2019, pp. 1-6.
  * [16] S. Zhang, P. He, K. Suto, and _et al._ , “Cooperative Edge Caching in User-Centric Clustered Mobile Networks,” _IEEE Trans. Mobile Comput._ , vol. 17, no. 8, pp. 1791-1805, Aug. 2018.
  * [17] Y. Liu, A. Zhang, X. Xia, and _et al._ , “Proactive Data Caching and Replacement in the Edge Computing Environment,” in _Proc. of IEEE CLOUD_ , Beijing, China, Oct. 2020, pp. 193-200.
  * [18] L. Wang, L. Jiao, T. He, and _et al._ , “Service Entity Placement for Social Virtual Reality Applications in Edge Computing,” in _Proc. of IEEE INFOCOM_ , Honolulu, HI, Apr. 2018, pp. 468-476.
  * [19] I. Lera, C. Guerrero and C. Juiz, “Availability-Aware Service Placement Policy in Fog Computing Based on Graph Partitions,” _IEEE Internet Things J._ , vol. 6, no. 2, pp. 3641-3651, Apr. 2019.
  * [20] Z. Xu, L. Zhou, S. Chi-Kin Chau, and _et al._ , ”Collaborate or Separate? Distributed Service Caching in Mobile Edge Clouds,” in _Proc. of IEEE INFOCOM_ , Toronto, ON, Canada, Jul. 2020, pp. 2066-2075.
  * [21] L. Yang, J. Cao, G. Liang, and _et al._ , “Cost Aware Service Placement and Load Dispatching in Mobile Cloud Systems,” _IEEE Trans Comput._ , vol. 65, no. 5, pp. 1440-1452, May 2016.
  * [22] J. Xu, L. Chen and P. Zhou, “Joint Service Caching and Task Offloading for Mobile Edge Computing in Dense Networks,” in _Proc. of IEEE INFOCOM_ , Honolulu, HI, USA, Apr. 2018, pp. 207-215.
  * [23] X. Ma, A. Zhou, S. Zhang, and _et al._ , “Cooperative Service Caching and Workload Scheduling in Mobile Edge Computing,” in _Proc. of IEEE INFOCOM_ , Toronto, ON, Canada, Jul. 2020, pp. 2076-2085.
  * [24] L. Liu, H. Tan, S. H.-C. Jiang, and _et al._ , “Dependent Task Placement and Scheduling with Function Configuration in Edge Computing,” in _Proc. of IEEE/ACM IWQoS_ , Phoenix, AZ, USA, Jun. 2019, pp. 1-10.
  * [25] Multi-access Edge Computing (MEC); Phase2: Use Cases and Requirements, ETSI Group Spec. MEC 002, V2.1.1, Oct. 2018.
  * [26] G. Franks, T. Al-Omari, M. Woodside, and _et al._ , “Enhanced Modeling and Solution of Layered Queueing Networks,” _IEEE Trans. Softw. Eng._ , vol. 35, no. 2, pp. 148-161, Mar.-Apr. 2009.
  * [27] W. Zhao, R. Chellappa, P. J. Phillips, and _et al._ , “Face recognition: A literature survey,” _ACM Comput. Surv. (CSUR)_ , vol. 35, no. 4, pp. 399–458, 2003.
  * [28] N. C. Fofack, P. Nain, G. Neglia, and _et al._ , “Performance Evaluation of Hierarchical TTL-based Cache Networks,” _Comput. Netw._ , vol. 65, pp. 212-231, Jun. 2014.
  * [29] G. Casale and N. Gast, “Performance Analysis Methods for List-Based Caches With Non-Uniform Access,” _IEEE/ACM Trans. Netw._ , vol. 29, no. 2, pp. 651-664, Dec. 2020.
  * [30] G. Bolch, S. Greiner, H. De Meer, and _et al._ , _Queueing networks and Markov chains_ , John Wiley & Sons, 2006.
  * [31] N. Gast and B. V. Houdt, “Transient and Steady-state Regime of a Family of List-based Cache Replacement Algorithms,” in _Proc. of SIGMETRICS_ , pp. 123–136, ACM, 2015.
  * [32] M. Bertoli, G. Casale and G. Serazzi, “JMT: Performance Engineering Tools for System Modeling,” _ACM SIGMETRICS PER_ , vol. 36, no. 4, pp. 10–15, 2009.
  * [33] M. Shahrad, R. Fonseca, I. Goiri, and _et al._ , “Serverless in the Wild: Characterizing and Optimizing the Serverless Workload at a Large Cloud Provider,” in _Proc. of USENIX ATC 20_ , Jul. 2020, pp. 205-218.
  * [34] D. T. Hoang, D. Niyato, D. N. Nguyen, and _et al._ , “A Dynamic Edge Caching Framework for Mobile 5G Networks,” _IEEE Wireless Commun._ , vol. 25, no. 5, pp. 95-103, Oct. 2018.
  * [35] “A Guide to 5G Small Cells and Macrocells,” https://www. essentracomponents.com/en-gb/news/guides/guide-to-5g-small-cells-and-macrocells, Accessed: 2021-12-31.