On load balancing for distributed multiagent computing

Multiagent computing on a cluster of workstations is widely envisioned to be a powerful paradigm for building useful distributed applications. The agents of the system span across all the machines of a cluster. Just like the case of traditional distributed systems, load balancing becomes an area of concern. With different characteristics between ordinary processes and agents, it is both interesting and useful to investigate whether conventional load-balancing strategies are also applicable and sufficient to cope with the newly emerging needs, such as coping with temporally continuous agents, devising a performance metric for multiagent systems, and taking into account the vast amount of communication and interaction among agent. This paper discusses the above issues with reference to agent properties and load balancing techniques and outlines the space of load-balancing design choices in the arena of multiagent computing. In view of the special agent characteristics, a novel communication-based load-balancing algorithm is proposed, implemented, and evaluated. The proposed algorithm works by associating a credit value with each agent. The credit of an agent depends on its affinity to a machine, its current workload, its communication behavior, and mobility, etc. When a load imbalance occurs, the credits of all agents are examined and an agent with a lower credit value is migrated to relatively lightly loaded machine in the system. Quasi-simulated experiments of this algorithm show load-balancing improvement compared with conventional workload-oriented load-balancing schemes.     

Static and decentralized-adaptive load balancing in a starconfigured distributed computing system

The problem of minimizing the average job response time (sojourn time) in a star configured distributed computing system (DCS) with N peripheral processors and one central processor is studied. Each peripheral processor (satellite) receives a stream of Poisson arrivals. A job arriving at a satellite S_i will be processed with a probability (1-P_i) by itself and routed to the central site for remote processing with probability P_i. The service time distribution at each processor is arbitrary with means 1/μ_i and second moments E[Y_i²], i=0,…,N. We first develop an algorithm to compute the optimal routing probabilities when the arrival and the service parameters are known a priori. We then develop an adaptive estimator to be used by each satellite to compute its optimal routing probability, when the parameters (everywhere) are unknown a priori, a copy of the algorithm runs on each peripheral processor and uses the sojourn time measurements that the peripheral processor can gather on its own from those jobs that are sent to the central processor and returned to the originating site after service     

A load balanced distributed computing system

The main objective of this study is to transform a network of workstations into a load balanced distributed computing system (LBDCS). LBDCS is to improve the performance of generally underutilized timeshared workstations and highly CPU intensive independent or parallel applications. It affects the initial placement of the tasks and task migrations later during their executions. One of the important implementation features of LBDCS is that it does not use any intermediary such as PVM (parallel virtual machine) or MPI (message passing interface) for inter-task communication. It defines various metrics to characterize the level of load and dynamically monitors the system and applications to detect the load imbalances. The employed load balancing algorithm makes use of predicted load indices which are computed as weighted averages of the past system and application loads. Performance analysis of the system has been conducted using a number of hypothetical applications and two simple real life applications (in this case matrix multiplication and merge-sort). Hypothetical applications provide flexibility for testing the system under tunable application conditions. Using load balancing, an average speedup and efficiency close to 70% of their theoretical upper bounds are observed for different applications. Copyright © 1999 John Wiley & Sons, Ltd.     

Parallel computing with load balancing on heterogeneous distributed systems

In the present work, the parallelization of the solution of a system of linear equations, in the framework of finite element computational analyses, is dealt with. As the substructuring method is used, the basic idea refers to a way of decomposing the considered spatial domain, discretized by the finite elements, into a finite set of non-overlapping subdomains, each assigned to an individual processor and computationally analysed in parallel. Considering the fact that Personal Computers and Work Stations are still the most frequently used computers, a parallel computational platform can be built by connecting the available computers into a computer network. The incorporated computers being usually of different computational power and memory size, the efficiency of parallel computations on such a heterogeneous distributed system depends mainly on proper load balance. To cope the balance problem, an algorithm for the efficient load balance for structured and free 2D quadrilateral finite element meshes based on the rearrangement of elements among respective sub-domains, has been developed.     

A hierarchical adaptive distributed algorithm for load balancing

Load balancing/sharing exploits the communication facility between the servers of a distributed system, by using the exchanging of status information and jobs between any two servers of the system in order to improve the overall performance.We propose an adaptive distributed hierarchical scheme, the Virtual Tree Algorithm (VTA), which creates a virtual binary tree structure over the actual network topology. It uses the difference-initiated (DI) technique for load balancing, which needs remote information for the transfer policy and no additional information for the location policy. We demonstrate that the introduced virtual construction keeps the exchanged messages to relatively low levels. To evaluate the performance of our policy, we present both theoretical and simulation results. By using simulation, we compare our results with one of the most representative, adaptive, symmetrical and efficient algorithms, the Variable Threshold (V_THR) algorithm.     

