A repartitioning hypergraph model for dynamic load balancing

In parallel adaptive applications, the computational structure of the applications changes over time, leading to load imbalances even though the initial load distributions were balanced. To restore balance and to keep communication volume low in further iterations of the applications, dynamic load balancing (repartitioning) of the changed computational structure is required. Repartitioning differs from static load balancing (partitioning) due to the additional requirement of minimizing migration cost to move data from an existing partition to a new partition. In this paper, we present a novel repartitioning hypergraph model for dynamic load balancing that accounts for both communication volume in the application and migration cost to move data, in order to minimize the overall cost. The use of a hypergraph-based model allows us to accurately model communication costs rather than approximate them with graph-based models. We show that the new model can be realized using hypergraph partitioning with fixed vertices and describe our parallel multilevel implementation within the Zoltan load balancing toolkit. To the best of our knowledge, this is the first implementation for dynamic load balancing based on hypergraph partitioning. To demonstrate the effectiveness of our approach, we conducted experiments on a Linux cluster with 1024 processors. The results show that, in terms of reducing total cost, our new model compares favorably to the graph-based dynamic load balancing approaches, and multilevel approaches improve the repartitioning quality significantly.     

一种基于负载平衡的网络接入选择方法

针对异构无线环境,提出了一种基于负载平衡的网络选择算法。采用"终端辅助,网络决策"的策略,首先利用修正权重后的层次分析法得到网络参考向量,然后终端用户根据向量间的几何关系挑选出可接入网络集合,最后网络侧基于负载平衡的前提下为终端用户选择最终接入网络。通过仿真对比,验证了该算法的有效性。     

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 decomposition algorithm for optimal static load balancing in treehierarchy network configurations

We study the static load balancing problem in a distributed computer system with the tree hierarchy configuration. It is formulated as a nonlinear optimization problem. After studying the conditions that the solution to the optimization problem of the tree hierarchy network satisfies, we demonstrate that the special structure of the optimization problem leads to an interesting decomposition technique. A new effective decomposition algorithm to solve the optimization problem is presented. The proposed algorithm Is compared with two other well known algorithms: the Flow Deviation (FD) algorithm and the Dafermos-Sparrow (D-S) algorithm. It is shown that the amounts of the storage required for the proposed algorithm and the FD algorithm are O(n) for load balancing of an n-node system. However, the amount of the storage required for the D-S algorithm is O(n log(n)). By using numerical experiments, we show that both the proposed algorithm and the D-S algorithm have much faster convergence in terms of central processing unit (CPU) time than the FD algorithm     

基于OpenFlow的数据中心网络负载均衡算法

现代数据中心网络(Date Center Network,DCN)经常会使用多路径(Multi Path,MP)拓扑结构,这样可以避免两节点间某条链路失效而导致的网络拥塞问题,而且增加了网络的带宽和容错率。传统的OSPF(Open Shortest Path First)路由算法会选择单条最短路径作为最终路径,这样可能会导致大部分数据流集中在单一路径上而出现网络拥塞,而其他可用路径处于闲置状态,不能充分地利用DCN中的链路资源,基于SDN(Software Defined Network)的集中化的调度方式能够提高网络利用效率。设计了一套基于Open Flow协议的链路负载均衡模型,详细阐述了它的总体框架和算法实现过程,并通过实验仿真验证了算法的可行性和有效性。     

Autonomic load balancing of flow monitors

In monitoring flows at routers for flow analysis or deep packet inspection, the monitor calculates hash values from the flow ID of each packet arriving at the input port of the router. Therefore, the monitors must update the flow table at the transmission line rate, so high-speed and high-cost memory, such as SRAM, is used for the flow table. This requires the monitors to limit the monitoring target to just some of the flows. However, if the monitors randomly select the monitoring targets, multiple routers on the route will sometimes monitor the same flow, or no monitors will monitor a flow. To maximize the number of monitored flows in the entire network, the monitors must select the monitoring targets while maintaining a balanced load among them. We propose an autonomous load-balancing method where monitors exchange information on monitor load only with adjacent monitors. Numerical evaluations using the actual traffic matrix of Internet2 show that the proposed method improves the total monitored flow count by about 50% compared with that of independent sampling. Moreover, we evaluate the load-balancing effect on 36 backbone networks of commercial ISPs.     

An asynchronous and iterative load balancing algorithm for discrete load model

