{'fraction_non_alphanumeric': 0.030562532661283524, 'fraction_numerical': 0.012659934930294499, 'mean_word_length': 4.62720546385885, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dynamic Scheduling for Stochastic Edge-Cloud Computing Environments using A3C learning and Residual Recurrent Neural Networks

The ubiquitous adoption of Internet-of-Things (IoT) based applications has resulted in the emergence of the Fog computing paradigm, which allows seamlessly harnessing both mobile-edge and cloud resources. Efficient scheduling of application tasks in such environments is challenging due to constrained resource capabilities, mobility factors in IoT, resource heterogeneity, network hierarchy, and stochastic behaviors. xisting heuristics and Reinforcement Learning based approaches lack generalizability and quick adaptability, thus failing to tackle this problem optimally. They are also unable to utilize the temporal workload patterns and are suitable only for centralized setups. However, Asynchronous-Advantage-Actor-Critic (A3C) learning is known to quickly adapt to dynamic scenarios with less data and Residual Recurrent Neural Network (R2N2) to quickly update model parameters. Thus, we propose an A3C based real-time scheduler for stochastic Edge-Cloud environments allowing decentralized learning, concurrently across multiple agents. We use the R2N2 architecture to capture a large number of host and task parameters together with temporal patterns to provide efficient scheduling decisions. The proposed model is adaptive and able to tune different hyper-parameters based on the application requirements. We explicate our choice of hyper-parameters through sensitivity analysis. The experiments conducted on real-world data set show a significant improvement in terms of energy consumption, response time, Service-Level-Agreement and running cost by 14.4%, 7.74%, 31.9%, and 4.64%, respectively when compared to the state-of-the-art algorithms.


INTRODUCTION
The advancements in the Internet of Things (IoT) have resulted in a massive amount of data being generated with enormous volume and rate. Applications that access this data, analyze and trigger actions based on stated goals, require adequate computational infrastructure to satisfy the requirements of users [1]. Due to increased network latency, traditional cloud-centric IoT application deployments fail to provide quick response to many of the time-critical applications such as health-care, emergency response, and traffic surveillance [2]. Consequently, emerging Edge-Cloud is a promising computing paradigm that provides a low latency response to this new class of IoT applications [3], [4], [5]. Here, along with remote cloud, the edge of the network have limited computational resources to provide a quick response to time-critical applications.
The resources at the edge of the network are constrained due to cost and feasibility factors [6]. Efficient utilization of Edge resources to accommodate a greater number of applications and to simultaneously maximize their Quality of Service (QoS) is extremely necessary. To achieve this, ideally, we need a scheduler that efficiently manages workloads and underlying resources. However, scheduling in the between different interdependent parameters. Recent works have explored different value-based RL techniques to optimize several aspects of Resource Management Systems (RMS) in distributed environments [16], [17], [18], [19]. Such methods store a Q value function in a table or using a Neural network for each state of the edge-cloud environment, which is an expected cumulative reward in the RL setup [20]. The tabular value-based RL methods face problem of limited scalability [21], [22], [23], for which researchers have proposed various Deep learning based methods like Deep Q Learning (DQN) [24], [25], [26] which use a neural network to approximate the Q value. However, previous studies have shown that such value-based RL techniques are not suitable for highly stochastic environments [27], which make them perform poorly in Edge-Cloud deployments. Limited number of works exist which are able to leverage policy gradient methods [28] and optimize for only a single QoS parameter and do not use asynchronous updates for faster adaptability in highly stochastic environments. Moreover, all prior works do not exploit temporal patterns in workload, network and node behaviours to further improve scheduling decisions. Furthermore, these works use a centralized scheduling policy which is not suitable for decentralized or hierarchical environments. Hence, this work maps and solves the scheduling problem in stochastic edge-cloud environments using asynchronous policy gradient methods which can recognize the temporal patterns using recurrent neural networks and continuously adapt to the dynamics of the system to yield better results.
In this regard, we propose a deep policy gradient based scheduling method to capture the complex dynamics of workloads and heterogeneity of resources. To continuously improve over the dynamic environment, we use the asynchronous policy gradient reinforcement learning method called Asynchronous Advantage Actor Critic (A3C). A3C, proposed by Mnih et al. [27], is a policy gradient method for directly updating a stochastic policy which runs multiple actor-agents asynchronously with each agent having it's own neural network. The agents are trained in parallel and update a global network periodically, which holds shared parameters. After each update, the agents resets their parameters to those of the global network and continue their independent exploration and training until they update themselves again. This method allows exploration of larger state-action space quickly [27] and enables models to rapidly adapt to stochastic environments. Moreover, it allows us to run multiple models asynchronously on different edge or cloud nodes in a decentralized fashion without a single point of failure. Using this, we propose a learning model based on Residual Recurrent Neural Network (R2N2). The R2N2 model is capable of accurately identifying the highly nonlinear patterns across different features of the input and exploiting the temporal workload and node patterns, with residual layers increasing the speed of learning [29]. Moreover, the proposed scheduling model can be tuned to optimize the required QoS metrics based on the application demands using the adaptive loss function proposed in this work. To that end, minimizing this loss function through policy learning helps achieve highly optimized scheduling decisions. Unlike heuristics, the proposed framework can adapt to the new requirements as it contin-uously improves the model by tuning parameters based on new observations. Furthermore, policy gradient enables our model to quickly adapt allocation policy responding to the dynamic workload, host behaviour and QoS requirements, compared to traditional DQN methods. The experiment results using an extended version of iFogSim Toolkit [30] with elements of CloudSim 5.0 [31] show the superiority of our model against existing heuristics and previously proposed RL models. Our proposed methodology achieves significant efficiency for several critical metrics such as energy, response time, Service Level Agreements (SLA) violation [8] and cost among others.
In summary, the key contributions of this paper are: • We design an architectural system model for the datadriven deep reinforcement learning based scheduling for Edge-Cloud environments. • We outline a generic asynchronous learning model for scheduling in decentralized environments. • We propose a Policy gradient based Reinforcement learning method (A3C) for stochastic dynamic scheduling method. • We demonstrate a Residual Recurrent Neural Network (R2N2) based framework for exploiting temporal patterns for scheduling in a hybrid Edge-Cloud setup. • We show the superiority of the proposed solution through extensive simulation experiments and compare the results against several baseline policies. The rest of the paper is organized as follows. Section 2 describes the system model and also formulates the problem specifications. Section 3 explains a generic policy gradient based learning model. Section 4 explains the proposed A3C-R2N2 model for scheduling in Edge-Cloud environments. The performance evaluation of the proposed method is shown in Section 5. The relevant prior works are explained in Section 6. Conclusions and future directions are presented in Section 7.

SYSTEM MODEL AND PROBLEM FORMULATION
In this section, we describe the system model and interaction between various components that allow an adaptive reinforcement-based scheduling. In addition, we describe the workload model and problem formulation.

System Model
In this work, we assume that the underlying infrastructure is composed of both edge and cloud nodes. An overview of the system model is shown in Figure 1. The edge-cloud environment consists of distributed heterogeneous resources in the network hierarchy, from the edge of the network to the multi-hop remote cloud. The computing resources act as hosts for various application tasks. These hosts can vary significantly in their compute power and response times. The edge devices are closer to the users and hence provide much lower response times but are resource-constrained with limited computation capability. On the other hand, cloud resources (Virtual Machines) located several hops away from the users, provide much higher response time. However, cloud nodes are resource enriched with increased computational capabilities that can process multiple tasks concurrently.

Fog Nodes
Cloud Nodes  The infrastructure is controlled by a Resource Management System (RMS) which consists of Scheduling, Migration and Resource Monitoring Services. The RMS receives tasks with their QoS and SLA requirements from IoT devices and users. It schedules the new tasks and also periodically decides if existing tasks needs to be migrated to new hosts based on the optimization objectives. The tasks' CPU, RAM, bandwidth, and disk requirements with their expected completion times or deadlines affect the decision of the RMS. This effect is simulated using a stochastic task generator known as the Workload Generation Module (WGM) following a dynamic workload model for task execution described in the next subsection.
In our model, the Scheduler and Migration services interact with a Deep Reinforcement Learning Module (DRLM), which suggests placement decision for each task (on hosts) to the former services. Instead of a single scheduler, we run multiple schedulers with separate partitions of tasks and nodes. These schedulers can be run on a single node or separate edge-cloud nodes [27]. As shown in prior works [27], [32], having multiple actors learn parameter updates in an asynchronous fashion allows computational load to be distributed among different hosts, allowing faster learning within the limits of resource constrained edge devices. Thus, in our system, we assume all edge and cloud nodes to accumulate local gradients to their schedulers and add and synchronize gradients of all such hosts to update their models individually. Our policy learning model is part of the DRLM with each scheduler with a separate copy of the global neural network, which allows asynchronous updates. Another vital component of the RMS is the Constraint Satisfaction Module (CSM) which checks if the suggestion from the DRLM is valid in terms of constraints such as whether a task is already in migration or the target host is running at full capacity. The importance and detailed functionality of CSM is explained in Section 3.2.

Workload Model
As described before, task generation is stochastic and each task has a dynamic workload. Based on changing user demands and mobility of IoT devices, the computation and bandwidth requirements of the tasks change with time. As done in prior works [8], [30], we divide our execution time into scheduling intervals of equal duration. The scheduling intervals are numbered based on their order of occurrence as shown in Figure 2. The i th scheduling interval is shown as SI i , which starts at time t i and continues till the beginning of the next interval i.e., t i+1 . In each SI i , the active tasks are those that were being executed on the hosts and are denoted as a i . Also, at the beginning of SI i , the set of tasks that get completed is denoted as l i and the new tasks that are sent by the WGM are denoted as n i . The tasks l i leave the system and new tasks n i are added to the system. Thus, at the beginning of the interval SI i , the active tasks a i is a i−1 ∪ n i \ l i .

Problem Formulation
The problem that we consider is to optimize the performance of the scheduler in the edge-cloud environment as described in Section 2.1 and dynamic workload described in Section 2.2. The performance of the scheduler is quantified by the metric denoted as Loss defined for each scheduling interval. The lower the value of Loss, the better the scheduler. We denote loss of the interval SI i as Loss i .
In the edge-cloud environment, the set of hosts is denoted as Hosts and its enumeration as [H 0 , H 1 , ..., H n ]. We assume that the maximum number of hosts at any instant of the execution is n. We also denote host assigned to a task T as {T }. We define our scheduler as a mapping between the state of the system to an action which consists of host allocation for new tasks and migration decision for active tasks. The state of the system at the beginning of SI i , denoted as State i , consists of the parameter values of Hosts, remaining active tasks of the previous interval which (a i−1 \ l i ) and new tasks (n i ). The scheduler has to decide for each task in a i (= a i−1 ∪ n i \ l i ), the host to be allocated or migrated to, which we denote as the Action i for SI i . However, all tasks may not be migratable. Let m i ⊆ a i−1 \ l i be the migratable tasks. Thus, Action i = {h ∈ Hosts for task T |T ∈ m i ∪ n i } which is a migration decision for tasks in m i and allocation decision for tasks in n i . Thus scheduler, denotes as M odel, is a function: State i → Action i . The Loss i of an interval depends on the allocation of the tasks to hosts i.e., Action i by the M odel. Hence, for an optimal M odel, the problem A symbol table for ease of meaning recall and a Venn diagram of various task sets are given in Table 1 and Figure  3, respectively.

REINFORCEMENT LEARNING MODEL
We now propose a Reinforcement Learning model for the problem statement described in Section 2.3 suitable for policy gradient learning. First, we present the input and output specifications of the Neural Network and then describe the modeling of Loss i (from Equation 1) in our model.

Input Specification
The input of the scheduler M odel, is the State i which consists of the parameters of hosts, which include utilization and capacity of CPU, RAM, bandwidth, and disk [16]. It also includes the power characteristics, cost per unit time, Million Instructions per Seconds (MIPS) for the host, response time, and the number of tasks to which this host is allocated. Different hosts would have different computational power (CPU), memory capacity (RAM) and I/O availability (disk and bandwidth). As tasks in an edge-cloud setup impose compute, memory and I/O limitations, such parameters are crucial for scheduling decisions. Moreover, allowing multiple tasks to be placed on a small cluster of hosts could ensure low energy usage (hibernating the ones with no tasks). A host with higher I/O capacity (disk read/write speeds) could allow I/O intensive tasks to be completed quickly and prevent SLA violations. All these parameters are defined for all hosts in a feature vector denoted as F V Hosts i as shown in Figure 4(a). The tasks in a i are segregated into two disjoint sets: n i and a i−1 \l i . The former consists of parameters like task CPU, RAM, bandwidth, and disk requirements. The latter also consists of the index of the host assigned in the previous interval. The feature vectors of these set of tasks are denoted as F V ni i and F V ai−1\li i as shown in Figures 4(b) and 4(c) respectively. Thus, , which is the input of the model.

Output Specification
At the beginning of the interval SI i , the model needs to provide a host assignment for each task in a i based on the input State i . The output, also denoted as Action i is a host assignment for each new task ∈ n i and migration decision for remaining active tasks from previous interval ∈ a i−1 \ l i . This assignment must be valid in terms of the feasibility constraints such that each task which is migrated must be migratable to the new host (we denote migratable task as m i which is ⊆ a i ), i.e., it is not under migration. Moreover, when a host h is allocated to any task T , then after allocation h should not get overloaded i.e., h is suitable for T . Thus, we describe Action i through Equation 2 such that for the (2) However, developing a model that provides a constrained output is computationally difficult [33] hence, we use an alternative definition of model action which is unconstrained. We compensate for the constraints in the objective function. In the unconstrained formulation of the model action, the output would be a priority list of hosts for each task. Thus, for task T ai j , we have a list of hosts [H 0 j , H 1 j , ..., H n j ] in decreasing order of allocation preference. For a neural network, the output could be a vector of allocation preference for each host for every task. This means that rather than specifying a single host for each task, the model provides a ranked list of hosts. We denote this unconstrained model action for policy gradient setup as Action P G i as shown in Figure 5. This unconstrained action cannot be used directly for updating the task allocation to hosts. We need to select the most preferable host for each task which is suitable for only those tasks that are migratable. To convert Action P G i to Action i is straightforward as shown in Equation 3. For it is not migrated. Otherwise, T ai j will be allocated to the highest rank host which is suitable. By the conversion of Equation 3, Action i always obeys constraints specified in Equation 2 and hence is used for model update as Additionally, we define penalty for the unconstrained action as in Equation 4. This captures two aspects of penalty: (1) the migration penalty as the fraction of tasks that the model wanted to migrate but cannot be migrated to the total number of tasks and (2) the host allocation penalty as the sum for each task, the number of hosts that could not be allocated to that task but were given higher preference. This penalty would be used in the Loss function defined in Section 3.3. The first addend in Equation 4 captures the host allocation penalty and the second addend captures the migration penalty and this penalty guides the learning model to make decisions based on the constraints in Equation 2. Thus, we define penalty as: Hence, the output Action P G i is first processed by the CSM to generate Action i and P enalty i+1 . Now, to update the parameters of the model at the beginning of SI i , we incorporate both Loss i and P enalty i as described in the next subsection.

Loss Function
In our learning model, we want the model to be optimum to reduce Loss i in each interval and hence the cumulative loss. Also, we want our model, which is a mapping from State i to Action i , to adapt to the dynamically changing state. For this, we now define Loss i , which acts as a metric for parameter update for the model. First, we define various metrics (normalized to [0,1]) which help us to define Loss i . 1) Average Energy Consumption (AEC) is defined for any interval as the energy consumption of the infrastructure (which includes all edge and cloud hosts) normalized by the maximum power of the environment. However, edge and cloud nodes may have different energy sources like energy harvesting devices for edge and main supply for cloud [34]. Thus, we multiply the energy consumed by a host h ∈ Hosts by a factor α h ∈ [0, 1] which can be set for edge and cloud nodes as per the user requirement and deployment strategy. The power is normalized as where P h (t) is the power function of host h with time, and P max h is maximum possible power of h. 2) Average Response Time (ART) is defined for an interval SI i as the average response time for all leaving tasks (l i+1 ) in that interval normalized by maximum response time until the current interval as shown in Equation 6. The task response time is the sum of host (on which this task is scheduled) response time and task execution time.
Hence ART is defined as . (6) 3) Average Migration Time (AMT) is defined for an interval SI i as the average migration time for all active tasks (a i ) in that interval normalized by maximum migration time until the current interval as shown in Equation 7. AMT is defines as: . (7) 4) Cost (C) is defined for an interval SI i as the total cost incurred during that interval as shown in Equation 8, where C h (t) is the cost function for host h with time, and C max h is maximum cost per unit for host h.

