The relative performance of scalable load balancing algorithms in loosely-coupled distributed systems. Available in 2 volumes.

The computer systems of today are characterised by data and program control that are distributed functionally and geographically across a network. A major issue of concern in this environment is the operating system activity of resource management for different processors in the network. To ensure equity in load distribution and improved system performance, load balancing is often undertaken. The research conducted in this field so far, has been primarily concerned with a small set of algorithms operating on tightly-coupled distributed systems. More recent studies have investigated the performance of such algorithms in loosely-coupled architectures but using a small set of processors. This thesis describes a simulation model developed to study the behaviour and general performance characteristics of a range of dynamic load balancing algorithms. Further, the scalability of these algorithms are discussed and a range of regionalised load balancing algorithms developed. In particular, we examine the impact of network diameter and delay on the performance of such algorithms across a range of system workloads. The results produced seem to suggest that the performance of simple dynamic policies are scalable but lack the load stability of more complex global average algorithms.

Mesh partitioning and load balancing for distributed memory parallel systems

A method is outlined for optimising graph partitions which arise in mapping unstructured mesh calculations to parallel computers. The method employs a relative gain iterative technique to both evenly balance the workload and minimise the number and volume of interprocessor communications. A parallel graph reduction technique is also briefly described and can be used to give a global perspective to the optimisation. The algorithms work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds. The algorithms can also be used for dynamic load-balancing, reusing existing partitions and in this case the procedures are much faster than static techniques, provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data.

Dynamic mesh partitioning and load-balancing for parallel computational mechanics codes

In this Chapter we discuss the load-balancing issues arising in parallel mesh based computational mechanics codes for which the processor loading changes during the run. We briefly touch on geometric repartitioning ideas and then focus on different ways of using a graph both to solve the load-balancing problem and the optimisation problem, both locally and globally. We also briefly discuss whether repartitioning is always valid. Sample illustrative results are presented and we conclude that repartitioning is an attractive option if the load changes are not too dramatic and that there is a certain trade-off between partition quality and volume of data that the underlying application needs to migrate.

Shape-optimized mesh partitioning and load balancing for parallel adaptive FEM

We present a dynamic distributed load balancing algorithm for parallel, adaptive Finite Element simulations in which we use preconditioned Conjugate Gradient solvers based on domain-decomposition. The load balancing is designed to maintain good partition aspect ratio and we show that cut size is not always the appropriate measure in load balancing. Furthermore, we attempt to answer the question why the aspect ratio of partitions plays an important role for certain solvers. We define and rate different kinds of aspect ratio and present a new center-based partitioning method of calculating the initial distribution which implicitly optimizes this measure. During the adaptive simulation, the load balancer calculates a balancing flow using different versions of the diffusion algorithm and a variant of breadth first search. Elements to be migrated are chosen according to a cost function aiming at the optimization of subdomain shapes. Experimental results for Bramble's preconditioner and comparisons to state-of-the-art load balancers show the benefits of the construction.

Load-balancing for parallel adaptive unstructured grids

A parallel method for the dynamic partitioning of unstructured meshes is outlined. The method includes diffusive load-balancing techniques and an iterative optimisation technique known as relative gain optimisationwhich both balances theworkload and attempts to minimise the interprocessor communications overhead. It can also optionally include amultilevel strategy. Experiments on a series of adaptively refined meshes indicate that the algorithmprovides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Load balancing for parallel adaptive FEM

We present a dynamic distributed load balancing algorithm for parallel, adaptive finite element simulations using preconditioned conjugate gradient solvers based on domain-decomposition. The load balancer is designed to maintain good partition aspect ratios. It calculates a balancing flow using different versions of diffusion and a variant of breadth first search. Elements to be migrated are chosen according to a cost function aiming at the optimization of subdomain shapes. We show how to use information from the second step to guide the first. Experimental results using Bramble's preconditioner and comparisons to existing state-of-the-art balancers show the benefits of the construction.

Dynamic load sharing for heavy vehicles : a new metric

