capbtabboxtable[][] [figure]objectset=raggedright, margins=raggedright,
midcode=captionskip, captionskip=10pt

# PerfSim: A Performance Simulator for Cloud Native Microservice Chains

Michel Gokan Khan, Javid Taheri, Auday Al-Dulaimy, and Andreas Kassler M.
Gokan Khan, J. Taheri, and A. Kassler are with the Department of Mathematics
and Computer Science, Karlstad University, Sweden.
E-mails<EMAIL_ADDRESS>A. Al-Dulaimy is
with the School of Innovation, Design and Engineering, Mälardalen University,
Sweden. E-mail<EMAIL_ADDRESS>
###### Abstract

Cloud native computing paradigm allows microservice-based applications to take
advantage of cloud infrastructure in a scalable, reusable, and interoperable
way. However, in a cloud native system, the vast number of configuration
parameters and highly granular resource allocation policies can significantly
impact the performance and deployment cost. For understanding and analyzing
these implications in an easy, quick, and cost-effective way, we present
PerfSim, a discrete-event simulator for approximating and predicting the
performance of cloud native service chains in user-defined scenarios. To this
end, we proposed a systematic approach for modeling the performance of
microservices endpoint functions by collecting and analyzing their performance
and network traces. With a combination of the extracted models and user-
defined scenarios, PerfSim can then simulate the performance behavior of all
services over a given period and provide an approximation for system KPIs,
such as requests’ average response time. Using the processing power of a
single laptop, we evaluated both simulation accuracy and speed of PerfSim in
104 prevalent scenarios and compared the simulation results with the identical
deployment in a real Kubernetes cluster. We achieved
$\scriptstyle\mathtt{\sim}$81-99% simulation accuracy in approximating the
average response time of incoming requests and
$\scriptstyle\mathtt{\sim}$16-1200 times speed-up factor for the simulation.

###### Index Terms:

performance simulator, performance modeling, cloud native computing, service
chains, simulation platform

##  1 Introduction

Cloud Native Computing is an emerging paradigm of distributed computing that
“empower organizations to build and run scalable applications in modern,
dynamic environments such as public, private, and hybrid cloud” [a2018_cncf].
One of the key purposes of introducing this paradigm was to answer the
increasing need for mitigating the efforts of application-level clustering in
the cloud and inline with the emergence of microservice architecture that
promotes decoupling components of a software system into multiple
independently manageable services, known as a microservice
[10.1145/3183628.3183631]. Since Google first introduced Kubernetes during the
Google Developer Forum in 2014, as an approach for “decoupling of application
containers from the details of the systems on which they run” [k8s_intro], it
becomes the de-facto enabler for utilizing microservice architecture based on
technologies such as OS-level virtualization, better known as containers
[Casalicchio2019].

Amongst the main advantages of cloud native computing is the possibility for
allocating highly granular resources to large-scale chains of services in a
cluster. This additional granularity, while facilitating the scalability of
service chaining, imposes complexity in resource allocation, traffic shaping
and placement of containers in a cluster. Therefore, as microservices networks
grow larger, the need for tools and techniques that shed light on service
chaining implications upon system performance becomes critical. Furthermore,
by the rising trend of cloud native computing in containerized cluster
environments, many researchers are nurturing new methods and schemes to
implement new deployment [10.1007/978-3-030-45989-5_6] and performance
optimization techniques [mao2020resource] at various levels: starting from
modern container scheduling [HU2020562, Liu2018ANC, Menouer2020KCSSKC,
Mao2020SpeculativeCS] methods to predictive request load-balancing
[Burroughs2021] and resource auto-scaling algorithms [Casalicchio2019-2,
10.1007/978-981-13-9190-3_35].

Analyzing the performance behavior of a service chain in a real testbed gives
the most reliable results. However, evaluating in real clusters is not always
possible. In many cases, it might be too costly, notably time-consuming, and
sometimes various skill sets are required to configure, run and manage the
testbed. Moreover, in most performance optimization techniques, various
scenarios need to be evaluated in a timely manner to eventually minimize a
cost function. Performing such evaluations in a real testbed, while providing
accurate results, imposes a dramatic burden for achieving a scalable and
efficient optimization method.

Moreover, modern cloud native distributed systems have important performance
affecting properties that earlier generation software systems such as
monoliths (single-tiered software systems consisting of multiple tightly-
coupled components) didn’t have to cope with as much. Properties such as agile
horizontal/vertical scaling, highly granular resource allocation, context-
awareness, contention with other services, service chaining, and dynamic load-
balancing between replicas.

To mitigate the aforementioned implications of using real testbeds for
performance evaluation of cloud native microservice chains, we proposed
PerfSim, a simulation platform that aims to approximately predict the
performance of service chains under various placement, resource allocation,
and traffic scenarios using profoundly limited resources of a laptop. We also
proposed a systematic performance modeling approach to model the time-
predictable endpoint functions of microservices using performance traces
generated by the profiling and tracing tools such as perf and ebpf as well as
distributed network tracing programs such as jeager and zipkin. Using these
models and a user-defined scenario, PerfSim can then simulates performance
behavior of all service chains under a desired placement, resource allocation
policy, network topology and traffic scenario.

Using profoundly limited resources of a laptop, we evaluated the simulation
accuracy and speed of PerfSim under 104 prevalent scenarios by deploying and
running them on a real Kubernetes cluster and comparing measured KPIs with the
simulation results (i.e., average requests latency). We used sfc-stress, a
synthetic service chain generation toolkit, for generating various service
chains and microservice-based workloads. In our evaluation, we achieved
$\scriptstyle\mathtt{\sim}$81-99% accuracy in predicting the average latency
of incoming requests and $\scriptstyle\mathtt{\sim}$16-1200 times speed-up
factor between the simulation time and actual execution time on a real
cluster. With the same laptop, we also simulated a large service chain
consisting of 100 microservices interconnected with 200 links over 100 hosts
and showed that PerfSim can be effectively used for large-scale simulations.

To summarize, with PerfSim we contributed to the relatively new, but rich area
of cloud native computing by enabling a fast, accurate and easy way for
evaluating various user-defined policies in microservice-based applications.

##  2 Related Works

In this section, we briefly review existing works in the areas of (1)
simulation platforms, (2) emulation tools and (3) analytical performance
modeling approaches. Table I presents a comparison between the key properties
of the most popular frameworks with PerfSim. In this table, besides common
features, we also compared additional challenges imposed by simulating
performance of microservices in cloud native environments.

###  2.1 Simulation tools

Cloud native systems have intricate provisioning and deployment requirements.
Evaluating and predicting the performance of such services, studying the
impact of provisioning policies, and correlating workload models with
achievable performance are not straightforward due to the diversity and
complexity of system interactions. Even though studying these interactions on
real testbeds provides the most accurate results, several researchers and
companies argue that computer simulation can be a powerful method to test
multiple scenarios and evaluate various policies before enforcing them at
different levels [5683561, CloudSimToolkit2010, PULIAFITO2020102062,
Riley2010]. In recent years, several works aim to predict the services’
performance using computer simulations to develop adequate resource policies
and other decisions at different levels to meet the required Quality of
Service (QoS) in a dynamic manner.

CloudSim [CloudSimToolkit2010] is one of the most popular simulators in this
category that is designed to simulate cloud computing infrastructures. It
allows modeling of various data centers, workload scheduling, and allocation
policies. Using CloudSim in many scenarios can boost the development of
innovative methods and algorithms in the cloud computing paradigm without the
need for deploying applications in the production environments. In recent
years, several tools and modules had been designed based on CloudSim. For
example, the iFogSim toolkit [iFogSim2017] inherits the features of CloudSim,
and extends them by the ability of modeling IoT and Edge/Fog environments. The
authors in [EdgeCoudSim2018] also built upon CloudSim to simulate the
specifications of edge/fog computing and support the required functionalities.
There exist several other CloudSim-based simulators for simulating various use
cases in fog or edge environments [7987304, RECAP2017-1].

CloudSim and modules/plugins/tools based on CloudSim provide a sophisticated
and straightforward way for researchers to simulate cloud/edge/fog computing
infrastructure for modeling service brokers, data-centers, and scheduling
policies. However, they are not designed with the purpose of simulating
rigorous performance testings of microservices under extremely granular
resource allocation and placement policies that exists in containerized
services in cloud native applications. Moreover, to effectively simulate a set
of service chains, we need to precisely specify the links and connections
between each microservice within all chains, and then route the requests based
on the user-defined traffic scenarios and network topology model. Something
that the CloudSim category of simulators has not been designed to address.

In addition to CloudSim, there are other simulators in the context of cloud
simulation. Yet Another Fog Simulator (YAFS) [YAFS2019] is a discrete-event
simulator based on Simpy that allows to simulate the impact of applications’
deployment in edge/fog computing environments through customizable strategies.
YAFS allows to model the relationships between applications, infrastructure
configurations, and network topologies. It uses those relationships to predict
network throughput and latency in dynamic and customized scenarios, such as
path routing and service scheduling. Even though YAFS offers a novel approach
towards simulating performance of large network topologies, it’s not designed
to simulate the microservices’ performance within the context of complex
service chains over a set of hosts in a cluster.

Apart from cloud/edge/fog simulators, there exist other simulators that focus
on specific aspects of cloud computing paradigm, such as energy efficiency or
network modeling and optimization. For example, GreenCloud [5683561], is a
packet-level simulator for capturing energy footprint of data center
components with the aim towards providing an environment for researchers to
design more energy-aware data centers [7090996, 6825028]. Other examples are
NS-3 [Riley2010], OMNet++ [Varga2019] and NetSim [WAHIDULASHRAF2018547] that
are primarily designed to simulate various types of networks and topologies.
Although these simulators can smoothly simulate specific aspects of cloud
systems that they are designed for (e.g., networking and energy efficiency),
they cannot be used to simulate cloud native applications’ performance; or at
least can only be used to simulate specific aspects of service chains, such as
their network performance or placement efficiency.

###  2.2 Performance emulators

Another popular experimentation approach in evaluating performance of cloud
systems is emulation. Using emulation, users can analyze the system
performance behavior supported by the available hardware in a more realistic
way than using simulation [beuran2012introduction]. Mininet [MiniNetWebsite,
10.1145/1868447.1868466] is one of the widely used network emulators that can
form a network of virtual switches, routers, controllers, links, and hosts.
The hosts in Mininet are able to run Linux network software, while switches
offer flexible custom routing and SDN. The bright reputation of Mininet
inspired many researchers to extend Mininet in various ways. For example,
MaxiNet [6857078] extended MiniNet to support spanning emulated networks over
multiple hosts. Then EmuFog [EmuFog2017] extended MaxiNet to support fog
computing deployment models. Another MaxiNet-based emulator, called Fogbed
[Fogbed2018] enables the emulation of fog nodes as software containers under
various network configurations to mimic edge/fog environments.

After Mininet introduced the idea of using containers for network and process
emulation, other works also started to adopt a similar concept. For example,
Dockemu [to2015dockemu] adopted both Docker for emulating network nodes and
NS-3 for simulating the network traffic. NEaaS [lai2020network], a cloud-based
network emulation platform, utilizes both Docker and virtual machines to
emulate various networking scenarios.

However, the widespread popularity of such emulators stands in stark contrast
to the rather trembling fact that they are bounded to the available
computation power and bandwidth of the underlying hardware they are deployed
upon, and consequently, they cannot be efficiently used to predict the
resource utilization aspects of large-scale and complex cloud native
applications. Moreover, emulation cannot dramatically improve the speed of
evaluating various resource allocation or placement policies, and therefore
can’t be used for exhaustive policy testing.

###  2.3 Analytical performance modeling approaches

TABLE I: Comparison of performance characteristics in popular simulation and
emulation frameworks with PerfSim

|  Type |  |  Target Environment |  Granular Resource Allocation |  Vertical Scaling |  Horizontal Scaling |  |  CPU Scheduling |  Multi-threaded Endpoints |  Contention Modeling |  Fast Performance Prediction |  PTE Independent/Low Cost |  |  Service Chains Support |  Multi-chain Support |  Dynamic Control |  |  Load-balancing |  Congestion Control |  Advanced Routing
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
CloudSim category [CloudSimToolkit2010] | S |  | Cloud |  | ✓ |  |  | ✓ |  |  | ✓ | ✓ |  |  |  | ✓ |  | ✓ | ✓ |
YAFS [YAFS2019] | S |  | Fog/Edge |  |  |  |  |  |  |  | ✓ | ✓ |  | ✓ | ✓ | ✓ |  |  | ✓ | ✓
GreenCloud [5683561] | S |  | Cloud |  |  |  |  |  |  |  | ✓ | ✓ |  |  |  | ✓ |  | ✓ |  |
NS-3 [Riley2010] | S |  | Any |  |  |  |  |  |  |  | ✓ | ✓ |  | ✓ | ✓ | ✓ |  | ✓ | ✓ | ✓
OMNet++ [Varga2019] | S |  | Any |  |  |  |  |  |  |  | ✓ | ✓ |  | ✓ | ✓ | ✓ |  | ✓ | ✓ | ✓
NetSim [WAHIDULASHRAF2018547] | S |  | Any |  |  |  |  |  |  |  | ✓ | ✓ |  | ✓ | ✓ | ✓ |  | ✓ | ✓ | ✓
Emulators [10.1145/1868447.1868466][to2015dockemu][lai2020network] | E |  | Any | ✓ | ✓ | ✓ |  | ✓ | ✓ | ✓ |  |  |  | ✓ | ✓ | ✓ |  |  | ✓ | ✓
PerfSim | S |  | Cloud/Edge | ✓ | ✓ | ✓ |  | ✓ | ✓ | ✓ | ✓ | ✓ |  | ✓ | ✓ | ✓ |  | ✓ | ✓ |
S=Simulator,E=Emulator | Resources |  | Threads |  | Services |  | Network |

There is a third category of approaches towards modeling the performance of
cloud native applications which based upon an analytical framework. Contrary
to the simulation/emulation techniques, which employ a bottom-up approach in
modeling and simulating various performance aspects of cloud applications,
analytical methods adopt a top-down approach for that purpose by collecting
and analyzing application KPIs via running various stress tests on the system
or using historical performance measurements.

