# Dimensioning network slices for power minimization under reliability constraints

Wei Huang, Andrea Araldo, Hind Castel-Taleb, Badii Jouaber

► To cite this version:

Wei Huang, Andrea Araldo, Hind Castel-Taleb, Badii Jouaber. Dimensioning network slices for power minimization under reliability constraints. Future Generation Computer Systems, 2025, 170, pp.107824. 10.1016/j.future.2025.107824. hal-05023300

HAL Id: hal-05023300

https://hal.science/hal-05023300v1

Submitted on 20 Jan 2026

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Dimensioning Network Slices for Power Minimization under Reliability Constraints

Wei Huang, Andrea Araldo, Hind Castel-Taleb, Badii Jouaber

Telecom SudParis, SAMOVAR, IP-Paris

`{first_name}.{last_name}@telecom-sudparis.eu`

## Abstract

Network slicing allows multiplexing virtualized networks, called *slices*, over a single physical network infrastructure. Research has extensively focused on the placement of virtual functions and the links that compose each network slice. On the other hand, performance greatly depends on how many resources are allocated to virtual nodes and links, *after* they are placed. This aspect has been mostly neglected.

In this paper, we propose a method to dimension computation and network resources to slices, with the aim to minimize dynamic power consumption. Latency and power are the result of non-trivial couplings between different components of each slice. Therefore, minimizing power while satisfying the reliability constraints of all slices is challenging. To capture these couplings, we model slices as multiple Jackson networks (one per slice) co-existing in the same resource-constrained physical network. To the best of our knowledge, we are the first to employ Jackson Networks in such a setting. Dynamic power savings are in large part obtained by finely deciding CPU clock frequency, exploiting Dynamic Voltage Frequency Scaling (DVFS). Via numerical evaluation, we show that our method finds per each slice just the right amount of resources to satisfy latency constraints (expressed in probabilistic terms, as chance-constraints). This brings relevant dynamic power reduction with respect to baselines representing the state of the art in network slicing, which focuses on placement without specific strategies for resources dimensioning.

**Keywords:** Network Slicing, Resource Allocation, Jackson Networks, Hypo-exponential Distribution, Optimization.

## 1. Introduction

Fifth Generation (5G) of mobile networks and beyond are expected to be able to host multiple services, such as augmented reality and automated driving, running in the same infrastructure. Such services, run by third-party Service Providers (SPs) may have heterogeneous requirements, e.g., in terms of journey time (total time spent to satisfy user requests). Network slicing is a solution to virtually isolate such services, thus guaranteeing their respective requirements, Indeed, network slicing enables network operators to virtualize physical resources including Central Processing Unit (CPU) cycles in physical nodes and bandwidth in physical links and segment them into isolated, customizable virtual networks known as slices. Each slice can be regarded as an independent logical network, tailored to meet the specific requirements of third-party Service Providers (SPs). These SPs, providing applications and services, can run a part of their computation in-network and achieve latency and traffic reduction [1].

We assume that SPs are organized under the microservice philosophy [2]: the logic of the SP is split into different software components ordered in sequence to provide end-to-end services and each of which performs a basic virtual function. In case SPs are third party applications, e.g., gaming, video streaming, such components might be pieces of software implementing the application logic. Our approach can also be applied in the context of Network Function Virtualization (NFV) [3, Table 1]. In the NFV paradigm, network functions are implemented as software mod-

ules, known as Virtual Network Functions (VNFs), which are deployed on a virtualized infrastructure. This infrastructure enables resource allocation, scalability, and efficient management of physical resources. In this context, a component in our framework can be a VNF, taking advantage of NFV's software design and virtualization benefits. Components are interconnected via virtual links, each mapped to a physical path. The process of Virtual Network Embedding (VNE) involves determining how to appropriately place components onto physical nodes and virtual links onto physical paths [4, 5]. The assumption common to the VNF/VNE literature is that each component and virtual link "needs" a pre-defined amount of resources, declared by the SP.

We believe that the above assumption is too strong. Indeed, a component can work under different amounts of allocated computation capacity: the larger the capacity, the faster the computing speed. The same reasoning holds for virtual links. Therefore, how and who would set a priori the amount of computation and bandwidth "needed" by components and virtual links is unclear. Moreover, it is too restrictive to impose each component and virtual link to occupy always the same amount of resources. Such an amount could instead be computed based on current load. For this reason, in this work we formulate the *Slice Dimensioning Problem*, where we determine the amount of computational and bandwidth resources to allocate to each slice in order to minimize dynamic power consumption. Reducing power consumption is one of the current priorities in the academic community and in the industry [6], since it can greatly contribute to mitigate the environmental effect of Information
and Communication Technologies (ICT). This raised interest around the concept of “Just Enough Network Resources”, which calls for parsimony in ICT [7].

The slice dimensioning problem is challenging. On the one hand, we wish to use little resources to save power. On the other hand, resources must be enough so as to satisfy latency requirements. Resource dimensioning becomes even more challenging when considering that a single component may be replicated to multiple physical nodes and receive a different input request rate at each replica. This requires making dimensioning decisions for all replicas. The same applies to virtual links.

**1st contribution.** To tackle the slice dimensioning problem, we introduce an original formulation based on multiple Jackson networks (we presented the preliminary version in conference [8]). A Jackson network is a network of queues with exponential service rate (see precise definition in [9, Sec. 20.1]). In our formulation, multiple Jackson networks, each corresponding to a slice, co-exist in the same physical network, and are subject to limited capacity of physical nodes and physical links. Our formulation allows us to represent the latency reliability constraints in probabilistic terms, as chance-constraints, which are a natural way to define Service Level Agreements (SLA). We derive a close formula of the cumulative distribution function of the journey time for each slice, based on a mixture of hypo-exponential distribution (§ 4.1). To the best of our knowledge, we are the first to solve a resource optimization problem with chance constraint on latency, resulting from a network of queues.

**2nd contribution.** We propose “Just Enough Resources for Network Slices (JER-NS)”, an efficient algorithm to solve approximately the problem above and satisfy exactly latency constraints.

**3rd contribution.** We exploit DVFS technology for resource dimensioning of network slicing and demonstrate its potential to save power. To the best of our knowledge, we are the first to optimally decide CPU frequencies for a network of software components (and not just for single components).

In the numerical section, we test our algorithm on different scenarios, including realistic physical networks, different loads and heterogeneous slice types, such as enhanced Mobile Broadband (eMBB), Ultra-Reliable Low-Latency Communication (URLLC), massive Machine Type Communication (mMTC). We show significant dynamic power savings.

The paper is organized as follows. Related work is discussed in §2. The model and the problem are formalized in §3.1. The latency and power performance analysis is provided in §4.1. We present our resolution method (JER-NS algorithm) in §5 and numerical results §6. §7 concludes the paper. Our code is available as open-source.<fnref n="1" />

## 2. Related work

Our work is cast within the following areas presented below.

*Stochastic network dimensioning.* A telecommunication network is a Stochastic Network (SN), since user request arrival

and complexities are uncertain and stochastic. Previous work studies dimensioning one SN only [10–12]. They aim to minimize latency, by using as many resources as possible within a resource budget. We instead model several SPs, each corresponding to a slice, all coexisting in the same physical network. We thus need to replace the single resource budget constraint, with a multitude of capacity constraints, one per physical node and link. Different slices are modeled in [13], with SLAs expressed as chance constraints, similar to us. However, they only dimension only one component per slice, while we dimension a chain of components and virtual links, tightly interrelated, which is thus more complex.

*Network slicing.* The concept of network slicing has been applied in (i) the Radio Access Network (RAN) [14],[15] and (ii) the rest of the network [16], [17]. RAN slicing ensures that each slice has the appropriate radio resources to support specific use cases and performance requirements at the edge of the network. In comparison to core slicing in (ii), wireless conditions and user mobility should be considered in RAN slicing. Our work framed into (ii) and can be combined with methods dealing with RAN slicing [15], which is however outside our scope. A test framework is shown in [18] to study the performance (throughput, packet loss, average delay, and CPU consumption) of a slice of several software components. The authors found performance to be significantly sensitive to resource allocation. While [18] only measures performance, we optimize resource allocation to improve them.

*Network Function Placement.* A request entering a slice, traverses an ordered sequence of software components, i.e., a chain of Virtual Network Functions (VNFs). The problem of placement VNFs onto a physical network is called Virtual Network Embedding (VNE). VNE is often studied together with routing requests in a virtual network [19] and offloading computation tasks from user devices to the virtual network [5, 20] or placing virtual machines in the edge [21]. The line of work in service chain composition [22] also decides the order of VNFs. VNE has been studied applying Operations Research, as a variant of the bin-packing problem [23], reinforcement learning [19], distributed algorithms with regret guarantees [24]. Jackson networks have been used to model the performance obtained via different placements [23, 25]. All the aforementioned work assumes that the amount of CPU and bandwidth are given as input. We instead focus on dimensioning them. Note that VNF are usually considered to run software performing network-related tasks, e.g., gateways, firewalls. In this paper we consider they can also be functions of third party SPs running applications other than network-related ones, e.g., augmented reality.

*Scaling.* One way to improve power efficiency is to set to sleep mode the elements of the infrastructure that are not in use [26]. In the servers that are in use, limiting consumption of CPU cycles contributes to power saving. Auto-scaling automatically and dynamically allocates resource according to system load. Horizontal Scaling (HS) adjusts the number of replicas of software components, while Vertical Scaling (VS) adjusts the amount

<footnote n="1">¹https://github.com/Free-Wei/SliceDimensioning.git</footnote>
of CPU per component [27]. HS is applied to VNFs [28], a new virtual machine with more resources is instantiated if load is high. However, when VNFs have a state, such a state must be replicated and kept coherent when performing HS, which may be complex and time-consuming. In this case, VS is more appropriate, in particular when the component is not required to restart [29]. We can use VS mechanisms provided by cloud-native platforms to implement the resource dimensioning decisions we obtain with our optimization strategy. Note that scaling mechanisms are usually reactive and based on resource usage, e.g., if a certain percentage of CPU is exceeded, more resources will be given. By only considering resource utilization and not the SLA, reactive VS may lead to overprovisioning. Indeed, a component may be close to full resource utilization but still be able to meet the latency requirements. In this case, an increase in the allocated resources would not be needed, but reactive VS would still increase them, due to exceeding the related resource utilization threshold. This would let the application execute faster and force the CPU to work at higher frequencies (thus consuming more power), although not necessary. We wish instead to provide just-enough resources, to minimize dynamic power consumption, and we thus replace threshold-based reactive VS with the allocation decisions resulting from our model.

**Dynamic resource allocation.** Dynamic policies have been proposed to adjust resource allocation to react to dynamic network conditions. In particular, Deep Reinforcement Learning has shown impressive results [30]. However, such approaches cannot provide analytic SLA-related guarantees. In this paper, we are not proposing a dynamic policy, to make operational-level decisions: we propose instead a strategy for planning-level decisions, providing guarantees of satisfaction of SLAs, expressed as chance-constraints.

**Dynamic Voltage Frequency Scaling (DVFS).** Within the literature on DVFS, a technique that adjusts CPU clock frequency to save power, only [31, 32] explicitly take latency requirements into account. However, they only find the minimum CPU frequency satisfying certain latency requirements of a single component. We instead deal with a chain of computing and networking components, whose impact on the SLA cannot be disentangled. This required us to resort to Jackson network models.

**Preliminary version.** In [8], we expressed latency constraints in terms of expected values and modeled power in a simplistic fashion, without accounting for DVFS. In the current paper our model is more realistic, as latency constraints are probabilistic (chance constraint) and CPU frequencies are now among the decision variables. This makes our resolution method much more involved. Alg. 1 and all propositions and proofs (except Prop. 1 are new). Sensitivity analysis is new and all results (now considering realistic slice requirements) are new.

## 3. System Model and power optimization

We present here the model of the physical network (§3.1), of a Service Provider (SP) (§3.2), the input (consisting in com-

ponent placement and routing) and the model of the journey time of a request (§3.3), the abstraction of an SP as a network of queues (§3.5). Finally, we present the dynamic power minimization problem (§3.6). The notation is shown in Tab.1.

