Abstract

This paper reviews certain papers on resource management in cloud computing. Algorithms and frameworks in resource allocation, resource calculation, resource provisioning, resource discovery and selection are described and summarized.

1Introduction

Resource Management is critical in cloud computing. With improper resource management, applications might experience network congestion, long time wait, CPU waist, overused CPU and memory, and security problems. To maximized cloud computing infrastructure utilization and minimize total cost of both the cloud computing infrastructure and running applications, resources need to be managed properly.

In this report, certain papers on resource management in cloud computing are reviewed. Four types of resource management, resource allocation, resource calculation, resource provisioning and resource discovery and selection, are described.

2Problems of Resource Management

In cloud computing, the underlying large-scale computing infrastructure is often heterogeneous, not only because it’s not economic and reliable to procure all the servers, network devices and power supply devices in one size and one time, but because different application requires different computer hardware, e.g. workflow extensive computing might need standard and cheep hardware; scientific computing might need specific hardware other than CPU like GPU or ASIC.

There are kinds of resources in the large-scale computing infrastructure need to be managed, CPU load, network bandwidth, disk quota, and even type of operating systems. To provide better quality of service, resources are provisioned to the users or applications, via load balancing mechanism, high availability mechanism and security and authority mechanism. To maximize cloud utilization, the capacity of application requirements shall be calculated so that minimal cloud computing infrastructure devices shall be procured and maintained. Given access to the cloud computing infrastructure, applications shall allocate proper resources to perform the computation with time cost and infrastructure cost minimized. Proper resources shall be selected for specific applications. In other words, resource management in cloud computing is categorized into four types, resource allocation, resource calculation, resource provisioning and resource discovery and selection.

3Resource Management Review

Distributed resource management has become a research topic since (Injong 1995), in which resource allocation in distributed systems are formulated as three kinds: the dining philosophers problem, the drinking philosophers problem and the dynamic resource allocation problem.

3.1Resource Allocation

In a distributed computing environment, e.g. a distributed cloud application based on the CORBA infrastructure, resource allocation (Carter, St. Louis & Andert 1998)can help with issues of component migration, scheduling, and load balancing across dynamic computational resources. In such an environment, applications run on collections of interconnected computers, also known as networks of workstations (NOW).  In this work, heterogeneous CORBA job migration is presented, and a prioritized set of job queues based on the job migration is demonstrated. To provide fault tolerance, application checkpoints are described, that failure of the system is detected automatically and restarted without loss of client jobs.#p#分頁標題#e#

An efficient online algorithm for co-allocating resources and advanced resource reservations is presented in (Claris, George & Khaled 2009). The algorithm uses specific data structures to store availability of resources. Efficient range searches are designed to identify all available resources. The overall complexity for a successful scheduling attempt is, while  is the spatial size of the reservation, N is the amount of servers, Q is the amount of partitions of the system.

The Service Oriented Architecture (SOA) and virtualization of physical resources combination has emerged the Service Oriented Infrastructure (SOI), which provide flexible solution for on demand component accessing. The problem of determining the optimum resource allocation for Virtual Machines is addressed in work (Danilo et al. 2009), in which the resource allocation problem is modeled non-linearly which is able to be solved optimally.

For asynchronous distributed environment, two algorithms, RBA* and OBA, are introduced in (Hegazy & Ravindran 2002)to maximize application QoS and minimize deadline missing ratio. Both algorithms build distributed application models based on Jenson benefit functions to model timely resource requirements in the distributed applications. Adaptation functions are proposed to predict resource requirements in the near future. Application adaptation models are built to accommodate dynamic application replication for sharing increased workload. The underlying network model is built as a switched real-time Ethernet network. The difference of the two algorithms is that RBA* allocates resources by analyzing the process response times of each application, while OBA makes allocation decisions based on the processor workloads. The time cost of RBA* is about, n is the size of the task set; the time cost of OBA is relatively lower, about, with the same meaning of n as RBA*. However, the experiments show that RBA* provides better QoS with less deadline missing.