5) Average SLA Violations (SLAV) is defined for an interval
SI i as the average number of SLA violations in that interval for leaving task (l i+1 ) as shown in Equation 9. SLA(t) of task T is defined in [8] which is product of two metrics: (i) SLA violation time per active host and (ii) performance degradation due to migrations. Thus, To minimize the above mentioned metrics, as done in various prior works [16], [35], we define Loss i as a convex combination of these metrics for interval SI i−1 . Thus, Based on different user QoS requirements and application settings different values of hyper-parameters (α, β, γ, δ, ) may be required. Say for energy sensitive applications [36], [37], [38], we need to optimize energy even though other metrics might get compromised. Then the loss would have α = 1 and rest 0. For response timesensitive applications like healthcare monitoring or traffic management [39], the loss would have β = 1 and rest 0. Similarly, for different applications, a different set of hyperparameter values is required. Now, for the Neural Network model we need to include the penalty as well because the output described in Section 3.2 is unconstrained, as done in other works [40], [41]. If , then the model updates its parameters to not only minimize Loss i but also to satisfy constraints described in Equation 2. Thus, we define the loss for the Neural Network as shown in Equation 11. So,

Model update
Having defined the input-output specifications and the loss function we now define the procedure to update the Model after every scheduling interval. A summary of the interaction and model update for the transition from interval SI i−1 to the interval SI i is shown in Figure 6. We consider an episode to contain n scheduling intervals. At the beginning of every scheduling interval say SI i , the WGM sends new tasks to the Scheduling and Migration Service (SMS). Then, SMS and WGM send the State i to the DRLM which includes the feature vectors of hosts, remaining active tasks from previous interval (a i−1 \ l i ) and new tasks (n i ). Also, the RMS sends the Loss i to the DRLM. The CSM sends P enalty i based on decision of Action P G i−1 .The model then generates an Action P G i and updates its parameters based on Equation 11. which is sent to the CSM. The CSM converts Action P G i to Action i and sends it to RMS. It also calculates and stores P enalty i+1 for next interval SI i+1 . The RMS allocates new tasks (n i ) and migrates remaining tasks from previous interval (a i−1 \ l i ) based on Action i received from CSM. This updates a i−1 to a i as a i ← a i−1 ∪ n i \ l i . The tasks in a i execute for the interval SI i and the cycle repeats for the next interval SI i+1 .

