Bandwidth-Guaranteed Resource Allocation and Scheduling for Parallel Jobs in Cloud Data Center

Zhen Li, Bin Chen, Xiaocheng Liu, Dandan Ning, Qihang Wei, Yiping Wang, Xiaogang QiuSymmetry 2018 · DOI

TL;DR

This paper tackles the challenge of efficiently scheduling parallel jobs in cloud data centers, where network bandwidth is a critical bottleneck. They introduce a novel adaptive bandwidth-aware virtual cluster embedding algorithm (AdaBa) and a bandwidth-guaranteed migration and backfilling scheduling algorithm (BgMBF) to improve job acceptance rates and reduce response times, outperforming existing methods.

What Problem Does This Paper Address?

High-Performance Computing (HPC) jobs, often designed for tightly coupled parallel processes, are increasingly being run on cloud platforms. However, cloud environments, characterized by shared resources and variable network latency, can lead to unpredictable job completion times and violate Quality of Service (QoS) requirements. A key challenge is ensuring guaranteed network bandwidth for these parallel jobs, which is crucial for predictable performance. Existing solutions often focus on improving job acceptance rates but neglect the impact on future jobs or fail to guarantee bandwidth. This paper aims to address this by providing a framework that guarantees bandwidth for parallel jobs, leading to more predictable performance and efficient resource utilization in cloud data centers.

Methods

The paper proposes a two-pronged approach:

  • Adaptive Bandwidth-Aware (AdaBa) Virtual Cluster Embedding Algorithm: This algorithm is designed to intelligently allocate virtual machines (VMs) and reserve bandwidth for incoming parallel jobs. Its core idea is to "hide" bandwidth occupation by placing VMs of a single job on the same server, allowing them to communicate via the server's internal loopback network. AdaBa dynamically adjusts server priorities based on the requested bandwidth demand and the server's available resources. It uses a weight function that considers both the number of idle slots on a server and the ratio of the current job's bandwidth demand to the maximum bandwidth demand ever encountered. This adaptive strategy aims to maximize the reservation of bandwidth for future jobs.
  • Bandwidth-Guaranteed Migration and Backfilling (BgMBF) Scheduling Algorithm: This algorithm builds upon the First-Come-First-Serve (FCFS) principle but incorporates backfilling to utilize idle resources. It integrates AdaBa to ensure bandwidth guarantees for scheduled jobs. BgMBF allows suitable jobs from the waiting queue to be scheduled in idle resource fragments while the top job is waiting for resources. To prevent starvation of the top job, a preemptive mechanism is included. An enhanced version, BgMBFSDF, further optimizes scheduling by prioritizing backfilled jobs with shorter execution durations, aiming to increase the number of jobs completed before preemption.

Datasets

The paper uses two real-world parallel workload logs for evaluation:

  • KTH SP2 workload logs: Eleven months of accounting records from a 100-node IBM SP2.
  • NASA iPSC workload logs: Three months of records for a 128-node iPSC/860.

For these workloads, bandwidth demands were generated using a normal distribution based on calculated minimum, maximum, and average bandwidths.

Key Insights and Ideas

  • Bandwidth is the Bottleneck: The paper strongly emphasizes that network bandwidth, not just CPU or memory, is a critical factor for parallel job performance in cloud environments.
  • Hiding Bandwidth Usage: The core innovation of AdaBa is the strategy of placing VMs of a single job on the same server to leverage internal network bandwidth, thereby freeing up external network links for other jobs.
  • Adaptive Prioritization: Dynamically adjusting server priorities based on both the job's bandwidth needs and the server's available resources is key to AdaBa's success.
  • Backfilling for Efficiency: BgMBF demonstrates that intelligently filling idle resource fragments with waiting jobs can significantly improve overall system performance.
  • Shortest Duration First for Backfilling: The BgMBFSDF enhancement highlights that prioritizing shorter jobs for backfilling can lead to higher throughput and reduced migration costs.

Key Results

  • AdaBa's Acceptance Rate: AdaBa achieved up to a 15% improvement in job acceptance rate compared to existing algorithms like Oktupus and greedy algorithms, especially for workloads with higher average bandwidth demands.
  • BgMBF/BgMBFSDF Performance: The proposed BgMBF and BgMBFSDF algorithms significantly outperformed FCFS and other basic scheduling strategies in terms of average response time and average bounded slowdown.
  • Migration Cost: While BgMBF and BgMBFSDF utilize migration, the associated time cost was found to be significantly smaller than the gains in scheduling performance.
  • BgMBFSDF vs. BgMBF: BgMBFSDF consistently outperformed BgMBF, demonstrating the benefit of prioritizing shorter jobs for backfilling.

Limitations and Future Work

  • Static Bandwidth Reservation: The paper acknowledges that static bandwidth reservation might still be inefficient if traffic flows among parallel processes change dynamically.
  • Future Work: The authors plan to extend AdaBa to handle more complex scenarios, including heterogeneous bandwidth demands and uncertainty in bandwidth requirements. They also aim to explore dynamic bandwidth allocation mechanisms for parallel jobs.

Summary updated

BibTeX
@article{li2018bandwidth,
  author = {Zhen Li and Bin Chen and Xiaocheng Liu and Dandan Ning and Qihang Wei and Yiping Wang and Xiaogang Qiu},
  title = {{Bandwidth-Guaranteed Resource Allocation and Scheduling for Parallel Jobs in Cloud Data Center}},
  journal = {Symmetry},
  year = {2018},
  doi = {10.3390/sym10050134},
}
Figure