Dynamic load sharing can be defined as a measure of the ability of a heavy vehicle multi-axle group to equalise load across its wheels under typical travel conditions; i.e. in the dynamic sense at typical travel speeds and operating conditions of that vehicle. Various attempts have been made to quantify the ability of heavy vehicles to equalise the load across their wheels during travel. One of these was the concept of the load sharing coefficient (LSC). Other metrics such as the dynamic load coefficient (DLC) have been used to compare one heavy vehicle suspension with another for potential road damage. This paper compares these metrics and determines a relationship between DLC and LSC with sensitivity analysis of this relationship. The shortcomings of these presently-available metrics are discussed with a new metric proposed - the dynamic load equalisation (DLE) measure.

Model development and dynamic load-sharing analysis of longitudinal-connected air suspensions

The objective of this research was to investigate the effect of suspension parameters on dynamic load-sharing of longitudinal-connected air suspensions of a tri-axle semi-trailer. A novel nonlinear model of a multi-axle semi-trailer with longitudinal-connected air suspension was formulated based on fluid mechanics and thermodynamics and was validated through test results. The effects of suspension parameters on dynamic load-sharing and road-friendliness of the semi-trailer were analyzed. Simulation results indicate that the road-friendliness metric DLC (Dynamic Load Coefficient), is generally in accordance with the load-sharing metric - DLSC (Dynamic Load Sharing Coefficient). When the static height or static pressure increases, the DLSC optimization ratio declines monotonically. The effect of employing larger air lines and connectors on the DLSC optimization ratio gives varying results as road roughness increases and as driving speed increases. The results also indicate that if the air line diameter is always assumed to be larger than the connector diameter, the influence of air line diameter on load-sharing is more significant than that of the connector.

Effect of driving conditions and suspension parameters on dynamic load-sharing of longitudinal-connected air suspensions

The objective of this research was to investigate the effects of driving conditions and suspension parameters on dynamic load-sharing of longitudinal-connected air suspensions of a tri-axle semi-trailer. A novel nonlinear model of a multi-axle semi-trailer with longitudinal-connected air suspension was formulated based on fluid mechanics and thermodynamics and was validated through test results. The effects of driving conditions and suspension parameters on dynamic load-sharing and road-friendliness of the semi-trailer were analyzed. Simulation results indicate that the road-friendliness metric-DLC (dynamic load coefficient) is not always in accordance with the load-sharing metric-DLSC (dynamic load-sharing coefficient). The effect of employing larger air lines and connectors on the DLSC optimization ratio gives varying results as road roughness increases and as driving speed increases. When the vehicle load reduces, or the static pressure increases, the DLSC optimization ratio declines monotonically. The results also indicate that if the air line diameter is always assumed to be larger than the connector diameter, the influence of air line diameter on load-sharing is more significant than that of the connector.

Dynamic load-sharing of longitudinal-connected air suspensions of a tri-axle semi-trailer

The effects of suspension parameters and driving conditions on dynamic load-sharing of longitudinal-connected air suspensions of a tri-axle semi-trailer are investigated in this study. A novel nonlinear model of a multi-axle semi-trailer with longitudinal-connected air suspensions is formulated based on fluid mechanics and thermodynamics and validated through test results. The effects of road surface conditions, driving speeds, air line inside diameter and connector inside diameter on dynamic load-sharing capability of the semi-trailer were analyzed in terms of load-sharing criteria. Simulation results indicate that, when larger air lines and connectors are employed, the DLSC (Dynamic Load-Sharing Coefficient) optimization ratio reaches its peak value when the road roughness is medium. The optimization ratio fluctuates in a complex manner as driving speed increases. The results also indicate that if the air line inside diameter is always assumed to be larger than the connector inside diameter, the influence of air line inside diameter on load-sharing is more significant than that of the connector inside diameter. The proposed approach can be used for further study of the influence of additional factors (such as vehicle load, static absolute air pressure and static height of air spring) on load-sharing and the control methods for multi-axle air suspensions with longitudinal air line.

Dynamic load sharing in heavy vehicle suspensions - further analysis of the equalisation effects of larger air lines

