{'fraction_non_alphanumeric': 0.03950254602428516, 'fraction_numerical': 0.010849980415197807, 'mean_word_length': 4.556147986942329, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 4, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
H2O-Cloud: A Resource and Quality of Service-Aware Task Scheduling Framework for Warehouse-Scale Data Centers -- A Hierarchical Hybrid DRL (Deep Reinforcement Learning) based Approach

Cloud computing has attracted both end-users and Cloud Service Providers (CSPs) in recent years. Improving resource utilization rate (RUtR), such as CPU and memory usages on servers, while maintaining Quality-of-Service (QoS) is one key challenge faced by CSPs with warehouse-scale data centers. Prior works proposed various algorithms to reduce energy cost or to improve RUtR, which either lack the fine-grained task scheduling capabilities, or fail to take a comprehensive system model into consideration. This article presents H2O-Cloud, a Hierarchical and Hybrid Online task scheduling framework for warehouse-scale CSPs, to improve resource usage effectiveness while maintaining QoS. H2O-Cloud is highly scalable and considers comprehensive information such as various workload scenarios, cloud platform configurations, user request information and dynamic pricing model. The hierarchy and hybridity of the framework, combined with its deep reinforcement learning (DRL) engines, enable H2O-Cloud to efficiently start on-the-go scheduling and learning in an unpredictable environment without pre-training. Our experiments confirm the high efficiency of the proposed H2O-Cloud when compared to baseline approaches, in terms of energy and cost while maintaining QoS. Compared with a state-of-the-art DRL-based algorithm, H2O-Cloud achieves up to 201.17% energy cost efficiency improvement, 47.88% energy efficiency improvement and 551.76% reward rate improvement.


I. INTRODUCTION
A Cloud is a platform over network where information technology and computing resources are available instantly and on-demand [1]. Cloud computing has become an efficient and powerful archetype for both end-users and cloud operators. The advantages of high computing power, low service cost, high scalability and availability attract endusers with desirability to implement computational and power consuming applications at low expense. The huge revenue opportunity is an inviting treasure for Cloud Service Providers (CSPs). Recent reports have shown that the global public cloud market revenue was more than $130 billion in 2017 and is expected to exceed $500 billion in 2026. Google App Engine (GAE) [2], Amazon Web Service (AWS) [3], and Windows The authors are with the Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA, 90089, USA (e-mail: mingxic@usc.edu; jli724@usc.edu; pbogdan@usc.edu; shahin.nazarian@usc.edu).
Azure [4] are among the popular commercial services in cloud computing.
Although the revenue of cloud computing is notable, the electricity bill of data centers (DCs) is also noteworthy. DCs in US alone used 91 billion kilowatt-hours of electrical energy in 2013, and the annual usage will increase to 139 billion kilowatt-hours by 2020, with the cost of power of $13.7 billion [5]. With large-scale DCs, resource management of cloud-platform enables CSPs to achieve economies of scale by improving cost effectiveness [6]. However, power efficiency of large-scale DCs is harmed by inefficient resource utilization of servers, which is a well-known problem faced by modern CSPs [7]- [9].
CPU and memory utilization of a Google cluster with 12.5k machines in one month has been analyzed by former researchers [9]. The majority utilization rate of both CPU and memory resources is below 50% for most of the time, which harms power usage effectiveness [10]. Similarly, Barroso et al. [11] note two critical features of energy usage of DCs: (i) servers tend to be more energy inefficient under low utilization rate (with the optimal power efficient utilization rate of most servers ranging between 70% and 80%), and (ii) servers consume a considerable amount of power in idle mode. Therefore, resource-efficient cluster management should take DCs' resource utilization rate (RUtR) into consideration while maintaining Quality of Service (QoS). QoS is defined based on a combination of task rejection rate, deadline violation rate and reward rate (which measures how often the user-designated task priority requirement is fulfilled) in this work. For profitdriven CSPs in industrial community with warehouse-scale DCs, effective cloud resource management and task scheduling are resultful measures to broaden profit margin.
Along with the fast-growing cloud computing market, a number of challenges have arisen with respect to resource management and task scheduling: (i) Scalability has become an important consideration to support large-scale DCs that have been investigated or are being planned worldwide. (ii) Self-learning techniques are required to handle the uncertainty and changing nature of user requests [12], [13]. Figure 1 shows that user requests have different patterns, and resource requirements such as CPU and memory vary over time. (iii) Short runtime is highly desirable, in order to provide quick response to user requests. To deal with these challenges, arXiv:1912.10808v3 [cs.DC] 12 Feb 2020 intelligent cloud resource management has risen and become the state-of-the-art fashion in cloud computing [14].
In this work, we propose a Hierarchical and Hybrid Online task scheduler for Cloud computing (H 2 O-Cloud), inspired by deep reinforcement learning (DRL) [15]. DRL is effective for problems where state space has high dimensions and action space is rather limited [15], [16]. Therefore, the large dimension of state space (i.e., large-scale cloud platform configuration) in this cloud resource management and task scheduling problem can be resolved by applying DRL technique. In order to handle the enormous action space (i.e., a large number of available servers and exact task execution time options) and realize real-time scheduling, a hierarchical task scheduling process is proposed. More precisely, the proposed hierarchical method decouples the action space into several sub-action spaces: server farms, servers, hours and minutes, where the decision for each sub-action is made by one Deep Q-Network (DQN). The specialized DQNs not only schedule tasks faster than one combined large DQN, but also improve the decision quality as one DQN is responsible for one type of action.
The proposed hierarchical task scheduling process schedules an incoming task into a server farm, and chooses a server in selected server farm; then takes dynamic pricing model (proposed in Section III-E) into consideration to select optimal hour and minute(s) to run the task (details presented in Section IV-A and Section V-B). In the proposed framework, uncertainties in user requests are handled by the DQNs that are capable of autonomic learning. In addition, the fast decisionmaking challenge as well as the scalability are enabled by the online scheduling of DRL. Comprehensive environment information is considered in our model, such as user-request information, current environment status, historical decisions, user workload patterns and realistic electric price model, etc. Our proposed method can be extended to include more input information as either new features of certain DQNs or new DQN layers.
In summary, the main contributions of our paper are as follows.
• Four-Layer Hierarchical Architecture. H 2 O-Cloud schedules incoming user requests in series and makes complex long-term decisions hierarchically. The fourlayer structure is trained individually on-the-go without pre-training. It breaks down massive state and action spaces generated by the warehouse-scale cloud platform configuration, hence speeds up the decision-making process while maintaining high performance. • Hybrid Mechanism. The hybrid mechanism provides valid actions when DRL agent generates invalid actions in some corner cases. This back-up mechanism further reduces the task rejection rate and contributes to improvement of QoS, which is defined earlier as the task rejection rate, deadline violation rate and reward rate. • Fine-grained Online Scheduling for Warehouse-Scale CSPs. This work achieves fine-grained (minutelevel scheduling) high-performance online scheduling for warehouse-scale CSPs by using DRL without the need for pre-training. The remainder of this paper is organized as follows: related work is reviewed in Section II, Major properties of H 2 O-Cloud and system model are presented in Section III, The structure and algorithm of H 2 O-Cloud are presented in Section IV and Section V respectively, and the experiment results are discussed in Section VI.
II. RELATED WORK Cloud resource management has become a popular research area and many approaches have been proposed to fulfill various objectives. The authors in [10], [17] proposed Paragon to increase the capability and cost effectiveness of large-scale DCs by improving their resource efficiency. Delimitrou et al. proposed a resource-efficient and QoS-aware cluster management system for joint resource allocation and assignment [6]. The authors in [18] presented a distributed scheduler that targets both scheduling speed and quality, also performs admission control. A hybrid cloud resource provisioning system that uses both reserved and on-demand resources was proposed in [12]. Nevertheless, these prior works scale up to 1000 servers which is not enough for a warehouse-scale CSP (with 10, 000+ servers [11]). The authors in [19]- [22] utilized a realistic electric price model to improve the energy cost efficiency; however their solution suffers from scalability issues, and their offline algorithms have difficulties in dealing with the large size of inputs. N. Liu et al. applied DRL techniques to (partially) solve the resource allocation problem [16], which can deal with scalability issues. Their solution, however, does not schedule tasks with data dependencies, which is critical to guarantee that parallel tasks are executed correctly in the cloud environment [23]. The authors in [24] proposed a DRL-based QoS-aware job scheduling framework to reduce average job response time, where QoS requirement is defined as the expected job response time. However, energy cost is not considered in their work. None of these works conducts fine-grained online scheduling, i.e., scheduling each task into specific minute(s) on-the-fly while targeting energy cost reduction at the same time.

III. H 2 O-CLOUD: PROPERTIES AND SYSTEM MODELING
The properties of H 2 O-Cloud and system model are introduced in this section, including the models for user workload, cloud platform, energy consumption and electricity price.
A. Property 1) Resource-Efficient: CSPs that own warehouse-scale DCs are incentivized by increasing the profit through minimizing energy cost while meeting users' requirements in cloud services. Utilizing resources efficiently is a reasonable way of achieving economies of scale. Considering a server tends to be more energy-efficient when its RUtR lies in the optimal range, but consumes a lot of energy when idle [11], the resource efficiency of H 2 O-Cloud is realized through scheduling tasks intelligently to make each running server work at its optimal energy-efficient operating range and to selectively shut down idle servers.
2) QoS-Aware: Task priority and deadline describe the importance and emergency degree of a task, which are designated by end-users. In the case of contention, tasks with higher priorities should be executed before tasks with lower priorities, and tasks with earlier deadlines should be executed before tasks with loose deadlines. Awareness of task priorities and deadlines enables H 2 O-Cloud to achieve priority-aware task scheduling with low deadline violation rate and to yield better QoS. In addition, the commonly used soft-deadline for tasks [25]- [27] is adopted in this work. In contrast to a harddeadline, the missing of which causes permanent task rejection and is defined as catastrophic failure, a soft-deadline allows a task to be recycled and rescheduled in case of a deadline violation. Utilization of soft-deadlines equips the presented framework with a solution to reduce task rejection rate while guaranteeing admission control.
3) Fast, Warehouse-Scale, Online: H 2 O-Cloud allocates resources and schedules tasks by using the DRL-based hybrid algorithm, which enables quick effective resource allocation and task scheduling even on warehouse-scale cloud platforms. H 2 O-Cloud is able to make decisions on-the-fly, given that it is aware of historical decisions and current utilization of all DCs, and does not need to wait for the presence of all task requests to make high quality decisions. Fast convergence of DRL algorithm gives good performance in runtime, cost efficiency, and energy efficiency without pre-training the models.