POLICY GRADIENT LEARNING
The complete framework works as follows: at the beginning of every scheduling interval, (1) the RMS receives the task requests including task parameters like computation, bandwidth and SLA requirements.   4) For the new tasks, the RMS informs the user/IoT device to send its request directly to the corresponding edge/cloud device scheduled for this task. (5) The loss function is calculated for the DRL model and its parameters are updated. The formulation and the learning model described earlier in Section 3 is generic for any policy based RL model. The model, which is a function form State i to Action P G i is assumed to be the theoretically best function for minimizing Loss P G i . There exist many prior works which try to model this function using Q-Table or a neural network function approximator [16], [24], [26] giving a deterministic policy which is unable to adapt in stochastic settings. However, our approach tries to approximate the policy itself and optimize it using policy gradient methods with Loss P G i as a signal to update the network.

Neural Network Architecture
To approximate the function from State i to Action P G i for every interval SI i , we use a R2N2 network. The advantage of using an R2N2 network is its ability to capture complex temporal relationships between the inputs and outputs. The architecture with the layer description used for the proposed work is shown in Figure 7. A single network is used to predict both policy (actor head) and cumulative loss after the current interval (critic head).
The R2N2 network has 2 fully connected layers followed by 3 recurrent layers with skip connections. A 2-dimensional input is first flattened and then passed through the dense layers. The output of the last recurrent layer is sent to the two network heads. The actor head output is of size 10 4 which is reshaped to a 2-dimension 100 × 100 vector. This means that the this model can manage maximum 100 tasks and 100 hosts. This is done for a fair comparison with other methods that have tested on similar settings [8], [16], but for a larger system the network must be changed accordingly. Finally, softmax is applied across the second dimension so that all values are in [0,1] and the sum of all values in a row equals 1. This output (say O) can be interpreted as a probability map where O jk represents the probability with which task T ai j should be assigned to host H k which is k th host in an enumeration of Hosts. The output of the critic head is a single constant which signifies the value function i.e., the cumulative loss starting from next interval (CLoss P G i+1 ). The recurrent layers are formed using Gated Recurrent Units (GRUs) [42], which model the temporal aspects of the task and host characteristics including tasks' CPU, RAM and bandwidth requirements and hosts' CPU, RAM and bandwidth capacities. Although the GRU layers help in taking an informed scheduling decision by modeling the temporal characteristics, they increase the training complexity due to large number of network parameters. This is solved by using the skip connections between these layers for faster gradient propagation.

