Large-scale workflow placement in serverless computing using integer nonlinear programming

1

Large-scale workflow placement in serverless computing using integer nonlinear programming

arXiv:2608.14427v1 [cs.DC] 14 Aug 2026

Joshua Adamek1 , Natalie Carl2 , Trever Schirmer2 , Moritz Heinlein1 , David Bermbach2 and Sergio Lucia1

Abstract—Serverless edge computing has become a powerful cloud framework that enables the execution of large workflows without the need for the user to manage the underlying servers and edge devices. In this work, we address the challenge of deploying these workflows on a large number of different existing servers and edge devices such that monetary costs for the users and workflow evaluation times are minimized. To this end, the workflow and cloud node attributes are modeled in a mathematical framework. As a result, we present a novel model of the optimal placement problem as a nonlinear integer program. To solve both the issues of scaling towards a larger number of cloud/edge nodes as well as decomposed knowledge of node attributes, we propose a novel decomposition strategy. In a case study, we show the beneficial scaling properties of the decomposition approach and a mean improvement of 10% against a simple deployment heuristic. Index Terms—Cloud computing; Optimal Scheduling; Integer programming

I. I NTRODUCTION Serverless computing has emerged as a promising cloud computing paradigm for Internet of Things (IoT) applications [21]. As the user interaction with the cloud platform is decoupled from the underlying physical servers, this offers flexibility and easier usage. This general idea motivates a Functions-asa-Service (FaaS) architecture [34], where deployment requires only functions and their data or software dependencies, while placement on physical devices is managed entirely by the cloud management system [8]. FaaS platforms have gained attention in both research [3] and practice [24], particularly for IoT applications involving large numbers of dependent functions, also referred to as workflows [15]. The decomposition of workflows into functions and their deployment represents one of the primary use cases for FaaS [29]. Past literature distinguishes between the workflow deployment operation, commonly referred to as the placement problem [11], and the scheduling operation, where a deployed workflow is selected for each user request. Both workflow placement and scheduling have been extensively studied in the literature [11]. To efficiently utilize cloud resources, placement is typically optimized with respect to objectives such as latency, execution time, monetary cost, resource utilization, and energy efficiency [11, 23, 27]. *This work has been funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Projektnummer 495343202. 1 Joshua Adamek, Moritz Heinlein and Sergio Lucia are with the Chair of Process Automation Systems at Technische Universität Dortmund, EmilFigge-Str. 70, 44227 Dortmund, Germany. 2 Natalie Carl, Trever Schirmer, and David Bermbach are with the Scalable Software Systems Research Group at Technische Universität Berlin, Einsteinufer 17, 10587 Berlin.

Provider 1

Provider n

Region 1

Region n

User

User

Fig. 1: Decentralized serverless architecture considered in this work. We consider a mixture of cloud, fog and edge computation nodes of different providers and locations as well as different attributes of the considered nodes. Cloud nodes are clustered by providers, edge/fog nodes by region of operation.

As described in [11], existing placement approaches can be broadly classified into machine learning-based [33, 30, 22], heuristic-based [7, 26], and model-based methods [9, 6, 4, 5, 14, 2, 36]. Heuristic approaches scale well to large workflow and cloud infrastructures but generally produce suboptimal solutions [11]. Consequently, they have been widely adopted in practical serverless platforms such as XFaaS [24] and ECO [1]. Machine learning-based and model-based approaches, on the other hand, can provide optimal or near-optimal placements but face scalability challenges. Learning-based methods struggle with representing large workflow and infrastructure states and require substantial training data, typically targeting infrastructures with only 10–50 nodes [32]. Nevertheless, machine learning has also been successfully applied to large-scale serverless systems for improving placement and scheduling decisions based on runtime observations [7]. Model-based approaches formulate workflow placement as an optimization problem based on mathematical models of workflows and cloud infrastructures. Existing formulations commonly represent workflows as directed acyclic graphs [16] and cloud infrastructures as node-based networks [33]. Two major challenges remain. First, the computational complexity of solving these optimization problems typically grows exponentially with the number of workflow functions and cloud nodes, limiting their applicability to large-scale deployments. While previous work has addressed the decomposition of large workflows [35], cloud decomposition has received considerably less attention [10], particularly in the context of optimal

This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

2

placement. As FaaS infrastructures evolve from centralized cloud deployments toward geographically distributed cloud, fog, and edge environments spanning multiple providers [1, 20], scalable optimization over large numbers of compute nodes becomes increasingly important. Second, the actual placement cost depends on the stochastic sequence of user requests and the resulting workflow selection during runtime [19]. Since modeling all possible request scenarios is computationally intractable [19, 11], many optimization-based approaches neglect the scheduling phase and instead optimize surrogate objectives such as latency or execution time [5]. Furthermore, many optimization methods rely on shortest-path formulations for DAG-based workflows [9, 31]. Although recent work has proposed linear optimization models [13], there remains a gap in modeling more complex workflow and infrastructure characteristics, including parallel workflow branches, data dependencies, and communication costs, within a nonlinear optimization framework. Advances in mixed-integer nonlinear optimization solvers, such as Gurobi [12] and BARON [28], now make such formulations computationally tractable while naturally supporting multi-objective optimization [17]. This paper presents a mathematical framework for workflow placement in large-scale serverless architectures. To address the identified research gaps, the main contributions are: We propose a mathematical model for the workflow placement problem for which we can provide a hierarchical decomposition strategy that addresses the scalability and privacy challenges arising in large-scale decentralized serverless architectures. The proposed approach exhibits logarithmic growth in computational demand with respect to the number of cloud nodes. • Into this a mathematical model we explicitly incorporate the workflow selection strategy. To account for waiting times during online execution, we introduce utilizationbased costs for both compute nodes and workflow deployments. • Additionally, we incorporate recently proposed improvements to the workflow modeling, such as data dependencies, parallel branches of workflows and data transmissions costs into this framework. • The placement problem is formulated as a multi-objective optimization problem and we analyze the trade-offs between competing objectives using Pareto analysis. • The scalability and performance of the proposed approach is evaluated through extensive simulation studies. Additionally, we analyze real world applicability of the approach through robustness analysis against incorrect parameter estimation during deployment.

•

The remainder of this paper is organized as follows: Section II introduces the modeling framework, including attributes for workflows and nodes, Section III formulates the optimal placement problem and presents a decomposed solution enabling scalable algorithms for distributed clouds. Section IV provides case studies demonstrating advantages such as scalability to larger problems, adaptability in multi-objective settings, and comparison to heuristic approaches. Section V concludes with

final remarks and outlook. II. M ODELING OF PLACEMENT AND SELECTION OF WORKFLOWS

A. Workflow modeling In the following, we establish the modeling framework for the workflows considered in this work. Previous work commonly models workflows as directed acyclic graphs [9, 31]. We follow this general representation, but adapt it to the requirements of the proposed MINLP formulation for workflow placement in decentralized serverless architectures. In particular, the model is designed such that placement decisions, data transfers, dependencies between functions, and parallel workflow branches can be represented explicitly and later decomposed according to the regional structure of the infrastructure. We also include parallel workflow branches, as considered in [31]. The novelty of the modeling step therefore lies not in the graph-based workflow representation itself, but in its integration into a decomposable placement formulation for large-scale FaaS infrastructures. A workflow s consists of nfunc functions. Each workflow is deployed to the cloud/edge structure ndeployments times. Each function is stateless [8], meaning that all required data dependencies and inputs are provided externally, and a function is executed only once within a workflow. We assume that every function in a workflow is executed each time the workflow is invoked. The workflow structure is illustrated in Fig. 2. We allow for nbranches different branches within each workflow. To define a workflow, we introduce variables bc,m , which equals one if function m ∈ {0, . . . nfunc −1} belongs to branch c ∈ {0, nbranches − 1}. Furthermore, we set am,m̃ = 1 if function m̃ follows function m, indicating that function m must be executed before data can be transferred between these two functions. Each function has an estimated computational demand Rfunc,m , defined by its computation time tfunc,m and memory usage RAMm . This demand is assumed to be fixed such that Rfunc,m = RAMm tfunc,m , which is treated as a constant value.