B. Cloud Platform Model
Virtualization is the fundamental technology of cloud computing, which enables multiple operating systems to run on the same physical platform [28]. One server in cloud platform can hold several virtual machine (VM) configurations, and servers can hold different machine types. VMs are used by CSPs to provide infrastructures, platforms, and resources (e.g., CPU, memory, storage, etc.) to run end-users' applications. For example, Google App Engine (GAE) supports more than twenty machine types to configure cloud services differently, such as high-memory configuration and high-CPU configuration [29].
Graph modeling is used to present server farms in this work. Each vertex in the graph represents a server, and each edge represents a channel between servers. As shown in Figure 2, a CSP owns N servers {ψ 1 , ψ 2 , ..., ψ N }, and nearby servers are structured into M clusters (or farms, server cluster and server farm are equivalent in this work). Server clusters are connected with two-way high-speed channels, whereas servers within one server cluster are connected through local channels. The bandwidth of channels between servers ψ i and ψ j in a cluster is represented by the weight of the corresponding edge (denoted by B(i, j)). A CSP supports V types of VMs {V M 1 , ..., V M V } in total, and each server supports a subset of these types. Each type V M v (v ∈ [1, V ]) is associated with a two-tuple parameter set {R v CP U , R v M EM }, which represents the required amount of CPU and memory units, respectively.
A server ψ n holds in total CP U n units of CPU and M EM n units of memory. Therefore, at any time t, the total amount of CPU and memory structured in VMs on server ψ n should be less than the upper bound of its CPU and memory, i.e.,

