An improved load-balancing mechanism based on deadline failure recovery on GridSim

Grid computing has emerged a new field, distinguished from conventional distributed computing. It focuses on large-scale resource sharing, innovative applications and in some cases, high performance orientation. The Grid serves as a comprehensive and complete system for organizations by which the maximum utilization of resources is achieved. The load balancing is a process which involves the resource management and an effective load distribution among the resources. Therefore, it is considered to be very important in Grid systems. For a Grid, a dynamic, distributed load balancing scheme provides deadline control for tasks. Due to the condition of deadline failure, developing, deploying, and executing long running applications over the grid remains a challenge. So, deadline failure recovery is an essential factor for Grid computing. In this paper, we propose a dynamic distributed load-balancing technique called “Enhanced GridSim with Load balancing based on Deadline Failure Recovery” (EGDFR) for computational Grids with heterogeneous resources. The proposed algorithm EGDFR is an improved version of the existing EGDC in which we perform load balancing by providing a scheduling system which includes the mechanism of recovery from deadline failure of the Gridlets. Extensive simulation experiments are conducted to quantify the performance of the proposed load-balancing strategy on the GridSim platform. Experiments have shown that the proposed system can considerably improve Grid performance in terms of total execution time, percentage gain in execution time, average response time, resubmitted time and throughput. The proposed load-balancing technique gives 7 % better performance than EGDC in case of constant number of resources, whereas in case of constant number of Gridlets, it gives 11 % better performance than EGDC.     

Enhanced GridSim architecture with load balancing

Grid is a network of computational resources that may potentially span many continents. Maximization of the resource utilization hinges on the implementation of an efficient load balancing scheme, which provides (i) minimization of idle time, (ii) minimization of overloading, and (iii) minimization of control overhead. In this paper, we propose a dynamic and distributed load balancing scheme for grid networks. The distributed nature of the proposed scheme not only reduces the communication overhead of grid resources but also cuts down the idle time of the resources during the process of load balancing. We apply the proposed load balancing approach on Enhanced GridSim in order to gauge the effectiveness in terms of communication overhead and response time reduction. We show that significant savings are delivered by the proposed technique compared to other approaches such as centralized load balancing and no load balancing.     

An enhanced load balancing mechanism based on deadline control on GridSim

A Grid is a network of computational resources that may potentially span many continents. Load balancing in a Grid is a hot research issue which affects every aspect of the Grid, including service selection and task execution. Thus, it is necessary and significant to solve the load balancing problem in a Grid. In this paper, we propose a dynamic, distributed load balancing scheme for a Grid which provides deadline control for tasks. In our scenario, first, resources check their state and make a request to the Grid Broker according to the change of load state. Then, the Grid Broker assigns Gridlets between resources and scheduling for load balancing under the deadline request. We apply our load balancing strategy into a popular Grid simulation platform GridSim. Experimental results prove that our proposed load balancing mechanism can (1) reduce the makespan, (2) improve the finished rate of the Gridlet, and (3) reduce the resubmitted time.     

Dynamic Load Balancing and Pricing in Grid Computing with Communication Delay

Due to the emergence of Grid computing over the Internet, there is presently a need for dynamic load balancing algorithms which take into account the characteristics of Grid computing environments. In this paper, we consider a Grid architecture where computers belong to dispersed administrative domains or groups which are connected with heterogeneous communication bandwidths. We address the problem of determining which group an arriving job should be allocated to and how its load can be distributed among computers in the group to optimize the performance. We propose algorithms which guarantee finding a load distribution over computers in a group that leads to the minimum response time or computational cost. We then study the effect of pricing on load distribution by considering a simple pricing function. We develop three fully distributed algorithms to decide which group the load should be allocated to, taking into account the communication cost among groups. These algorithms use different information exchange methods and a resource estimation technique to improve the accuracy of load balancing. We conducted extensive simulations to evaluate the performance of the proposed algorithms and strategies.     

A hybrid load balancing policy underlying grid computing environment

In recent years, network bandwidth and quality has been drastically improved, even much faster than the enhancement of computer performance. The various communication and computing tasks in the fields such as telecommunication, multimedia, information technology, and construction simulation, can be integrated and applied in a distributed computing environment nowadays. However, as the demands of many researches for computing resources gradually grow, Grid Computing integrated with a distributed computing environment and the Internet (network) has gained more attention. The so-called Grid Computing is to utilize the idle computing resources (nodes) on the network to facilitate the execution of complicated tasks that require large-scale computing. In other words, the composition of Grid resources is dynamic and varies with time. Thus, when selecting nodes for executing a task, the dynamic of the nodes in the Grid must be considered, and to exploit the effectiveness of the resources, they have to be properly selected according to the properties of the task. This study proposed a hybrid load balancing policy which integrated static and dynamic load balancing technologies to assist in the selection for effective nodes. In addition, if any selected node can no longer provide resources, it can be promptly identified and replaced with a substitutive node to maintain the execution performance and the load balancing of the system.     

