Cloud Scheduling Algorithms

Cloud and Virtualization: Scheduling Algorithms

• Scheduling algorithms in cloud and fog computing are explored
• Material sourced from a talk by Mudit Verma & Radovan Zvonček, with supervision from Luis Veiga

Motivation

• The goal is to minimize the time it takes to reach a classroom using different modes of transport, considering waiting times
  • Bus (15 minutes + waiting time)
  • Tuk-tuk (30 minutes)

A Similar Problem

• Addresses scheduling for three machines with specific CPU and memory requirements
• Involves tasks waiting in a queue and execution time, with the aim of a relaxed execution time

Quick Review: Cloud Definition

• A cloud is an interconnected and virtualized computer collection
• Resources presented as unified computing resources
• Based on Service Level Agreements (SLAs) negotiated between providers and consumers

Cloud Service Models

• Software as a Service (SaaS) is shown via providers and applications like SalesForce CRM and Google App
• Platform as a Service (PaaS) allows deploying customer-created applications
• Infrastructure as a Service (IaaS) involves renting processing, storage, network capacity, and computing resources, exemplified by Amazon Web Services and Rackspace

Areas for Improvement in Clouds

• Resource management needs enhancement
• Task scheduling optimization is required

Cloud and Fog Computing

• Data centers/clouds are connected to the edge via LAN/WAN
• The edge consists of sensors and controllers

Introduction to Scheduling

• Scheduling is central to distributed computing
• PaaS model: Workflow (job) scheduling
• IaaS model: Virtual Machines (VM) scheduling
• Schedulers decide which job/VM runs on which machine
• Effective schedulers reduce operational costs
• They reduce queue waiting time
• They increase resource utilization

Scheduling Definition

• It is a mapping mechanism from user tasks to resource selection and execution
• It's considered a challenging issue
• The goal is to spread load, maximize processor use, and minimize execution time
• Involves ordering jobs under transaction constraints
• Emphasis on high throughput and minimal execution time

Scheduling Goals

• Manage cloud computing performance and QoS
• Manage memory and CPU resources
• Maximize resource use while minimizing task execution time
• Improve fairness across all tasks
• Increase the number of successfully completed tasks
• Schedule tasks on real-time systems
• High system throughput is critical
• Improve load balance

Different Types of Task Scheduling

• Immediate Scheduling: Tasks scheduled directly to VMs upon arrival
• Batch Scheduling: Tasks grouped before dispatch, also known as mapping events
• Static Scheduling: Relies on prior global system state, divides traffic evenly
• Dynamic Scheduling:Considers current VM states, allocates tasks based on capacity
• Preemptive Scheduling: Tasks can be interrupted and moved during execution
• Non-preemptive Scheduling: VMs aren't reassigned until the current task finishes

Static Task Scheduling Algorithms

• First Come First Serve
• Prioritized Scheduling

Workflow Scheduling

• Jobs are arranged as workflows, typically defined as Directed Acyclic Graphs (DAG)
• DAG nodes represent tasks
• Edges represent flow
• Job completion time depends on DAG design and parallelism scope
• There is a wait time in the queue
• No prior knowledge of resource availability

VM Scheduling

• Simple with a single priority
• There is no guarantee of optimized resource utilization
• Dynamic VM scheduling and migration are used
• Hypervisor is not considered into the loop

Job Scheduling

• It is illustrated with a 10x10 Job Shop Scheduling Problem

Utility Driven Scheduling

• Goals: optimized resource utilization and relaxed QoS in overcommitted scenarios
• Approach: partial utility function and continuous resource monitoring & feedback

Partial Utility Function Example

• Includes job details, user, priority, CPU, memory, disk usage and relaxation values for different tasks

Utility Scheduler

• Utilizes a monitor and scheduler
• Considers CPU, memory, disk resources across a cluster of nodes (N1-N7)

Test Bed Setup

• Utilizes a Condor Cluster with 13 machines (52 cores) and 8 GB Physical Memory/machine
• A scheduler experiment setup uses 4 machines (16 cores) with 8 GB Physical Memory/machine

Result 1

• Aims to demonstrate a gain of 33% in CPU utilization/core
• Able to run roughly 1.5 times more jobs

Result 2

• Illustrates memory utilization

Conclusion

• Partial Utility is good to optimize resources and reduce operational costs
• More jobs can run in parallel
• Reducing queue waiting time is important
• QoS may degrade during execution but provides better long-run results

Scheduling for Volunteer Cloud Resources

• Focus on QoS-aware and cost-efficient task scheduling
• Includes latency-sensitive IoT applications like autonomous cars and industrial robotics
• Also includes latency-tolerant IoT applications like big data analysis

Motivation - Others

• Considers priority of tasks, violation cost, deadline constraints and network latency
• Can scheduling policies mitigate costs and QoS of volunteer requests?
• Can proposed methods improve QoS for real-time fog-cloud tasks?
• How does fog-cloud collaboration affect the QoS and monetary cost of volunteer requests?

Problem Statement

• To assign tasks that minimizes Computation, Communication, and Violation costs
• While maintaining high QoS by ensuring tasks meet deadlines with low computation and communication costs

Two Heuristic Scheduling Algorithms

• Min-CCV (minimize Computation, Communication and Violation costs)
• Min-V (minimize Violation cost)

Evaluation Criteria

• Evaluating algorithms through QoS in terms of makespan (total task time) and total cost
• Metaheuristic algorithms are performing a random search to find scheduling problem solution

Min-CCV Algorithm

• A Task scheduling algorithm using computation, communication, and violation awareness to minimize cost

Min-V Algorithm

• Designed for batch mode to minimize delay violations, prioritizing QoS

Complexity Analysis

• Min-CCV algorithm has a time complexity of O(n × m) and space complexity of O(n + m)
• Min-V algorithm has a time complexity of O(nlogn + n x m) and space complexity of O(n + m)

Performance Evaluation - simulation settings

Experiment one: varying the number of tasks from 50 to 300, fixing fog and cloud nodes to 30 and 15 respectively - Experiment two: with 200 tasks and 15 cloud nodes, varying the number of fog nodes from 10 to 50 - Experiment three: varying the number of cloud nodes, while the tasks and fog nodes were fixed to 200 and 30

Simulation Metrics

• Computation, communication, and violation cost
• Percentage of deadline satisfied tasks (PDST)
• Makespan (The makespan is the amount of time to process all of the tasks.)