1

3

2

0

4 5

7 6

Fig. 2: Structure of a workflow with eight functions and three branches. In this example, b0,1 = 1 indicates that function 1 belongs to branch 0, while a1,2 = 1 shows that function 2 succeeds function 1. In addition to computational demand, each function sends data dsend to its successor within the respective branch once execution finishes. The first function of a workflow receives input data din from the user invoking the workflow. Figure 2

3

illustrates these data flows required for completing the workflow. Furthermore, each function might require dependency data ddata , which are stored physically on nodes within the serverless architecture.

Provider 1

Provider 1

B. Serverless infrastructure modeling We consider a hierarchical serverless edge-fog-cloud architecture rather than a fully peer-to-peer connected infrastructure. The modeled infrastructure contains all compute nodes that may host workflow functions, including edge nodes close to users, optional fog or regional nodes, and cloud nodes operated by one or multiple providers. User devices are modeled as request origins and are considered candidate nodes for function placement as we assume that these leave nodes explicitly provide computational resources. Edge and fog nodes may represent on-premises or regionally deployed resources, while cloud nodes are typically grouped according to their provider. The proposed model is agnostic to the ownership of individual nodes. Differences between providers, regions, and node types are captured through their latency, cost, speedup, and resource attributes. However, with this particular grouping, we ensure that every provider node attributes have to be shared to the overall architecture, providing a realistic real world setting for the serverless architecture. The task addressed by the placement problem is to assign each function m of every workflow n to a physical device within the serverless structure, referred to as a node. We define the serverless structure as a set of nodes i ∈ {0, . . . , nnodes }. These nodes are divided into edge nodes and cloud nodes. In this modeling framework, cloud nodes provide higher computational power, which can reduce the computation time of a function m. In our approach, we assume that executing functions on cloud nodes incurs monetary cost, whereas computations on edge nodes are considered free, but the modeling approach is not limited to this assumption. Furthermore, we consider multiple participants in the cloud environment. Each cloud node belongs to an entity (e.g. company or provider) that defines its attributes. For each provider, we assume a constant price to execute one megabyte for one second on its devices, denoted by pRAM . This assumes a linear pricing model for the number of CPUs involved in executing a function. Additionally, we define a constant price for sending or receiving one megabyte of data as psend , and a cost for transferring dependency data required for function execution as pdata per megabyte. The resulting topology is represented as a hierarchy of regions and providers. Nodes within the same region or provider can communicate through local links, whereas communication between different regions or providers is routed through representative head nodes. These head nodes may correspond to physical gateways, provider endpoints, or logical aggregation points used by the orchestration layer. Consequently, the architecture is not assumed to be fully connected at the physical node level. Instead, the hierarchical representation reflects practical decentralized deployments in which detailed information is locally available within regions or providers, while only aggregated information is exchanged between them. Figure 3 illustrates the proposed structure and

User

User

Region 1

Region 1

(a) Assumed model of con- (b) Non-scalable model of nections in the serverless ar- connections in the serverless chitecture. architecture.

Fig. 3: General connection structure of the serverless architecture. Cloud providers and edge nodes are distinguished. Requests from users originate from edge nodes only. Cloud nodes are clustered by provider or region. Connections between providers or regions exist through single links, as shown on the left. A fully connected topology, as shown on the right, is neither efficient nor realistic when different providers are involved. connectivity of the serverless architecture using a simplified example. The bottom level represents user nodes at the edge from which requests originate during workflow execution. Each connection between node i and node j is characterized by an estimated latency Li,j . As shown in Fig. 3b, an idealized setting would allow all nodes to be fully connected so that data could be transferred freely among them. In practice, especially with many providers and users, a separation occurs as depicted in Fig. 3a. It is reasonable to assume that regions or providers can communicate only through single head node links connecting their respective top-level representatives. This leads naturally to a hierarchical decomposition into regions and providers. In the simple example, there are two levels in the hierarchy: level zero contains two head nodes (region one and provider one), while level one includes three subordinate nodes per region/provider. We now establish notation for indexing these hierarchical levels in general form with levels indexed by l ∈ {0, . . . , nl − 1}. At each level l, we consider nregions,l regions/providers indexed by r ∈ {0, . . . , nregions,l − 1}, each containing nnodes,l,r individual nodes indexed by i ∈ {0, . . . , nnodes,l,r − 1}. The number of regions at level l is therefore the number of nodes at level (l − 1): nregions,l−1

nregions,l =

X

nnodes,l−1,r .

s=0

In this setting, latencies are defined for every connection between two nodes within the same region such that Ll,r,i,j denotes the latency between nodes i and j in region s at level r. To navigate within the regional structure we define the

4

Algorithm 1 Latency calculation for regionally structured serverless architectures. Require: Indices i and j of the physical devices Li,j = 0 and l = nl − 1 ĩ = curr node(l, i), and j̃ = curr node(l, j) si = curr region(l, i) and sj = curr region(l, j) while si ̸= sj do Li,j = Li,j + Ll,ri ,0,ĩ + Ll,rj .0,j̃ ĩ = succ node(l, ri ) and j̃ = succ node(l, rj ) ri = succ region(l, ri ) and rj = succ region(l, rj ) Li,j = Li,j + Ll,ri ,ĩ,j̃ following four functions: Given a node i in level l (that is the overall node number in the entire level over all regions in this level), we define the function r = curr region(l, i) that outputs the current region of this node, while ĩ = curr node(l, i) is the index of the node within this region (that is the local node number in this region starting from the index zero in each region). Likewise, for a region s in level r, we define the successor node ĩ = succ node(l, r) in level l − 1, which is the index of the node in the successor region r̃ = succ region(l, r). The latencies between two nodes i and j can be calculated according to Algorithm 1. C. Operation modeling We model the considered architecture as a serverless FaaS environment, where resource management, orchestration, deployment, and workflow selection are handled by the serverless platform. We assume that multiple cloud providers and edge or fog regions are jointly organized through a logical orchestration layer. During placement, a deploying user requests the deployment of one or multiple workflows. The orchestration layer then decides on which nodes the individual functions of each workflow are placed. In a centralized setting, this decision is made by one logical entity with access to the complete infrastructure model. In the decomposed setting, placement decisions are distributed across the hierarchy, such that regional or provider head nodes solve local subproblems using local information. For every individual deployed workflow that is for the number of instances of one specific workflow we solve one placement problem, to reduce the complexity of the underlying optimization problem. During runtime, users invoke workflows through requests originating from leaf nodes of the architecture. These leaf nodes may also provide computational resources and can therefore be part of the placement decision. For each request, the orchestration layer applies a selection policy that determines which deployed workflow instance is used. Thus, the user only submits deployment and invocation requests, while placement, selection, and execution are managed by the serverless platform. After the initial placement we assume no rescheduling of the placed workflow instances during the online scheduling phasse. III. S OLUTION STRATEGY A. Decision variables and assumed problem structure

In the following we setup the optimization problem for the placement of the workflows in the proposed serverless architecture. There already exists linear mixed-integer optimization model formulations [13]. However in this work, we consider more complex workflow and infrastructure characteristics, including parallel workflow branches, data dependencies, and communication costs, which require formulating the optimization as a mixed-integer nonlinear problem. Since mixed-integer nonlinear programs are computationally demanding, we establish a decomposition approach to enable deployment on larger serverless architectures. To set up the placement problem, the optimization variables defining the placement must be established. Since each workflow t is deployed separately, we omit the index t in our problem formulation for brevity. Each function m of workflow n must be placed on a node i within the serverless architecture. Therefore, we define the decision variable Pn,m,i to be one if this function is placed on node i, and zero otherwise. For every function, exactly one node is selected, such that X Pn,m,i = 1 , i

