Load balancing algorithms based on gradient methods and their analysis through algebraic graph theory

The main results of this paper are based on the idea that most load balancing algorithms can be described in the framework of optimization theory. It enables to involve classical results linked with convergence, its speed and other elements. We emphasize that these classical results have been found independently and till now this connection has not been shown clearly. In this paper, we analyze the load balancing algorithm based on the steepest descent algorithm. The analysis shows that the speed of convergence is determined by eigenvalues of the Laplacian for the graph of a given load balancing system. This consideration also leads to the problems of choosing an optimal structure for a load balancing system. We prove that these optimal graphs have special Laplacians: the multiplicities of their minimal and maximal positive eigenvalues must be greater than one. Such a property is essential for strongly regular graphs, investigated in algebraic graph theory.     

Load balancing in project assignment

In this paper, we study a project assignment problem. Specifically, a set of projects, each of which needs to be finished over a project development cycle, are to be assigned to a group of identical engineers over a discrete planning horizon. The workload of the projects is different and fluctuates over their development cycles. In each period, engineers have a maximum allowed workload. The objective of the problem is to assign the projects to engineers with the objective of balancing the total workload among the engineers; the load balance is measured by the difference between the maximum and the minimum total workload. Such a problem is new to the literature. After proving the problem is strongly NP-hard, we propose a two-stage heuristic approach to solve it. Extensive numerical experiments show that the proposed approach can achieve optimal or nearly optimal solutions for all test cases; such performance is much better than what can be obtained from an IP model solved with ILOG CPLEX. An analysis of the algorithm has also been provided to explain how the superior performance has been achieved.     

Load balancing and data-management strategies in a multitenant database cluster

A multitenant database cluster is a data-storage subsystem for applications with multiclient architecture. Essentially, it may be regarded as an additional level of abstraction beyond the set of regular servers in relational databases. This approach permits effective operation in multiclient applications. Various management strategies for client data in a multitenant database cluster are compared. Simple strategies may be based on the client-base structure of the applications, while more complex strategies are based on special metrics. The comparison of the management strategies relies on simulation of the cluster. On the basis of experimental results, conclusions are formulated regarding the best data-management strategy.     

Load balancing in peer-to-peer systems using a diffusive approach

We developed a diffusive load balancing technique for P2P systems. This technique uses the overlay network of a P2P system and results in the nodes of the network having similar available capacities; therefore the services hosted on these nodes are expected to have similar mean response times. In this paper, the technique is presented, including the policies, stages of operation, and decision algorithms. The convergence of the available capacities to the global average is demonstrated. The convergence speed depends on the decision algorithm, the neighborhood structure of the underlying overlay network, and the workload distribution. When used in a system with churn, the technique keeps the standard deviation of available capacities in the system within a bound. This bound depends on the amount of churn and the frequency of the load balancing operations, as well as on the distribution of node capacities. However, the sizes of services have little impact on this bound. The paper presents the results of analytical analysis and simulation studies.     

Load balancing in large-scale RFID systems

A radio frequency identifier (RFID) system consists of inexpensive, uniquely-identifiable tags that are mounted on physical objects, and readers that track these tags (and hence these physical objects) through RF communication. For many performance measures in large-scale RFID systems, the set of tags to be monitored needs to be properly balanced among all readers. In this paper we, therefore, address this load balancing problem for readers — how should a given set of tags be assigned to readers such that the cost for monitoring tags across the different readers is balanced, while guaranteeing that each tag is monitored by at least one reader. We first present centralized solutions to two different variants of this load balancing problem: (i) min–max cost assignment (MCA), and (ii) min–max tag count assignment (MTA). We show that MCA, the generalized variant of the load balancing problem, is NP-hard and hence present a 2-approximation algorithm for it. We next present an optimal centralized solution for MTA, an important specialized variant of the problem. Subsequently, we present a localized distributed algorithm that is probabilistic in nature and closely matches the performance of the centralized algorithms. Finally we present detailed simulation results that illustrate the performance of the localized distributed approach, how it compares with the centralized optimal and near-optimal solutions, and how it adapts the solution with changes in tag distribution and reader topology. Our results demonstrate that our schemes achieve very good performance even in highly dynamic large-scale RFID systems.     