C. User Workload Model
In this paper, the entire user workload is composed of a number of jobs (i.e., user requests), each of which containing several tasks with dependencies. A job is modeled by a Directed Acyclic Graph (DAG) [23], [30], as shown in Figure  2. A vertex u i ϕ in the DAG represents the i-th task in the uth job. The weight of an edge w u (a, b) indicates the amount of dependent data that needs to be transferred from task u a ϕ to task u b ϕ in job u . Using job 1 in Figure 2 as an example: job 1 contains 7 tasks { 1 1 ϕ, ..., 1 7 ϕ}, and edge weight w 1 (a, b) (a, b ∈ [1,7]) is the amount of data that needs to be transferred from task 1 a ϕ to task 1 b ϕ so that the following task 1 b ϕ can be executed.
Each task u i ϕ (i.e., task i in job u ) is associated with a parameter tuple { u i D CP U , u i D M EM , u i D V M , u i P rr, u i DDL}, which represents the requested CPU, memory, VM type, priority and soft-deadline of task u i ϕ, respectively. Each VM type has its own amount of CPU and memory, i.e., Based on the Admission Control Policy, if a task requests unfulfillable amount of resources, then this task and the corresponding job should be rejected immediately. If the softdeadline is violated, the job will be redirected and rescheduled instead of being rejected permanently. Also, according to Service Level Agreement (SLA), one prerequisite should be met if a task u i ϕ is allocated to server ψ n at time t: the requested CPU and memory in each VM type should be less than or equal to the amount of CPU and memory in that VM type on the server, i.e.,

D. Energy Consumption Model
The total power of server ψ n at time t, P wr n ttl (t), is composed of static power P wr n st (t) and dynamic power P wr n dy (t), both of which are dependent on the CPU utilization rate U r n (t) of server ψ n at time t, which is calculated as: P wr n st (t) is constant when U r n (t) > 0 and zero otherwise. P wr n dy (t) increases linearly as U r n (t) increases linearly under the optimal utilization rate U r n Opt , and increases non-linearly otherwise [20], [22]. Additionally, different servers have different energy performances even under exactly identical utilization rate. In this paper, we adopt the dynamic power model from [20] and P wr n dy (t) is calculated as U r n (t) · a n , U r n (t) < U r n Opt U r n Opt · a n + U r n (t) − U r n Opt 2 · b n , U r n (t) ≥ U r n Opt .
We use parameters a n and b n to capture the linear behavior and non-linear behavior of power increase of server α n , respectively. The total power used in all servers at time t is P wr ttl (t) = N n=1 P wr n ttl (t) = N n=1 P wr n st (t) + P wr n dy (t) . The total energy consumption can be calculated as Energy = T 0 P wr ttl (t)dt, i.e., energy efficiency is

E. Dynamic Pricing Model
In this paper, we consider a realistic non-flat price model P rice t, P wr that is composed of a time-of-use-pricing (TOUP) component and a real-time pricing (RTP) component [31]- [33]. The TOUP is dependent on the time of the day and is usually higher in peak usage time periods than offpeak time, in order to incentivize users to shift loads towards off-peak periods. The RTP price increases as the total energy usage grows. The energy cost of server ψ n at time t is P rice(t, P wr n ttl (t)). The total energy cost of all servers is: Then energy cost efficiency can be calculated as T otalCP U Cost , where T otalCP U is the total amount of CPU requirement processed in time period T .

F. Problem Formulation
In this work, the cloud energy cost reduction problem is formulated as: Given the user workload model, cloud platform model, energy consumption model, and dynamic pricing model. Find resource allocation and task scheduling on-the-fly. Maximize energy cost efficiency. Subject to: and task dependency requirements.

IV. H 2 O-CLOUD: THE RESOURCE MANAGEMENT AND TASK SCHEDULING FRAMEWORK
Making decisions under a comprehensive system model and in one step may offer high performance as the overall environment and user request information are considered altogether. That however would significantly increase the runtime as the state space and possibly the action space are large; which in turn eliminates the possibility of real-time effectiveness and hence impacts its feasibility.
In this section, we present H 2 O-Cloud: a Hierarchical and Hybrid Online Cloud resource management and task scheduling framework based on DRL. H 2 O-Cloud utilizes cloud resources efficiently and is aware of QoS. As shown in Figure 3, four decisions are made in the proposed multilayer system. More specifically, H 2 O-Cloud provisions cloud resources in clusters and servers in the first two layers, and schedules tasks into appropriate hours and specific minutes in the last two layers. Training of Deep Q-Network (DQN) systems is done on-the-fly, and performance is guaranteed by fast convergence of our algorithm described in Section V-B. By using DRL-based hybrid Algorithm 1 we have proposed in this work, resource efficiency and QoS are improved.