Pre-processing and Output Conversion
The input to the model for the interval SI i is . Among these vectors, the values of all elements of the first two are continuous, but the host index in each row of F V ai−1\li i is a categorical value. Hence, the host indices are converted to a one-hot vector of size n and all feature vectors are concatenated. After this, each element in the concatenated vector is normalized based on the minimum and maximum values of each feature and clipped between [0,1]. We denote the feature of element e as f e , and minimum and maximum values for feature f as min f and max f respectively. These minimum and maximum values are calculated based on a sample dataset using two heuristic-based scheduling policies: Local-Regression (LR) for task allocation and Maximum-Migration-Time (MMT) for task selection as described in [8]. Then, the feature-wise standardization is done based on Equation 12. Hence, This pre-processed input is then sent to the R2N2 model which flattens it and passes through the Dense layers. The output generated O is converted to Action P G i by first generating the sorted list of host SortedHosts i with decreasing probability in O i for all i. Then, Action P G i (T mi∪ni k ) ← SortedHosts k ∀ k ∈ {1, 2, ..., |m i ∪ n i |}.

Policy Learning
To learn the weights and biases of the R2N2 network, we use the back-propagation algorithm with reward as −Loss P G i . For the current model, we use adaptive learning rate starting from 10 −2 and decrease it to 1/10 th when the absolute sum of of change in the reward for the last ten iterations is less than 0.1. Using reward as −Loss P G i , we perform Automatic Differentiation [43] to update the network parameters. We accumulate the gradients of local networks at all edge nodes asynchronously and update the global network parameters periodically as described in [27]. The gradient accumulation rule after the i th scheduling interval is given by Equation 13 similar to the one in [27]. Here θ denotes the global network parameters and θ denotes the local parameters (only one gradient is set because of a single network with two heads). (Action i , P enalty i+1 ) ← CONSTRAINTSATISFAC-TIONMODULE(probabilityM ap) 10: Allocate new tasks and migrate existing tasks based on Action i

