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.     

A new step toward load balancing based on competency rank and transitional phases in Grid networks

Grid computing is a network of software-hardware capabilities. It serves as a comprehensive and complete system for organizations by which the maximum utilization from resources is achieved. Resource distribution in a heterogeneous and unstable environment and also effective load distribution among these resources are the important and difficult problems in Grid networks. Using dynamic and static algorithms or searching tree and Branch and Bound algorithm are considered to be among the available methods to reach the load balancing in Grid networks. This paper presents a new method for dynamic load balancing. In this method, we use the subtraction of forward and backward ants as a competency rank to take the priority of the sites, and we use a control word to search the suitable resource as well. Our main purpose is to devote jobs to the existing resources based on their processing power. Simulation results show that the proposed method can reduce the total completion time and also total tardiness to get the load balancing. The cost of using resources as an effective factor in load balancing is also observed.     

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.     

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.     

内容发布订阅系统中的动态负载均衡

复杂广域网络应用带来了内容发布订阅系统动态负载失衡问题。提出了一种动态负载均衡框架解决该问题。采用周期性交换和计算负载的方法实现了负载探测,采用代理复制和区域重构的方法解决了负载迁移问题,设计了负载协商状态机用于协商代理之间的负载迁移,采用转移加入和动态自适应两种方法进行负载均衡决策。实验结果表明,该负载均衡框架能够有效解决内容发布订阅系统的动态负载失衡问题,将负载均衡效率提高了50%。     

An improved approach for load balancing among heterogeneous resources in computational grids

In recent days, due to the rapid technological advancements, the grid computing has become an important area of research in distributed systems. The load balancing is a very important and complex problem in grid computing. In this paper, we propose a dynamic-distributed load-balancing technique called the improved load balancing on enhanced GridSim with deadline control (IEGDC) for computational grids. Here, we provide a new mechanism of scheduling to enhance the utilization of the resources and to prevent the resource overloading. A selection method for scheduling by considering the state of resource bandwidth and capacity of various resources is presented. We simulate the proposed load-balancing strategy on the GridSim platform. The proposed mechanism on comparison is found to outperform the existing schemes in terms of response time, resubmitted time, finished and unfinished Gridlets. The simulation results are presented.     

Swarm Intelligence Approaches for Grid Load Balancing

With the rapid growth of data and computational needs, distributed systems and computational Grids are gaining more and more attention. The huge amount of computations a Grid can fulfill in a specific amount of time cannot be performed by the best supercomputers. However, Grid performance can still be improved by making sure all the resources available in the Grid are utilized optimally using a good load balancing algorithm. This research proposes two new distributed swarm intelligence inspired load balancing algorithms. One algorithm is based on ant colony optimization and the other algorithm is based on particle swarm optimization. A simulation of the proposed approaches using a Grid simulation toolkit (GridSim) is conducted. The performance of the algorithms are evaluated using performance criteria such as makespan and load balancing level. A comparison of our proposed approaches with a classical approach called State Broadcast Algorithm and two random approaches is provided. Experimental results show the proposed algorithms perform very well in a Grid environment. Especially the application of particle swarm optimization, can yield better performance results in many scenarios than the ant colony approach.     

A Grid resource brokering strategy based on resource and network performance in Grid

To achieve high performance distributed data access and computing in Grid environment, monitoring of resource and network performance is vital. Our proposed Grid network monitoring architecture is modeled by the Grid scheduler. The proposed Grid network monitoring retrieves network metrics using sensors as network monitoring tools. The mobile agents are migrated to start the sensors to measure the network metrics in all Grid Resources from the Resource Broker. The raw data provided by the monitoring tools is used to produce a high level view of the Grid through the set of internal cost functions. The network cost function is formed by combining various network metrics such as bandwidth, Round Trip Time, jitter and packet loss to measure the network performance. This paper presents the Grid Resource Brokering strategy which analyzes the network metrics along with the resource metrics for the selection of the Grid resource to submit the job and the proposed approach is integrated with CARE Resource Broker (CRB) for job submission. The experimental results are evident for the minimization of job completion time for the submitted job. The simulation results also prove that the more number of jobs are completed with the proposed strategy which influences the better utilization of the Grid resources.     

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.     

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

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

多维QoS指导的DBC最优算法

目前应用于网格的一些调度算法过于简单,不能满足对QoS的多样化需求,比如DBC（deadline and budget constrained）调度算法只支持两维的QoS需求,即截止期限（deadline）和预算（budge）。而对于真正的网格应用,用户与系统之间的交互应该加强,用户应能对提交的工作提出多种多样的QoS需求。在对传统DBC算法进行优化的基础上,提出了“多维QoS指导的DBC最优算法”,以确保搜索到所有满足用户需求的资源,不仅包括价格、时间最优,而且满足他们自己定义的专有QoS需求。为了测试这一最优算法,所做的模拟实验是以上海网格环境中各高性能结点的数据信息作为参数。     

A design of RFTOG model for distributed real-time applications