A. Multi-Layer Resource Management and Task Scheduling Framework
A CSP with tens of thousands of DCs faces a complicated decision-making challenge as it receives millions of user requests a day, and has to figure out the following decisions to run a certain incoming task: 1) which server cluster; 2) which server in that cluster; 3) which hour of a day to reduce electric bill; 4) which minute(s) in that hour to ensure onthe-fly response and avoid congestion; and 5) how to manage the deadline and priority, e.g., reschedule the task if its softdeadline cannot be met. All of these decisions need to be made in a short time (less than one minute) when an incoming task has arrived.
In this work, we consider a CSP with warehouse-scale servers. Tens of thousands of servers are clustered into tens of server clusters. In order to make decisions more efficiently, and also increase the performance of the DQN of our system, our framework first decides which cluster should be used and then specifies the exact server. In addition, according to realistic price model and quality of service awareness, coarsegrained scheduling (hour control) and fine-grained scheduling (minute control) of tasks should be done separately to meet the requirement of efficiency and effectiveness.
1) Layer 1 -Cluster-Level Control: The inputs of this layer, D CP U and D M EM , as shown in Figure 3 are used in the Admission Control to filter jobs with tasks demanding unfulfillable resources. After admission control, one task could be handled by any cluster candidate in the warehouse-scale CSP. In order to reduce energy cost and latency of transmission between clusters, tasks within one job will be allocated into the same cluster. And the first layer decides which cluster to allocate the job. With proper training, this DQN can learn the rules of assigning new jobs to a cluster such that overall the U r is optimized.
2) Layer 2 -Server-Level Control: One cluster may consist of tens of thousands of servers, and each server supports several different kinds of virtual machine configurations. Serverlevel control allocates incoming tasks into a subset of servers which have the required machine configurations to support these tasks. This is the reason to include the VM type D V M in the inputs of this layer. The second layer then decides which server to host the task. With the deep structure in the DQN, a rule is learned to select a server with medium U r (e.g. 40% − 60%) to host incoming tasks as it is closer to the optimal utilization rate. The admission control in this layer is done similarly as cluster-level.
3) Layer 3 -Hour Scheduling: The realistic electric price model comes into play in this layer. Incoming tasks are highly likely to be allocated into hours with lower electric prices if U r is in an acceptable (efficient) range. In other words, hour scheduling is congestion-aware, cost-aware, and resource-efficient. All incoming tasks come with softdeadlines designated by end-users, and the proposed system will assign a penalty if any soft-deadlines is violated. Therefore, hour scheduling is also deadline-aware and QoS-aware. The admission control in this layer is done similarly to that of the cluster-level. 4) Layer 4 -Minute Scheduling: The proposed system schedules tasks into specific server and exact minute(s) as the requirement of online scheduling. Tasks with higher priorities will be executed earlier, which fulfills the priorityaware requirement. This last layer is QoS-aware, as it provides feedback to the scheduler when priority requirement is met or violated. The admission control is the same as the one in the cluster-level.

B. Deep Q-Learning Background
Deep Q-learning combines reinforcement learning with deep neural network, which is proposed by Google DeepMind [34] and used in playing Atari games [15], [35]. In an environment, a reinforcement learning (RL) agent makes a sequence of actions (a), based on the observations of environment and rewards (r) of actions. At each time-step the agent selects a valid action from a set of available actions, which is called the action space. By taking the action, the agent changes the internal state of the environment, which may not be accessible to the agent, instead the agent only obtains some observation of the environment. The agent can also get some rewards in addition to observation after taking the action. Therefore, the inputs of RL algorithm are the sequence of previous actions and observations of the environment, and the algorithm learns strategies to maximize future rewards depending on these sequences (s).
As we mentioned before, the goal of RL agent is to seek maximum future rewards by selecting actions. The future rewards are discounted by a factor of γ per timestep, so the future discounted reward at time t is defined as Then the maximum expected return achievable by following any policy π after seeing sequence s and taking action a is defined as the optimal action-value function Q * (s, a) = max π E[R t |s t = s, a t = a, π]. This optimal action value function obeys the identity known as the Bellman equation: It is common to use a function approximator to estimate the optimal action-value function: Q(s, a; θ) ≈ Q * (s, a). Other than a linear function approximator, a nonlinear function approximator such as a neural network can also be used. A neural network function approximator with weights θ is defined as a Q-network [15].

