Dynamic Resource Allocation on the Edge: A Causal and Contextually-Aware Machine Learning Approach

Dynamic Resource Allocation on the Edge: A Causal and Contextually-Aware Machine Learning Approach Chrysostomos Symvoulidis, Efterpi Paraskevoulakou, Athanasios Kiourtis, Argiro Mavrogiorgou, and Dimosthenis Kyriazis Dept. of Digital Systems, University of Piraeus, Piraeus, Greece {simvoul, e.paraskevoulakou, kiourtis, margy, dimos}@unipi.gr Abstract. A new age of distributed and decentralized computing architectures has emerged in recent years due to the rise of edge computing. However, despite its potential, edge computing faces a variety of challenges, and one critical issue lies in the optimization of resource utilization due to the diverse nature of edge environments. Although resource allocation regards a topic heavily discussed in the area of edge computing, traditional approaches cannot manage to address efficiently this problem due to the heterogeneous nature of such environments. Motivated by this, in this paper, a novel dynamic resource allocation strategy for edge computing infrastructures is proposed, capable of identifying contextual information and causal relationships between the factors that affect an edge computing system and encapsulate them into the framework in order to perform informed adaptation decisions. The proposed framework is evaluated extensively in a simulated environment and the results show that it manages to optimize resource allocation and enhance the overall performance of the edge computing environment significantly when utilized. Keywords: resource allocation, edge computing, machine learning, causalaware ai, context-awareness 1 Introduction In the recent years, the rise of edge computing has resulted in a new era of decentralized and distributed computing architectures. Edge computing, with its emphasis on processing data closer to the source, brings forth new opportunities for both consumers and businesses. From managing Internet of Things (IoT) devices for transportation [23], [7], to smart cities [6], [8], [9], edge computing has proven to be the most effective solution. Yet the challenges that still remain are plenty. One of the key challenges which needs to be addressed, regards in the efficient utilization of resources [21], [14] and the demand for real-time and context-aware applications [16] at the edge intensifies, the need for a robust dynamic resource allocation framework becomes increasingly important. 2 C. Symvoulidis et al. Traditional resource allocation strategies frequently fall short in addressing the complexity of edge computing environments, which are characterized by a variety of devices, varying workloads, and dynamic contextual factors [18]. For this reason, in this paper, a novel dynamic resource allocation framework is proposed. The proposed framework is designed to perform dynamic resource adaptations on the nodes of an edge computing infrastructure, such as the one shown in Figure 1. The designed framework performs predictions with a Machine Learning (ML) model, trained with a causally and contextually enhanced dataset which encompasses this information and allows the model to better generalize and adapt better to dynamic environments as an edge computing network. The remainder of this paper is constructed as follows: Section 2 provides a detailed analysis of the State-of-the-Art with respect to dynamic resource allocation and adaptation on the edge. Section 3 presents the problem formulation and describes the proposed dynamic resource allocation framework overview. Section 4 describes the evaluation in which the proposed framework was put under. Finally, Section 5 concludes the paper, and discusses future works based on the current research. 2 Related Work Dynamic resource allocation refers to the process of adapting the computing resources of a system based on the workload or demand. It is a research topic related to cloud computing [20], yet with the emergence of edge computing a major shift towards the research of resource allocation at the edge was acknowledged. To start with, Tang et al. [17] proposed a resource allocation strategy for latency-critical application in hybrid cloud and edge computing infrastructures. The proposed strategy is comprised of two algorithms, the resource scheduling algorithm and the resource matching algorithm. The first one, calculates the cost of scheduling tasks given the transmission cost between the data centers (i.e., the cloud infrastructure part) and the edge servers. Taking into account the outcomes of the resource scheduling algorithm, the resource matching algorithm optimizes the resources to be allocated for the given task on an edge server, taking into consideration the task priorities, the overall network transmission cost and the resource location. The authors of [3], proposed a computation and communication resources optimization for Mobile Edge Computing (MEC) environments towards the optimization of throughput using a dynamic throughput maximum (DTM) algorithm based on the Lyapunov optimization. In a similar manner, in [11] the authors proposed a resource allocation strategy for Virtual Machines (VM) in MEC, taking into consideration the users’ mobility [13]. Furthermore, the algorithm identifies the optimal path between the users and the deployed VM taking into consideration their movement. Based on the work found in [5] and [22], Gong et al. [4] proposed a Generative Adversarial Network (GAN)-assisted dynamic resource allocation scheme for MEC, in which they analyze the historical data set related to the users’ Dynamic Resource Allocation on the Edge 3 mobility to predict the demand for each edge node in the next time slot and perform allocation decisions according to this information information. 3 Dynamic Resource Allocation Framework Cloud Infrastructure Edge Node Edge Node Edge Server Edge Node Edge Node Fig. 1: The Hybrid Cloud / Edge architecture of the system. 3.1 Problem Formulation Consider an edge network as the one depicted in Figure 1. The edge network can be represented as a graph G, where G= (V, E), V={v1, v2, ..., vm}are the 4 C. Symvoulidis et al. edge nodes and E={e1, e2, ..., en}are the edges of the network connecting the nodes. The goal of the proposed resource allocation framework is twofold: (i) to predict the resource utilization for the nodes of the given edge network, (ii) dynamically adapt the resources of any given node depending on the predictions. For each node vi∈V,ci=c(vi) represents its storage capacity, mi=m(vi) represents its memory usage, and pi=p(vi) its CPU usage at any given time. Furthermore, for each node, lij =l(vi, vj) contains the calculated least distance between i-th and j-th nodes. Thus, a list of all least distances for any node iis found in the L={lij}distance matrix. The distance in this case refers to the physical distance (i.e., the number of edges that connect the two servers). In addition, the service migration cost wij between nodes iand jis measured. Furthermore, the transmission delay between any two nodes iand j(where jmaybe the actual user in the network) is defined as: tij = n X k=1 δ+Tproc +Ttrans (1) where δis the default delay of the edge that connects iand jin ms, Tproc the processing time of the service and Ttrans the transmission delay between iand jwhich is equal to dk bij , where dkis the size of the transmitted data and bij the available bandwidth for the edge iand j. Thus, the overall delay can be defined as the sum of all pairs tij for any i and j: T= m X i=1,j=1 tij (2) Given the above, the proposed framework needs to perform actions in order to optimize resource utilization of the overall edge network, while reducing the overall delay. 3.2 Dynamic Resource Allocation framework’s Components The proposed Dynamic Resource Allocation framework is comprised of the following components, as also depicted in Figure 3: (i) the Monitoring component, (ii) the Resource Usage Prediction component, (iii) the Intervention Model Generation component, and (iv) the Resources Adaptation component, which will all be further explained below. Monitoring component This component is used for monitoring the resources of all nodes in the edge network. It is in essence a system which monitors the edge nodes and keeps track of key metrics including CPU, and memory utilization, available disk storage, along with network metrics such as egress and ingress bandwidth, and latency. All metrics are then stored in a MySQL database. Dynamic Resource Allocation on the Edge 5 Fig. 2: The produced Causal Diagram which was utilized for the generation of the causal features. Resource Usage Prediction component This component is used for the prediction of the resource usage of any edge node at a given time. It utilizes a novel data enhancement method, as explained below, in order to predict the utilization of two key metrics; CPU and memory. First, it is important to discuss how the data is enhanced. In more detail, there are two methods used for the enhancement of the dataset. The first regards causal feature generation [13], while the second regards the identification of the most important instances in the dataset and the generation of the new enhanced dataset [15]. Starting with the causal features generation, as also shown in Algorithm 1, the process starts with the identification of the causal relationships among the features of the dataset. This is performed using the Direct Linear nonGaussian structural equation model (DirectLiNGAM) [12]. The outcome of DirectLiNGAM can be represented as an acyclic causal graph which each node represents a feature of the dataset and the edges represent a causal relationship between two features, as shown in Figure 2, such that if Aand Bare features of the dataset, then Ax −→ Bmeans that Ais a cause of B, while the number xon the arrow represents the causal influence of Aon B. Subsequently, for any target (i.e., in this case CPU usage and memory usage) the parents (i.e., the causes of those features) are selected. For each identified tuple of a target variable and its parent, and for each instance in the dataset, the number of instances that have the same value as the target variable, multiplied by the z-score (zi=ei−µ σ) 6 C. Symvoulidis et al. of the effect eiof its cause is calculated, as shown in Algorithm 1 (line 11). This represents the new causal feature which is then appended to the original dataset. The above procedure is repeated for every identified target feature or cause feature. Edge Node MEdge Node 2Edge Node 1 Real-time / Historical Data Service 1 Service 2 Service N Resources Monitoring Resource Usage Prediction Intervention Model Generation Resources Adaptation Fig. 3: High-level overview of the Dynamic Resource Allocation platform. Next, the identification of the influential instances and the generation of the contextually enhanced dataset takes place, as depicted in Algorithm 2. First, the ML algorithm is trained using the original dataset and the Mean Absolute Error (MAE) and the Root Mean Square Error (RMSE) are calculated. Afterwards, the instances of the dataset are evaluated with respect to their influence as follows. The instance is removed from the original dataset, the model is retrained and the two metrics are recalculated. If the model’s performance is worse (i.e., the RMSE and MAE are increased) this instance is considered influential, and it is appended to the influential instances dataset (I). Upon measuring its importance, the instance is inserted back into the original dataset. Once the above procedure is over, the remaining instances that were not initially considered influential are evaluated again by measuring the distance they have from any of the alreadyidentified influential instances. If this distance (measured in degrees since they are represented as a vector of an X-dimensional space, where Xis the number Dynamic Resource Allocation on the Edge 7 Algorithm 1 Causal Features generation. 1: dLiNGAM ←DirectLINGAM(D) 2: pc ←p c(dLiNGAM)if causal effect value eiis positive 3: for each tuple in pc do 4: calculate occurrences of an instance appears in the dataset for P(t|CFt) 5: end for 6: for each tuple iin pc do 7: max((P(t|CFt)) ←calculate max occurrences in the dataset for P(t|CFt) for any tuple in pc 8: min(P(t|CFt)) ←calculate min occurrences in the dataset for P(t|CFt) for any tuple in pc 9: end for 10: for each tuple iin pc do 11: causalF eaturei←P(t|CFt)−min(P(t|CFt)) max(P(t|CFt))−min(P(t|CFt)) ×zi\\ ziis the z-score of the effect ei 12: D:D ∪ causalF eaturei// Append the new causal feature to the existing dataset 13: end for 14: return D of the features) is less than a given value Θ, the instance is considered influential as well and appended to the Idataset. The above procedure only happens once, or every time the selected ML model is retrained. The process starts with selecting the monitoring information of a node from the monitoring data collected and stored in the MySQL database. Once the contextually enhanced dataset is generated, the ML model needs to be trained in order to forecast the CPU and memory utilization of a given edge node, given the collected historical data. Random Forest Regressor was selected with 1000 trees, since it has been proven efficient in such tasks [1]. Intervention Model Generation component This component is responsible for making the decisions with respect to the actions that need to be undertaken. Given the end goal, which is to reduce the overall latency of the network, and optimize resource usage, the Intervention Model Generation component has a set of options, taking into consideration the predictions made by the Resource Usage Prediction component. The goal is to reduce the average delay of the system and keep it under a given threshold, which in this case is set to 10 ms. If the average delay stays beneath this value, but the CPU and / or memory utilization is over 80% no changes are required to be made, while if the CPU or the memory utilization is below the 80% threshold the Intevention component requests freeing resources (scaling down) of those (edge) nodes with the least CPU and memory utilization in order to free unused resources. On the other hand, if the average delay exceeds the 10 ms threshold, it requests deploying the service . 8 C. Symvoulidis et al. Algorithm 2 Context identification and dataset enhancement. 1: fit(D) 2: I= [ ] 3: calculate MAE(D) 4: calculate RMSE(D) 5: for i∈ D do 6: D−i:i /∈D 7: fit(D−i) 8: calculate MAE(D−i) and RMSE(D−i) 9: if RMSE(D−i)≥RMSE(D) && MAE(D−i≥MAE(D)then 10: I:I ∪ i 11: D:D − i 12: end if 13: end for 14: for i:i∈ D ∧ i /∈ I and k :k∈ I do 15: if θ(i, k)≤Θand i=kthen 16: I:I ∪ i 17: end if 18: end for 19: return I Resource Adaptation component This component is responsible for performing the necessary adaptations to the edge infrastructure as indicated by the Intervention component. In more detail, in the fist case where scaling down is requested, the Resources Adaptation component, based also on the real-time monitoring information coming from the Monitoring component, identifies the nodes with the least CPU and / or memory utilization and requests a downscale. In the second case, the Resources Adaptation component, starts with scaling up on the nodes with the highest resource utilization. If this adaptation is sufficient and the average delay meets the 10 ms threshold, no other changes are required. Alternatively, if this change does not succeed to reduce the average latency (after a given number of iterations), the Resource Adaption component identifies the nodes with the highest utilization and those with the least utilization and performs a service migration in order to utilize those nodes more efficiently, given that their current CPU and memory utilization along with their available storage capacity allows the services to be deployed there. 4 Performance Evaluation In order to evaluate the proposed resource allocation framework different simulations were executed in an edge computing network as described below. The network topology regards a randomly generated network graph G, with 50 edge servers. 100 services were initially deployed randomly and were set to require 5−10% of CPU, 10 −15% of memory and 1 −5% of storage. When they were first deployed, they were assigned 10−15% of the server’s available CPU, 15−20% Dynamic Resource Allocation on the Edge 9 of memory, and 5 −10% storage capacity. The edges of the graph represented the delay which was randomly set in the range of 6 −20 ms. 1000 users were gradually introduced into the edge network and the latency between the users and the node to which they were connected was also randomly set from 6 to 20 ms. The different kinds of services can be categorized as CPUor memoryintensive and various simulations were executed. For instance, when it comes to CPU-intensive applications, every 10 users required an additional 5% CPU on the service they were using. Fig. 4: Comparison of average CPU utilization for the entire edge network. In order to assess the proposed resource allocation framework, the following metrics were used: the average latency, CPU and memory utilization for the overall edge network, and 3 metrics related to the performance of the Resource Usage Prediction component. Given that in both cases for the CPU and memory utilization this was a time-series forecasting (regression) task, the utilized metrics that were used are Mean Squared Error (MSE), Mean Absolute Error (MAE), and the R2-score. To start with the overall performance of the proposed framework, the results show that the overall latency was improved when compared to the edge network when the resource adaptation was not utilized. As depicted in Figures 4, 5, and 6, the results show that the proposed approach managed to significantly reduce the average utilization of the network’s computing resources, while reducing the average latency.