A multiple degree load balancing resource allocation scheme is introduced in (Lee 2004). Each of load balance degree maps to each resource management configuration and reduces data traffic among distributed components. A High Level Architecture (HLA) bridge middleware environment is also introduced for data bridging among multiple federations.

An autonomous decentralized resource allocation scheme is presented in (Masuishi et al. 2005). A system architecture utilizing the autonomous decentralized resource allocation scheme is designed, in which there is a subsystem that has a production server to process request and a coordination server to adapt resources to load changes. Three architectures, centralized control architecture, autonomous decentralized architecture with independent adaptation and autonomous decentralized architecture with coordinated adaptation, are compared and simulated in this paper. The results show that autonomous decentralized resource allocation is better for server availability and the tracking accuracy for the autonomous decentralized resource allocation with coordinated adaptation is comparable with the centralized control architecture.#p#分頁標題#e#

The problem of apportioning multiple resources to satisfy a single QoS dimension is addressed in (Rajkumar et al. 1998). This paper first introduces Q-RAM, the QoS-based resource allocation model, and then discusses allocation of a single resource with multiple QoS dimensions. After the discussion of multiple QoS dimensions, the paper analyzes the allocation problem of multiple resources with single QoS dimension. The paper shows that the problem of finding optimal resource allocation is NP-hard.  However, a simple polynomial algorithm based on computational geometry helps find a solution very near to the optimal solution of the resource allocation problem.

A decentralized market-based approach allocating resources in a heterogeneous overlay network is presented in (Smith et al. 2008). In this paper, a resource allocation strategy of the overlay network resources is defined to assign traffic dynamically based on the current utilization, thus enabling the system to accommodate fluctuating network demands. A mathematical model of the resource allocation environment is presented and the problem is regarded as a constrained optimization problem.

A resource allocation evaluation framework in Application Layer Networks is presented in (Streitberger et al. 2006). A pyramid of metrics is defined to evaluate resource allocation methods. Two layers of metrics are defined, technical parameters and economic parameters. Technical parameters are technical metrics in the system, such as Discovery Time, Message Latency, Message Size, Service Provisioning Time, and Negotiation Time. Economic parameters are, in the upper layer of the pyramid, derived from technical parameters.

3.2Resource Calculation

In the Software as a Service (SaaS) paradigm, the cost of deployment, customization and hosting of applications can be reduced by sharing with multiple tenants. However, to maximize user experience and minimize the cost, the service provider has to calculate how the resources are allocated. In the work of (Kwok & Mohindra 2008), the resource calculation is addressed and solutions are provided. A multi-tenant placement model is given to place multiple applications in a set of servers.

For satellite networks, to maximize the use of satellite is important. Certain model (Petraki et al. 2007)has been built for MF-TDMA satellite network to help provide minimum timeslots but still guarantee the QoS required in the network. Three algorithms, SIT side algorithm, NCS side algorithm and multiple subset sum algorithm, are given in this work.

3.3Resource Provisioning

Cloud, such as Amazon EC2 and S3, offers storage and computational resources that can be used on demand for a fee. Different usages of the resources in such a cloud have different impact on the final cost. The paper (Deelman et al. 2008)addresses this problem to minimize the total cost of cloud utilization. The paper first introduces a scientific application Montage of its computational workflow; then it presents the computational models and cost models (Amazon EC2); after that, simulations are conducted based on the models. Results show that for a data-intensive application with a small computational granularity, the storage costs are insignificant compared to CPU costs.#p#分頁標題#e#

In Service Oriented Architecture (SOA), a set of low-level atomic services are composite to form the high-level services, in which capacity planning and resource provisioning is important. In paper (Chun et al. 2008), a black-box method for estimating service requests demanded CPU resource is presented. The method is based on linear regression between the observed requests and resource utilization. The service composition relationship discovery is also introduced. The discovered service composition relationship can further be used to improve the CPU demand estimation quality.