C. Deep Q-Learning in Resource Management System
For a warehouse-scale CSP, the state space and action space are enormous if tasks are allocated directly into specific server and minute(s). In order to overcome this challenge, we propose the multi-layer structure to decouple the huge decision spaces (i.e., number of clusters × number of servers × number of hours × number of minutes in one hour). Each layer of H 2 O-Cloud uses deep Q-learning algorithm with experience play (shown in Algorithm 1) which is suitable for solving complicated control and decision-making problems with a large state space but a finite action space. Also, the four-layer framework divides the original one single action space with an enormous size into four smaller subsets with different input features.
The algorithm selects and executes decisions according to a deep Q-learning based hybrid algorithm, i.e., if thegreedy policy generates a legal action, then the action will be executed and stored into memory. Otherwise the Round-Robin algorithm will be used to generate the action. The rationale behind this is that DRL technology sometimes generates illegal actions and with the same input, the decision-making neural network generates same output before next learning. Therefore, the background Round-Robin algorithm can help to avoid poor decisions in such cases.
1) Action Space: A RL agent interacts with its environment and selects an action from a set of available actions based on observation. In our case the proposed framework receives an incoming task, and selects a server to execute this task at some time (i.e., action), based on the information retrieved from the task and data center environment, such as requested resources of task, available resource of servers, task priority and deadline designated by end user, and historical decisions made by agent, etc. For layer 1 to layer 4, action spaces are defined as: available clusters, available servers, available hours, and available minutes, respectively. Store transition (s t+1 , at, rt, st) in memory 20 Store decision and reject signal 21 Sample random mini-batch of transitions (s j+1 , a j , r j , s j ) from memory 22 target j = r j , if episode terminates at step j+1 r j + γmax a Q (s j+1 , a ; θ ), otherwise 23 Perform a gradient descent step on target j − Q(s j , a j ; θ) 2 24 Every Y steps, train evaluation network, decrease 25 Every ζ steps, copy Q toQ 26 end 27 end 28 return All actions at, all reject signals 2) State Space: The agent observes current status of the data center and incoming task, and the optimal action is determined based on current observation x. Current server observation describes available resources such as CPU and memory of requested VMs on server, whereas the observation of task u i ϕ (i.e., task i in job u ) is the parameter tuple { u i D CP U , u i D M EM , u i D V M , u i P rr, u i DDL} presented in Section III-C. Therefore, state s t at time t is a sequence of actions and observations, i.e., s t = x 1 , a 1 , x 2 , a 2 , ..., a t−1 , x t [15], and is input to the proposed deep Q-learning-based system. After taking an action, the RL agent receives an immediate reward from the environment, and transits into next state. Instead of using immediate reward as the value of stateaction pair, Q-learning agent updates the Q value as Equation 14 obeys Bellman equation 13, which is a weighted sum of the expected values of the rewards of all future steps starting from the current state, in its value iteration.
with learning rate η ∈ (0, 1] and discount factor γ ∈ [0, 1]. 3) Reward Function: The goal of H 2 O-Cloud is to maximize cost efficiency while maintaining QoS by taking a sequence of actions. Therefore, reward functions in four layers are modified differently to achieve different goals for training purposes. After running lots of experiments to verify the reward function hypothesis, this is the best combination we've found in our experiments.
In Layer 1, reward function R(layer = 1) is defined as: In Layer 2, reward function R(layer = 2) is defined as: In Layer 3, reward function R(layer = 3) is defined as: 100% < U r(t) −P rice(t, P wr n ttl (t)) P rice(t, P wr n ttl (t)) < 0.3 −P rice(t, P wr n ttl (t)) * 4 otherwise (17) In Layer 4, reward function R(layer = 4) is defined as: If the scheduled minute ∈ [ u i P rr − 1, u i P rr + 1]: The modification of reward function parameters is performed empirically based on our experimental results, and according to the following two principles: (i) Parameter modifications in the current layer highly impacts the performance of the following layers. We therefore manually select cases with potentially positive impacts, in order to minimize the chance of cases with negative effects on the following layers. (ii) The preferred range of U r(t) for reward function of each layer is selected according to practical limits and revised based on principle (i). For example, in Layer 4, the reward function takes a maximum reward value of +2 in case the utilization rate of a server in the exact minute ranges in (60%, 80%). Higher utilization rates provide higher resource effectiveness, and naturally leads to a positive reward feedback. However, during the training process of DQN, if the maximum reward is assigned based on utilization rate in the range (80%, 100%), the DQN will learn to assign as many tasks as possible to that range. That may result in high rejection rates and impact the overall performance of the framework. Hence, the maximum reward should be assigned to range lower than (80%, 100%) to encourage scheduling and prevent rejection at the same time.

V. H 2 O-CLOUD: THE DEEP Q-LEARNING AND SYSTEM CONTROL ALGORITHM
For a warehouse-scale CSP, the key target is to schedule a large volume of incoming tasks rapidly and effectively. The decomposition strategy of H 2 O-Cloud avoids a large DQN and guarantees on-the-fly decision-making capacity, as training four smaller DQNs converges much faster than training a huge one. In addition, there are four types of decision (i.e., those related to cluster, server, hour and minute(s)) that need to be made in the whole scheduling process. Different feature will cause different effects to DQN. A combination of features may lead to slower convergence of algorithm and degradation of decision quality. Finding the optimal reward function for a DQN is a difficult problem, especially when mixing different features in the decision-making process. Therefore, dedicating one DQN to each decision type not only provides reasonable runtime, but also further guarantees final scheduling decision quality.
Scheduling order is designed as cluster, server, hour, and minute for the following reasons: (i) It is obvious that the server farm and hour should be designated before choosing the exact server and minute(s). (ii) Scheduling efficiency will be higher if we first determine server farm and server, then select hour and minute(s). For example, assume an incoming task requests unfulfillable amount of resource, and it should be rejected at server layer by Admission Control. If we use the hour, minute(s), server farm, and server scheduling order, the task will be rejected at the last layer and the decision-making steps of the previous three layers are wasted. However, if we use the server farm, server, hour, and minute(s) scheduling order, the task will be rejected at the second layer, which is more efficient in terms of runtime. (iii) First choosing server, then selecting an optimal hour, yields a reward function (described in Section IV-C3) of DQN that is based on energy cost of one server. However, if we decide which hour to run an incoming task first, the reward function will be based on total energy cost of all servers. It will be hard to guarantee that each server is working in its optimal RUtR and energy cost range, although both scheduling orders are valid in task scheduling problem.

