A new fuzzy-decision based load balancing system for distributed object computing

Distributed object computing systems are widely envisioned to be the desired distributed software development paradigm due to the higher modularity and the capability of handling machine and operating system heterogeneity. Indeed, enabled by the tremendous advancements in processor and networking technologies, complex operations such as object serialization and data marshaling have become very efficient, and thus, distributed object systems are being built for many different applications. However, as the system scales up (e.g., with larger number of server and client objects, and more machines), a judicious load balancing system is required to efficiently distribute the workload (e.g., the queries, messages/objects passing) among the different servers in the system. Unfortunately, in existing distributed object middleware systems, such a load balancing facility does not exist. In this paper, we present the design and implementation of a new dynamic fuzzy-decision-based load balancing system incorporated in a distributed object computing environment. Our proposed approach works by using a fuzzy logic controller which informs a client object to use the most appropriate service such that load balancing among servers is achieved. We have chosen Jini to build our experimental middleware platform, on which our proposed approach as well as other related techniques are implemented and compared. Extensive experiments are conducted to investigate the effectiveness of our fuzzy-decision-based algorithm, which is found to be consistently better than other approaches.     

The grid, the load and the gradient

An important concern for an efficient use of distributed computing is dealing with load balancing to ensure all available nodes and their shared resources are equally exploited. In large scale systems such as volunteer computing platforms and desktop grids, centralized solutions may introduce performance bottlenecks and single points of failure. Accordingly fully distributed alternatives have been considered, due to their inherent robustness and reliability. In extremely dynamic contexts, scheduling middlewares should adapt their job scheduling policies to the actual availability and overcome the volatility and heterogeneity typical of the underlying nodes. To deal with the dynamicity of a large pool of resources, self-organizing and adaptive solutions represent a promising research direction. Solutions based on bio-inspired methodologies are particularly suitable, as they inherently provide the desired features. In this paper we present a fully distributed load balancing mechanism, called ozmos, which aims at increasing the efficiency of distributed computing systems through peer-to-peer interaction between nodes. The proposed algorithm is based on a Chord overlay, and employs ant-like agents to spread information about the current load on each node, to reschedule tasks from overloaded systems to underloaded ones, and to relocate incompatible tasks on suitable resources in heterogeneous grids. By means of several evaluation scenarios we demonstrate the effectiveness of the proposed solution in achieving system-wide load balancing, both with homogeneous and heterogeneous resources. In particular we consider the load balancing performance of our approach, its scalability, as well as its communication efficiency.     

Autonomous mobile agent routing for efficient server resource allocation

Mobile agents are becoming increasingly important in the highly distributed applications frameworks seen today. Their routing/dispatching from node to node is a very important issue as we need to safeguard application efficiency, achieve better load balancing and resource utilization throughout the underlying network. Selecting the best target server for dispatching a mobile agent is, therefore, a multi-faceted problem that needs to be carefully tackled. In this paper we propose distributed, adaptive routing schemes (next node selection) for mobile agents. The proposed schemes overcome risks like load oscillations, i.e., agents simultaneously abandoning a congested node in search for other, less saturated node. We try to induce different routing decisions taken by agents to achieve load balancing and better utilization of network resources. We consider five different algorithms and evaluate them through simulations. Our findings are quite promising both from the user/application and the network/infrastructure perspective.     

Experiences from integrating algorithmic and systemic load balancing strategies

Load balancing increases the efficient use of existing resources for parallel and distributed applications. At a coarse level of granularity, advances in runtime systems for parallel programs have been proposed in order to control available resources as efficiently as possible by utilizing idle resources and using task migration. Simultaneously, at a finer granularity level, advances in algorithmic strategies for dynamically balancing computational loads by data redistribution have been proposed in order to respond to variations in processor performance during the execution of a given parallel application. Combining strategies from each level of granularity can result in a system which delivers advantages of both. The resulting integration is systemic in nature and transfers the responsibility of efficient resource utilization from the application programmer to the runtime system. This paper presents the design and implementation of a system that combines an algorithmic fine-grained data parallel load balancing strategy with a systemic coarse-grained task-parallel load balancing strategy, and reports on recent experimental results of running a computationally intensive scientific application under this integrated system. The experimental results indicate that a distributed runtime environment which combines both task and data migration can provide performance advantages with little overhead. It also presents proposals for performance enhancements of the implementation, as well as future explorations for effective resource management. Copyright © 2001 John Wiley & Sons, Ltd.     

