A Distributed Deep Reinforcement Learning Technique for Application Placement in Edge and Fog Computing Environments

Mohammad Goudarzi; Marimuthu Palaniswami; Rajkumar Buyya

Source-linked AI summary

A Distributed Deep Reinforcement Learning Technique for Application Placement in Edge and Fog Computing Environments

Mohammad Goudarzi, Marimuthu Palaniswami, Rajkumar Buyya

arXiv:2110.12415v1Oct 24, 2021cs.DCcs.LG

TL;DR

DAG-based IoT placement in heterogeneous fog environments is difficult because task dependencies, stochastic resources, and costly DRL exploration complicate decision-making. The paper proposes X-DDRL, a distributed IMPALA-based placement technique with pre-scheduling, recurrent processing, and replay. Across simulation and testbed experiments, X-DDRL is reported to perform 8 to 16 times faster than other DRL-based techniques.

Problem
DAG dependencies and heterogeneous fog resources make application placement computationally complex, while DRL training requires costly exploration data.
Method
X-DDRL uses distributed IMPALA actors and learners, pre-schedules dependent tasks, and applies a weighted execution-time and energy-cost model.
Results
8 to 16 times faster than other DRL-based techniques in the reported simulation and testbed comparisons.
Takeaways & Limitations
Distributed experience sharing enables X-DDRL to rapidly converge well-suited placement solutions in heterogeneous fog environments with many servers and users.
Takeaways & Limitations
The current weighted cost model does not yet include monetary cost, dynamic transmission-power changes, or total system cost, and mobility models remain future work.

Abstract

from arXiv · show

Fog/Edge computing is a novel computing paradigm supporting resource-constrained Internet of Things (IoT) devices by the placement of their tasks on the edge and/or cloud servers. Recently, several Deep Reinforcement Learning (DRL)-based placement techniques have been proposed in fog/edge computing environments, which are only suitable for centralized setups. The training of well-performed DRL agents requires manifold training data while obtaining training data is costly. Hence, these centralized DRL-based techniques lack generalizability and quick adaptability, thus failing to efficiently tackle application placement problems. Moreover, many IoT applications are modeled as Directed Acyclic Graphs (DAGs) with diverse topologies. Satisfying dependencies of DAG-based IoT applications incur additional constraints and increase the complexity of placement problems. To overcome these challenges, we propose an actor-critic-based distributed application placement technique, working based on the IMPortance weighted Actor-Learner Architectures (IMPALA). IMPALA is known for efficient distributed experience trajectory generation that significantly reduces the exploration costs of agents. Besides, it uses an adaptive off-policy correction method for faster convergence to optimal solutions. Our technique uses recurrent layers to capture temporal behaviors of input data and a replay buffer to improve the sample efficiency. The performance results, obtained from simulation and testbed experiments, demonstrate that our technique significantly improves the execution cost of IoT applications up to 30\% compared to its counterparts.

1 INTRODUCTION

The paper targets DAG-based IoT application placement in heterogeneous fog environments, where dependency constraints, stochastic resources, and costly DRL exploration complicate efficient decisions. It proposes X-DDRL, a distributed IMPALA-based technique combining shared experience, recurrent processing, replay, pre-scheduling, and a weighted execution-cost model.

1 INTRODUCTION: DAG-based IoT placement must minimize execution time and energy while satisfying dependencies among tasks.DAG nodes represent tasks and edges represent communication among dependent tasks, increasing placement complexity.
1 INTRODUCTION: DRL agents require large and diverse experience trajectories in complex fog environments, making exploration costly.The paper motivates distributed experience generation as a response to the training burden of centralized DRL techniques.
1 INTRODUCTION: X-DDRL distributes environment interaction across actors and learners using IMPALA, reducing exploration costs and reusing experience trajectories.Actors generate trajectories in parallel, while the learner updates the policy and corrects the actor–learner policy gap.
1 INTRODUCTION: The approach combines pre-scheduling for dependent tasks with a weighted cost model adapted for DRL-based placement.The weighted model targets both execution time and IoT-device energy consumption.
1 INTRODUCTION: The technique uses recurrent layers and an experience replay buffer to capture input dynamics and improve sampling efficiency.The replay buffer also helps break strong correlations between experience trajectories.
1 INTRODUCTION: Evaluation uses simulation and testbed experiments across synthetic DAGs derived from real IoT applications, comparing X-DDRL with Double-DQN, PPO, and a greedy heuristic.The experiments vary application dependencies, task counts, and execution costs.

