An Effective QoS-Constrained Scheduling Scheme for Cloud Computing Services

Liang-Teh Lee, Kang-Yuan Liu, and Ming-Jen Chiang

1. Introduction

With the rise of cloud computing, many large data centers provide cloud services have emerged. Therefore,how to improve the resource utilization and service quality of the data center has become an important issue under the economic and environmental considerations.

Cloud services are usually built based on the computing and data storage in the data center. Under this environment,the network computing service needs a high loading, high availability, and high scalability, and the resources utilization and service quality issues of these multi-level,distributed and virtualized systems also become more challenging.

On cloud computing, the task scheduler in addition to being able to meet the users’ quality of service (QoS)requirements must be able to make full use of system resources. From the users’ point of view, the QoS requirements are based on the deadline of the tasks submitted and the need of computing resources and types;from the server’s point of view, the system has to consider not only the above requirements, but also the resource utilization and power saving.

2. Related Work

The skills and knowledge applied to this study will be described in this section, including the concept of cloud computing, virtualization, QoS, kernel-based virtual machine (KVM), virtual machine migration, and extenics.

2.1 Cloud Computing

Cloud computing is a computing environment based on the Internet and can be extended dynamically. It uses network technology as a service to provide users with a large number of service nodes. Providers, who provide cloud services, using virtualization technology to build its services and rapid deployment of resources, provide users with a variety of service needs. Furthermore, users can obtain service resources and the type of services according to their needs. Therefore, regardless of the computing power of software resources or storage capacity of network,users can obtain those resources through the cloud services supplier, and significantly reduce the cost of the software and hardware purchasing[1].

2.2 Virtualization

The first commercialize virtual machine appeared in 1972 on IBM mainframe via the VM (virtual machine)operating system. The mainframe can be divided into a number of logic elements (virtual machines), and each logical unit is running on the same host. Fig. 1 is a schematic diagram of the virtualization technology[2],[3].

Fig. 1. Virtualization.

In general, the system on the physical machine is divided into several levels, the hardware resources,operating systems, applications, and hardware drive interface in operating system (OS). To make the multiple virtual machines run on the same physical machine, we need to join a software layer in the OS layer and the bottom layer of the middle of the hardware resources, it is called hypervisor or virtual machine manager (VMM) and is used to manage the hardware resources and guest OS scheduling.

2.3 Quality of Service (QoS)

QoS refers to the degree of satisfaction according to the users’ requirements. In the field of network services, voice and data applications have different requirements for QoS[1],[4],[5]. In this paper, QoS is defined as the degree of difference between the actual completion time of a user’s job and the latest completion time that the user expects.

2.4 Kernel-Based Virtual Machine (KVM)

KVM is an open-source virtual monitor, mainly in the way of full virtualization, but it provides para-virtualization function now. Compared with other VMM, the biggest difference is the KVM is directly applied to the Linux kernel as the VMM. KVM consists of two parts: the Linux kernel module and user space. Linux kernel module is the device driver which is responsible for the management of virtual hardware resources and management I/O requests from the guest OS; whereas user space is responsible for handling the virtual machine I/O request by calling the kernel module driver to perform an action. Fig. 2 is the system architecture of KVM.

Fig. 2. System architecture of KVM.

Fig. 3. Virtual machine migration.

2.5 Virtual Machine Migration (VMM)

Migration technology is an important function in virtualization technology. Virtual machine migration is to move an application running on a virtual machine in the original host to run on another virtual machine in other hosts. By applying the virtual machine migration technology, each virtual machine is considered as a completely movable unit[6].

The following benefits can be achieved by applying the migration technology.

1) After migration, the destination virtual machine,which has better processing performance, can increase the strength of the virtual machine execution and reduce the total completion time of work, to enable the supplier to work earlier after the execution.

2) Because of the implementation of the migration movements in the virtual machine level, continuous-time migration of data is the complete content of the system memory.

By using virtual machine migration technology, each virtual machine can be migrated to the destination data center, that is, the location which provides resources. As a result, the system administrator does not provide the operating system access permissions to users, and this can also be a higher level of security in the provision of services. In short, a combination of virtual machine and migration technology can significantly improve the overall management. Fig. 3 shows the schematic diagram of the virtual machine migration.

2.6 Extenics Theory