11:
Execute tasks in edge-cloud infrastructure for interval SI i 12: end for End State i . To minimize this, the gradients are proportional to this quantity and have a minus sign to reduce total loss. The second gradient term is the Mean Square Error (MSE) of the predicted cumulative loss with the cumulative loss after one-step look-ahead. The output Action P G i is converted to Action i by CSM and sent to the RMS every scheduling interval. Thus, for each interval, there is a forward pass of the R2N2 network. For back-propagation, we use a episode size of 12, thus we save the experience of the previous episode to find and accumulate gradients and update model parameters after 12 intervals. For large batch sizes, parameter updates are slower and for small ones the gradient accumulation is not able to generalize and has high variance. Accordingly, empirical analysis has resulted into optimal episode size of 12. As described in Section 5.1, the experimental setup has a scheduling interval of 5 minutes, and hence back-propagation is performed every 1 hour of simulation time (after 12 intervals) .
A summary of the model update and scheduling with back-propagation is shown in Algorithm 1. To decide the best possible scheduling decision for each scheduling interval, we iteratively pre-process and send the interval state to the R2N2 model with the loss and penalty to update the network parameters. This allows the model to adapt on-the-fly to the environment, user and application specific requirements.
Complexity Analysis: The complexity of Algorithm 1 depends on multiple tasks. The pre-processing of the input state is O(ab) where a × b is the maximum size of feature vector among the vectors F V Hosts To generate the Action i and P enalty i the CSM takes O(n 2 ) time for n hosts and tasks based on Equations 4 and 3. As the feature vectors have a higher cardinality than the number of hosts or tasks, O(ab) dominates O(n 2 ). Therefore, discarding the forward pass and back-propagation (as they are performed in Graphics Processing Units -GPU [44]), for N scheduling intervals, the total time complexity is O(abN ).

PERFORMANCE EVALUATION
In this section, we describe the experimental set up, evaluation metrics, dataset and give a detailed analysis of results comparing our model with several baseline algorithms.

Experimental Set Up
To evaluate the proposed Deep Learning-based scheduling framework, we developed a simulation environment by extending the elements of iFogSim [30] and CloudSim toolkits [31] which already have resource monitoring services inbuilt. As described in Section 4.3, the execution of the simulation was divided into equal-length scheduling intervals. The interval size was chosen to be 5 minutes long, same as in other works [8], [16], [24] for a fair comparison with baseline algorithms. The tasks, named as Cloudlets in iFogSim nomenclature, are generated by the WGM based on Bitbrain dataset [45]. We extended the modules of iFogSim and CloudSim to allow the use of parameters like response time, cost and power of edge nodes. We also created new modules to simulate mobility of IoT devices using bandwidth variations, delayed execution of tasks and interact with deep learning software. Additional software for Constraint Satisfaction Module, input pre-processing and output conversion was developed.
The loss function is calculated based on host and task monitoring services in CloudSim. The penalty is calculated by the CSM and sent to the DRLM for model parameter update. We now describe in more detail the dataset, task generation and duration implementation, hosts' configuration and metrics for evaluation.

Dataset
In the simulation environment, the tasks (cloudlets) are assigned to Virtual Machines (VMs) which are then allocated to hosts. For the current setting of task on edge-cloud environment, we consider a bijection from cloudlets to VMs by allocating i th created Cloudlet to i th created VM and discard the VM when the corresponding Cloudlet is completed. The dynamic workload is generated for cloudlets based on realworld open-source Bitbrain's dataset [45] 1 .
The Bitbrain's dataset [45] has real traces of resource consumption metrics of business-critical workload hosted on Bitbrain infrastructure. This data includes logs of over 1000 VMs workload hosting on two types of machines. We have 1 , where the latter also has an index of host allocated in the previous scheduling/simulation interval. The CPU, RAM, network bandwidth and disk characteristics for a random node and its trace in the BitBrain dataset are shown to be highly volatile in Figure 8.
We divide the dataset into two partitions of 25% and 75% VM workloads. The larger partition is used for training of the R2N2 network and the former partition is used for testing of the network, sensitivity analysis and comparison with other related works.

Task generation and duration configuration
In the proposed work, we consider a dynamic task generation model. Prior work [8] does not consider a dynamic task generation environment, which is not close to the real-world setting. At the beginning of every interval, the WGM sends n i new tasks where |n i | is normal distributed N (µ n , σ 2 n ). Also, each task t ∈ n i has an execution duration of N (µ t , σ 2 t ) seconds. In our setting, we kept 100 hosts and no more than 100 tasks in the system being scheduled on 10 actor-agents (schedulers). We keep in our simulation environment: (µ ni , σ ni ) = (12, 5) and (µ t , σ t ) = (1800, 300) seconds for number of new tasks and duration of tasks respectively. At the time of task creation, for already active |a i−1 \ l i | tasks, we only create min(100 − |a i−1 \ l i |, N (µ ni , σ 2 ni )) tasks so that |a i | does not exceed 100. This limit is required because the size of the input to the R2N2 network has a prefixed upper limit which in our case is 100.

Hosts -Edge and Cloud nodes
The infrastructure considered in our studies is a heterogeneous edge-cloud based environment. Unlike prior work [16], [24], [25], [26], we consider both resource-constrained edge-cloud devices closer to the user and thus having lower response time and also resource-abundant cloud nodes with much higher response time. In our settings, we have considered response time of edge-cloud nodes to be 1 ms and that of cloud nodes to be 10 ms based on the empirical studies using the Ping utility in an existing edge-cloud framework namely FogBus [4].
Moreover, the environment considered is heterogeneous with a diverse range of computation capabilities of edge and cloud host. A summary of CPU, RAM, Network and other capacities with the Cost Model is given in Table 2  nodes, the cost is based on the energy consumed by the edge node. As per the targeted environment convention, we choose resource-constrained machines at edge (Intel i3 and Intel i5) and powerful rack server as cloud nodes (Intel Xeon). The power consumption averaged over the different SPEC benchmarks [46] for respective machines is shown in Table 2. However, the power consumption values shown in Table 2 are average values over this specific benchmark suite. Power consumption of hosts also depends on RAM, Disk and bandwidth consumption characteristics and are provided to the model by the underlying CloudSim simulator. In the execution environment, we consider the host capacities (CPU, RAM, Network Bandwidth, etc) and the current usage to form the feature vector F V Hosts i for the i th scheduling interval. For the experiments, we keep the testing simulation duration of 1 day, which equals to total 288 scheduling intervals.