2 RELATED WORK

Prior work includes DRL placement methods for edge and fog settings, with different dependency models, resource heterogeneity, and learning architectures. The paper positions X-DDRL as a distributed IMPALA-based response to the greater feature complexity and exploration costs of heterogeneous fog environments.

2 RELATED WORK: Fog-based placement studies face higher resource heterogeneity than edge-only studies because they combine edge and remote cloud resources.This increases the number of environmental features that DRL-based placement methods must identify.
2 RELATED WORK: Existing studies use varied learning designs, including DQN, Double-DQN with replay, PPO, A3C, and RNN-based scheduling.These works target objectives such as service delay, system cost, execution time, or energy consumption.
2 RELATED WORK: Related DRL methods cover independent and dependent IoT applications, but some dependent-task approaches restrict execution to sequential dependencies.One cited method considers dependencies while excluding parallel task execution.
2 RELATED WORK: The comparison framework organizes prior methods by application dependency, task properties, architectural features, and placement-engine decision parameters.Table 1 provides the qualitative comparison across these categories.
2 RELATED WORK: X-DDRL addresses feature-rich heterogeneous environments by generating experience trajectories through multiple distributed actors and forwarding them to a learner.The paper states that this significantly reduces exploration and training costs relative to centralized DRL techniques.

3 SYSTEM MODEL AND PROBLEM FORMULATION

The system models DAG-based IoT applications and places their dependent tasks across IoT devices, fog servers, and cloud servers. It formulates execution time, device energy, and weighted placement cost models while enforcing dependency, resource, and assignment constraints.

3.2 Problem Formulation: Tasks are assigned locally or to heterogeneous fog and cloud servers, with each application placement represented by the assignments of all its tasks.The broker uses each application's DAG, constraints, and system status to make placement decisions.
3.2 Problem Formulation: DAG dependencies are respected by scheduling every parent before its children, while CP(v_i) identifies tasks on the application's highest-cost critical path.Critical-path tasks determine which parallel execution times contribute to the modeled application execution time.
3.2.1 Execution time model: Execution time combines input-data availability, required CPU cycles, assigned-server processing speed, and inter-server bandwidth and latency.Communication is included when dependent tasks are assigned to different servers, and these parameters vary across heterogeneous, stochastic environments.
3.2.1 Execution time model: The execution-time model seeks a placement that minimizes application execution time, focusing on the critical path because parallel tasks can overlap.CP(v_j) is one for critical-path tasks and zero otherwise.
3.2.2 Energy consumption model: The energy model minimizes IoT-device consumption by combining task-processing energy, idle energy for remotely executed tasks, and communication energy across DAG edges.Only IoT-device energy is counted because fog and cloud servers are assumed to use constant power supplies; transmission energy applies when an edge connects local and nonlocal execution.
3.2.3 Weighted cost model: A weighted cost combines execution time and IoT-device energy, with w_1 and w_2 controlling their relative importance.Setting w_1=1,w_2=0 yields execution-time cost, while w_1=0,w_2=1 yields energy cost; the model can be extended with other decision parameters.
3.2.3 Weighted cost model: The placement problem is NP-hard, and its complexity grows exponentially with the number of heterogeneous servers or application tasks.This motivates the use of heuristic, rule-based, approximation, and learning-based approaches rather than polynomial-time iterative optimization.

4 DEEP REINFORCEMENT LEARNING MODEL

The paper models fog application placement as a DRL problem in which states describe heterogeneous servers and the current DAG task, actions assign servers, and rewards minimize weighted execution cost.

DRL models placement as a Markov Decision Process with state, action, transition, reward, and discount components.
The state combines heterogeneous-server features with information about the current DAG task and prior placement configuration.Server features include processing, capacity, utilization, bandwidth, and latency; task information includes requirements and dependency-related placement context.
Actions assign the current task to an available server, including fog or other execution resources represented in the environment.
The reward is the negative weighted task cost for feasible execution and a large penalty when the selected assignment cannot be performed.

5 DISTRIBUTED DRL-BASED FRAMEWORK

X-DDRL combines actor-critic learning with distributed actors, V-trace correction, replay, and recurrent layers to place dependency-constrained DAG tasks while sharing experience across brokers.