A Grid-based Virtual Reactor: Parallel performance and adaptive load balancing

We address the problem of porting parallel distributed applications from static homogeneous cluster environments to dynamic heterogeneous Grid resources. We introduce a generic technique for adaptive load balancing of parallel applications on heterogeneous resources and evaluate it using a case study application: a Virtual Reactor for simulation of plasma chemical vapour deposition. This application has a modular architecture with a number of loosely coupled components suitable for distribution over the Grid. It requires large parameter space exploration that allows using Grid resources for high-throughput computing. The Virtual Reactor contains a number of parallel solvers originally designed for homogeneous computer clusters that needed adaptation to the heterogeneity of the Grid. In this paper we study the performance of one of the parallel solvers, apply the technique developed for adaptive load balancing, evaluate the efficiency of this approach and outline an automated procedure for optimal utilization of heterogeneous Grid resources for high-performance parallel computing.     

Towards a hybrid load balancing policy in grid computing system

Grid computing has become conventional in distributed systems due to technological advancements and network popularity. Grid computing facilitates distributed applications by integrating available idle network computing resources into formidable computing power. As a result, by using efficient integration and sharing of resources, this enables abundant computing resources to solve complicated problems that a single machine cannot manage. However, grid computing mines resources from accessible idle nodes and node accessibility varies with time. A node that is currently idle, may become occupied within a second of time and then be unavailable to provide resources. Accordingly, node selection must provide effective and sufficient resources over a long period to allow load assignment. This study proposes a hybrid load balancing policy to integrate static and dynamic load balancing technologies. Essentially, a static load balancing policy is applied to select effective and suitable node sets. This will lower the unbalanced load probability caused by assigning tasks to ineffective nodes. When a node reveals the possible inability to continue providing resources, the dynamic load balancing policy will determine whether the node in question is ineffective to provide load assignment. The system will then obtain a new replacement node within a short time, to maintain system execution performance.     

一种有效负载均衡的网格Web服务体系结构模型

基于Web服务资源的小世界模型,提出了一种可无缝结合网格OGSA框架的Web服务体系结构与动态的资源负载均衡分配模型,它以Web服务资源注册中心(Web Services Resource Register Center,WSRRC)作为Web服务资源查找的入口,以Web服务资源ID类形成的虚拟资源树作为资源逻辑组织与负载均衡分配结构,以小世界形成的区域代理自治系统(Area Proxy Autonomy System．APAS)来进行Web服务资源的维护．并详细描述了该模型的实现机制、组织协议与数据结构,着重研究了逻辑资源树负载信息的传播机制及负载均衡策略,模拟试验表明该模型是合理而有效的：它可以在较小开销下获得较满意的资源组织与定位性能,能适应网格Web服务资源的异构、复杂与动态性,具有良好的可扩展性及保持全局网络负载均衡的良好性能．     

Static strategy and dynamic adjustment: An effective method for Grid task scheduling

Task scheduling is the key technology in Grid computing. Hierarchical organization is suitable for the computational Grid because of the dynamic, heterogeneous and autonomous nature of the Grid. Although a number of Grid systems adopt this organization, few of them has dealt with task scheduling for the hierarchical architecture. In this paper, we present an effective method, fully taking into account both historical Grid trade data and dynamic variation of the Grid market to improve the task scheduling for a hierarchical Grid market. The main idea of the proposed method is a combination of an off-line static strategy using time series prediction and an on-line dynamic adjustment using reinforcement learning. The superiority of this new scheduling algorithm, in improving the inquiry efficiency for resource consumers, getting better load balancing of the whole hierarchical Grid market, and achieving higher success rate of the Grid service request, is demonstrated by simulation experiments.     

上海网格中间件中基于负载平衡的调度框架

在网格环境中,实现动态的负载平衡在服务调度中起到了非常关键的作用。然而,网格环境中的资源的动态性决定了它难以被监控,自治性又决定了它难以被集中管理。为在网格中间件中实现服务调度的负载平衡,提供了一些具有参考价值的解决方案。介绍设计和实现调度框架的动机以及需要解决的问题,并深入探讨在上海网格中间件中设计和实现调度框架的思路,以及达到动态负载平衡的具体方案。     

