PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Reinforcement Learning-based Scheduling for Optimizing System Load and Response Time in Edge and Fog Computing Environments

Zhiyu Wang, Mohammad Goudarzi, Mingming Gong, Rajkumar Buyya

arXiv:2309.07407v2cs.DC

TL;DR

IoT application scheduling in heterogeneous edge and fog environments must handle overload, dependent tasks, changing conditions, and limited computational resources. The paper proposes DRLIS, a deep reinforcement learning scheduler implemented in FogBus2, and reports improvements over metaheuristic and reinforcement learning counterparts. The authors also identify extensions involving distributed learning, additional cost dimensions, and GPU-oriented scheduling.

  • Problem

    Dynamic and stochastic edge/fog environments require scheduling that balances server load and application response time despite dependent tasks and limited computational resources.

  • Method

    DRLIS uses deep reinforcement learning, including PPO-based policy optimization and a weighted cost model, to schedule IoT applications in heterogeneous fog environments.

  • Results

    DRLIS achieves performance improvements of up to 49%, 60%, and 55% in convergence speed, optimization cost, and scheduling overhead, respectively, compared with existing work.

  • Takeaways & Limitations

    DRLIS provides an implemented scheduler for heterogeneous edge and fog environments and is reported to improve convergence speed, optimization cost, and scheduling overhead.

  • Takeaways & Limitations

    Future work is needed to support distributed deep reinforcement learning, economic and energy costs, and GPU-task scheduling on ASIC/GPU-based servers.

Abstract

from arXiv · show

Edge/fog computing, as a distributed computing paradigm, satisfies the low-latency requirements of ever-increasing number of IoT applications and has become the mainstream computing paradigm behind IoT applications. However, because large number of IoT applications require execution on the edge/fog resources, the servers may be overloaded. Hence, it may disrupt the edge/fog servers and also negatively affect IoT applications' response time. Moreover, many IoT applications are composed of dependent components incurring extra constraints for their execution. Besides, edge/fog computing environments and IoT applications are inherently dynamic and stochastic. Thus, efficient and adaptive scheduling of IoT applications in heterogeneous edge/fog computing environments is of paramount importance. However, limited computational resources on edge/fog servers imposes an extra burden for applying optimal but computationally demanding techniques. To overcome these challenges, we propose a Deep Reinforcement Learning-based IoT application Scheduling algorithm, called DRLIS to adaptively and efficiently optimize the response time of heterogeneous IoT applications and balance the load of the edge/fog servers. We implemented DRLIS as a practical scheduler in the FogBus2 function-as-a-service framework for creating an edge-fog-cloud integrated serverless computing environment. Results obtained from extensive experiments show that DRLIS significantly reduces the execution cost of IoT applications by up to 55%, 37%, and 50% in terms of load balancing, response time, and weighted cost, respectively, compared with metaheuristic algorithms and other reinforcement learning techniques.

1. Introduction

IoT growth increases the need for low-latency processing, while heterogeneous and dynamic edge/fog environments make scheduling dependent applications difficult. The paper proposes DRLIS, a deep reinforcement learning scheduler designed to optimize weighted cost, response time, and server load balancing.

  • Motivation: Increasing IoT applications and servers make minimizing execution time and balancing server load important scheduling objectives.Distributing requests across servers can avoid overloading individual servers and improve response times and throughput.
  • Motivation: Dynamic server conditions, random resource requirements, and DAG-based task dependencies complicate scheduling in fog environments.Existing approaches may rely on global information or control over environmental changes, which are not consistently available.
  • Proposed approach: The paper proposes a weighted cost model for DAG-based applications that combines server load balancing with application response-time minimization.The model is adapted for use with deep reinforcement learning algorithms.
  • Proposed approach: DRLIS uses deep reinforcement learning to solve a weighted cost optimization problem in dynamic and stochastic fog computing environments.The algorithm adaptively updates its scheduling policy when application requests, server resources, or server counts change.
  • Implementation and evaluation: DRLIS is implemented as a practical scheduler in the FogBus2 function-as-a-service framework for heterogeneous edge and fog environments.The framework is extended to support DRL techniques and scheduling requests from different IoT applications.
  • Implementation and evaluation: Experiments with real IoT applications compare DRLIS with NSGA2, NSGA3, and Q-Learning using convergence speed, optimization cost, and scheduling time.The evaluation uses heterogeneous tasks and resource demands in a real system setup.

2. Related Work

The related work is organized around metaheuristic and reinforcement learning approaches for scheduling IoT applications in edge and fog environments. Prior studies address latency, load balancing, or resource allocation, but the comparison considers broader application, architecture, algorithm, and evaluation properties.

  • Review structure: The review divides prior scheduling studies into metaheuristic and reinforcement learning categories.
  • Reinforcement learning approaches: Prior dependent-task studies use MDP, Q-learning, or DQN approaches to reduce latency, balance load, or minimize job completion time.Their stated settings and objectives differ across edge, fog-cloud, and heterogeneous IoT environments.
  • Reinforcement learning approaches: The reviewed approaches have limitations including weak adaptation to changing environments, omission of task dependencies, restricted edge-only settings, or single-objective optimization.
  • Comparison framework: Table 1 compares related work with the proposed algorithm across application, architecture, algorithm, and evaluation properties.The comparison includes task dependencies, computing layers, server heterogeneity, optimization objectives, and evaluation characteristics.