A. System Control Algorithm
System control algorithm in this work is shown in Algorithm 2, which implements the hierarchical structure described in Section IV-A. After initialization of the price model and environment of DRL, that includes the user workload model and cloud platform model, our four-layer decision-making processes are executed as shown in Algorithm 2. DQN () is the proposed Algorithm 1, which is modified for each layer, as described before. Decisions of tasks are recorded for the later calculation of energy-efficiency and cost-efficiency, etc.

Algorithm 2: Control Algorithm for H 2 O-Cloud
1 Initialize realistic price model P rice(t, P wr) 2 Initialize environment as env 3 Layer I: Initialize DQN (layer = 1) for cluster control 4 Run DQN (), store user request allocation Ac and reject signals Rejectc 5 Layer II: Initialize DQN (layer = 2) for server control 6 for all cluster do 7 Run DQN (cluster), store As and Rejects 8 end 9 Layer III: Initialize DQN (layer = 3) for hour control 10 for all server do 11 Run DQN (cluster, server), store At and Rejectt 12 end 13 Layer IV: Initialize DQN (layer = 4) for minute control 14 for all hour do 15 Run DQN (cluster, server, hour), store Am and Rejectm 16 end 17 Calculate final user request allocation matrix, i.e., U r for every server in every minute according to Ac, As, At, Am, Rejectc, Rejects, Rejectt and Rejectm 18 Calculate final energy consumption Energy, electric bill Cost, energy efficiency and cost efficiency Each layer takes output of preceding layers as input, and uses Algorithm 1 as the decision-making agent. The training method is used in all four layers, so there are four such training procedures for one batch of data. All four layers in H 2 O-Cloud utilize the same DQN hidden layer structure and deep Q-learning parameters, such as the learning rate, discount rate, etc. Algorithm 1 converges fast in all four layers, which guarantees the good performance, and shows robustness and portability of our algorithm. Figure 3 shows the structure of our H 2 O-Cloud, with an example. For layer 1, after DQN () is initialized, it takes available clusters and incoming tasks as input, and makes decision according to Algorithm 1. Action space in layer 1 of H 2 O-Cloud agent is the available clusters. Reward function is defined based on U r as described in Section IV-C3. For instance, after taking an action (e.g., cluster 20 as shown in Figure 3), a positive reward will be received when U r of cluster 20 is lower than 45%.
Cluster-level control is done for incoming tasks in Layer 1. Then the server-level control will proceed in Layer II. Initialization of layer 2 takes output of layer 1, for example cluster 20 , and information of task {D V M , D CP U , D M EM } as inputs. Each server in cluster 20 may hold a subset of VMs as described in Section III-B, therefore the action space of our H 2 O-Cloud agent in layer 2 is the available servers in the cluster, e.g., cluster 20 .
Output of layer 2 (e.g., server 501 ), layer 1 (e.g., cluster 20 ), and information of incoming task {DDL, D CP U , D M EM } will then be the input of layer 3. Next, layer 3 schedules the task into an hour (e.g. hour 5 in our example). The last decision, i.e., exactly which minute(s) to spend for the task execution, is made by the final layer, i.e., layer 4. This completes the decision procedures of the multi-layer part of our H 2 O-Cloud framework. For example, the complete decision in Figure 3 is represented as cluster 20 , server 501 , hour 5 , min 38 .
B. Training for Deep Q-Learning Algorithm in H 2 O-Cloud 1) Hybridity: DRL agents may produce invalid actions while training on-the-go, such as actions violating the softdeadline that is designated by end-user, or actions that make resource utilization of server explode, etc. In addition, DRL tends to make the same decision when current state stays the same, i.e., it will keep scheduling an incoming task into same place. Therefore, instead of waiting for the DRL agents to make a valid decision for current task by the -greedy mechanism, our hybrid method can provide a valuable action more efficiently. In other words, the hybrid method is a backup plan which will be triggered if DRL agent cannot handle the incoming task efficiently. Furthermore, incoming tasks must be scheduled in a short time after they have arrived. This is rather significant for a warehouse-scale CSP to provision resources and schedule tasks on-the-fly. Therefore, Algorithm 1 employs Round-Robin, a fast scheduling mechanism, in a hybrid fashion along with the DQN systems to schedule tasks into valid positions rapidly.
2) Experience Replay and Target Network: Q-learning updates are done in mini-batches of experience, which are selected randomly from the memory of stored transitions. Mini-batches training breaks the correlation of learning data and reduces the variance of update, which provides learning procedure with a higher efficiency. Target network is a separate neural network with the same structure as the evaluation network, which is used in DQN to generate target Q value in the Q-learning update. By introducing a delay between the time an update affects Q and the time an update affects the target, divergence and oscillations are eliminated [15].
3) Error Clipping: In this work, we also use error clipping [15] to further improve the stability of Q-learning algorithm. By clipping the error term from the update target j − Q(s j , a j ; θ) 2 into [−1, 1] interval, convergence of Algorithm 1 is further guaranteed.