Diffusion algorithms are some of the most popular algorithms for dynamic load balancing in which loads move from heavily loaded processors to lightly loaded neighbor processors. To achieve a global load balance in a parallel computer, the algorithm is iterated until the load difference between any two processors is smaller than a specified value. Therefore, one fundamental property to be studied is algorithm convergence. Several analytical works on the convergence of different diffusion load balancing algorithms have been carried out, but they treat loads as non-negative real quantities. In this paper, we describe the Diffusion Algorithm Searching Unbalanced Domains (DASUD) algorithm, which uses loads as non-negative integer values and, unlike existing algorithms, reaches a local balance situation where the maximum load difference between any two processor in the set of neighbor processors for each processor is one load unit. The convergence property of an asynchronous implementation of DASUD using integer loads is proven theoretically.     

A case for on-machine load balancing

This paper diverges from the traditional load balancing, and introduces a new principle called the on-machine load balance rule. The on-machine load balance rule leads to resource allocations that are better in tolerating uncertainties in the processing times of the tasks allocated to the resources when compared to other resource allocations that are derived using the conventional “across-the-machines” load balancing rule. The on-machine load balance rule calls for the resource allocation algorithms to allocate similarly sized tasks on a machine (in addition to optimizing some primary performance measures such as estimated makespan and average response time). The on-machine load balance rule is very different from the usual across-the-machines load balance rule that strives to balance load across resources so that all resources have similar finishing times.We give a mathematical justification for the on-machine load balance rule requiring only liberal assumptions about task processing times. Then we validate with extensive simulations that the resource allocations derived using on-machine load balance rule are indeed more tolerant of uncertain task processing times.     

网络计算机集群负载均衡机制的研究

目前使用单台网络计算机应用服务器难以满足大量用户的并发访问需求,在网络计算机系统中引入集群/负载均衡技术是解决这一问题的理想途径.研究网络计算机集群的负载均衡机制.设计和实现了适合于网络计算机应用模式的负载评估方法及负载状态更新机制,并在此基础上提出和实现了一种基于分布式协商的动态负载均衡算法.     

Perfect load balancing on the star interconnection network

In this paper, we use the regular distribution method to design a perfect load balancing algorithm for an n-star with a maximum error of 1 and a time complexity of 3n(n+1). This algorithm is based on the novel notion of leader trees. A second algorithm proposed in this paper as an enhancement to our first algorithm and uses an arbitrary spanning tree as the leader tree and has a worst time complexity of 2.25n ²−3n+0.75. We also discuss the issue of dynamically selecting the leader tree and hybrid load balancing algorithms in general. Furthermore, we present a hybrid algorithm for load balancing on the star interconnection network which benefits from a diffusion load balancing preprocessing phase and shows a smaller mean time complexity than our two first algorithms.     

A load index and load balancing algorithm for heterogeneous clusters

This paper presents a load balancing algorithm specifically designed for heterogeneous clusters, composed of nodes with different computational capabilities. The method is based on a new index, which takes into consideration two levels of processors heterogeneity: the number of cores per node and the computational power of each core. The experimental results show that this index allows achieving balanced workload distributions even on those clusters where heterogeneity can not be neglected.     

A model for communication between resource discovery and load balancing units in computing environments

Resource overloading causes one of the main challenges in computing environments. In this case, a new resource should be discovered to transfer the extra load. However, this results in drastic performance degradation. Thus, it is of high importance to discover the appropriate resource at first. So far, several resource discovery mechanisms have been introduced to overcome this challenge, a majority of which neglect the fact that this important decision should be made in cooperation with other units existing in a computing environment. One of the units is load balancing. In this paper, we propose a model for communication between resource discovery and load balancing units in a computing environment. Based on the model, resource discovery and load balancing decisions are made cooperatively considering the behavior of running processes and resources capacities. These considerations make decisions more precise. In addition, the model presents the loosest type of coupling between resource discovery and load balancing units, i.e., message coupling. This feature provides a better scalability in size for the model. Comparative results show that the proposed model increases scalability in size by 7 to 15 %, cuts message transmission rate by 15 % and improves hit rate by 51 %.     

The probability of load balancing success in a homogeneous network

