Best-KFF: a multi-objective preemptive resource allocation policy for cloud computing systems

• Published in: Cluster computing 2022-02, Vol.25 (1), p.321-336
• Main Authors: Fathalla, Ahmed, Li, Kenli, Salah, Ahmad
• Format: Article
• Language: English
• Subjects: Algorithms; Cloud computing; Computer Communication Networks; Computer networks; Computer Science; Deadlines; Employment; Energy consumption; Heuristic; Heuristic methods; Infrastructure; Leases; Operating Systems; Preempting; Processor Architectures; Provisioning; Resource allocation; Resource utilization; Response time; Utility computing
• ISSN: 1386-7857; 1573-7543
• DOI: 10.1007/s10586-021-03407-z

Resource provisioning is a key issue in large-scale distributed systems such as cloud computing systems. Several resource provider systems utilized preemptive resource allocation techniques to maintain a high quality of service level. When there is a lack of resources for high-priority requests, leases/jobs with higher priority can run by suspending or canceling leases/jobs with lower priority to release the required resources. The state-of-the-art preemptive resource allocation methods are classified into two classes, namely, (1) heuristic and (2) brute force. The heuristic-based methods are fast, but they can’t maintain the system performance, while brute force-based methods are vice versa. In this work, we proposed a new multi-objective preemptive resource allocation policy that benefits from these two classes. We proposed a new heuristic called Best K-First-Fit ( Best - KFF ). The Best - KFF searches for the first k preemption choices at each physical machine (PM) and then sorts these preemption choices obtained from the PMs with respect to several objectives (e.g., resource utilization). Then, the Best - KFF selects the best choice maintaining the cloud computing system performance. Thus, the Best - KFF algorithm is a compromise between the heuristic and brute force classes. The higher the value of k is, the larger the search space is. The Best - KFF method maximizes the resource utilization of the physical machines and minimizes the average waiting time of advanced-reservation requests, the number of lease preemption, the preemption time, and energy consumption. The proposed method was thoroughly examined and compared against the state-of-the-art methods. The experimental results on various cloud computing systems demonstrated that the proposed preemption policy outperforms the state-of-the-art methods.