A Dynamic Load Balancing Mechanism for Distributed Systems

It is desirable in a distributed system to have the system load balanced evenly among the nodes so that the mean job response time is minimized.In this paper,we present a dynamic load balancing mechanism(DLB).It adopts a cntralized approach and is network topology independent.The DLB mechanism employs a set of threscholds which are automatically adjusted as the system load changes.It also provides a simple mechanism for the system to switch between periodic and instantaneous load balancing policies with ease.The performance of the proposed algorithm is evaluated by intensive simulations for various parameters.Te simulation results show that the mean job response time in a system implementing DLB algorithm is significantly lower than the same system without load balancings.Furthermore,compared with a previously proposed algorithm,DLB algorithm demonstrates improved performance,especially when the system is heavily loaded and the load is unevenly distributed.     

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

根据分布式系统的静态和动态负载均衡策略的优缺点,提出了在网格计算环境下的混合负载均衡策略.为了让网络中节点在网格计算环境中有效地执行需要大量计算的复杂任务,提出了用来评估节点效率的函数,并结合模拟实验证实了在此函数下算法的优越性.     

基于逐跳计算的分布式负载均衡算法

网络中流量的不断增长容易导致流量不均衡、网络拥塞,进而影响用户的体验。因特网服务提供商（ISP）通常采用优化开放最短路径优先（OSPF）权值（OPW）算法应对网络拥塞,然而该算法存在三个方面的问题：1）需要实际流量矩阵;2）容易导致网络震荡;3）OPW已经被证实为NP难题,并且需要采用集中式方法求解。针对OPW算法存在的问题,提出了一种基于逐跳计算的分布式负载均衡算法（DLBH）。首先,为所有节点设置虚拟流量;然后,根据虚拟流量计算所有链路的代价;最后,采用分布式算法计算最优路由。DLBH采用分布式方法解决网络拥塞问题,而OPW只能采用集中式方法解决网络拥塞问题,因此DLBH的扩展性优于OPW的扩展性。理论分析表明,DLBH的时间复杂度远远小于OPW的时间复杂度。实验结果表明,DLBH的最大链路利用率明显低于OPW算法的最大链路利用率,大幅降低了网络拥塞。     

一种基于负载反馈的分布式数字集群动态负载均衡算法

针对传统负载均衡算法不能满足公网数字集群系统高并发用户请求和快速呼叫建立等需求,提出一种基于负载反馈的分布式数字集群动态负载均衡算法,实现公网数字集群系统负载均衡,提高用户容量。首先建立参与MCPTT服务器的静态负载和动态负载监控机制和指标;然后利用加权轮询算法为用户分配参与MCPTT服务器,并通过用户请求的处理获得复合负载参数;根据负载指标的反馈更新参与MCPTT服务器权值以动态调整服务器负载。仿真结果表明,该算法的负载均衡效果优于传统算法和其他动态反馈算法,负载均衡度更小、用户请求响应延迟更低。     

A framework of auto-adapting distributed object for mobile computing

The low bandwidth hinders the development of mobile computing.Besides providing relatively higher bandwidth on communication layer,constructing adaptable upper application is important.In this paper,a framework of autoadapting distributed object is proposed,and evaluating methods of object performance are given as well.Bistributed objects can abjust their behaviors automatically in the framework and keep in relatively good performance to serve requests of remote applications.It is an efficient way to implement the performance transparency for mobile clients.     

改进粒子群算法在云计算负载均衡中的应用研究

云计算系统采用虚拟化技术可以更加灵活和高效地分配运算资源,便于管理员根据用户任务需求按需分配云计算资源。但虚拟化后的云计算中心存在种类多样、数量庞大的虚拟机资源,难以将虚拟机合理地放置到物理主机集群上并达到较好的负载均衡。为此,给出了云计算中心虚拟机放置到物理主机的负载均衡模型,采用改进后的粒子群算法（PSO）来求解最优解。最后通过和常用虚拟机放置算法的仿真对比实验,验证了所提云计算负载均衡优化算法的有效性。     

A bipartite model for load balancing in grid computing environments

In this paper, a bipartite model for load balancing (LB) in grid computing environments, called Transverse viewpoint-based Bi-Tier model (TBT), is proposed. TBT can efficiently eliminate topology mismatching between overlay- and physical-networks during the load transfer process. As an implementation of TBT, a novel LB policy called M²ON (Min-cost and Max-flow Channel based Overlay Network) is presented. In M²ON, the communication capability is denoted as M²C (Min-cost and Max-flow Channel) which is obtained using a Labeled Tree Probing (LTP) method. The computing capacity is denoted as the Idle Factor (IF) which is obtained from the semantic overlay. The higher- and lower-level characteristics are combined into an Integrated Impacting Factor (IIF) using a Double Linear Inserting (DLI) function. Based on IIF, optimal topology matching can be achieved in the LB process. Extensive experiments and simulations have been performed and will be discussed. The results show that M²ON achieves more accurate topology matching with a minimum increment in the overall locating time yet achieving higher system performance as a whole.     