A absolute delay guaranteed resource provision technique for real-time applications is presented in (Chunfeng et al. 2003). Runtime network workload uneven distribution factors are considered to configure resources provided. A resource provision model for real-time applications is built, in which the end-to-end worst-case delay for real-time traffic, the bandwidth constraint, the delay constraint, and the admission probability are formulated. The results show that the overall resource utilization by admission probability is higher than the uniform UBAC method.

A general complex resource provisioning (CRP) model and the major requirements to the authorization service infrastructure (AuthZ) to support multi-domain CRP are defined in (Demchenko, Gommans & de Laat 2007). Two main issues are focused, AuthZ session support and policy expression for CRP models. The eXtensible Access Control Markup Language and its special profiles to specify complex resources access control policies are described. A XML based AuthZ ticket format is proposed to support extended AuthZ session context. Specific functionality are added to the gLite Java Authorization Framework (gJAF) to handle dynamic security context, e.g. the AuthZ sessions.

An application-level BPEL workflow on demand resource provisioning is introduced in (Dornemann, Juhnke & Freisleben 2009), in which BPEL service calls are scheduled according to the target host loads. The solution schedules workflow steps to underutilized servers and allocates extra hosts utilizing the Cloud computing infrastructures at service load peaks. The BPEL standard is not required to modify in this approach. The Cloud computing infrastructure utilized in this paper is Amazon’s Elastic Compute Cloud (EC2). The BPEL implementation is ActiveBPEL engine.

A Universal Factory Service (UFS) that provides dynamic resource deployment and resource broker named the Door service, is introduced in (Eun-Kyu et al. 2005).

Autonomous Decentralized Community System (ADCS) is proposed to adapt transportation services (Filali, Hafid & Gendreau 2008), in which global mobile communication technologies are used and service condition changes dynamically. Based on ADCS, resources are shared among transportation neighbors that each node provides resources to other node requests. Autonomous collaboration technology is proposed to satisfy the cooperation among computational nodes. By evaluation of a taxi dispatching application, effectiveness of ADCS is approved.#p#分頁標題#e#

In large-scale scientific workflows, three techniques for resource provisioning, advance reservations, multi-level scheduling, and infrastructure as a service (IaaS), are proposed in (Juve & Deelman 2008). Advance reservation is achieved by users requesting slots from batch schedulers that specify the number of resources to reserve and the duration of the reservation and the beginning and the end of the advance reservation. Rather than batch scheduler based advance reservations, another advance reservation is to use probabilistic advance reservations in which reservations are made based on statistical estimates of queue times. In multi-level scheduling, the allocation of resources and the management of application tasks are separated in which application tasks are submitted using standard mechanisms, but the node managers are in charge of contacting an external resource manager. Infrastructure as a service (IaaS) enables users to run applications on remote servers by configuring and launching virtual machines on these servers. The virtual machines can be allocated with certain amounts of CPU, disk space and memory, with certain type of operating systems, computing frameworks and application software.

A dynamic resource provisioning framework for dynamically provisioning virtual machines is introduced in (Kusic et al. 2009)to reduce the power consumption in large data centers, by sharing servers among multiple online services utilizing virtualization technology, achieving higher server utilization and energy efficiency while still maintain desired quality of services. A LLC framework is implemented and validated. The switching costs and the risk notion are explicitly encoded in the optimization problem. The experiments show that the LLC framework can save 22% on average in power consumption cost.

3.4Resource Discovery and Selection

There are resource discovery mechanisms such as self-announcer and resource broker. Self-announcer (Bouyer, Mohebi & Abdullah 2009)method is based on machine learning theory. A broker-based approach (Malarvizhi & Uthariaraj 2008)is built based on resource brokers.

Resource selection methods, by manual and by autonomous approaches, are enumerated. In (Malarvizhi & Uthariaraj 2008), local resource managers are implemented to help manage and schedule the resources. The detailed interaction during the resource selection is presented in this paper.

