Technical Summary: DEFT Scheduling of Dynamic Cloud Workflows

Problem Definition

The paper addresses the Cost-Aware Dynamic Workflow Scheduling (CADWS) problem in cloud computing environments. In this setting, workflows arrive dynamically and are modeled as Directed Acyclic Graphs (DAGs) where nodes represent computational tasks and edges represent precedence constraints. Each workflow is associated with a Service-Level Agreement (SLA) deadline.

The core challenge lies in the dynamic nature of the environment:

1. Dynamic Arrivals: Workflows arrive unpredictably with varying structures and sizes.
2. Varying Deadlines: Deadlines exhibit a wide spectrum of tightness, ranging from lenient to extremely urgent.
3. Resource Fluctuation: Virtual Machine (VM) availability and costs change over time.

The objective is to minimize the total execution cost, which is a composite of:

• VM Rental Fees: Costs incurred for leasing VMs on a pay-as-you-go basis.
• SLA Penalties: Financial penalties incurred when a workflow fails to meet its deadline.

Existing Deep Reinforcement Learning (DRL) approaches for CADWS typically employ monolithic policy networks (single feedforward pathways). The authors argue that these rigid architectures struggle to adapt to the diverse scheduling scenarios imposed by varying deadline tightness, as a single set of decision rules cannot optimally handle both relaxed and urgent deadlines simultaneously.

Methodology: DEFT

The authors propose DEFT (Deadline-pErceptive Mixture-oF-TExperts), a novel DRL policy architecture designed to overcome the limitations of rigid inference pathways.

1. Mixture-of-Experts (MoE) Architecture

Instead of a single policy network, DEFT utilizes a pool of specialized sub-networks (experts).

• Specialization: Each expert is trained to handle a specific level of deadline tightness (controlled by a deadline relaxation coefficient $\gamma$). For instance, one expert may specialize in aggressive, cost-insensitive scheduling for tight deadlines, while another focuses on cost-efficient, delay-tolerant strategies for relaxed deadlines.
• Two-Phase Training:
  • Phase 1 (Expert Pre-training): Experts are independently pre-trained on workflows with fixed, specific $\gamma$ values to learn distinct scheduling behaviors.
  • Phase 2 (Joint Fine-tuning): All experts are loaded into the full architecture and jointly fine-tuned alongside a gating network and the State Embedding Module (SEM). This phase allows the system to adapt to mixed-deadline distributions.

2. Graph-Adaptive Gating Network

A critical innovation in DEFT is the Graph-Adaptive Gating Network, which dynamically routes decisions to the most appropriate expert at each time step.

• Input Context: The gating network integrates four key components:
  1. Global workflow embeddings (DAG structure).
  2. Features of the current ready task and its topological context.
  3. System-level features (VM availability and states).
  4. Normalized deadline tightness scores.
• Cross-Attention Mechanism: Unlike traditional MoE gating that uses simple linear layers, DEFT employs a cross-attention mechanism. The workflow DAG embedding and task states form the Query (Q), while the expert representations serve as Keys (K) and Values (V). This allows the gate to perform fine-grained, deadline-sensitive expert selection based on the complex structural dependencies of the workflow.
• Routing Strategy: The system uses Top-1 routing, selecting the single most suitable expert for each decision step. Ablation studies in the paper suggest that Top-1 routing outperforms Top-k routing in this discrete action space, as it avoids "blending" conflicting expert recommendations which can lead to suboptimal VM selections.

3. Optimization

The policy is optimized using OpenAI Evolution Strategies (ES), a population-based optimization technique chosen for its robustness in dynamic environments and suitability for parallel implementation.

Key Contributions

The paper claims three primary contributions:

1. First MoE Application in Dynamic Workflow Scheduling: DEFT is presented as the first approach to introduce Mixture-of-Experts architectures specifically for dynamic cloud workflow scheduling, introducing a new level of adaptivity in deadline-aware policy design.
2. Enhanced Policy Diversity and Generalization: By employing a two-phase training strategy (specialized pre-training followed by joint fine-tuning), DEFT achieves superior generalization across varying deadline regimes and workflow scales (Small, Medium, Large) compared to monolithic DRL baselines.
3. Graph-Adaptive Gating: The authors introduce a novel gating mechanism that combines Graph Neural Network (GNN) representations with MoE routing. This is the first design to integrate structured workflow DAGs with MoE routing in a DRL scheduler, enabling precise, deadline-driven expert activation.

Experimental Results

The authors evaluated DEFT against five baselines: two heuristic methods (ProLis, GRP-HEFT) and three state-of-the-art DRL methods (ES-RL, SPN-CWS, GATES).

• Total Cost Reduction: DEFT consistently achieved the lowest total cost across all workflow scales (S, M, L).
  • On Large-scale workflows, DEFT reduced costs by 29.6% compared to the best DRL baseline (GATES).
  • Heuristic methods performed significantly worse, with costs 3 to 10 times higher than DRL approaches.
• Scalability: While other DRL methods (like ES-RL) degraded sharply as workflow size increased, DEFT demonstrated strong scalability, with cost increases being much slower as deadlines tightened and workflows grew.
• Balance of Costs: DEFT effectively balanced the trade-off between VM rental fees and SLA penalties. In scenarios with tight deadlines, it prioritized avoiding penalties; in relaxed scenarios, it minimized VM costs, adapting its strategy dynamically.
• Ablation Studies:
  • Gating Mechanism: The graph-adaptive gating significantly outperformed linear and standard MLP gating mechanisms.
  • MoE vs. Capacity: Replacing the fixed PMM with MoE yielded better results than simply deepening the MLP in the baseline, confirming that the gain comes from specialized policy selection rather than just increased model capacity.
  • Routing: Top-1 routing was found to be superior to Top-k routing for this specific problem, preventing the averaging of conflicting expert decisions.

Significance and Claims

The paper positions DEFT as a significant advancement in the field of cloud workflow scheduling. The authors claim that:

• Rigid architectures are insufficient: Single-path DRL policies cannot effectively handle the wide spectrum of deadline tightness found in real-world cloud environments.
• Adaptivity is key: By dynamically selecting specialized experts based on real-time workflow structure and deadline urgency, DEFT achieves a level of flexibility and precision that static policies cannot match.
• Practical Impact: The method offers a principled approach to structured, deadline-driven scheduling that significantly reduces execution costs and deadline violations, making it suitable for complex, dynamic cloud environments.

The authors conclude that DEFT represents a shift from static, one-size-fits-all scheduling policies to adaptive, context-aware systems capable of reasoning over diverse and evolving constraints. Future work is suggested to extend this approach to multi-tenant environments and explore explainability in expert routing.