QOS-Driven Job Scheduling: Multi-Tier Dependency Considerations

摘要

For a cloud service provider, delivering optimal system performance while fulfilling Quality of Service(QoS) obligations is critical for maintaining a viably profitable business. This goal is often hard to attaingiven the irregular nature of cloud computing jobs. These jobs expect high QoS on an on-demand fashion,that is on random arrival. To optimize the response to such client demands, cloud service providersorganize the cloud computing environment as a multi-tier architecture. Each tier executes its designatedtasks and passes the job to the next tier; in a fashion similar, but not identical, to the traditional job-shopenvironments. An optimization process must take place to schedule the appropriate tasks of the job on theresources of the tier, so as to meet the QoS expectations of the job. Existing approaches employ schedulingstrategies that consider the performance optimization at the individual resource level and produce optimalsingle-tier driven schedules. Due to the sequential nature of the multi-tier environment, the impact ofsuch schedules on the performance of other resources and tiers tend to be ignored, resulting in a less thanoptimal performance when measured at the multi-tier level.In this paper, we propose a multi-tier-oriented job scheduling and allocation technique. The scheduling andallocation process is formulated as a problem of assigning jobs to the resource queues of the cloud computingenvironment, where each resource of the environment employs a queue to hold the jobs assigned toit. The scheduling problem is NP-hard, as such a biologically inspired genetic algorithm is proposed. Thecomputing resources across all tiers of the environment are virtualized in one resource by means of a singlequeue virtualization. A chromosome that mimics the sequencing and allocation of the tasks in the proposedvirtual queue is proposed. System performance is optimized at this chromosome level. Chromosome manipulationrules are enforced to ensure task dependencies are met. The paper reports experimental results todemonstrate the performance of the proposed technique under various conditions and in comparison withother commonly used techniques.