分布式系统中基于移动代理的负载均衡模型和负载更新算法的研究

在分布式控制中,结点间的信息交互一般都是通过广播的方式来进行的,占用了大量的网络资源。其次,由于各个结点很难准确地了解整个系统的负载状况及变化,因此很难实现整体的负载均衡。论文首先介绍了基于移动代理的负载均衡结构。通过移动代理良好的移动性、智能性等优点,可以解决传统负载均衡的这些问题。其次,文章分析了传统负载信息更新方法,提出了基于移动代理的ULIMA负载信息更新算法,通过仿真实验证明了该算法的有效性,从而可以较大地提高了负载均衡系统的性能和效率。     

一种有效负载均衡的网格Web服务体系结构模型

基于Web服务资源的小世界模型,提出了一种可无缝结合网格OGSA框架的Web服务体系结构与动态的资源负载均衡分配模型,它以Web服务资源注册中心(Web Services Resource Register Center,WSRRC)作为Web服务资源查找的入口,以Web服务资源ID类形成的虚拟资源树作为资源逻辑组织与负载均衡分配结构,以小世界形成的区域代理自治系统(Area Proxy Autonomy System．APAS)来进行Web服务资源的维护．并详细描述了该模型的实现机制、组织协议与数据结构,着重研究了逻辑资源树负载信息的传播机制及负载均衡策略,模拟试验表明该模型是合理而有效的：它可以在较小开销下获得较满意的资源组织与定位性能,能适应网格Web服务资源的异构、复杂与动态性,具有良好的可扩展性及保持全局网络负载均衡的良好性能．     

基于反馈机制的动态负载平衡算法研究*

动态负载平衡是提高多处理器系统资源利用率和并行计算性能的重要途径。为了解决变化负载系统中子任务可并行计算的双重循环(PTM-NL)问题,提出一种基于反馈机制的动态负载平衡算法。该算法以处理器作业速度为负载指标,在循环计算中根据反馈的负载指标分配计算任务,动态适应负载变化。实验结果表明,该算法在变化负载的系统中能有效提高PTM-NL问题并行效率。     

Dynamic balancing of communication and computation load for HLA-based simulations on large-scale distributed systems

Dynamic balancing of computation and communication load is vital for the execution stability and performance of distributed, parallel simulations deployed on the shared, unreliable resources of large-scale environments. High Level Architecture (HLA) based simulations can experience a decrease in performance due to imbalances that are produced initially and/or during run time. These imbalances are generated by the dynamic load changes of distributed simulations or by unknown, non-managed background processes resulting from the non-dedication of shared resources. Due to the dynamic execution characteristics of elements that compose distributed applications, the computational load and interaction dependencies of each simulation entity change during run time. These dynamic changes lead to an irregular load and communication distribution, which increases overhead of resources and latencies. A static partitioning of load is limited to deterministic applications and is incapable of predicting the dynamic changes caused by distributed applications or by external background processes. Therefore, a scheme for balancing the communication and computational load during the execution of distributed simulations is devised in a scalable hierarchical architecture. The proposed balancing system employs local and cluster monitoring mechanisms in order to observe the distributed load changes and identify imbalances, repartitioning policies to determine a distribution of load and minimize imbalances. A migration technique is also employed by this proposed balancing system to perform reliable and low-latency load transfers. Such a system successfully improves the use of shared resources and increases distributed simulations’ performance by minimizing communication latencies and partitioning the load evenly. Experiments and comparative analyses were conducted in order to identify the gains that the proposed balancing scheme provides to large-scale distributed simulations.     

基于Mobile Agent技术的负载平衡模型研究

为更好地实现分布式系统中的负载平衡,结合自主设计的分布式数据库服务器系统DDSS（distributed database server system）,抽象出分布式冗余系统的3层管理框架,从对负载索引的客观描述与定义着眼,引入服务请求消化率、阈值负载贴近度等概念及主动负载平衡的思想,提出并实现了基于移动代理技术的负载平衡模型MMA,并对其性能进行了分析．通过分析表明,基于移动代理技术的负载平衡模型MMA具有代价小、智能性好、效率高及具有对负载索引的刻画客观准确等优点．     

基于遗传算法的移动代理调度