Evaluation Metrics
To evaluate the efficacy of the proposed A3C-R2N2 based scheduler, we consider the following metrics. Motivated from prior works [4], [16], [35], energy is paramount in resource constrained edge-cloud environments and realtime tasks require low response times. Moreover, service level agreements are crucial in time-critical tasks and low execution cost is required for budget task execution.: 1) Total Energy Consumption which is given as

Baseline Algorithms
We evaluate the performance of our proposed algorithms with the following baseline algorithms, the reasons for choosing these is described in Section 6. Multiple heuristics have been proposed by [8] for dynamic scheduling. These are a combination of different sub heuristics for different sub-problems such as host overload detection and task/VM selection and we have selected the best three heuristics from those. All of these variants use Best Fit Decreasing (BFD) heuristics to identify the target host. Furthermore, we also compare our results to two types of standard RL approaches that are widely used in the literature.  [16], [25], [26]. We implement the optimized Double DQN technique. • DRL (REINFORCE): policy gradient based REINFORCE method with fully connected neural network [28].
It is important to note that we implement these algorithms adapting to our problem and compare the results. The RL model that has been used for comparison with our proposed model uses a state representation same as the State i defined in Section 3.1 for fair comparison. An action is a change from one state to another in the state space. As in [24], the DQN network is updated using Bellman Equation [47] with the reward defined as −Loss P G i . The REINFORCE method is implemented without asynchronous updates or recurrent network.

Analysis of Results
In this subsection, we provide the experimental results using the experimental setup and the dataset described in Section 5.1. We also discuss and compare our results based on evaluation metrics specified in Section 5.2. We first analyze the sensitivity of hyper-parameters (α, β, γ, δ, ) on the model learning and how it affects different metrics. We then analyze the variation of scheduling decisions based on different hyper-parameter values and show how the combined optimization of different evaluation metrics provides better results. We also compare the fraction of scheduling time with total execution time by varying the number of layers on the R2N2 network. Based on the above analysis, we find the optimum R2N2 network and hyper-parameter values to compare with the baseline algorithms described in Section 5.3. All model learning is done for 10 days of simulation time and testing is done for 1 day of simulation time using a disjoint set of workloads of the dataset.

Sensitivity Analysis of Hyper-parameters
We first provide experimental results in Figure 9 for different hyper-parameter values and show how changing the loss function to learn only one of the metric of interest specifically, varies the learned network to give different values of the evaluation metrics, these experiments were carried for a single day of simulation duration. To visualize the output probability map from the R2N2 network, we display it using a color map to depict probabilities (0 to 1) of allocating tasks to hosts as described in Section 4.2. When α = 1 (rest = 0), then the R2N2 network solely tries to optimize the average energy consumption, and hence we call it Energy Minimizing Network (EMN). The total energy consumed across the simulation duration is least for this network as shown in Figure 9(a). As low energy devices (edge nodes) consume the least energy and also have least cost, energy is highly correlated to cost, and hence the Cost Minimizing Network (CMN, δ = 1) also has very low total energy consumption. As shown in Figure 10, for the same State i , the probability map and hence the allocation are similar for both networks. Similarly, we can also see that in Figure 9(d), CMN has the least cost and the next least cost is achieved by EMN.
The graph in Figure 9(b) shows that the Response Time Minimizing Network (RTMN, β = 1) has the least average response time and tries to place most of the tasks on edge nodes also shown in Figure 11(a). Moreover, this network does not differentiate among the edge nodes in terms of their CPU loads because all edge nodes have the same response time and hence gives almost same probability to every edge node for each task. The SLA Violation Minimizing Network (SLAVMN, = 1) also has a low response time as a number of SLA violations are directly related to response time for tasks. However, SLA violations also depend on the completion time of tasks, and as the average task completion time of RTMN is very high, the SLA violations of this network are much more than the other network as shown in Figure 9(c). The fraction of SLA violation is least for  (MMN, γ = 1). The SLAVMN network also sends tasks to edge nodes like RTMN, but it also considers task execution time and CPU loads to distribute tasks more evenly as shown in Figure 11(b). When only average migration time is being optimized, the average task completion time is minimum, as shown in Figure 9(e). However, the SLA violation is not minimum as this network does not try to minimize the response time of tasks, as shown in Figure 9(b). Moreover, the number of completed tasks is highest for this network as shown in Figure 9(f). Still, the fraction of tasks completed within the expected time is highest for SLAVMN. Figures 9(g) and 9(h) show that number of task migrations and migration time is least for MTMN. Also compared in Figure 12 the number of migrations for the sample size of 30 initial tasks are 7 for EMN and 0 for the other.
Optimizing each of the evaluation metrics independently shows that the R2N2 based network can adapt and update its parameters to learn the dependence among tasks and hosts to reduce metric of interest which may be energy, response time, etc. However, for the optimum network, we use a combination of all metrics. This combined optimization leads to a much lower value of the loss and a much better network. This is because optimizing only along one variable might reach a local optimum and the loss of hyper-parameter space being a highly non-linear function, combined optimization leads to much better network [48]. Based on the empirical evaluation for each combination and block coordinate descent [49] for minimizing Loss,

Sensitivity Analysis of the number of layers
Now that we have the optimum values of hyper-parameters, we analyze the scheduling overhead with the number of recurrent layers of the R2N2 network. The scheduling overhead is calculated as the ratio of time taken for scheduling to the total execution duration in terms of simulation time. As shown in Figure 13, the value of the loss function decreases with the increase in the number of layers of the Neural Network. This is expected because as the number of layers increase so do the number of parameters and thus the ability of the network to fit more complex functions becomes better. The scheduling overhead depends on the system on which the simulation is run, and for the current experiments, the system used had CPU -Intel i7-7700K and GPU -Nvidia GTX 1070 graphics card (8GB graphics RAM). As shown in the figure, there is an inflection point at 3 recurrent layers because the R2N2 network with 4 or more such layers could not fit in the GPU graphics RAM. Based on the available simulation infrastructure, for the comparison with baseline algorithms, we use the R2N2 network with 3 recurrent layers and hyper-parameter values given by Equation 14.