In this paper, we design the Real-Time Fault-Tolerant Object Group (RFTOG) model that supports the grouping of distributed objects that are required for distributed application. The proposed model basically provides two services. One is the group management service, which supports both consistency maintenance and transparency of the replicated objects with a variety of replication mechanisms. It also provides the load balancing of distributed applications. The other is real-time service in an object group. When the clients request the service to the service object selected through the load balance, this service guarantees the service execution within deadline for the clients’ requests. We develop the Naval Air Defense System (NADS) simulator for verifying the effectiveness of the services proposed by the RFTOG model.     

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.     

一种基于流量映射代理的以太网流量均衡实现结构

流量均衡是提高网络性能的重要技术。随着基于以太网技术构建的网络规模不断扩大,如何实现流量均衡成为制约以太网技术发展的重要问题之一。针对该问题,论文提出了一种以太网流量均衡实现结构,该结构的核心部分是采用流量均衡选路算法的流量映射代理,它能够利用虚拟局域网技术和多生成树协议控制用户流量在网络中的分布,实现流量均衡。     

基于网格计算的混合负载均衡的改进策略

近年来,随着科学研究对计算资源的要求不断增加,结合分布式计算环境和互联网的网格计算已经得到越来越多研究者的关注。网格计算就是利用网络中的空闲计算资源来协助那些要求大量计算的复杂任务的执行。根据分布式系统的静态和动态负载均衡策略的优缺点,本文提出了在网格计算环境下的混合负载均衡策略。为了让网络中的节点在网格计算环境中有效地执行需要大量计算的复杂任务,并根据大量的实验总结,提出了新的用来评估节点效率的函数,较以前的函数执行效率有了提高。     

基于LVS＋KEEPALIVED的高可用负载均衡研究与应用

本文针对网络服务商普遍面临的的高并发访问量导致响应速度迟缓的问题进行分析,研究了基于LVS（Linux虚拟服务器）和KEEPALIVED（交换机制软件）的高可用负载均衡的原理,实现了一个可伸缩的、高可用的并具有容错容灾能力的负载均衡系统,该系统采用VS/DR的模式搭建,系统基于IP层和基于内容请求分发的负载平衡调度解决算法,将这些算法在Linux内核中进行实现,并对系统的高可用和负载均衡进行实验,实验证明,该负载均衡系统能对客户的请求进行分流,能有效减轻单个服务器的负载压力.     

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.     

Real-time load balancing scheduling algorithm for periodic simulation models

A scheduling algorithm is crucial for real-time simulations because it guarantees that each model meets its deadline. Traditional online real-time scheduling algorithms such as Earliest Deadline First (EDF) introduce a high overhead when scheduling a large number of models. In this paper, a new algorithm called time-stepped load balancing (TLS) is proposed to address the real-time execution of a model set in a time-stepped simulation. A load balancing schedule table is generated before a simulation and rebalanced at runtime to dynamically schedule the changed model set. This table is organized by the execution periods of the models and balanced according to the load of each time step. Moreover, the slack time is distributed evenly among the steps to improve the real-time reliability. An extension to the algorithm for a multi-core environment is further studied to address those models with long execution times. Experimental results show that our scheduling algorithm outperforms the classical EDF approach. The highest performance improvement of TLS over EDF reaches 3–4% in terms of saving processor resources, and the jitter is about 4 times less when 90 entities are employed in a typical tank combat simulation scenario.     

一种新的网格环境模型——TGrid Model

在分析了现有网格环境不足的基础上,提出一种新的网格环境模型——基于树形结构的网格体系与环境TGrid,支持高性能计算,面向主题的资源共享和新一代的需求建模。它以树结构来组织网格节点和集成各种资源,实现了自底向上、多级、面向需求的资源抽象和多种资源融合。而且树型结构符合自然层次组织关系,容易实现网格系统的层次化管理,有利于减轻中心节点的负载和实现大规模应用的负载平衡,提高资源查找效率。同时,TGrid以虚拟资源的形式实现网格资源的共享,利用分布式JVM（TJVM）虚拟网格节点上CPU和主存资源,利用多数据库中间件（TDOD）实现数据库级资源集成和共享,利用Globus网格服务（GService）实现其他软件和数据资源共享。该树型网格为日益增长的网格应用的需求提供了新的解决方案。     

Agent-based load balancing on homogeneous minigrids: macroscopic modeling and characterization

In this paper, we present a macroscopic-characterization of agent-based load balancing in homogeneous minigrid environments. The agent-based load balancing is regarded as agent distribution from a macroscopic point of view. We study two quantities on minigrids: the number and size of teams where agents (tasks) queue. In macroscopic modeling, the load balancing mechanism is characterized using differential equations. We show that the load balancing we concern always converges to a steady state. Furthermore, we show that load balancing with different initial distributions converges to the same steady state gradually. Also, we prove that the steady state becomes an even distribution if and only if agents have complete knowledge about agent teams on minigrids. Utility gains and efficiency are introduced to measure the quality of load balancing. Through numerical simulations, we discuss the utility gains and efficiency of load balancing in different cases and give a series of analysis. In order to maximize the utility gain and the efficiency, we theoretically study the optimization of agents' strategies. Finally, in order to validate our proposed agent- based load balancing mechanism, we develop a computing platform, called simulation system for grid task distribution (SSGTD). Through experimentation, we note that our experimental results in general confirm our theoretical proofs and numerical simulation results from the proposed equation system. In addition, we find a very interesting phenomenon, that is, agent-based load balancing mechanism is topology-independent.