X-DDRL uses an actor-critic framework to combine policy-based and value-based learning for DAG placement in heterogeneous fog environments.
X-DDRL: Application Placement Phase: Distributed brokers generate experience trajectories while a learner updates the shared policy and distributes it back to brokers.The state includes server features and the current ordered task; brokers then assign that task to a server and receive rewards.
X-DDRL: Pre-scheduling Phase: The pre-scheduling phase ranks DAG tasks, satisfying dependencies and prioritizing parallel tasks with higher total execution costs.
V-trace corrects the mismatch between broker behavior policies and the learner policy during distributed training.
Experience sharing, replay buffering, and recurrent layers reduce exploration or communication costs, improve sample efficiency, and support scaling across brokers.
The framework addresses resource contention when multiple heterogeneous applications compete for limited heterogeneous servers.

6 PERFORMANCE EVALUATION

The performance-evaluation section introduces the evaluation organization, covering experimental setup, hyperparameters, and detailed comparisons with baseline techniques.

The evaluation describes the experimental setup, X-DDRL hyperparameters, and performance comparisons against counterpart methods.

6.1 Experimental Setup

X-DDRL is evaluated in simulation and on a heterogeneous testbed using synthetic DAG workloads and several heuristic and DRL baselines.

The study evaluates X-DDRL in both an OpenAI Gym-based event-driven simulation and a real-world testbed.
Synthetic DAG datasets vary task count, width, height, density, dependency models, and randomly selected task weights.
The testbed includes Raspberry Pi, Jetson Nano, Horizon Cloud, and Nectar Cloud servers, with single-core virtual machines representing IoT devices.
Evaluation compares X-DDRL with PPO-RNN, PPO-No-RNN, Double-DQN, and a greedy heuristic.

6.2 X-DDRL Hyperparameters

X-DDRL uses a recurrent neural architecture with two fully connected layers followed by two LSTM layers, with hyperparameters selected through grid search.

X-DDRL agents use two fully connected layers followed by two LSTM recurrent layers.The recurrent layers are part of the standard IMPALA implementation used by X-DDRL.
Grid-search tuning sets the learning rate lr to 0.01 and discount factor γ to 0.99.
The V-trace control parameters ρ and c are both set to 1 based on tuning experiments.

6.3 Performance Study

Across simulation and testbed experiments, X-DDRL converges faster and achieves better placement outcomes than competing techniques across execution cost, scalability, and speedup evaluations.

Execution cost vs policy update analysis: X-DDRL outperforms other techniques in execution time, energy consumption, and weighted cost while converging faster across both policy-update scenarios.The second scenario evaluates generalization from training on L ∈{10, 15, 25, 30} to datasets with L = 20.
System size analysis: With 24 or 48 candidate servers, X-DDRL consistently outperforms other techniques and converges faster, indicating better scalability as system size grows.Weighted execution costs increase when the system expands from 24 to 48 servers, while DRL methods improve with more iterations.
Speedup and placement time overhead analysis: X-DDRL’s placement-time overhead is less than 1% higher than other DRL techniques in the worst case, while its speedup is 8 to 16 times greater.RNN-based methods generally have higher placement-time overhead than non-RNN methods.

7 CONCLUSIONS AND FUTURE WORK

The paper concludes that X-DDRL combines weighted-cost optimization, DAG-aware pre-scheduling, and distributed IMPALA-based placement for heterogeneous fog environments. Across simulation and testbed experiments, it converges faster and improves execution time, energy consumption, and weighted cost, while future work expands the cost model and mobility support.

7 CONCLUSIONS AND FUTURE WORK: The technique combines a weighted cost model, DAG-based dependent-task pre-scheduling, and IMPALA-based distributed brokers for application placement.Pre-scheduling prioritizes dependent tasks using the DAG dependency model and estimated execution cost.
7 CONCLUSIONS AND FUTURE WORK: X-DDRL achieves up to 30%, 11%, and 24% performance gains in execution time, energy consumption, and weighted cost, respectively, over other DRL techniques.It also performs 8 to 16 times faster than other DRL-based techniques.
7 CONCLUSIONS AND FUTURE WORK: X-DDRL rapidly converges to well-suited solutions in heterogeneous fog environments with many servers and users.The evaluation includes extensive simulation and testbed experiments against state-of-the-art techniques.
7 CONCLUSIONS AND FUTURE WORK: Future work will extend the cost model to monetary cost, dynamic transmission power, and total system cost, and incorporate mobility models.The placement technique will be adapted accordingly for mobile scenarios.