This paper provides details on comparative testing of axle-to-chassis forces of two heavy vehicles (HVs) based on an experimental programme carried out in 2007. Dynamic forces at the air springs were measured against speed and roughness values for the test roads used. One goal of that programme was to determine whether dynamic axle-to-chassis forces could be reduced by using larger-than-standard diameter longitudinal air lines. This paper presents a portion of the methodology, analysis and results from that programme. Two analytical techniques and their results are presented. The first uses correlation coefficients of the forces between air springs and the second is a student’s t-test. These were used to determine the causality surrounding improved dynamic load sharing between heavy vehicle air springs with larger air lines installed longitudinally compared with the standard sized air lines installed on the majority of air-sprung heavy vehicles.

PMU measurement based dynamic load modeling using SVC devices in online environment

Online dynamic load modeling has become possible with the availability of Static Voltage Compensator (SVC) and Phasor Measurement Unit (PMU) devices. The power of the load response to the small random bounded voltage fluctuations caused from SVC can be measured by PMU for modelling purposes. The aim of this paper is to illustrate the capability of identifying an aggregated load model from high voltage substation level in the online environment. The induction motor is used as the main test subject since it contributes the majority of the dynamic loads. A test system representing simple electromechanical generator model serving dynamic loads through the transmission network is used to verify the proposed method. Also, dynamic load with multiple induction motors are modeled to achieve a better realistic load representation.

Adaptive optimal load balancing in a nonhomogeneous multiserver system with a central job scheduler

A model comprising several servers, each equipped with its own queue and with possibly different service speeds, is considered. Each server receives a dedicated arrival stream of jobs; there is also a stream of generic jobs that arrive to a job scheduler and can be individually allocated to any of the servers. It is shown that if the arrival streams are all Poisson and all jobs have the same exponentially distributed service requirements, the probabilistic splitting of the generic stream that minimizes the average job response time is such that it balances the server idle times in a weighted least-squares sense, where the weighting coefficients are related to the service speeds of the servers. The corresponding result holds for nonexponentially distributed service times if the service speeds are all equal. This result is used to develop adaptive quasi-static algorithms for allocating jobs in the generic arrival stream when the load parameters are unknown. The algorithms utilize server idle-time measurements which are sent periodically to the central job scheduler. A model is developed for these measurements, and the result mentioned is used to cast the problem into one of finding a projection of the root of an affine function, when only noisy values of the function can be observed

Relay Load Balancing in Queued Cooperative Wireless Networks with Rateless Codes

Relay selection combined with buffering of packets of relays can substantially increase the throughput of a cooperative network that uses rateless codes. However, buffering also increases the end-to-end delays due to the additional queuing delays at the relay nodes. In this paper we propose a novel method that exploits a unique property of rateless codes that enables a receiver to decode a packet from non-contiguous and unordered portions of the received signal. In it, each relay, depending on its queue length, ignores its received coded bits with a given probability. We show that this substantially reduces the end-to-end delays while retaining almost all of the throughput gain achieved by buffering. In effect, the method increases the odds that the packet is first decoded by a relay with a smaller queue. Thus, the queuing load is balanced across the relays and traded off with transmission times. We derive explicit necessary and sufficient conditions for the stability of this system when the various channels undergo fading. Despite encountering analytically intractable G/GI/1 queues in our system, we also gain insights about the method by analyzing a similar system with a simpler model for the relay-to-destination transmission times.

Load Balancing with Availability Checker and Load Reporters (LB-ACLRs) for improved Performance in Distributed Systems

Distributed system has quite a lot of servers to attain increased availability of service and for fault tolerance. Balancing the load among these servers is an important task to achieve better performance. There are various hardware and software based load balancing solutions available. However there is always an overhead on Servers and the Load Balancer while communicating with each other and sharing their availability and the current load status information. Load balancer is always busy in listening to clients' request and redirecting them. It also needs to collect the servers' availability status frequently, to keep itself up-to-date. Servers are busy in not only providing service to clients but also sharing their current load information with load balancing algorithms. In this paper we have proposed and discussed the concept and system model for software based load balancer along with Availability-Checker and Load Reporters (LB-ACLRs) which reduces the overhead on server and the load balancer. We have also described the architectural components with their roles and responsibilities. We have presented a detailed analysis to show how our proposed Availability Checker significantly increases the performance of the system.