The extenics theory was proposed by Professor Cai Wen in 1983 to solve the incompatibility problem through the systematic transformation[7]. The element is the basic component in the extenics theory. It consists of three tuples,events, characteristics, and values. In order to solve the incompatible problems, the relationship of events,characteristics, and values must be considered. The extenics associative function can be established to find the relationship of events, characteristics, and values.

In extenics, the distance between two points has been defined as ρ(x, y) =|x-y| which is the same as in classical mathematics. In order to establish an associative function,the distance between a point and a finite interval should be defined. The distance between a point x and the real interval X0=[a0, b0] is denoted by ρ(x, X0) and defined as

In extenics set, if a point x is outside the interval, the distance between x and the interval is the distance between x and the closest endpoint of the interval. However, if x is inside the interval, the distance becomes negative.Furthermore, considering the relationship between a point x and two intervals X and X0, the positional distance can be denoted as D(x, X0, X).

Fig. 4. Extenics associative function.

Let X0= [a0, b0] and X = [c0, d0] be two intervals in the domain of real, X⊃X0, and if these two intervals do not have a common end point, then the positional distance can be defined as:

The basic associative function can be expressed as:

To calculate the degree of the associability of the relationship between a point x and an interval X0in extenics,an extenics associative function K(x) must be created. We say x is related to X0if K(x)≥0 and x is not related to X0if K(x)＜0. When -1＜K(x)＜0, then the current situation of x is not related to X0, but it can be transferred to be related to X0.Fig. 4 shows an extenics associative function to describe that K(x)≥0 if the point x is in the range [a, b], and -1＜K(x)＜0 if x is in [c, a] or [b, d]; otherwise, K(x) will be less than -1.

In the proposed system, QoS is described by the extenics associative function.

3. Proposed Mechanism

3.1 System Framework

In cloud computing environment, when users require the cloud services, in the proposed system, the cloud server will assign different priority levels to user tasks according to the users’ requirements. The expected completion time for the tasks submitted by the user is used to calculate the QoS by applying the extenics associative function. In this study, we propose a scheduling mechanism to enhance the utilization efficiency of the processor and to meet the QoS according to users’ requirements.

3.2 Scheduling Mechanism

In the proposed system, the central processing units(CPUs) with different performance in the cloud server are classified into five levels. When a task is waiting for execution on the CPU with lower performance, it will be migrated to be executed on an idle CPU with higher performance. Thus, the utilization of the CPU with higher performance will be kept in the busy state for increasing its utilization, as shown in Fig. 5.

Fig. 5. Schematic diagram of enhancing the utilization of the higher-level CPU by applying virtual machine migration.

The priority of user’s task is defined according to the rent user paid. In this study, the cloud server consists of five physical machines with different performance and each physical machine supports two VMs. In accordance with the processing capabilities of the processor, CPU performance is divided into five levels: level one is the machine with the highest performance and level five is the lowest one. The rent of the server is also divided into five levels corresponding to the CPU performance level for executing tasks.

A. When a Task is Entering the System

Once a task is entering the system, it is assigned to the VM for execution on the corresponding CPU level with the corresponding priority.

a) When the CPU is idle, the upper level CPU is checked to see whether it is idle, until the busy CPU or the highest level of CPU has been checked. On the busy CPU,the priority of executing tasks is compared with the priority of new coming tasks.

1) When the priority of a new coming task is lower, it will be degraded to be executed on the lower-level CPU.

2) When the priority of a new coming task is higher, it will be executed in this CPU, and the running tasks will be migrated to be executed on the lower-level CPU.

b) When the CPU is busy, the priority of a new coming task is compared with the priorities of those executing tasks and waiting tasks on this CPU.

1) When the priority of the new coming task is equal or lower than the running tasks, it will be put into the waiting queue of the CPU.

2) When the priority of the new coming task is higher than the running tasks, it will be executed in this CPU, and some running tasks will be migrated to the lower-level CPU for execution.

The flowchart of the process is shown in Fig. 6. In Fig.6, taskirepresents the entering task with priority i, VMidenotes the level-i VM, G.Q is the global queue, and CPUirepresents the CPU with level-i performance, while j represents the level of running VM in CPUk.

Fig. 6. Process to be performed when a task is entering the system.

B. When the Task is Running

During the period of executing the task, once an idle CPU is checked, the following process will be performed:

a) Check the level of the idle CPU, if it is the lowest one then no further action will be performed, otherwise the next lower-level CPU is checked. If it is idle then no further action will be performed, otherwise the number of the waiting VMs in this CPU is checked.