3. System Model and Problem Formulation

The section models dependent IoT applications as DAGs scheduled across heterogeneous servers, then formulates load balancing, response time, and weighted cost objectives under resource and dependency constraints. The resulting optimization seeks balanced server utilization and reduced processing time but is non-convex and NP-hard.

  • 3.1. System Model: IoT applications are represented as DAGs whose vertices are tasks, edges encode data flow, and critical paths identify highest-cost execution paths.Tasks may execute sequentially or in parallel according to parent-child dependencies.
  • 3.1. System Model: The heterogeneous server model includes CPU and RAM capacities plus inter-server transmission time, propagation time, packet size, and bandwidth.These properties characterize both computation and communication costs during scheduling.
  • 3.2. Problem Formulation: Each task is assigned a server, application configurations aggregate task assignments, and the full configuration aggregates assignments across applications.The formulation permits different tasks within an application to run on different servers.
  • 3.2.1. Load Balancing Model: The load balancing model measures CPU and RAM resource variance across servers and minimizes overall utilization variance during application processing.Control parameters tune the weighted contributions of CPU and RAM balancing.
  • 3.2.2. Response Time Model: The response time model combines task data-arrival and server-processing times, weighting tasks on an application’s critical path.Transmission time depends on packet size and bandwidth, while processing time depends on required CPU cycles and server frequency.
  • 3.2.2. Response Time Model: The response time objective minimizes total processing time for the server set by selecting an appropriate application scheduling configuration.The model explicitly accounts for the time required for assigned servers to process tasks.
  • 3.2.3. Weighted Cost Model: The weighted cost model is a tunable weighted sum of normalized load balancing and response time models.Normalization addresses different value ranges, while control parameters determine the two objectives’ contributions.
  • 3.2.3. Weighted Cost Model: The optimization enforces single-server assignment, valid utilization and hardware capacities, sufficient RAM, dependency ordering, and valid control parameters.Because the formulation is non-convex and NP-hard, iterative convex decomposition may reduce complexity at the expense of accuracy.

4. Deep Reinforcement Learning Model

The paper models scheduling as a Markov Decision Process in which an agent assigns tasks to servers and learns policies from state transitions and rewards. The state captures task and server conditions, while rewards encode penalties and improvements in load balancing, response time, and weighted cost.

  • MDP Formulation: The reinforcement-learning problem is represented as an MDP with states, actions, transition probabilities, rewards, and a discount factor.The agent learns a policy that maximizes expected cumulative discounted reward.
  • State Space: The state combines features of the current task with the current server set, including application, dependency, utilization, capacity, propagation, and bandwidth information.This representation reflects both task characteristics and heterogeneous server conditions.
  • Action Space: At each time step, the action assigns the currently processed task to a server in the scheduling configuration.The action space is defined to minimize the weighted-cost objective.
  • Reward Function: The reward function applies a large negative penalty when a task cannot be processed on its assigned server.Feasibility violations therefore receive an explicit penalty.
  • Reward Function: Load-balancing rewards are positive when scheduling reduces the server-set load-balancing model, while response-time rewards are positive when current response time is below the average.The weighted-cost reward combines normalized objectives using control parameters.
  • Deep Reinforcement Learning: PPO is identified as a deep reinforcement-learning method that improves convergence and sampling efficiency through importance sampling and proportional clipping.The paper also situates PPO alongside TD3 and SAC as advanced reinforcement-learning algorithms.

5. DRL-based Optimization Algorithm

DRLIS applies PPO-based actor-critic reinforcement learning to optimize weighted scheduling cost in dynamic edge and fog environments. Its clipped policy updates, reward design, and iterative network training support adaptive scheduling while limiting update deviation and computational complexity.

  • DRLIS overview: DRLIS uses PPO to optimize the weighted cost of IoT application scheduling in edge and fog computing environments.The optimization targets server load balancing, application response time, and their weighted cost.
  • PPO preliminaries: Policy-gradient learning adjusts policy parameters to maximize expected cumulative discounted rewards using sampled state-action trajectories and advantage estimates.The policy gradient uses the expected product of the log-policy gradient and the advantage function.
  • PPO preliminaries: PPO constrains policy changes by clipping the new-to-old action-probability ratio, avoiding the KL penalty used in KL-PPO.The clipping range restricts the ratio to (1 − ϵ, 1 + ϵ), while PPO reduces computational complexity relative to constrained optimization approaches.
  • DRLIS architecture: DRLIS uses an actor-critic architecture in which the actor learns the policy and the critic evaluates it to guide subsequent actions.The actor and critic are implemented as deep neural networks, with the critic using temporal-difference learning.
  • DRLIS operation: The scheduler collects T-step state-action-reward tuples, estimates advantages, optimizes the networks K times, and copies the updated actor to the old actor.DRLIS maintains one critic and two actor networks representing the old and new policies; its stated complexity begins with O(N + …).