for all functions m in workflow n. The main difficulty in describing the cost function arises from the fact that total cost does not directly result from workflow placement itself but rather from user selection of workflows during execution. Consequently, we aim to minimize the expected selection cost incurred by users invoking workflows. To model user behavior, we define a variable Hk,n indicating which workflow is selected by user k. In general, this variable is not known in advance. It represents a runtime decision made during operation. Optimal choices may differ depending on request conditions. Modeling such behavior leads to a twostage stochastic optimization problem [25] , where placement variables Pn,m,i would need to be optimized for all possible realizations of Hk,n . Since integer-based two-stage stochastic problems are computationally demanding [25] , they are unsuitable for large-scale serverless architectures. We therefore assume a deterministic selection policy Hk,n , which we determine prior to execution and include as decision variables in the placement problem, ensuring that exactly one workflow is selected for each user request: X Hk,n = 1 , n

for every possible user k. In turn, this policy cannot react to the stochastic nature of the user requests, leading to possible blocking of resources or deployed functions, amplifying the need to address this issue in the placement problem as proposed in the next subsection. B. Problem definition After modeling the workflows and nodes in the serverless architecture, we next define costs and constraints for the placement problem. We place each workflow separately, that is, each workflow s is placed by solving the following optimization problem. We consider two competing objectives that influence

5

TABLE I: Overview of the model parameters used in the main optimization problem (1). Notation k i,j l m n r c Hk,n Pn,m,i Cm,i Dm,i,j Tn Tm,i Ll,r,i,j pRAM psend pdata ddata dsend tfunc,m RAMm Rfunc,m nfunc nbranches ndeployments bc,m am,m̃ xi,m nl nregions,l nnodes,l,r

Definition Index used to address leaves Indices used to address general nodes in the cloud Index used to address levels in the serverless architecture Index used to address functions within a workflow Index used to address different deployments of the same workflow Index used to address a region in a level in the serverless architecture Index used to address the branches of the workflow Variable selecting workflow n for a request from leaf k Variable placing function m from workflow n on the node i Cost to execute function m on node i Cost to send data generated by function m from node i to node j Maximum time to execute workflow n Time to execute function m on node i Latency between node i and j in region s in level r of the serverless architecture. If only one region is considered this is shorten to Li,j . Cost to execute one MB of RAM for one second Cost to send 1 MB of output data from a function Cost to transfer 1 MB of data needed for the execution of a function Amount of data needed for the execution of a function Amount of output data send from a function Estimated running time of function m on a normal device Estimated RAM usage of function m Constant computational demand of function m Number of functions in a workflow Number of branches of workflow Number of deployments of workflow s Indicates if function m is in branch c Indicates if function m̃ is a successor of function m Estimated speedup of large functions deployed on cloud node m Number of levels considered in the serverless architecture Number of regions considered in level l in the serverless architecture Number of nodes in region r on level l in the serverless architecture

the placement: the time required to evaluate a workflow and the monetary cost incurred by a user when executing it. Using the modeling introduced in the previous section, these costs can be expressed as functions of the placement and selection decision variables, as well as parameters describing nodes and workflows (summarized in Table I). We denote by Tn,c the time required to evaluate branch c of workflow n. The overall evaluation time depends on the slowest branch among all nbranches branches of a workflow. To include this dependency in the optimization problem, we introduce an auxiliary variable Tn , constrained by

Tn ≥ Tn,c

∀c ∈ {0, nbranches } .

Each branch time Tn,c is computed as the sum of function evaluation times for all functions m within that branch and latencies between nodes hosting consecutive functions. Con-

sequently, we can formulate XX Tn,c = (bc,m Pn,m,i tm,i m

+

i XX

Pn,m,i Pn,m̃,j am,m̃ bc,m Li,j ) .

j

m̃

The execution time tm,i of function m on node i is determined by the base execution time tfunc,m multiplied with a potential speedup xm,i of executing the function on node m tm,i = xm,i tfunc,m . Note that latency introduces bilinear terms into this expression, as the placement variables Pn,m,i and Pn,m̃,j are multiplied. Analogously, monetary costs consist of two components: Provider 1

1

0 2

Provider 2

6 7

3 8

User

4

5

Region 1

Fig. 4: Overview of the centralized optimization strategy on the example of a workflow consisting of two functions placed two times on an architecture with three edge nodes and two providers with three physical devices. The placement variables P show which function of which workflow is placed on which device, while the selection variable H defines which workflow will be selected from a user node. The first two users (node 6 and 7) select the first workflow (variables in red) while the third user (node 8) select the second workflow (variables in blue). a linear part representing direct execution costs Cm,i for running function m on node i, and a bilinear part describing data transfer costs between adjacent functions deployed on different nodes. We denote Cm,i the sum of the execution cost and the potential additional cost for transferring data to node i Cm,i = pRAM,i Rfunc,m + pdata,i ddata,m . If the transfer data is already available on node i, we formulate pdata,i = 0. Additionally, data is transferred between two functions located on different nodes, represented by Dm,i,j = (psend,i + psend,j )dsend,m . Therefore, we can introduce the bilinear monetary variable for sending data as XX Sn,m,i = Pn,m,i Pn,m̃,j am,m̃ Dm,i,j ∀(n, m, i). m̃

j

In addition to these two primary cost components, time and monetary, we must also account for communication costs

6

! min w1

P,T,H,S

XX k

λk Hk,n

Pn,mstart ,i Din,i + Pn,mend ,i Dm,i,k +

n

XX

Pn,m,i Cm,i + Sn,m,i

m

i

{z

|

}

Monetary costs M

! + w2

XX k

λk Hk,n

Tn +

n

X

(Pn,mstart ,i Lk,i + Pn,mend ,i Lk,i ) + w3

n

i

|

{z

subject to: X Pn,m,i = 1 ∀(n, m)

Hk,n = 1 ∀(k)

Sn,m,i =

XX

n

i

Tn ≥

X

m̃

{z

}

Placement and selection constraint

XX m

(bc,m Pn,m,i tm,i +

XX

i

m̃

n

Node utilization

}

Pn,m,i Pn,m̃,j am,m̃ Dm,i,j ∀(n, m, i)

(1)

|

{z

}

Monetary bilinear variable

Pn,m,i Pn,m̃,j am,m̃ bc,m Li,j ) ∀(n, c)

j

m λk Hk,n Pn,m,i Rfunc,m

RAMmax,i {z

i

Utilization cost U

}

Maximum branch time constraint k

Mi2

j

P P P Mi = |

(un,m ) +

X

{z

{z

|

2

m

|

}

Basic Time cost B

|

! XX

+ M0,i ∀(i) }

between users and nodes executing either the initial or final function of each workflow. These contributions are added respectively to both time-related and monetary terms. Furthermore, all these costs results from invoking these workflows from user requests. We assume that the user randomly requests workflows with a rate of λk for every leaf node k. To get the correct expected cost, we sum over user requests by weighting each monetary cost and evaluation time by the request rate λk for every user. These two cost factors are exact if every resource and function is always free to use, that is, we do not expect waiting time in the scheduling approach due to resource constraints. As this is not realistic, we introduce an additional cost term addressing resource limitations. Because exact sequences of user requests cannot be anticipated during runtime, imposing strict constraints on workflow or node usage would lead to conservative solutions. Instead, we define a third penalty term that discourages excessive utilization of specific workflows or nodes within the serverless architecture. Additionally, modeling the exact waiting time anticipated due to the utilization of nodes and functions is equally unrealistic. Instead, we penalize the unequal placement of functions upon the serverless architecture, especially edge nodes that are resource constraint by a maximum RAM RAMmax,i , that is, we assume function evaluations on these edge nodes are blocked if the RAM reaches the maximum RAM constraint. We penalize the expected utilization of each node Mi where P P P λk Hk,n Pn,m,i Rf unc,m Mi = k n m + M0,i . RAMmax,i The utilization of this resource is dependent on the usage of this node over all s workflows. To mitigate this, we track the utilization by adding the current utilization to Mi,0 , which in turn is the summed utilization of previous placed workflows. Furthermore, blocking of a function happens if a

un,m =

X

λk Hk,n Pn,m,i tm,i ∀(n, m)

k

|

{z

Function utilization

}

specific function is already used through a different request. We therefore penalize the function utilization given as XX un,m = λk Hk,n Pn,m,i tm,i . k

