Utility-driven solution for optimal resource allocation in computational grid

Optimal resource allocation is a complex undertaking due to large-scale heterogeneity present in computational grid. Traditionally, the decision based on certain cost functions has been used in allocating grid resource as a standard method that does not take resource access cost into consideration. In this paper, the utility function is presented as a promising method for grid resource allocation. To tackle the issue of heterogeneous demand, the user's preference is represented by utility function, which is driven by a user-centric scheme rather than system-centric parameters adopted by cost functions. The goal of each grid user is to maximize its own utility under different constraints. In order to allocate a common resource to multiple bidding users, the optimal solution is achieved by searching the equilibrium point of resource price such that the total demand for a resource exactly equals the total amount available to generate a set of optimal user bids. The experiments run on a Java-based discrete-event grid simulation toolkit called GridSim are made to study characteristics of the utility-driven resource allocation strategy under different constraints. Results show that utility optimization under budget constraint outperforms deadline constraint in terms of time spent, whereas deadline constraint outperforms budget constraint in terms of cost spent. The conclusion indicates that the utility-driven method is a very potential candidate for the optimal resource allocation in computational grid.     

Improving grid performance through processor allocation considering both speed heterogeneity and resource fragmentation

Grid performance are usually measured by the average turnaround time of all jobs in the system. A job’s turnaround time consists of two parts: queue waiting time and actual execution time, which in a heterogeneous grid environment, are severely affected by the resource fragmentation and speed heterogeneity factors. Most existing processor allocation methods focus on one of these two factors only. This paper proposes processor allocation methods, which consider both resource fragmentation and speed heterogeneity, to improve system performance of heterogeneous grids. Extensive simulation studies have been conducted to show that the proposed methods can effectively deliver better performance under most resource and workload conditions.     

Self-adjustment of resource allocation for grid applications

Grids involve coordinated resource sharing and problem solving in heterogeneous dynamic environments to meet the needs of a generation of researchers requiring large amounts of bandwidth and more powerful computational resources. The lack of resource ownership by grid schedulers and fluctuations in resource availability require mechanisms which will enable grids to adjust themselves to cope with fluctuations. The lack of a central controller implies a need for self-adaptation. Grids must thus be enabled with the ability to discover, monitor and manage the use of resources so they can operate autonomously. Two different approaches have been conceived to match the resource demands of grid applications to resource availability: Dynamic scheduling and adaptive scheduling. However, these two approaches fail to address at least one of three important issues: (i) the production of feasible schedules in a reasonable amount of time in relation to that required for the execution of an application; (ii) the impact of network link availability on the execution time of an application; and (iii) the necessity of migrating codes to decrease the execution time of an application. To overcome these challenges, this paper proposes a procedure for enabling grid applications, composed of various dependent tasks, to deal with the availability of hosts and links bandwidth. This procedure involves task scheduling, resource monitoring and task migration, with the goal of decreasing the execution time of grid applications. The procedure differs from other approaches in the literature because it constantly considers changes in resource availability, especially network bandwidth availability, to trigger task migration. The proposed procedure is illustrated via simulation using various scenarios involving fluctuation of resource availability. An additional contribution of this paper is the introduction of a set of schedulers offering solutions which differ in terms of both schedule length and computational complexity. The distinguishing aspect of this set of schedulers is the consideration of time requirements in the production of feasible schedules. Performance is then evaluated considering various network topologies and task dependencies.     

Goal state optimization algorithm considering computational resource constraints and uncertainty in task execution time

A search methodology with goal state optimization considering computational resource constraints is proposed. The combination of “an extended graph search methodology” and “parallelization of task execution and online planning” makes it possible to solve the problem. The uncertainty of the task execution time is also considered. The problem can be solved by utilizing a random-based and/or a greedy-based graph-searching methodology. The proposed method is evaluated using a rearrangement problem of 20 movable objects with uncertainty in the task execution time, and the effectiveness is shown with simulation results.     

QoS based resource scheduling by computational economy in computational grid

In this paper, we consider multiple QoS based grid resource scheduling. Each of grid task agent's diverse requirements is modeled as a quality of service (QoS) dimension, associated with each QoS dimension is a utility function that defines the benefit that is perceived by a user with respect to QoS choices in that dimension. The objective of multiple QoS based grid resource scheduling is to maximize the global utility of the scheduling system.     

