浅谈网络负载均衡

通畅的网络是在一个网络的负载均衡的条件下建立的,他的存在可以说是给整个网络的性能优良打下了基础,他的建立使网络的透明化、高效化、廉价化进入了一个成熟阶段,这位网络的进一步升级提供了非常方便的服务途径,网络的带宽、吞吐量都和网络的数据处理水平都能得到优化,这样便建立了一个成熟、灵活和可靠的网络。     

Application of load balancing based on symmetric balanced incomplete block design to random networks

In a load balancing algorithm [O. Lee, M. Anshel, I. Chung, Design of an efficient load balancing algorithm on distributed networks by employing symmetric balanced incomplete block design, IEE Proceedings - Communications 151 (6) (2004) 535-538] based on the SBIBD (Symmetric Balanced Incomplete Block Design), each node receives global workload information by only two round message exchange with traffic overhead, where v is the number of nodes. It is very efficient and works well only when v=p²+p+1 is used for a prime number p. In this paper, we generated a special incidence structure using the SBIBD and then propose a new load balancing algorithm, which executes well for an arbitrary number of nodes. To accomplish this, we add a number of links to nodes in order for each node to receive more than 80% of the workload information by two round message exchange. For performance of our algorithm, we carried out an experiment for the number of nodes, w, which was up to 5000. Traffic overhead is less than in a round and standard deviation of traffic overhead shows that each node has a mostly well-balanced amount of traffic.     

Enhancing self-scheduling algorithms via synchronization and weighting

Existing dynamic self-scheduling algorithms, used to schedule independent tasks on heterogeneous clusters, cannot handle tasks with dependencies because they lack the support for internode communication. To compensate for this deficiency we introduce a synchronization mechanism that provides inter-processor communication, thus, enabling self-scheduling algorithms to handle efficiently nested loops with dependencies. We also present a weighting mechanism that significantly improves the performance of dynamic self-scheduling algorithms. These algorithms divide the total number of tasks into chunks and assign them to processors. The weighting mechanism adapts the chunk sizes to the computing power and current run-queue state of the processors. The synchronization and weighting mechanisms are orthogonal, in the sense that they can simultaneously be applied to loops with dependencies. Thus, they broaden the application spectrum of dynamic self-scheduling algorithms and improve their performance. Extensive testing confirms the efficiency of the synchronization and weighting mechanisms and the significant improvement of the synchronized–weighted versions of the algorithms over the synchronized-only versions.     

One-dimensional partitioning for heterogeneous systems: Theory and practice

We study the problem of one-dimensional partitioning of nonuniform workload arrays, with optimal load balancing for heterogeneous systems. We look at two cases: chain-on-chain partitioning, where the order of the processors is specified, and chain partitioning, where processor permutation is allowed. We present polynomial time algorithms to solve the chain-on-chain partitioning problem optimally, while we prove that the chain partitioning problem is NP-complete. Our empirical studies show that our proposed exact algorithms produce substantially better results than heuristics, while solution times remain comparable.     

Optimal replica placement in hierarchical Data Grids with locality assurance

In this paper, we address three issues concerning data replica placement in hierarchical Data Grids that can be presented as tree structures. The first is how to ensure load balance among replicas. To achieve this, we propose a placement algorithm that finds the optimal locations for replicas so that their workload is balanced. The second issue is how to minimize the number of replicas. To solve this problem, we propose an algorithm that determines the minimum number of replicas required when the maximum workload capacity of each replica server is known. Finally, we address the issue of service quality by proposing a new model in which each request must be given a quality-of-service guarantee. We describe new algorithms that ensure both workload balance and quality of service simultaneously.     

Dynamic load balancing with adaptive factoring methods in scientific applications

To improve the performance of scientific applications with parallel loops, dynamic loop scheduling methods have been proposed. Such methods address performance degradations due to load imbalance caused by predictable phenomena like nonuniform data distribution or algorithmic variance, and unpredictable phenomena such as data access latency or operating system interference. In particular, methods such as factoring, weighted factoring, adaptive weighted factoring, and adaptive factoring have been developed based on a probabilistic analysis of parallel loop iterates with variable running times. These methods have been successfully implemented in a number of applications such as: N-Body and Monte Carlo simulations, computational fluid dynamics, and radar signal processing. The focus of this paper is on adaptive weighted factoring (AWF), a method that was designed for scheduling parallel loops in time-stepping scientific applications. The main contribution of the paper is to relax the time-stepping requirement, a modification that allows the AWF to be used in any application with a parallel loop. The modification further allows the AWF to adapt to load imbalance that may occur during loop execution. Results of experiments to compare the performance of the modified AWF with the performance of the other loop scheduling methods in the context of three nontrivial applications reveal that the performance of the modified method is comparable to, and in some cases, superior to the performance of the most recently introduced adaptive factoring method.

服务组合中一种服务组合路径优化方法研究

在大规模网络环境下的服务组合路径研究中,服务组合路径长度总是大于服务组合中服务的个数.然而,在服务密集分布、节点间网络距离近似相等的环境下,这个结论不再成立.此时,服务组合路径长度服务组合中的服务路径选择问题的关键在于如何在不影响负载平衡的前提下,选择合适的服务节点,使服务组合能连续使用部署在同一节点上的服务资源,以减少路由次数.为此引入了保持因子和匹配长度因子这两个参数来调整服务节点的选择算法,并通过模拟实验分析了这两个参数对负载平衡和服务路径长度的影响,最后给出这两个参数的选择策略和选择方法.     

P2P网络环境下的一种高效虚拟协同服务模型

在现实网络中,资源主要集中在少数的重要节点中,大量节点是服务请求者.由于P2P网络是建立在Internet之上的应用层虚拟网络,加上网络中搭便车现象日益严重,在广域环境下,不可避免地存在拥塞、单点失效、效率和服务质量不高的问题.针对这些问题,通过在系统中动态地构造由协同服务盟员组成的服务池来解决.提出了一种有盟主的虚拟协同服务组织模型,旨在现实环境下针对盟主的目标需求,解决盟主如何动态组织自主的协同伙伴和构建虚拟组织协同进行求解的问题.构造了基于D-S证据推理的服务盟员选择策略,运用节点交易历史信息和推荐证书的方法来表征备选服务盟员的全局信任特征属性,给出了构建虚拟协同服务池的数学模型、约束条件和构造规则,并进行了较为详细的分析.仿真实验表明,动态构造服务池的负载平衡策略能较好地解决P2P网络中存在拥塞、单点失效、效率和服务质量不高的问题,极大地改善了P2P网络的服务质量.     

分布式高可扩展负载平衡中间件技术研究

现有的负载平衡中间件大多采用单一的基于对象的负载平衡粒度,更多地关注同一对象组的不同副本之间的平衡,复杂的分布式应用往往存在多种不同类型的服务对象组共存的情况。该文基于CORBA技术,论述提高负载平衡中间件可扩展性的关键问题、解决方法及其实现,给出了相关的测试结果。