i

In this work we only assume request blocking because of exceeding the RAM limit and when the specific deployment of a function is currently utilized by another user. Therefore, reducing the utilization of a node automatically reduces the chance of blocking and in return will reduce the waiting time. We will test this hypothesis in the case study and additionally evaluate how this additional cost influence the optimization problem. As illustrated in Figure 4, the total cost is evaluated as the summation over all potential user requests. The three individual cost components, monetary, temporal, and utilizationrelated, together form a multi-objective optimization problem. We solve this problem by employing a weighted-sum approach [17], assigning each objective a corresponding weight. The weights dimensions are chosen such that the cost function is dimensionless (w1 [$−1 ], w2 [s−1 ], w3 [−]). Consequently, the complete optimization problem can be formulated as in (1). Every cost is nonlinear, due to the multiplication of the selection and placement optimization variables. Additionally, nonlinear terms are added in the constraints as we model time and monetary costs based on the interaction of adjacent functions on possible different nodes. We further introduce continuous variables such as the monetary bilinear term S and the basic time variable T . The problem we are solving is therefore classified as a mixed-integer nonlinear program. This problem formulation scales exponentially in computation time for an increasing number of nodes and workflow functions, which is especially difficult for a serverless architecture with many nodes. Therefore, and considering the already established decompositions that are build into the modeling of the

7

Provider 1

serverless architecture, we propose a decomposition approach that scales well for a larger number of nodes in the next subsection. We do not directly model time-out of resources or deadlines, but the heuristic nature of the proposed utilization cost extends to these problems. Future work will address these as additional constraints in the optimization problem formulation.

0

1

2

0

1

2 Provider 2

C. Decomposition strategy There are two main reasons why solving (1) is computationally intractable in practice. First, it requires complete knowledge of all costs, speedups, and latencies across the entire serverless architecture on a single node. This assumption is unrealistic since nodes may belong to different providers that do not share all information, and collecting such statistics would accumulate large amounts of data on one node. Second, computation time scales exponentially with the number of nodes considered. As described in Subsection II-B, direct communication among all nodes as a fully connected network is improbable. Instead, it is more realistic to divide the architecture into smaller regions represented on the higher level as a single node. We extend this idea to the optimization problem itself. On each hierarchical level, placement decisions for functions within a region are performed by the respective head node that possesses local information such as latencies, costs, and speedups for its region. These regions are chosen such that node characteristics (speedup factors, type of node, region) remain homogeneous within each subset, and edge nodes are grouped only with other edge nodes. This approach addresses both challenges: only local information is required, and regions remain small enough for efficient computation. An example of the structure of the decomposition is illustrated in Figure 5. The goal of the decomposition approach is to solve a variant of (1) independently within each region at every level while maintaining proximity to the solution obtained when considering all nodes simultaneously. Therefore, we now reformulate the decision variables to Hl,r,k,n and Pl,r,n,m,i as we consider r ∈ {0, . . . , nregions,l −1} optimization problems in level l ∈ {0, . . . , nl −1}. Figure 5 illustrates the decomposition strategy. We start at level nl − 1, where physical nodes exist. For the next level, groups of edge-node regions and cloud providers are aggregated into single representative nodes. This results in several regions, each having a head node responsible for solving its local subproblem. Analogous to the main problem formulation, user requests must be included for every subproblem. Any node consisting solely of edge devices or representing physical edge hardware remains treated as a leaf node from which requests originate. Therefore, the user request rate is calculated by summing over all rates in the lower level X λl,k . (2) λl−1,succ node(l,k) =

0 1

0 2

1

2

User Region 1

Fig. 5: Decomposed approximation based on regions and providers shown for three nodes per provider and three edgeregion nodes. The one workflow in this example is placed twice ndeployments=2 . Each region or provider is represented by a single node in the main problem, where placement variables P and selection variables H are determined. Functions placed on representing nodes are then resolved within subproblems for their respective subsets. In contrast to the centralized approach, selection can be performed only once per region. Thus, only one workflow can be selected for all three edge nodes collectively in this example.

problem at level 0 and proceed through successive levels by providing the upper level placements to the lower level head nodes. Although this introduces an exponential increase in subproblem count across levels, each subproblem operates independently on its own head node and can thus be computed in parallel. Two additional constraints must be introduced to correctly perform decomposition: First, if certain functions or entire workflows have already been placed elsewhere, that is, if these functions were not assigned to their predecessor node at level (l − 1), they cannot be reconsidered within the current subproblems. Because communication routes always pass through head nodes, placing such functions virtually on their head node has an equivalent effect as placing them outside their subset entirely (see Figure 5). These virtual placements do not represent functions that are physically executed on the local head node, but only serve as placeholders for workflow parts that are outside the current region and interact with it through the head-node interface. Therefore, we add a function m into the set Mn if Pl−1,succ region(l,r),n,m,succ node(l,r) =0 and add the following constraints

Pl,r,n,m,0 = 1 ∀m ∈ Mn .

(3)

k

Each region of nodes at level l corresponds to a single representative node at level (l − 1). Therefore, placements within regions can be tracked by determining whether function m of workflow n was placed on its predecessor node at level (l − 1). Naturally, we start solving the placement

As these are virtual placements, they cannot be included in the calculation of the selection cost, especially the function placement penalization Ml,r,0 on the head node. To account for this number of virtual placements in the selection cost, we

8

have to adapt the function term Ml,r,0 for all subproblems P P P ⋆ λl,r,k Hl,r,k,n Pl,r,n,m⋆ ,0 Rf unc,m⋆ Ml,r,0 = k n m RAMmax,0 + Ml,r,0,0 , (4) where m⋆ ̸∈ Mn . If complete workflows have been deployed elsewhere, we reduce ndeployments by one accordingly. This pruning strategy reduces computational effort since regions without placed functions do not need to perform further calculations. Under the assumed hierarchical communication model, this pruning step does not introduce additional local cost by itself. The situation differs for selection decision variables Hl,r,k,n . Because upper-level representations also aggregate multiple edge regions into regional entities, selection decisions become coupled among users belonging to those regions (see Figure 5). To obtain correct cost estimation during selection evaluation, we must assume identical workflow choices across all user requests originating from one region. Hence, recomputation of Hl,r,k,n beyond level l > 0 is omitted. Again, we have to distinguish between leaf nodes that stem from real users, where if in the upper level succ node(l,r) is a leaf node and Hl−1,succ region(l,r),succ node(l,r),n = 1 we set Hl,r,k,n = 1 ,

(5)

for all leaf nodes k participating in the next-level subproblems. For the head node zero, we have to additionally account for workflows that are possibly invoked through nodes from other regions. As these information exchanges run through this main node, we treat the main node as the leaf for these additional nodes. Therefore, we sum the selections Hl−1,succ region(l,r),k,n = 1 for all leaves that are not the successor of this optimization problem that is ! X Hl,r,0,n = Γ Hl−1,succ region(l,r),k,n , (6) k

where Γ(·) is the step function. This binary aggregation only indicates whether workflow deployment n is relevant for the current subproblem through external requests. The corresponding request volume is not represented by Γ(·), but by the aggregated request rates introduced below. This coupling reduces degrees of freedom compared with centralized optimization and typically increases overall cost, particularly regarding selection-related terms, since regional uniformity restricts flexibility among users sharing similar locations or providers. Therefore, successful decomposition requires balancing computational feasibility against model accuracy, specifically, there exists a trade-off between reduced computational demand achieved via coarse regional aggregation (solving fewer largescale problems) and finer granularity necessary to represent realistic distributions among edge-node clusters. During the solving process, the user requests have to be adapted as well, depending on the decisions made in the upper level. As the head node serves as a placeholder for requests coming from outside the region, we have to additionally add the user request rate depending on the requests from the other regions, that is Here, succ node(l,0) denotes the upper-level representative of

the current regional subproblem, i.e., the node at level (l − 1) that corresponds to the local head node indexed by zero. λl,0 = λl,0 +

X

λl−1,k − λl−1,succ node(l,0) ,