移动代理能够从一台机器移动到网络上的另一台机器,这对平衡系统中的负载很有作用。然而在移动代理系统中缺乏调度机制,以指导代理的移动。论文基于遗传算法设计一个移动代理系统的调度框架,使代理能够移动到负载轻的机器,达到平衡负载的目的。方法的有效性通过实验得到了验证。     

一种基于逢低买入的频谱分配机制

为解决移动自组织网络(MANET)中网络拥塞导致的网络时延增大和吞吐量下降, 提出一种基于概率的负载均衡算法, 节点利用历史负载信息映射网络负载状态, 用概率算法进行路由准入, 从而完成负载均衡。基于历史状态的负载映射有效解决了分布式独立运算中存在的负载状态判断困难等问题, 概率算法能有效克服门限准入法则存在的模糊判别问题, 同时大量减少广播包的洪泛, 节省信道资源。结合经典的按需路由协议, 设计了H&P_DSR(History and Probability Based Dynamic Source Routing)协议。仿真和理论分析一致表明, 该负载均衡算法能够准确有效的对网络负载进行均衡, H&P_DSR协议在没有增加任何信道开销的情况下显著提高了网络吞吐量, 降低了时延。     

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

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

An agent infrastructure for on-demand processing of remote-sensing archives

Advances in data collection techniques and database technologies, such as remote sensing and satellite telemetry, have led to the collection of huge amounts of data distributed among large databases and heterogeneous remote sites. Intelligent and automatic processing of the distributed data and efficiently supporting scientific collaboration between both professional and casual users is a highly demanding task. It is also particularly challenging when the system must cope with active data that is processed on-demand. These requirements have generated an urgent need for more advanced software infrastructure to create, maintain, evolve, and federate these active digital libraries of scientific data. Traditional models of distributed computing are inadequate to support such complex applications. As part of the ongoing Synthetic Aperture Radar Atlas (SARA) Digital Library project, the research presented here proposes a collaborating mobile agent approach to on-demand processing of remote sensing data. The approach, which is based on autonomous data processing and enables different image analysis algorithms to be wrapped as mobile agents, is expected to be an improvement over the static CGI-based interface and inefficient information discovery that are currently used by SARA. We discuss the agent-based infrastructure we have developed. The SARA system allows users to dispatch their compute-intensive jobs as mobile agents. Since the agents can be programmed to satisfy their specific goals, even if they move and lose contact with their creators they can survive intermittent or unreliable network connections. During their lifetime, the agents can also move themselves autonomously from one server to another for load balancing, and to enhance data locality and fault tolerance. The SARA system relies on XML to support agent communications on clusters of servers. Although the examples presented are based mainly on the SARA system, the proposed techniques are applicable to other active archives. In particular, we believe the proposed agent design can be used to dynamically configure distributed parallel computing resources and automatically integrate data analysis in remote sensing systems.     

An adaptive load balancing management technique for RFID middleware systems

In recent years, Radio Frequency Identification (RFID) industries have taken a great interest in utilizing the benefits of RFID for supply chain management, inventory control and various other applications. This paper proposed an adaptive load balancing technique for RFID middleware systems to meet the demands of scalability and heterogeneity. First, we explored five basic load balancing policies, namely, information policy, job selection policy, transfer policy, initiation policy and location policy. Eighteen load balancing schemes were then proposed for RFID middleware systems that were combinations of various types of the five basic load balancing policies. Our empirical study suggested that these load balancing strategies performed differently under different workload statuses. Finally, an adaptive load balancing strategy was proposed. The load balancing schemes and the proposed adaptive load balancing strategy have been implemented in the RFID Middleware Load Management System (RM‐LMS). Copyright © 2010 John Wiley & Sons, Ltd.     

LTE系统中的分布式负载迁移协商均衡算法

为了提高长期演进计划(long term evolution,LTE)系统中业务处理资源的利用率,降低由于系统处理资源分配不均而导致的呼损率,给出了一种适用于LTE系统的分布式负载迁移协商均衡算法.分析了LTE系统通信的特点,指出可利用LTE系统eNodeB (evolved NodeB)间使用X2接口进行数据通信的特点,在组网的eNodeB问进行负载迁移.在此基础上建立了负载迁移协商均衡模型,指出了算法的适用场景,说明了算法均衡粒度的选取标准和性能评价指标.通过与传统的轮询算法进行比较,使用分布式事件驱动方法对该算法进行了性能分析,验证结果表明了该算法的有效性.     

Mobile agent-enabled framework for structuring and building distributed systems on the internet

