Report

Multi-dimensional SLA-based Resource Allocation for Multi-tier Cloud Computing Systems Hadi Goudarzi and Massoud Pedram University of Southern California, Los Angeles in IEEE Cloud 2011 (The 4th International Conference on Cloud Computing) Agenda • • • • • • • Introduction System model Problem formulation An upper-bound on the total profit Profit maximization solution Simulation results Conclusion 2 Introduction • Modern internet applications are complex software implemented on multi-tier architectures. – Each tier provides a defined service to the next tiers and uses services from the previous tiers. • The problem of resource allocation for multi-tier applications is harder than that for single-tier applications – tiers are not homogenous – a performance bottleneck in one tier can decrease the overall profit, even if the other tiers have acceptable service quality. 3 Introduction (cont’d) • The IT infrastructure provided by the datacenter owners/operators must meet various SLAs established with the clients. • The problem of optimal resource provisioning is challenging due to the diversity present in the client applications being hosted and the SLAs. – reduce the cost incurred on the datacenter operators – meet the clients’ SLAs. 4 Introduction (cont’d) • This paper focus on the SLA based resource allocation in the cloud computing system. • Two types of SLA contracts: – For Gold SLA class: response time is guaranteed and if this constraint is violated, the cloud provider pays a penalty. – For the Bronze SLA class, each client has a defined utility function based on its response time. 5 Introduction (cont’d) • In this paper, we assume that servers are characterized by their maximum capacity in three dimensions: – processing power – memory usage – communication bandwidth • Objective – An SLA-based multi-dimensional resource allocation scheme for the multi-tier services in a cloud computing system to optimize the total expected profit. 6 System model vi3 ui1 1 u 3 wi6 vi4 i2 4 2 vi5 6 wi7 7 5 for each server j: 7 Problem formulation Profit Total allocated resource 1 Memory If tij is not zero, the value of ztij is set to one, otherwise the value of ztij is zero. 8 Average response time estimation • We consider generalized processor sharing at each queue. • Based on the queuing theory, the output of each queue with this characteristic has an exponential distribution with a mean value of 1/(-). – : average service rate, : average arrival rate Average response time in tier t : Average response time : 9 Profit • Utility function – Gold SLA: – Bronze SLA: Ubi(Ri) is a nonincreasing function of the average response time. • Cost (power consumption) • Profit in a duration Te: 10 Baseline solution • Optimization parameters: • Iterative method (IM) [12][13] – fix the resource shares and optimize the task distribution rates – and then fix the distribution rates and optimize the resource shares 11 Profit upper-bound problem statement • Release some constraints and fix tij This problem can be solved using KKT condition. – Find the best case of assigning the client’s requests to the servers tij . – solve the problem for each client independently and sum up the results of best profits for all clients 12 Profit maximization solution 1. An initial solution based on the solution given for the profit upper bound problem is generated. 2. Distribution rates are fixed and resource sharing is improved by a local optimization step. 3. Finally a resource consolidation technique, inspired by the force-directed scheduling, is applied to consolidate resources, determine the active (ON) servers and further optimize the resource assignment. 13 Initial solution • A greedy technique to rank the clients and the application tiers for each client is used • to determine the order of resource assignment processing in our constructive approach. • For each client, the following equation is used as its ranking metric: • For the selected client, tiers are ordered using a similar metric: 14 Initial solution (cont’d) • Based on the solution given for the profit upper bound problem, determine the ij and tij for each client. Replaced by 15 Force-directed Resource Assignment (FRA) • Resource Consolidation using Force-Directed Search • A client that has the highest force difference toward a new server is picked and if the required server is available, the load replacement is done. • The definition of force is based on the partial profit gained from allocating each portion of the clients’ request in a specific tier to a server with specific type. Gold: Bronze: 16 Force-directed Resource Assignment (FRA) 17 Force-directed Resource Assignment (FRA) • After this replacement, forces are updated and the new maximum force differential client-to-server assignment is made. • This algorithm continues until there are no positive force differentials for any clients. • Limit the number of tries in the algorithm and avoid loops and lockouts 18 Simulations • Consider 10 to 100 clients – For each client the processing power and memory capacity requirements are set with random variables. • Ten different application tiers are considered. • The number of application tiers for each client is selected randomly to be between 3 and 5. • The probabilities of going forward or backward – average of 80% going forward and 20% backward for each tier. • Service times for clients with different application tiers are also modeled with random variables. • Gold or Bronze SLA class with probability of 50% 19 Simulations (cont’d) • The first scenario (low server to client ratio) – The average number of servers is 5n where n denotes the number of clients. • The second scenario (high server to client ratio) – The average number of servers is set to 10n. 20 Simulation results 21 Simulation results (cont’d) • An example of Resource Consolidation Improvement in case of a bad initial solution. 22 Simulation results (cont’d) • Computation overhead 23 Simulation results (cont’d) • Average utilization factor of the servers 24 Conclusion • A closed-form formula for calculating the average response time of a client’s request for multi-tier applications. • A unified framework for handling both strong (Gold class) and weak (Bronze class) SLAs. • A provable upper bound on the total profit in the system for given clients, resources and SLAs. • A multi-dimensional resource allocation scheme to consider communication resources for multi-tier applications that incur large inter-server communications. 25 Comments • A well problem formulation. • The upper bound is too loose. • Computation overhead is high – static dispatcher in this paper • We can consider the effect of virtualization – A host server has multiple application. • Another issue – How to design a dynamic dispatcher according to request arrival and server condition ? 26