With regard to virtualization technology trends, Dynamic Virtual Infrastructures (DVI) requires dynamic adaptation to the changing user requirements. The Virtual Appliance (VA), the resources such as the guest operating system and applications hosted on the DVI, are deployed on computers across the network. To adapt the changing user requirements, proper VA nodes shall be selected to do the computation. In paper (Bergua et al. 2009), a function for efficient node selection is presented. Five metrics, compute performance, memory capacity, storage capacity, network cost and transfer performance are modeled into the algorithm and certain steps are performed to select optimum nodes.#p#分頁標題#e#

Large-scale computing infrastructures are often comprised of heterogeneous hardware and software resources. A fully decentralized resource selection algorithm, by which resources are autonomously selected when the attributes match a query, is presented in (Costa et al. 2009). A system model is described that each node in the system is characterized by a set of (attribute, value) pairs like CPU, bandwidth and disk quota. A resource discovery protocol, including the overlay network topology and query routing, is also defined.

A online automatic resource selection approach based on control theory is presented in (Hao, Sorensen & Nazir 2009), in which a utility-based learning and tuning algorithm is used to enable the automatic resource tuning and selection. A middleware is designed to listen to the application execution performance report and re-configure execution environment intelligently to meet the performance requirements. Execution Satisfaction Degree (ESD) is defined to measure the satisfaction of application execution QoS. Applications need to define the ESD function to represent execution satisfaction. Furthermore, applications are required to be adaptive, that they are able to add or release resources during the execution at any time. Application Agent (AA), an application-level middleware interact with the underlying computing infrastructure to transparently provide the execution environment, is extended to provide resources autonomously. The theory of the utility-based policy is to find the utility to each candidate resource of the application. The utility is defined as accumulative contribution that a host made to the application. AA calculates the utility by the reported ESDs and the provided hosts handled. AA uses the ordered utility values to operate on hosts to make the ESD approaching 1.0. AA keeps updating the utility values iteratively and manages the resources as the result.

A empirical prediction model that generates an appropriate resource allocation specification based on a DAG structured workflow application is given in (Huang, Casanova & Chien 2007). The resource allocation specification includes the number of resources, the range of resources clock rates and network bandwidth. The model, using an optional utility function, with the application DAG structure kept in mind, trades off cost and performance. A resource model is also built to evaluate the application model since it’s too expensive and time consuming to do experiments in a large-scale distributed computing environment. The resource environment is assumed to be composed of reservation based resources and the middleware layer can acquire dedicated resources on behalf of the user. Compute resources are assumed to have identical processor architectures and their speed depends only on their clock rates. Applications are simulated based on performance models of the tasks. The resource selection system returns the user with a resource collection (RC) or a set of hosts on which the user can execute the desired application. The “best” RC is defined as one that minimizes application turn-around time. Two parameters of RC are given, number of hosts and coefficient of variance of host clock rates. Results show than using the prediction model is far more cost effective while achieving better performance.#p#分頁標題#e#

The notion of accessibility to evaluate both availability and performance is introduced in (Kim, Chandra & Weissman 2008). A system model is provided that nodes are separated into two types, compute nodes and data nodes. Data nodes store data objects required in the computation; compute nodes execute actual application jobs. Both compute and data nodes are connected in an overlay structure. The nodes are decentralized that any node in the system can submit a job. A job is defined as a unit of work that does the computation on objects. To allocate a job, there is a submission node named initiator, which selects compute node for candidates. Certain resource discovery algorithms are used to determine the set of candidate nodes. After a node is selected by the initiator, the job is transferred to the selected node, named worker. The worker then download data objects required by the job and then perform the computation. When the job is done, the result is returned from the worker to the initiator. An accessibility-based ranking function is used to order the node candidates. The expected data download time is used as a metric to quantify accessibility. Accessibility is estimated in two approaches, self estimation and neighbor estimation. By self estimation, transfer latency to the server and download speed of the server are used to assess the accessibility to a data object. By neighbor estimation, neighbor information is used to correlate a neighbor’s download experience to the node’s experience. Results show that the self and neighbor estimation-based selections are 52% and 70% more efficient respectively than latency-based selection.