Agent based sensors resource allocation in sensor grid

Sensor enabled grid may combine real time data about physical environment with vast computational resources derived from the grid architecture. One of the major challenges of designing a sensor enabled grid is how to efficiently schedule sensor resource to user jobs across the collection of sensor resources. The paper presents an agent based scheme for assigning sensor resources to appropriate sensor grid users on the basis of negotiation results among agents. The proposed model consists of two types of agents: the sensor resource agents that represent the economic interests of the underlying sensor resource providers of the sensor grid and the sensor user agents that represent the interests of grid user application using the grid to achieve goals. Interactions between the two agent types are mediated by means of market mechanisms. We model sensor allocation problems by introducing the sensor utility function. The goal is to find a sensor resource allocation that maximizes the total profit. This paper proposes a distributed optimal sensor resource allocation algorithm. The performance evaluation of proposed algorithm is evaluated and compared with other resource allocation algorithms for sensor grid. The paper also gives the application example of proposed approach.     

基于TOPSIS模型的网格资源分配决策算法

针对如何在网格环境中提高整个网格平台的性能和效率问题,提出了逼近理想解的排序法,即TOPSIS(technique for order preference by similarity to ideal solution)多指标综合评价模型,对网格节点的网络性能进行评价,将评价结果用于网格资源分配决策,得到了最短任务完成时间的资源分配方案.用网格模拟器GridSim搭建了包括路由器的网格环境,测试及与随机算法对比结果表明了TOPSIS多指标网格资源分配决策算法的可用性和高效性.     

A flexible layered control policy for resource allocation in a sensor grid

The paper proposes a flexible layered control policy for sensor resource allocation in a sensor grid. In order to allocate sensor resources in the system to maximize the sensor grid utility, different controllers are deployed at three levels: a job-level controller, an application group controller, and a sensor grid system controller. At the lowest levels, job-level controllers perform fast, frequent, local adaptation for optimizing a single sensor grid application at a time, while, at the highest levels, sensor grid system controllers perform less frequent control actions to optimize all applications. Sensor grid system control considers all sensor grid applications in response to large system changes at coarse time granularity. Sensor grid system control exploits the interlayer coupling of the resource layer and the application layer to achieve a system-wide optimization based on the sensor grid users’ preferences. Job-level control adapts a single application to small changes at fine granularity. The layered control system uses a set of utility functions to evaluate the performance of sensor grid applications and groups. The control system chooses control actions that would result in a higher level of utility. In the simulation, a performance evaluation of the algorithm is carried out.     

A computational economy for grid computing and its implementation in the Nimrod-G resource broker

Computational grids that couple geographically distributed resources such as PCs, workstations, clusters, and scientific instruments, have emerged as a next generation computing platform for solving large-scale problems in science, engineering, and commerce. However, application development, resource management, and scheduling in these environments continue to be a complex undertaking. In this article, we discuss our efforts in developing a resource management system for scheduling computations on resources distributed across the world with varying quality of service (QoS). Our service-oriented grid computing system called Nimrod-G manages all operations associated with remote execution including resource discovery, trading, scheduling based on economic principles and a user-defined QoS requirement. The Nimrod-G resource broker is implemented by leveraging existing technologies such as Globus, and provides new services that are essential for constructing industrial-strength grids. We present the results of experiments using the Nimrod-G resource broker for scheduling parametric computations on the World Wide Grid (WWG) resources that span five continents.     

Efficient location and allocation strategies for undesirable facilities considering their fundamental properties

The phrase “not in my backyard” (NIMBY) refers to the well-known social phenomena in which residents oppose the construction or location of undesirable facilities near their homes. Examples of such facilities include electric transmission lines, recycling centers and crematoria. Due to the opposition typically encountered in constructing an undesirable facility, the facility planner should understand the nature of the NIMBY phenomena and consider it as a key factor in determining facility location. We examine the characteristics of NIMBY phenomena and suggest two alternative mathematical optimization models with the objective of minimizing the total degree of NIMBY sentiments. Genetic algorithms are proposed to solve our linear and nonlinear integer programs. The results obtained via genetic algorithms for our linear integer programs are compared with those of CPLEX to evaluate their performance. The nonlinear programs are tested with various allocation policies. Sensitivity analysis is conducted about several system parameters.     