The problem of load balancing in distributed systems composed of several homogeneous sites connected by a subnet is examined. The author determines a general formula for the probability that any one site in the system is underloaded while some other site in the system is overloaded. This probability can be used to define the likelihood of load balancing success in a distributed operating system. This probability gives insight into the utilization of the system and is an aid in determining a measure of effectiveness of the system. From this formula one can determine this probability when the workload is composed of processes typical to distributed systems. The influence of variants in the load balancing algorithm on this probability is demonstrated     

A hybrid column generation with GRASP and path relinking for the network load balancing problem

In this paper, a hybrid meta-heuristic is proposed which combines the GRASP with path relinking method and Column Generation. The key idea of this method is to run a GRASP with path relinking search on a restricted search space, defined by Column Generation, instead of running the search on the complete search space of the problem. Moreover, column generation is used not only to compute the initial restricted search space but also to modify it during the whole algorithm. The proposed heuristic is used to solve the network load balancing problem: given a capacitated telecommunications network with single path routing and an estimated traffic demand matrix, the network load balancing problem is the determination of a routing path for each traffic commodity such that the network load balancing is optimized, i.e., the worst link load is minimized, among all such solutions, the second worst link load is minimized, and continuing in this way until all link loads are minimized. The computational results presented in this paper show that, for the network load balancing problem, the proposed heuristic is effective in obtaining better quality solutions in shorter running times.     

支持动态负载平衡的分层消息队列模型

中间件技术为解决异构分布式环境下的负载平衡问题提供了有力的工具,但传统的消息中间件负载平衡的实现较为复杂,其动态参数繁多且容易带来额外开销。提出了一种分层消息队列模型,该模型中利用队列组管理器对分布式队列进行组管理,并提供了丰富的任务分配策略。在该模型的基础上提出动态负载平衡实现方案:通过基于队列的阈值阈长模型实时监控成员队列的负载情况,采用集中式调度进行负载信息搜集和负载平衡决策,结合负载迁移和队列组管理进行过载处理。     

Agent scheduling model for adaptive dynamic load balancing in agent-based distributed simulations

Agent-based distributed simulations are confronted with load imbalance problem, which significantly affects simulation performance. Dynamic load balancing can be effective in decreasing simulation execution time and improving simulation performance. The characteristics of multi-agent systems and time synchronization mechanisms make the traditional dynamic load balancing approaches not suitable for dynamic load balancing in agent-based distributed simulations. In this paper, an adaptive dynamic load balancing model in agent-based distributed simulations is proposed. Due to the complexity and huge time consuming for solving the model, a distributed approximate optimized scheduling algorithm with partial information (DAOSAPI) is proposed. It integrates the distributed mode, approximate optimization and agent set scheduling approach. Finally, experiments are conducted to verify the efficiency of the proposed algorithm and the simulation performance under dynamic agent scheduling. The experiments indicate that DAOSPI has the advantage of short execution time in large-scale agent scheduling, and the distributed simulation performance under this dynamic agent scheduling outperforms that under static random agent distribution.     

Scheduling of thermal units with a nonlinear load flow network model

We describe a formulation of the thermal unit commitment problem that includes AC network constraints, which allows taking into account VAr production as a criterion for generator commitment for the first time. The formulation makes it possible to use the Lagrangian Relaxation technique as a solution algorithm even though the network constraints are not linear. Although the solution method is computationally intensive, the problem exhibits a separation structure and a price coordination schedule that suggest several ways of improving the performance. Preliminary test results are reported.     

一种动态的客户端负载均衡机制

互联网应用的并发用户数量不仅多变并且这种变化常常不可预测.将系统容量配置为固定值的惯用做法在面临多变的请求时常常会导致两种结果,一种是因为配置过低而引起用户的不满,另一种则因为配置过高而造成计算资源的浪费.而通过运用云架构按需提供、按使用收费的能力,系统具有了实时地按需配置计算资源的能力.然而静态的客户端负载均衡方法作为一种主要的负载均衡技术很难适应云架构条件下更加易变的集群结构.本文提出了一种动态的客户端负载均衡机制.通过引入分布式的集群视图更新、控制流等技术,该机制在保持客户端负载均衡机制分布式、可伸缩性强的基础上,又为集群节点的动态加入与退出和负载均衡策略的动态调整提供了有效的支持.同时,本文分析了该机制在一个开源JEE应用服务器PKUAS中的关键实现问题,并通过实验从多方面验证了该机制的有效性.