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.     

On delay adjustment for dynamic load balancing in distributed virtual environments

Distributed virtual environments (DVEs) are becoming very popular in recent years, due to the rapid growing of applications, such as massive multiplayer online games (MMOGs). As the number of concurrent users increases, scalability becomes one of the major challenges in designing an interactive DVE system. One solution to address this scalability problem is to adopt a multi-server architecture. While some methods focus on the quality of partitioning the load among the servers, others focus on the efficiency of the partitioning process itself. However, all these methods neglect the effect of network delay among the servers on the accuracy of the load balancing solutions. As we show in this paper, the change in the load of the servers due to network delay would affect the performance of the load balancing algorithm. In this work, we conduct a formal analysis of this problem and discuss two efficient delay adjustment schemes to address the problem. Our experimental results show that our proposed schemes can significantly improve the performance of the load balancing algorithm with neglectable computation overhead.     

Honey bee behavior inspired load balancing of tasks in cloud computing environments

Scheduling of tasks in cloud computing is an NP-hard optimization problem. Load balancing of non-preemptive independent tasks on virtual machines (VMs) is an important aspect of task scheduling in clouds. Whenever certain VMs are overloaded and remaining VMs are under loaded with tasks for processing, the load has to be balanced to achieve optimal machine utilization. In this paper, we propose an algorithm named honey bee behavior inspired load balancing (HBB-LB), which aims to achieve well balanced load across virtual machines for maximizing the throughput. The proposed algorithm also balances the priorities of tasks on the machines in such a way that the amount of waiting time of the tasks in the queue is minimal. We have compared the proposed algorithm with existing load balancing and scheduling algorithms. The experimental results show that the algorithm is effective when compared with existing algorithms. Our approach illustrates that there is a significant improvement in average execution time and reduction in waiting time of tasks on queue.     

A hybrid policy for fault tolerant load balancing in grid computing environments

Due to the emergence of grid computing over the Internet, there is a need for a hybrid load balancing algorithm which takes into account the various characteristics of the grid computing environment. Hence, this research proposes a fault tolerant hybrid load balancing strategy namely AlgHybrid_LB, which takes into account grid architecture, computer heterogeneity, communication delay, network bandwidth, resource availability, resource unpredictability and job characteristics. AlgHybrid_LB juxtaposes the strong points of neighbor-based and cluster based load balancing algorithms. Our main objective is to arrive at job assignments that could achieve minimum response time and optimal computing node utilization. Major achievements include low complexity of proposed approach and drastic reduction of number of additional communications induced due to load balancing. A simulation of the proposed approach using Grid Simulation Toolkit (GridSim) is conducted. Experimental results show that the proposed algorithm performs very well in a large grid environment.     

基于空间填充曲线的动态负载均衡算法

针对Web集群系统中服务器的数量不断增加、负载指标动态变化的特点,为实现均衡的分配请求,提出一种使用空间填充曲线来实现动态负载均衡的算法。利用空间填充曲线可高效得将高维数据映射到一维索引的特点,使均衡器根据实时收集的各项负载指标快速定位到最优编码的服务器。实验结果表明,该算法能有效地缩短请求响应时间,提升了集群系统的整体性能,在大规模集群系统中均衡效果更好。     

Task distribution using factoring load balancing in Master-Worker applications

Load imbalance among workers is one of the main causes of performance shortcomings in Master-Worker applications. We have observed that this problem is very similar to the one of scheduling distributed parallel loops, which has been widely in the literature. Thus, we have adapted one of the most successful algorithms, known as Factoring, to be used for Master-Worker applications. This has leads to a simple an elegant strategy that can be used to obtain an excellent automatic and dynamic load balancing strategy for the workers. Finally, we have assessed the resulting strategy through extensive experimentation and simulation.     

Dynamic storage and access load balancing for answering range queries in peer-to-peer networks

Recently, many applications have used Peer-to-Peer (P2P) systems to overcome the current problems with client/server systems such as non-scalability, high bandwidth requirement and single point of failure. In this paper, we propose an efficient scheme to support efficient range query processing over structured P2P systems, while balancing both the storage load and access load. The paper proposes a rotating token scheme to balance the storage load by placing joining nodes in appropriate locations in the identifier space to share loads with already overloaded nodes. Then, to support range queries, we utilize an order-preserving mapping function to map keys to nodes in order preserving way and without hashing. This may result in an access load imbalance due to non-uniform distribution of keys in the identifier space. Thus, we propose an adaptive replication scheme to relieve overloaded nodes by shedding some load on other nodes to balance the access load. We derive a formula for estimating the overhead of the proposed adaptive replication scheme. In this study, we carry simulation experiments with synthetic data to measure the performance of the proposed schemes. Our simulation experiments show significant gains in both storage load balancing and access load balancing.     

Solution of non-convex economic load dispatch problem using Grey Wolf Optimizer

Grey Wolf Optimizer (GWO) is a recently developed meta-heuristic search algorithm inspired by grey wolves (Canis lupus), which simulate the social stratum and hunting mechanism of grey wolves in nature and based on three main steps of hunting: searching for prey, encircling prey and attacking prey. This paper presents the application of GWO algorithm for the solution of non-convex and dynamic economic load dispatch problem (ELDP) of electric power system. The performance of GWO is tested for ELDP of small-, medium- and large-scale power systems, and the results are verified by a comparative study with lambda iteration method, Particle Swarm Optimization algorithm, Genetic Algorithm, Biogeography-Based Optimization, Differential Evolution algorithm, pattern search algorithm, NN-EPSO, FEP, CEP, IFEP and MFEP. Comparative results show that the GWO algorithm is able to provide very competitive results compared to other well-known conventional, heuristics and meta-heuristics search algorithms.     