基于计算经济的网格资源管理模型研究

由于网格中的资源具有分布性、自治性、异构性和动态性,对网格资源进行高效的管理是一个具有挑战性的问题.提出把移动Agent和Agent技术、计算经济机制引入网格资源管理.自治Agent利用双向拍卖经济杠杆的调节,以用户的QoS所驱动,对资源的使用进行竞价拍卖,使网格的资源管理能够自动适应环境的变化.提出的基于计算经济的网格资源管理模型DynamicSA,实现了以用户的QoS驱动,对网格资源的有效管理具有一定的理论意义.     

Optimal testing resource allocation during module testing considering cost, testing effort and reliability

Software reliability is one of the most important quality attributes of commercial software. During software testing, software reliability growth models (SRGMs) are commonly used to describe the phenomenon of failure occurrence and/or fault removal which consequently enhancements software reliability. Large software systems are developed by integrating a number of relatively small and independent modules, which are tested independently during module testing phase. The amount of testing resource available is limited which is desired to be consumed judiciously so as to optimize the testing process. In this paper we formulate a resource allocation problem of minimizing the cost of software testing under available amount of testing resource, given a reliability constraint. We use a flexible SRGM considering testing effort which, depending upon the values of parameters, can describe either exponential or S-shaped failure pattern of software modules. A systematic and sequential Algorithm is proposed to solve the optimization problem formulated. Numerical examples are given to illustrate the formulation and solution procedures. Sensitivity analysis is performed to examine the behavior of some parameters of SRGM with most significant influence.     

Heuristic solutions to resource allocation in grid computing: a natural approach

Grid computing connects heterogeneous resources to achieve the illusion of being a single available entity. Charging for these resources based on demand is often referred to as utility computing, where resource providers lease computing power with varying costs based on processing speed. Consumers using this resource have time and cost constraints associated with each job they submit. Determining the optimal way to divide the job among the available resources with regard to the time and cost constraints is tasked to the Grid Resource Broker (GRB). The GRB must use an optimization algorithm that returns an accurate result in a timely manner. The genetic algorithm and the simulated annealing algorithm can both be used to achieve this goal, although simulated annealing outperforms the genetic algorithm for use by the GRB. Determining optimal values for the variables used in each algorithm is often achieved through trial and error, and success depends upon the solution domain of the problem.

A distributed multiple dimensional QoS constrained resource scheduling optimization policy in computational grid

This paper is to solve efficient QoS based resource scheduling in computational grid. It defines a set of QoS dimensions with utility function for each dimensions, uses a market model for distributed optimization to maximize the global utility. The user specifies its requirement by a utility function. A utility function can be specified for each QoS dimension. In the grid, grid task agent acted as consumer pay for the grid resource and resource providers get profits from task agents. The task agent' utility can then be defined as a weighted sum of single-dimensional QoS utility function. QoS based grid resource scheduling optimization is decomposed to two subproblems: joint optimization of resource user and resource provider in grid market. An iterative multiple QoS scheduling algorithm that is used to perform optimal multiple QoS based resource scheduling. The grid users propose payment for the resource providers, while the resource providers set a price for each resource. The experiments show that optimal QoS based resource scheduling involves less overhead and leads to more efficient resource allocation than no optimal resource allocation.     

An effective and robust two-phase resource allocation scheme for interdependent tasks in mobile ad hoc computational Grids

This paper addresses the problem of resource allocation to interdependent tasks in mobile ad hoc computational Grids. Dependencies between tasks imply that there can be heavy communication induced by data transfers between tasks executed on separate nodes. The communication in mobile ad hoc Grids is always expensive and unreliable, and therefore plays a critical role in application performance. There are several factors that contribute to communication cost. Unreliable and short-term connectivity can increase communication cost due to frequent failure and activation of links, and ineffective resource allocation can increase communication cost due to multi hop communication between dependent tasks. To reduce communication cost, an effective and robust resource allocation scheme is required. However, the design of such a scheme for mobile ad hoc computational Grids exhibits numerous difficulties due to the constrained communication environment, node mobility, and lack of pre-existing network infrastructure.     