(7)

k

where we sum over all other regions in the upper level to gather the requests. With the addition of (2)-(7), the main problem (1) can now be solved for each region r in each level l, requiring only communication down the levels during the placement and an update of the current cloud attributes after the placement on the lowest physical node level.

D. Scalability and Suboptimality The theoretical properties of the proposed decomposition can be analyzed mathematically. We first provide a scalability analysis and then discuss the suboptimality introduced by the decomposition. For scalability, we analyze how the overall computation time Tcomp required to solve the decomposed problem grows with the number of nodes Ns . To simplify the analysis, we make the following assumptions: Assumption 1. The overall number of Ns nodes is divided into regions of size ns ∈ [ns,min , ns,max ]. Likewise, each region in level l is represented by one node in level l−1, and a number of ns regions are grouped into one region in level l − 1. Assumption 2. For a given decomposition, we assume that the computational demand of each subproblem depends only on the number of nodes in the corresponding region. Hence, the computation time of the subproblems is bounded by T (ns,min ) ≤ T (ns ) ≤ T (ns,max ). Assumption 3. All subproblems within the same level can be solved in parallel, since the algorithm is decentralized and each subproblem is solved by the corresponding regional head node. However, the subproblems in level l require the solution of the corresponding subproblem in level l − 1. Therefore, the levels have to be processed sequentially. These assumptions are valid in the case of large cloud sizes with multiple providers as examined in this work. Under these assumptions, the following theorem holds: Theorem 1. The computation time of the decomposed approach grows logarithmically with the number of nodes, that is, Tcomp (Ns ) ∼ O(⌈logns,min (Ns )⌉). Proof. From Assumption 1, it follows that L levels are required to represent Ns nodes with subregions of size ns or smaller. This number can be overapproximated by L ≤ ⌈logns,min (Ns )⌉. Under Assumption 3, the time Tl required to solve all subproblems in level l is given by the maximum computation time of any subproblem in that level. Therefore, using Assumption 2, it follows that Tl ≤ T (ns,max ). Since the levels have to be processed sequentially according to Assumption 3, the overall computation time Tcomp (Ns ) is the sum of all level-

9

wise computation times Tl for l ∈ [0, . . . , L − 1]. Thus, we obtain Tcomp (Ns ) =

L−1 X l=0

Tl ≤

L−1 X

T (ns,max )

l=0

= L · T (ns,max ) ≤ ⌈logns,min (Ns )⌉T (ns,max ). This proves that Tcomp (Ns ) ∼ O(⌈logns,min (Ns )⌉). In addition to scalability, the suboptimality introduced by the decomposition and by the fixed selection policy has to be considered. The decomposed formulation restricts the feasible set of the centralized problem, since placement and selection decisions are made region-wise and information between regions is exchanged only through the hierarchical head-node structure. In particular, the selection variables Hk,n are fixed during placement and cannot adapt to the realized stochastic request sequence during runtime. Moreover, in the decomposed formulation, users aggregated within the same region may be forced to share selection decisions that could be chosen independently in the centralized formulation. Therefore, the decomposed solution is generally suboptimal with respect to the centralized formulation. A tight analytical bound on this suboptimality is difficult to obtain, because the realized cost depends on the stochastic request sequence, the resulting resource contention, and the interaction between placement and selection decisions. Consequently, we do not claim an a priori optimality certificate for the decomposed solution. Instead, the practical impact of this suboptimality is quantified empirically in the case study by comparing the decomposed formulation with the centralized formulation on a small example and with a heuristic baseline for larger architectures. IV. C ASE STUDY A. Evaluation Methodology In the case study, we analyze the benefits of the proposed algorithm using simulated serverless architectures and synthetic workflows. For modeling purposes, we define parameters describing both workflows and the architecture, such as evaluation costs on cloud nodes, the number of nodes within the serverless architecture, and the number of functions contained in each workflow. Modeling parameters are chosen closely to values of real applications, such as in [11]. These TABLE II: Fixed model parameters for the serverless architecture and workflows. Architecture pRAM provider 1 psend provider 1 pdata provider 1 pRAM provider 2 psend provider 2 pdata provider 2 Lnodes bdecrease nl λk

Value 0.0167 $MB−1 0.01 $MB−1 0.01 $MB−1 0.02 $MB−1 5 · 10−3 $MB−1 1 · 10−3 $MB−1 [0, 10]s 10 2 [0.03 0.05]

Workflow ndeployments RAM tfunc xfunc din dsend ddata ρdata nfunc

Value [2 5] [1 100]MBs−1 [100, 1000]s [0.75, 1] [0, 100]MB [100, 1000]MB [0, 1000]MB 0.2 [3, 6]

parameters are either uniformly distributed within fixed bounds

or remain constant throughout the case study. Table II defines these parameters together with the values used across all experiments. The serverless architecture is modeled with two cloud providers and one type of edge node. Each provider has fixed costs for sending data, executing functions, and transferring dependent data, chosen to approximate realistic values for commercial cloud services [32]. Additional architectural parameters include bounds for latencies and speedups on nodes. To achieve a more realistic simulation, latency bounds are reduced in each level to reflect increasingly regional connections according to the following formula Ll,upper bound = Lnodes b−l decrease . Function attributes are randomly sampled to generate diverse workflows. These attributes include evaluation time requirements, data sizes exchanged between functions, dependency data sizes, and the probability that a function depends on external data. In addition to these workflow parameters, we define several architectural scaling parameters that influence problem size. The number of nodes per level is uniformly distributed, combined with the total number of levels, these two parameters determine the overall scale of the serverless architecture. Furthermore, we separately specify the number of nodes considered in the highest level. For workflows, scalability is controlled by varying both the total number of workflows deployed on the architecture and the number of functions contained within each workflow. As the actual costs for a placed workflow can only be evaluated in the online selection phase, the case study simulates requests in a simulation time of tsim = 200 s. The requests are randomly sampled with a Poisson distribution using the request rate λk for each physical user k. These requests are scheduled using a FIFO scheduling, where for each workflow request, the future resources are blocked immediately. In this simulation, we therefore model two blocking mechanisms: A specific function m in a workflow t with the deployment number n cannot be used twice in the same time step, and if the RAM resource of node i is fully occupied, no further function can be executed on said node. Instead of the heuristic utilization cost U that is used in the placement problem, we focus, therefore, on the actual waiting time W due to blocking. We can therefore formulate the overall cost C, defined as a weighted sum of the two competing objectives, C = w1 M + w2 (B + W ) . In this study, we additionally will have to show that the weight w3 has an influence on reducing the waiting time. The stochastic simulation emulates realistic workflow request scenarios and is therefore essential for evaluating how effectively the proposed placement formulation, including its proxy utilization cost, performs under stochastic request arrivals. Instead of relying on real workflow traces, this work considers synthetic workflows whose attributes, such as function execution times, data demands, and resource allocations, are initially assumed to match the estimates available during deployment. Similar simulation-based evaluations are widely used in the literature [9, 6, 4, 5, 14, 2], where the required parameters are typically

10

obtained through an initial profiling or monitoring phase. Extending the evaluation to real traces requires accounting for deviations between estimated and realized parameters and for the resulting suboptimality of the placement. This aspect is investigated in the final subsection of this case study. For comparison reasons, we frequently evaluate the gap between the cost of two different solution strategies g=

NX level −1 l=0

max tc,r,l ,

0

1

2

Provider 2

6

3

7

8

5

4

User

C1 − C 2 , C1

with C1 > C2 . Second, we analyze the computation time required to solve the placement problem. In the centralized formulation, this corresponds to solving a single global optimization problem. In contrast, under decomposition we assume that total computation time equals the sum over maximum subproblem times at each level, tc =

Provider 1

Region 1

Fig. 6: Placement solution of the centralized approach for two workflows (first workflow placements and selections in red, second in blue) containing three functions. In the centralized approach, the three different users can select different workflows (user 6 and 8 selecting the second, user 7 the first), giving more freedom to reduce blocking as well as basic time and monetary costs.

r