<table><caption>Table 1: Table of Notation</caption><thead><tr><th colspan="2">Acronyms</th></tr></thead><tbody><tr><td>VNE</td><td>Virtual Network Embedding (§1)</td></tr><tr><td>SPs</td><td>Service Providers (§1)</td></tr><tr><td>RAN</td><td>Radio Access Network (§2)</td></tr><tr><td>NO</td><td>Network Operator (§2)</td></tr><tr><td>DVFS</td><td>Dynamic Frequency Voltage Scaling (§2)</td></tr><tr><td>VNF</td><td>Virtual Network Function (§3.2)</td></tr><tr><td>SLA</td><td>Service Level Agreement (§3.2)</td></tr><tr><td>JER-NS</td><td>Just Enough Resources for Network Slices (Alg. 1)</td></tr><tr><td colspan="2">Inputs</td></tr><tr><td>S</td><td>Sets of SPs (or slices) (§3.1)</td></tr><tr><td>G = (V, E)</td><td>Physical network with nodes V and links E (§3.1)</td></tr><tr><td>R<sub>v</sub></td><td>Computational resources in physical node v ∈ V (§3.1)</td></tr><tr><td>R<sub>v,v'</sub></td><td>Bandwidth capacity of link (v, v') ∈ E (§3.1)</td></tr><tr><td>V<sup>s</sup><sub>in</sub></td><td>Set of ingress nodes for service provider s (§3.2)</td></tr><tr><td>c<sup>s</sup><sub>i</sub></td><td>The i-th software component of a SP s (§3.2)</td></tr><tr><td>A<sup>s</sup><sub>i,j</sub>, B<sup>s</sup><sub>i,j</sub></td><td>Random variables of the computation and communication complexity (§3.2)</td></tr><tr><td>α<sup>s</sup><sub>i</sub></td><td>Average computational complexity for component c<sup>s</sup><sub>i</sub> in instructions (§3.2)</td></tr><tr><td>β<sup>s</sup><sub>i,j</sub></td><td>Average communication complexity between component c<sup>s</sup><sub>i</sub> and component c<sup>s</sup><sub>i+1</sub> in bits (§3.2)</td></tr><tr><td>c<sup>s</sup><sub>i,v</sub></td><td>Replica of component c<sup>s</sup><sub>i</sub> deployed in node v (§3.3)</td></tr><tr><td>λ<sup>s</sup><sub>v,in</sub></td><td>Data rate of user-requests for SP s ingressing from each node v (§3.3)</td></tr><tr><td>P<sup>s</sup><sub>v,v'</sub></td><td>A single path in terms of physical links between physical nodes v and v', obtained from routing function. (§3.3)</td></tr><tr><td>R<sup>s</sup></td><td>Service Level Agreement reliability requirement of SP (or slice) s (§3.3)</td></tr><tr><td>D<sup>s</sup></td><td>Time threshold for requests of SP s (§3.3)</td></tr><tr><td>P<sup>s</sup><sub>S</sub></td><td>The sets of all possible paths for requests of SP s (§3.5)</td></tr><tr><td>Q<sub>v</sub></td><td>Set of queues representing component replicas placed in node v (§3.5)</td></tr><tr><td>Q<sub>v,v'</sub></td><td>Set of queues representing virtual links mapped to physical link (v, v') ∈ E (§3.5)</td></tr><tr><td>Q<sup>s</sup></td><td>The set of queues for SP s (§3.5)</td></tr><tr><td>γ</td><td>The instructions per cycle each CPU core can execute (§4.2.1)</td></tr><tr><td>λ<sub>q</sub></td><td>Arrival rate of queue q (3)</td></tr><tr><td>N<sup>s</sup></td><td>The number of queues belonging to SP s, equivalent to |Q<sup>s</sup>| (§5.3)</td></tr><tr><td>R<sub>q</sub></td><td>Computational resources (MIPS) in the physical node v ∈ V hosting VNF q ∈ Q<sub>q</sub> (§3.6)</td></tr><tr><td colspan="2">Decision variables</td></tr><tr><td>r<sup>s</sup><sub>i,v</sub></td><td>CPU allocated by NO to component replica c<sup>s</sup><sub>i,v</sub> (§3.4)</td></tr><tr><td>r<sup>s</sup><sub>i,v,i+1,v'</sub></td><td>Bandwidth allocated by the NO for the communication between component replicas c<sup>s</sup><sub>i,v</sub> and c<sup>s</sup><sub>i+1,v'</sub> (§3.4)</td></tr><tr><td>r<sub>q</sub></td><td>Allocated resources to queue q (§3.6)</td></tr><tr><td colspan="2">Outputs</td></tr><tr><td>g<sup>s</sup><sub>i</sub>(r<sup>s</sup><sub>i,v</sub>)</td><td>The function giving the average time needed to process one instruction of component i (§3.5)</td></tr><tr><td>μ<sub>q</sub>(r<sub>q</sub>)</td><td>Service rate of queue q (§3.5)</td></tr><tr><td>r<sub>v,v'</sub></td><td>Total allocated bandwidth in physical link (v, v') (§3.6)</td></tr><tr><td>ρ<sub>q</sub></td><td>Server utilization, which means the probability that all the servers are in use (§4.2.1)</td></tr><tr><td>T<sup>s</sup>(r)</td><td>The journey time of an arbitrary request of SP s under allocated resources r, following hypo-exponential distribution (§4.1)</td></tr><tr><td>T<sup>s</sup><sub>exp</sub>(r<sub>q</sub>)</td><td>The journey time of an arbitrary request of SP s in queue q under allocated resources r<sub>q</sub>, following exponential distribution (§5.3)</td></tr><tr><td>T<sub>q</sub>(r<sub>q</sub>)</td><td>Service time under resource allocation r<sub>q</sub> for queue q (§3.5)</td></tr><tr><td>E(T<sup>s</sup>(r))</td><td>The average total journey time of requests of SP s under allocated resources r (§4.1)</td></tr><tr><td>f(r<sub>q</sub>)</td><td>Frequency for queue q hosted on corresponding CPU core under resources allocation r<sub>q</sub> (§4.2.1)</td></tr><tr><td>P<sup>v</sup><sub>dyn</sub>(r<sub>q</sub>)</td><td>Power consumption at node v for queue q under resources allocation r<sub>q</sub> (§4.2.1)</td></tr><tr><td>P<sub>v,v'</sub>(r<sub>v,v'</sub>)</td><td>Power consumption on physical link (v, v') (§4.2.1)</td></tr></tbody></table>
### 3.1. Model of the physical network

We model the underlying physical network as directed graph $G = (V, E)$, where $V$ and $E$ are the set of nodes and edges, respectively. This graph represents the core network topology, going from the edge Data Centers (DCs), through local DCs to regional DCs [33, Fig. 5]. Each node $v \in V$ represents a general purpose server with computation, storage, and network cards. Following the VNF philosophy, such nodes act as high-speed core routers [34] and can at the same time host other functions. Each node is considered holding a limited amount of resources $R_v$, which in our case is CPU resources (Instructions/Sec).

We denote with $(v, v') \in E \subseteq V \times V$ a link and with $R_{v,v'} \ge 0$ its bandwidth capacity (Bits/Sec). Note that $R_{v,v'}$ may be different than $R_{v',v}$. We assume that physical network $G$ is owned by a NO and that a set $s \in S$ of SPs are concurrently deployed in $G$, each in a separate slice, which we also denote with $s$.

### 3.2. Model of a Service Provider

A SP $s$ receives Poissonian user requests from any node $v \in V$ at rate $\lambda_{v,in}^s \ge 0$. The nodes for which $\lambda_{v,in}^s > 0$ are ingress nodes for $s$. We denote with $V_{in}^s = \{v \in V | \lambda_{v,in}^s > 0\}$ the set of such nodes.

Each SP $s$ is a chain of $n^s$ software components $\{c_i^s\}_{i=1,...,n^s}$. Each component can run in a container (or a virtual machine). Computation complexity $A_{c_i^s}$ of component $c_i^s$ is the amount of machine-level instructions to be executed by that component at every request. We assume $A_{c_i^s}$ is an exponentially distributed random variable with mean $\alpha_{c_i^s}$. For every request, after computation ends in $c_i^s$, some data are sent to $c_{i+1}^s$ for that request to be processed therein.

Communication complexity $B_{c_i^s, c_{i+1}^s}$ is the amount of data (in bits) sent from $c_i^s$ to $c_{i+1}^s$ at each request. It is also an exponentially distributed random variable with mean $\beta_{c_i^s, c_{i+1}^s}$. We denote by $\beta_{0, c_i^s}$ the amount of data transmitted at each request from a user of SP $s$ to the first processing component.

### 3.3. Component placement, replicas, routing and journey time

Note that a component may be replicated in several nodes [1, 14]. We denote by $c_{i,v}^s$ the replica of component $c_i^s$ deployed in node $v \in V$. Observe that placement is for us an input to our problem. In practice, placing component replicas requires some cost of migration and start-up. However, we do not consider these aspects, since we tackle resource dimensioning after component replicas have been placed. For each replica $c_{i,v}^s$, a pre-defined routing function returns replica $c_{i+1,v'}^s$ (of the next component) that should receive requests after $c_{i,v}^s$, as well as the set of physical links to be traversed. Placement and routing function are an input to our problem. In the numerical results, we will adopt a routing function that always returns the closest among the replicas of the next component and shortest-path (in terms of number of links) to reach it.

Random variable $T^s$ denotes the journey time of a request of SP $s$, i.e., the time between the instant in which a user request enters the physical network and the instant in which the request

<figure><img src="image_2.png" /><figcaption>Figure 1: Slices embedded on physical network</figcaption></figure>

has been processed by the last component replica. Each SP $s$ specifies a latency requirement, expressed similarly as [35, (3)]:

$$ \mathbb{P}(T^s \le D^s) \ge R^s, \quad (1) $$

i.e., the journey time is required to be less than a threshold $D^s$ with probability of at least $R^s$, which we call reliability in compliance to the literature terminology [35, Tab.1]. We assume SP $s$ knows its requirements, computation and communication complexities, so that it can declare a SLA, which is an input for our power minimization problem:

$$ s = (\{c_i^s\}_{i \le n^s}, \{\alpha_i^s, \beta_{i,i+1}^s\}_{i \le n^s}, \{\lambda_{v,in}^s\}_{v \in V_{in}^s}, D^s, R^s) \quad (2) $$

Note that we are only modeling the core network and we do not account for the delay and the power consumption related to the wireless channel. Therefore, requirement (1) does not refer to the end-to-end delay, but only to the core network part of the request journey. Therefore, to optimize a mobile network “end-to-end”, our method should be combined with another dedicated to the wireless part, which is outside of our scope.

The example in Fig. 1 depicts two SPs $s_1$ and $s_2$, and three ingress nodes (with red contour). SP $s_1$ has two components $c_1^{s_1}$ and $c_2^{s_1}$, with two replicas each. For the first component $c_1^{s_1}$, replicas $c_{1,v_1}^{s_1}$ and $c_{1,v_6}^{s_1}$ are in the physical nodes $v_1$ and $v_6$ respectively. The second component $c_2^{s_1}$ has replicas $c_{2,v_2}^{s_1}$ and $c_{2,v_3}^{s_1}$, deployed in physical nodes $v_2$ and $v_3$. User requests arrive from ingress nodes $v_4, v_5$ for SP $s_1$, and from $v_8$ for SP $s_2$. Let us consider a request for SP $s_1$ entering from node $v_5$: it goes to $v_6$ where it is executed by replica $c_{1,v_6}^{s_1}$ (as the other replica $c_{1,v_1}^{s_1}$ has a longer path from $v_5$), then the request goes to replica $c_{2,v_3}^{s_1}$.

### 3.4. Decision variables

For any SP $s$, the Network Operator (NO) decides:

* $r_{i,v}^s$ CPU resources (instructions per second) in physical node $v$, allocated to component replica $c_{i,v}^s$.

* $r_{i,v,i+1,v'}^s$ the bandwidth allocated for communication between component replicas $c_{i,v}^s$ and $c_{i+1,v'}^s$. Let $\mathcal{P}_{v,v'}$ denote the path, i.e. sequence of physical links between physical nodes $v$ and $v'$, obtained from the routing function.
Observe that $r_{i,v,i+1,v'}^s$ is reserved in each physical link belonging to path $\mathcal{P}_{v,v'}$. If $v$ is an ingress node, $r_{0,v,1,v'}^s$ is the reserved bandwidth to transmit the requests entering $v$ to component replica $c_{1,v'}^s$ of the first component.

Let $\mathbf{r}^s$ denote the vector of the aforementioned decision variables. By convention, we set:

* $r_{i,v}^s = 0$ if there is no replica of component $c_i^s$ in node $v$.

* for $i > 0$, $r_{i,v,i+1,v'} = 0$ if, according to the pre-fixed routing function (§3.3), requests exiting replica $c_{i,v}^s$ are never routed to replica $c_{i+1,v'}^s$ (They are always routed to other replicas, in physical nodes other than $v'$).

* Similarly, $r_{0,v,1,v'} = 0$ if the pre-fixed routing does not route requests entering from $v$ toward replica $c_{1,v'}^s$.

Observe that in our model, the SP does not request directly a certain amount of resources, but just specify the SLA (2) to be satisfied. The NO has the responsibility to choose the resource allocation in order to minimize power and satisfy the SLAs. Observe that in this way we satisfy the isolation requirement of slicing [36]: each SP has reserved CPU and bandwidth resources for its component replicas and inter-replica communications. It can run its applications as it were alone on a physical infrastructure with those resources entirely dedicated to it.

### 3.5. Acyclic Jackson network model of a Service Provider

The slice corresponding to each SP $s$ can be modeled as a feed-forward network of queues: a request enters from an ingress node and circulates into the network of queues until the execution of the request ends, in the last component. Fig. 2 illustrates the network of queues modeling SPs $s_1$ and $s_2$ of Fig. 1. For SP $s_1$, the traffic arrives from ingress nodes $v_4$ and $v_5$, with arrival rates $\lambda_{v_4,in}^{s_1}$, and $\lambda_{v_5,in}^{s_1}$, then it goes to the different numbered queues in order from left to right.

We denote by $\mathcal{P}\mathcal{S}^s$ the sets of all possible paths for the requests of SP $s$. For instance, in Fig. 2, $\mathcal{P}\mathcal{S}^{s_1}$ is composed of 4 paths (one of these paths is $\mathcal{P} = \{q_1^{s_1}, q_2^{s_1}, q_3^{s_1}, q_4^{s_1}\}$), while $\mathcal{P}\mathcal{S}^{s_2}$ is composed of one path only, namely $\mathcal{P}' = \{q_1^{s_2}, \dots, q_7^{s_2}\}$. Let $\mathcal{Q}^{s_1}$ (resp. $\mathcal{Q}^{s_2}$) be the set of queues modeling SP $s_1$ (resp. SP $s_2$):

$$ \mathcal{Q}^{s_1} = \{q_1^{s_1}, \dots, q_{10}^{s_1}\} \quad \text{and} \quad \mathcal{Q}^{s_2} = \{q_1^{s_2}, \dots, q_7^{s_2}\} $$

Several networks of queues co-exist in the same physical network. For each node $v$, let $Q_v$ be the set of queues for node $v$, and $Q_{v,v'}$ be the set of queues representing virtual links mapped to physical link $(v, v') \in \mathcal{E}$, regardless of the pair of component replicas connected by these virtual links and regardless of the SP to which they belong.

From Fig. 1, we can see that on physical node $v_1$, replicas $c_{1,v_1}^{s_1}$ and $c_{1,v_1}^{s_2}$ are placed, which are modeled in Fig. 2 as $Q_{v_1} = \{q_2^{s_1}, q_3^{s_2}\}$. We can also see that $Q_{v_1,v_2} = \{q_3^{s_1}, q_3^{s_2}\}$. Here, $q_3^{s_1}$ represents the channel, reserved into physical link $(v_1, v_2)$, for the virtual link between $c_{1,v_1}^{s_1}$ and $c_{2,v_2}^{s_1}$, and $q_3^{s_2}$ represents the channel, reserved into the same physical link, for the virtual link between $c_{1,v_1}^{s_2}$ and $c_{2,v_2}^{s_2}$. Note that the virtual link between the components $c_{2,v_2}^{s_2}$ and $c_{3,v_6}^{s_2}$ needs reserved channels in physical links $(v_2, v_5)$ and $(v_5, v_6)$, which we model with respective queues $Q_{v_2,v_5} = \{q_5^{s_2}\}$, $Q_{v_5,v_6} = \{q_6^{s_2}\}$. With the assumptions of

§3.2 and assuming all queues are infinite and follow a First In First Out discipline, each queue can be modeled as a M/M/1 queue, as common in the literature [37, 38]. Indeed, it has been found that the Poissonian nature of arrival and departures emerges when the load is sufficiently high [38, Sec.II.A.1-2]. Therefore, each SP $s$ becomes an acyclic Jackson network [9, Sec. 20.1]. A queue $q \in \mathcal{Q}^s$ can represent two things:

* Queue $q$ may represent replica $c_{i,v}^s$. With slight abuse of notation, we will talk in this case of “replica” $q$. The service time is the time needed to process $A_{c_i^s}$ instructions. Let $r_q = r_{i,v}^s$ denote the computation resources (instruction/second) allocated to that replica. Let $g_{c_i^s}^s(r_{i,v}^s)$ denote the function giving the average time needed to process one instruction of component $i$. In the simplest case [39, 40], $g_{c_i^s}^s(r_{i,v}^s) = 1/r_{i,v}^s$, but if component $c_i^s$ heavily accesses memory or storage, this function may have a different shape [41]. We have $T_q(r_q) = A_{c_i^s} \cdot g_{c_i^s}^s(r_q)$, defined as service time of queue $q$ under allocated resources $r_q$. Since $A_{c_i^s}$ is exponentially distributed, also $T_q(r_q)$ is exponentially distributed with mean $\mathbb{E}[T_q(r_q)] = \mathbb{E}[A_{c_i^s} g_{c_i^s}^s(r_q)] = \alpha_{c_i^s} \cdot g_{c_i^s}^s(r_q)$. Therefore, the service time of queue $q$ is Poisson with rate $\mu_q(r_q) = \frac{1}{\mathbb{E}[T_q(r_q)]} = \frac{1}{\alpha_{c_i^s} \cdot g_{c_i^s}^s(r_q)}$.

* Queue $q$ may represent the channel reserved to the virtual link between $c_{i,v}^s$ and $c_{i+1,v'}^s$ into physical link $(v'', v''')$, belonging to physical path $\mathcal{P}(v, v')$ selected by the routing function. In this case, we define $r_q = r_{i,v}^s$ for the bandwidth (bits/second) allocated to that channel on physical link $(v'', v''')$. Thus, the service time is $T_q(r_q) = \frac{B_{c_i^s} c_{i+1}^s}{r_q}$. Because communication complexity $B_{c_i^s} c_{i+1}^s$ is exponentially distributed with mean $\beta_{i,v,i+1,v'}^s$, then $T_q(r_q)$ is Poisson with rate $\frac{r_q}{\beta_{i,v,i+1,v'}^s}$.

Therefore, for a queue $q$, we can represent its service rate as the following function $\mu_q(r_q) = \frac{1}{\alpha_q \cdot g_{c_i^s}^s(r_q)}$ where:

* If $q$ represents component replica $c_{i,v}^s$, then $r_q$ is the computational resource $r_{i,v}^s$ allocated to SP $s$ in physical node $v$ and $\alpha_q$ is equal to the mean computation complexity $\alpha_{c_i,v}^s$ (§3.2).

* If $q$ represents the virtual channel reserved for the communication between $c_{i,v}^s$ and $c_{i+1,v'}^s$ in any link of the path between physical link $(v, v')$, then $g_{c_i^s}^s(r_q) = \frac{1}{r_q}$ and $r_q$ is the amount $r_{i,v,i+1,v'}^s$ of bandwidth allocated and $\alpha_q$ is equal to mean communication complexity $\beta_{i,v,i+1,v'}^s$ (§3.2).

Let us take any queue $q \in \mathcal{Q}^s$ of SP $s$, and represent routing decisions with two probabilities: $p_{q',q}$ is the probability that a request exiting queue $q'$ is directed to queue $q$; $p_{v,q}$ is the probability that a request entering the network through ingress node $v$ is directed to queue $q$ representing a replica of the first component. Both routing probabilities are given by the routing function (§3.3). The request rate entering $q$ is then

$$ \lambda_q = \sum_{q' \in \mathcal{Q}'} \lambda_{q'} \cdot p_{q',q} + \sum_{v \in \mathcal{V}_{in}} \lambda_{v,in}^s \cdot p_{v,q} \quad (3) $$

As an example, referring to Fig. 2 and SP $s_2$, and denoting by $q = q_1^{s_2}$ the channel reserved into physical link $(v_8, v_1)$ for
<figure><img src="image_3.png" /><figcaption>Figure 2: example of SP 1 and 2 on Jackson network</figcaption></figure>

communication between ingress node $v_8$ and replica $c_{1,v_1}^{s_2}$, then the arrival rate of $q$ is $\lambda_q = \lambda_{v_8,in}^{s_2}$.

### 3.6. Optimization constraints and objective

Our goal is to minimize dynamic power consumption, while still satisfying the latency constraints (1) of all SPs. Note that satisfying an SP's requirements is equivalent to meeting the requirements of its corresponding service. Therefore, we will write "service requirements" or "SP requirements" interchangeably. Power consumption is the sum of static and dynamic power. Only the latter depends on our decision variables, which concern CPU and bandwidth utilization. The static power consumption of physical nodes and links is simply a constant that adds to power computation. It would be useless to add this constant to our problem, as it would not change the decision variables. Our resource dimensioning problem is to determine how much CPU resources $r_q$ ($q \in Q_v$) to allocate to each component replica and how much bandwidth $r_q$ ($q \in Q_{v,v'}$) to allocate to each virtual link. Besides, we need to give more resources to SPs with more stringent latency constraints and larger request rates. Following industrial practice, we assume that there are "dedicated VNF cores" (§5.1 [42]), each entirely dedicated to a single component replica, in order to "provide isolation from other VNFs as well as isolation from the host". We denote by $R_q$ the capacity (in Millions Instructions per Second - MIPS) of the physical core hosting component replica $q$.<fnref n="2" /> We denote with $R_{v,v'}$ the bandwidth capacity (in bits per second) of physical link $(v, v')$.

Let $\mathbf{r} \triangleq \{r_q\}_{q \in Q_{v,v'} \in S}$ denote the vector of decision variables, i.e., the allocated resources and by $P_{dyn}^v(r_q)$ and $P_{v,v'}(r_{v,v'})$ the dynamic power consumed on physical node $v$ and communication power consumed in physical links $(v, v')$ (see § 4.2.2),

respectively. We formalize the problem as follows:

$$ \mathbf{P1}: \min_{\mathbf{r}} \sum_{v \in V} \sum_{q \in Q_v} P_{dyn}^v(r_q) + \sum_{(v,v') \in \mathcal{E}} P_{v,v'}(r_{v,v'}) \quad (4) $$

$$ \text{s.t.} \quad r_q \le R_q, \forall q \in Q_v, \forall v \in V \quad (5) $$

$$ \sum_{q \in Q_{v,v'}} r_q \le R_{v,v'}, \forall (v, v') \in \mathcal{E} \quad (6) $$

$$ \mathbb{P}(T^s(\mathbf{r}) \le D^s) \ge R^s, \forall \text{SP s} \quad (7) $$

$$ \mu_q(r_q) > \lambda_q, \forall q \in Q^s, \forall \text{SP s} \quad (8) $$

$$ r_{v,v'} = \sum_{q \in Q_{v,v'}} r_q, \forall (v, v') \in \mathcal{E} \quad (9) $$

Constraints (5)-(6) guarantee that we do not allocate, on physical nodes and links, more capacity than available. Constraint (7) corresponds to latency reliability constraint (1). Constraint (8) guarantees the stability of the Jackson networks [9, Eqn. (515)]. Constraint (9) just computes the total bandwidth allocated on each physical link. It is not easy to find a "power-efficient" $\mathbf{r}$ that satisfies (7). For this reason, in §5 we will transform (7) into a simpler expression. In §4.2, we will develop objective function (4).

Observe that the problem we want to solve is a dimensioning problem at a planning level, where we want to guarantee the SLAs. It is impossible to provide precise guarantees if the conditions under which we want to achieve them are not specified. Indeed, the characteristics of the incoming load must be known, if we want to ensure any SLAs. Any policy that does not rely on this information (like the dynamic ones mentioned in § 2) is, by construction, a best-effort policy, which cannot guarantee that the requirements will be met. In case of non-stationary load, problem P1 could be repeated periodically to comply with the current load characteristics.

## 4. Latency and power characterization

We now provide closed formulas for the average journey time and reliability constraint (7) (in § 4.1), and for power consumption of nodes and links (4) (in § 4.2).

### 4.1. Journey time for SPs

Recall that we model each SP as an acyclic Jackson network (§3.5). We assume journey time in each queue is independent from the others.<fnref n="3" />

<footnote n="2">²However, the formulation can be very easily adapted to the case in which multiple component replicas run on the same core. It would suffice in this case to explicitly write, in capacity constraint (5), the sum of the resources allocated to the component replicas running in a certain physical node, similarly to what we do for the bandwidth constraint (6).</footnote>

<footnote n="3">³In the case of the acyclic Jackson network, as in our case, there have been some riveting discussions on the independence of journey time of queues [43–45]. In summary, independence holds only if there is no overtaking. Overtaking refers to the process of providing service to a customer or job that arrives later at a queue, thereby enabling them to complete their task prior to an earlier-arriving customer. Theoretically, in our model, overtaking may happen since requests may traverse different paths from one physical node to another. We still adopt the queue independence assumption, leveraging simulation studies [46] that show that it provides a good approximation of the performance, even if overtaking occurs.</footnote>
**Proposition 1.** Assume stability conditions in all queues are met (i.e., $\mu_q(r_q) > \lambda_q, \forall q \in Q^s$). Then the mean journey time of a request of SP s is:

$$ \mathbb{E}[(T^s(\mathbf{r}))] = \frac{1}{\lambda^s} \cdot \sum_{q \in Q^s} \frac{\lambda_q}{\mu_q(r_q) - \lambda_q} \quad (10) $$

where $\lambda^s = \sum_{v \in V^s} \lambda_v^s$ is the overall ingress rate.

To verify reliability constraints (7), it is not sufficient to know the mean journey time. The entire probability distribution must be known. Prop. 2 expresses the journey time in terms of hypo-exponential distributions [47, §5.2.4] and allows to write reliability constraint (7) in closed form.

**Proposition 2.** Total journey time $T^s(\mathbf{r})$ of a request of SP s follows a mixture of hypo-exponential distributions. Denoting by $\mathbb{P}(\mathcal{P})$ the probability of choosing path $\mathcal{P} \in \mathcal{PS}^s$ and setting $\phi_q(\mathbf{r}) = \mu_q(r_q) - \lambda_q, \forall q \in Q^s$, the cumulative distribution function (CDF) of the total journey time is

$$ D^s \rightarrow \mathbb{P}(T^s(\mathbf{r}) \le D^s) = 1 - \sum_{\mathcal{P} \in \mathcal{PS}^s} \mathbb{P}(\mathcal{P}) \cdot \sum_{q \in \mathcal{P}} \prod_{q' \in \mathcal{P} \setminus \{q\}} \frac{\phi_{q'}(\mathbf{r})}{\phi_{q'}(\mathbf{r}) - \phi_q(\mathbf{r})} e^{-\phi_q(\mathbf{r}) \cdot D^s} \quad (11) $$

## 4.2. Power consumption model

### 4.2.1. Power consumption of computational nodes

CPU, memory and disk contribute to the dynamic power consumption of a physical node [48] at 58%, 28% and 14%, respectively [49, Fig. 3]. We here only focus on minimizing CPU dynamic power consumption, for the following reasons.

*First*, it represents the largest contribution.

*Second*, an increase of 1 watt in CPU dynamic power consumption will result in a rise of 27 watts in a data center [50, Fig. 1]. Hence, despite the fact that, in absolute terms, the dynamic power consumption of CPUs is little in comparison to the overall power consumption in the data center, the benefits of CPUs' dynamic power saving are substantial.

*Third*, trying to factor is memory dynamic consumption would not be pertinent. Indeed, it makes sense for a Network Operator (NO) to limit the CPU MIPS allocated to a software component: the component would simply adapt to this by running less fast. On the other hand, the memory required by a component is uniquely determined by its code (i.e., system function calls, such as the malloc): if the NO allocates less memory than the one used by the code, an Out-of-Memory error would occur. In other words, the NO cannot decide the amount of allocated memory and cannot thus influence, with any decision variable, the power consumption of memory. Similar argument holds for the storage.

For these reasons, memory and storage dynamic power is to be considered a constant with respect to our optimization decisions and can thus be omitted. In our model, each computational node $v \in V$ has multiple CPU cores. Each replica of a component runs in one CPU core. Let us consider a replica, represented by queue $q$, of component $c_i^s$, with mean computation complexity $\alpha_{c_i^s}$ (§3.2). We denote by $\lambda_q$ the rate (req/sec) of

<table><caption>Table 2: Voltage versus CPU Frequency, CPU MIPS, and Power Consumption of a CPU Core (source: [51])</caption><tr><td>Voltage (V)</td><td>0.72</td><td>0.75</td><td>0.78</td><td>0.81</td><td>0.84</td><td>0.87</td><td>0.90</td><td>0.93</td><td>0.96</td><td>0.99</td></tr><tr><td>CPU Frequency (GHz)</td><td>1.67</td><td>1.89</td><td>2.09</td><td>2.31</td><td>2.51</td><td>2.70</td><td>2.90</td><td>3.07</td><td>3.26</td><td>3.44</td></tr><tr><td>Dynamic Power (W)</td><td>7.1</td><td>8.7</td><td>10.4</td><td>12.4</td><td>14.6</td><td>17.1</td><td>20.0</td><td>23.2</td><td>27.0</td><td>31.4</td></tr><tr><td>CPU MIPS (§6)</td><td>5.01</td><td>5.67</td><td>6.27</td><td>6.93</td><td>7.53</td><td>8.1</td><td>8.7</td><td>9.21</td><td>9.78</td><td>10.32</td></tr></table>

request entering that replica, as in (3). We denote by $\alpha_q = \alpha_{c_i^s}$ the average computation complexity, i.e., the average number of instructions executed in that component replica per each request. We denote by $\gamma$ the instructions per cycle each CPU core can execute. A CPU is characterized by discrete set $\mathcal{F}$ of clock frequencies at which its core can run.<fnref n="4" /> For each frequency $f \in \mathcal{F}$, the number of instructions/second run by the core are $f \cdot \gamma$. If we want to run $r_q$ instructions per second, we need the CPU core to work at the following clock frequency

$$ f(r_q) = \min\{f \in \mathcal{F} | f \ge r_q/\gamma\} \quad (12) $$

**Proposition 3.** We denote $P_{dyn,max}^v(f)$ as the maximum dynamic power consumption (attained at full utilization) of a CPU core of node $v$ when working at frequency $f$. Then, the mean dynamic power consumed by the CPU core hosting queue $q$ is:

$$ P_{dyn}(r_q) = P_{dyn,max}(f(r_q)) \cdot \frac{\alpha_q \cdot g_{c_i}^s(r_q) \cdot r_q \cdot \lambda_q}{f(r_q)\gamma} \quad (13) $$

We assume the possible values of CPU core frequency are those in Tab.2.<fnref n="5" /> To simplify problem resolution, we work with continuous relaxations of power, using continuous variable $\tilde{f}(r_q) = \frac{r_q}{\gamma}$ to approximate $f(r_q)$. We fit a polynomial regression on Tab.2 to get the following continuous relaxation of $P_{dyn,max}^v(f)$:

$$ \tilde{P}_{dyn,max}^v(\tilde{f}) = 5.24\tilde{f}^2 - 13.42\tilde{f} + 15.25, \forall \tilde{f} > 0 $$

and the following continuous relaxation of $P_{dyn}^v(r_q)$:

$$ \tilde{P}_{dyn}^v(r_q) = \tilde{P}_{dyn,max}^v(\tilde{f}(r_q)) \cdot \alpha_q \cdot g_{c_i}^s(r_q) \cdot \lambda_q \quad (14) $$

It is then clear that, in order to minimize CPU power consumption, we need to reduce $r_q$ so as to be let the CPU core run slower (slower frequency $\tilde{f}(r_q)$). As commonly done in real-time systems, CPUfreq governor “userspace” [53] and “In-place” resource resize [29] can be used by the Network Operator (NO) to set the desired CPU frequency<fnref n="6" />). However, to satisfy stability

<footnote n="4">⁴CPUs deployed in the network may be heterogeneous. In this case, each CPU may have a different set of allowed clock frequencies and different power consumption profiles. Our model could be easily extended, by adding appropriate subscripts, to represent such heterogeneity. We assume here CPUs are homogeneous to avoid overcomplicated notation.</footnote>

<footnote n="5">⁵Key CPU configuration parameters are shown in [51, Tab.1]. Also, [52, Tab.2] shows that the Intel i5 processor operates at a different frequency/voltage pair in different P states.</footnote>

<footnote n="6">⁶Usually, the CPUGovernor, e.g., OnDemand governor, lets the CPU core decide the frequency automatically: it increases the frequency to the maximum when the load exceeds a predefined threshold, and decreases it step by step once the load drops below this threshold [54]. However, this policy is power-inefficient [55, Fig. 8].</footnote>
conditions (Prop. 1) and latency constraints (11), $r_q$ should be large enough, which implies that frequency $\widehat{f}(r_q)$ should be large enough. Since a physical node $v$ can be composed of multiple CPU cores, and each CPU core hosts one queue representing one component replica of some SP, the mean dynamic power consumption of physical node $v$ is the sum of the power consumptions of all the queues hosted in the cores of $v$.

### 4.2.2. Power consumption of links

Power consumption of wired networks, e.g., Ethernet cannot be neglected (small Ethernet switches in the US consumed 7.9 TWh in 2011 [56]). To model the dependence between bandwidth and power consumption, we resort to a curve whose shape has been found experimentally in [57], where authors also show that the exact parameters of this curve depend on the specifications of the particular piece of network equipment under observation (brand and model). We use here representative parameters that comply with the observations of [57]. The power consumption of 10 Gb/s Ethernet is between 4.5W - 20W [58]. In this paper, we assume that all link capacity is allocated to the slice traffic of interest. Traffic from other sources is either negligible or managed on separate, dedicated resources. Note that our model could also be naturally employed when other traffic is to be represented explicitly. In this case, we would introduce an additional fictitious SP, representing this other traffic. The power on physical link $(v, v')$ depend on bandwidth $r_{v,v'} = \sum_{q \in Q_{v,v'}} r_q$, i.e., the sum of all bandwidths allocated to all virtual links using $(v, v)$. If a virtual link uses multiple physical links, its allocated bandwidth will be considered in all such physical links, when computing their power consumptions. For all these reasons:

$$P_{v,v'}(r_{v,v'}) = \begin{cases} 0, & \text{if } r_{v,v'} = 0 \text{ Mb/s} \\ \frac{14.555}{550} \cdot r_{v,v'} + 4.5, & \text{if } r_{v,v'} < 550 \text{ Mb/s} \quad (15) \\ 19.055 + 10^{-4} \cdot r_{v,v'}, & \text{otherwise} \end{cases}$$

## 5. Resolution method

To minimize objective function (4), we would like to determine $r_q$ to be as low as possible for any $q \in Q^s$ and any SP $s$. However, we can only lower $r_q$ as long as reliability constraint (7) is met. Finding the set of values $r_q, q \in Q^s$, $\forall$ SP $s$ is thus challenging. Ideally, we would like to find a reverse function that gives the smallest values of $r_q$ for any pair of maximum delay $D^s$ and reliability $R^s$, for any SP $s$. This is however impossible since the probability distribution of delay $T^s(\mathbf{r})$ is too complicated (Prop. 2) and not invertible. Our JER-NS algorithm is iterative. At each iteration a simplified version of the original problem **P1** is solved. We call this the simplified version $\text{OPT}_{(b)}$, where $\mathbf{b} = (\mathbf{b}^s)_{s \in S}$ is a vector of parameters and $\mathbf{b}^s = (b_q \ge 0)_{q \in Q^s}$, $\forall$ SP $s$. More precisely, the simplified problem $\text{OPT}_{(b)}$ is obtained by replacing constraint (7) with constraint:

$$\mathbb{P}(\tilde{T}_{\mathbf{b}}^{s}(\mathbf{r}) \le D^s) \ge R^s, \forall \text{SP } s \quad (16)$$

where $\tilde{T}_{\mathbf{b}}^s(\mathbf{r})$ is a parametric approximation of $T^s(\mathbf{r})$ following truncated hypo-exponential distribution with parameter $\mathbf{b}$.

$\text{OPT}_{(b)}$ is simpler than the original problem **P1**, as the SLA articulated as (16) can be reformulated in terms of expected value, by appropriately applying Hoeffding's inequality (see Prop. 4 and its proof). This expected value is more straightforward to handle because it can be written as a sum of expected values one per each queue $q \in Q^s$, as we will show in (19). For any parameter $\mathbf{b}$, by solving the surrogate problem $\text{OPT}_{(b)}$, via the method explained in §5.2, we obtain a solution $\mathbf{r}$. This is why $\text{OPT}_{(b)}$ is an important part of our solution method.

We check if resources allocated in $\mathbf{r}$ are insufficient (by checking the SLAs against the exact the probability distributions of journey time $T^s$ (Prop. 2)) or overprovisioned (if SLAs could be satisfied also with less resources). Based on the previous check, we adjust parameter $\mathbf{b}$, as explained in §5.4.

Note that JER-NS uses surrogate problems $\text{OPT}_{(b)}$ to compute promising allocations $\mathbf{r}$, since directly calculating the solution to the original problem **P1** would be extremely difficult. However, we are sure that the final allocation satisfies all SLAs, thanks to checking journey time against the exact probability distributions.

### 5.1. Parametric approximation

We construct an approximation $\tilde{T}_{\mathbf{b}}^s(\mathbf{r})$ with parameter $\mathbf{b}$, which will be used in $\text{OPT}_{(b)}$ in lieu of $T^s(\mathbf{r})$. We first define hypo-exponential $\tilde{T}^s(\mathbf{r})$ composed of a sum of exponentials $T_q^{\text{sej}}(r_q)$, each of which is the journey time spent by a request in queue $q$:

$$\tilde{T}^s(\mathbf{r}) = \sum_{q \in Q^s} T_q^{\text{sej}}(r_q) \quad (17)$$

Referring to [47, §5.2.4], $\tilde{T}^s(\mathbf{r})$ has the following CDF and expected value:

$$\mathbb{P}(\tilde{T}^s(\mathbf{r}) \le D^s) = 1 - \sum_{q \in Q^s} \prod_{q' \in Q^s \setminus \{q\}} \frac{\tilde{\phi}_{q'}(\mathbf{r})}{\tilde{\phi}_{q'}(\mathbf{r}) - \tilde{\phi}_{q}(\mathbf{r})} e^{-\tilde{\phi}_{q}(\mathbf{r}) \cdot D^s} \quad (18)$$

$$\mathbb{E}[\tilde{T}^s(\mathbf{r})] = \sum_{q \in Q^s} \frac{1}{\tilde{\phi}_{q}} \quad (19)$$

where $\tilde{\phi}_{q} = \frac{\mu_{q}(r_{q}) - \lambda_{q}}{\Delta_{q}}$ and $\Delta_{q} = \frac{\lambda_{q}}{\lambda^{s}}$, $\forall q \in Q^s$.

We verify that $\tilde{T}^s(\mathbf{r})$ approximates quite well $T^s(\mathbf{r})$. These two random variables have the same expected value (Prop. 6 in the Appendix) and also the entire respective distributions are quite similar (Appendix A.4 and Tab.A.5). Note that $\tilde{T}^s(\mathbf{r}) = T^s(\mathbf{r})$ when the routing function returns exactly one path per each pair of component. The two distributions are slightly different when multipath is allowed: in this case, $T^s(\mathbf{r})$ is a mixture of hypo-exponential, which we instead approximate with a single hypo-exponential.

Given any vector $\mathbf{b} \triangleq (b_q)_{q \in Q^s}$, we define $\tilde{T}_{\mathbf{b}}^s(\mathbf{r})$ as the random variable with following CDF:

$$\mathbb{P}(\tilde{T}_{\mathbf{b}}^{s}(\mathbf{r}) \le D^s) \triangleq \mathbb{P}(\tilde{T}^{s}(\mathbf{r}) \le D^s | T_{q}^{\text{sej}}(r_q) \le b_q, \forall q \in Q^s) \quad (20)$$

The following property of approximation $\tilde{T}_{\mathbf{b}}^s$ allows efficient resolution of $\text{OPT}_{(b)}$.
**Proposition 4.** *Sufficient condition for the constraint $\mathbb{P}(\tilde{T}_b^s(\mathbf{r}) \le D^s) \ge R^s$ to hold is that decision $\mathbf{r}$ is such that*

$$ \mathbb{E}[\tilde{T}^s(\mathbf{r})] = D^s - t^s, \text{ where } t^s = \sqrt{\frac{\ln(1 - R_s) \cdot \sum_{q \in Q^s} (b_q)^2}{-2}} \quad (21) $$

## 5.2. Resolution of the approximated problem

To solve the simplified problem OPT<sub>(b)</sub>, we need to deal with constraint (16) which makes finding optimal **r** non trivial to obtain final resource allocation **r**. Thanks to Prop. 4, for any **b**<sup>s</sup>, we can calculate t<sup>s</sup> for each SP s and replace constraint (16) by (25). Combined with Prop. 3, OPT<sub>(b)</sub> becomes as following.

$$ \mathrm{OPT}_{(b)} : \min_{\mathbf{r}} \sum_{v \in \mathcal{V}} \sum_{q \in Q_v} P_{dyn}^{v}(r_q) + \sum_{(v,v') \in \mathcal{E}} P_{v,v'}(r_{v,v'}) \quad (22) $$

$$ \text{s.t.} \quad r_q/\gamma \le \mathcal{F}_{\max}, \forall q \in Q_v, \forall v \in \mathcal{V} \quad (23) $$

$$ \sum_{q \in Q_{v,v'}} r_q \le R_{v,v'}, \forall (v, v') \in \mathcal{E} \quad (24) $$

$$ \mathbb{E}[\tilde{T}^s(\mathbf{r})] = \sum_{q \in Q_v} \frac{1}{\phi_q} = D^s - t^s \quad (25) $$

$$ \mu_q(r_q) > \lambda_q, \forall q \in Q^s, \forall \text{SP s} \quad (26) $$

$$ r_{v,v'} = \sum_{q \in Q_{v,v'}} r_q, \forall (v, v') \in \mathcal{E} \quad (27) $$

To be precise, problem (22)-(27) is not exactly the same as the problem with constraint (16): indeed, the solution space of the former is a subset of the latter, since Prop. 4 is a sufficient condition. But we pinpoint here that, whenever we mention OPT<sub>(b)</sub> from now on, we will refer to (22)-(27). We solve OPT<sub>(b)</sub> via the interior point method [59].

## 5.3. Initialization of **b**

For any **b**, we can now easily find resource allocation results on OPT<sub>(b)</sub>. JER-NS algorithm will explore different values of **b**. However, in order to avoid wasting computation time trying values of **b** for which reliability constraints are far from being satisfied or for which power consumption is excessive, it is useful to start JER-NS algorithm with an appropriate initial value of **b**, which we obtain in the following proposition.

**Proposition 5.** *If we initialize*

$$ b_q = \sqrt{\frac{-32}{25 \cdot N^s \cdot \ln(1 - R^s)}} \cdot D^s, \forall q \in Q^s, \forall \text{SP s,} $$

where $N^s$ is the number of traversed queues by a request of SP s with $\max(N^s) = 1000$, then $\mathbb{P}(\tilde{T}^s(\mathbf{r}) \le D^s) \ge 99\%$

## 5.4. JER-NS Algorithm

The main steps of JER-NS Algorithm (Alg. 1) are:

(i) Initialize parameter **b** (as detailed in §5.3) and solve the simplified problem OPT<sub>(b)</sub>, as explained in §5.2. This process yields a preliminary resource allocation **r** and obtains the “true reliability” $R^s(\mathbf{b})$ for all SP s.

## Algorithm 1 JER-NS Algorithm

**Input:** $R^s$: Reliability of SP s, $T_p^s$: Tolerance parameter of SP s, $\epsilon$: Re-initialization with probability $\epsilon_s$, $D^s$: Latency requirement of SP s

**Output:** **r:** Resources allocation satisfying all constraints, $P(\mathbf{r})$: Overall power consumption

1: Initialize upper bound $b_q^s$ of each queue $q_i$ for each SP s (§5.3)

2: Solve optimization problem OPT<sub>(b)</sub> (Prop. 5.2) and obtain **r**, then calculate $R^s(\mathbf{b})$ for each SP

3: **for** Each SP s **do**

4:     **while** $R^s(\mathbf{b}) \notin [R^s - T_p^s, R^s + T_p^s]$ **do**

5:         **Phase 1: Exploration**

6:         Apply $b_q^s$ to constraint (Eqn. 25) and solve optimization problem OPT<sub>(b)</sub> (Prop. 5.2), obtain resource allocation **r**

7:         **Phase 2: Verification**

8:         $R^s(\mathbf{b}) \leftarrow \mathbb{P}(T^s(\mathbf{r}) \le D^s)$ (Eqn. 11)

9:         **if** $R^s(\mathbf{b}) > R^s$ **then**

10:         Decrease $b_q^s$ # Dichotomy method, more details found in appendix

11:     **else if** $R^s(\mathbf{b}) < R^s$ **then**

12:         Increase $b_q^s$ # Dichotomy method

13:     **end if**

14:     **Phase 3: Randomness**

15:     With probability $\epsilon$ for SP s, reinitialize $b_q^s$ for all queues $q$ of SP s

16:     **end while**

17: **end for**

18: Calculate CPU core frequency $f_q = \frac{r_q}{\gamma}$ for queue q in physical nodes

19: Adjust each $f_q$ to the closest larger discrete CPU core frequency and recalculate CPU MIPS

20: Calculate overall power consumption $P(\mathbf{r})$

21: **return** **r** and $P(\mathbf{r})$

(ii) If $R^s(\mathbf{b})$ is much higher than the required $R^s$, for a certain $R^s$ this means that allocation **r** is feasible yet inefficient. In such cases, we should prefer to reduce the reliability by reducing resources allocated to SP s, thereby decreasing power consumption. Allocating less resources implies, in general, increasing the expected value of total journey time, which is achieved (see Prop. 4) by decreasing $b_q, \forall q \in Q^s$.

(iii) On the contrary, if $R^s(\mathbf{b})$ is lower than $R^s$, we increase $b_q, \forall q \in Q^s$.

(iv) We iterate the previous steps until $R^s(\mathbf{b})$ is sufficiently close to $R^s$ for every SP s. Then, we take the final allocation vector **r**.

(v) For all queues $q \in Q^s$ that represent component replicas, we incrementally adjust $r_q$ upwards to find a valid CPU frequency $f_q$, as specified in Tab.2, such that $f_q \cdot \gamma = r_q$.

Note that JER-NS algorithm is stochastic, via parameter $\epsilon$. In this way, we can explore more broadly the solution space and escape from local minima. Furthermore, JER-NS verifies the allocation **r** obtained with “true reliability” constraint under the original distribution of the journey time, thereby guaranteeing that the final allocation meets the original optimization problem **P1**. Note that in real network environments, traffic load can fluctuate over time. The complexity of JER-NS is $O((|\mathcal{S}| \cdot (|\mathcal{V}| + |\mathcal{E}|))^3)$. The running time of JER-NS (Tab.4) allows running it periodically, i.e., every hour, to adapt the allocation to traffic evolution. Also note that JER-NS is iterative, allowing for the reuse of the previous allocation as a starting point in subsequent time periods, rather than initiating from scratch each time.
<table><caption>Figure 3: Physical network parameters and default topology</caption><tr><td>Node computational capacity</td><td>F<sub>max</sub>=3.44 GHz, &forall; c &isin; C<sub>u</sub>, v &isin; V (each CPU core process 1.032&middot;10<sup>10</sup> Instr/Sec )</td><td rowspan="4">[Figure 3: Physical network parameters and default topology]</td></tr><tr><td>Physical link capacity</td><td>R<sub>u,u</sub>=10 Gb/Sec, &forall; (u, u') &isin; E</td></tr><tr><td>Number of physical nodes</td><td>20-149</td></tr><tr><td>Number of physical links</td><td>40-386</td></tr></table>

# 6. Numerical results

JER-NS is evaluated under different traffic conditions (§6.2, 6.3), component replication scenarios (§6.4), in realistic networks (§6.5), in simulation (§6.5) and with dynamic traffic (§6.7).

## 6.1. Evaluation Setup

1) **Scenario description:** 3GPP has identified three primary usage scenarios: eMBB, mMTC, and URLLC [62]. We consider the network of Fig. 3 with three SPs, each representing one of the traffic classes. The number of components for these slices are chosen randomly from the range in Tab.3. Additionally, each component can be replicated once or twice. Similar to [39, 40], we assume that each physical node possesses sufficient memory and storage resources so that they do not impose additional capacity constraints. User requests can enter the network from any node (all nodes can serve as ingress nodes). Unless otherwise stated, we will use the scenario parameters (and their default values) specified in Tab.3. We will vary one parameter at a time, to assess its impact, and leave the others equal to their default values.

We assume communication complexity is related to the request size, requiring 200 CPU cycles per bit transmitted [63, Tab.1]. We assume a CPU executes 3 instructions per cycle [69]. Each run is stationary but stochastic (complexities and routing decisions are stationary random variables).

2) **Experiment execution:** Problem (22)-(27) is implemented in the Matlab solver called `fmincon` by applying interior point algorithm. Results are averaged over 20 independent runs each with a different random placement of replicas and with a different realization per each random variable. Since Alg. 1 may be trapped in local minima of optimization problem P1, we repeat it 5 times with $\epsilon = 0.07$, and select the resulting allocation r with the smallest power consumption. We ran experiments on a server with Intel(R) Xeon(R) Gold 5220R CPU @ 2.20GHz. Table 4 shows the mean and standard deviation of execution time on different physical networks over 20 random seeds. Topologies represent real networks and are taken from Topology Zoo [70].

3) **Details on routing function:** In our model, components can be duplicated, requiring the routing function (presented in §3.3) to select the best replica and path when forwarding requests, aiming to minimize the number of physical links traversed. Our formulation is independent of the chosen routing function. In the numerical results we consider a routing that behaves as follows. If a request needs to be forwarded to the next component and two replicas exist of that component and

they are reachable with two paths of the same length, then: with probability $p$ the request is delivered to one of the two replicas, while with probability $1-p$, it is delivered to the other replica (recall that there can be at most two replicas in our scenarios). For example, consider a user request for SP $s$ enters the network from an ingress node $v \in V$. The routing function decides to which replica of component $c_1^s$ this request will be forwarded. Suppose there is a replica in physical node $v_1$, and another in $v_2$. We may have the following cases for routing:

* If the shortest path between $v$ and $v_1$ has fewer links than the shortest path between $v$ and $v_2$, then the request is always forwarded to replica $c_{1,v_1}^s$, otherwise to replica $c_{1,v_2}^s$.

* If the two shortest paths have equal lengths, then the request is forwarded according to probability $p$ to replica $c_{1,v_1}^s$ or with probability $1-p$ to $c_{1,v_2}^s$.

4) **Compared strategies:** We compare the performance of our JER-NS algorithm (Alg. 1), with four other baselines representative of approaches commonly found in VNE literature. As described in §2, to the best of our knowledge, we are the first to jointly deal with dimensioning allocated resources to components and links. We cannot thus compare with previous work.

* **MinRes:** only the minimum resources needed to satisfy stability conditions (8) are allocated;

The other three baselines allocate resources proportionally to task sizes and complexities. A defined percentage, $p_{prop}$, of capacity is utilized across all active CPU cores and physical links. A CPU core is active if it hosts a component replica of any slice. A physical link is active if it is traversed by some virtual links of some slices. Inactive CPU cores and physical links remain unused. The capacity of active cores and links is allocated among slices proportionally to request rates and complexities.

* **PropRes50, PropRes75, PropRes100:** 50%, 75% and 100% of physical link and node resources are used, i.e. $p_{prop} = 0.5, p_{prop} = 0.75, p_{prop} = 1$, respectively.

## 6.2. Impact of different complexities

In Fig. 4(a), 4(b), and 4(c), we vary, from a run to another, computational and communication complexities. The computational complexity of any component $c_i$ of any slice $s$ is kept within interval $[\alpha^{s,min}, \alpha^{s,max}]$ where the values of $\alpha^{s,min}$ and $\alpha^{s,max}$ are provided in Tab.3. In particular, for a certain run, the computation complexity is set to $\alpha^{s,min} + \Omega \cdot (\alpha^{s,max} - \alpha^{s,min})$. In Fig. 4, we let $\Omega$ vary in $[0, 1]$, which we call complexity factor. Similarly, the communication complexity is within the range $\beta^{s,min} + \Omega \cdot (\beta^{s,max} - \beta^{s,min})$. Observe that by varying $\Omega$, we jointly vary computation and communication complexity.

From Fig. 4(a) - 4(c), we observe that both JER-NS and PropRes100 strategies are consistently above the reliability requirement for all slices (Tab.3). In Fig. 4(d) - 4(e), as expected, as the complexity increases, we need to consume more overall power to satisfy slices' requirements. Our JER-NS is consistently the strategy with the minimum power consumption, except for MinRes, which is anyways unusable, since it violates reliability constraints. JER-NS achieves this power-efficiency by
<table><caption>Table 3: Scenario parameters. References supporting the reported values are also provided. Default values are in bold. For each parameter, we specify the range of values that we tested in the different scenarios.</caption><thead><tr><th>Types of slices<br>Parameters</th><th>eMBB</th><th>mMTC</th><th>URLLC</th></tr></thead><tbody><tr><td>Avg. comm. complexity β<sup>s</sup><sub>c<sub>i</sub>,c<sub>i+1</sub></sub>, ∀c<sub>i</sub>, c<sub>i+1</sub></td><td>64-1500 bytes/req<br>([14, Table II], [60, Table 4]), <b>787.5</b></td><td>20-125 bytes/req<br>([61, Table XIX]), <b>72.5</b></td><td>32-300 bytes/req<br>([62]), <b>162.5</b></td></tr><tr><td>Avg. comput. complexity α<sup>s</sup><sub>c<sub>i</sub></sub>, ∀c<sub>i</sub><br>(200 instr/bit [63])</td><td>3.072 · 10<sup>5</sup> - 7.2 · 10<sup>6</sup> instr/req, <b>3.409 · 10<sup>6</sup></b></td><td>9.5 · 10<sup>4</sup> - 6 · 10<sup>5</sup> instr/req, <b>3.228 · 10<sup>5</sup></b></td><td>1.536 · 10<sup>5</sup> - 1.44 · 10<sup>6</sup> instr/req, <b>7.325 · 10<sup>5</sup></b></td></tr><tr><td>Avg. ingress req rate<br>per ingress node</td><td>100 - 1000 (reqs/s), <b>500</b></td><td>6000-15000 (reqs/s), <b>10000</b></td><td>3200-5000 (reqs/s), <b>4000</b></td></tr><tr><td>Number of components</td><td>2-5</td><td>2-5</td><td>2-3 [64]</td></tr><tr><td>Routing probability</td><td>0% - 100%, <b>50%</b></td><td>0% - 100%, <b>50%</b></td><td>0% - 100%, <b>50%</b></td></tr><tr><td>Replication probability</td><td>0% - 100%, <b>50%</b></td><td>0% - 100%, <b>50%</b></td><td>0% - 100%, <b>50%</b></td></tr><tr><td>Latency requirement</td><td>10-100ms ([61, Table XIX or Table XX]), <b>50</b></td><td><b>1s</b> ([61, Table XIX])</td><td>1-10ms ([65, Table IV]), <b>5</b></td></tr><tr><td>Reliability</td><td>90%-99.99% ([66, Fig.I], [67, Fig.I]), <b>95%</b></td><td><b>90%</b> ([65, Table IV])</td><td>95%-99.999% ([68, §V], [62]), <b>99%</b></td></tr><tr><td>Service time function g<sup>s</sup><sub>c<sub>i</sub></sub>(r<sup>s</sup><sub>i,v</sub>)</td><td>g<sup>s</sup><sub>c<sub>i</sub></sub>(r<sup>s</sup><sub>i,v</sub>) = 1/r<sup>s</sup><sub>i,v</sub> [39, 40]</td><td>g<sup>s</sup><sub>c<sub>i</sub></sub>(r<sup>s</sup><sub>i,v</sub>) = 1/r<sup>s</sup><sub>i,v</sub> [39, 40]</td><td>g<sup>s</sup><sub>c<sub>i</sub></sub>(r<sup>s</sup><sub>i,v</sub>) = 1/r<sup>s</sup><sub>i,v</sub> [39, 40]</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Figure 4: Impact of computational and communication complexity on reliability and power consumption. (In (a), (b) and (c), Ω is complexity factor, cells filled with **black** means succeeding to achieve reliability requirement, with **white** means failure.)</figcaption></figure>

adapting resources allocation to the reliability requirements of each of the three slices. This is the main advantage of JER-NS over PropRes, whose allocation is instead blindly based on request load and complexity and neglects latency, thus penalizing URLLC, which has low load but very stringent reliability.

## 6.3. Impact of different load

In Fig. 5 we vary request rates, assuming that within any given slice, the request rate from all ingress nodes is the same. For each specified request rate, we perform 20 optimization runs, each with a distinct seed. In each run, for every slice, we select randomly a number of ingress nodes between 1 and 2, so as to avoid being biased by a particular set of ingress nodes. We let the ingress rates for each slice vary between the minimum and maximum values (Tab.3), chosen to explore all feasible loads.<fnref n="8" />

For simplicity, we vary the load of all three slices together, by increasing a “load factor” $\Gamma \in [0.2, 2]$ and obtaining the load (in Kreq/s) for each ingress node of each slice as: eMBB: $\Gamma \cdot 0.5$, mMTC: $5 + \Gamma \cdot 5$, URLLC: $3 + \Gamma \cdot 1$

<figure><img src="image_5.png" /><figcaption>Figure 5: Impact of different ingress request rates. (In (a), (b) and (c), $\Gamma$ is arrival factor, cells filled with **black** means succeeding to achieve reliability requirement, with **white** means failure.)</figcaption></figure>

Additionally, we maintain other parameters at their default values, as specified in Tab.3. A trend similar to the previous figures is observed: MinRes minimizes power but fails to meet the reliability requirements of any slice. Conversely, all PropRes strategies exhibit low power efficiency. On the other hand, JER-NS successfully adapts to different traffic loads while achieving significantly lower power consumption, consistently across all the considered scenarios.

## 6.4. Impact of different routing and replication probability

In this section, we examine the overall performance under varying routing and replication probability. Fig. 6(a)-top is obtained by deploying 1 or 2 replicas per each component. In

<footnote n="7">⁷Physical network topologies from TopologyZoo [70] are, in order: (1) Twaren, (2) Abvt, (3) GtsHungary, (4) GtsSlovakia, (5) Intranetwork, (6) Bt-NorthAmerica, (7) Bellsouth, (8) Iris, (9) Renater2010, (10) GtsCe.</footnote>

<footnote n="8">⁸To check if a certain load is feasible, we compute the minimum resources we would need to satisfy stability (26). If these resources exceed available capacity,</footnote>

<footnote>then we know for sure that such load value is not feasible. We use this criterion to choose the maximum value of load to try (Tab.3).</footnote>
<table><caption>Table 4: Physical network<sup>7</sup> parameters and execution time</caption><thead><tr><th>Physical Network</th><th>Twaren</th><th>Abvt</th><th>GtsHun</th><th>GtsSl</th><th>InNet</th><th>BtNA</th><th>BellS</th><th>Iris</th><th>Renater</th><th>GtsCe</th></tr></thead><tbody><tr><td>Execution time (Sec)</td><td>47.0 ± 19.3</td><td>125.1 ± 102.1</td><td>94.8 ± 21.8</td><td>127.7 ± 30.3</td><td>219.1 ± 123.9</td><td>382.3 ± 138.7</td><td>350.8 ± 102.8</td><td>374.8 ± 125.3</td><td>283.1 ± 94.2</td><td>2992.1 ± 902.0</td></tr><tr><td>Nb of physical nodes</td><td>20</td><td>23</td><td>30</td><td>35</td><td>39</td><td>36</td><td>51</td><td>51</td><td>43</td><td>149</td></tr><tr><td>Nb of physical links</td><td>40</td><td>62</td><td>62</td><td>74</td><td>106</td><td>152</td><td>132</td><td>128</td><td>112</td><td>386</td></tr></tbody></table>

particular, for each seed, a first replica of each component is placed randomly. This placement is maintained, for that seed, over all the runs represented in the figure. Then, taking each component, an additional replica is also placed, with a probability equal to a “replication probability”. Also these additional replicas are placed randomly per each seed. We observe that the baseline policies all increase power consumption when increasing replicas. This does not occur for JER-NS, which instead can even slightly benefit from additional replicas, as it tends to consume generally less power than with no replication. We explain this via two effects:

* Recall that the routing function we consider always sends a request out from a component to the closest replica of the next component. Therefore, the more replicas, the higher the probability of finding a closer next-component replica. As a consequence, higher replication tends to reduce the number of links to be traversed by a request, and thus the power consumed by them. By the same argument, high replication tends to reduce the time spent traversing links, which leaves more time budget for processing. This allows reducing CPU clock frequencies, and thus CPU power. This is visible in Fig. 6(b): when replication is “full” (all components are replicated twice), CPU clock frequencies tend to be lower (except for eMBB, whose requirements are so loose that CPUs hosting its components can always run at the lowest frequency in our scenarios).

* Recall that the dynamic CPU power grows superlinearly with the computation capacity (right plot - Tab.2). This means that in the case of a very high load, it can be more power-efficient to split the load among two replicas, so that we can keep their two CPU frequencies low, instead of loading one replica a lot. Observe that replication and placement are inputs to our optimization problem and we do not decide them. If one also wanted to include a replication strategy in the decisions, one would need to consider that, by reducing replicas, it would be possible to turn more CPU cores off, thus saving static power. However, this is far from the setting of this work, in which the focus is on dynamic power and we want to get the best resource dimensioning, given an input set of already placed replicas.

In Fig. 6(a)-bottom, we set replication probability to 100% which implies 2 replicas deployed for each component. Recall that requests are always forwarded to the next replica with the shortest path and, only when two replicas of the next components are at the same distance, requests are sent to one and the other with a certain probability. It is evident that JER-NS consumes significantly less power than the other PropRes strategies. The lowest power consumption under JER-NS is achieved when the routing probability is set to either 0% or 100%. Indeed,

<figure><img src="image_6.png" /><figcaption>(a) Impact of different replication (b) Active CPU core frequencies on probability and routing probability replication and no-replication case</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 7: Dynamic power consumption per component on different physical networks</figcaption></figure>

with those probabilities, all requests of a slice entering from any identical ingress nodes follow the same path. This means that the number of links used overall is less than when routing probability is between 0 and 1, where multiple paths per ingress node are allowed. We pinpoint however that multiple paths are not useless. On the contrary, when the load from a certain ingress node is very high and using one path only would not provide enough capacity, we would benefit from multiple paths. However, the routing function is an input to our problem, and deciding how to set it optimally is outside our scope. Overall, Fig. 6(a) can be interpreted by saying that multipath routing is to be avoided if not strictly needed.

## 6.5. Performance on different physical networks

In this section, we compare dynamic power consumption per component across different physical networks. Their topologies are taken from Topology Zoo [70] and represent heterogeneous real networks, ordered from small to big networks (Tab.4). As in §3.1, we assume each router is replaced by a general-purpose
server. Fig. 7 confirms our previous observations, i.e., dynamic power consumption of JER-NS consistently outperforms the other strategies and is always very close the lower bound on dynamic consumption, which is represented by MinRes (but recall that MinRes does not satisfy the SLAs).

We observe that JER-NS’s dynamic power consumption per component is approximately 100 Watts lower than that of other strategies in the physical network “GtsCe”. Observe that the number of components per slice and the number of slices can be much large than what we presented here and that reduction in dynamic power consumption brings dramatically down other power consumption causes (e.g., cooling [71, Fig. 9]). Therefore, the 100 Watts dynamic power savings, which may seem a small figure per se, translates into very relevant overall power savings.

## 6.6. Simulation

We validate the performance of our JER-NS algorithm in Java Modelling Tools, in the default scenario (Tab.3), with complexity $\Omega = 0.75$, with more than $10^6$ requests as input. Fig. 8 shows that JER-NS robustly satisfies the requirements of the 3 slices.

<figure><img src="image_8.png" /><figcaption>Figure 8: Journey time for different slices via simulation. (a): 90th Percentile of mMTC Samples by 2s Interval. (b) 95th Percentile of eMBB Samples by 30s Interval. (c): 99th Percentile of URLLC Samples by 8s Interval</figcaption></figure>

## 6.7. Dynamic traffic scenario

<figure><img src="image_9.png" /><figcaption>Figure 9: Traffic and Power Consumption Over Time</figcaption></figure>

We now apply our approach to a dynamic case, where traffic is non-stationary. Fig. 9 shows the trend $\Lambda_t$ of request rate, normalized to 1, which matches traffic observed in real networks [72, Fig. 2]. SP $s$ request rate is $\Lambda_t \cdot \lambda^s$, where $\lambda^s$ is the maximum request rate from Tab.3. Every 10 minutes, we run our optimization on current conditions (i.e., assuming current $\Lambda_t \cdot \lambda^s, \forall s \in S$) and we recompute decision variable $r$ accordingly. Fig. 9 shows that our approach manages to adapt power consumption (plotted with a smoothing window of 1 hour) to dynamic condition, violating the SLA (1), of just one SP, and

only once in 24 hours. Note that executing every of optimization took at most 50 seconds, which is largely compatible with the 10 minutes re-optimization.

# 7. Conclusion and perspectives

This paper introduces a novel approach to minimize dynamic power consumption of a physical network with multiple slices, while satisfying their SLAs. We model the problem as capacity dimensioning of multiple Jackson networks coexisting in the same resource-constrained network. We propose an iterative resolution method, which we call JER-NS. Our evaluation shows that JER-NS achieves up to 60% savings compared to proportional dimensioning approaches, without violating SLAs.

A bi-level optimization could be studied, with placement in the upper level and resource dimensioning in the bottom level. This could allow turning off physical nodes and links that are left unused. Moreover, strategies dealing with extremely high loads can be associated with JER-NS, to decide on possible slice rejection.

# Acknowledgement

This work was partially funded by Beyond5G, a project of the French Government’s recovery plan “France Relance”.

# References

[1] S. Sharma, et al., Vnf availability and sfc sizing model for service provider networks, IEEE Access (2020).

[2] A. Magalhaes, et al., Repo: A microservices elastic management system for cost reduction in the cloud, in: IEEE ISCC, 2018.

[3] S. Yang, et al., Recent advances of resource allocation in network function virtualization, IEEE TPDS (2020).

[4] M. Elkael, et al., Monkey business: Reinforcement learning meets neighborhood search for virtual network embedding, Computer Networks (2022).

[5] Badri, et al., Energy-aware application placement in mobile edge computing: A stochastic optimization approach, IEEE TPDS (2020).

[6] HUAWEI, Green 5g lights the way to a low-carbon future, https://www.huawei.com/en/huaweitech/publication/winwin/40/green-5g-low-carbon-future (2021).

[7] Just enough networks, ANR Project (2023-27).

[8] W. Huang, et al., Dimensioning resources of network slices for energy-performance trade-off, in: IEEE ISCC, 2022.

[9] M. Zukerman, Introduction to queueing theory and stochastic teletraffic models, ArXiv (2013).

[10] K. Leonard, Communication Nets: Stochastic Message Flow and Delay, McGraw-Hill, 1964.

[11] L. M. Wein, Capacity allocation in generalized jackson networks, Oper. Res. Lett. (1989).

[12] A. B. Dieker, et al., Optimal resource capacity management for stochastic networks, Oper. Res. (2017).

[13] M. Elkael, et al., Joint placement, routing and resource dimensioning at the network edge for energy minimization and performance guarantees, in: IEEE Globecom, 2023.

[14] A. Chagdali, et al., Impact of slice function placement on the performance of urllc with redundant coverage, in: WiMob, 2020.

[15] G. O. Boateng, et al., Consortium blockchain-based spectrum trading for network slicing in 5g ran: A multi-agent deep reinforcement learning approach, IEEE Transactions on Mobile Computing (2023).

[16] W. da Silva Coelho, et al., Function splitting, isolation, and placement trade-offs in network slicing, IEEE Trans. Netw. Service Manag. (2022).
[17] S. Cabrera, et al., Economic feasibility of virtual operators in 5g via network slicing, Future Gener. Comput. Syst. (2020).

[18] S. Troia, et al., Performance characterization and profiling of chained cpu-bound virtual network functions, Comp. Net. (2023).

[19] N. He, et al., Leveraging deep reinforcement learning with attention mechanism for virtual network function placement and routing, IEEE TPDS (2023).

[20] X. Wang, et al., On jointly optimizing partial offloading and sfc mapping: A cooperative dual-agent deep reinforcement learning approach, IEEE TPDS (2023).

[21] Bahreini, et al., Mechanisms for resource allocation and pricing in mobile edge computing systems, IEEE TPDS (2022).

[22] Y. He, et al., Joint optimization of service chain graph design and mapping in nfv-enabled networks, Computer Networks (2022).

[23] Q. Zhang, et al., Joint optimization of chain placement and request scheduling for network function virtualization, in: IEEE ICDCS, 2017.

[24] T. S. Salem, et al., Toward inference delivery networks: Distributing machine learning with optimality guarantees, IEEE/ACM ToN (2023).

[25] W. Liang, et al., Low-latency service function chain migration in edge-core networks based on open jackson networks, J. Syst. Archit. (2022).

[26] F. E. a. o. Salem, Scalable markov decision process model for advanced sleep modes management in 5g networks, Association for Computing Machinery, 2020.

[27] J. Krzywda, et al., Power-performance tradeoffs in data center servers: DVFS, CPU pinning, horizontal and vertical scaling, Future Gener. Comput. Syst. (2018).

[28] T. Taleb, et al., Cdn slicing over a multi-domain edge cloud, IEEE Trans. Mob. Comput. (2020).

[29] V. K. K. Labs), In-place resource resize for kubernetes pods (alpha), https://kubernetes.io/blog/2023/05/12/in-place-pod-resize-alpha/ (2023).

[30] N. Saha, et al., Deep reinforcement learning approaches to network slice scaling and placement: A survey, Comm. Mag. (2023).

[31] S. Wang, et al., A dvfs based energy-efficient tasks scheduling in a data center, IEEE Access (2017).

[32] H. Kasture, et al., Rubik: Fast analytical power management for latency-critical systems, in: IEEE/ACM MICRO, 2015.

[33] 5g service-guaranteed network slicing white paper, Tech. rep., Huawei (2019).

[34] Y. Ohara, et al., Kamuee: An ip packet forwarding engine for multi-hundred-gigabit software-based networks, in: Proc. Internet Conf., 2018.

[35] D. Chemodanov, et al., A near optimal reliable composition approach for geo-distributed latency-sensitive service chains, in: IEEE INFOCOM 2019 - IEEE Conference on Computer Communications, 2019.

[36] A. J. Gonzalez, et al., The isolation concept in the 5g network slicing, in: EuCNC, 2020.

[37] B. Han, et al., A utility-driven multi-queue admission control solution for network slicing, in: IEEE INFOCOM 2019 - IEEE Conference on Computer Communications, 2019.

[38] S. Kamath, et al., Multiclass queueing network modeling and traffic flow analysis for sdn-enabled mobile core networks with network slicing, IEEE Access (2020).

[39] Q. Ye, et al., End-to-end delay modeling for embedded vnf chains in 5g core networks, IEEE Internet of Things Journal (2019).

[40] G. Garg, et al., Davis: A delay-aware vnf selection algorithm for service function chaining, in: COMSNETS, 2019.

[41] R. Ramaswamy, et al., Characterizing network processing delay, in: IEEE GLOBECOM, 2004.

[42] Red Hat, Inc., Red hat openstack platform 11 network functions virtualization planning and prerequisites guide, Tech. rep., OpenStack Team (2019).

[43] A. J. Lemoine, Networks of queues-a survey of equilibrium analysis, Manag. Sci. (1977).

[44] I. Mitrani, Note—a critical note on a result by lemoine, Manag. Sci. (1979).

[45] B. Simon, et al., Some results on sojourn times in acyclic jackson networks, Manag. Sci. (1979).

[46] P. C. Kiessler, A simulation analysis of sojourn times in a jackson network, Master's thesis, Virginia Polytechnic Inst. and State Univ. Blacksburg (1980).

[47] S. M. Ross, Introduction to Probability Models, Elsevier, 2007.

[48] Y. Li, et al., An online power metering model for cloud environment, in: IEEE NCA, 2012.

[49] A. Kansal, et al., Virtual machine power metering and provisioning, in: ACM SoCC, 2010.

[50] C. De Napoli, et al., Efficiency and green metrics for distributed data centers, Report P-26, ICAR (2016).

[51] J. Y. Jang, et al., Workload-aware optimal power allocation on single-chip heterogeneous processors, IEEE TPDS (2016).

[52] S. Saha, et al., An experimental evaluation of real-time dvfs scheduling algorithms, in: Int. Conf. High Perf. Comp. Netw. Storage Anal., 2012.

[53] R. J. Wysocki, Cpu performance scaling, 2017 intel corporation, https://docs.kernel.org/admin-guide/pm/cpufreq.html.

[54] T. Guérout, et al., Energy-aware simulation with dvfs, Simulation Modelling Practice and Theory (2013).

[55] R. Hebbar, et al., An experimental evaluation of workload driven dvfs, in: Companion of the ACM/SPEC ICPE, 2021.

[56] M. Mostowfi, et al., Saving energy in lan switches: New methods of packet coalescing for energy efficient ethernet, in: 2011 IGSC, 2011.

[57] D. Larrabeiti, et al., Towards an energy efficient 10 gb/s optical ethernet: Performance analysis and viability, Optical Switching and Networking (2011).

[58] R. Sohan, et al., Characterizing 10 gbps network interface energy consumption, in: IEEE Conf. LCN, 2010.

[59] R. H. Byrd, et al., An interior point algorithm for large-scale nonlinear programming, SIAM Journal on Optimization (1999).

[60] L. Cominardi, et al., Understanding qos applicability in 5g transport networks, in: IEEE BMSB, 2018.

[61] J. Navarro-Ortiz, et al., A survey on 5g usage scenarios and traffic models, IEEE Commun. Surv. Tutor. (2020).

[62] 3rd Generation Partnership Project (3GPP), Study on scenarios and requirements for next generation access technologies, http://www.3gpp.org/ftp/Specs/archive/38_series/38.913/ (2016).

[63] H. Zhou, et al., Knowledge transfer based radio and computation resource allocation for 5g ran slicing, in: IEEE CCNC, 2022.

[64] H. Huang, et al., Nfv and blockchain enabled 5g for ultra-reliable and low-latency communications in industry: Architecture and performance evaluation, IEEE Trans. Ind. Inform. (2021).

[65] S. R. Pokhrel, et al., Towards enabling critical mmtc: A review of urllc within mmtc, IEEE Access (2020).

[66] M. Shirvanimoghaddam, et al., Short block-length codes for ultra-reliable low latency communications, IEEE Commun. Mag. (2019).

[67] M. Alsenwi, et al., embb-urllc resource slicing: A risk-sensitive approach, IEEE Commun. Lett. (2019).

[68] Y.-J. Chen, et al., Prioritized resource reservation for reducing random access delay in 5g urllc, in: IEEE PIMRC, 2017.

[69] S. Josilo, et al., Joint wireless and edge computing resource management with dynamic network slice selection, CoRR (2020).

[70] University of Adelaide, The internet topology zoo, http://topology-zoo.org/dataset.html.

[71] S.-W. Ham, et al., Simplified server model to simulate data center cooling energy consumption, Energy and Buildings (2015).

[72] A. P. Vela, A. Vía, F. Morales, M. Ruiz, L. Velasco, Traffic generation for telecom cloud-based simulation, in: 2016 ICTON, 2016.

[73] M. A. M. Ferreira, et al., Sojourn times in jackson networks, J. Appl. Math. (2012).

[74] V. Gupta, et al., An analysis of power reduction in datacenters using heterogeneous chip multiprocessors, SIGMETRICS PER (2011).

[75] X. Fan, et al., Power provisioning for a warehouse-sized computer, in: Proc. ISCA, 2007.

[76] S. woo Ham, et al., Simplified server model to simulate data center cooling energy consumption, Energy Build. (2015).

[77] M. Tokmachev, Modeling of truncated probability distributions, in: IOP Conf.: Materials Sci. and Eng., 2018.

[78] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc. (1963).
# Appendix A. Proofs

## Appendix A.1. Proof of Proposition 1

*Proof.* Let us focus on SP s. In §3.5, we modeled it as an open Jackson network of $m = |Q_s| M/M/1$ queues. For any $q \in Q^s$, let us define utilization $\rho_q = \frac{\lambda_q}{\mu_q(r_q)}$, where $\lambda_q$ is the arrival rate of $q$ and $\mu_q(r_q)$ is the service rate (which depends on the resource $r_q$ allocated and the computational/communication complexity - see §3.5). If all queues are in steady-state, then ([9, Eqn.(517)):

$$ \bar{N}_q = \frac{\rho_q}{1 - \rho_q} = \frac{\lambda_q}{\mu_q(r_q) - \lambda_q} \quad (A.1) $$

Moreover, the mean journey time is ([9, 519]):

$$ \mathbb{E}[T^s(\mathbf{r})] = \frac{\sum_{q \in Q^s} \bar{N}_q}{\sum_{v \in V_{in}} \lambda_v^s} = \frac{1}{\lambda^s} \cdot \sum_{q \in Q^s} \frac{\lambda_q}{\mu_q(r_q) - \lambda_q} \quad (A.2) $$

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

## Appendix A.2. Proof of Proposition 2

*Proof.* In our model, we assume that requests arrive from outside following a Poisson process with arrival rate $\lambda_q$ and service time are exponentially distributed with service rate $\mu_q(r_q)$ for each queue $q \in Q^s$ of SP s. From [73, §2], the journey time $T^s(r_q)$ spent at each queue $q$ in an open Jackson network without overtaking A customer or job that arrives later at a queue can complete service before an earlier-arriving customer is a random variable following an exponential distribution with rate $\mu_q - \lambda_q$ and independent. Therefore, the total journey time of requests is the sum of journey time of each queue $q$ which belongs to the same path $\mathcal{P} \in \mathcal{PS}^s$.

The hypo-exponential distribution is defined as a series of exponential distributions with their own rate parameter. Thus, the total journey time of requests passing through any path $\mathcal{P} \in \mathcal{PS}^s$ follows hypo-exponential distribution. We derive the cumulative distribution function (§5.2.4 [47]) of the journey time experienced by a request traversing path $\mathcal{P} \in \mathcal{PS}^s$ as follows:

$$ \mathbb{P}(T^s(\mathbf{r}) \le D^s | \mathcal{P}) = 1 - \sum_{q \in \mathcal{P}} \prod_{q' \in \mathcal{P} \setminus \{q\}} \frac{\phi_{q'}(\mathbf{r})}{\phi_{q'}(\mathbf{r}) - \phi_q(\mathbf{r})} e^{-\phi_q(\mathbf{r}) \cdot D^s} \quad (A.3) $$

Where $D^s$ is the latency requirement of SP s.

Note that routing probabilities are inputs in our model. Therefore, probability $\mathbb{P}(\mathcal{P})$ of choosing path $\mathcal{P}$ can be computed as an input and $\sum_{\mathcal{P} \in \mathcal{PS}^s} \mathbb{P}(\mathcal{P}) = 1$. By the theorem of total probability:

$$ \begin{aligned} \mathbb{P}(T^s(\mathbf{r}) \le D^s) &= \sum_k \mathbb{P}(\mathcal{P}) \cdot \mathbb{P}(T_k^s(\mathbf{r}) \le D^s | \mathcal{P}) \\ &= 1 - \sum_k \mathbb{P}(\mathcal{P}) \cdot \sum_{q \in \mathcal{P}} \prod_{q' \in \mathcal{P} \setminus \{q\}} \frac{\phi_{q'}(\mathbf{r})}{\phi_{q'}(\mathbf{r}) - \phi_q(\mathbf{r})} e^{-\phi_q(\mathbf{r}) \cdot D^s} \end{aligned} \quad (A.4) $$

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

## Appendix A.3. Proof of proposition 3

*Proof.* It is well known that a CPU core's dynamic power consumption is approximately proportional to the product of its dynamic switching capacitance $C_{cap}$ and the square of the voltage $V_{vol}$ applied to the CPU core and the CPU core frequency $f$ [48]. Dynamic voltage and frequency scaling (DVFS) has been widely used to save dynamic power consumption. Note that voltage $V_{vol}(f)$ that must be applied to a CPU core increases with its clock frequency $f$. Thus, we apply DVFS into our model and consider that, in a physical node, separate CPU cores are embedded in order to be reserved for replicas of a certain component of different SPs. Therefore, the maximum dynamic power consumption of a CPU core held by physical node $v$ running at clock frequency $f$:

$$ P_{dyn,max}^{v}(f) \propto C_{cap} \cdot V_{vol}(f)^2 \cdot f. \quad (A.5) $$

In reality, only a part of this maximum power is consumed, depending on the actual CPU utilization. To model actual dynamic power consumption on a node, we refer to [74, 75], where the authors have shown that it grows linearly with the CPU utilization. CPU core utilization is the fraction of time that the core is active. CPU core utilization also depends on the clock frequency: the more the clock frequency, the less time each instruction takes and thus the less the utilization for processing the same number of requests. We denote by $\chi_q(f) \in [0, 1]$ the utilization of the core hosting component replica $q$, when clock cycle is $f$.

Based on formula [76, Eqn. (2)], the actual dynamic power of the CPU core hosting component replica $q$ is:

$$ P_{dyn}^{v}(r_q) = P_{dyn,max}^{v}(f(r_q)) \cdot \chi_q(f(r_q)) \quad (A.6) $$

where $\chi_q(f(r_q))$ is the utilization of CPU core, i.e., the fraction of time it is doing some computation. Such a fraction of time depends on the replica is placed in a core. For simplicity, we assume component replicas are not a huge number, so that we can assume a core gets at most one replica. Since $q$ is the queue corresponding to the component replica placed in a core. The utilization is:

$$ \begin{aligned} \chi_q(f(r_q)) &= \mathbb{P}[\text{core is active in any cycle}]^9 \\ &= \mathbb{P}[\text{core is active|cycle is allocated to } q] \\ &\quad \cdot \mathbb{P}[\text{cycle is allocated to } q] \\ &\quad + \mathbb{P}[\text{core is active|cycle is not allocated to } q] \\ &\quad \cdot \mathbb{P}[\text{cycle is not allocated to } q] \end{aligned} \quad (A.7) $$

We assume that the CPU core can execute $\gamma$ instructions per cycle. So, at a certain frequency $f(r_q) = \min\{f \in \mathcal{F} | f \ge r_q/\gamma\}$, the instructions per second are $r_q$. If we set a maximum percentage of usage to $r_q/(f(r_q)\gamma)$, the operating system will allocate to $q$ only a fraction $r_q/(f(r_q)\gamma)$ of CPU core cycles. Thus, the probability that the cycle is allocated to $q$ is:

$$ \mathbb{P}[\text{cycle is allocated to } q] = \frac{r_q}{(f(r_q)\gamma)} \quad (A.8) $$

<footnote n="9">⁹Law of total probability</footnote>
However, if we take any cycle allocated to $q$, in that cycle the CPU core might be active or inactive: the second case occurs when, despite the fact that the operating system has allowed queue $q$ to run in that cycle, queue $q$ has nothing to do. Therefore, the probability that, considering any cycle allocated to $q$, the CPU core will be active in that cycle is:

$$ 
\begin{aligned}
\mathbb{P}[\text{CPU core is active}|\text{cycle is allocated to } q] \\
&= \mathbb{P}[\text{queue } q \text{ is using the cycle}|\text{cycle is allocated to } q] \quad (A.9) \\
&= \rho_q, \text{ where } \rho_q = \frac{\lambda_q}{\mu_q(r_q)}.
\end{aligned}
$$

Indeed, we can consider that by means of virtualization technology, queue $q$ runs as a virtual machine or container. Therefore we can assume queue $q$ is running on a dedicated CPU core with capacity $r_q^{10}$, thus resulting in service rate $\mu_q(r_q) = \frac{1}{\alpha_q g_{c_i}^s(r_q)}$. Also note that the CPU core will be activated only if cycle is allocated to $q$, which indicates probability:

$$ \mathbb{P}[\text{core is active} | \text{cycle is not allocated to } q] = 0. $$

Then we replace the formula of $\chi_q(f(r_q))$ as follows:

$$ \chi_q(f(r_q)) = \rho_q \cdot \frac{r_q}{f(r_q)\gamma} + 0 = \frac{\alpha_q \cdot g_{c_i}^s(r_q) \cdot r_q \cdot \lambda_q}{f(r_q)\gamma} \quad (A.10) $$

Thus, the average dynamic power consumption of CPU core corresponding to a queue $q \in Q_v$:

$$ P_{dyn}^{v}(r_q) = P_{dyn,max}^{v}(f(r_q)) \cdot \frac{\alpha_q \cdot g_{c_i}^s(r_q) \cdot r_q \cdot \lambda_q}{f(r_q)\gamma} \quad (A.11) $$

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

<table><caption>Table A.5: KL divergence (A.14) for different ranges of $\omega_q = \mu_q - \lambda_q$. We used bold text to highlight the highest value for each range</caption><thead><tr><th>Routing probability</th><th>ω<sub>1,...,10</sub> &isin; [0, 10]</th><th>ω<sub>1,...,10</sub> &isin; [10, 100]</th><th>ω<sub>1,...,10</sub> &isin; [100, 1000]</th><th>ω<sub>1,...,10</sub> &isin; [1000, 10000]</th></tr></thead><tbody><tr><td>P = 0.1</td><td>0.0704&plusmn;0.0586</td><td>0.0479&plusmn;0.0357</td><td>0.0665&plusmn;0.0563</td><td>0.0952&plusmn;0.0985</td></tr><tr><td>P = 0.2</td><td>0.0528&plusmn;0.0559</td><td>0.0580&plusmn;0.0378</td><td>0.0890&plusmn;0.0799</td><td>0.0868&plusmn;0.0988</td></tr><tr><td>P = 0.3</td><td>0.0584&plusmn;0.0539</td><td>0.0821&plusmn;0.0608</td><td>0.1077&plusmn;0.0785</td><td>0.0900&plusmn;0.0580</td></tr><tr><td>P = 0.4</td><td>0.0702&plusmn;0.0490</td><td>0.1010&plusmn;0.0720</td><td>0.1366&plusmn;0.0835</td><td>0.0826&plusmn;0.0430</td></tr><tr><td>P = 0.5</td><td><b>0.0757&plusmn;0.0492</b></td><td><b>0.1055&plusmn;0.0733</b></td><td><b>0.1516&plusmn;0.0924</b></td><td>0.1008&plusmn;0.0903</td></tr><tr><td>P = 0.6</td><td>0.0743&plusmn;0.0542</td><td>0.0949&plusmn;0.0666</td><td>0.1426&plusmn;0.0980</td><td><b>0.1088&plusmn;0.1144</b></td></tr><tr><td>P = 0.7</td><td>0.0648&plusmn;0.0614</td><td>0.0725&plusmn;0.0556</td><td>0.1374&plusmn;0.0988</td><td>0.0814&plusmn;0.0799</td></tr><tr><td>P = 0.8</td><td>0.0569&plusmn;0.0564</td><td>0.0560&plusmn;0.0428</td><td>0.1028&plusmn;0.0972</td><td>0.0742&plusmn;0.0726</td></tr><tr><td>P = 0.9</td><td>0.0573&plusmn;0.0540</td><td>0.0553&plusmn;0.0592</td><td>0.0877&plusmn;0.0797</td><td>0.0664&plusmn;0.0607</td></tr></tbody></table>

## Appendix A.4. Distribution analyses and approximation

We now analyze the following two distributions: mixture of hypo-exponential distributions ($T^s$ in Prop. 2), which models the actual journey time, and approximate hypo-exponential distribution ($\tilde{T}^s$ in (20)) illustrated in Fig. A.10.

Mixture of hypo-exponential scenario:

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

One approximate hypo-exponential scenario:

<figure><img src="image_14.png" /><figcaption>Figure A.10: Distribution analysis</figcaption></figure>

The CDF of $T^s$ (A.4) is introduced in Prop. 2. Note that journey time of each queue is independent and follows an exponential distribution with rate $\omega_q = \mu_q - \lambda_q$. For any path $\mathcal{P} \in \mathcal{PS}^s$, total journey time of requests follows hypo-exponential distribution. Taking the example of Fig. A.10, $\mathcal{PS}^s = \{\mathcal{P}_1, \mathcal{P}_2\}$. There are two traversing paths $\mathcal{P}_1 = \{A, B, D\}$ and $\mathcal{P}_2 = \{A, C, D\}$, with $\mathbb{P}(\mathcal{P}_1) = P$ and $\mathbb{P}(\mathcal{P}_2) = 1 - P$, respectively. Then we obtain:

$$ \mathbb{P}(T^s \le D^s) = 1 - \left( P \cdot \sum_{q \in \mathcal{P}_1} \prod_{q' \in \mathcal{P}_1 \setminus \{q\}} \frac{\omega_{q'}}{\omega_{q'} - \omega_q} e^{-\omega_{q'} \cdot D^s} + (1-P) \cdot \sum_{q \in \mathcal{P}_2} \prod_{q' \in \mathcal{P}_2 \setminus \{q\}} \frac{\omega_{q'}}{\omega_{q'} - \omega_q} e^{-\omega_{q'} \cdot D^s} \right) $$

The CDF of $\tilde{T}^s$ is:

$$ \mathbb{P}(\tilde{T}^s \le D^s) = 1 - \sum_{q \in Q^s} \prod_{q' \ne q} \frac{\omega_{q'}}{\omega_{q'} - \omega_q} e^{-\omega_{q'} \cdot D^s} $$

In the example of Fig. A.10, we have $Q^s = \{A, B', C', D\}$.

Referring to [47, §5.2.4], the probability density function (namely $f_{T^s(\mathbf{r})}(D^s)$ and $f_{\tilde{T}^s(\mathbf{r})}(D^s)$) are as follows:

$$ f_{T^s(\mathbf{r})}(D^s) = \sum_k \mathbb{P}(\mathcal{P}_k) \cdot \sum_q \prod_{q' \in \mathcal{P}_k \setminus \{q\}} \frac{\phi_{q'}(\mathbf{r})}{\phi_{q'}(\mathbf{r}) - \phi_q(\mathbf{r})} \phi_q(\mathbf{r}) e^{-\phi_q(\mathbf{r}) \cdot D^s} $$

Where $D^s$ is the latency requirement of SP $s$, $q$ and $q'$ are queues that belong to $\mathcal{P}_k^s$.

$$ f_{\tilde{T}^s(\mathbf{r})}(D^s) = \sum_q \prod_{q' \ne q} \frac{\phi_{q'}(\mathbf{r})}{\phi_{q'}(\mathbf{r}) - \phi_q(\mathbf{r})} \phi_q(\mathbf{r}) e^{-\phi_q(\mathbf{r}) \cdot D^s} $$

Where $D^s$ is the latency requirement of SP $s$, $q$ and $q'$ are queues that belong to $Q^s$. We recall the definition of $T^s(\mathbf{r})$ in Prop. 2 and $\lambda^s$ the total date rate of user-requests for SP $s$ from outside.

**Proposition 6.** If we define a random variable $\tilde{T}^s(\mathbf{r})$ following hypo-exponential distribution with rate $\tilde{\phi}_q = \frac{r_q}{\alpha_q \cdot \Delta_q} - \frac{\lambda_q}{\Delta_q}$ and $\Delta_q = \frac{\lambda_q}{\lambda^s}$, $\forall q \in Q^s$. Then $\mathbb{E}[\tilde{T}^s(\mathbf{r})] = \mathbb{E}[T^s(\mathbf{r})]$.

*Proof.* From Prop. 2, $T^s(\mathbf{r})$ follows mixture of hypo-exponential distributions with rate $\phi_q(\mathbf{r}) = \frac{r_q}{\alpha_q} - \lambda_q, \forall q \in Q^s$. Denoting with

<footnote n="10">¹⁰Suppose that a physical CPU core has $\mathcal{X}$ MIPS (Million Instructions per second). If we allocate only $\mathcal{Y}$ MIPS to queue $q$, from our modeling viewpoint the situation is equivalent to queue $q$ running in a physical CPU of $\mathcal{Y}$ MIPS.</footnote>
$\mathbb{P}(\mathcal{P})$ the probability of choosing path $\mathcal{P}$ among the possible paths $\mathcal{P}\mathcal{S}^s$. By the theorem of total expectation, we get

$$ \mathbb{E}[T^s(\mathbf{r})] = \sum_{\mathcal{P} \in \mathcal{P}\mathcal{S}^s} \mathbb{P}(\mathcal{P}) \sum_{q \in \mathcal{P}} \frac{1}{\phi_q(\mathbf{r})} = \sum_{\mathcal{P} \in \mathcal{P}\mathcal{S}^s} \mathbb{P}(\mathcal{P}) \sum_{q \in \mathcal{P}} \frac{\alpha_q}{r_q - \alpha_q \lambda_q} $$

The expected value of $\tilde{T}^s(\mathbf{r})$ is

$$ \mathbb{E}[\tilde{T}^s(\mathbf{r})] = \sum_{q \in \mathcal{Q}^s} \frac{1}{\tilde{\phi}_q(\mathbf{r})} = \sum_{q \in \mathcal{Q}^s} \frac{\lambda_q}{\lambda^s} \cdot \frac{\alpha_q}{r_q - \alpha_q \lambda_q} \quad (A.12) $$

Regarding one queue $q$ of SP $s$, $\frac{\lambda_q}{\lambda^s}$ can be represented as the percentage of total data rate of SP $s$ from outside $\lambda^s$ that passes the queue $q$. Then the following holds:

$$ \begin{aligned} \mathbb{E}[\tilde{T}^s(\mathbf{r})] &= \sum_{q \in \mathcal{Q}^s} \sum_{\mathcal{P} \in \mathcal{P}\mathcal{S}^s} \mathbb{P}(\mathcal{P}) \cdot 1[q \in \mathcal{P}] \cdot \frac{\alpha_q}{r_q - \alpha_q \lambda_q} \quad (A.13) \\ &= \sum_{\mathcal{P} \in \mathcal{P}\mathcal{S}^s} \mathbb{P}(\mathcal{P}) \sum_{q \in \mathcal{Q}^s} 1[q \in \mathcal{P}] \cdot \frac{\alpha_q}{r_q - \alpha_q \lambda_q} = \mathbb{E}[T^s(\mathbf{r})] \end{aligned} $$

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

We now show that $\tilde{T}^s$ is a good approximation of $T^s$. The Kullback-Leibler divergence is defined as

$$ D_{KL}(f_{\tilde{T}^s(\mathbf{r})}(D^s) \| f_{\tilde{T}^s(\mathbf{r})}(D^s)) = \int_0^\infty f_{\tilde{T}^s(\mathbf{r})}(D^s) \cdot \log \frac{f_{\tilde{T}^s(\mathbf{r})}(D^s)}{f_{\tilde{T}^s(\mathbf{r})}(D^s)} dx \quad (A.14) $$

We show (A.14) under several combinations of $\omega_q = \mu_q - \lambda_q$ and 20 random runs in Tab.A.5. Observe that the error we get when approximating $T^s$ with $\tilde{T}^s$ is not negligible, but it is not extremely high. We can thus use this approximation as a base to build a surrogate problem $\text{OPT}_b$ and obtain a "good" allocation $\mathbf{r}_b$, which in any case will be verified to respect the reliability constraint under the exact journey time distribution $T^s$.

The Lemma below will be used in the proof of Prop. 4. We first define $\tilde{T}^s_b(\mathbf{r})$ as a sum of journey times on the queues of SP $s$, conditional to the journey time on each queue being $\le b_q$.

**Lemma 7.** Consider taking the decision with resource allocation $\mathbf{r}$, then

$$ \mathbb{E}[\tilde{T}^s(\mathbf{r})] \ge \mathbb{E}[\tilde{T}^s_b(\mathbf{r})] \quad (A.15) $$

*Proof.* Since $\mathbf{b}$ is the set of the upper bounds of each queue $q$, then $\tilde{T}^s_b(\mathbf{r})$ follows a truncated hypo-exponential distribution with the same $b_q$ for all $q \in \mathcal{Q}^s$. Let us define $g_{\tilde{T}^s(\mathbf{r})}(t)$ as follows:

$$ g_{\tilde{T}^s(\mathbf{r})}(t) \triangleq \begin{cases} f_{\tilde{T}^s(\mathbf{r})}(t) & t \le \sum_q b_q \\ 0 & \text{Otherwise} \end{cases} \quad (A.16) $$

where $f_{\tilde{T}^s(\mathbf{r})}(t)$ is the probability density function of hypo-exponential distribution. The probability density function of truncated hypo-exponential distribution is [77] $f_{\tilde{T}^s(\mathbf{r})}(t|\lambda, \mathbf{b}) = \frac{g_{\tilde{T}^s(\mathbf{r})}(t)}{f_{\tilde{T}^s(\mathbf{r})}(\lambda, \mathbf{b})}$, where $F_{\tilde{T}^s(\mathbf{r})}(\lambda, \mathbf{b})$ is the CDF of approximate distribution. Then the expectation of $\tilde{T}^s_b(\mathbf{r})$ is:

$$ \mathbb{E}[\tilde{T}^s_b(\mathbf{r})] = \int_0^{\sum_q b_q} t f_{\tilde{T}^s(\mathbf{r})}(t) dt = \frac{\int_0^{\sum_q b_q} t g_{\tilde{T}^s(\mathbf{r})}(t) dt}{F_{\tilde{T}^s(\mathbf{r})}(\lambda, \mathbf{b})} \quad (A.17) $$

Regarding $\tilde{T}^s(\mathbf{r})$, its expectation is $\mathbb{E}[\tilde{T}^s(\mathbf{r})] = \int_0^\infty t f_{\tilde{T}^s(\mathbf{r})}(t) dt$. Note that when $\mathbb{E}[\tilde{T}^s(\mathbf{r})] \ge \sum_q b_q$, (A.15) is valid because $\mathbb{E}[\tilde{T}^s_b(\mathbf{r})]$ must be smaller than its upper bound. To complete this proof, we need to prove (A.15) in the case that $\mathbb{E}[\tilde{T}^s(\mathbf{r})] \le \sum_q b_q$:

$$ \mathbb{E}[\tilde{T}^s_b(\mathbf{r})] - \mathbb{E}[\tilde{T}^s(\mathbf{r})] \le 0 \quad (A.18) $$

$$ \Leftrightarrow \frac{\int_0^{\sum_q b_q} t g_{\tilde{T}^s(\mathbf{r})}(t) dt}{F_{\tilde{T}^s(\mathbf{r})}(\lambda, \mathbf{b})} - \int_0^\infty t f_{\tilde{T}^s(\mathbf{r})}(t) dt \le 0 \quad (A.19) $$

$$ \Leftrightarrow F_{\tilde{T}^s(\mathbf{r})}(\lambda, \mathbf{b}) \ge \frac{\int_0^{\sum_q b_q} t f_{\tilde{T}^s(\mathbf{r})}(t) dt}{\int_0^\infty t f_{\tilde{T}^s(\mathbf{r})}(t) dt} \quad (A.20) $$

From (A.12), we have $\mathbb{E}[\tilde{T}^s(\mathbf{r})] = \int_0^\infty t f_{\tilde{T}^s(\mathbf{r})}(t) dt = \sum_{q \in \mathcal{Q}^s} \frac{1}{\tilde{\phi}_q(\mathbf{r})}$.

Then recall the probability density function of $\tilde{T}^s(\mathbf{r})$ ([47, §5.2.4]):

$$ f_{\tilde{T}^s(\mathbf{r})}(t) = \sum_q \prod_{q' \ne q} \frac{\tilde{\phi}_{q'}(\mathbf{r})}{\tilde{\phi}_{q'}(\mathbf{r}) - \tilde{\phi}_q(\mathbf{r})} \tilde{\phi}_q(\mathbf{r}) e^{-\tilde{\phi}_q(\mathbf{r}) \cdot t} \quad (A.21) $$

Let $C_q \triangleq \prod_{q' \ne q} \frac{\tilde{\phi}_{q'}(\mathbf{r})}{\tilde{\phi}_{q'}(\mathbf{r}) - \tilde{\phi}_q(\mathbf{r})}$, $\forall q \in \mathcal{Q}^s$ and $B = \sum_q b_q$, note that $b_q$ is identical for all queues $q$.

$$ \int_0^B t f_{\tilde{T}^s(\mathbf{r})}(t) dt = \int_0^B \sum_q C_q \tilde{\phi}_q(\mathbf{r}) t e^{-\tilde{\phi}_q(\mathbf{r}) \cdot t} dt \quad (A.22) $$

$$ = \sum_q C_q \int_0^B \tilde{\phi}_q(\mathbf{r}) t e^{-\tilde{\phi}_q(\mathbf{r}) \cdot t} dt \quad (A.23) $$

$$ = \sum_q -C_q \left( t + \frac{1}{\tilde{\phi}_q(\mathbf{r})} \right) e^{-\tilde{\phi}_q(\mathbf{r}) \cdot t} \Big|_0^B \quad (A.24) $$

$$ = \sum_q \frac{C_q}{\tilde{\phi}_q(\mathbf{r})} - \sum_q C_q \left( B + \frac{1}{\tilde{\phi}_q(\mathbf{r})} \right) e^{-\tilde{\phi}_q(\mathbf{r}) \cdot B} \quad (A.25) $$

Then we recall (A.12):

$$ \mathbb{E}[\tilde{T}^s(\mathbf{r})] = \int_0^\infty t f_{\tilde{T}^s(\mathbf{r})}(t) dt = \sum_q \frac{1}{\tilde{\phi}_q(\mathbf{r})} \quad (A.26) $$

$$ = \sum_q -C_q \left( t + \frac{1}{\tilde{\phi}_q(\mathbf{r})} \right) e^{-\tilde{\phi}_q(\mathbf{r}) \cdot t} \Big|_0^\infty = \sum_q \frac{C_q}{\tilde{\phi}_q(\mathbf{r})} \quad (A.27) $$

Also, we recall that $\mathbb{E}[\tilde{T}^s(\mathbf{r})] = \sum_q \frac{1}{\tilde{\phi}_q(\mathbf{r})}$ from property of hypo-exponential distribution. Then we obtain:

$$ \begin{aligned} \frac{\int_0^B t f_{\tilde{T}^s(\mathbf{r})}(t) dt}{\int_0^\infty t f_{\tilde{T}^s(\mathbf{r})}(t) dt} &= 1 - \left( \frac{\sum_q C_q (B + \frac{1}{\tilde{\phi}_q(\mathbf{r})}) e^{-\tilde{\phi}_q(\mathbf{r}) \cdot B}}{\sum_q \frac{C_q}{\tilde{\phi}_q(\mathbf{r})}} \right) \\ &= 1 - \left( \frac{\sum_q C_q (B + \frac{1}{\tilde{\phi}_q(\mathbf{r})}) e^{-\tilde{\phi}_q(\mathbf{r}) \cdot B}}{\sum_q \frac{C_q}{\tilde{\phi}_q(\mathbf{r})}} \right) \le 1 - \left( \frac{\sum_q C_q (B + \frac{1}{\tilde{\phi}_q(\mathbf{r})}) e^{-\tilde{\phi}_q(\mathbf{r}) \cdot B}}{B} \right) \end{aligned} $$

$$ = 1 - \left( \sum_q C_q e^{-\tilde{\phi}_q(\mathbf{r}) \cdot B} + \frac{\sum_q \frac{C_q}{\tilde{\phi}_q(\mathbf{r})} e^{-\tilde{\phi}_q(\mathbf{r}) \cdot B}}{B} \right) $$
In addition, we recall (A.21) and we know that $\tilde{\phi}_q \ge 0, \forall q \in Q^s$.

Thus, it is obvious that $\frac{\sum_q \frac{c_q}{\tilde{\phi}_q(r)} e^{-\tilde{\phi}_q(r) \cdot B}}{B} \ge 0$. Regarding $F_{\tilde{T}^s(\mathbf{r})}(\lambda, \mathbf{b})$:

$$F_{\tilde{T}^s(\mathbf{r})}(\lambda, \mathbf{b}) = \mathbb{P}(\tilde{T}^s(\mathbf{r}) \le B) \quad (A.28)$$

$$= 1 - \sum_{q \in Q^s} \prod_{q' \in Q^s \setminus \{q\}} \frac{\tilde{\phi}_{q'}(\mathbf{r})}{\phi_{q'}(\mathbf{r}) - \tilde{\phi}_q(\mathbf{r})} e^{-\tilde{\phi}_q(\mathbf{r}) \cdot B} \quad (A.29)$$

$$= 1 - \sum_q C_q e^{-\tilde{\phi}_q(\mathbf{r}) \cdot B} \ge \frac{\int_0^B t f_{\tilde{T}^s(\mathbf{r})}(t) dt}{\int_0^\infty t f_{\tilde{T}^s(\mathbf{r})}(t) dt} \quad (A.30)$$

□

## Appendix A.5. Proof of proposition 4

*Proof.* We resort to Hoeffding's inequality [78] that ensures that, if $X_1, ..., X_n$ are independent random variables such that $0 \le X_i \le b_i$, then for all $t > 0$

$$\mathbb{P}\left(\sum_{i=1}^{n} X_i - \mathbb{E}\left[\sum_{i=1}^{n} X_i\right] \ge t\right) \le \exp\left(\frac{-2t^2}{\sum_{i=1}^{n} (b_i)^2}\right) \quad (A.31)$$

Recall that $\tilde{T}_b^s(\mathbf{r})$ is defined as a sum of $T_q^{sej}$ of each queue $q \in Q^s$, conditional to the journey time on each queue is smaller than $b_q$. Therefore, we can apply Hoeffding's inequality:

$$\mathbb{P}(\tilde{T}_{\mathbf{b}}^{s}(\mathbf{r}) - \mathbb{E}[\tilde{T}_{\mathbf{b}}^{s}(\mathbf{r})] \ge t) \le \exp\left(-2t^2 / \sum_{q \in Q^s} (b_q)^2\right). \quad (A.32)$$

If $t^s$ is as in (21), using (A.32) we get

$$\mathbb{P}(\tilde{T}_{\mathbf{b}}^{s}(\mathbf{r}) - \mathbb{E}[\tilde{T}_{\mathbf{b}}^{s}(\mathbf{r})] \ge t^s) \le 1 - R_s, \forall \text{SP s} \quad (A.33)$$

Let us know assume that $\mathbf{r}$ is such that (25) holds: $\mathbb{E}[\tilde{T}^s(\mathbf{r})] = D^s - t^s$. We know that $\tilde{T}_b^s(\mathbf{r})$ is bounded by $b_q$ for each queue $q$. From Lemma. 7, we have $\mathbb{E}[\tilde{T}^s(\mathbf{r})] \ge \mathbb{E}[\tilde{T}_b^s(\mathbf{r})]$. Then

$$\begin{aligned} 1 - R^s &\ge \mathbb{P}(\tilde{T}_{\mathbf{b}}^s(\mathbf{r}) - \mathbb{E}[\tilde{T}_{\mathbf{b}}^s(\mathbf{r})] \ge t^s) \\ &= \mathbb{P}(\tilde{T}_{\mathbf{b}}^s(\mathbf{r}) \ge \mathbb{E}[\tilde{T}_{\mathbf{b}}^s(\mathbf{r})] + t^s) \\ &\ge \mathbb{P}(\tilde{T}_{\mathbf{b}}^s(\mathbf{r}) \ge \mathbb{E}[\tilde{T}^s(\mathbf{r})] + t^s) \\ &\ge \mathbb{P}(\tilde{T}_{\mathbf{b}}^s(\mathbf{r}) \ge (D^s - t^s) + t^s) = \mathbb{P}(\tilde{T}_{\mathbf{b}}^s(\mathbf{r}) \ge D^s) \quad (A.34) \end{aligned}$$

Therefore, $\mathbb{P}(\tilde{T}_{\mathbf{b}}^s(\mathbf{r}) \ge D^s) \le 1 - R^s$

$$\Rightarrow 1 - \mathbb{P}(\tilde{T}_{\mathbf{b}}^s(\mathbf{r}) \ge D^s) \ge 1 - (1 - R^s) \quad (A.35)$$

$$\Rightarrow \mathbb{P}(\tilde{T}_{\mathbf{b}}^s(\mathbf{r}) \le D^s) \ge R^s, \forall \text{SP s} \quad (A.36)$$

□

## Appendix A.6. Proof of proposition 5

*Proof.* As defined in §5.1, the journey time of each queue $q$ is $T_q^{sej}(r_q)$, within the Jackson network, follows an exponential distribution with mean $\mathbb{E}[T_q^{sej}(r_q)]$. Consequently, its CDF is:

$$\mathbb{P}(T_q^{\text{sej}}(r_q) \le D_q) = 1 - \exp\left(-\frac{D^q}{\mathbb{E}[T_q^{\text{sej}}(r_q)]}\right), \forall D_q > 0 \quad (A.37)$$

If we initialize $b_q = \sqrt{\frac{-32}{25 \cdot N^s \cdot \ln(1 - R^s)}} \cdot D^s, \forall q \in Q^s, \forall \text{SPs}$, combined with (21) in Prop. 4, then we get $t^s = \frac{4}{5}D^s$. From (25), we have $\mathbb{E}[\tilde{T}^s(\mathbf{r})] = \frac{1}{5}D^s$. Thanks to Prop. 6 and (17), we get:

$$\mathbb{E}[\tilde{T}^s(\mathbf{r})] = \mathbb{E}[T^s(\mathbf{r})] = \sum_{q \in Q^s} \mathbb{E}[T_q^{\text{sej}}(r_q)] = \frac{1}{5} N^s \cdot D^q \quad (A.38)$$

$$\Rightarrow \mathbb{E}[T_q^{\text{sej}}(r_q)] = \frac{1}{5} D^q, \forall q \in Q^s \quad (A.39)$$

Taking (A.39) into (A.37), by simple calculation, $P(T_q^{sej}(r_q) \le D_q) = 99.999\%$. Observe that the total latency requirement $D^s$ of SP $s$ is provided as input, and the routing function of SP $s$ provides the number of queues $N^s$ traversed by each request. Consequently, if we allocate $r_q$ such that (A.39) is satisfied, for each SP $s$, the probability that total journey time $\tilde{T}^s(\mathbf{r})$ is smaller than $D^s = N^s \cdot D^q$ is shown as follows:

$$\mathbb{P}[\tilde{T}^s(\mathbf{r}) \stackrel{(17)}{=} \sum_{q \in Q^s} T_q^{\text{sej}}(r_q) \le D^s] = 0.99999^{N^s} \quad (A.40)$$

If we assume $\max(N^s) = 1000$ which means the request can traverse maximum 1000 queues for each SP $s$, then we obtain: $\mathbb{P}[\tilde{T}^s(\mathbf{r}) \le D^s] \ge 0.99999^{1000} \ge 99\%$. □

## Appendix B. Dichotomy method for $b_q$

### Algorithm 2 Dichotomy method $b_q$

**Input:** $b_q^s$: Initialization value of $b_q^s$: $R_s(b)$: Current reliability calculated from CDF of SP $s$ under $b$; $R^s$: Reliability of SP $s$; step: Steps of adjusting $b^s$

**Output:** **b**: Vector of $b^s$ ($\forall q \in SP s, b_q^s$ are identical)

1: # Initialization phase

2: if step == 1 then

3: $B^{\text{upp.s}} \leftarrow 0, B^{\text{low.s}} \leftarrow 1, \text{round}^s \leftarrow 1$

4: end if

5: for Each SP $s$ do

6: &nbsp;&nbsp;&nbsp;&nbsp; if $R_s(b) > R^s$ then

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if $B^{\text{upp.s}} == 0$ then $\text{round}^s \leftarrow 2^{\text{step}}$ else $B^{\text{upp.s}} \leftarrow \text{round}^s$

8: &nbsp;&nbsp;&nbsp;&nbsp; else if $R_s(b) < R^s$ then

9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if $B^{\text{upp.s}} == 0$ then

10: $B^{\text{upp.s}} \leftarrow 2^{\text{step}}$

11: $\text{round}^s \leftarrow B^{\text{low.s}} + \frac{B^{\text{upp.s}} - B^{\text{low.s}}}{2}$

12: else

13: $B^{\text{low.s}} \leftarrow \text{round}^s$

14: $\text{round}^s \leftarrow B^{\text{low.s}} + \frac{B^{\text{upp.s}} - B^{\text{low.s}}}{2}$

15: end if

16: end if

17: $b^s \leftarrow \frac{b^s}{\text{round}^s}$

18: end for

19: step $\leftarrow$ step + 1

20: return **b**