6. Performance Evaluation

The evaluation first describes the experimental setup and applications, then tunes DRLIS hyperparameters and compares its performance with counterpart schedulers.

  • Evaluation plan: The evaluation covers experimental setup, sample applications, hyperparameter investigation, and comparisons with counterpart schedulers.These stages are presented in that order.

6.1. Experiment Setup

The study evaluates a DRLIS-based FogBus2 scheduler in a heterogeneous environment containing IoT devices, resource-limited fog servers, and resource-rich cloud servers. Four sensor-actuator IoT applications and three classes of comparison schedulers are included.

  • Environment: The evaluation uses a heterogeneous environment of IoT devices, resource-limited fog servers, and resource-rich cloud servers.Two Nectar Cloud instances provide 2-core/9GB and 16-core/64GB configurations.
  • Applications: Four applications provide real-time and non-real-time video workloads using sensor-actuator architectures and single data streams.The applications are Face Detection, Color Tracking, Face And Eye Detection, and Video OCR.
  • Baselines: The comparison set includes DQN and Q-Learning reinforcement-learning schedulers alongside NSGA2 and NSGA3 metaheuristic schedulers.The alternative schedulers are integrated or implemented for the weighted load-balancing and response-time cost problem.

6.2. Hyperparameter Tuning

DRLIS is implemented with compact actor and critic networks suited to resource-limited fog devices. Hyperparameter tuning addresses the weighted cost problem and identifies a clipping range of 0.3 as the best tested setting.

  • Implementation: DRLIS uses three-layer actor and critic networks consisting of input, hidden, and output layers.The compact design considers limited computational resources in fog environments.
  • Clipping range: 0.3 is the clipping range ϵ at which the model performs best in the reported tuning experiment.The tested candidate clipping ranges are 0.1, 0.2, and 0.3.
  • Selected settings: Table 3 reports the hyperparameter settings selected for DRLIS.The table is part of the tuning analysis for the weighted cost problem.

6.3. Performance Study

DRLIS is evaluated against reinforcement-learning and metaheuristic schedulers across load balancing, response time, weighted cost, convergence, and scheduling overhead. It achieves lower costs and faster convergence than the compared techniques, while maintaining lower scheduling overhead than metaheuristics.

  • Experimental setup: The experiments compare schedulers on server load balancing, IoT application response time, weighted cost, and scheduling overhead.The evaluation uses four IoT applications and examines training and evaluation behavior, plus repeated overhead measurements.
  • Cost vs policy update analysis: DRLIS converges to a stable load-balancing state in about 20 policy updates, versus more than 60 for Q-Learning and more than 80 for DQN.NSGA2 and NSGA3 do not reach a convergence state for load balancing.
  • Cost vs policy update analysis: DRLIS achieves lower average cost and faster convergence than the compared schedulers across load balancing, response time, and weighted cost objectives.In training, reinforcement-learning schedulers generally outperform NSGA2 and NSGA3 on cost, while DRLIS provides the fastest convergence among the reinforcement-learning methods.
  • Cost vs policy update analysis: 55%, 37%, and 50% average performance improvements are reported for server load balancing, IoT application response time, and weighted cost, respectively, versus Q-Learning.In the weighted-cost evaluation, DRLIS converges after about 30 updates, compared with about 60 for Q-Learning and more than 80 for DQN.
  • Scheduling overhead analysis: DRLIS scheduling overhead is more than 50% lower than NSGA2 and NSGA3 and more than 33% lower than DQN, but about 2 ms higher than Q-Learning.The reported 95% confidence intervals for reinforcement-learning techniques are also shorter than those for metaheuristics.
  • Overall findings: DRLIS handles weighted-cost optimization more efficiently than other techniques in heterogeneous edge and fog computing environments.This conclusion follows the reported improvements in optimization cost, convergence behavior, and scheduling overhead.

7. Conclusions and Future Work

The paper proposes DRLIS for weighted-cost IoT application scheduling in heterogeneous edge and fog environments and implements it in FogBus2. Experiments report improvements in load balancing, response time, and weighted cost, while future work targets distributed learning and broader resource models.

  • Conclusions: DRLIS solves weighted-cost IoT application scheduling in heterogeneous edge and fog computing environments.The approach includes cost models for load balancing and response time and a weighted model combining them.
  • Conclusions: DRLIS is implemented as a practical IoT application scheduler in the FogBus2 function-as-a-service framework.The framework supports the paper’s edge and fog scheduling evaluation.
  • Conclusions: 49%, 60%, and 55% performance improvements are reported for load balancing, response time, and weighted cost, respectively, compared with existing work.The reported improvements come from extensive experiments and comparisons with other works in the literature.
  • Future work: Future work will explore distributed deep reinforcement learning and extend the weighted cost model to economic and energy-consumption aspects.The authors also plan to support GPU-task scheduling on ASIC- and GPU-based edge and cloud servers.
Loading 2309.07407v2…