A Stable Matching Approach to Energy Efficient and Sustainable Serverless Scheduling for the Green Cloud Continuum

A Stable Matching Approach to Energy Efficient and Sustainable Serverless Scheduling for the Green Cloud Continuum Yashwant Singh Patel Dept. Computing Science Ume˚ a University Ume˚ a, Sweden [email protected] Paul Townend Dept. Computing Science Ume˚ a University Ume˚ a, Sweden paul.to[email protected] Abstract—Cloud infrastructures are evolving from centralised systems to geographically distributed federations of edge devices, fog nodes, and clouds - often known as the Cloud-Edge Continuum. Continuum systems are dynamic, often massive in scale, and feature disparate infrastructure providers and platforms; this greatly increase the complexity of developing and managing applications. The Serverless paradigm shows the potential to greatly simplify the process of building Continuum applications - however, current scheduling mechanisms for Serverless Continuum platforms pay little attention to reducing the energy consumption and improving the sustainability of function execution. This is a significant omission, made worse as computing nodes within a Continuum may be powered by renewable energy sources that are intermittent and unpredictable, making low-powered and bottleneck nodes unavailable. There is great opportunity to design a decentralized energy management scheme for scheduling Serverless functions that takes advantage of the different layers of the Continuum, such as IoT devices located at the Edge, on-premises clusters closer to the data sources, or directly on large Cloud infrastructures. To achieve this, we formally model a green energy-aware Serverless workload scheduling problem for the multi-provider Cloud-Edge Continuum. We then design stable matching based technique for decentralized energy management (utilising a distributed controller) that considers the availability of green energy nodes and the QoS requirements of Serverless functions. We prove the complexity, stability and termination of the proposed heuristic algorithm, and also compare its performance with baseline scheduling techniques. KeywordsCloud-Edge Continuum, Serverless Computing, Renewable energy, Scheduling, Function-as-a-Service, Matching. I. INTRODUCTION To address the ultra-low latency demands of next generation applications, Cloud infrastructures are rapidly progressing from centralised large-scale systems to geographically distributed federations of edge devices, fog nodes, and cloud data centers - often termed as the Cloud-Edge Continuum. The Cloud-Edge Continuum, illustrated in Fig. 1, consists of heterogeneous regions (e.g. R1, R2, R3, R4) containing many IoT devices (shown by black dots), fog & edge nodes and Cloud data centers (represented by Eand C), powered by multiple energy providers (e.g. EP1, EP2, EP3, EP4), and controlled by different service operators. Fig. 1. Migrating functions in a Continuum system To better address the requirements of modern applications, a Continuum system must be capable of managing the massive complexity of disparate infrastructure providers, energy providers, resource heterogeneity, and infrastructural dynamicity, whilst providing secure orchestration over public networks [1]. These characteristics lead to many substantial integration challenges (from both technical and business perspectives) for providers, and introduce further complexity - particularly in resource scheduling and management across multi-layered and multi-provider infrastructures. More concretely, conventional cloud scheduling policies rely on greedy algorithms that do not effectively manage Cloud-Edge Continuum platform heterogeneity and fail to optimize data transfers. Serverless computing [2], [3] is a popular emerging paradigm (projected market value expected to reach $42.4 billion by 2030 [4]) to significantly reduce this complexity for application developers, moving much of the application management burden to providers. Serverless technologies allow developers to implement application functionality as invokable services (often referred to as Function-as-a-Service (FaaS)), with providers managing the provisioning, deployment, and scaling of these services based on a range of factors such as cost, load balancing, efficiency, etc. This offers the prospect of greatly improving the ability of smaller developers to implement applications across a complex Continuum of resources. While this server-agnostic model partially alleviates several Cloud-Edge Continuum characteristics (e.g. providing codeoffloading capabilities to constrained devices, removing infrastructural dynamicity concerns for application developers, etc.), there are still multiple distinct research challenges that need to be addressed to build a functional multi-provider Serverless infrastructure for Cloud-Continuum. Crosscutting these challenges is the necessity for Cloud-Edge systems to adapt to uncertain nature of end users and providers demands, system and network behaviors, and most importantly, integrate energy considerations (e.g. the availability of renewable (green) energy sources, multiple energy providers, energy policies and pricing, the requirement to balance energy consumption over large areas with non-Cloud consumers, etc.) [1], [5]. On a large scale, this adaptability requires energy-aware monitoring and control of the heterogeneous platforms and applications that deal with massive volumes of data, and the deployment of complex software environments such as the ones required for AI/ML applications. The size of Continuum systems is expanding rapidly; forecasts suggest that over 75 billion devices will be deployed in the Continuum by the year 3PM 6PM 9PM 12AM 3AM 6AM 9AM 0 100 200 300 400 500 Carbon Intensity (gCO eq/kWh) 20.4x 4.3x 1.3x 2.4x 1.1x Sweden Finland Germany Netherlands Fig. 2. Carbon intensity for four different regions 2025 [7]. This leads to Continuum systems requiring massive energy consumption; one estimate suggests that data centers and networks combined will consume 18% of the world’s electrical power consumption by 2030 [8]. This consumption is causing great strain on electricity grids (national and local) [12] and has the potential for significant environmental impact, especially considering that nearly 80% of the world’s energy is still produced by brown energy (non-renewable) sources such as coal, natural gas, oil, and nuclear energy, which emit a very high carbon footprint [11]. The carbon footprint of Continuum systems can be estimated by considering the carbon intensity (CI) of the power grids powering each node; this is expressed in grams of CO2 equivalent per watt (g·CO2eq/kWh), which reflects the average weighted carbon intensity of the mix of sources utilized to generate energy at any particular moment. Fig. 2 shows the carbon intensity variations of grid energy for two days in four regions of the Europe. These variations encourage the utilization of temporal and spatial shifting techniques in Cloud systems [9], as a task’s carbon footprint can vary by up to 4.3 times (for example, notice the CI values for the Netherlands at 3pm and 9pm) depending on whether it is executed during a low or high carbon-intensity period. Moreover, it can be seen that the carbon intensity of grid energy varies by up to 20 times across different regions (for example, the CI value between Sweden and Netherlands at 9pm) [10]. This issue is becoming ever more acute as society’s energy challenges grow; it is a major concern for power grids, which must balance the demands of Continuum systems alongside those of other energy consumers. It is thus crucial to develop methods for mitigating, optimizing and, where feasible, reducing energy consumption in Continuum systems. An encouraging technique is energy-aware resource scheduling in Serverless systems; by closely monitoring large federated systems, functions can be placed on the most energyefficient resource available, considering factors such as Quality of Service (QoS) and pricing, etc. For instance, functions can intentionally be assigned to Continuum nodes that are currently utilizing substantial amounts of green (renewable) energy, such as wind or solar power. Conversely, functions can be offloaded away from nodes in regions experiencing high energy demand to free up local power grid capacity for other users, thereby achieving load balancing across regional and national power grids. These scheduling decisions may also consider energy pricing alongside user and software servicelevel objectives (SLOs). For example, functions demanding ultra-low latency (delay sensitive) may be placed on a local edge node, even if that node relies on energy from a brown (non-renewable) energy source, while delay-tolerant functions may be scheduled to more sustainable locations. An example of one such scenario is shown in Fig. 1. Initially, certain functions f1, f2, f3, f4, and f5are assigned to region R2. However, as green energy availability in R2reduces to 10% (suffering from low energy density), an offloading decision is made to transfer functions f1, f2, f3, f4and f5 to well-powered regions R1and R4, where green energy availability is higher (e.g. 90% at R1and 70% at R4). This strategic offloading of functions enables us to maximize the green energy usage while also balancing resource loadings across federated regions of the Continuum. However, the current scheduling mechanisms for Serverless platforms pay little attention to the reduction of energy consumption during function execution - and none adequately integrate energy considerations (e.g. availability of renewable (green) energy sources, multiple providers, energy policies, energy pricing, and the requirement to balance consumption over large areas with other non-Cloud consumers, etc.). Energyaware resource scheduling in Serverless Cloud-Continuum is a particular concern when developing autonomous resource management systems, as current management approaches do not consider energy policies, constraints and optimizations across large federations. To address these research gaps, we make the following key contributions: •Problem: Formulate the problem of decentralized energy management for green energy aware Continuum nodes running on Serverless and multi-provider Cloud-Edge Continuum. •Research approach: Presenting a matching theory based research approach to dynamically manage resource allocations to Serverless workloads. •Evaluation: Evaluate the efficiency of proposed solution in comparison with baseline scheduling techniques in terms of green energy usage, workload intensity, throughput, and satisfaction. This paper is organized as follows. Section II discusses the current research status of relevant Serverless-aware CloudEdge models. Section III emphasizes on system modeling and problem formulation. Section IV focuses on our research approach for scheduling the Serverless workloads in energyaware Cloud Continuum. Section V discusses the experimental results, and finally Section VI concludes the paper with future research opportunities in the context of energy-aware Serverless workloads modeling in Cloud-Edge Continuum. II. RELATED WORK There is limited research dedicated to energy-aware scheduling for the Serverless Cloud Continuum, and none of it adequately integrates energy considerations. Additionally, few scheduling based solutions have been designed specifically for Serverless Cloud or Edge systems. We discuss some of the most relevant works available in the literature on Scheduling for Serverless Cloud-Edge systems. Aslanpour et al. [13], [14] discuss the problem of energyaware scheduling in Serverless edge systems; the authors design several resource scheduling algorithms to assign functions on different edge nodes powered by various green energy and battery energy sources. The objective of the work is to optimize the operational uptime of edge nodes while ensuring a higher Quality of Service (QoS) and throughput. Through experimental evaluation in a real test-bed setup, the authors demonstrate that their energy-aware scheduler enhances operational uptime, serviceability, and throughput compared to benchmark algorithms. However, the work only applies centralized scheduling within a homogeneous environment, and evaluates energy-efficiency specifically for edge nodes only. Angelelli et al. [17] investigate the utilization of Serverless platforms within the Cloud Continuum. Their study evaluates the effect of platform heterogeneity during scheduling while optimizing data transfers and function execution times. They develop a multi-objective scheduling policy for the allocation of Serverless functions across Cloud-Edge platforms, with the objectives of minimizing makespan and the data downloads required for deploying containers and functions’ I/O operations. The experiments show disparities between greedy and multi-objective scheduling algorithms in Serverless platforms - however, this scheduling policy is time-consuming, and does not take into account delay-sensitive tasks and the energy consumption of edge-cloud nodes. Rastegar et al. [18] present ‘EneX’, an energy-aware execution scheduler for Serverless resource providers. The authors investigate online and offline solutions, taking into account key factors such as performance, scalability, and complexity. Russo et al. [20] design a FaaS framework for function offloading and migration in cloud-edge systems, developing various mechanisms for Serverledge FaaS framework and evaluating the approaches in terms of throughput and response time. Dantas et al. [19] design ‘GreenLAC’, a load balancer and reverse proxy to manage Serverless deployments of edgecore IoT applications. The authors validate the feasibility and performance of the Serverless balancer using a public cloud platform. Suresh et al. [21] apply OpenWhisk to develop an ‘FnSched’ scheduling policy, which aims to minimize the cost of resources; the authors integrate CPU-shares regulation and a greedy technique. Zuk et al. [22] develop some online nodelevel scheduling policies; they modify well-known policies such as FIFO (First-In, First-Out), EECT (Earliest Expected Completion Time), and SEPT (Shortest Expected Processing Time) and utilize historical data to reduce cold starts. To enhance latency and cost efficiency, various task placement solutions are also suggested. ActionWhisk [23] aims to reduce cost rather than energy optimization, whilst another study focuses on latency [24], examining the relocation of tasks and functions within a cluster of heterogeneous nodes. Gu et al. [25] suggest a deep reinforcement learning (DRL) driven strategy for edge environment, which examines the system states and dynamically makes decisions on energy scheduling and service management to reduce the long-term cost. Verma et al. [26] introduce the ‘LEASE’ framework for resource allocation in Serverless functions supporting various microservices while meeting their deadlines. To optimize scheduling decisions, they propose a priority-based scheme that offloads functions from over-provisioned nodes to under-provisioned nodes. This approach considers the energy expended in the process without neglecting the finishing time of the microservices. Adeppady et al. [27] explore a straightforward threshold-based approach to reduce the energy consumption of active servers in Serverless edge environment. This method optimally manages different container states while ensuring the target delay of requested services. Overall, our analysis of existing work highlights the lack of unified systems and methods to integrate multiple infrastructure providers, energy and data policies, resource restrictions, QoS and SLO requirements of end-users, and key energy factors (such as green energy sources, disparate energy providers, Spatial-temporal pricing, energy provider requirements, etc.). To address these research gaps, we model a green energyaware Serverless workload scheduling problem for the multiprovider Cloud-Edge Continuum. III. MODELING AND PROBLEM FORMULATION A. System Modeling Fig. 1 depicts a high-level overview of a decentralized Serverless Cloud-Edge system; we model a Continuum consisting of a federation of regions i.e, edge and cloud nodes with heterogeneous computational power, storage, and networks. CPU speeds may vary across regions, and each region is powered by green energy sources, brown energy sources and energy storage devices (e.g. battery with limited capacity) with different rates of energy generation. Typically, energy demand is high during peak hours of the day and low during offpeak hours. Energy storage devices store green energy when energy demand in a region is low, allowing utilization of stored energy during peak hours instead of relying on brown energy. Compared to traditional Cloud based platforms, scheduling functionalities are distributed and thus every node within a region is able to schedule the execution of incoming requests. This is especially crucial for requests generated at the edge. The request comprises several microservices, and the function executes tasks associated with each microservice. Each region possesses a local controller, which follows the IBM MAPE-K [28] (Monitoring, Analysis, Planning, Execution, and Knowledge) model. The MAPE-K serves as the reference control model for autonomic and distributed self-adaptive systems. It is designed to accurately capture the dynamics of the system and make effective decisions based on the available data and knowledge. Apart from the local controllers (LCs), there exists a global controller (GC) which provides information on all regions deployed in the continuum. Next, we formulate the Continuum model in terms of regional nodes, workload, Serverless functions, and network delay. Regional nodes: We consider a discretized workload model by considering Tconsecutive equal time slots, denoted as T={t|t∈[0, T],(t+ 1) −t= ∆tseconds}. We assume a set of regions R={rj|j∈[1, m]}and set of nheterogeneous computing nodes represented as D={dj i|i∈ [1, n], j ∈[1, m]}located across mdifferent regions. A local controller, which is not included in Dfollows the IBM MAPE-K [28] model to perform management of resources. Assuming G={gj it,|i∈[1, n], j ∈[1, m], t ∈T, gj it ≥0} represent the energy input to node i, which is powered by green energy sources with different rates of energy generation. Energy consumption of nodes during tis represented as E={ej it|i∈[1, n], j ∈[1, m], t ∈T, ej it ≥0}. At each region different function invocation requests are generated at varying and sporadic rates. The State of Charge (SoC) and CPU consumption are critical parameters [9], [13] for device dj i located in region j. The SoC denotes the available amount of battery charge on computing nodes at different time intervals represented as S={sj it,|i∈[1, n], j ∈[1, m], t ∈T, δ ≥ sj it ≥0}, where δdenotes the maximum level of battery charge. In a wind and solar hybrid system, wind turbines and photovoltaic modules aggregate their outputs to charge the batteries [29]. The overall resource capacity of nodes is measured in MIPS (Million Instruction Per Seconds) and denoted as Cap ={capj it,|i∈[1, n], j ∈[1, m], t ∈T, capj it ∈ [0, γ]}, where γdenotes the maximum capacity of resources. Nodes can host functions if they satisfy the minimum energy threshold sj it ≥ζ. The availability of a node is expressed as Y={yi,j t|i∈[1, n], j ∈[1, m], t ∈T, yi t∈ {0,1}}, which means yi,j t= 0 whenever the node is unavailable during t. Mathematically, the status of Continuum nodes across the region is represented as: dj i∈D:yi,j t=(1,if sj it ≥ζ 0,otherwise (1) Here the value of SoC sj it entirely relies on the SoC at the past time period sj i(t−1), green energy input gj it, and energy consumption ej it at t. For all dj i∈D, The SoC sj it is formulated by the following equation [13], [15], [16]: ∀dj i∈D:si,j t= min(δ, max(sj i(t−1) +gj it −ej it,0)) (2) The surplus green energy for regional node iat time slot tis (sj i(t−1) +gj it −ej it). Here SoC may vary between 0 and δ. In cases where the green energy of all nodes is depleted, the brown energy consumption can be calculated as (ej it −gj it + sj i(t−1)). The value of ej it is computed based on the assigned functions to dj iat t. The overall energy consumption [13] for all dj i∈Dis modeled as: ej it = Pl k=1((αi,j,k t+βi,j,k t)×qk) Ω×υ +l X k=1 (oek,trans ×(κi,j,k t−αi,j,k t))+ l X k=1 (oek,recv ×βi,j,k t)!×∆t (3) Eq. 3 considers energy consumption during direct usage and offloading overhead scenarios [13]. Direct usage estimates the occupied resources of a node for each microservice k, the energy consumption is obtained by Pl k=1 ((αi,j,k t+βi,j,k t)×qk) Ωmultiplied by power consumption rate υ. For the offloading overhead, energy consumption is computed as Pl k=1(oek,trans × (κi,j,k t−αi,j,k t)) + Pl k=1(oek,recv ×βi,j,k t). The energy consumption by direct usage and offloading overhead is then multiplied by the total length of the time slot ∆t. Workload: The set of microservices is expressed as B= {bk|k∈[1, l]}. The workload generated for a collection of microservices at different time intervals across the regions is represented as Λ = {λj,k it ,|i∈[1, n], j ∈[1, m], k ∈ [1, l], t ∈T, λj,k it ∈[0, λj,k it max]}. The λj,k it max denotes the maximum possible workload that can enter into node iat region j. For execution, each workload comprises a specific amount of processing in Million Instructions (MI) expressed as Π = {πk,|k∈[1, l],0≤πk∈R}. The local controller determines the amount of workload σj,k it ≤λj,k it that can be processed locally in its region. The remaining part of workload (λj,k it −σj,k it )should be offloaded to the nearest region for processing. Serverless functions: The set of functions is defined as F={fi,j,k t,|i∈[1, n], j ∈[1, m], k ∈[1, l], t ∈T}, here functions fi,j,k perform workload execution for the bkmicroservice managed by compute node diin region j. Each function contains five attributes, i.e., fi,j,k =< fi,j,k type , fi,j,k priority, fi,j,k at , fi,j,k d, fi,j,k q>, where fi,j,k type denotes the function ID to be invoked, fi,j,k priority represents the priority level (high or low), fi,j,k at denotes arrival time, fi,j,k drepresents the deadline, and fi,j,k qdenotes the resource requirement. The required amount of resources for function deployment is determined as Q={qk|k∈ {1, l}, qk∈[0,Ω]}, where qkis restricted to the the node’s maximum capacity γ. To support auto-scaling feature in Serverless, fi,j,k may contain multiple function replicas at time t, restricted at ℜ. Multiple replicas will ensure scalability and fault tolerance. Following the replica-level modelling in [13], we set Ψ = {κi,j,k t|i∈[1, n], j ∈[1, m], k ∈[1, l], t ∈T, κi,j,k t∈[0,ℜ]} represents the required number of replicas per function. Based on the expected incoming workload, the number of replicas for bkon dj iat tis estimated as κi,j,k t= min ℜ,lλj,k it ×πk qkm, which may receive a value between 0 to ℜ. In the case where dj iis unavailable at t, then κi,j,k tbecomes 0 (i.e., zero replica). To model the replicas, the Fis expanded to F={fi,j,k,x t,|i∈ [1, n], j ∈[1, m], k ∈[1, l], t ∈T, x ∈[1, κi,j,k t]}, where x represents the xth replica. Replicas of functions can either be assigned to their local node or offloaded to nearby devices as decided by the local controller. Depending on the si,j ton dj iat t, the local agent determines local and remote function assignments [13] per regional nodes. The local assignments is defined as A = {αi,j,k t,|i∈[1, n], j ∈[1, m], k ∈[1, l], t ∈ T, α ≥0}and remote assignments of functions as B = {βi,j,k t,|i∈[1, n], j ∈[1, m], k ∈[1, l], t ∈T, α ≥0}. The local agent must ensure that the constraint for local assignment αi,j,k tof replicas for fi,j,k tis αi,j,k t≤κi,j,k t. Supposing fi,j,k,l t is offloaded to any candidate node dp, then a transfer cost for dj iand receiving cost dpare computed. The overhead energy cost [13] per micro-service for fi,j,k,l tis expressed as OE ={oek,w|k∈[1, l], w ∈ {trans, recv}, oek,w ∈[0,1]}. Network delay: The following types of workload processing delays can occur on nodes. (a) Transmission delay: The transmission delay, denoted as Cwi i,j,k(t), arises while transmitting workloads over a wireless network. It correlates directly with the network’s input workload (i.e., λj,k it ). (b) Local processing delay: The local processing delay denoted by Cloc i,j,k(t)occurs during processing of workloads within a local region. The delay can be computed using the number of active nodes, denoted by dj it ∈[0, D]and the amount of locally processed workload in the region i.e., σj,k it , thus expressed as Cloc i,j,k(σj,k it , dj it). As discussed in [29], the M/G/1 mechanism is adopted for queue management of servers. Consequently, the processing delay in a region is derived using the following expression [29]: Cloc i,j,k(σj,k it , dj it) = σj,k it dj it.η −σj,k it (4) where ηsignifies the processing capacity of each node. (c) Offloading delay: The offloading delay expressed as Coff i,j,k(t)pertains to the transmission delay of a remaining workload to other regions. With congestion intensity denoted by hi,j,k(t), the offloading delay magnitude is determined by the following equation [29]: Coff i,j,k(σj,k it , λj,k it , hi,j,k(t)) = (λj,k it −σj,k it )hi,j,k(t)(5) Now, the overall delay cost for the aggregate input workload is determined by summing the three aforementioned delays [29]: Cdelay i,j,k (σj,k it , λj,k it , hi,j,k(t), dj it) = Cwi i,j,k(λj,k it ) + Cloc i,j,k(σj,k it , dj it) + Coff i,j,k(σj,k it , λj,k it , hi,j,k(t)) (6) B. Problem Formulation Based on the system modeling above, we now formulate the Serverless workload scheduling problem to maximize green energy usage throughout a Continuum by dynamically adjusting the distribution of functions among cloud-edge nodes while meeting QoS and resource constraints. This adjustment is necessary to meet sustainability criteria by optimizing Serverless workloads and unequal distribution of power. When the green energy of all nodes is fully utilised, brown energy consumption can be calculated as (ej it −gj it +sj i(t−1)). The primary objective of the global controller is to minimize the usage of brown energy by maximizing the usage of green energy at ttime interval. Mathematically, the optimization objective is modeled as: min X t n X i=1 m X j=1 (max(ej it −gj it +sj i(t−1),0)) (7) Subject to:   n X i=1 m X j=1 αi,j,k t+βi,j,k t =  n X i=1 m X j=1 κi,j,k t ∀t∈T,∀bk∈B (8) κi,j,k t=yi,j t×min ℜ,&λj,k it ×πk qk'!∀t∈T,∀dj i∈D, ∀bk∈B (9) l X k=1 ((αi,j,k t+βi,j,k t)×qk)!≤(yi,j t×ω)∀t∈T,∀dj i∈D (10) fi,j,k w+fi,j,k p≤fi,j,k d(11) SOV (fi,j,k t, dj i)=SOV (fi,j,k t, dp) =⇒fi,j,k t×yi,j t= 0 (12) For any time period t, Eq. 8 ensures that all function replicas are scheduled, while Eq. 9 stipulates that no scheduling of microservices on a node takes place if the node is unavailable. Eq. 10 specifies that the total capacity required for assigned functions must not surpass the maximum available capacity ω of a node, either local or offloaded. Additionally, the incorporation of variable yi,j tprohibits assignment on unavailable nodes. Eq. 11 ensures that the expected maximum time to finish function execution must not violate the deadline. Here fi,j,k wis the waiting time for scheduling the function and fi,j,k p is the processing time for function. Eq. 12 guarantees that functions assigned to any node possess full authority and autonomy over their resources. A functions cannot be assigned to a node in a region that does not respect its sovereignty (SOV). Maintaining data sovereignty ensures that data is stored and processed in accordance with regulatory mandates throughout the Continuum. We suggest viewing data sovereignty as a collection of constraints [6] (e.g., regional whitelists, lists of excluded nodes/providers, etc.) to be integrated by the controller. However, the Serverless workload scheduling problem is not solvable in polynomial time due to its NP-hard nature. Therefore, we propose a novel stable matching based solution, as it offers an advantage by providing an approximate solution to this highly complex combinatorial optimization problem. The stable matching problem is a generalisation of the stable marriage problem treated in [33]. IV. STABLE MATCHING FOR SERVERLESS WORKLOAD SCHEDULING The formulated problem can be cast as the generalized assignment problem [31] such as a bin-packing problem [32] for which we can drive a promising solution by applying matching theory [30], [31]. Specifically, one function is only assigned to one node, while one node can host many functions depending on its available resources. By mapping this problem with matching theory [33], functions and nodes can be treated as the two sides of players involved in a many−to−one matching game. This matching idea is widely used in different types of applications such as VM allocation in cloud data centers to obtain the stable assignments [34], [35]. Therefore, we propose an algorithm inspired by the matching theory idea. A. Construction of Preference Lists Function’s preference list: Each function fi,j,k has a choice to match with any node in a region. However, since a function is concerned with energy benefit and QoS factors, it builds a preference order Pf(t)over the set of all available nodes applying the following relation: (dpj i(SoC, QoS)) ≻f(dj i(SoC, QoS)) (13) These preferences ensure the desirability of more sustainably powered nodes (energy-benefit) and avoid recurring replacements and deadline violations (QoS). Node’s preference list: Similarly, each node constructs a preference list over functions. This preference list is created according to the consolidation policy, in which each node prioritizes improving resource usage by hosting more functions. More specifically, a node dj iprefers to be allocated more functions to avoid resource wastage. Therefore, we apply the Best Fit algorithm [32] to build the preference list. We apply the norm-based metric [37] to locate a node with the most suitable resources. f≻df′⇔X q∈Q τq(fq−capq i)2< τq(f′ q−capq i)2(14) Here, τqrepresents the weight of resource type q. B. Properties for Matching Multiple functions can be assigned to one node based on preference functions and matching constraints. To understand the concepts of matching theory, we discuss the following properties: Matching Function: For a given set of functions Fand a set of nodes D, a matching function can be defined formally as µ:F∪D⇒2F∪Dsuch that: •µ(d)⊆Fsuch that |µ(d)|q≤capq i,∀d∈D, where |µ(d)| represents the aggregated resources of all functions that are matched to d. •µ(f)⊆Dsuch that |µ(f)|q=capq i, or |µ(f)|q= 0,∀f∈Fand d∈D, where |µ(f)|qis the node resources of dthat is matched to fand |µ(f)|q= 0 means that function fis not assigned. •f∈µ(d)if and only if µ(f) = d,∀f∈Fand d∈D, These matching properties are defined to be a many-to-one relation, where each regional node is matched to a subset of functions. The primary goal of a matching driven solution is to obtain an efficient and stable matching. In this matching game, each participating player specifies their preferences over the others based on their objectives in the Cloud-Edge Continuum. Blocking Pair: A matching µcan be blocked by an agents’ pair (f, d)if there exists a (f, d)pair where f /∈µ(d)and d /∈µ(f). Such a pair is termed a blocking pair. Stable: The obtained matching µis considered stable if (a) no blocking pairs exist and (b) all functions are allocated to Continuum nodes. C. Matching based Function Scheduling At each region, the function invocation requests are submitted to the local controller. If the region has not sufficient energy for function execution, then the global controller is notified. The allocation of functions requests to a node is Algorithm 1: Matching based Function Scheduling 1Input: Set of regions, set of nodes with respective resource capacities, set of functions with their required resource capacities, 2Output: A stable matching µof functions and nodes 3while t≤Tdo 4Phase 1: Initialization: 5/* Regions */ 6R← {R|ri,j,k t∈R, ri t=ψ} 7/* Nodes */ 8D← {D|dj i∈D, i =null} 9/* Resource Capacities */ 10 Cap ← {Cap|capj it ∈cap, capj it =γ} 11 /* State of Charge */ 12 S← {S|sj it ∈S, sj it =current SoC} 13 /* Functions */ 14 F← {F|fi,j,k t∈F, k =null} 15 Phase 2: Preference List Construction: 16 /* Creating a function’s preference list */ 17 for each function fi,j,k t∈Fdo 18 1. Find the candidate node dpj isuch that (dpj i(SoC, QoS)) ≻f(dj i(SoC, QoS)); 19 2. Add dpj iinto the preference list of node fi,j,k t. 20 end 21 /* Creating a node’s preference list */ 22 for each node dj i∈Ddo 23 1. Find the next function fi,j,k tsuch that capjq it ≥fi,j,k qt ,∀q∈Qand fi,j,k treleases the least amount of resources; 24 2. Add fi,j,k tinto the preference list of node dj i. 25 end 26 Phase 3: Matching: 27 while ∃fi,j,k t∈Fis not placed do 28 dj i←Find the top rank in P(fi,j,k t); 29 if capjq it ≥fi,j,k qt ,∀q∈Qthen 30 Assign fi,j,k tto dj i; 31 capjq it =capjq it −fi,j,k qt ,∀q∈Q; 32 end 33 else 34 Determine all f′ ti,j,k to satisfy fi,j,k t≻df′ ti,j,k; 35 Reject all f′ ti,j,k and mark f′ ti,j,k as unengaged; 36 Update node dj iresources as: 37 capjq it =capjq it +f′ qti,j,k,∀q∈Q 38 Eliminate f′ ti,j,k out of P(dj i); 39 Eliminate dj iout of P(f′ ti,j,k); 40 end 41 end 42 end performed by the local controller, based on the features of the functions, energy and QoS availability of nodes in the region provided it through the monitoring component of MAPE-K model. Now we discuss our proposed algorithm, as shown in Algorithm 1, which is a generalisation of the Gale and Shapley′sDeferred Acceptance Algorithm (DAA) [33] for many-to-one stable matching for two-sided matching markets. We execute Algorithm 1 on each local agent. In the Initialization phase, the local controller collects the current list of functions with their respective resource demands and QoS, as well as the list of nodes along with their resource availability, latest SoC values. In the Preference List Construction phase, we create function’s preference list and node’s preference list. In the function’s preference list, each function’s replica fi,j,k,l prefers to be located in the node that has better SoC and satisfies its resource constraints and desired QoS levels. Similarly, in the node’s preference list, each node builds a preference list over functions. This preference list is created according to the consolidation policy, in which each node prioritizes enhancing resource utilization by deploying more functions. Additionally, it implies that the node favors assignment over unassignment. The Matching phase is inspired by the deferred acceptance algorithm [33]. The matching procedure commences from some unassigned functions fi,j,k t. The function fi,j,k tselects the highest rank node dj ifrom its preference list P(fi,j,k t)to propose. If node dj ihas enough resources to place function fi,j,k t, it will accept the function fi,j,k t. However, if node dj ilacks the necessary resources, it rejects fi,j,k t. Before rejecting fi,j,k t, node dj irejects all its matched functions f′i,j,k tsuch that fi,j,k tis preferred over f′i,j,k t(i.e., (fi,j,k t)≻d(f′i,j,k t)). Subsequently, function fi,j,k tremoves node dj ifrom its preference list P(fi,j,k t)and restarts the proposing process. Consequently, the algorithm can eventually converge to a stable assignment of functions and nodes within a finite number of steps. D. Distributed Algorithm for Function Offloading The distributed algorithm for function offloading (shown in Algorithm 2) is a generalisation of the distributed stable matching problem [36]. The distributed algorithm operates in the following phases: The Local Controller() procedure: This procedure is executed by every local controller. 1) Firstly, in line 5−7it initializes the Function-PriorityList and the Deadline-Based-Priority-List for the region rjusing fi,j,k priority and fi,j,k drespectively. After that it builds an Offload-List of functions based on FunctionPriority-List and Deadline-Based-Priority-List. 2) It iteratively applies the constraints until the Offload− List becomes empty. From line 10 −11 it checks the deadline, priority, and available green energy in a local region. If it is satisfied, then it sends an offload message for function fi,j,k to the global controller and waits for a reply. 3) From line 12−20, if the reply is accepted then it offloads the function fi,j,k and removes the function from the Algorithm 2: Distributed Algorithm for Function Offloading 1Procedure Local Controller(): 2Input: Functions which are ready to offload 3Output: Offloading decision for each function in region 4begin 5Build an Function-Priority-List in which we rank the functions in the region rjusing fi,j,k priority 6Build a Deadline-Based-Priority-List in which we rank the functions in the region rjusing fi,j,k d 7Build a Offload-List of functions based on Function-Priority-List, and Deadline-Based-Priority-List 8while Offload-List =∅do 9fi,j,k ←first element of Offload-List 10 if (fi,j,k w+fi,j,k p> fi,j,k d)or fi,j,k priority =high and sj it < ζ then 11 sendMsg(offload,fi,j,k) 12 msg ←getMsg() 13 switch msg.type do 14 accepted: Offloading the function fi,j,k 15 rejected: if (fi,j,k w+fi,j,k p> fi,j,k d)or fi,j,k priority =high and sj it < ζ then 16 Execute the function locally using the brown energy. 17 else 18 Defer the execution of function for ∆θ time period. 19 Remove function fi,j,k from Offload-List 20 end 21 Procedure Global Controller(): 22 Input: Set of available regions and nodes. 23 Output: Offloading decision for each of the function in region 24 begin 25 stop ←false 26 while ¬stop do 27 msg ←getMsg() 28 switch msg.type do 29 offload: fi,j,k ←msg.function 30 if SOV (fi,j,k t, rj) = SOV (fi,j,k t, rjp)and sj it ≥ζand (fi,j,k w+fi,j,k p≤fi,j,k d)then 31 sendMsg(accepted) 32 else 33 sendMsg(rejected) 34 stop: stop ←true 35 end Offload−List. If the reply is rejected then it executes the function locally using brown energy and removes the function from the Offload−List, else it defers the execution of function for ∆θtime period until energy becomes available. 4) If the Offload −List becomes empty then a stop message is received. The Global Controller() procedure: This procedure is executed by the global controller 1) Wait for messages from local controller. 2) In line 25 −35, it receives the message from the local controller and checks the sovereignty, SoC, and completion time constraints; if it is satisfied, it sends an “accepted message” else it sends a “rejected message” to the local agent for fi,j,k . 3) Upon completing the procedure, a stop message is received. E. Algorithmic Analysis In this section, we discuss the complexity of the proposed algorithms. Theorem 1. The time complexity of the scheduling algorithm Algorithm 1 is O(FD(Flog2D+Flog2F)). Proof. : The complexity of the scheduling approach relies solely on the preference lists. For the function’s preference lists, the sorting operation for each function requires a complexity of O(Dlog2D). Therefore, the overall complexity to construct function preference lists is O(FD log2D)for the set Fof functions. Similarly, to build a node’s preference list, the complexity is O(DF log2F). Thus, the overall time complexity of Algorithm 1 is O(FD(Flog2D+Flog2F)). Theorem 2. The time complexity of the offloading algorithm Algorithm 2 is O(FlnF). Proof. : We provide various functions as input to the algorithm and receive decisions (e.g., offloading, local execution, or rejection) for each function. The overall time complexity of the offloading algorithm is O(FlnF), where Frepresents the total number of functions. This is computed as the sum of the number of functions available in the region. V. PERFORMANCE ANALYSIS We validate the efficacy of our proposed algorithm on simulated environments and compared with other baseline approaches. A. Experimental Settings We implement the algorithms on a machine with the following specifications: an Intel Core i7-12700 CPU running at 2.1 GHz with 12 cores and 32GB of RAM. We use the Java programming language, running on the OpenJDK Runtime Environment. To evaluate the performance of the algorithms in real-world settings, we assume a Continuum environment with four regions, where edge devices (e.g., Raspberry Pi model 3B+ and Raspberry Pi model 3B) and cloud servers (based on configurations from Google cluster traces [38]) are used. We randomly generate nodes Dranging from 50 to 100 per region, with the number of microservices per node varying from 1 to 10, executing real-world traces from Wikipedia [40] (for request arrival patterns) and Azure function traces [41] (for resource requirement and average execution times). These traces generate the load for 140 different application types, with a peak load of 16 times the number of requests per second. We use solar energy traces [39] to set the value of G. Each regional node receives different rates of energy input, and the maximum battery capacity is set to 1250 mWh. In the scalability analysis, we study the effect of varying battery sizes. The send and receive overhead values for function offloading are set to 0.02 and 0.01, as described in [13]. The study does not include an analysis of the impact of container startup delays. We conducted each experiment over a one-hour duration and repeated each experiment three times. B. Baseline algorithms We compare the performance of our proposed algorithm against the following baseline algorithms described in [13]: Local: This baseline always deploys functions locally, e.g., fi,j,k,l t→dj i. This is crucial to understanding the effect of computation offloading. Random: This baseline randomly places functions across the region. It showcases the worst-case setting, where the scheduler’s decision is made without any intelligence, First-Fit: This baseline assigns nodes to functions based on their arrival order, allocating them to the first available node that meets their requirements. C. Performance Metrics Satisfaction analysis: The satisfaction metric measures the effectiveness of conflict resolution between functions and regional nodes through stable matching. We determine the “satisfaction” of a match by considering the rank percentile of the selected partner (e.g., function or regional node). For regional nodes, satisfaction is determined by the average rank achieved across the matched functions. We assess the performance of satisfaction by varying the total number of functions and regional nodes. Request filtering: The objective of the request filtering metric is to reduce the number of offloading requests that fail to meet deadline constraints, thereby enhancing the latency of offloading decision-making. We also analyze the impact of various load-input data ratios (LDRs) on the filtering of requests. Throughput: Throughput measures the aggregated number of functions executed per second. Throughput time is influenced by multiple factors including network congestion and processing power. A higher optimization rate of the algorithm results in faster throughput. Green energy availability: This metric is defined as the percentage of time in which a node has enough battery charge to execute functions. It measures the availability and sustainability of regional nodes to meet the operational needs of functions. D. Evaluation Results Satisfaction analysis: Figures 3(a) and 3(b) illustrate the satisfaction percentages of functions and regional nodes respectively. In this experiment, we examine 50 nodes and increase the functions from 50 to 300. Matching satisfaction is evaluated using the average rank of matches for functions and nodes. Compared to the First-Fit benchmark algorithm, the proposed distributed matching heuristic significantly enhances node performance, effectively resolving conflicts between functions and regional nodes using stable matching. Unlike First-Fit, which only allows a uniform ranking of functions for all listed nodes, this approach enables regional nodes to express their preferences. Additionally, First-Fit cannot match a function to a node with insufficient capacity, resulting in no further rejections from nodes. In contrast, our algorithm allows rejections if a function is more preferable than other node’s functions throughout its execution, thus improving function and node satisfaction. For large-scale simulations, we vary the number of functions and nodes, and analyze overall satisfaction performance. As shown in Fig. 3(c), functions receive their top 6 to 8% preferences, while regional nodes obtain their 12 to 18% preferences, demonstrating that our approach effectively analyzes policies and resolves conflicts for large-scale scenarios. Request filtering: Request filtering primarily aims to reject offloading requests that cannot meet energy availability, request priority, and deadline constraints, thus minimizing overall delay in decision making. In Fig. 3(d), we analyze the request filtering effect by varying the offloading requests from 100 to 900. From Fig. 3(d), it is evident that the filtering process performs better when the LDR (Local Execution to offloading Delay Ratio) value is low (LDR=1.0), as most offloading request are communication-intensive and suitable for local execution due to time constraints. Thus, in each scenario, it is noticeable that with a high LDR value (LDR=1.5), requests are more likely to be offloaded due to their computation-intensive nature. Throughput vs. battery size of nodes: Fig. 3(e) analyzes the throughput for different battery size of nodes. The analysis shows a linear growth with larger batteries, as lowpowered nodes can remain available for longer periods offering continuous execution of requests. Conversely, the local and random approaches show the least improvement. It is also observed that, if we increase the battery sizes then not only well-powered and under utilized nodes, but also moderatelypowered nodes, can store more energy during peak times. Throughput vs. workload intensity: Fig. 3(f) analyzes throughput for different workload intensities. The graph shows an increasing trend with the rise in workload intensity (i.e., 25% to 100%). A crucial observation is the amplified variance in throughput between different schedulers as workload intensity increases. This demonstrates the importance of a green energy-aware dynamic scheduler to address demanding workloads effectively. Although the local scheduler consistently delivers a reasonable throughput, it lacks in meeting sustainability metrics.