Scalability Analysis
We now show how the A3C-R2N2 model scales with the number of actor agent hosts in the setup. As discussed in Section 2, we have multiple edge-cloud nodes in the environment which run the policy learning as described in Section 4.3. However, the number of such agents affects the time to train the Actor-Critic network. We define the time taken by n agents to reduce the loss value to 2.5 as T ime n . Now, speedup corresponding to a system with n actors is calculated as S n = T ime1 T imen . Moreover, efficiency of a system with n agents is defined as E n = Sn n [50]. Figure 14 shows how speedup and efficiency of the model vary with number of agent nodes. As shown, the speedup increases with n, however, efficiency reduces as n increases in a piece-wise linear fashion. There is a sudden drop in efficiency when number of agents is increased from 1. This is because of the communication delay between agents which leads to slower model updates. The drop increases again after 20 hosts due to addition of GPU-less agents after 20 hosts. Thus, having agent run only on CPU significantly reduces the efficiency of the proposed architecture. For our experiments, we keep all active edge-cloud hosts (100 in our case) as actor agents in the A3C learning for faster convergence and worst-case overhead comparison. In such a case, the speedup is 34.3 and efficiency is 0.37.

Evaluation with Baseline Algorithms
Having the empirically best set of values of hyperparameters and the number of layers and discussed the scalability aspects of the model, we now compare our policy gradient based reinforcement learning model with the baseline algorithms described in Section 5.3. The graphs in Figure 16 provide results for 1 day of simulation time with a scheduling interval of 5 minutes on the Bitbrain dataset. Figure 16(a) shows that among the baseline algorithms, DDQN and REINFORCE have the least energy consumption, but A3C-R2N2 model has even lower energy consumption which is 14.4% and 15.8% lower than REINFORCE and DDQN respectively. The main reason behind this is that the A3C-R2N2 network is able to adapt to the task workload behavior quickly. This allows a resource hungry task to be scheduled to a powerful machine. Moreover, the presence of Average Energy Consumption (AEC) metric of all the edgecloud nodes within the loss function enforces the model  Figure 16(b) shows that among all the scheduling policies, A3C-R2N2 provides the least average response time which is 7.74% lower than the REINFORCE policy, best among the baseline algorithms. This is because the A3C-R2N2 model explicitly takes input about whether a node is a edge or cloud node and allocates tasks without multiple migrations and Average Migration Time (AMT) being embedded in the loss function. As shown in Figure 16(c), the A3C-R2N2 model has the least number of SLA violations which is 31.9% lower than the REINFORCE policy. This again is due to reduced migrations and intelligent scheduling of tasks to prevent the high loss value because of SLA violations. As shown in Figure 16(d), the total cost of the data center is least for the A3C-R2N2 model as it gets the cost model (Cost per hour consumption) for each host as a feature in F V Hosts i and can ensure that tasks can be allocated to as low number of cloud VMs as possible to reduce cost. Compared to the best baseline (REINFORCE), the A3C-R2N2 model reduces cost by 4.64%.
Furthermore, the A3C-R2N2 model also considers the tasks completion time in the previous scheduling interval and the expected completion time for running tasks. For time-critical tasks, the A3C-R2N2 model allocates it to a powerful host machine and avoid migration to save the migration time. This way, the A3C-R2N2 model can reduce the average completion time as shown in Figure 16(e) which is lower than REINFORCE by 17.53%. Also, as seen in Figure  16(f), the number of tasks completed and the fraction completed in expected time is highest for the A3C-R2N2 model. As a number of migration and migration time severely affect the quality of response of the tasks, Figure 16(g) and 16(h) show how A3C-R2N2 model can achieve the best metric values by having a low number of task migrations. To compare the scheduling overhead of the R2N2 model with the baseline algorithms, we provide a comparative result in Figure 15. As the R2N2 network needs to be updated every 1 hour of simulation time, the scheduling time is slightly higher than the other algorithms. Heuristicbased algorithms have very low scheduling overhead as they follow simple greedy approaches. R2N2 model has overhead higher by 0.002% from RL model. Even though the scheduling overhead is higher than the baseline algorithms, it is not significantly large. Considering the performance improvement by the R2N2 model, this overhead is negligible and makes the R2N2 model a better scheduler compared to the heuristics or traditional RL based techniques for Edge-Cloud environments with stochastic workloads.

Summary of insights
The R2N2 model works better than the baseline algorithms because it can sense and adapt to the dynamically changing environment, unlike the heuristic-based policies which use a representative technique for making scheduling decisions and are prone to jump to erroneous conclusions due to their limited adaptability. Compared to the DDQN approach, Heuristics [12] Heuristics [51] Gaussian Process Regression [24], [52] DQN [16] Q Learning [18] DNN [19], [25], [53] DDQN [28], [54] DRL (REINFORCE) This Work DRL (A3C-R2N2)  Figure 17 shows scheduling decisions classified as edge or cloud for different approaches with time for a sample task and response time minimization goal. For a task that has low resource requirement, it is better to schedule in low latency edge node rather than cloud. When task becomes resource intensive, only then is it optimal to send it to cloud as it may slow down the edge node. The REINFORCE-Dense model is unable to exploit temporal patterns like increasing resource utilization of a task with previous scheduling decisions to optimally decide the task allocation. This not only leads to higher frequency of sub-optimal decisions but also increases migration time. Considering these points, the A3C-R2N2 strategy can adapt to non-stationary targets and approximate and learn the parameters much faster and more precisely compared to the traditional RL based approaches as shown in Figure 18. Figure 18 also shows that the loss value for the RL framework is much lower when the A3C-R2N2 model compared to the REINFORCE-Dense model. The average loss value in last 1 hour in a full day experiment is 2.78 for REINFORCE-Dense and 1.12 (nearly 60% reduction in loss value) for the proposed model. To summarize, earlier works did not model temporal aspects using neural networks due to slower training of recurrent layers like GRU. However, modern advancements of residual connections and the proposed formulation allow faster propagation of gradients leading to a solution for the slow training problem.