As an example, the work proposed in [LearningPredictiveAutoscaling2019] aims
to model the response time of microservices based on stress testing and
concurrently collecting performance traces for predefined intervals to learn a
predictive auto-scaling model, such that the response time requirements are
satisfied. Those performance traces are used to learn the resource
provisioning policy model using a regression analysis approach. In
[PerformanceModelingfor2019], microservices are being tested individually
using service-based sandboxing to construct the corresponding model, the
analyzed data and performance model are presented to the user. Considering
modeling throughput and latency, in our previous work
[APerformanceModellingApproach2020], we used a combination of stress-testing
and regression modeling approaches to understand the impact of microservices’
resource configurations, model the correlation between the KPIs and resource
configurations in a smaller Performance Testing Environment (PTE) to predict
the performance in a larger Production Environment (PE).

Although the aforementioned methods benefit from accurate performance
measurements on real systems and can be considered as the most widely used
techniques in performance engineering in production environments, they suffer
from three major limitations. Their first limitation is the high cost of test
environment preparation that can accurately provide performance measurements.
As for gathering accurate performance insights, the tests need to be performed
on either a production environment or a PTE that mimics it; that imposes a
high cost of deployment in either case. The second limitation is the slow
stress-testing procedure as for getting accurate results, several hours of
performance testing is required. Last but not least of their limitations is
applicability in utilizing advanced optimization techniques, such as deep
learning or meta-heuristics based optimization heuristics, which requires
numerous re-deployments to learn, train, or find an optimal policy.

##  3 PerfSim Design and Implementation

In this section, we introduce the system architecture and implementation
details of PerfSim and mathematical notation used in this paper (summarized in
Table II).

###  3.1 Modeling elements of cloud native systems

PerfSim has models for various elements of cloud native systems and their
underlying infrastructure.

As described in the previous sections, the joint problem of placement and
resource allocation of a service chain over a cluster is complex as multiple
dimensions impact the achievable performance and latency. However, several
parameters have only marginal impact on the prediction quality. Consequently,
we aim at providing a simplified model that is tractable but powerful enough
in order to predict the performance of typical cloud native service chain
architectures when deployed on several well-known container orchestration
platforms such as Kubernetes.

TABLE II: Table of the base notations used in this paper

Hosts |  $H=\\{h_{k}\\}_{k=1}^{|H|}$ |  Set of hosts |  $W^{r^{H}}$ |  Weights of resources |  $h_{k}^{\text{cores}},h_{k}^{\text{clock}}$ |  Cores count and CPU clock (hz) in $h_{k}$
---|---|---|---|---|---|---
|  $r^{H}\in{R^{H}}$ |  Set of resource names |  $\hat{V}_{H}(r^{H},h_{k})$ |  Initial $r^{h}$ capacity of $h_{k}$ |  ${V_{H}(r^{H},h_{k})}$ |  Current $r^{H}$ capacity of $h_{k}$
Network
Topology |  $P=\\{\rho_{z}\\}_{z=1}^{|P|}$ |  Set of all routers |  $L=~\\!\\!{}^{\scalebox{0.6}{$H$}}\\!{L}\cup{{}^{\scalebox{0.7}{$\tau$}}\\!{L}}$ |  Set of all network links |  $G(\tau)=(P,L)$ |  Graph represent. of network topology $\tau$
|  ${}^{\scalebox{0.6}{$H$}}\\!{L}=\\{^{\scalebox{0.6}{$H$}}\\!{l}_{o}\\}_{o=1}^{|^{\scalebox{0.5}{$H$}}\\!{L}|}$ |  Set of host$\leftrightarrows$router links |  $\rho_{z}^{\text{in bw}},\rho_{z}^{\text{out bw}}$ |  In/out bw of $\rho_{z}$ (Bps) |  $G(\tau)_{h_{a},h_{b}}$ |  Network path between $h_{a}$ and $h_{b}$
|  ${}^{\scalebox{0.7}{$\tau$}}\\!{L}=\\{^{\scalebox{0.7}{$\tau$}}\\!{l}_{o}\\}_{o=1}^{|^{\scalebox{0.7}{$\tau$}}\\!{L}|}$ |  Set of router$\leftrightarrows$router links |  $l_{o}^{\text{lat}},\rho_{z}^{\text{lat}}$ |  Latencies of $l_{o}$ & $\rho_{z}$ (ns) |  $\rho^{h_{k}}\in{P}$ |  The router connected to $h_{k}$
Services and
Endpoints |  $S=\\{S_{i}\\}_{i=1}^{|S|}$ |  Set of all services |  $r^{S}\in{R^{S}}$ |  Set of res. ctrl. params |  $\Pi=(p_{i,j}\in{\\{0,1\\}})$ |  Service replica placement matrix
|  $S_{i}=\\{\hat{s}_{j}^{i}\\}_{j=1}^{|S_{i}|}$ |  Set of replicas of $S_{i}$ |  $\hat{V}_{S}(r^{S}\\!,S_{i})$,$V_{S}(r^{S}\\!,\hat{s}_{j}^{i})$ |  Initial/current $r^{S}$ cap. of $\hat{s}_{j}^{i}$ |  $\Pi(\hat{s}_{j}^{i})\in{H}$ |  The host that $\hat{s}_{j}^{i}$ is currently placed
|  $F_{i}=\\{f_{n}^{i}\\}_{n=1}^{|F_{i}|}$ |  Set of endpnt. funcs of $S_{i}$ |  $A_{S_{i}},\widetilde{A}_{S_{i}}$ |  Affinities/anti-affinities |  $H^{\hat{s}_{j}^{i}}$, $\psi_{\hat{s}_{j}^{i}}^{h_{k}}$ |  Eligible hosts and score of $h_{k}$ for $\hat{s}_{j}^{i}$
Service Chains
and Traffic |  $C=\\{C_{l}\\}_{l=1}^{|C|}$ |  Set of service chains |  $\\!\\!~{}^{l}\\!F$=$\\{\\!\\!~{}^{l}\\!f_{n}\\}_{n=1}^{|\\!\\!~{}^{l}\\!F|}$ |  Set of endpnt. funcs in $C_{l}$ |  $\\!\\!~{}^{l}\\!U$=$\\{\\!\\!~{}^{l}\\!u_{o}\\}_{o=1}^{|\\!\\!~{}^{l}\\!U|}$ |  Set of user requests in $C_{l}$
|  $\\!\\!~{}^{l}\\!S=\\{\\!\\!~{}^{l}\\!S_{i}\\}_{i=1}^{|\\!\\!~{}^{l}\\!S|}$$\subseteq{S}$ |  Set of services in $C_{l}$ |  $\\!\\!~{}^{l}\\!F_{i}$=$\\{\\!\\!~{}^{l}\\!f^{i}_{n}\\}_{n=1}^{|\\!\\!~{}^{l}\\!F_{i}|}\\!\subseteq{\\!\\!\\!~{}^{l}\\!F}$ |  Set of endpnt. funcs of $\\!~{}^{l}\\!S_{i}$ |  $C_{l}^{\text{rate}},\\!C_{l}^{\text{duration}},\\!C_{l}^{\text{batch}}$ |  Arrival rate/duration & batch size of $C_{l}$
|  $\\!\\!~{}^{l}\\!E=\left(\\!\\!~{}^{l}\\!e_{x}\right)_{x=1}^{|\\!\\!~{}^{l}\\!\\!E|}$ |  Ordered set of links in $C_{l}$ |  $G(C_{l})$=$(\\!~{}^{l}\\!F$,$~{}^{l}\\!E)$ |  Graph represent. of $C_{l}$ |  $\\!\\!~{}^{l}\\!u_{o}^{\text{in time}},\\!\\!~{}^{l}\\!u_{o}^{\text{exe time}}$ |  Req. arrival & exe time of $\\!\\!~{}^{l}\\!u_{o}$
Threads |  $\\!\\!~{}^{l}\\!f_{n}$=$\\{t_{m}\\}_{m=1}^{|\\!\\!~{}^{l}\\!f_{n}|}$ |  Set of threads in $\\!\\!~{}^{l}\\!f_{n}$ |  $t_{m}^{\text{maccs}}$ |  Mem. accesses of $t_{m}$ |  $t_{m}^{\text{blk rw}}$ |  blkio R/W of $t_{m}$ (in bytes)
|  $\\!\\!~{}^{l}\\!f^{i}_{n}$=$\\{t_{m}|t_{m}\in{\\!\\!~{}^{l}\\!f^{i}_{n}}\\}$ |  Set of threads in $\\!\\!~{}^{l}\\!f_{n}^{i}\subseteq{\\!\\!~{}^{l}\\!f_{n}}$ |  $t_{m}^{\text{crefs}},t_{m}^{\text{cmiss}}$ |  Cache refs & misses of $t_{m}$ |  $t_{m}^{\text{idle}}$ |  Total idle time of $t_{m}$
|  $t_{m}^{\text{inst}},t_{m}^{\text{CPI}}$ |  Inst. count & CPI of $t_{m}$ |  $t_{m}^{\text{cpenalty}}$ |  Avg. lost cycles per miss |  $\hat{f}_{h_{k}}$ |  Set of running threads on $h_{k}$

####  3.1.1 Hosts

An $h_{k}\in{H=\\{h_{k}\\}_{k=1}^{|H|}}$ is a model of Linux-based physical
machine that has $h_{k}^{\text{cores}}$ number of CPU cores with
$h_{k}^{\text{clock}}$ clock speed (in Hertz). It has also a set of consumable
resources, such as a memory capacity (in bytes), a NIC with a limited ingress
and egress network bandwidth (in bytes per second), a local storage with a
limited storage read/write bandwidth and storage capacity. The CPU resource is
measured in millicores. Each host $h_{k}$ introspects the OS to determine the
$h_{k}^{\text{cores}}$ and then multiples it by $1000$ to denote its total
capacity (Eq. 1).

$h_{k}^{\text{millicores}}=h_{k}^{\text{cores}}\times{1000}$ (1)

To facilitate our formulation, we denote hosts consumable resources as
$R^{H}=\\{$millicores, mem, in bw, out bw, blkio bw, blkio size$\\}$. For each
resource $r^{H}\in{R^{H}}$, a host $h_{k}$ has an initial resource capacity
denoted as $\hat{V}_{H}(r^{H},h_{k})$ as well as a current capacity denoted as
$V_{H}(r^{H},h_{k})$.

####  3.1.2 Network topology

A network topology, denoted as $\tau$, has a directed acyclic graph
representation of $G(\tau)=(P,^{\scalebox{0.7}{$\tau$}}\\!\\!{L})$ with
routers $\rho_{z}\in{P}$ as nodes, and directed links
${}^{\scalebox{0.7}{$\tau$}}\\!{l}_{o}=(\rho_{i},\rho_{j})\in{{}^{\scalebox{0.7}{$\tau$}}\\!{L}}$
between them as edges. To separately model egress and ingress bandwidth of
interconnection between nodes, we hypothetically assumed there are always 2
links between each pair of routers with opposite directions. We denote the
maximum ingress/egress bandwidth of a router as $\rho_{z}^{\text{in bw}}$ and
$\rho_{z}^{\text{out bw}}$.

Each host $h_{k}$ is connected to a router
${\rho}^{h_{k}}\in{P=\\{\rho_{z}\\}_{z=1}^{|P|}}$ using a hypothetically
separated egress/ingress directed links, denoted as
${}^{\scalebox{0.6}{$H$}}\\!{l}_{o}\in{{}^{\scalebox{0.6}{$H$}}\\!{L}}$ that
have a pair of ordered host$\rightarrow$router $(h_{k},\rho_{i})$ and
router$\rightarrow$host $(\rho_{i},h_{k})$) links.

Each router $\rho_{z}$ and link $l_{o}\in{L}$, may respectively add extra
latency of $\rho_{z}^{\text{lat}}$ and $l_{o}^{\text{lat}}$ nanoseconds to
each request. These additional latencies differs from the delay caused by
network congestion which we modelled separately.

####  3.1.3 Services

We assume that each chain of services is composed of a set of $|S|$
containerized services $S=\\{S_{i}\\}_{i=1}^{|S|}$ such that each
$S_{i}\in{S}$ may have $|S_{i}|$ number of single-process/multi-threaded
replicas $\\{\hat{s}_{j}^{i}\\}_{j=1}^{|S_{i}|}$ load balanced among $|H|$
hosts and connected through $|P|$ routers. A given service $S_{i}$ has a set
of endpoint functions $F_{i}=\\{f_{n}^{i}\\}_{n=1}^{|F_{i}|}$ that can be
executed based on the type of incoming request. Each endpoint function
$f_{n}^{i}$ may spawns a set of threads $t_{m}\in{f_{n}^{i}}$. We will explain
properties of these threads in section 3.1.10.

####  3.1.4 CPU scheduler and resource controller

A service $S_{i}$ may optionally have resource constraints on its
containerized replicas. We denote this set of resources as $R^{S}=\\{$CPU
requests, mem requests, in bw, out bw, blkio bw, blkio size$\\}$, which
corresponds to resources $R^{H}$ in each host ($R:R^{S}\rightarrow{R^{H}}$).
By default, there is no reservation or usage limitation on any resource.

In Linux kernel, a service replica is in a form of a container and is being
managed by Control Groups (cgroups) [cgroups] that is responsible for auditing
and restricting a set of processes. The limits associated with cgroups isolate
the resource usage of a collection of processes.