A clairvoyant site allocation policy based on service demands of jobs in a computational grid

In the present paper we evaluate the performance of three different site allocation policies in a 2-level computational grid with heterogeneous sites. We examine the case where service demands of jobs show high variability, and we consider that schedulers are aware of the service times. A simulation model is used to evaluate performance in terms of the average response time and slowdown, under medium and high load. The impact of the various input parameters on performance is also taken into account. Simulation results show that one policy outperforms the other two that are examined, especially at high load. Furthermore, no performance degradation is observed when estimations are used instead of exact knowledge about job service times.     

Joint optimal sensing time and power allocation for multi-channel cognitive radio networks considering sensing-channel selection

In this paper,we consider a multi-channel cognitive radio network(CRN)where each secondary user(SU)can only choose to sense a subset of channels.We formulate a joint optimization problem of sensingchannel selection,sensing time and power allocation under the constraints of average transmit power budget and average interference power budget,which maximizes the CRN’s total throughput.We propose a greedy algorithm to solve the joint optimization problem,which has much less computational complexity.Moreover,it is shown that the search space of the greedy algorithm can be further pruned.Finally,numerical results demonstrate that the greedy algorithm has comparable performance to the exhaustive search algorithm.     

A near-optimal database allocation for reducing the average waiting time in the grid computing environment

In a grid computing environment, a great many users may access the same database simultaneously. To reduce the average waiting time for all users, a grid designer usually replicates the frequently accessed database among nodes based on the load balance heuristic. On the other hand, users may raise identical queries regarding an issue of interest, e.g., stock information, on a database and each of the queries will be directed to any node having a replica of that database. That is, the same answer will be determined by multiple nodes. Consequently, there exist two shortcomings of poor data sharing and duplicate calculations if the database is not replicated and allocated adequately. In this paper, we aim to minimize average waiting time and try to overcome the two shortcomings by performing database allocation over multiple nodes without any replication. The main idea behind the proposed method is to map the original problem to the Euclidean space Rⁿ and to solve the mapped problem in Rⁿ by a gradient-based optimization technique. The theoretical analyses ensure that the proposed method can converge linearly and achieve near-optimal results.     

Negotiation strategy for continuous long-term tasks in a grid environment

Nowadays, much research is concerned with execution of long-term continuous tasks, which produce data in real time, e.g. monitoring applications. These tasks can be run for months or years and they are usually resource intensive in terms of the large amounts of data which is processed per time unit. A Grid can potentially provide the amount of resources necessary to execute these tasks, but it might prove to be impossible or non-beneficial for a Grid to allocate resources for such long durations as these resources can be also requested by other clients or might join a Grid only for some periods of time. To resolve these differences, a client and a Grid Resource Allocator negotiate, and a client has to agree for a shorter execution period at the end of which it needs to negotiate again. In this paper, we discuss in detail a decision-making mechanism for a client as part of its negotiation strategy, which aims to increase the duration of execution periods and to decrease the duration of interruptions. This new strategy, ConTask, has been tested on a realistic Grid resource simulator, and it demonstrates better utilities than our strategy which has not been specifically designed for continuous tasks under various conditions.     

Cross-layer optimization policy for QoS scheduling in computational grid

This paper presents a cross-layer quality of service (QoS) optimization policy for computational grid. Efficient QoS management is critical for computational grid to meet heterogeneity and dynamics of resources and users’ requirements. There are different QoS metrics at different layers of computational grid. To improve perceived QoS by end users over computational grid, QoS supports can be addressed in different layers, including application layer, collective layer, fabric layer and so forth. The paper tackles cross-layer grid QoS optimization as optimization decomposition, each layer corresponds to a decomposed subproblem. The proposed policy produces an optimal set of grid resources, service compositions and user's payments at the fabric layer, collective layer and application layer respectively to maximize global grid QoS. The cross-layer optimization problem decomposes into three subproblems: grid resource allocation problem, service composing and user satisfaction degree maximization problem, all of which interact through the optimal variables for capacities of grid resources and service demand. In order to coordinate the subproblems, cross-layer QoS feedback mechanism is established to ensure different layer interactions. The simulations are conducted to validate the efficiency of the proposed policy.