where tc,r,l denotes computation time for subproblem r at level l. Since subproblems within a given level can be solved in parallel, only their maximum runtime contributes per level. The communication time required to pass information between levels is neglected here, as the centralized approach would also need constant communication between the nodes to update the central parameters and because we want to focus on the computational burden of the placement optimization problem in itself. All simulations are performed on an AMD Ryzen 9 16-Core processor equipped with 94 GB RAM. The modeling framework and cost calculations are implemented in Python. Integer decision problems are solved using Gurobi [12]. The code necessary to generate the presented results is openly available1 . B. Small working example First, we reintroduce the small example used in the modeling section, now with real parameters as described in Table II to illustrate the modeling and solution structure of the proposed placement algorithm and highlight its differences compared to the centralized approach. For ease of visualization, we reduce the number of deployments to two, the number of functions for each workflow to three, the number of nodes in the second level to three, and the number of edge node regions in the first level to one. Figure 6 shows the full problem, considering all nodes in one optimization problem. In comparison, Figure 7 shows the serverless architecture considered in the decomposed setting, consisting of two hierarchical levels. In the centralized case, three users can send requests independently, whereas in the decomposed approach, only one workflow can be selected per region, resulting in slightly higher overall cost. In total, we solve one optimization problem containing 131 decision variables for the centralized formulation and four subproblems for the decomposed approach. The main problem in the decomposition approach includes 49 decision variables, while the sizes of subordinate problems 1 https://github.com/JoshuaAda/IEA LSWPISCUINP

Provider 1

0

1

2

0

2

1 Provider 2

0 1

0 2

1

2

User Region 1

Fig. 7: Placement solution of the decomposed approach for two workflows (first workflow placements and selections in red, second in blue) containing three functions. In the decomposed approach, only one workflow can be selected as the three users are lumped in one region on the first level of optimization. The functions are placed on the regions in the first level and are later distributed onto the nodes of the regions in the second level.

depend on decisions made at this top level (26, 0, and 26 decision variables for the specific subproblems). Figure 6 presents results for the centralized solution, while Figure 7 shows outcomes for the decomposed strategy assuming equal weights for the monetary cost and time cost w1 = w2 = 0.5, and a utilization cost of w3 = 1. The primary difference between the centralized and the decomposed approach lies in the selection behavior. This difference can be seen in the small example. In Figure 7, all three users can select the second workflow, whereas the first workflow has no influence on the cost. On the contrary, the centralized approach can select different workflows for different users, such that the second workflow is selected for the second user. The result follows directly from the costs presented in (1). In general, it is beneficial to place the functions on the regional edge nodes as they offer small latencies and free evaluation. As

11

the first function in the workflow can be completed much faster on the cloud node of the first provider, it is placed there. As the latencies between the regional nodes are very small, the selection cost leads to a more equal distribution of the function onto the edge nodes. The total cost C across all three users in the simulation amounts to 305.27 for the centralized approach and 427.07 for the decomposed variant. The main difference stems from the waiting time, which is 137 s in the decomposed case against 79 s in the centralized approach, which is due to the higher degree of freedom to choose the workflows in the centralized approach. Despite the higher cost due to restricted selection flexibility, computation time decreases even within this small-scale scenario substantially from 217.93 ms for centralized optimization to 47.57 ms using the decomposition. C. Scaling of the decomposition approach After demonstrating the main functionalities of the proposed algorithm, we now highlight its principal advantage: the significantly improved scalability of the algorithm compared to the centralized approach. This aspect is crucial for realistic workflow placement scenarios, as the number of nodes expected in practical serverless architectures is typically significantly larger than those considered in the previous subsection. To scale the architecture, two parameters can be adjusted. First, the number of nodes within each subregion can be increased either as a fixed value or as bounds for a uniform distribution from which these values are sampled, which leads to a moderate increase in total node count. Second, we can increase the number of hierarchical levels used to organize nodes within the architecture. This results in an exponential growth of total nodes and provides a useful setting for evaluating scalability under large system sizes. Due to this exponential growth in decision variables with increasing numbers of nodes, we expect that computation time for the centralized approach will scale poorly. Therefore, we compare both approaches using an architecture with two levels while gradually increasing node counts within subregions. Other workflow and node parameters are sampled uniformly within bounds provided in Table II. Table III shows overall costs and computation times for both approaches. Costs are slightly higher for the decomposed method across all configurations, the maximum gap observed between both approaches is 5.23 %. TABLE III: Overall cost C and computation time tc for a two-level decomposition with an increasing number of nodes nnodes,1,r in the second level for every region in comparison to the centralized approach that solves the full optimization problem. Value C [-] (decomposed) C [-] (centralized) g[%] tc (decomposed) [s] tc (centralized) [s]

nnodes,1,r = 2 16510.59 15690.41 5.23 1.65 12.74

nnodes,1,r = 3 13799.34 13545.68 1.87 1.90 67.35

nnodes,1,r = 4 15379.66 15024.66 2.36 2.03 161.13

For the centralized optimization, the runtime increases exponentially with the number of nodes. For instance, placing

two workflows on a serverless architecture containing a total of 16 nodes already requires 161.13 s. In contrast, computation time for the decomposed approach increases logarithmically with node count (linear with respect to the number of levels) due to parallel evaluation of subproblems at each level. These findings confirm that decomposition enables efficient scaling toward large architectures while providing accurate approximations to global optimal solutions. There is no clear increase or decrease of the gap between the centralized and decomposed solution with the rising number of nodes, confirming that the approximation error is not dependent from the number of nodes. The gap instead depends highly on the chosen scenario. For example, a rising number of deployments can allow for a much bigger gap due to the additional degree of freedom to choose workflows for the centralized approach as discussed in Subsection IV-B. For the computation time, we achieve a favorable scaling using the decomposed approach in contrast to the exponential growth in the centralized approach. To further validate scalability benefits, we next increase architectural depth by varying hierarchical levels, thereby enabling substantially larger physical number of nodes. In this scenario, direct comparison against centralized optimization becomes infeasible since it fails to produce solutions. Instead, we benchmark against a simple heuristic strategy that places all functions on one cloud provider (provider 1). This cloud-only placement serves as a standard baseline in related work [32]. We further note that other heuristic-based approaches, such as [7, 26], address different variants of the serverless placement problem with different assumptions and objectives. Therefore, they are not directly comparable to the decentralized workflow placement setting considered in this work. In our case, it serves as a good heuristic, as blocking because of RAM constraints is reduced as much as possible with this heuristic. In this experiment, we scale from two up to four levels while assuming two regional edge nodes (and again two cloud nodes) initially. Each subproblem contains ten physical nodes per region or provider, consequently total node counts reach 40, 400, and 4000 physical devices at successive levels across three test cases. Table IV shows the TABLE IV: Overall cost C and computation time tc for increased number of levels nl and therefore the total number P of nodes in the last level nnodes = r nnodes,nl −1,r in the decomposition in comparison to a cloud only heuristic. Value C [-] (decomposed) C [-] (heuristic) g[%] tc (decomposed) [s] tc (heuristic) [s]

nl = 2 nnodes = 40 13873.43 16942.93 22.12 4.85 0.00

nl = 3 nnodes = 400 11294.04 12141.04 7.50 10.59 0.00

nl = 4 nnodes = 4000 13591.81 13863.40 1.99 37.37 0.00

cost and computation times for the decomposed approach and a cloud-only heuristic for an increased number of levels. It shows that the proposed decomposed approach consistently outperforms this heuristic regarding overall cost. Computation times reveal negligible runtime requirements for heuristics but linear growth for decomposition. This is an expected

12

