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.     

基于风险策略的多单元连续双向拍卖的网格资源分配

针对计算网格资源的特点,提出一种基于风险策略的多单元连续双向拍卖的网格资源分配机制,实现对网格资源灵活有效的管理。首先,介绍了基于多单元连续双拍卖的网格资源分配框架。其次,针对计算网格资源的有限性,提出了RB2-MCDA机制。RB2-MCDA机制是在多单元连续双向拍卖中,代理采用Risk-Based2策略进行资源交易。Risk-Based2策略是一种基于风险行为的代理策略。实验结果表明,在不同规模的有限资源的计算网格中采用RB2-MCDA机制能够实现较高的资源分配效率,当资源需求量接近供给量时,分配效率超过99%。     

基于贝叶斯策略的网格资源分配方法

考虑网格应用QoS需求,以最大化网格系统的经济收益为目标,提出了一种基于贝叶斯策略的网格资源分配方法。该方法基于价格可代表资源QoS综合性能的思想,利用历史QoS匹配记录,运用朴素贝叶斯定理根据用户提交的价格参数来分配与其级别相对应的符合要价范围资源,并优先考虑QoS水平较高的任务,将当前时刻QoS水平较高的资源预留给下一时刻到达的QoS水平较高的任务,而忽略当前时刻QoS水平较低的任务。实验结果表明,该资源分配方法不仅能有效地保障用户QoS,而且能使网格系统获得较大的经济收益。     

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.     

Parallel resource co-allocation for the computational grid

Resource co-allocation is one of the crucial problems affecting the utility of the grid. Because the numbers of the application tasks and amounts of required resources are enormous and quick responses to the requirements of users are necessary in the real grid environment, real-time resource co-allocation may be large-scale. A parallel resource co-allocation algorithm based on the framework for mapping with resource co-allocation is proposed in this paper. Through the result of experiments, it is concluded that the parallel method reduces the execution time of the resource co-allocation algorithm significantly, and makes the overall response time to the end-users small.     

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.     

网格环境下基于信任关系的资源调度策略

提出一个信任评估模型。为了减少资源调度过程中使用传统安全措施带来的网格开销,提出把信任关系作为安全衡量标准融入网格环境下的资源调度策略中。设计了一个融入信任关系的资源映射算法TRM-Schedule,仿真试验证明了算法的合理性和有效性。     

智能电网中两阶段网络切片资源分配技术

为满足网络切片在智能电网中的多样化需求,提出了一个在智能电网中基于云-边协同的切片资源分配模型.为优化网络切片分配,提出一种两阶段的切片分配模型:在第一阶段中,以用户体验最优为目标,建立了本地边缘网络的资源分配问题的优化模型,并采用拉格朗日乘子法对此最优问题进行了求解;在第二阶段中,首先将网络切片资源分配系统建模成Ma...     

融合PSO与ACS的网格资源分配研究

资源分配和任务调度是网格计算的一个关键问题之一。提出一种融合离散粒子群优化算法和蚁群算法的新型算法来解决网格资源分配问题。该算法通过在粒子群算法中引入蚂蚁算法,可有效克服粒子群算法后期的局部搜索能力差和蚁群算法前期盲目搜索的缺陷。理论分析及模拟实验表明该算法具有良好的性能。     

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.     

基于超市模型的网格资源分配方法研究*

针对网格资源管理中的资源分配问题,提出了一种基于超市模型的网格资源管理分配方法.该方法能够实现子资源的快速匹配,从而减少了网格管理开销,更高效地分配了稀缺资源.     

面向运行时间预测和容错感知的网格资源分配

提出与描述了一种面向任务运行时间预测和容错感知（Fault-Aware）的网格资源分配策略,采用主动容错的方式,在资源出错之前尽量提前避免它出错或异常的情况发生。该策略把网格中任务的运行时间（runtime）预测和资源的在线时间（uptime）预测结合起来,相对于普通的调度策略具有比较高的资源利用率。在具体的CoBRA网格中间件中实现了该容错感知调度,描述了实现该容错感知调度策略模块的功能。测试过程中选择了睡眠任务技术,划分四种不同的场景进行实验,把该容错感知资源分配与普通的FCFS调度策略进行比较,结果证明在可变化的资源可用性的情况下系统可以加快应用的整体执行时间,具有很小的偏差。     

网格资源分配算法的研究

资源分配是网格计算研究领域中的一个要点问题,目前已研究的若干计算智能方法大多是单一的用于解决网格资源分配问题,对于在混合的前提下提高资源分配性能方面还缺乏深入的研究。为此,针对网格资源分配问题提出了一个启发式混合搜索算法,通过带有启发式的遗传算法在资源中进行搜索,在生成的解中再利用蚁群算法做进一步的探索。仿真实验结果表明,该算法在满足用户需求的前提下,有效地提高了网格资源利用率。     

一种面向随机性负载的计算网格资源预留定价策略

针对传统预留机制对本地任务服务质量造成的负面影响,提出了基于预留收益与损失均衡的资源预留机制。首先,基于本地任务相关统计特性利用概率论方法,给出并证明了一段时间内本地任务执行时间之和的概率分布函数。然后,在资源提供者的效用中考虑本地任务可能带来的损失,求解出了为保障本地任务服务质量的最低资源价格。实验结果表明,提出的预留机制能有效保障本地任务的服务质量,提高资源利用率、降低任务拒绝率。     

基于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.     

An efficient resource allocation for maximizing benefit of users and resource providers in ad hoc grid environment

Ad hoc grids allow a group of individuals to accomplish a mission that involves computation and communication among the grid components, often without fixed structure. In an ad hoc grid, every node in the network can spontaneously arise as a resource consumer or a resource producer at any time when it needs a resource or it possesses an idle resource. At the same time, the node in ad hoc grid is often energy constrained. The paper proposes an efficient resource allocation scheme for grid computing marketplace where ad hoc grid users can buy usage of memory and CPU from grid resource providers. The ad hoc grid user agents purpose to obtain the optimized quality of service to accomplish their tasks on time with a given budget, and the goal of grid resource providers as profit-maximization. Combining perspectives of both ad hoc grid users and resource providers, the paper present ad hoc grid resource allocation algorithm to maximize the global utility of the ad hoc grid system which are beneficial for both grid users and grid resource providers. Simulations are conducted to compare the performance of the algorithms with related work.