A dynamic load balancing scheme with incentive mechanism in heterogeneous structured P2P networks

Dynamic load imbalance is a basic and inherent problem in structured P2P networks. Most existing research suffers from the problems of inefficiency in globally managing the nodes’ load information and consumption of network bandwidth. This paper describes the mechanisms for collecting and globally managing the dynamic load of each node, and based on which to present a load balancing strategy which transfers the load from overloaded to under loaded nodes so as to improve load balancing efficiency. In order to encourage the rational and selfish nodes to actively participate in the load balancing process, we also propose an incentive mechanism in dynamic load balancing, by which the differentiated services could be provided for the nodes according to their load balancing abilities. The simulation results indicate that our approach could tackle the load imbalance problem in structured P2P networks effectively and efficiently in terms of the load distribution and the transferred load volume.     

DistDLB: Improving cosmology SAMR simulations on distributed computing systems through hierarchical load balancing

Cosmology SAMR simulations have played a prominent role in the field of astrophysics. The emerging distributed computing systems provide an economic alternative to the traditional parallel machines, and enable scientists to conduct cosmological simulations that require vast computing power. An important issue of conducting distributed cosmological simulations is about performance and efficiency. In this paper, we present a dynamic load balancing scheme called DistDLB that is designed to improve the performance of distributed cosmology simulations. Distributed systems, e.g. the Computation Grid, usually consist of heterogeneous resources connected with shared networks. By considering these features of distributed systems and unique characteristics of cosmology SAMR simulations, DistDLB focuses on reducing the redistribution cost through a hierarchical load balancing approach and a run-time decision making mechanism. Heuristic methods have been proposed to adaptively adjust load balancing strategies based on the observation of the current system and application state. Our experiments with real-world cosmology simulations on production systems indicate that the proposed DistDLB scheme can effectively improve the performance of cosmology simulations by 2.56–79.14% as compared to the scheme that does not consider the heterogeneous and dynamic features of distributed systems.     

A dynamic resource management in mobile agent by artificial neural network

In this paper, a resource management for dynamic load balancing in mobile agent by artificial neural network scheme (ANN-DLB) is presented to maximize the number of the served tasks in developing high performance cluster. This dynamic load balance with the growth of the service type and user number in the mobile networks of the higher performance is required in service provision and throughput. Most of the conventional policies are used in load indices with the threshold value to decide the load status of the agent hosts by CPU or memory. The main factor influencing the workload is the competitions among the computing resources such as CPU, memory, I/O and network. There are certain I/O data of the intensive applications where load balancing becomes the important issue. This relationship between the computing resources is very complex to define the rules for deciding the workload. This paper proposed a new dynamic load balancing for evaluating the agent hosts’ workload with the artificial neural network (ANN). By applying the automatic learning of the back-propagation network (BPN) model can establish the ANN model and also can measure the agent host loading with five inputs: CPU, memory, I/O, network and run-queue length. The structure of the load balancing system is composed of three design agents: the load index agent (LIA), the resource management agent (RMA) and the load transfer agent (LTA). These experimental results reveal that the proposed ANN-DLB yields better performance than the other methods. These results demonstrate that the proposed method has high throughput, short response time and turnaround time, and less agent host negotiation complexity and migrating tasks than the previous methods.     

An Adaptive Scheduler for Grids

The recent development of telecommunication infra-structures such as the world-wide networks, interconnecting millions of computers spread all over the world, has made possible the coordinated use of a large amount of heterogeneous, weakly connected computational resources. This new area, known as Grid computing, is currently the focus of several research activities and projects. However, as in every new domain of research, in this one there are many unsolved questions, in particular those related to the management of the processing load inside the system. In this work, the problem of balancing processing loads on a Grid is approached by the introduction of the Generational Scheduling with Task Replication (GSTR) algorithm. A comprehensive set of simulations and tests is carried out in order to validate the proposed solution. A methodology for calculating and analyzing speed-up and efficiency ratios on heterogeneous groups of computers is also shown.     

Dynamic balancing of communication and computation load for HLA-based simulations on large-scale distributed systems