outcome since additional levels introduce more parallelizable subproblems rather than sequential dependencies. Overall findings demonstrate that employing optimal placement through integer programming becomes feasible even at large scales when combined with practical decomposition strategies and has significant advantages over simple heuristics rules. The proposed method thus compromised between theoretical optimality and computational tractability required for realistic serverless environments. D. Sensitivity to weight parameters Until this subsection, we have evaluated the solution of the placement problem with fixed weights. As described in (1), we consider two competing costs (monetary and time) with the additional utilization cost that in turn reduces the waiting time and therefore again the overall time to run a workflow. Next, we want to verify that monetary and time costs are competing and that the algorithm can be tuned using w1 and w2 to reduce or increase the monetary and basic time costs. Furthermore, we investigate whether increasing the utilization cost factor w3 leads to a reduced waiting time and whether it has any impact on the tuning of the basic time and monetary cost. Understanding how varying the relative importance of each cost factor influences overall performance is essential when deciding which objective should receive greater emphasis. Such analyses are commonly conducted through Pareto front evaluation [18]. The Pareto front represents all points in the multi-dimensional cost space for which improvement in one objective necessarily leads to deterioration in at least one other. As proposed in [17], the optimal solution obtained from a weighted-sum formulation, such as the placement problem defined in (1), corresponds to a point located on this Pareto front. To further investigate trade-offs among monetary cost and evaluation time of the workflow, we perform a simulation involving ten workflows deployed on a serverless architecture with attributes given in Table II. This experiment is conducted

9000 Basic Time B [s]

Basic Time B [s]

12000 11000 10000

8900 8800 8700

9000 0

5000 10000 15000 Money cost M [$]

16000

20000

(a) w3 = 0.

17000 18000 19000 Money cost M [$]

20000

(b) w3 = 3.

8800

Basic Time B [s]

Basic Time B [s]

8800

8750 8700

17000

18000 19000 Money cost M [$]

(c) w3 = 6.

20000

8750

8700

17000

18000 19000 Money cost M [$]

20000

(d) w3 = 9.

Fig. 8: Pareto fronts for monetary and basic time costs using a weighted sum approach (increase weight w1 for basic time cost, while decrease weight w2 = 1 − w1 for the monetary cost), exemplary for different values of penalization of utilization w3 .

for different weights between the two competing costs (eleven values between zero and one for w1 and w2 = 1 − w1 ). Additionally, this process is repeated for eleven additional values of w3 between zero and ten. TABLE V: Overall waiting time in seconds evaluated with increased penalization of utilization w3 for different weight combinations w1 /w2 on the Pareto front. w1 = 0.0; w2 = 1.0 w1 = 0.3; w2 = 0.7 w1 = 0.6; w2 = 0.4 w1 = 0.9; w2 = 0.1

w3 = 0 2246 283852 384092 232362

w3 = 1 1568 1587 2252 16224

w3 = 2 1568 1568 1742 1817

w3 = 3 1568 1568 1582 1804

Figure 8 shows four exemplary Pareto fronts for basic time cost B against the monetary cost M . Each example is done for a specific value of w3 and is generated by increasing the weight for basic time cost w1 , while reducing the weight of the monetary cost w2 . The Pareto fronts show that both cost factors are competing and can be tuned with w1 and w2 for all values of w3 . Additionally, Table V shows the reduced waiting time with increasing w3 for different combinations of w1 and w2 for the lower value experiments of w3 . Without considering the utilization cost for all combinations of w1 and w2 , the waiting time is much longer than the basic time T . Even for small values of w3 the waiting time reduces fast and remains stable, demonstrating that the utilization penalty effectively reduces waiting time due to blocking in simulation.

E. Sensitivity to incorrect model parameters and real world applicability Since the proposed algorithm is evaluated in a high-fidelity simulation and not directly on real workflow deployments, we next discuss the real-world applicability of the approach. The main bottleneck for practical deployment is the uncertainty of essential model parameters, such as request rates, execution times, latencies, and resource demands. Many approaches estimate these values in an initial profiling phase before deployment [11]. However, these parameters may change during runtime or may be difficult to estimate accurately from short observation windows. We therefore investigate scenarios in which the parameters used in the simulation differ from the parameters assumed in the placement optimization. The placement remains feasible under such deviations, but the resulting solution may become suboptimal. The investigation is conducted on an architecture with two levels and a total of 100 physical nodes, as used in the comparison against the heuristic in Subsection IV-C, with weights chosen as w1 = 0.5, w2 = 0.5, w3 = 1. To analyze the influence of incorrect parameter estimates, we scale one uncertain parameter at a time in the simulation while keeping the value used in the placement problem fixed. We consider four uncertain parameters: the latencies L, the user request rates λ, the allocated RAM, and the runtime of each function. In a first step, we analyze the sensitivity of the simulated cost with respect to these parameter deviations. Figure 9 shows that the simulated cost increases monotonically with

13

decomposed

17500

400

15000

300

12500 10000 0.8

1.0

1.2

0.8

scale factor

1.0

1.2

scale factor

Fig. 9: Sensitivity analysis for the simulated placement costs for four uncertain parameters: latencies, allocated RAM, function runtimes, and user request rates. Each parameter is scaled in the simulation relative to the value assumed in the placement problem. The comparison is performed against the heuristic introduced in Subsection IV-C.

the scaling factor for all investigated parameters. Thus, if the realized parameters are smaller than assumed, the simulated cost decreases, whereas larger realized values lead to higher costs. This behavior is observed for both the decomposed approach and the heuristic baseline. The monotonic response is important for practical deployment, since it indicates that conservative over-approximations of uncertain parameters can be used to obtain more robust placements against worst-case parameter deviations. In a second step, we compare the nominal placement, which is computed using the original parameter estimates, with an adapted placement that is recomputed using the true scaled parameter values. Figure 10 shows that the benefit of re-planning is comparatively small and does not exhibit a clear monotonic trend with the scaling factor. In some cases, adapting the placement to the true parameter values improves the simulated cost, while in other cases the difference is negligible. This behavior is expected, since the utilization term used in the placement problem is a heuristic proxy for the waiting time observed in the stochastic simulation. While the parameters have a significant influence on the cost, there is little than can be done in the optimization to prevent this from happening. Overall, this study show that cost rises monotone with possible uncertain parameters, allowing for worst-case approximations in real world applications to enable robust solutions against parametric uncertainty. Furthermore, the study shows that the difference between choosing the perfect parameters and a deviated estimate is small, further pointing toward real world applicability of the approach. V. C ONCLUSION In this work, we present a modeling framework for the optimal placement of workflows in serverless fog computing architectures. The framework jointly models workflow placement and selection within the architecture and formulates a nonlinear optimization problem that minimizes both monetary cost and execution time. To address decomposed information and the exponential growth of computational demand with increasing numbers of nodes, we introduce a decomposition

Cnominal − Cadapted

20000

Regret of keeping the nominal placement vs. re-planning

Overall cost C

22500

Overall cost C

heuristic

demand λ runtime latency L RAM nominal placement adapted placement

decomposed demand λ runtime latency L RAM

200 100 0

−100

2.0 (Cnom − Cad ) /Cad [%]

25000

1.5 1.0 0.5 0.0

−0.5

0.8

0.9

1.0 scale factor

1.1

1.2

Fig. 10: Regret of keeping the nominal placement compared with re-planning using the true scaled parameter values. Positive values indicate that re-planning improves the simulated cost.

strategy enabling scalable optimization. We demonstrate the advantages of the proposed method compared to a centralized formulation and heuristic baseline, as well as its adaptability through a Pareto analysis of competing cost objectives. Future work will extend the framework toward advanced probabilistic online selection strategies and incorporate additional cost factors relevant to practical deployment scenarios, such as workflow cold-start delays and energy consumption of serverless nodes. Additionally, real world application requires adaption to incorrect parameter estimation. Future work will address this challenge through recourse action in the placement problem as well as robust optimization problem formulations that allows to deal with uncertain parameter settings. D ECLARATION OF GENERATIVE AI AND AI- ASSISTED TECHNOLOGIES IN THE MANUSCRIPT PREPARATION PROCESS

During the preparation of this work the authors used GPT 5.0-5.5 in order to make adjustments to existing text in this paper, as well as small adaptation to coding sections for data storage and figure creation. After using this tool/service, the author(s) reviewed and edited the content as needed and take(s) full responsibility for the content of the published article.

14

R EFERENCES [1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12] [13]

[14]