VI. EXPERIMENTAL RESULTS
A. Experiment Setup 1) Baselines: The following three baselines are used to evaluate the efficiency of H 2 O-Cloud: • Round-Robin (RR): RR is commonly used as a baseline in cloud resource management [36], [37]. The CSP assigns each task in a circular order. If the current assignment violates SLA, the scheduler will try the following options until non violation. If no possible assignment, the task will be rejected as unfulfillable. In the experiment setup of this work, we have chosen RR as a baseline for its scalability and reasonable runtime.  [38], which uses a DRL-based two-stage Resource Provisioning and Task Scheduling (RP-TS) processor to schedule tasks into hours without fine-grained scheduling and hard-deadlines only. Three user workload scenarios (i.e., user-server relations) are used (Figure 1). They are as follows: #user #server, #user < #server, #user #server, which considers all the possible realistic scenarios. We adopt the realistic price data from [39], [40] to calculate the energy cost after scheduling, where it is assumed that the utility company announces the pricing 24 hours in advance. Google clusterusage traces with 12.5k servers and timing information [41] are used in this work.
2) Indicators: Comparisons are based on five indicators: • Energy Cost Efficiency (ECE): Units of CPU that can be executed by using one unit of energy cost. • Energy Efficiency (EE): Units of CPU that can be executed by using one unit of energy. • Turn-off Rate (TFR): Servers will be turned off when no task is scheduled into it in one hour. TFR is introduced to visualize the sparse usage of servers. • Util-opt Rate (UOR): Util-opt rate indicates how may working servers are running in their optimal status. Compared to TFR, which shows sparse usage of servers, UOR shows resource utilization status of working servers as described in Section I. • ddl-Violation Rate (ddlVR): Soft-deadline violation rate.
• Reward Rate: A reward will be given to the scheduler in training process when priority requirement is fulfilled. Reward Rate indicates how often the scheduler receives the priority fulfillment reward, i.e., it represents how often the user-designated task priority requirement can be fulfilled. The data details for the low, medium and high variance scenarios, shown in Figure 1, Figure 4, Figure 5, Table I and  Table II 3) Experiment Scale: Comparisons are performed based on the following three scales: • Small-Scale: 600 servers in total, clustered into 2 server clusters, corresponding to #user #server user-server relation. • Medium-Scale: 1, 080 servers clustered into 3 server clusters, corresponding to #user < #server. • Large-Scale: 12, 500 servers clustered into 5 server clusters, corresponding to #user #server. DQN structure in both HDRL and H 2 O-Cloud uses a twohidden-layer neural network with ten neurons in each hidden layer. According to our experiments, hierarchical strategy of HDRL and H 2 O-Cloud makes it less sensitive to DQN structure changes, as long as the number of hidden layers and the number of neurons lie in the range of [2,5] and [5,50], respectively. For deep Q-learning, learning rate η = 0.1, discount factor γ = 0.9, and is decreased from 0.9 by 0.05 in each learning iteration, memory size ∆ = 500, replace target network step ζ = 300, train evaluation network step Y = 20, 5, 10, 10 in Layer 1 to 4, respectively. All parameters are initially chosen from a commonly used range [15], [42] and tuned based on the experiments in order to provide relatively optimal performances.
To show the effectiveness of our framework more clearly, the following comparisons are presented in the following: Our HDRL and H 2 O-Cloud vs. RR (Section VI-B), HDRL and H 2 O-Cloud vs. DRL-Cloud (Section VI-C), and H 2 O-Cloud vs. HDRL (Section VI-D).

B. H 2 O-Cloud and HDRL vs. RR
Comparisons of H 2 O-Cloud and HDRL with baseline RR in low variance and high variance scenarios are shown in Table I, with RR as the reference (base). The normalization process uses the highest value in each column as the reference. Comparison in the medium variance scenario is shown in Figure 4. Compared to RR, H 2 O-Cloud and HDRL significantly outperform in terms of ECE, EE, TFR, UOR and ddlVR, which shows that H 2 O-Cloud and HDRL achieve higher energy and cost efficiency while maintaining QoS.
Based on admission control policy, if a task requests unfulfillable amount of resources, then this task should be rejected immediately. All the baselines and H 2 O-Cloud follow the same admission control policy and the implementation codes are strictly the same. RR completes admission control in one step, while HDRL and H 2 O-Cloud perform it hierarchically. These two approaches are fundamentally very similar. Therefore, the results are not biased by the admission control. Same admission policy means that the rejection rates of difference policies are very similar. In our experiment setup, RR would not reject tasks as they do not turn off servers. The rejection rates of both HDRL and H 2 O-Cloud range between 0% and 0.1% in our various setup cases. RR provides zero task rejection and results in much higher energy consumption in return. HDRL and H 2 O-Cloud balance between energy cost efficiency and task rejection rate by scheduling tasks and turning off servers intelligently while maintaining QoS. It should be noted that HDRL and H 2 O-Cloud can be modified to achieve zero task rejection while outperforming RR in terms of energy efficiency if we put rejection rate as top priority.
As we can see in Table I, H 2 O-Cloud and HDRL consistently outperform RR in all scenarios in terms of normalized ECE, normalized EE, UOR, TFR and ddlVR. H 2 O-Cloud and HDRL result in significant improvement because they are both aware of historical decisions and current environment status. In addition, utilization of user request information such as task priority and task deadline lead to low soft-deadline violation, which improves quality of service. High turn-off rate shows the sparse usage of DCs, which further improves resource efficiency in working servers.
According to our experiments in Table I