Dynamic balancing of computation and communication load is vital for the execution stability and performance of distributed, parallel simulations deployed on the shared, unreliable resources of large-scale environments. High Level Architecture (HLA) based simulations can experience a decrease in performance due to imbalances that are produced initially and/or during run time. These imbalances are generated by the dynamic load changes of distributed simulations or by unknown, non-managed background processes resulting from the non-dedication of shared resources. Due to the dynamic execution characteristics of elements that compose distributed applications, the computational load and interaction dependencies of each simulation entity change during run time. These dynamic changes lead to an irregular load and communication distribution, which increases overhead of resources and latencies. A static partitioning of load is limited to deterministic applications and is incapable of predicting the dynamic changes caused by distributed applications or by external background processes. Therefore, a scheme for balancing the communication and computational load during the execution of distributed simulations is devised in a scalable hierarchical architecture. The proposed balancing system employs local and cluster monitoring mechanisms in order to observe the distributed load changes and identify imbalances, repartitioning policies to determine a distribution of load and minimize imbalances. A migration technique is also employed by this proposed balancing system to perform reliable and low-latency load transfers. Such a system successfully improves the use of shared resources and increases distributed simulations’ performance by minimizing communication latencies and partitioning the load evenly. Experiments and comparative analyses were conducted in order to identify the gains that the proposed balancing scheme provides to large-scale distributed simulations.     

Distributed semantic document retrieval using O-FCN

Object-Fuzzy Concept Network (O-FCN) is a recent knowledge representation model to integrate Fuzzy Ontologies in Information Retrieval systems. O-FCNs handle huge data collections and have to face the inherent complexity of semantic manipulation during the retrieval process. Therefore their distribution is an essential requirement to reach good scalability. We present ‘Grid2Peer’: a distributed architecture for O-FCN-based semantic information retrieval that exploits the self-organization characteristics of both Grid and P2P systems. The most relevant features in Grid2Peer are the adoption of the fuzzy sets to organize the overlay itself, the capability of migrating knowledge towards the location where it is accessed, and granting dynamic load balancing among peers. Numerical simulations are performed in order to analyze these characteristics, evaluating also fuzzy precision and fuzzy recall measures given by the distributed retrieval algorithm for the Grid2Peer architecture.     

集群动态负载平衡系统的性能评价

该文使用随机Petri网对集群动态负载平衡系统建立了一个抽象模型．通过细化模型中的节点本地处理部分对5种动态负载平衡算法的性能进行了分析，并讨论了集群负载特性对动态负载平衡系统性能的影响，最后得出的主要结论有：(1)动态负载平衡算法可以取得比静态负载平衡算法更好的性能；(2)与传统的只考虑CPU就绪队列的负载平衡算法相比，考虑了各种I／O请求队列的负载平衡算法可以取得更好的性能；(3)即使在极端的集群负载特性中。集群动态负载平衡算法仍然能取得比较理想的性能，因此实现即使是十分简单的集群动态负载平衡系统也是很有必要的。     

集群服务器负载均衡技术研究

负载均衡服务器集群中,负载均衡是一个关键部分,它是集群系统中任务分配的核心环节。本文提出了一种基于动态反馈的负载均衡方法,其避免了服务器间的负载不平衡,能较好地避免服务器的倾斜,提高系统的资源使用效率以及系统的吞吐率,有效地解决负载迁移的抖动问题,提高了平衡系统的性能。     

Biased random walks on resource network graphs for load balancing

The currently emerging large-scale complex networks and networks of networks are becoming apparent in the pervasive supply of seamless and transparent access to heterogeneous resources and services such as network domains, applications, services and storage owned by multiple organizations. The dynamics and heterogeneous environments involved, however, pose many challenges for controlling and balancing resource access, composition and deployment across complex grid and network infrastructures. In this paper, a scheme is proposed that gives a distributed load-balancing scheme by generating almost regular resource allocation networks. This network system is self-organized and depends only on local information for load distribution and resource discovery. The in-degree of each node refers to its free resources, and the job assignment and resource discovery processes required for load-balancing are accomplished by using fitted random sampling. Simulation results show that the generated network system provides an effective, scalable, and reliable load-balancing scheme for the distributed resources in grids and networks. The proposed solution is tested with real world data and the performance is tested against a recently reported distributed algorithm for load balancing.     

计算网格中基于时间均衡的并行粗粒度任务调度算法

考虑网格资源异构、自治、动态等特性,讨论本地用户具有强占优先权情况下的任务调度问题,提出了TBBS(Time-Balancing Based Scheduling Algorithm)算法.建立调度优化模型,以期望完成时间最小为目标选择执行任务的最佳资源组合.以时间均衡策略将任务分解并调度到资源上执行,减少了子任务同步时因等待而产生的延时,获得较好的并行计算性能.采用重复调度策略,适应计算网格中资源的特性.