4Conclusion

In this report, certain papers on resource management in cloud computing is reviewed. Certain algorithms and frameworks in resource allocation, resource calculation, resource provisioning and resource discovery and selection are described.
 

Reference

Bergua, B, Garcia, F, Rodriguez, A & Carretero, J 2009, 'Resource selection for fast large-scale Virtual Appliances Propagation', in Computers and Communications, 2009. ISCC 2009. IEEE Symposium on, pp. 824-9.

Bouyer, A, Mohebi, E & Abdullah, AH 2009, 'Using Self-Announcer Approach for Resource Availability Detection in Grid Environment', in Computing in the Global Information Technology, 2009. ICCGI '09. Fourth International Multi-Conference on, pp. 151-6.

Carter, RL, St. Louis, D & Andert, EP, Jr. 1998, 'Resource allocation in a distributed computing environment', in Digital Avionics Systems Conference, 1998. Proceedings., 17th DASC. The AIAA/IEEE/SAE, vol. 1, pp. C32/1-C/8 vol.1.

Chun, Z, Chang, RN, Chang-Shing, P, So, E, Chunqiang, T & Tao, T 2008, 'Leveraging Service Composition Relationship to Improve CPU Demand Estimation in SOA Environments', in Services Computing, 2008. SCC '08. IEEE International Conference on, vol. 1, pp. 317-24.#p#分頁標題#e#

Chunfeng, W, Xiuzhong, C, Ru, L, Xiaolu, H & Zhongcheng, L 2003, 'Effective resource provision for real-time applications in static-priority scheduling networks', in Communication Technology Proceedings, 2003. ICCT 2003. International Conference on, vol. 2, pp. 1547-52 vol.2.

Claris, C, George, NR & Khaled, H 2009, 'Resource co-allocation for large-scale distributed environments', paper presented to Proceedings of the 18th ACM international symposium on High performance distributed computing, Garching, Germany.

Costa, P, Napper, J, Pierre, G & van Steen, M 2009, 'Autonomous Resource Selection for Decentralized Utility Computing', in Distributed Computing Systems, 2009. ICDCS '09. 29th IEEE International Conference on, pp. 561-70.

Danilo, A, Raffaela, M, Marco, T & Li, Z 2009, 'Run-time resource management in SOA virtualized environments', paper presented to Proceedings of the 1st international workshop on Quality of service-oriented software systems, Amsterdam, The Netherlands.

Deelman, E, Singh, G, Livny, M, Berriman, B & Good, J 2008, 'The cost of doing science on the cloud: The Montage example', in High Performance Computing, Networking, Storage and Analysis, 2008. SC 2008. International Conference for, pp. 1-12.

Demchenko, Y, Gommans, L & de Laat, C 2007, 'Using SAML and XACML for Complex Resource Provisioning in Grid Based Applications', in Policies for Distributed Systems and Networks, 2007. POLICY '07. Eighth IEEE International Workshop on, pp. 183-7.

Dornemann, T, Juhnke, E & Freisleben, B 2009, 'On-Demand Resource Provisioning for BPEL Workflows Using Amazon's Elastic Compute Cloud', in Cluster Computing and the Grid, 2009. CCGRID '09. 9th IEEE/ACM International Symposium on, pp. 140-7.

Eun-Kyu, B, Jae-Wan, J, Wook, J & Jin-Soo, K 2005, 'A dynamic grid services deployment mechanism for on-demand resource provisioning', in Cluster Computing and the Grid, 2005. CCGrid 2005. IEEE International Symposium on, vol. 2, pp. 863-70 Vol. 2.