Muhamed Alarbi, Robert Belson, and Hanan Lutfiyya. “ECO: edge continuum orchestrator framework for managing serverless chains across the cloud-edge spectrum”. In: 2024 33rd International Conference on Computer Communications and Networks (ICCCN). 2024. “An efficient mechanism for function scheduling and placement in function as a service edge environment”. In: Journal of Network and Computer Applications 226 (2024), p. 103890. Daniel Barcelona-Pons et al. “On the FaaS Track: Building Stateful Distributed Applications with Serverless Architectures”. In: Proceedings of the 20th International Middleware Conference. Davis CA USA, Dec. 2019, pp. 41–54. Luciano Baresi et al. “NEPTUNE: A Comprehensive Framework for Managing Serverless Functions at the Edge”. In: ACM Trans. Auton. Adapt. Syst. 19.1 (2024). David Bermbach et al. “AuctionWhisk: Using an auction-inspired approach for function placement in serverless fog platforms”. In: Software: Practice and Experience 52.5 (2022), pp. 1143–1169. Vincenzo De Maio, David Bermbach, and Ivona Brandic. “TAROT: spatio-temporal function placement for serverless smart city applications”. In: 2022 IEEE/ACM 15th International Conference on Utility and Cloud Computing (UCC). IEEE. 2022, pp. 21–30. Chinmaya Kumar Dehury, Shivananda Poojara, and Satish Narayana Srirama. “Def-DReL: Towards a sustainable serverless functions deployment strategy for fog-cloud environments using deep reinforcement learning”. In: Applied Soft Computing 152 (2024), p. 111179. Simon Eismann et al. “The State of Serverless Applications: Collection, Characterization, and Community Consensus”. In: IEEE Transactions on Software Engineering 48.10 (Oct. 2022), pp. 4152–4166. Tarek Elgamal et al. “Costless: Optimizing Cost of Serverless Computing through Function Fusion and Placement”. In: 2018 IEEE/ACM Symposium on Edge Computing (SEC). 2018, pp. 300–312. Adrien Gallego et al. “Machine learning inference on serverless platforms using model decomposition”. In: Proceedings of the IEEE/ACM 16th International Conference on Utility and Cloud Computing. 2023, pp. 1–6. Mohsen Ghorbian, Mostafa Ghobaei-Arani, and Rohollah Asadolahpour-Karimi. “Function Placement Approaches in Serverless Computing: A Survey”. In: Journal of Systems Architecture 157 (2024), p. 103291. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual. 2024. URL: https://www.gurobi.com. Yunshan Jia et al. “FaaSPR: Latency-Oriented Placement and Routing Optimization for Serverless Workflow Processing”. In: IEEE Transactions on Networking 33.4 (2025), pp. 2063–2078. Shouxi Luo et al. “Efficient and flexible component placement for serverless computing”. In: IEEE Systems Journal 18.2 (2024), pp. 1104–1114.

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

Ashraf Mahgoub et al. “{SONIC}: Application-aware data passing for chained serverless applications”. In: 2021 USeNIX annual technical conference. 2021, pp. 285–301. Marcin Majewski, Maciej Pawlik, and Maciej Malawski. “Algorithms for scheduling scientific workflows on serverless architecture”. In: 2021 IEEE/ACM 21st International Symposium on Cluster, Cloud and Internet Computing (CCGrid). 2021, pp. 782–789. R. Timothy Marler and Jasbir S. Arora. “The weighted sum method for multi-objective optimization: new insights”. In: Structural and Multidisciplinary Optimization 41.6 (June 2010), pp. 853–862. P. Ngatchou, A. Zarei, and A. El-Sharkawi. “Pareto Multi Objective Optimization”. In: Proceedings of the 13th International Conference on, Intelligent Systems Application to Power Systems. Arlington, Virginia, USA, 2005, pp. 84–91. Andrei Palade et al. “A Swarm-based Approach for Function Placement in Federated Edges”. In: 2020 IEEE International Conference on Services Computing (SCC). 2020, pp. 48–50. Tobias Pfandzelter and David Bermbach. “tinyFaaS: A Lightweight FaaS Platform for Edge Environments”. In: 2020 IEEE International Conference on Fog Computing (ICFC). Sydney, Australia, Apr. 2020, pp. 17–24. Arokia Paul Rajan. “A review on serverless architectures - function as a service (FaaS) in cloud computing”. In: TELKOMNIKA (Telecommunication Computing Electronics and Control) 18.1 (Feb. 2020), p. 530. Ali Raza et al. “Configuration and placement of serverless applications using statistical learning”. In: IEEE Transactions on Network and Service Management 20.2 (2023), pp. 1065–1077. Sashko Ristov and Philipp Gritsch. “FaaSt: Optimize makespan of serverless workflows in federated commercial FaaS”. In: 2022 IEEE International Conference on Cluster Computing (CLUSTER). 2022, pp. 183–194. Alireza Sahraei et al. “XFaaS: Hyperscale and Low Cost Serverless Functions at Meta”. In: Proceedings of the 29th Symposium on Operating Systems Principles. Koblenz Germany, Oct. 2023, pp. 231–246. R. Schultz, L. Stougie, and M. H. Van Der Vlerk. “Twostage stochastic integer programming: a survey”. In: Statistica Neerlandica 50.3 (Nov. 1996), pp. 404–416. Christopher Peter Smith et al. “FaDO: FaaS Functions and Data Orchestrator for Multiple Serverless EdgeCloud Clusters”. In: 2022 IEEE 6th International Conference on Fog and Edge Computing (ICFEC). 2022, pp. 17–25. Márk Szalay, Péter Mátray, and László Toka. “RealTime FaaS: Towards a Latency Bounded Serverless Cloud”. In: IEEE Transactions on Cloud Computing 11.2 (Apr. 2023), pp. 1636–1650. Mohit Tawarmalani and Nikolaos V. Sahinidis. Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory, algo-

15

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

rithms, software, and applications. eng. Nonconvex Optimization and its Applications Volume 65. Boston, [Massachusetts], 2002. Kan Wang, Jing Ma, and Edmund M-K Lai. “BriskChain: Decentralized function composition for high-performance serverless computing”. In: IEEE Access 12 (2024), pp. 131313–131322. Luying Wang et al. “SD-SRF: An Intelligent Service Deployment Scheme for Serverless-operated CloudEdge Computing in 6G Networks”. In: Future Generation Computer Systems 151 (2024), pp. 242–259. Zhijie Wang et al. “LPCD: A Parallel Candidate Deployment Strategy in Stateful Serverless Computing With Low Latency”. In: IEEE Transactions on Network and Service Management 22.6 (2025), pp. 5927–5944. Renchao Xie et al. “Workflow Scheduling in Serverless Edge Computing for the Industrial Internet of Things: A Learning Approach”. In: IEEE Transactions on Industrial Informatics 19.7 (July 2023), pp. 8242–8252. Zichuan Xu et al. “Stateful serverless application placement in MEC with function and state dependencies”. In: IEEE Transactions on Computers 72.9 (2023), pp. 2701–2716. Murat Yilmaz et al. “A Multivocal Literature Review of Function-as-a-Service (FaaS) Infrastructures and Implications for Software Developers”. In: Systems, Software and Services Process Improvement. 2020, pp. 58–75. Xiaofei Yue et al. “HyFaaS: Accelerating Serverless Workflows by Unleashing Hybrid Resource Elasticity”. In: IEEE Transactions on Parallel and Distributed Systems 37.1 (2026), pp. 272–286. Atiya Zahed, Mostafa Ghobaei-Arani, and Leila Esmaeili. “An efficient function placement approach in serverless edge computing”. In: Computing 107.3 (2025), p. 80.

Related documents

• A characterization of workflow management systems for extreme-scale applications#786170
• Improving the Energy Efficiency of High Throughput Computing: A Measurement-Based Case Study#440327
• Serverless Frameworks for Scalable Banking App Backends#78859
• State Without a Landlord: An Architecture Proposal for Peer-to-Peer Replication of Durable Workflow State#1011376
• State Without a Landlord: An Architecture Proposal for Peer-to-Peer Replication of Durable Workflow State#965395