Mobile agent has shown its promise as a powerful means to complement and enhance existing technology in various application areas. In particular, existing work has demonstrated that MA can simplify the development and improve the performance of certain classes of distributed applications, especially for those running on a wide-area, heterogeneous, and dynamic networking environment like the Internet. In our previous work, we extended the application of MA to the design of distributed control functions, which require the maintenance of logical relationship among and/or coordination of proc- essing entities in a distributed system. A novel framework is presented for structuring and building distributed systems, which use cooperating mobile agents as an aid to carry out coordination and cooperation tasks in distributed systems. The framework has been used for designing various distributed control functions such as load balancing and mutual ex- clusion in our previous work. In this paper, we use the framework to propose a novel ap- proach to detecting deadlocks in distributed system by using mobile agents, which dem- onstrates the advantage of being adaptive and flexible of mobile agents. We first describe the MAEDD (Mobile Agent Enabled Deadlock Detection) scheme, in which mobile agents are dispatched to collect and analyze deadlock information distributed across the network sites and, based on the analysis, to detect and resolve deadlocks. Then the design of an adaptive hybrid algorithm derived from the framework is presented. The algorithm can dynamically adapt itself to the changes in system state by using different deadlock detec- tion strategies. The performance of the proposed algorithm has been evaluated using simulations. The results show that the algorithm can outperform existing algorithms that use a fixed deadlock detection strategy.     

基于模糊逻辑技术的中间件负载平衡机制

针对当前基于中间件负载平衡机制中负载定位不够准确、监测粒度过大等问题,基于模糊逻辑技术提出一种更精确、更细粒度的负载平衡系统及其负载平衡机制。负载平衡系统的节点负载信息记录表记录系统中所有节点从模糊推理得出的负载状态信息,负载转发表记录服务节点与相应服务请求者之间的关系。实验结果表明,该负载平衡机制能有效地定位过载节点,较好地实现集群中的负载平衡服务。     

Geo-Agents系统中的负载控制策略

Geo-Agents是一个基于Agent的分布式GIS系统．首先分析Geo-Agents系统中的负载问题：主机负载和网络负载．主机负载指的是运行在该主机上的Agent数目；而网络负载则由Agent之间的通信和地理空间数据的传输组成．主机负载和网络负载是相互关联的．在Geo-Agents系统中，由于地理空间数据的数据量非常巨大，因此减少网络负载是首位的问题，只有在网络负载一致时才考虑均衡主机负载．针对Geo-Agents系统中负载情况，给出了两个负载控制策略：Agent调度策略和对等主机策略，并对Geo-Agents系统的主机负载和网络负载进行控制．     

Optimal Static Load Balancing in Star Network Configurations with Two-Way Traffic

We study the static load balancing problem in a distributed computer system that consists of a set of heterogeneous computer systems interconnected by a star network with two-way traffic. We formulate the static load balancing problem as a nonlinear optimization problem which minimizes the mean response time. We prove that in the optimal solution the satellite nodes in the star network can be divided into four different types: the idle source nodes, the active source nodes, the neutral nodes, and the sink nodes. The necessary and sufficient conditions for optimal solution are studied. An efficient algorithm of complexity O(n) is proposed for the static load balancing of an n-satellite system. The effects of link communication time on optimal load balancing in a star network are also studied by parametric analysis. By employing the proposed algorithm, a significant system performance improvement over that without load balancing is illustrated in a numerical example. The numerical example also shows that the effects of the link communication time in a star network are large.     

Improving hybrid ad hoc networks: The election of gateways

The selection of an appropriate and stable route that enables suitable load balancing of Internet gateways is an important issue in hybrid mobile ad hoc networks. The variables employed to perform routing must ensure that no harm is caused that might degrade other network performance metrics such as delay and packet loss. Moreover, the effect of such routing must remain affordable, such as low losses or extra signaling messages. This paper proposes a new method, Steady Load Balancing Gateway Election, based on a fuzzy logic system to achieve this objective. The fuzzy system infers a new routing metric named cost that considers several networks performance variables to select the best gateway. To solve the problem of defining the fuzzy sets, they are optimized by a genetic algorithm whose fitness function also employs fuzzy logic and is designed with four network performance metrics. The promising results confirm that ad hoc networks are characterized by great uncertainty, so that the use of Computational Intelligence methods such as fuzzy logic or genetic algorithms is highly recommended.