Filali, A, Hafid, AS & Gendreau, M 2008, 'Adaptive Resources Provisioning for Grid Applications and Services', in Communications, 2008. ICC '08. IEEE International Conference on, pp. 186-91.

Hao, L, Sorensen, SA & Nazir, A 2009, 'On-line automatic resource selection in distributed computing', in Cluster Computing and Workshops, 2009. CLUSTER '09. IEEE International Conference on, pp. 1-9.

Hegazy, T & Ravindran, B 2002, 'Using application benefit for proactive resource allocation in asynchronous real-time distributed systems', Computers, IEEE Transactions on, vol. 51, no. 8, pp. 945-62.

Huang, R, Casanova, H & Chien, AA 2007, 'Automatic resource specification generation for resource selection', in Supercomputing, 2007. SC '07. Proceedings of the 2007 ACM/IEEE Conference on, pp. 1-11.#p#分頁標題#e#

Injong, R 1995, 'A fast distributed modular algorithm for resource allocation', in Distributed Computing Systems, 1995., Proceedings of the 15th International Conference on, pp. 161-8.

Juve, G & Deelman, E 2008, 'Resource Provisioning Options for Large-Scale Scientific Workflows', in eScience, 2008. eScience '08. IEEE Fourth International Conference on, pp. 608-13.

Kim, J, Chandra, A & Weissman, JB 2008, 'Accessibility-Based Resource Selection in Loosely-Coupled Distributed Systems', in Distributed Computing Systems, 2008. ICDCS '08. The 28th International Conference on, pp. 777-84.

Kusic, D, Kephart, J, Hanson, J, Kandasamy, N & Jiang, G 2009, 'Power and performance management of virtualized computing environments via lookahead control', Cluster Computing, vol. 12, no. 1, pp. 1-15.

Kwok, T & Mohindra, A 2008, 'Resource Calculations with Constraints, and Placement of Tenants and Instances for Multi-tenant SaaS Applications', in A Bouguettaya, I Krueger & T Margaria (eds), 6th International Conference on Service-Oriented Computing, Sydney, AUSTRALIA, pp. 633-48.

Lee, JS 2004, 'Data Management with Load Balancing in Distributed Computing ', inComputational Science and Its Applications – ICCSA, pp. 621-9.

Malarvizhi, N & Uthariaraj, VR 2008, 'A Broker-Based Approach to Resource Discovery and Selection in Grid Environments', in Computer and Electrical Engineering, 2008. ICCEE 2008. International Conference on, pp. 322-6.

Masuishi, T, Kuriyama, H, Ooki, Y & Mori, K 2005, 'Autonomous decentralized resource allocation for tracking dynamic load change', in Autonomous Decentralized Systems, 2005. ISADS 2005. Proceedings, pp. 277-83.

Petraki, DK, Anastasopoulos, MP, Panagopoulos, AD & Cottis, PG 2007, 'Dynamic Resource Calculation Algorithm in MF-TDMA Satellite Networks', in Mobile and Wireless Communications Summit, 2007. 16th IST, pp. 1-5.

Rajkumar, R, Chen, L, Lehoczky, JP & Siewiorek, DP 1998, 'Practical solutions for QoS-based resource allocation problems', in Real-Time Systems Symposium, 1998. Proceedings., The 19th IEEE, pp. 296-306.

Smith, J, Chong, EKP, Maciejewski, AA & Siegel, HJ 2008, 'Decentralized market-based resource allocation in a heterogeneous computing system', in Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on, pp. 1-12.

Streitberger, W, Reinicke, M, Eymann, T, Catalano, M & Giulioni, G 2006, 'Economic Evaluation Framework of Resource Allocation Methods in Service-Oriented Architectures', in E-Commerce Technology, 2006. The 8th IEEE International Conference on and Enterprise Computing, E-Commerce, and E-Services, The 3rd IEEE International Conference on, pp. 50-.