We partially modeled the behaviour of cgroups in PerfSim by allowing a service
$S_{i}$ to initially reserve $\hat{V}_{S}(r^{S},S_{i})$ resource capacities
for each of its replicas. When reserving CPU requests $\hat{V}_{S}(\text{CPU
requests},S_{i})$, PerfSim allows a replica to use as much as CPU units
available, even more than its reserved quota. We also partially modeled the
behaviour of CPU bandwidth controller [36669] of Linux by allowing to define
$S_{i}^{\text{CPU limits}}$ (in millicores) as an upper bound for replicas’
CPU consumption. In kernel level, CPU request and limit is translated to
cgroups cpu.shares, cpu.cfs_quota_us (in microseconds) and cpu.cfs_period_us
(in microseconds) control parameters. We denote them as $S_{i}^{\text{CPU
share}},S_{i}^{\text{CPU quota}}$, and $S_{i}^{\text{CPU period}}$. However,
for simplicity, we assume a fixed value for $S_{i}^{\text{CPU period}}$=100ms
in our calculations and only considered CPU share and quota when estimating
available resources for each replica. A usage example for this model is
simulating Kubernetes Best Effort and Guaranteed QoS classes for CPU resources
which we will cover in section 5.2.

The $\hat{V}_{S}(\text{mem requests},S_{i})$ specifies the initial memory
allocation of replicas of $S_{i}$ (in bytes). We modelled the
memory.limit_in_bytes control parameter in cgroups in a way that it may only
affect the placement of replicas.

To control the traffic shaping and the maximum network bandwidth of replicas
in $S_{i}$, the $\hat{V}_{S}(\text{in bw},S_{i})$, and $\hat{V}_{S}(\text{out
bw},S_{i})$ control parameters can be used (in Bps).

The storage size of replicas in PerfSim is controlled by a model of blkio
cgroups controller and denoted as $\hat{V}_{S}(\text{blkio size},S_{i})$. We
also denote the available bandwidth for blkio reads and write as
$\hat{V}_{S}(\text{blkio bw},S_{i})$. We intended to model and simulate the
disk bandwidth throttling feature of cgroups blkio.throttle.write_bps_device.

####  3.1.5 Affinity controller

A service may optionally have a set of in-service affinity/anti-affinity rules
for its placement. We define two binary decision vectors $A_{S_{i}}$ and
$\widetilde{A}_{S_{i}}$ that are respectively holding all the affinity and
anti-affinity rules related to service $S_{i}$. Each vector has a dimension of
$|S|\times 1$ where each row represents one of the services. An entry
$A_{S_{i}}[S_{j}]$ takes on the value of ‘1’ if replicas of services $S_{i}$
and $S_{j}$ must be placed at the same host and ‘0’ otherwise; and similarly
an entry $\widetilde{A}_{S_{i}}[S_{j}]$ takes on a value of ‘1’ if any
replicas of both services must not be placed at the same host and ‘0’
otherwise. It’s also possible to define host affinities, but due to the page
limitation we omitted the formal definition.

####  3.1.6 Placement algorithm

The placement of each $\hat{s}_{j}^{i}$ among all hosts, takes place using a
placement algorithm. By default, we implemented the Least Allocated bin
packing algorithm which partially simulates the container scheduling mechanism
of Kubernetes. This algorithm, favor hosts with fewer resource requests and is
controlled with weights for each resource $r^{H}\in{R^{H}}$, denoted as
$W^{r^{H}}$ to be used for scoring nodes. We described the details of this
algorithm in the next section.

####  3.1.7 Container scheduler

We use a binary matrix $\Pi$ of size $(\sum_{i=1}^{|S|}{|S_{i}|})\times{|H|}$
to keep tack of service replicas placement. In this matrix,
$p_{j,k}\in{\Pi}=1$ if the replica $\hat{s}_{j}\in\\{S_{i}\\}_{\in{S}}$ is
placed in host $h_{k}$ and $p_{j,k}$=$0$ if otherwise. Since each replica can
only be placed on one host, $\Pi(\hat{s}_{i}^{j})\in{H}$ indicates the host
that replica $\hat{s}_{i}^{j}$ is placed. After placing each replica, the
amount of available resources in each host $V_{H}(r^{H},h_{k})$ are
recalculated for all resources.

####  3.1.8 Service chains

The goal of services is to serve requesters through a set of service chains
$C=\\{C_{l}\\}_{l=1}^{|C|}$. These service chains represent the connection and
traffic flow between endpoint functions of services and are specified as a
directed flow network $G(C_{l})$=$(\\!\\!~{}^{l}\\!F,\\!\\!~{}^{l}\\!E)$ where
$\\!\\!~{}^{l}\\!F$ is the subset of endpoint functions which have a role in
providing service chain $C_{l}$, and $\\!\\!~{}^{l}\\!E$ is the subset of all
virtual links belonging to the service chain $C_{l}$. In other words, all
endpoint functions within $C_{l}$ are connected through $|\\!\\!~{}^{l}\\!E|$
number of ordered directed virtual links
$\\!\\!~{}^{l}\\!E$=$\big{(}\\!~{}^{l}\\!e_{1}$=$(\\!\\!~{}^{l}\\!f_{a},\\!\\!~{}^{l}\\!f_{a^{\prime}}\\!),...,\\!\\!~{}^{l}\\!e_{|\\!\\!~{}^{l}\\!E|}$=$(\\!\\!~{}^{l}\\!f_{c},\\!\\!~{}^{l}\\!f_{c^{\prime}})\big{)}$.
Each $\\!\\!~{}^{l}\\!e_{v}\in{\\!\\!~{}^{l}\\!E}$ has a request payload
$\\!\\!~{}^{l}\\!e_{v}^{\text{payload}}$ in bytes, which indicates the request
size flowing from edge’s first vertex to the second.

The first node in a $C_{l}$ is its only request entry point, known as the
source node, that receives requests from potential request senders and the
cluster load-balancer directs the traffic to a replica $\hat{s}_{j}^{i}$ based
on a desired load-balancing algorithm (default is Round-robin). A service
chain has also one or more sink nodes with no immediate outgoing edges.

####  3.1.9 Traffic control

Assuming a service chain $C_{l}$ is active for $C_{l}^{\text{duration}}$
seconds. The traffic rate of each $C_{l}$ is being controlled with 2 control
parameter $C_{l}^{\text{rate}}$ and $C_{l}^{\text{batch}}$; every
$\frac{1}{C_{l}^{\text{rate}}}$ seconds, a batch of $C_{l}^{\text{batch}}$
requests will arrive to service chain $C_{l}$. In other words, each service
chain $C_{l}$ may be requested by a plurality of $C_{l}^{\text{batch}}$ users
with an average arrival rate of
$C_{l}^{\text{rate}}\frac{\text{req}}{\text{s}}$. Therefore, the number of
requests $|\\!\\!~{}^{l}\\!U|$ for service chain $C_{l}$ over a period of time
$C_{l}^{\text{duration}}$ will be equal to
$C_{l}^{\text{duration}}\times{C_{l}^{\text{rate}}}\times{C_{l}^{\text{batch}}}$.
We denote set of all user requests of $C_{l}$ as
$\\!\\!~{}^{l}\\!U=\\{\\!\\!~{}^{l}\\!u_{o}\\}_{o=1}^{|\\!\\!~{}^{l}\\!U|}$
and their arrival time and execution time are denoted by
$\\!\\!~{}^{l}\\!u_{o}^{\text{in time}}$ and $\\!\\!~{}^{l}\\!u_{o}^{\text{exe
time}}$, respectively.

####  3.1.10 Service endpoint functions and associated threads

During the life cycle of the $C_{l}$, each endpoint function
$\\!\\!~{}^{l}\\!f_{n}\in{\\!\\!~{}^{l}F}$ spawns $|\\!\\!~{}^{l}\\!f_{n}|$
number of threads $\\{t_{m}\\}_{m=1}^{|\\!\\!~{}^{l}\\!f_{n}|}$ on one of its
replicas. Since each replica is placed on a host, we denote a subset of all
threads running on a host $h_{k}$ as $\hat{f}_{h_{k}}$.

Each thread $t_{m}\in{\\!\\!~{}^{l}\\!f_{n}}$ has a set of properties that
specified in the original model and extracted based on measurements of the
performance traces and monitoring tools during the modeling phase which we
will explain in section 3.2.

A $t_{m}$ executes $t_{m}^{\text{inst}}$ CPU instructions in which
$t_{m}^{\text{maccs}}$ number of them are due to memory accesses with
$t_{m}^{\text{CPI}}$ average CPU Cycle per Instruction (CPI). Moreover,
$t_{m}$ has total of $t_{m}^{\text{crefs}}$ cache references in which, when
$\hat{s}_{j}^{i}$ is deployed on an isolated and single core reference
machine, $t_{m}^{\text{cmiss}}$ number of those references will be cache
misses with average miss penalty of $t_{m}^{\text{cpenalty}}$ cycles. During
the simulation, PerfSim dynamically re-calculates cache misses based on
various factors such as co-located active threads, number of cores, CPU
requests, and cache size.

A thread may also read/write a total of $t_{m}^{\text{blk rw}}$ bytes of data
from/to the storage device. Moreover, a thread might be idle for some time
during its active life-cycle and we denote $t_{m}$ accumulated period of the
idle time as $t_{m}^{\text{idle}}$.

On a real Linux machine, threads are load balanced among all CPU runqueues in
the host using the Linux’s Completely Fair Scheduler (CFS). We implemented a
simplified version of CFS in PerfSim to imitate the impact of thread
scheduling mechanism on the performance. We described the details of our
implementation in section 5.

###  3.2 Modeling process

Figure 1: An overview of our proposed systematic method for modeling various
service chains and microservices with their corresponding endpoint functions
as well as underlying network topologies encapsulated in user-defined
scenarios

In order to accurately simulate the performance of service chains in a given
scenario, PerfSim requires to have performance models of each and every active
endpoint function within running services in the chain. To introduce such
performance models in PerfSim, the user can either provide a pre-defined model
file, or run a new modelling procedure. In the latter case, we proposed a
systematic performance testing and modeling approach to extract the KPIs of
endpoint functions, construct aforementioned modeling elements, and identify
each equipment’s resource capacities in the simulation. Once such performance
models being extracted for an endpoint function, the models can be re-used for
simulating various types of user-defined scenarios without any need for a new
profiling phase.

As presented in Figure 1, the modeling process starts by placing microservices
of all service chains on a set of reference hosts in the Performance Testing
Environment (PTE). Then, one by one the microservices get isolated on a single
host to start stressing each of its endpoint functions by flowing a single
request through the function, and in parallel, an automated script captures
various performance traces and resource utilization measurements and stores
the correlated traces it in a separate database.

While running the network traffic, various network tracing tools would be used
to identify the connections between microservices and identify service chains
within the cloud native system. For example, a service mesh layer based on
istio [istio], enables distributed tracing capabilities through Envoy [envoy]
which “allows developers to obtain visualizations of call flows in large
service oriented architectures” by taking advantage of tracing tools such as
LightStep[lightstep], Zipkin[zipkin], and Jaeger [jaeger]. Leveraging a
service mesh layer allows PerfSim to extract service chain flow models which
facilitates the modeling procedure. However, these models can also be provided
manually via PerfSim’s JSON model files or dynamic control objects.

After completing the profiling phase for all endpoint functions, a similar
procedure can optionally be repeated with all the target network equipments,
such as routers and NICs, using network performance measurement tools such as
iperf. The intention is to separately measure available egress/ingress
bandwidths of each network equipment and links latency to effectively simulate
the network congestion.

Finally, based on these extracted models, various user-defined scenarios can
be specified by the user. These scenarios includes resource allocation
policies, affinity rulesets, placemnent conigurations and algorithm,
equipments used in a cluster (i.e., active hosts and router), service chains,
incoming traffic scenarios, and underlying network topology. To start
simulating the given scenario, all the aforementioned models and simulation
parameters can be fed into PerfSim using a JSON model file or a Python script
(i.e. dynamic control object). We will cover the details of defining a
scenario in section 3.3.1.

###  3.3 System Architecture

Figure 2 presents the layered architecture of PerfSim. We employed a multi-
tier and object-oriented approach to architect PerfSim: (1) The presentation
layer (client), (2) business layer (PerfSim’s core), and (3) data layer
(results db).

Figure 2: Software architecture of PerfSim

####  3.3.1 Presentation layer: defining scenarios

To retrieve simulated performance insights using PerfSim, a scenario should be
specified for the simulator.

In the presentation layer, PerfSim user defines the simulation scenarios
and/or provides the control object. The user can provide the scenario in 3
general ways:

  * •

Using a JSON file for static simulations

  * •

Using a perfsim.Cluster object for dynamic simulations

  * •

Using the GUI for quick experimentation

A scenario’s structure in PerfSim is as follows:

  1. 1.

Prototypes define the model of all microservices, endpoint function, threads,
hosts, routers, links and traffics.

⬇

"prototypes": {

"microservices":
{{$\smash{\forall{C_{l}}\\!\in{\\!C}\;\forall{\;{}^{l}\\!S_{i}\\!\in{\\!{}^{l}\\!S}}\;\forall{{}^{l}\\!f_{n}^{i}\\!\in{\\!{}^{l}\\!F_{i}}}\rightarrow}$

"$\smash{\color[rgb]{0,0,1}{}^{l}\\!f_{n}^{i}}$":
[$\smash{\forall{t_{m}\in{{}^{l}\\!f_{n}^{i}}}\rightarrow}$

[$\smash{\color[rgb]{0.453125,0.16015625,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.453125,0.16015625,0.0078125}t_{m}^{\text{inst}},t_{m}^{\text{CPU}},t_{m}^{\text{maccs}},t_{m}^{\text{crefs}},t_{m}^{\text{cmiss}},t_{m}^{\text{cpenalty}},t_{m}^{\text{blk
rw}}}$]]}},

"hosts": {$\smash{\forall}$ host types $\rightarrow$

"{type_name}":
[$\smash{\color[rgb]{0.453125,0.16015625,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.453125,0.16015625,0.0078125}h^{\text{cores}},h^{\text{clock}},}${$\smash{\color[rgb]{0.453125,0.16015625,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.453125,0.16015625,0.0078125}\hat{V}_{H}(r^{H},*)\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}|r^{H}\in{R^{H}}}$}]},

"routers": {$\smash{\forall}$ router types$\rightarrow$

"{type_name}":
[$\smash{\color[rgb]{0.453125,0.16015625,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.453125,0.16015625,0.0078125}\rho^{\text{lat}},\rho^{\text{in
bw}},\rho^{\text{out bw}}}$]},