Parallel modular exponentiation using load balancing without precomputation

The modular exponentiation operation of the current algorithms for asymmetric cryptography is the most expensive part in terms of computational cost. The RSA algorithm, for example, uses the modular exponentiation algorithm in encryption and decryption procedure. Thus, the overall performance of those asymmetric cryptosystems depends heavily on the performance of the specific algorithm used for modular exponentiation. This work proposes new parallel algorithms to perform this arithmetical operation and determines the optimal number of processors that yields the greatest speedup. The optimal number is obtained by balancing the processing load evenly among the processors. Practical implementations are also performed to evaluate the theoretical proposals.     

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 %.     

Exploration of polygonal environments using range data

Several robotic problems involve the systematic traversal of the environment, commonly referred to as exploration. We present a strategy for the exploration of unknown finite polygonal environments, using a point robot with 1) no positional uncertainty and 2) an ideal range sensor that measures range in N uniformly distributed directions. The range data vector, obtained from the range sensor, corresponds to a sampled version of a visibility polygon. Visibility polygon edges that do not correspond to environmental edges are called jump edges and the exploration strategy is based on the fact that jump edges indicate directions of possibly unexplored environmental regions. We describe conditions under which it is possible to identify jump edges in the range data. We also show how the exploration strategy can be used in a solution to the terrain acquisition problem and describe conditions under which a solution is guaranteed within a finite number of measurements     

Global web server load balancing using evolutionary computational techniques

 As user load on web servers becomes more globalised, duplicated regional mirroring is being seen as an increasingly expensive solution to meeting regional peak demand. Alternative solutions are being explored by looking at dynamic load balancing using distributed intelligent middleware to re-route traffic from busy regions to quieter ones as global load patterns change over a 24 h cycle. The techniques used can also be employed under fault and planned maintenance conditions. One such solution, providing the load balancing via reconfigurable dynamic proxy servers, is seen as `unobtrusive' in that it works with standard web browsers and web server technology. The technique employs an evolutionary algorithm to perform combinatorial optimisation against a dynamic performance predicting model. This paper describes this solution, focussing on issues such as algorithm tuning, scalabilty and reliability. A prototype system is currently being trialled within the Systems Integration Department at British Telecommunications Research Labs, Adastral Park and is the subject of several BT held patents.     

Tracking human motion in structured environments using adistributed-camera system

This paper presents a comprehensive framework for tracking coarse human models from sequences of synchronized monocular grayscale images in multiple camera coordinates. It demonstrates the feasibility of an end-to-end person tracking system using a unique combination of motion analysis on 3D geometry in different camera coordinates and other existing techniques in motion detection, segmentation, and pattern recognition. The system starts with tracking from a single camera view. When the system predicts that the active camera will no longer have a good view of the subject of interest, tracking will be switched to another camera which provides a better view and requires the least switching to continue tracking. The nonrigidity of the human body is addressed by matching points of the middle line of the human image, spatially and temporally, using Bayesian classification schemes. Multivariate normal distributions are employed to model class-conditional densities of the features for tracking, such as location, intensity, and geometric features. Limited degrees of occlusion are tolerated within the system. Experimental results using a prototype system are presented and the performance of the algorithm is evaluated to demonstrate its feasibility for real time applications     

Structure and motion in urban environments using upright panoramas

Image-based modeling of urban environments is a key component of enabling outdoor, vision-based augmented reality applications. The images used for modeling may come from off-line efforts, or online user contributions. Panoramas have been used extensively in mapping cities and can be captured quickly by an end-user with a mobile phone. In this paper, we describe and evaluate a reconstruction pipeline for upright panoramas taken in an urban environment. We first describe how panoramas can be aligned to a common vertical orientation using vertical vanishing point detection, which we show to be robust for a range of inputs. The orientation sensors in modern cameras can also be used to correct the vertical orientation. Secondly, we introduce a pose estimation algorithm, which uses knowledge of a common vertical orientation as a simplifying constraint. This procedure is shown to reduce pose estimation error in comparison with the state of the art. Finally, we evaluate our reconstruction pipeline with several real-world examples.     

基于负载平衡智能体的分布式Web代理群集研究

为了帮助Web代理系统自动调整负载,提高服务器节点的使用效率,提出了基于多智能体的代理服务器集群架构,设计了一套适用于负载平衡的智能体通信协议和Web缓存管理机制,及时反映系统的负载变化及节点间的负载差异。当网络负载和服务器数量发生变化时,服务器节点能够随环境变化进行自适应的配置,在智能体指导下修改服务器的资源管理范围。实验结果表明,与其它代理群集相比,智能体代理系统在缓存命中率、负载均衡以及响应延迟方面都有显著提高。     

Noncooperative load balancing in distributed systems

In this paper, we present a game theoretic framework for obtaining a user-optimal load balancing scheme in heterogeneous distributed systems. We formulate the static load balancing problem in heterogeneous distributed systems as a noncooperative game among users. For the proposed noncooperative load balancing game, we present the structure of the Nash equilibrium. Based on this structure we derive a new distributed load balancing algorithm. Finally, the performance of our noncooperative load balancing scheme is compared with that of other existing schemes. The main advantages of our load balancing scheme are the distributed structure, low complexity and optimality of allocation for each user.