1) If the waiting queue is empty, the VM of the running task is migrated to the idle CPU.

2) If the waiting queue is not empty, then the VM at the head of the waiting queue is migrated to the idle CPU for execution.

b) No further action is performed if there is no idle CPU.

The flowchart of the process is shown in Fig. 7, where CPUkrepresents the CPU with level-k performance, and VMjdenotes the VM with level j.

The proposed mechanism allows the higher performance CPU to work continuously, and the resources of the high-performance processor will be effectively utilized so as to enhance the QoS.

3.3 QoS Measurement

In this paper, the QoS is measured by using the following three parameters:

i: the ideal completion time that users expect,

l: the latest completion time that users request,

r: the actual completion time.

In accordance with the above parameters, an extenics associative function can be built by (4) for measuring QoS,as illustrated in Fig. 8.

Fig. 7. Process to be performed when tasks are running.

Fig. 8. QoS measurement.

In accordance with the value of the extenics associative function, when r ＞ i, the QoS value is negative, indicating that the QoS is unsatisfying. However, if the QoS value is in the range between -1 to 0, the QoS is accepted but not ideal. When r = i, QoS is 0, indicating that the completion time is the ideal completion time the user expects. When r＜ i, QoS is positive, indicating that the QoS is satisfying.And the higher the QoS value is, the better the user is satisfied, since the task completes before the ideal time the user expects.

4. Experiments and Discussion

4.1 Experimental Environment

In the experiments, the computer is using Intel®Core™ 2 Quad Q8400 CPU with operating frequency 2.67 GHz, 4 GB DDR2 memory, and 1TB SATAII hard drive.The experimental platform is CloudSim, cloud simulation software, under Windows 7 operating system. The VM is the single-core architecture, and the compiler is IDE.

4.2 Experimental Results and Data Presentation

A. Experiment 1

This experiment is to simulate the workload requested by users during one day, and the requirement of completion time for each task is given. The simulation is divided into two parts, one is with applying the proposed strategy and the other is without applying the proposed strategy.

Part I: Applying the proposed strategy

Table 1 presents the requirements of the completion time by users. For example, in machine1, three tasks in corresponding VMs enter for execution, and the completion times are expected in 4, 5, and 8 hours, respectively. In machine2, five tasks in corresponding VMs enter for execution, but only three VMs can be run at the same time,and the remaining two VMs are waiting in the queue.

Table 2 shows the actual time required for each task. In this experiment, the actual time VM executed is 60% of the deadline the user expected. For example, in Table 1, the first VM executed in machine1 requires 2.4 hours, while the expected completion time of the user is four hours.

The actual completion time by applying the proposed strategy is shown in Table 3. It measures the elapse time for each VM.

Table 4 illustrates the standard of QoS. According to the completion time the user requested, 90% of this duration is the standards, that is, if the completion time the user requests is within four hours, then the ideal completion time for this VM is set to 3.6 hours.

Table 5 shows the measured QoS which is calculated by applying (1). In Table 5, some QoS is 0.5, because these VMs are not migrated during their execution, thus, QoS will not be improved in this situation. When the task has been migrated, the QoS will be improved, since migration will result in earlier completion.

Part II: Without applying the proposed strategy

In this experiment, the same data in Table 1 were applied and conducted with the same simulation but without applying the proposed strategy. Table 6 shows the actual completion time without applying the proposed strategy. That is, when 5 tasks enter the system, only three tasks can be run at the same time, while the remaining two VMs will wait in the queue. Even if there is an idle CPU with higher performance, the migration will not be performed, and each task is placed in the specified machine to run or wait.

Table 7 presents the measured QoS without applying the proposed strategy. We can see that without applying the proposed strategy, the migration will not be performed. As a result, only three tasks can achieve the better QoS, while the QoS of waiting tasks will be relatively low, even worse than that the user expected.

Table 1: Completion time user requested

Table 2: Actual execution time needed

Table 3: Actual completion time of applying the proposed strategy

Table 4: QoS standards

Table 5: QoS Measured by applying the proposed strategy

Table 6: Actual completion time without applying the proposed strategy

Table 7: QoS measured without applying the proposed strategy

Table 8 indicates the comparison of total execution time of each physical machine with applying and without applying the proposed strategy. In addition, the comparison is illustrated in Fig. 9.

B. Experiment 2