A bipartite model for load balancing in grid computing environments

In this paper, a bipartite model for load balancing (LB) in grid computing environments, called Transverse viewpoint-based Bi-Tier model (TBT), is proposed. TBT can efficiently eliminate topology mismatching between overlay- and physical-networks during the load transfer process. As an implementation of TBT, a novel LB policy called M²ON (Min-cost and Max-flow Channel based Overlay Network) is presented. In M²ON, the communication capability is denoted as M²C (Min-cost and Max-flow Channel) which is obtained using a Labeled Tree Probing (LTP) method. The computing capacity is denoted as the Idle Factor (IF) which is obtained from the semantic overlay. The higher- and lower-level characteristics are combined into an Integrated Impacting Factor (IIF) using a Double Linear Inserting (DLI) function. Based on IIF, optimal topology matching can be achieved in the LB process. Extensive experiments and simulations have been performed and will be discussed. The results show that M²ON achieves more accurate topology matching with a minimum increment in the overall locating time yet achieving higher system performance as a whole.     

Game-theoretic static load balancing for distributed systems

In this paper, we present a game theoretic approach to solve the static load balancing problem for single-class and multi-class (multi-user) jobs in a distributed system where the computers are connected by a communication network. The objective of our approach is to provide fairness to all the jobs (in a single-class system) and the users of the jobs (in a multi-user system). To provide fairness to all the jobs in the system, we use a cooperative game to model the load balancing problem. Our solution is based on the Nash Bargaining Solution (NBS) which provides a Pareto optimal solution for the distributed system and is also a fair solution. An algorithm for computing the NBS is derived for the proposed cooperative load balancing game. To provide fairness to all the users in the system, the load balancing problem is formulated as a non-cooperative game among the users who try to minimize the expected response time of their own jobs. We use the concept of Nash equilibrium as the solution of our non-cooperative game and derive a distributed algorithm for computing it. Our schemes are compared with other existing schemes using simulations with various system loads and configurations. We show that our schemes perform near the system optimal schemes and are superior to the other schemes in terms of fairness.     

Cooperative distributed dynamic load balancing

Summary This paper explores and applies the concept of cooperation to the load balancing problem in a computer network. We discuss an analytical model and propose a scheme which can be classified as distributed, dynamic, and stochastic. In the case of a homogeneous network, we guarantee that the load is balanced and no communication cost or information exchange is necessary.     

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.     

云计算下负载均衡的多维QoS约束任务调度机制

高效的任务调度机制能够更好地满足用户的QoS需求,实现各物理主机间的负载均衡,从而提高云计算环境的整体性能。而传统的任务调度往往只考虑任务的响应时间或安全性等,且负载均衡策略是静态的。根据云计算的弹性化和虚拟化等新特性,综合考虑任务的性能QoS和信任QoS,提出一种在云计算环境下的任务调度机制,采用虚拟机迁移技术实现动态负载均衡。通过在CloudSim2.1仿真环境下的分析和比较,该任务调度机制不但可以提高用户满意度,而且可以有效实现负载均衡。     

分布式数据库系统的动态负载平衡策略及算法设计

随着网络中数据库应用的发展,使得分布式数据库系统的负载平衡问题突显出来。目前大多数分布式数据库管理系统没有负责平衡功能,其负载平衡依赖于操作系统的负载平衡机制来解决,这样带来的问题是系统负载的评价粒度细小和负载转移的开销增加。讨论了动态负载平衡策略的要素,针对分布式数据库系统的负载平衡问题,提出了以事务队列长度作为负载评价标准,并给出了一个动态负载平衡策略及算法。     

A self‐organized load balancing mechanism for cloud computing

The growth in computer and networking technologies over the past decades established cloud computing as a new paradigm in information technology. The cloud computing promises to deliver cost‐effective services by running workloads in a large scale data center consisting of thousands of virtualized servers. The main challenge with a cloud platform is its unpredictable performance. A possible solution to this challenge could be load balancing mechanism that aims to distribute the workload across the servers of the data center effectively. In this paper, we present a distributed and scalable load balancing mechanism for cloud computing using game theory. The mechanism is self‐organized and depends only on the local information for the load balancing. We proved that our mechanism converges and its inefficiency is bounded. Simulation results show that the generated placement of workload on servers provides an efficient, scalable, and reliable load balancing scheme for the cloud data center. Copyright © 2016 John Wiley & Sons, Ltd.