RELATED WORK
Several studies [7], [8], [9], [10], [11], [12], [55] have proposed different types of heuristics for the scheduling applications in Edge-Cloud environment. Each of these studies focuses on optimizing different parameters for a specific set of applications. Some of the works are applied to Cloud systems, while others are for Edge-Cloud environments. It is well known that heuristics work for generic cases and fail to respond to the dynamic changes in environments. However, a learning-based model can adapt and improve over time by tuning its parameters according to new observations.
Predictive optimizations have been studied by [16], [17], [18], [19], [24], [25], [26], [52] in many of the recent works. These works use different ML (Machine Learning) and DL (Deep Learning) techniques to optimize the Resource Management System (RMS). Deep Neural Networks (DNN) and Deep Reinforcement Learning (DRL) approaches have been widely used in this regard. In most of these works, optimizing energy is a primary objective. Bui et al. [51] studied a predictive optimization framework for energy efficiency of cloud computing. They predict the resource utilization of the system in the next scheduling period by Gaussian process regression method. Based on this prediction, they choose a minimum number of servers to be active to reduce the energy consumption of the overall system. However, their approach still uses many heuristics in scheduling decisions and hence do not adapt to dynamic Edge-Cloud environments or changing workload characteristics. Zhang et al, [26] proposed a DDQN for energy-efficient edge computing. The proposed hybrid dynamic voltage frequency scaling (DVFS) scheduling based on Q-learning. As a deep Q-learning model cannot distinguish the continuous system states, in an extended work [19], they investigated a double deep Q-learning model to optimize the solution further. Xu et al. [18] proposed LASER, a DNN approach for speculative execution and replication of deadline critical jobs in the cloud. They implement these DNN based scheduling framework for the Hadoop framework. Basu et al. [16] investigated the live migration problem of Virtual Machines (VMs) using RL based Q-learning model. The proposed algorithms are aimed to improve over existing heuristicbased live migration. Live migration is widely used for consolidating the VMs to reduce energy consumption. Their proposed RL model Megh, continuously adapts and learns to the changes in the system to increase the energy efficiency. Cheng et al. [24] have studied Deep reinforcement learningbased resource provisioning and task scheduling approach for cloud service providers. Their Q-learning based model is optimized to reduce the electricity price and task rejection rate. Similarly, Mao et al. [25] and Li et al. [53] explored Resource Management with DDQN. They apply the DRL to scheduling jobs on multiple resources and analyze the reasons for achieving high gain compared to state-of-theart heuristics. As described before, these Q-learning based algorithms lack the ability to quickly adapt in stochastic environments. Mao et al. [28] and Rjoub et al. [54] also explored DRL (REINFORCE) based scheduling for edge only environments. They only consider response time as a metric and also do not exploit asynchronous or recurrent networks to optimize model adaptability and robustness.
A summary of the comparison of relevant works with our work over different parameters is shown in Table 3. We consider that the scheduler is dynamic if the optimization is carried dynamically for active tasks and new tasks that arrive in the system continuously. Stochastic workload is defined by changing tasks arrival rates and resource consumption characteristics. The definitions for remaining parameters are self explanatory. For the sake of brevity, instead of comparing to all the heuristics based work in the table, we compare our work to [8] and [12] which act as some of the baseline algorithm in our experiments. The existing RL based solutions use Q-learning models [16], [24], [25] and are focused on optimizing the specific parameters such as energy or cost, wherein we compare our approach with DDQN [53] and DRL (REINFORCE) [54]. All these baseline methods are adapted to be used in the proposed edge-cloud setup. However, in the Edge-Cloud environments, infrastructure is shared among the diverse set of users requiring different QoS for their respective applications. In such a case, the scheduling algorithm must be adaptive and be able to tune automatically to application requirements. Our proposed framework can be optimized to achieve better efficiency with respect to different QoS parameters as shown in Section 4 and Section 5. Moreover, Edge-Cloud environment brings heterogeneous complexity and stochastic behavior of workloads which need to be modeled within a scheduling problem. We model these parameters efficiently in our model.

CONCLUSIONS AND FUTURE WORK
Efficiently utilizing edge and cloud resources to provide a better QoS and response time in stochastic environments with dynamic workloads is a complex problem. This problem is complicated further due to the heterogeneity of multi-layer resources and difference in response times of devices in Edge-Cloud datacenters. Integrated usage of cloud and edge is a non-trivial problem as resources and network have completely different characteristics when users or edge-nodes are mobile. Prior work not only fails to consider these differences in edge and cloud devices but also ignores the effect of stochastic workloads and dynamic environments. This work aims to provide an endto-end real-time task scheduler for integrated edge and cloud computing environments. We propose a novel A3C-R2N2 based scheduler that can consider all important parameters of tasks and hosts to make scheduling decisions to provide better performance. Furthermore, A3C allows the scheduler to quickly adapt to dynamically changing environments using asynchronous updates, and R2N2 is able to quickly learn network weights also exploiting the temporal task/workload behaviours. Extensive simulation experiments using iFogSim and CloudSim on real-world Bitbrain dataset show that our approach can reduce energy consumption by 14.4%, response time by 7.74%, SLA violations by 31.9% and cost by 4.64%. Moreover, our model has a negligible scheduling overhead of 0.002% compared to the existing baseline which makes it a better alternative for dynamic task scheduling in stochastic environments.
As part of future work, we plan to implement this model in real edge-cloud environments. Implementation in real environments would require constant profiling CPU, RAM and disk requirements of new tasks. This can be done using exponential averaging of requirement values in the current scheduling interval with the average computed in the previous interval. Further, the CPU, RAM, disk and bandwidth usage would have to be collected and synchronized across all A3C agents in the edge-cloud setup. Further to the scalablity analysis, we also plan to conduct tests to check the scalability of the proposed framework with number of hosts and tasks. The current model can schedule for a fixed number of edge nodes and tasks. However, upcoming scalable reinforcement learning models like Impala [56] can be investigated in future. Moreover, we plan to investigate the data privacy and security aspects in future.

SOFTWARE AVAILABILITY
Our code, experiment scripts and raw result files are available online under GPL-3.0 License at: https://github.com/ Cloudslab/DLSF.