DiffServ MPLS网络中的负载平衡

简要介绍了多协议标记交换协议MPLS与区分服务DiffServ ,分析了MPLS与DiffServ相结合对网络的设计和控制带来的影响。并在此基础上 ,提出了一种动态负载平衡的方法 ,将DiffServ几种业务在多条LSP上平衡传输。仿真试验表明 ,大大降低了延迟和队长 ,提高了吞吐量     

DiffSerwMPLS网络中的负载平衡

简要介绍了多协议标记交换协议MPLS与区分服务DiffServ，分析了MPLS与DiffServ相结合对网络的设计和控制带来的影响。并在此基础上，提出了一种动态负载平衡的方法，将DiffServ几种业务在多余LSP上平衡传输。仿真试验表明，大大降低了延迟和队长，提高了吞吐量。     

Dynamic average consensus with topology balancing under a directed graph

In this paper, the distributed average tracking problem is studied on the premise of a strongly connected directed graph. To this end, we propose a weight balance strategy that could potentially make the adjacency matrix doubly stochastic for any strongly connected directed graph. The proposed scheme is fully distributive with finite time convergence and we again prove that network connectivity (described by the first left eigenvector) is instrumental in networked control systems. Then, a discrete‐time average tracking observer is introduced to ensure that all networked systems can track the average of the reference signals with bounded error. Simulation results verify the effectiveness of the proposed methods.     

基于负载均衡的簇间路由协议

针对无线传感器网络簇头节点负载不均衡的问题,提出一种基于负载均衡的簇间路由协议.该协议通过记录邻居簇头节点到Sink节点的最小跳数信息建立到Sink节点的多条路径,根据簇节点的剩余能量和负载选择合适的路径进行路由,从而实现了簇头节点间的负载均衡.仿真实验结果表明,该路由协议能有效地均衡网络负载和簇头节点能量消耗,减少数据传输延迟,延长网络生存时间.     

基于流量均衡装置的负载均衡VOD系统及仿真

为了满足园区网VOD系统日益增长的用户点播需求,提出一种负载均衡VOD方案.该方案通过在VOD系统中添加多个新型网络设备--流量均衡装置,在用户汇聚点形成存储矩阵及服务矩阵以提供热门节目的点播服务,并根据网络状况和用户点播情况对矩阵拓扑进行动态调整,实现流量均衡装置的负载均衡及全局的流量均衡,从而大大提高了并发服务能力.仿真结果表明,该方案的实施效果良好,可广泛应用于园区网VOD系统的建设与改造.     

Load balancing of parallelized information filters

We investigate the data-parallel implementation of a set of "information filters" used to rule out uninteresting data from a database or data stream. We develop an analytic model for the costs and advantages of load rebalancing for the parallel filtering processes, as well as a quick heuristic for its desirability. Our model uses binomial models of the filter processes and fits key parameters to the results of extensive simulations. Experiments confirm our model. Rebalancing should pay off whenever processor communications costs are high. Further experiments showed it can also pay off even with low communications costs for 16-64 processes and 1-10 data items per processor; then, imbalances can increase processing time by up to 52 percent in representative cases, and rebalancing can increase it by 78 percent, so our quick predictive model can be valuable. Results also show that our proposed heuristic rebalancing criterion gives close to optimal balancing. We also extend our model to handle variations in filter processing time per data item     

一种平衡负载的分布式动态型微移动管理方案

目前微移动管理方案大多是采用分层的原则,在子域外设置一个外地管理代理（FMA）作为区域代理。移动主机（MH）在域内进行移动时只需向FMA进行注册,而对家乡代理（HA）透明。为了弥补MH数量过多而导致的FMA负载过大的缺陷,提出了一种平衡负载的分布式动态型微移动管理方案。该方案在网络中放置多个区域移动代理来实现分布式的域内主机移动管理,并采用一种由网络根据自身的负载情况动态地选择区域移动代理的算法。该算法有效避免了传统方案中FMA在MH数量过多时负载过大的问题,且没有对网络拓扑结构和区域移动代理的位置做任何强制性要求。分析和仿真均表明,当主机数量快速递增时网络的负载平衡状况得到了改善。     