C. H 2 O-Cloud and HDRL vs. DRL-Cloud
DRL-Cloud [38] comprehensively solves the energy cost reduction problem for large-scale CSPs by using a two-stage RP-TS processor. The first stage of RP-TS allocates a task to server farm and determines the timeslot to start processing the task, then the second stage chooses the exact server to run the task. The difference between H 2 O-Cloud and DRL-Cloud can be expressed in five aspects: 1) Fine-grained Task Scheduling: H 2 O-Cloud realizes a fine-grained scheduling by determining the exact minute(s) to run task, whereas in case of DRL-cloud, the task scheduling level of granularity is hourly. Fine-grained scheduling leads to better energy cost efficiency and energy efficiency.
2) Hybridity: Both H 2 O-Cloud and DRL-Cloud rely on DRL decision-making core to schedule tasks, however, H 2 O-Cloud is embedded with a back-up hybrid mechanism, which functions whenever DRL cannot make right decisions in some corner cases.
3) Task Recycling Mechanism: H 2 O-Cloud defines task deadlines as soft, which means tasks can be recycled and rescheduled when the first scheduled processing time failed to meet the deadline. DRL-Cloud defines task deadlines as hard instead, and rejects tasks immediately when the hard-deadline is violated. The soft-deadline, task recycling mechanism, and hybridity of H 2 O-Cloud yield lower task rejection rate. 4) QoS-Awareness: H 2 O-Cloud retrieves more user information to construct the user workload model, one of the important new parameters is priority. Priority defines the task importance. If the scheduled processing time range matches the priority, a reward will be given to the scheduling system as a user feedback (which is defined in Equation 19). H 2 O-Cloud then uses the feedback to tune the scheduling system further in Layer 4. 5) Professionalized Hierarchical Structure: H 2 O-Cloud utilizes a more professionalized structure to accomplish the decision-making process hierarchically, i.e., one DQN per decision stage, while DRL-Cloud uses two DQNs for whole RP-TS process. Training each DQN individually provides it with specialized decision-making ability, which allows each DQN to concentrate on a specific decision step, which yields better scheduling decisions.
The experiment results of comparison between H 2 O-Cloud, HDRL and DRL-Cloud are shown in Figure 5 and Table II. ECE and EE are normalized regarding highest values in each scenario. Compared to DRL-Cloud, H 2 O-Cloud and HDRL achieve higher ECE and Reward Rate in all scenarios as shown in Table II and Figure 5 (a) and (c), respectively. Higher scheduling precision (fine-grained scheduling) and professionalized hierarchical structure contribute the most to this result. H 2 O-Cloud and HDRL outperform DRL-Cloud regarding the Reward Rate because both of which are QoS-aware. Utilizing user feedback and introducing task priority help the scheduling system generate decisions that match the user preference as much as possible. As we can see in Figure 5 (b) and Table  II O-Cloud is lower than HDRL), whereas the the rejection rate of DRL-Cloud ranges between 0.01% to 1%. Lower rejection rate of H 2 O-Cloud is achieved by hybridity and task recycling mechanism as described in Section VI-C3.

D. H 2 O-Cloud vs. HDRL
The rejection rates of both HDRL and H 2 O-Cloud range between 0% and 0.1% in our various setup cases. It is noted that HDRL's goal in this work is to maximize energy cost efficiency, hence it learns to shut down idle servers so that working servers achieve good utilization rate. This means HDRL's rejection rate is higher than that of H 2 O-Cloud (details appear in Section IV-C).
H 2 O-Cloud outperforms HDRL in large-scale configuration and high variance scenario in terms of resource efficiency metrics, such as normalized ECE and normalized EE, and ddlVR. The reasons are twofold: i) For small-scale and medium-scale configurations, action space is much smaller than that of the large-scale configuration. This enables DRL agent to make intelligent decisions by fully learning the historical decisions and current status of environment. Note that in this case, the backup mechanism of RR in H 2 O-Cloud would not help with resource efficiency. HDRL outperforms H 2 O-Cloud in small-scale in terms of EE and ECE in Figure 5 because of the uncertainties in training. ii) H 2 O-Cloud consistently outperforms baselines in high variance scenario because the training of DRL agent is on-the-go and may introduce delay between changing environment and DQN. While environment is changing too fast for the DRL agent to keep up, decision  VII. CONCLUSION In this work, H 2 O-Cloud, a hierarchical and hybrid online cloud resource management and task scheduling framework, is presented to improve resource efficiency for warehouse-scale cloud service provider, while maintaining quality of service. By utilizing hierarchy, and hybridity in system modeling and optimization, H 2 O-Cloud achieves high performance in resource utilization, while maintaining robustness of framework. H 2 O-Cloud improves resource efficiency and quality of service remarkably, when compared to the baseline approaches, namely Round-Robin and DRL-Cloud. The experiment results confirm that the hierarchical structure with hybrid mechanism is effective and efficient in resource management and task scheduling for warehouse-scale cloud service providers. H 2 O-Cloud outperforms baseline HDRL (Hierarchical DRL) in large-scale configuration and high variance scenario in terms of energy cost efficiency, energy efficiency, and soft-deadline violation rate. This result further shows the improvements contributed by hybridity on top of the hierarchical DRL. Fellowship. His research interests include the theoretical foundations of cyber-physical systems, the control of complex time-varying interdependent networks, the modeling and analysis of biological systems and swarms, new control algorithms for dynamical systems exhibiting multi-fractal characteristics, modeling biological / molecular communication, the development of fractal mean field games to model and analyze biological, social and technological system-of-systems, performance analysis and design methodologies for manycore systems.