"links": {$\smash{\forall}$ link types$\rightarrow$

"{type_name}":
[$\smash{\color[rgb]{0.453125,0.16015625,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.453125,0.16015625,0.0078125}l^{\text{lat}}}$]},

"traffics": {$\smash{\forall}$ traffic types$\rightarrow$

"{type_name}":
[$\smash{\color[rgb]{0.453125,0.16015625,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.453125,0.16015625,0.0078125}C^{\text{rate}},C^{\text{duration}},C^{\text{batch}}}$]}}

Listing 1: Prototypes JSON object in the scenario file

  2. 2.

Equipments define the hosts and routers that are going to be used in the
cluster scenarios. These equipments should be created based on the defined
”prototypes”.

⬇

"equipments": {

"hosts": {$\smash{\forall{h_{k}\in{H}}\rightarrow}$
"$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}h_{k}$":
"{host_type_name}"},

"routers": {$\smash{\forall{\rho_{z}\in{P}}\rightarrow}$
"$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\rho_{z}$":
"{router_type_name}"}

Listing 2: The JSON object defining hosts and routers

  3. 3.

Topologies define the network topologies that are going to be used in the
cluster scenarios.

⬇

"topologies": {$\smash{\forall}$ topologies and links$\rightarrow$

"{topology_name}": {"nodes":{$\smash{P\cup{H}}$}, "edges":{$\smash{L}$}}}

Listing 3: Defining network topologies and hosts links

  4. 4.

Service chains define the chain of microsrevices as a graph (nodes and edges)
including all link payloads.

⬇

"sfcs":{$\smash{\forall{C_{l}\in{C}}\rightarrow}$"$\smash{C_{l}}$":
{"nodes":{$\smash{\\!\\!\\!~{}^{l}\\!F}$},"edges":{$\smash{\\!\\!\\!~{}^{l}\\!E}$}}}

Listing 4: Defining service chains graph $G(C_{l})$

  5. 5.

Resource allocation scenarios consists of resource policy templates that later
on can be assigned to each replica in a cluster scenario.

⬇

"res_alloc_scenarios": {$\smash{\forall}$ res. alloc.
scenario$\smash{\rightarrow}$

"{res_scenario_name}":
{$\smash{\forall{r^{S}\in{R^{S}}}\\!\\!\rightarrow}$"$\smash{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r^{S}}$":
$\smash{\color[rgb]{0.453125,0.16015625,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.453125,0.16015625,0.0078125}\hat{V}_{S}(r^{S}\\!,*)}$}}

Listing 5: Defining resource allocation scenarios

  6. 6.

Placement scenarios define the algorithm, weights and configuration of the
container scheduler. By default, PerfSim uses the Least Allocated placement
algorithm.

⬇

"placement_scenarios": {$\smash{\forall}$ placement scenario$\rightarrow$

"{placement_scenario_name}":

"algorithm": "{algorithm_name}",

"options": {e.g., $\smash{\forall{r^{H}\in{R^{H}}}}\rightarrow$
"$\smash{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r^{H}}$":
$\smash{\color[rgb]{0.453125,0.16015625,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.453125,0.16015625,0.0078125}W^{r^{H}}}$}}

Listing 6: Placement algorithms and related options

  7. 7.

Affinity rule-sets define the affinity/anti-affinity ruleset scenarios that
can be used in the cluster scenario.

⬇

"affinity_rulesets": {$\smash{\forall}$ affinity ruleset$\rightarrow$

"{affinity_set_name}": {

"affinity": [$\smash{\forall{S_{i}\in{S}}\rightarrow{A_{S_{i}}}}$],

"anti-affinity":
[$\smash{\forall{S_{i}\in{S}}\rightarrow{\widetilde{A}_{S_{i}}}}$]}}

Listing 7: Rulesets containing affinity/anti-affinity rules

  8. 8.

Cluster scenario defines ultimate cluster scenarios and consists of a
combination of all aforementioned sections, as well as additional
configuration to define number of replicas for each service and network
timeouts.

⬇

"cluster_scenarios": {$\smash{\forall}$ cluster scenario$\rightarrow$

"{scenario_name}": {

"service_chains":{$\smash{\forall{C_{l}\in{C}}\rightarrow}$

"$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}C_{l}$": {

"traffic_type": "{traffic_type_name}",

"nodes_settings": {$\smash{\forall{S_{i}\in{S}}\rightarrow}$

"$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S_{i}$": {

"replica_count":
$\color[rgb]{0.453125,0.16015625,0.0078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.453125,0.16015625,0.0078125}|S_{i}|$,

"res_scenario": "{res_scenario_name}"}}}},

"placement_scenario": "{placement_scenario_name}",

"topology": "{topology_name}"}}

Listing 8: The ultimate simulation scenarios object

Similar to static JSON-based scenarios, a user can define the ScenarioManager
object in pure Python and provide the control object to PerfSim to start the
simulation. As shown in Listing 1, since the JSON-based scenario is human-
readable, a PerfSim user can easily modify scenarios and/or add new ones as
needed. Moreover, a user can define and simulate various types of scenarios
without any need for performance trace logs or profiling data. The
aforementioned scenarios can be provided based on either extracted performance
models mentioned in the previous section or based on user-defined models. A
PerfSim user can then retrieve simulated insights of the final performance of
the system in the given scenario.

####  3.3.2 Business and data layers

In the business layer, PerfSim creates all necessary objects to perform the
simulation. The details of modeling and simulation in PerfSim is covered in
the next section.

After performing the simulation, the extracting performance simulation resutls
will be saved in a database. The user can choose between saving the result in
(1) a JSON file or (2) store it in a database (e.g., neptune.ai or MySQL).

1

2

3function  _filter_hosts ($\hat{s}_{j}^{i}$)_

4 $A^{\prime}_{S}\leftarrow{x\text{ in }A_{S_{i}}[x]\text{ if
}A_{S_{i}}[x]\text{=}1}$

5 $\widetilde{A}^{\prime}_{S}\leftarrow{x\text{ in
}\widetilde{A}_{S_{i}}[x]\text{ if }\widetilde{A}_{S_{i}}[x]\text{=}1}$

6 $H^{\hat{s}_{j}^{i}}\leftarrow{\text{ if }A^{\prime}_{S}=\emptyset\text{
then }[]\text{ else }H}$

7 foreach  _$S^{\prime}\in{A^{\prime}_{S}}$_

8 foreach  _$s^{\prime}\in{S^{\prime}}$_

9 $H^{\hat{s}_{j}^{i}}$.push($\Pi(s^{\prime})$)

10

11

12 foreach  _$\hbox to0.0pt{\hskip
0.51874pt\leavevmode\hbox{$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{$S$}}^{\prime}\in{\widetilde{A}^{\prime}_{S}}$_

13 foreach  _$\hskip 0.39063pt\hbox
to0.0pt{\leavevmode\hbox{$s$}\hss}{\hskip-0.39063pt\leavevmode\hbox{$\overline{\hbox{}}$}}^{\prime}\in{\hbox
to0.0pt{\hskip
0.51874pt\leavevmode\hbox{$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{$S$}}^{\prime}}$_

14 $H^{\hat{s}_{j}^{i}}$.pop($\Pi(\hskip 0.39063pt\hbox
to0.0pt{\leavevmode\hbox{$s$}\hss}{\hskip-0.39063pt\leavevmode\hbox{$\overline{\hbox{}}$}}^{\prime})$)

15

16

17 foreach  _$h_{k}\in{H^{\prime}}$_

18 foreach  _$(r^{S},r^{H})\in{R:R^{S}\rightarrow{R^{H}}}$_

19 if  _$V_{S}(r^{S},\hat{s}_{j}^{i}) >V_{H}(r^{H},h_{k})$_

20 $H^{\hat{s}_{j}^{i}}.\text{pop}(h_{k})$

21

22

23 $\textbf{return }H^{\hat{s}_{j}^{i}}$

24

25function  _score ($\hat{s}_{j}^{i}$,$h_{k}$)_

26
$\psi^{\text{min}}\leftarrow{0},\psi^{\text{max}}\leftarrow{100},\psi_{\hat{s}_{j}^{i}}^{h_{k}}\leftarrow{\text{based
on Eq. \ref{eq:score}}}$

27 $\textbf{return }\psi_{\hat{s}_{j}^{i}}^{h_{k}}$

28

29function  _place ($\hat{s}_{j}^{i}$,$h_{k}$)_

30 update_values($\Pi,V_{H},V_{S}$)

31

32function  _schedule ()_

33 foreach  _$\hat{s}_{j}^{i}\in{Q}$_

34 $H^{\hat{s}_{j}^{i}}\leftarrow{\text{filter\\_hosts}(\hat{s}_{j}^{i})}$

35 if  _$H^{\hat{s}_{j}^{i}}=\emptyset$_

36 $Q.$pop$(\hat{s}_{j}^{i})$.push($\hat{s}_{j}^{i}$)

37 $h^{*}\leftarrow{\text{first }h\in{H^{\hat{s}_{j}^{i}}}},\hbox
to0.0pt{\hskip
0.43124pt\leavevmode\hbox{$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{$\psi$}}_{\hat{s}_{j}^{i}}^{h_{k}}\leftarrow{\text{score(}\hat{s}_{j}^{i},h^{*}\text{)}}$

38 foreach  _$h_{k}\in{H^{\hat{s}_{j}^{i}}}$_

39

40 if  _$\hbox to0.0pt{\hskip
0.43124pt\leavevmode\hbox{$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{$\psi$}}_{\hat{s}_{j}^{i}}^{h_{k}}$
>$\text{score}(\hat{s}_{j}^{i},h_{k})$_

41 $h_{\hat{s}_{j}^{i}}^{*}\leftarrow{\nth{1}\text{
}h\in{H^{\hat{s}_{j}^{i}}}},\hbox to0.0pt{\hskip
0.43124pt\leavevmode\hbox{$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{$\psi$}}_{\hat{s}_{j}^{i}}^{h_{k}}\leftarrow{\text{
score(}\hat{s}_{j}^{i},h_{\hat{s}_{j}^{i}}^{*}\text{)}}$

42

43

44 place($\hat{s}_{j}^{i},h_{\hat{s}_{j}^{i}}^{*}$)

45 $Q.$pop($S_{j}^{i}$)

46

Algorithm 1 Simplified placement of service replicas among several hosts in a
cluster

##  4 Placement, Chaining and Routing of Services over the Cluster

In PerfSim, the first step towards approximating the performance of service
chains in a user-defined scenario is to place replicas on a cluster of hosts.
After the placement, PerfSim simulates the traffic scenario by first
processing the defined service chain flow graphs, identifying parallel
subchains, and extracting the exact route between service replicas based on
the given network topology $\tau$.

###  4.1 Placement of service replicas on the cluster

By default, we implemented a simplified version of the Least Allocated bin
packing algorithm for the placement of service replicas, partially imitating
the Kubernetes scheduler’s placement strategy. The key idea behind this
strategy is to ensure that replicas are placed on hosts with adequate
resources and balance out the resource utilization of hosts. It consists of
four steps: (1) enqueuing replicas, (2) filtering hosts, (3) scoring hosts,
and (4) placement of the replica on the host. All these steps are managed by a
schedule procedure. Algorithm 1 represents each of these steps and Figure 3
represents an example of such final placement.

Figure 3: An example placement of replicas over multiple hosts connected to a
network with topology $\tau$

####  4.1.1 Enqueuing replicas

Replicas are being placed one after the other. When a service requests for
scheduling a replica on the cluster, scheduler adds that request to a queue
(denoted as $Q$ in Algorithm 1) and then attempts to find a suitable host for
placing it.

$Q=\\{\hat{s}_{j}^{i}|\hat{s}_{j}^{i}\in{S_{i}}\in{S}\\}$ (2)

####  4.1.2 Filtering hosts

Considering all affinity/anti-affinity rules as well as re-source constraints
of the service replica, the scheduler needs to filter out all the hosts that
matches the specified limitations by the service. The filtered nodes, denoted
as $H^{\hat{s}_{j}^{i}}$, are potentially eligible to host the replica
$\hat{s}_{j}^{i}\in{S_{i}}$.

$H^{\hat{s}_{j}^{i}}\text{=}\\{h_{k}|\texttt{filter}\text{\\_}\texttt{hosts}(\hat{s}_{j}^{i})\\}$
(3)

####  4.1.3 Scoring hosts

In the Least Allocated bin packing strategy, in order to fairly distribute a
replica $\hat{s}_{j}^{i}$ among several hosts in a cluster, all eligible hosts
in the $H^{\hat{s}_{j}^{i}}$ are scored based on the request to capacity ratio
of primary resources $r^{S}\in{R^{S}}$ and $r^{H}\in{R^{H}}$ considering the
weight of each resource denoted as $W^{r^{H}}$. The score
$\psi_{\hat{s}_{j}^{i}}^{h_{k}}$ for each host $h_{k}$ related to a replica
$\hat{s}_{j}^{i}$ are between $\psi^{\text{min}}$ and $\psi^{\text{max}}$ are
calculated as follows:

$\psi_{\hat{s}_{j}^{i}}^{h_{k}}=\frac{\psi^{\text{max}}{{{\sum}}}\limits_{\scalebox{0.5}{$(r^{S},r^{H})\in{R}$}}{\bigg{(}1-\big{(}\frac{V_{H}(r^{H},h_{k})-V_{S}(r^{S},\hat{s}_{j}^{i})}{{\hat{V}_{H}(r^{H},h_{k})}}\Big{)}\bigg{)}{W^{r^{H}}}}}{{\sum}\limits_{{r}^{H}\in{R^{H}}}{W^{r^{H}}}}$
(4)

####  4.1.4 Placement of replicas

After calculating the score of all eligible nodes for hosting replica
$\hat{s}_{j}^{i}$, the host $h_{\hat{s}_{j}^{i}}^{*}$ with the lowest score
will be selected:

$h_{\hat{s}_{j}^{i}}^{*}=\Big{\\{}h^{*}\in{H^{\hat{s}_{j}^{i}}}\big{|}\psi_{\hat{s}_{j}^{i}}^{h^{*}}=\text{max}\big{\\{}\psi_{\hat{s}_{j}^{i}}^{h_{k}}|\forall{h_{k}\in{H^{\hat{s}_{j}^{i}}}}\big{\\}}\Big{\\}}$
(5)

###  4.2 Service chain flow graphs

A network flow graph $G(C_{l})=(\\!\\!~{}^{l}\\!S,\\!\\!~{}^{l}\\!E)$ of
service chain $C_{l}$ is a directed ordered graph that can have any form, from
a

Figure 4: Forming alternative graph $G^{\prime}$ and flow graph
$G^{\prime\prime}$

simple tree-like service chain to a complex multi-degree cyclic
multigraph. To efficiently simulate these service chains, we should be able to
estimate the processing time of each service replica
$\\!\\!~{}^{l}\\!\hat{s}_{j}^{i}\in{\\!\\!~{}^{l}\\!S_{i}}\in{\\!\\!~{}^{l}\\!S}\subseteq{S}$,
and then considering the outgoing request payload and network congestion,
estimate the network transfer time between two services
$(\\!\\!~{}^{l}\\!S_{i},\\!\\!\\!\\!~{}^{l}\\!S_{i^{\prime}})\in{\\!\\!~{}^{l}\\!E}$.
To accomplish these tasks, we should first identify the exact execution order
of service requests.

In any given service chain $C_{l}$, there might be subchains that run in
parallel and their execution order are entirely depends on their execution
time; this in turn depends on a vast range of parameters, starting from the
processing power of the host to allocated resources to each service.

To identify all subchains within a service chain flow graph $G(C_{l})$, we
first form an alternative graph
$G^{\prime}(C_{l})=(\\!\\!~{}^{l}\\!S^{\prime},\\!\\!~{}^{l}\\!E^{\prime},\\!\\!~{}^{l}\\!F)$
from the original graph $G(C_{l})$ in which every service
$\\!\\!~{}^{l}\\!S^{\prime}_{i}\in{\\!\\!~{}^{l}\\!S^{\prime}}$ is visited
only once. We form $G^{\prime}(C_{l})$ by duplicating services in
$\\!\\!~{}^{l}\\!S_{i}\in{\\!\\!~{}^{l}\\!S}$ that are visited more than once;
in other words, duplicate service nodes where has indegree of
$\delta^{-}(\\!\\!~{}^{l}\\!S^{\prime}_{i})\geq{2}$, and rerouting connecting
edges to newly generated nodes. Then, based on newly formed
$G^{\prime}(C_{l})$, we now identify all $n^{G^{\prime}(C_{l})}$ subchains in
$C_{l}$, denoted as
$\\{\\!\\!\\!~{}^{l}\\!c_{x}\\}_{x=1}^{n^{G^{\prime}(C_{l})}}$. Each subchain
$\\!\\!~{}^{l}\\!c_{x}$ has a flow subgraph
$G^{{}^{\prime\prime}}(\\!\\!~{}^{l}\\!c_{x})=(\\!\\!~{}^{l}\\!S^{\prime\prime}_{x},\\!\\!~{}^{l}\\!E^{\prime\prime}_{x},\\!\\!~{}^{l}\\!F^{\prime\prime}_{x})$
that has a source service, which is the first service of the subgraph, and a
sink service, which is the last service of the subgraph. In case a
$G^{{}^{\prime\prime}}(\\!\\!~{}^{l}\\!c_{x})$ has only one service, that
single service will be both source and sink node. We form each subgraph
$G^{{}^{\prime\prime}}(\\!\\!~{}^{l}\\!c_{x})$ of the subchain
$\\!\\!~{}^{l}\\!c_{x}$ by first identifying its source service. Starting from
the the very first source service
$\\!\\!~{}^{l}\\!S^{\prime}_{1}\in{\\!\\!~{}^{l}\\!S^{\prime}}$ that is
initiating first subchain $\\!\\!~{}^{l}\\!c_{1}$, when a service
$\\!\\!~{}^{l}\\!S^{\prime}_{i}\in{\\!\\!~{}^{l}\\!S^{\prime}}$ has an
outdegree of $\delta^{+}(\\!\\!~{}^{l}\\!S^{\prime}_{i})\geq{2}$, which means
it has more than one outgoing edges $\\{e^{\prime
l}_{y}=(\\!\\!~{}^{l}\\!S^{\prime}_{i},\\!\\!~{}^{l}\\!S^{\prime}_{x})\\}_{\in{\\!\\!~{}^{l}\\!E^{\prime}}}$,
then all immediate services $\\!\\!~{}^{l}\\!S^{\prime}_{x}$ will be marked as
source services and will initiate a new subchain. A subchain ends where we
meet a service node with an outdegree of
$\delta^{+}(\\!\\!~{}^{l}\\!S^{\prime}_{y})\neq 1$. A request
$\\!\\!~{}^{l}\\!u_{o}$ ends when all sink service nodes conclude their
executions.

As an example, Figure 4 demonstrates all aforementioned steps. In subfigure
(a), we see an example flow graph $G(C_{l})$ of service chain $C_{l}$ with all
its services $\\!\\!~{}^{l}\\!S$ (circles) and their containing service
replicas (cubes) together with all edges $\\!\\!~{}^{l}\\!E$ connecting
services together (arrows) with the source service node $S_{1}^{l}$. In this
graph, we see node $S_{3}^{l}$ initiate two parallel subchains and has a
indegree $\delta^{-}(S_{3}^{l})=2$. Also, $S_{6}^{l}$ forms a cycle with
$S_{7}^{l}$ with indegree $\delta^{-}(S_{6}^{l})=3$. In the second subgraph
(b), we form the alternative graph $G^{\prime}(C_{l})$ by duplicating
$S_{3}^{l}$ and $S_{6}^{l}$ and rerouting connected edges $e_{l,6}$,
$e_{l,8}$, and $e_{l,10}$. In subfigure (c), we identify all
$n^{G^{\prime}(C_{l})}=5$ subchains $\\{\\!\\!~{}^{l}\\!c_{x}\\}_{x=1}^{5}$
and form $\\{G^{\prime\prime}(\\!\\!~{}^{l}\\!c_{x})\\}_{x=1}^{5}$.

###  4.3 Routing requests

When a subchain $\\!\\!~{}^{l}\\!c_{x}$ of a service chain $C_{l}$ receives a
user request $\\!\\!~{}^{l}\\!u_{o}\in{{}^{l}{U}}$, based on the
$G^{\prime\prime}(\\!\\!~{}^{l}\\!c_{x})$, it’ll be routed to one of the
service replicas of the source service $\\!\\!~{}^{l}\\!S^{\prime\prime
x}_{1}\in{\\!\\!~{}^{l}\\!S^{\prime\prime
x}}\subseteq{\\!\\!~{}^{l}\\!S}\subseteq{S}$ that is chosen based on a round-
robin load balancing algorithm (neglecting the session affinity possibility).
If the chosen replica $\hat{s}_{j}^{1}\in{\\!\\!~{}^{l}\\!S^{\prime\prime
x}_{1}}$ is either placed in the same host as the requester’s service replica
or if $\\!\\!~{}^{l}\\!S^{\prime\prime x}_{1}$ is the source service replica
$S_{1}^{l}\in{\\!\\!~{}^{l}\\!S}$ of the service chain $C_{l}$, then, assuming
$\\!\\!~{}^{l}\\!S^{\prime\prime x}_{1}$ is not a sink service, after the
request is being process in the $s^{\prime\prime 1}_{j}$, it will simply get
routed to the next replica inside the same host. But in case the next replica
is not in the same host, then it needs to get routed to the destination
replica based on the network topology graph $G(\tau)$.

$\rho_{6}$$h_{10}$$\hat{s}^{1}_{1}$$\rho_{1}$$\rho_{4}$$\rho_{5}$$h_{8}$$\hat{s}^{2}_{1}$

Figure 5: Routing a request among replicas over a network

Considering $G(\tau)$ is a directed acyclic graph and there should be one-and-
only-one active path carrying information from a source to destination in a
network, we extract the path between all pairs of hosts and form a set of
$\binom{|H|}{2}$ subgraphs denoted as
$\\{G(\tau)_{h_{a},h_{b}}=(P_{h_{a},h_{b}},L_{h_{a},h_{b}})\\}_{h_{a},h_{b}\in{H}}$
where $P_{h_{a},h_{b}}$ is a set of routers between $h_{a}$ and $h_{b}$ that
are connected using $L_{h_{a},h_{b}}$ links. As an example in Figure 3, we
have eleven hosts $H=\\{h_{1},\dots,h_{11}\\}$ that are connected together
using six routers $P=\\{\rho_{1},\dots,\rho_{6}\\}$ with a tree topology
$\tau$ and network topology graph $G(\tau)$. Figure 5 represents the path from
$\hat{s}_{1}^{1}$ to $\hat{s}_{1}^{2}$ based on the network topology $\tau$
represented in Figure 3.

##  5 Approximating execution time of threads in a multi-core host

The next step after identifying and deploying service chains and network
routers is to estimate the execution time of each endpoint function
$\\!\\!~{}^{l}\\!f_{n}^{i}\in{\\!\\!~{}^{l}\\!F_{l}}\subseteq{\\!\\!~{}^{l}\\!F}$
when a request arrives alongside other running processes in a host. In each
cluster scenario, there exist a set of service replicas that each of them are
capable of running a set of endpoint functions. When a request arrives, an
endpoint function may propagate a few threads during its execution and each of
its threads, when load-balances on a core’s runqueue, may perform a few
different tasks at a time. To be precise, a thread may perform one of the
following tasks at any given time:

  * •

Execute a CPU intensive task on the processor

  * •

Read/write bytes of data from/to memory/cache

  * •

Read/Write a file from/to storage

  * •

Send/receive packets of information over the network

  * •

Be in the idle mode

Additionally, other running threads inside a host have direct influence on the
CPU time of an application because of the CPU scheduling mechanism in the
operating system. For instance, Linux’s CFS load-balance threads over dozens
of CPU runqueues based on their load, CPU share, CPU quota and other
parameters. Moreover, a typical multithreaded service have a main thread and a
number of worker threads that coordinate with each other through
synchronization primitives, that results additional overhead on execution time
[8401866].

Even though predicting the exact execution time of a thread in a host can be
very complex due to the aforementioned complexities, and considering that
cycle-level simulation of multi-threaded services can be a very time-consuming
procedure, we can predict a rough approximation of its run time by properly
categorize type of running tasks in a host and approximate the execution time
of each task by considering each thread’s parent cgroups’ resource constraints
as well as other parallel active threads in the host. Consequently, this
approximation may neglects a few performance factors such as microarchitecture
dependent variable (i.e.,CPU instruction sets and CPU architecture). However,
during the modeling phase in a reference PTE, these effects will be measured
and considered in the model, and therefore they contribute to the final
approximation.

To approximate the total execution time of a thread, we categorize its tasks
into 3 main types and accumulate measured values:

  1. 1.

Accumulated CPU instructions to be executed

  2. 2.

Accumulated stall cycles due to cache misses, memory access or block I/O

  3. 3.

Payload to be sent to the next service over the network

###  5.1 Load-balancing of Threads over CPU runqueues

The first thing before being able to approximate the execution time of threads
on a multi-core hardware, we need to estimate threads placement in a set of
active CPU cores. This is crucial for the estimation, as the execution time is
directly being affected by the other running threads in a core’s runqueue.
Therefore, we implemented a simplified version of Linux’s CFS load-balancing
algorithm [10.1145/2901318.2901326] in PerfSim. We presented the details of
our implementation in Algorithm 2. For simplicity, we assume there are only
one NUMA node (one CPU socket with multiple cores/runqueues in it).

1

2 sched_domains = $(\text{NUMA},\text{pairs})$

3sched_groups[NUMA][0] = $\\{\text{core}\\}_{\text{core}\in{h_{k}}}$

4sched_groups[pairs] = $\\{\\{(\nth{1}\text{core in pair},\nth{2}\text{core in
pair}\\}_{\text{core}\in{\text{core pairs}}}\\}_{\text{core pairs}\in{h_{k}}}$

5function  _load_balance_threads ($h_{k}$)_

6

7 foreach  _$\text{current\\_core}\in{\\{1\dots h_{k}^{\text{cores}}\\}}$_

8

9 foreach  _$\text{sd}\in{\\{\text{sched\\_domains}\\}}$_

10

11 $\text{first\\_core}\leftarrow{\texttt{first\\_idle\\_core}(sd)}$

12 if  _$\text{first\\_core}=\emptyset$_

13 $\text{first\\_core}\leftarrow{\texttt{first\\_core}(sd)}$

14 if  _first_core = current_core_

15 continue

16

17 foreach  _$\text{sched\\_group}\in{\text{sd}}$_

18 sched_group.load= avg($t_{m}^{\text{load}}\in{\text{sched\\_group}}$)

19

20 current_sg= current_sched_group(current_core)

21 bussiest_sg=bussiest_sched_group()

22 if  _bussiest_sg.load $>$ current_sg.load_

23 do

24 bussiest_core= bussiest_sg.next_bussiest_core()

25 load_balance(current_core,bussiest_core)

26

27 while  _load balance was not successful_

28

29

30

Algorithm 2 Simplified CFS load-balancing algorithm in a host $h_{k}$

The CFS balances cores runqueues based on their load which is a measure that
is a combination of threads accumulated weights (CPU shares) and average CPU
utilization. To estimated weight of a thread $t_{m}\in{f_{n}^{i}}$ on a core,
we first divide CPU shares of its parent service $S_{i}\in{\\!\\!~{}^{l}\\!S}$
with total number of its running threads, and then divide the result with sum
of all CPU shares currently running on the core:

$t_{m}^{\text{share}}=\frac{S_{i}^{\text{CPU share}}}{|f_{n}^{i}|}$ (6)

Assuming $\hat{f}_{h_{k}}$ is the set of running threads placed on $h_{k}$:

$\forall
t_{m}\in{\hat{f}_{h_{k}}}\rightarrow{}t_{m}^{\text{weight}}=\frac{t_{m}^{\text{share}}}{\sum\limits_{t_{j}\in{\hat{f}_{h_{k}}}}{\\!\\!\\!\\!t_{j}^{\text{share}}}}$
(7)

To calculate load of a thread:

$t_{m}^{\text{load}}=\frac{t_{m}^{\text{runnable
sum}}\times{t_{m}^{\text{weight}}}}{t_{m}^{\text{runnable period}}}$ (8)

In which, $t_{m}^{\text{runnable sum}}$ is the amount of time that the thread
was runnable and $t_{m}^{\text{runnable period}}$ is the total time that the
thread could potentially be running.

Additionally, the load-balancing procedure takes place by considering cache
locality and its hierarchical levels called scheduling domains. Within each
scheduling domain, load-balancing occurs between a set of cores, called
scheduling groups. Since we assumed there is only one CPU socket in each host,
there exist only two scheduling domains: NUMA node level and core-pair level.
Algorithm 2 represents our simplified version of the CFS algorithm used in
PerfSim.

###  5.2 Approximating CPU time

Here we explain PerfSim’s approach towards approximating CPU time of threads
when co-located in a host.

####  5.2.1 Calculating auxiliary CPU share of a thread

When a thread co-locates with other threads on a multi-core machine, its
execution time may be affected by the threads on the runqueue. Since we do not
intend to simulate CPU time in a cycle-by-cycle basis, we approximate the
effect of CPU bandwidth and CPU quota of threads by first defining an
auxiliary CPU share for each thread, denoted as $t_{m}^{\text{share ratio}}$.
For simplicity, we assume threads run in either (1) the Best Effort mode,
which implies there is no CPU quota and CPU bandwidth defined, or (2) in the
Guaranteed mode where CPU shares are fixed and guaranteed. For every threads
in a runqueue, we calculate $t_{m}^{\text{share ratio}}\in(0,1024]$ as
follows:

$\forall{t_{m}}\in{\hat{f}_{h_{k}}}\text{ s.t.
}t_{m}\in{f_{n}^{i}}\rightarrow{}\\\ t_{m}^{\text{share
ratio}}=\begin{cases}\frac{t_{m}^{\text{share}}\times{1024}}{\sum\limits_{t_{j}\in{\hat{f}_{h_{k}}}}{\\!\\!\\!\\!t_{j}^{\text{share}}}}&\text{
if }S_{i}^{\text{CPU quota}}\text{=}0\\\
t_{m}^{\text{share}}&\parbox{71.13188pt}{elif $t_{m}^{\text{share}}\leq
1024$}\\\ 1024&\parbox{71.13188pt}{elif
$t_{m}^{\text{share}}>1024$}\end{cases}$ (9)

####  5.2.2 Approximating cache miss rate based on cache stores and CPU size

The cache miss rate of a single thread can get affected by various hardware
dependent factors such as:

  * •

CPU L1, L2, and Last Level Cache (LLC) sizes

  * •

Support of CPU Cache Allocation Technology (CAT) allowing software control
over LLC allocation per process

  * •

microarchiture-level details

The cache miss rate may also get affected by following significant software
dependant factors:

  * •

Allocated CPU size of process

  * •

Memory access rate of co-located threads in runqueue

Since the focus of PerfSim was to model the performance of microservices in
merely software-oriented scenarios, such as container’s placement,
container/host affinity/anti-affinity, and resource allocation policies, we
assumed a fairly similar microarchitecture and cache implementation details
between the CPUs of PTE and the PE.

Hence, during the performance modeling phase, the effect of both (1) CPU size
and (2) memory access rate (store/loads) of co-located threads is measured and
a logarithmic regression model is being trained to predict the excessive cache
miss rate of each thread. We denote the first effect on $t_{m}\in{f_{n}^{i}}$
as $t_{m}^{\text{CMC}}$ and the second one as $t_{m}^{\text{CMT}}$.

$t_{m}^{\text{CMC}}\text{=}a\ln(\frac{S_{i}^{\text{CPU
limits}}}{|f_{n}^{i}|})+b$ (10)

$t_{m}^{\text{CMT}}\text{=}a\ln\Bigg(\hskip
20.0pt\mathop{\raisebox{-12.0001pt}{\scalebox{1.2}{$\displaystyle\sum$}}}_{\mathclap{\begin{subarray}{c}t_{j}\in\text{runqueue
of }t_{m}\end{subarray}}}t_{j}^{\text{maccs}}\hskip 8.0pt\Bigg{missing})+b$
(11)

We then apply these excessive penalties to the measured miss rate on the
reference PTE as follows:

$t_{m}^{\text{miss
rate}}=\frac{t_{m}^{\text{cmiss}}}{t_{m}^{\text{crefs}}}\times{(t_{m}^{\text{CMT}}+1)}\times{(t_{m}^{\text{CMC}}+1)}$
(12)

####  5.2.3 CPU time approximation

We used the CPU Performance Equation promoted in [patterson1990computer] to
approximate the CPU time of an isolated thread $t_{m}\in{f_{n}^{i}}$ on an
idle core (in the Best Effort mode):

$\text{Isolated CPU Time}(t_{m})=\\\
t_{m}^{\text{inst}}({t_{m}^{\text{CPI}}}+\frac{t_{m}^{\text{maccs}}}{t_{m}^{\text{inst}}}\times{t_{m}^{\text{miss
rate}}}\times{t_{m}^{\text{cpenalty}}})\times\frac{1}{h_{k}^{\text{clock}}}$
(13)

Considering that $t_{m}^{\text{inst}}$ is the accumulated number of
instructions that thread $t_{m}$ executes during its lifetime, it also
includes additional instructions that thread performs due to mem accesses,
cache misses, blkio r/w and net I/O.

$t_{m}^{\text{cycle
penalty}}=\frac{t_{m}^{\text{maccs}}}{t_{m}^{\text{inst}}}\times{t_{m}^{\text{miss
rate}}}\times{t_{m}^{\text{cpenalty}}}$ (14)

${}^{\hat{t}}t_{m}^{\text{relative
share}}=\frac{t_{m}^{\text{CPI}}\times{{}^{\hat{t}}t_{m}^{\text{share
ratio}}}}{t_{m}^{\text{CPI}}+t_{m}^{\text{cycle penalty}}}$ (15)

Assuming ${}^{\hat{t}}t_{m}^{\text{inst}}$ is the remaining instructions at
any given time $\hat{t}$, we approximated the CPU time of a thread on a CPU
runqueue at any given time as follows:

${}^{\hat{t}}t_{m}^{\text{CPU
time}}=\frac{{}^{\hat{t}}t_{m}^{\text{inst}}\times{t_{m}^{\text{CPI}}}\times{\frac{1}{h_{k}^{\text{clock}}}}}{{}^{\hat{t}}t_{m}^{\text{relative
share}}}$ (16)

Therefore, given a time period $\Delta{T}\geq{{}^{\hat{t}}t_{m}^{\text{CPU
time}}}$ (nanoseconds), we can estimate the executed instructions in that
period as follows:

${}^{\hat{t}+\Delta{T}}t_{m}^{\text{inst}}=^{\hat{t}}\\!\\!t_{m}^{\text{inst}}-\frac{\Delta{T}\times{{}^{\hat{t}}t_{m}^{\text{relative
share}}}}{t_{m}^{\text{CPI}}\times{\frac{1}{h_{k}^{\text{clock}}}}}$ (17)

###  5.3 Approximating the storage I/O time

Assuming a thread $t_{m}$ is placed on host $h_{k}$ with accumulated
reads/writes of $t_{m}^{\text{blk rw}}$, we can approximate its storage I/O
time as Equation 18.

$t_{m}^{\text{blkio time}}=\frac{t_{m}^{\text{blk rw}}}{h_{k}^{\text{blkio
bw}}}$ (18)

At any given time $\hat{t}$, the remaining blkio time is denoted by
${}^{\hat{t}}t_{m}^{\text{blkio time}}$.

###  5.4 Approximating execution time of a thread

As described in the previous section, the execution time of a thread consists
of the CPU time, blkio rw time and idle time. Therefore, given a time
$\hat{t}$, we can estimate the execution time of thread on a core’s runqueue
as follows:

${}^{\hat{t}}t_{m}^{\text{exe time}}=^{\hat{t}}\\!\\!t_{m}^{\text{CPU
time}}+^{\hat{t}}\\!\\!t_{m}^{\text{blkio
time}}+^{\hat{t}}\\!\\!t_{m}^{\text{idle time}}$ (19)

###  5.5 Approximating network transfer time

When a service replica
${}^{l}\\!{\hat{s}_{x}^{i}}\\!\in{\\!{}^{l}\\!S_{i}\in{\\!\\!~{}^{l}\\!S}}$
attempts to send $\\!\\!~{}^{l}\\!e_{v}^{\text{payload}}$ bytes of data to
another service replica
${}^{l}\\!{\hat{s}_{y}^{j}}\in{\\!{}^{l}\\!S_{j}\in{\\!\\!~{}^{l}\\!S}}$, they
are either placed on the same host and the network transfer time is equal to
zero, or they placed in two different hosts
$h_{a}=\Pi(^{l}\\!{\hat{s}_{x}^{i}})$ and
$h_{b}=\Pi(^{l}\\!{\hat{s}_{y}^{j}})$. In the latter case, a request needs to
traverse an ordered subgraph
$G(\tau)_{h_{a},h_{b}}=(N_{h_{a},h_{b}},L_{h_{a},h_{b}})$ where
$N_{h_{a},h_{b}}$ consist of both hosts $h_{a}$ and $h_{b}$ and all routers in
between them. Also, $L_{h_{a},h_{b}}$ is all the network links between two
hosts, including host links and topology links.

Depending on bandwidth usage of active requests flowing over a network link,
the available bandwidth of a link changes over time. We therefore, denote the
maximum available bandwidth of each link $l_{o}\in{L_{h_{a},h_{b}}}$ at any
give time $\hat{t}$ as $\theta(l_{o})_{\hat{t}}$ and calculate the maximum
available bandwidth between all links in $L_{h_{a},h_{b}}$ as follows:

$\Theta(L_{h_{a},h_{b}})_{\hat{t}}=\text{min}(\\{\theta(l_{o})\\}_{l_{o}\in{L_{h_{a},h_{b}}}})$
(20)

. We then for any given time $\hat{t}$, calculate the request bandwidth
between ${}^{l}\\!{\hat{s}_{x}^{i}}$ and ${}^{l}\\!{\hat{s}_{y}^{j}}$, denoted
as $\theta(^{l}\\!{\hat{s}_{x}^{i}},^{l}\\!{\hat{s}_{y}^{j}})_{\hat{t}}$, as
follows:

$\theta(^{l}\\!{\hat{s}_{x}^{i}},^{l}\\!{\hat{s}_{y}^{j}})_{\hat{t}}=\\\
\text{min}\bigg{(}\Theta(L_{h_{a},h_{b}})_{\hat{t}},V_{S}(\text{out
bw},^{l}\\!{\hat{s}_{x}^{i}}),V_{S}(\text{in
bw},^{l}\\!{\hat{s}_{y}^{j}})\bigg{)}$ (21)

To calculate the network time between 2 service replica
${}^{l}\\!{\hat{s}_{x}^{i}}$ and ${}^{l}\\!{\hat{s}_{y}^{j}}$, denoted as
$\omega(^{l}\\!{\hat{s}_{x}^{i}},^{l}\\!{\hat{s}_{y}^{j}})_{\hat{t}}$, we
calculate the transfer time by dividing the payload size with available
bandwidth, and then sum it up with routers and links latency as follows:

$\omega(^{l}\\!{\hat{s}_{x}^{i}},^{l}\\!{\hat{s}_{y}^{j}})_{\hat{t}}=\frac{{}^{\hat{t}}e_{v}^{\text{payload}}}{\theta(^{l}\\!{\hat{s}_{x}^{i}},^{l}\\!{\hat{s}_{y}^{j}})_{\hat{t}}}+\\!\\!\\!\sum_{\\!\\!\rho_{z}\in{P_{h_{a},h_{b}}}}\\!\rho_{z}^{\text{lat}}+\\!\\!\sum_{l_{o}\in{L_{h_{a},h_{b}}}}\\!\\!l_{o}^{\text{lat}}$
(22)

###  5.6 Putting all together: The simulation

During each iteration, PerfSim predicts the next event to simulate. We
categorized events into five main categories:

  * •

Request Generation simulates the incoming traffic to each service chain by
generating requests.

  * •

Threads Generation checks for new queued threads and generates them.

  * •

Threads Execution Time Estimation estimates the execution time of threads and
checks whether their execution is going to end before the next transmission
completes, or vice versa.

  * •

Threads Execution estimates consumed instructions in all threads and repeat
load-balancing among available cores in each host.

  * •

Network Transmissions: Estimates the remaining payload in each active
transmission in the network.

##  6 Simulation Accuracy Evaluation

In this section, we address the followings to highlight the accuracy, speed,
applicability and significance of PerfSim.

  1. 1.

Potential threats to evaluation validity (Section 6.2) to explain our approach
for ensuring evaluation validity.

  2. 2.

Performance modeling accuracy (Section 6.3) to reflect and report the
PerfSim’s simulation error using a comprehensive set of prevalent scenarios
(Table 6.3.1).

  3. 3.

Execution time of PerfSim prototype (Section 6.4) to report the amount of time
required to simulate each scenario using an early-stage prototype of PerfSim.

  4. 4.

Simulating large scale service chains (Section 6.5) to demonstrate the
applicability of PerfSim for simulating large-scale service chains.

  5. 5.

Challenges and limitations (Section 6.6) to highlight PerfSim’s practical
limitations as well as key challenges in simulating performance of computer
systems.

###  6.1 Experimental setup

Cluster setup. To evaluate the simulation error of service chains’ execution
time between PerfSim and the real setup, we deployed a Kubernetes cluster
using four physical machines (as compute nodes), and connected them through
one or more Netgear 10Gbps routers (depending on the topology). All our
servers are based on Intel Core i7 microarchitecture and their hardware
details specified in Table III. The latency of routers for processing a packet
is 7.3e5ns, and links latencies are 4.2e5ns.

Workload. To evaluate various scenarios described in this section, we used
sfc-stress [sfc-stress] that is a customizable synthetic service chain
benchmarking suit capable of generating different types of service chains with
various types of CPU/memory/blkio/storage intensive as well as user-defined
workloads. In sfc-stress, workloads are comparable to benchmark suites used
for microservices, such as DeathStarBench [10.1145/3297858.3304013]. They are
similar to real-world cloud native microservices in various ways, such as
capability of invoking any requested number of threads when their endpoint
function being called, REST API based, written in Node.js, cloud native,
deployable on both Kubernetes and Docker, fully parametric, and easily
customizable. Using sfc-stress provided us with the flexibility of easily
changing workloads type, size, threads count, execution duration, resource
allocation settings per service (both vertically and horizontally), and most
importantly design custom service chains and generate periodic automated
requested based on given arrival rate (request per second).

Simulation parameters. We used the pre-release prototype version (alpha-0.1)
of PerfSim for this evaluation. To drive the simulations, we first extracted
performance traces of various endpoint functions in sfc-stress and fed it to
PerfSim as the simulation’s initial parameters (Table III). We only set
$W^{\text{millicores}}$ and $W^{\text{mem}}$ to 1 and set other weights to 0
(similar to Kubernetes settings).

Placement of service replicas. We used Kubernetes default kube-scheduler with
weights specified in Table III to place and govern service replicas.

###  6.2 Potential threats to evaluation validity

As with any evaluation, potential threats exist to reduce its validity. We,
therefore, identified several of these threats before starting our evaluation
process and paid great attention to address them during our evaluation.

####  6.2.1 Evaluation consistency

During our initial experiments, we realized using only one experiment might
not be representative of the evaluation scenarios performance behaviour. Thus,
we repeated each experiment four times and calculated the average for each
data point. In the end, we calculated moving average for both simulated and
actual results as appropriate.

####  6.2.2 Procedural rigor

Collocating hosts in our testbed with other nodes in a cluster may introduce
additional noise to the system. Moreover, we realized connecting various hosts
to the same router may affect the performance of the network intensive
scenarios. To mitigate this problem and prevent any possible noise affecting
the experiments results, we isolated the entire testbed by locating hosts in a
separate rack and making sure no other hosts are connected to the routers.

We also noted that keeping energy saving options in the BIOS may slightly
affect the CPU performance by altering its clock frequency. To mitigate this
effect, we disabled energy saving options in the BIOS and optimizied it for
production.

####  6.2.3 Comprehensiveness of evaluation scenarios

Another threat to our evaluation was to neglect common scenarios used in
today’s systems. Nowadays a real distributed system may consist of different
type of services, each with various resource demands, workload sizes,
interconnections, and expected average traffic. Thus, to ensure the
comprehensiveness of our evaluation scenarios when studying the accuracy of
PerfSim, we designed 6 category of scenarios, each focusing on a distinct
aspect of PerfSim. These categories, as presented in Table 6.3.1, includes CPU
intensive, memory intensive, network intensive, scenarios with multiple
replicas, and scenarios with multiple endpoint functions per service.

###  6.3 Latency prediction accuracy

In this section, we evaluated the accuracy of PerfSim when simulating 104
different scenarios in 6 distinct category.

####  6.3.1 Evaluating distinctive classes of scenarios

We perform our evaluation by executing various workloads on our real
Kubernetes cluster for $\Delta\widehat{T}=60$ seconds and compared average
execution time of requests ($\overline{\\!\\!~{}^{l}\\!u_{o}^{\text{exe
time}}}$) with the ones computed using PerfSim. We summarized the simulation
error of all scenarios in Table 6.3.1 and illustrated the latency over
requests line graphs in Figure 8. We also illustrated the average latency
($\overline{\\!\\!~{}^{l}\\!u_{o}^{\text{exe time}}}$) of each scenario as a
bar graph in the same figure. We repeated each experiment four times to avoid
any unaccounted artifact.

Figure 6: Service chain scenarios
($\\!\\!~{}^{l}\\!e_{v}^{\text{payload}}$=50MB for all edges)

Each scenario has (1) a service chain as illustrated in Figure 6, (2) a
network topology as illustrated in Figure 7, (3) an arrival rate
$C_{l}^{\text{rate}}\frac{\text{req}}{s}$, and (4) a resource allocation
setting.

Figure 7: Network topologies used in the evaluation

In scenarios 1-20, our goal was to evaluate PerfSim simulation accuracy when
assigning different CPU sizes to a single CPU-intensive container. For
example, in scenario#1 we assigned 100 millicores to the only replica
available in $S_{1}$ and generated a traffic at a rate of 1
$\frac{\text{req}}{\text{s}}$ on $C_{1}$ and measured requests average
execution time ($\overline{\\!\\!~{}^{1}\\!u_{o}^{\text{exe time}}}$). We
repeat the exact same scenario using PerfSim and calculate the simulation
percentage error by comparing extracted
$\overline{\\!\\!~{}^{1}\\!u_{o}^{\text{exe time}}}$ in PerfSim with the one
measured in our real testbed.

TABLE III: Constant control parameters of hosts, routers, links and workloads
used in the evaluation

Hosts | $H$ | $h_{k}^{\text{clock}}$ | $h_{k}^{\text{cores}}$ | $h_{k}^{r^{H}}$
---|---|---|---|---
$h_{k}^{\text{millicores}}$ | $h_{k}^{\text{mem}}$ | $h_{k}^{\text{in bw}}$ | $h_{k}^{\text{out bw}}$ | $h_{k}^{\text{blkio bw}}$ | $h_{k}^{\text{blkio size}}$
$h_{1}$ $\smash{\vdots}$ $h_{4}$ |  1.59 GHz | 4 | 4000 |  16 GB |  1 Gbps |  1 Gbps |  657 MBps |  500 GB
| $S$ | Endpoint Functions
| $F$ | Threads
| $T$ | $t_{m}^{\text{inst}}$ | $t_{m}^{\text{cpi}}$ | $t_{m}^{\text{maccs}}$ | $t_{m}^{\text{crefs}}$ | $t_{m}^{\text{cmiss}}$ | $t_{m}^{\text{miss penalty}}$ | $t_{m}^{\text{blk rw}}$
|  | $f_{1}^{1}$ | $t_{1,1,1}$ | $1.4e9$ | 0.7432 | $3.1e8$ | $1.0e6$ | $1.0e5$ | 4 | $\epsilon$
|  | $f_{2}^{1}$ | $t_{1,2,1}$ | $3.1e9$ | 0.750 | $7.2e8$ | $1.2e6$ | $1.3e5$ | 4 | $\epsilon$
| $S_{1}$ | $t_{1,2,2}$ | $3.1e9$ | 0.715 | $6.6e8$ | $1.7e6$ | $2.2e5$ | 3 | $\epsilon$
|  | $f_{1}^{2}$ | $t_{2,1,1}$ | $1.7e9$ | $0.520$ | $3.4e8$ | $2.9e6$ | $2.0e6$ | 5 | $\epsilon$
| $S_{2}$ | $f_{2}^{2}$ | $t_{2,2,1}$ | $1.0e8$ | 0.4912 | $7.4e8$ | $5.5e6$ | $4.1e6$ | 5 | $\epsilon$
|  | $f_{1}^{3}$ | $t_{3,1,1}$ | $2.1e8$ | 0.6660 | $4.3e7$ | $1.5e6$ | $5.7e5$ | 5 | $5.1e7$
Services | $S_{3}$ | $f_{2}^{3}$ | $t_{3,2,1}$ | $5.1e8$ | 0.7199 | $2.2e7$ | $4.3e6$ | $2.3e6$ | 5 | $1.0e8$

In scenarios #2-19, we increase the CPU size by 100 millicores in each
scenario and repeat the same procedure; in scenario #20, we also evaluated the
case where all resources run in the best effort mode. In scenarios #21-40, we
repeated all aforementioned procedures but for the memory intensive workloads
(also implemented in the sfc-stress toolkit) to measure the accuracy of
PerfSim for simulating memory-intensive workloads. Similarly, in scenarios
#41-60, we focused on the disk-intensive workload.

To evaluate simulations involving networks and service chains, we designed
scenarios #61-80. In the first half of this category (scenarios #61-70), we
aimed to evaluate the accuracy of PerfSim when assigning egress bandwidth to
an outgoing service in service chain $C_{4}$ (Figure 6), and in the second
half (scenarios #71-80), our goal was to measure the accuracy when assigning
ingress bandwidth to the incoming node $S_{3}$. Scenarios #81-100 were
designed to measure the same effect but when the system is deployed in
slightly more complex network topology $\tau_{2}$ (Figure 7).

Scenario Type |  Experiment
Number | $C_{l}^{\text{rate}}$ ($\frac{\text{req}}{\text{s}}$) |  Target Resource Capacity | $\tau$ | $\overline{\\!\\!~{}^{l}\\!u_{o}^{\text{exe time}}}$ |  Avg. Error
---|---|---|---|---|---|---
PerfSim | Actual
CPU intensive | 1-19 | $C_{1}^{\text{rate}}$ = 1 |  $S_{1}^{\text{\footnotesize{}CPU requests}}$ = $\\{100k\\}_{k\leavevmode\resizebox{2.33333pt}{0.0pt}{=}{}1}^{19}$ | $\tau_{1}$ |  |  |
20 | $C_{1}^{\text{rate}}$ = 1 | Best Effort | $\tau_{1}$ | 38.23 | 36.42 | 1.237%
| 21-39 | $C_{2}^{\text{rate}}$ = 1 |  $S_{1}^{\text{\footnotesize{}CPU requests}}$ = $\\{100k\\}_{k\leavevmode\resizebox{2.33333pt}{0.0pt}{=}{}1}^{19}$ | $\tau_{1}$ |  |  |
Memory intensive | 40 | $C_{2}^{\text{rate}}$ = 1 | Best Effort | $\tau_{1}$ | 9.654 | 12.24 | 6.662%
Storage intensive | 41-59 | $C_{3}^{\text{rate}}$ = 1 |  $S_{3}^{\text{\footnotesize{}CPU requests}}$ = $\\{100k\\}_{k\leavevmode\resizebox{2.33333pt}{0.0pt}{=}{}1}^{19}$ | $\tau_{1}$ |  |  |
60 | $C_{3}^{\text{rate}}$ = 1 | Best Effort | $\tau_{1}$ | 1.877 | 4.144 | 19.27%
| 61-70 | $C_{4}^{\text{rate}}$ = 1 | $S_{1}^{\text{\footnotesize{}out bw}}\leavevmode\resizebox{3.33333pt}{0.0pt}{=}{}\\{100k\\}_{k\leavevmode\resizebox{2.33333pt}{0.0pt}{=}{}1}^{10}$ | $\tau_{1}$ | 99.60 | 98.97 | 5.086%
| 71-80 | $C_{4}^{\text{rate}}$ = 1 |  $S_{3}^{\text{\footnotesize{}in bw}}$ = $\\{100k\\}_{k\leavevmode\resizebox{2.33333pt}{0.0pt}{=}{}1}^{10}$ | $\tau_{1}$ | 34.45 | 33.84 | 12.77%
| 81-90 | $C_{4}^{\text{rate}}$ = 1 |  $S_{1}^{\text{\footnotesize{}out bw}}$ = $\\{100k\\}_{k\leavevmode\resizebox{2.33333pt}{0.0pt}{=}{}1}^{10}$ | $\tau_{2}$ | 99.62 | 99.60 | 4.306%
Network intensive | 91-100 | $C_{4}^{\text{rate}}$ = 1 |  $S_{3}^{\text{\footnotesize{}in bw}}$ = $\\{100k\\}_{k\leavevmode\resizebox{2.33333pt}{0.0pt}{=}{}1}^{10}$ | $\tau_{2}$ | 34.45 | 33.78 | 9.772%
Multi-replica | 101-102 | $C_{5}^{\text{rate}}$ = $\\{1,3\\}$ | Best Effort | $\tau_{1}$ | 14.57 | 17.17 | 13.63%
Multi-endpoint | 103-104 | $C_{6}^{\text{rate}}$ = $\\{\frac{1}{2},\frac{1}{3}\\}$ | Best Effort | $\tau_{1}$ | 40.98 | 45.53 | 10.10%
|  |  |  |  | Avg. error=9.203%

Evaluation scenarios and associated errors

To evaluate scenarios involving multiple replicas, we designed scenarios
#101-102. In these scenarios, we assigned 4 replicas to $S_{1}$, 2 replicas to
$S_{2}$, and 2 replicas to $S_{3}$. We tested 2 different arrival rates on
$C_{5}$: (a) 1 $\frac{\text{req}}{\text{s}}$ in scenario #101, and (b) 3
$\frac{\text{req}}{\text{s}}$ in scenario #102. In scenarios 103-104, we aimed
to evaluate deployment that involved multiple endpoint functions, as well as,
cases where an endpoint function spawns multiple threads (e.g., $f_{2}^{1}$).
Another goal of these scenarios was to test the performance of PerfSim in
scenarios with complex service chains (i.e., $C_{6}$) with multiple loops and
nested diamond-shaped connections.

Figure 8: Evaluation results representing latency vs requests line graphs of
PerfSim (blue) and actual (orange) as well as the bar graph of their average
latency ($\overline{\\!\\!~{}^{l}\\!u_{o}^{\text{exe time}}}$)

####  6.3.2 Reflections on simulation accuracy

In the vast majority of our experiments, as shown in Figure 8, PerfSim
predicted the latency trend with a high accuracy (with average error rate of
9% error). However, in all scenarios, the actual service latency has visible
fluctuations across time (the orange line) while PerfSim’s predictions (blue
line) did not capture those slight variations. This is because PerfSim is a
discrete-event simulator and captures changes in the system state based on
events such as request generation/conclusion, thread spawn/kill, network
transmission start/end, queue start/end, task scheduling start/end, etc.
Therefore, as PerfSim events are not defined based on the CPU clock resolution
(i.e., kernel clock) to maintain fast simulation speed, it doesn’t consider
the CPU noise-factor to simulate slight fluctuations (e.g., slight changes in
CPU frequency or clock speed).

Another observation captured from the experiments results is the clear harmony
between almost all simulation results and the reality. Nonetheless, in some
intense scenarios (e.g., scenarios 21-23 or 41-42) where very low CPU
resources has been assigned to a memory intensive or storage intensive
services (100-300 millicores), even though PerfSim accurately simulated the
trend of performance, we observe a gap between PerfSim’s approximated latency
and the actual obtained latency in reality. The nature of this variation is
due to the use of a static model for each service in our experiments. In
highly overloaded or intense scenarios, specially in a memory-intensive task,
cache-miss rate may significantly affected and undergo substantial changes,
which even though has already been considered in PerfSim’s core, combining it
with ever increasing rate of context switches and CPU migrations in such
intense scenarios, creates a high competition between service threads from one
hand and system/user threads on the other hand which puts the entire system in
a chaotic situation. This problem can be addressed by utilizing more dynamic
performance models per service and considering system level threads in the
simulation.

###  6.4 Execution time of PerfSim

One of the key ideas behind designing PerfSim is to eliminate the barrier for
utilizing advanced machine learning techniques (such as deep reinforcement
learning) for optimizing the performance of large-scale service chains that
require fast efficiency in estimating various resource allocation and
placement scenarios. In this section, we evaluated the execution time of all
104 scenarios and compared them with the simulation time in PerfSim.

Due to the fact that the main users of PerfSim will be researchers and
performance engineers with limited access to computation resources, and to
highlight the lightweight nature of PerfSim, a single personal laptop has been
used to measure the simulation speed. We ran PerfSim in single-threaded mode
using a MacBook Pro with a 2.6 GHz Intel Core i7 CPU and 16GB of RAM.

We represents the detailed speed comparison in Figure 9. As shown in the
graph, a single-thread execution of PerfSim is 16-1200 times faster to
evaluate the performance of a scenario when compared to running/evaluating the
same deployment on a real cluster.

Figure 9: Execution time (in seconds) of all scenarios in both PerfSim and
real deployment (note the difference in scales).

###  6.5 Simulating large scale service chains

heightadjust=all,valign=t

[] [.4]  [.59]

(a) Original service chain $G(C_{l})$

(b) Extracted alternative graph $G^{\prime}(C_{l})$ Figure 10: Simulating a
large service chain with different types of workload, payload sizes and
heaviness (e.g., large number of instruction, cache r/w)

When designing PerfSim, we initially aimed to use it for optimizing large-
scale service chains. Therefore, one of the aspects of this evaluation has
been focused on the ability of PerfSim to simulate large-scaled service
chains. For this purpose, we simulated the performance of a large randomized
service chain deployed over a cluster of 100 host. We illustrated both our
generated service chain $G(C_{l})$ and extracted alternative graph
$G^{\prime}(C_{l})$ in Figure 10. This service chain consists of 100 nodes and
200 edges with randomized payloads, workload heaviness and workload type.

Similar to the previous scenarios, we used a single-threaded version of
PerfSim for the entire experiment. We presents both simulation parameters and
results in Table 6.5. As shown, PerfSim was able to simulate the performance
of this large-scale service chain for up to 10 times faster than targeted
execution time $\Delta{\hat{T}}$ while using reasonable CPU and memory
resources.

Simulation parameters | Simulation results
---|---
Parameter | Value | Key | Value
$C_{l}^{\text{rate}}$ | 0.1 $\frac{\text{req}}{\text{s}}$ | $\overline{\\!\\!~{}^{l}\\!u_{o}^{\text{exe time}}}$ | 9,744.95ms
$\Delta{\hat{T}}$ | 600s | Sim. time | 68.80s
$|\\!\\!~{}^{l}\\!S|$ | 100 | $|\\!\\!~{}^{l}\\!S^{\prime}|$ | 201
$|\\!\\!~{}^{l}\\!E|$ | 200 | $n^{G^{\prime}(C_{l})}$ | 161
$|H|$ | 100 | Exec. threads | 12060
$\tau$ | $\tau_{1}$ | CPU usage | 99.9%
Resources | Best effort | Mem. usage | 1.64GB

Simulation parameters and summary of results in the large service chain
scenario using PerfSim prototype

###  6.6 Discussion on challenges and limitations

In this section, we discuss main challenges of performance simulation, as well
as, key limitations for using PerfSim.

####  6.6.1 Comments on time-predictability of tasks

Time-predictability of a task in a computer software mainly refers to the
properties of the phenomenon execution time, including the execution pattern
of instructions or spectrum of occurrence events related to a job’s execution
time [10.1007/978-3-642-16256-5_5, article-time-predictability]. These
properties directly affect the process of modeling a job’s execution time and,
in many cases, can make it impossible to extract any reusable pattern
[6404196]. Hence, it is a vital property to hold in real-time and embedded
systems due to their time and mission critical nature.

To shed light on the surface of the problem, we provide an example in Listing
2, representing 2 functions (f1 and f2), both calculating n number of MD5
hashes. Function f1 receives the value of n as an argument whereas f2
initiates n with a randomly generated number between 0 and $10^{10}$. For
these functions, modeling f1 is relatively straightforward because its
execution time is directly related to the input argument n; for f2 on the
other hand, it is extremely hard to approximate the execution time because it
depends on the randomly generated variable n.

⬇

//high time-predictability

function f1(n){

for($i=0; $i<$n; $i++){

createHash(’md5’);

}

}

⬇ //low time-predictability function f2(){ let n = randInt(0,10**10);
for($i=0; $i<$n; $i++){ createHash(’md5’); } }

⬇

\end{flushleft}

With the growing convergence of High-Performance Computing (HPC) systems and
cloud computing paradigm, modern design patterns tend to progressively
consider the properties of time-predictable computing in their approaches to
be able to plan for the underlying resource allocation policies,
infrastructure costs, as well as, to avoid Service Level Agreement (SLA)
penalties. However, many organizations are still not ready for such a
transition, and this imposes immense challenges in modeling and simulating the
performance of their designed systems.

\subsubsection{Modeling the software architecture}

The software architecture, as the key foundation of any software system, can
significantly impact the performance of chain of services. As described in the
previous sections, \name{} can adequately model architecture of a software
system by defining the connection between microservices and hosts, and
translating each microservice into a set of endpoint functions while
describing their properties.

However, one of the critical challenges in simulating large-scale systems is
to model components that may change their behaviour based on the context. For
example, some architectures foresee an HTTP cache server in the front-line of
their main webserver to reduce the latency of requests or API calls. When a
request arrives, these cache servers check their temporary storage for the
requested content and only send the request to the upstream server when they
have not found the requested content in the cache or when it is outdated.
Modeling such services that can change their behavior based on the situation,
although possible in \name, requires designing content-aware modules for the
simulator. For this, interested users can extend the corresponding classes to
override the methods responsible for consuming resources, as we well as the
pattern of executing endpoint functions and their corresponding threads.

\subsubsection{Model portability}

We rigorously evaluated \name{} in various scenarios and demonstrated its
accuracy in different settings. However, we find out that even though the
extracted models can be used in different hosts and settings, they cannot be
generalised/used to simulate the performance in other microarchitecture
settings. For example, a model extracted for an Intel CPU architecture cannot
be used to accurately simulate the performance of the ARM-compatible version
of the software in an ARM-based architecture (e.g., Apple’s M-series chips -
even with dynamic binary translation enabled).

\subsubsection{Simulating highly overloaded scenarios}

Two paramount features of \name{} are (1) its ability to simulate contention
for various resources when multiple containers are packed in a host, and (2)
simulating network congestion when microservices communicate over a network
topology. However, when a process enters an highly overloaded state (i.e.,
when the rate of incoming requests is more than the processing capacity of
serving processes

), the request queue will grow without a bound, and in the meanwhile, the
system aggressively throttles CPU and network resources. This, in turn, will
increase the rate of context switches, CPU migrations, and cache misses.

In large-scale systems, performance engineers generally define a rigorous set
of constraints and resource management policies throughout a software’s design
and deployment lifecycle to prevent the system from entering such
unpredictable situations \cite{10.5555/542306}. Hence, accurate simulation of
such chaotic situations are extremely challenging.

\subsubsection{Simulating containers on system virtual machines}

One of the widely used schemes for deploying container orchestrators (e.g.,
Kubernetes) on a cluster involves the use of hypervisor-based virtualization
platforms, such as OpenStack or VMWare. Such deployment scheme becomes popular
as system virtual machines (1) allows the use of various operating systems in
one machine, (2) allows OS-level customization for each service, and (3)
provide better data and resource isolation between neighbouring services.
However, study shows that virtualization suffers from noticeable performance
overhead due to the additional OS layer \cite{8284700,
Shirinbab2019PerformanceIO}.

One of the main intentions of designing \name{} is to simulate thread-level
performance of services and to enable accurate prediction of endpoint
functions performance when various threads compete over resources in a host.
Thus, the additional complexity of OS-level threads in the aforementioned
schemes, if not appropriately modelled, may affect the accuracy of simulation
in scenarios where the virtualization overhead is considerably high.

\subsubsection{Challenges of performance modeling}

As described earlier, the process of performance modeling occurs on a PTE that
mimics a PE to (1) obtain a complete isolation for services to collect
accurate measurements for each endpoint function and (2) to prevent
interference with the experience of real cloud users. However, preparing a PTE
may impose both technical and financial challenges that needs to be addressed
in the design of DevOps process flows. Automating the entire process of
performance testing after each release may dramatically reduce the cost of
modeling and dramatically increase the accuracy of simulations.

\section{Conclusion and future works}

In this work, we presented \name{} as a systematic method and simulation
platform for modeling and simulating the performance of large-scale service
chains in the context of cloud native computing. Using performance tracing and
monitoring tools, \name{} allows performance modeling of various microservices
and their corresponding service chains in cloud native orchestration platforms
(such as Kubernetes that we used in this article) and enables the possibility
to simulate the effectiveness of different resource management scenarios and
placement policies. We evaluated the accuracy of \name{} in a set of prevalent
scenarios and obtained {\raise.17ex\hbox{$\scriptstyle\mathtt{\sim}$}}81-99\%
prediction accuracy as well as
{\raise.17ex\hbox{$\scriptstyle\mathtt{\sim}$}}16-1200 times speed-up factor
in comparison to testing on a real system (excluding the time needed for
setting up the system and configuring the cluster). We evaluated the
capability of \name{} in simulating large-scale service chains and showed that
using a single-core of a laptop, it can achieve a 10 fold speed-up factor to
simulate a scenario with complex service chains (composed of 100 microservices
interconnected with 200 links deployed over a cluster with 100 hosts).

Our future work will cover three main categories: (1) improving speed, (2)
improving accuracy, and (3) expanding use cases of \name. To increase its
speed-up factor, we plan to refactor it to harness the parallel processing
capabilities of GPUs. To improve its accuracy, we will add more
layers/features, such as the support of defining cache-size per container (to
simulate various scenarios based on Intel’s CAT) or adding the simulation of
poll mode in NICs (e.g., scenarios involving DPDK). Because advanced
performance optimization methods can harness \name{’s} fast scenario
assessment capability to quickly perform numerous policy trials and errors, we
will work towards proposing novel performance optimization methods. We will
also use \name{} to train deep reinforcement learning agents that can
autonomously control different policies in the cluster. We will also implement
accounting features in PerfSim that would allow detailed report on cost of
deployment (e.g., when deploying on a public cloud) based on pricing/cost
information provided within the scenario config files.

\section*{Acknowledgments}

Parts of this work has been supported by the Knowledge Foundation of Sweden
(KKS) through the Project AIDA (20200067). The contribution of Auday Al-
Dulaimy to this work has been performed with the support of the KKS under the
SACSys project.

\ifCLASSOPTIONcaptionsoff

\newpage

\fi

\bibliographystyle{IEEEtran}

\bibliography{IEEEabrv,bib}

\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{images/authors/colored/michel.png}}]{Michel
Gokan Khan} (M’13) received the M.S. degree in software engineering from Iran
University of Science and Technology, Tehran, Iran, in 2016. He is currently
pursuing the Ph.D. degree in computer science at Karlstad University, Sweden.

His main research interest includes network function virtualization, cloud
native applications, mathematical and machine learning based performance
optimization for telecom clouds, cloud computing, and applications of AI in
distributed systems.

\end{IEEEbiography}

\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{images/authors/colored/javid.png}}]{Javid
Taheri} received the Ph.D. degree in mobile computing from the School of
Information Technologies, The University of Sydney, Australia. He is currently
a Professor with the Department of Computer Science, Karlstad University,
Sweden. His major areas of interest are profiling, modeling, and optimization
techniques for private and public cloud infrastructures, profiling, modeling,
and optimization techniques for software-defined networks, and network-aware
scheduling algorithms for cloud

computing.

\end{IEEEbiography}

\begin{IEEEbiography}

[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{images/authors/colored/auday.png}}]

{Auday Al-Dulaimy}

is a postdoctoral researcher at the School of Innovation, Design and
Engineering, Mälardalen University, Sweden. He received PhD degree in Computer
Science from Beirut Arab University, Lebanon in 2017; and B.Sc and M.Sc
degrees in Computer Science from Al-Nahrain University, Iraq in 2000 and 2003
respectively. His major areas of research interest includes Distributed
Systems, Cloud Computing, Internet of Things, and Edge Computing.

\end{IEEEbiography}

\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{images/authors/colored/andreas.png}}]{Andreas
J. Kassler} (SM’12) received his M.Sc. degree in mathematics/computer science
from Augsburg University, Germany in 1995 and his Ph.D. degree in computer
science from University of Ulm, Germany in 2002. He is currently Professor
with the Department of Computer Science, Karlstad University, Sweden. He
teaches wireless networks and advanced topics in computer networking. His main
research interests include Software Defined Networks, Future Internet, and
Network Function Virtualization.

\end{IEEEbiography}

\end{document}