Load balancing schemes for extrapolation methods

Solving initial value problems (IVPs) for ordinary differential equations (ODEs) has long been believed to be an inherently sequential procedure. But IVP solvers using the extrapolation method provide high quality solutions and offer a great potential for parallelism. In this paper, we present algorithms for extrapolation methods on distributed memory multiprocessors that combine different levels of parallelism. These algorithms differ mainly in the partitioning of the processors into groups which are responsible for the execution of the independent tasks of the extrapolation method. We present the algorithms in a compute–communicate scheme using appropriate primitives for the communication. A detailed analysis shows that a sophisticated load balancing scheme is required to achieve good speedup. We describe an optimal method based on Lagrange multipliers, investigate several simple heuristic schemes, and compare the heuristic schemes with an estimation for the optimal solution. An implementation of these schemes on an Intel iPSC\860 confirms the predicted runtimes. © 1997 by John Wiley & Sons, Ltd.     

一种多集群网格的负载均衡算法

网格环境由于其可扩展性、异构性以及大量的传输延迟,使得网格环境下的负载均衡不同于传统的分布式系统。提出了一种动态的分布式负载均衡算法,该算法综合考虑网格站点的处理能力和站点之间的传输延迟,采用即时分配策略来降低作业的执行成本,目标是使系统平均作业响应时间最小化。仿真结果显示该算法显著减少了作业的平均响应时间。     

A note on graph balancing problems with restrictions

We consider the graph balancing problem of providing orientations to edges in an undirected multi-graph to minimize the maximum load. We first obtain an FPTAS when the multi-graph is restricted to a tree. We also obtain some additional results for other restricted cases by showing equivalencies with related combinatorial problems.     

Load balancing and ordered selections in a computer system with multiple contention buses

In this paper, we study an efficient scheme for disseminating status information in a distributed computer system connected by multiple contention buses. Such a scheme is critical in resource sharing and load balancing applications. The collection of status information in these systems usually incurs a large overhead, which may impede regular message traffic and degrade system performance. Moreover, the status information collected may be outdated due to network delays. We describe our scheme with respect to the load balancing problem, although the scheme developed applies to resource sharing applications in general. We first reduce the decision problem for job migration in a system with multiple contention buses to the ordered-selection problem. A heuristic multiwindow protocol that utilizes the collision-detection capability of these buses is proposed and analyzed. The proposed protocol does not require explicit message transfers and can identify the t smallest variates out of N distributed random variates in an average of approximately (0.8 log₂t + 0.2 log₂N + 1.2) contention steps.     

基于对象存储的负载均衡存储策略

对象存储文件系统中将大数据文件分片存储到多个存储节点上,以获取更好的并行I/O性能,提高系统吞吐率.现有对象存储文件系统的存储策略并未充分考虑存储对象本身负载的动态变化,不利于提高系统资源利用率.针对此问题,考虑存储对象的空间及I/O等负载实时变化,提出了一种简单、灵活、高效的负载均衡存储策略,并对该策略进行了实现.实验结果表明,该策略能有效提高对象存储系统资源的利用率和吞吐率,保证对象存储文件系统高效的读写性能.     

Load balancing and OpenMP implementation of nested parallelism

Many problems have multiple layers of parallelism. The outer-level may consist of few and coarse-grained tasks. Next, each of these tasks may also be rich in parallelism, and be split into a number of fine-grained tasks, which again may consist of even finer subtasks, and so on. Here we argue and demonstrate by examples that utilizing multiple layers of parallelism may give much better scaling than if one restricts oneself to only one level of parallelism.Two non-trivial issues for multi-level parallelism are load balancing and implementation. In this paper we provide an algorithm for finding good distributions of threads to tasks and discuss how to implement nested parallelism in OpenMP.