This experiment is similar to Experiment 1, except the workload of the high performance CPUs are relatively low.That is the less number of tasks and shorter length of the tasks are simulated in this experiment. The results are shown in Table 9 to Table 16 and Fig. 10, respectively.

Table 8: Comparison of total execution time of each physical machine

Fig. 9. Comparison of total execution time in each machine.

Table 9: Completion time the user requests

Table 10: Actual execution time needed

Table 11: Actual completion time of applying the proposed strategy

Table 12: QoS standards

Table 13: Measured QoS by applying the proposed strategy

Table 14: Actual completion time without applying the proposed strategy

Table 15: QoS measured without applying the proposed strategy

Table 16: Comparison of total execution time of each physical machine

Fig. 10. Comparison of total execution time.

C. Experiment 3

This experiment is similar to the previous two experiments with roughly the same operation time in all processors, but the number of tasks and the length of the tasks are different. The results are shown in Table 17 to Table 24 and Fig. 11, respectively.T

Table 17: Completion time user requested

Table 18: Actual execution time needed

Table 19: Actual completion time by applying the proposed strategy

Table 20: QoS standards

Table 21: QoS measured by applying the proposed strategy

Table 22: Actual completion time without applying the proposed strategy

Table23: QoS measured without applying the proposed strategy

able 24: Comparison of total execution time of each physical machine

Fig. 11. Comparison of total execution time.

By comparing between Table 13 and Table 15, we can clearly see the changing of QoS before and after applying the proposed strategy. In Table 15, QoS are 0.5, because the actual work time is set to 60% of deadline, and the migration is not performed in this case. However, in Table 13, by applying the proposed strategy, the migration has been performed; the task requests for running on the lower performance processor can be executed on a higher performance processor to be completed earlier, so as to improve the QoS.

From the results of Experiment 1 and Experiment 2, we can see that the operation time of the physical machine will be significantly reduced by applying the proposed strategy,especially in the lower-level physical machines. In terms of performance, by applying the proposed strategy, the situation of idle high-performance processors but busy lowperformance processors can be avoided. From Experiment 3, we can see that with the heavy workload there will be no idle processor and the overall performance can only be a little improved, but QoS will not be degraded.

5. Conclusions

This paper presents a strategy for improving the system performance and satisfying the QoS of user’s requirement in cloud computing. QoS can be improved significantly in the case of existing idle higher performance processors. In our experiments, the average system utilization has been applied. The experimental results show that the QoS can be enhanced depending on the amount of the idle time of high-performance processors. The earlier the higher performance processors becoming idle, the more favorable to the task requests to be executed in the lower performance processor and the greater the QoS obtains. Even in the non-extreme case, by applying the proposed strategy, the QoS can also be effectively enhanced.

[1] R. K. Jha and U. D. Dalal, “A performance comparison with cost for QoS application in on-demand cloud computing,” in Proc. of 2011 IEEE Recent Advances in Intelligent Computational Systems, Trivandrum, 2011, pp. 11-18.

[2] Y.-F. Li, W. Li, and C.-F. Jiang, “A survey of virtual machine system: current technology and future trends,” in Proc. of the 3rd Int. Symposium on Electronic Commerce and Security, Guangzhou, 2010, pp. 332-336.

[3] W. Chen, H. Lu, L. Shen, Z. Wang, N. Xiao, and D. Chen,“A novel hardware assisted full virtualization technique,” in Proc. of the 9th Int. Conf. for Young Computer Scientists,Zhangjiajie, 2008, pp. 1292-1297.

[4] S. Hosono, A. Kuno, M. Hasegawa, T. Hara, Y.Shimomura, and T. Arai, “A framework of co-creating business values for IT services,” in Proc. of IEEE Int. Conf.on Cloud Computing, Bangalore, 2009, pp. 167-174.

[5] H. N. Van, F. D. Tran, and J. Menaud, “Autonomic virtual resource management for service hosting platforms,”presented at 2009 ICSE Workshop on Software Engineering Challenges of Cloud Computing, Vancouver, 2009.

[6] P.-C. Chen, C.-I. Lin, S.-W. Huang, J.-B. Chang, C.-K.Shieh, and T.-Y. Liang, “A performance study of virtual machine migration vs. thread migration for grid systems,” in Proc. of the 22nd Int. Conf. on Advanced Information Networking and Applications, GinoWan, 2008, pp. 86-91.

[7] W. Cai, “The extension set and incompatible problem,”Journal of Scientific Exploration, vol. 1, pp. 81-93, no. 1,1983.