A study of adaptive load balancing algorithms for distributed systems

With the advent of distributed computer systems with a largely transparent user interface, new questions have arisen regarding the management of such an environment by an operating system. One fertile area of research is that of load balancing, which attempts to improve system performance by redistributing the workload submitted to the system by the users. Early work in this field concentrated on static placement of computational objects to improve performance, given prior knowledge of process behaviour. More recently this has evolved into studying dynamic load balancing with process migration, thus allowing the system to adapt to varying loads. In this thesis, we describe a simulated system which facilitates experimentation with various load balancing algorithms. The system runs under UNIX and provides functions for user processes to communicate through software ports; processes reside on simulated homogeneous processors, connected by a user-specified topology, and a mechanism is included to allow migration of a process from one processor to another. We present the results of a study of adaptive load balancing algorithms, conducted using the aforementioned simulated system, under varying conditions; these results show the relative merits of different approaches to the load balancing problem, and we analyse the trade-offs between them. Following from this study, we present further novel modifications to suggested algorithms, and show their effects on system performance.

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.

Improving scheduling techniques in heterogeneous systems with dynamic, on-line optimisations

Computational performance increasingly depends on parallelism, and many systems rely on heterogeneous resources such as GPUs and FPGAs to accelerate computationally intensive applications. However, implementations for such heterogeneous systems are often hand-crafted and optimised to one computation scenario, and it can be challenging to maintain high performance when application parameters change. In this paper, we demonstrate that machine learning can help to dynamically choose parameters for task scheduling and load-balancing based on changing characteristics of the incoming workload. We use a financial option pricing application as a case study. We propose a simulation of processing financial tasks on a heterogeneous system with GPUs and FPGAs, and show how dynamic, on-line optimisations could improve such a system. We compare on-line and batch processing algorithms, and we also consider cases with no dynamic optimisations.

Ensuring efficiency and robustness in MANET

This paper introduces a joint load balancing and hotspot mitigation protocol for mobile ad-hoc network (MANET) termed by us as 'load_energy balance + hotspot mitigation protocol (LEB+HM)'. We argue that although ad-hoc wireless networks have limited network resources - bandwidth and power, prone to frequent link/node failures and have high security risk; existing ad hoc routing protocols do not put emphasis on maintaining robust link/node, efficient use of network resources and on maintaining the security of the network. Typical route selection metrics used by existing ad hoc routing protocols are shortest hop, shortest delay, and loop avoidance. These routing philosophy have the tendency to cause traffic concentration on certain regions or nodes, leading to heavy contention, congestion and resource exhaustion which in turn may result in increased end-to-end delay, packet loss and faster battery power depletion, degrading the overall performance of the network. Also in most existing on-demand ad hoc routing protocols intermediate nodes are allowed to send route reply RREP to source in response to a route request RREQ. In such situation a malicious node can send a false optimal route to the source so that data packets sent will be directed to or through it, and tamper with them as wish. It is therefore desirable to adopt routing schemes which can dynamically disperse traffic load, able to detect and remove any possible bottlenecks and provide some form of security to the network. In this paper we propose a combine adaptive load_energy balancing and hotspot mitigation scheme that aims at evenly distributing network traffic load and energy, mitigate against any possible occurrence of hotspot and provide some form of security to the network. This combine approach is expected to yield high reliability, availability and robustness, that best suits any dynamic and scalable ad hoc network environment. Dynamic source routing (DSR) was use as our underlying protocol for the implementation of our algorithm. Simulation comparison of our protocol to that of original DSR shows that our protocol has reduced node/link failure, even distribution of battery energy, and better network service efficiency.

Evolutionary market agents for resource allocation in decentralised systems

We introduce self-interested evolutionary market agents, which act on behalf of service providers in a large decentralised system, to adaptively price their resources over time. Our agents competitively co-evolve in the live market, driving it towards the Bertrand equilibrium, the non-cooperative Nash equilibrium, at which all sellers charge their reserve price and share the market equally. We demonstrate that this outcome results in even load-balancing between the service providers. Our contribution in this paper is twofold; the use of on-line competitive co-evolution of self-interested service providers to drive a decentralised market towards equilibrium, and a demonstration that load-balancing behaviour emerges under the assumptions we describe. Unlike previous studies on this topic, all our agents are entirely self-interested; no cooperation is assumed. This makes our problem a non-trivial and more realistic one.

Dynamic causal modeling of load-dependent modulation of effective connectivity within the verbal working memory network

Neuroimaging studies have consistently shown that working memory (WM) tasks engage a distributed neural network that primarily includes the dorsolateral prefrontal cortex, the parietal cortex, and the anterior cingulate cortex. The current challenge is to provide a mechanistic account of the changes observed in regional activity. To achieve this, we characterized neuroplastic responses in effective connectivity between these regions at increasing WM loads using dynamic causal modeling of functional magnetic resonance imaging data obtained from healthy individuals during a verbal n-back task. Our data demonstrate that increasing memory load was associated with (a) right-hemisphere dominance, (b) increasing forward (i.e., posterior to anterior) effective connectivity within the WM network, and (c) reduction in individual variability in WM network architecture resulting in the right-hemisphere forward model reaching an exceedance probability of 99% in the most demanding condition. Our results provide direct empirical support that task difficulty, in our case WM load, is a significant moderator of short-term plasticity, complementing existing theories of task-related reduction in variability in neural networks. Hum Brain Mapp, 2013. © 2013 Wiley Periodicals, Inc.

The lateral and ventromedial prefrontal cortex work as a dynamic integrated system:evidence from FMRI connectivity analysis

Recent functional magnetic resonance imaging (fMRI) investigations of the interaction between cognition and reward processing have found that the lateral prefrontal cortex (PFC) areas are preferentially activated to both increasing cognitive demand and reward level. Conversely, ventromedial PFC (VMPFC) areas show decreased activation to the same conditions, indicating a possible reciprocal relationship between cognitive and emotional processing regions. We report an fMRI study of a rewarded working memory task, in which we further explore how the relationship between reward and cognitive processing is mediated. We not only assess the integrity of reciprocal neural connections between the lateral PFC and VMPFC brain regions in different experimental contexts but also test whether additional cortical and subcortical regions influence this relationship. Psychophysiological interaction analyses were used as a measure of functional connectivity in order to characterize the influence of both cognitive and motivational variables on connectivity between the lateral PFC and the VMPFC. Psychophysiological interactions revealed negative functional connectivity between the lateral PFC and the VMPFC in the context of high memory load, and high memory load in tandem with a highly motivating context, but not in the context of reward alone. Physiophysiological interactions further indicated that the dorsal anterior cingulate and the caudate nucleus modulate this pathway. These findings provide evidence for a dynamic interplay between lateral PFC and VMPFC regions and are consistent with an emotional gating role for the VMPFC during cognitively demanding tasks. Our findings also support neuropsychological theories of mood disorders, which have long emphasized a dysfunctional relationship between emotion/motivational and cognitive processes in depression.

A dynamic bandwidth reservation scheme for hybrid IEEE 802.16 wireless networks

A dynamic bandwidth reservation (DBR) scheme for hybrid IEEE 802.16 wireless networks is investigated, in which 802.16 networks serve as the backhaul for client networks, such as WiFi hotspots and cellular networks. The DBR scheme implemented in the subscription stations (SSs) (co-locating with access pointers) consists of two components: connection admission controller (CAC), and bandwidth controller (BC). The CAC processes the received connection set-up requests from the client networks connected to the SSs. The BC manages the request and release of bandwidth from the base station (BS). It dynamically changes the reserved bandwidth between a small number of values. Hysteresis is incorporated in bandwidth release to reduce bandwidth request signalling load and connection blocking probability. An analytical model is proposed to evaluate the performances of reserved bandwidth, connection blocking probability and signalling load. The impacts of hysteresis mechanism and probability of reservation request blocking are taken into account. Simulation verifies the analytical model. ©2008 IEEE.

The effect of load on agent-based algorithms for distributed task allocation

Multi-agent algorithms inspired by the division of labour in social insects and by markets, are applied to a constrained problem of distributed task allocation. The efficiency (average number of tasks performed), the flexibility (ability to react to changes in the environment), and the sensitivity to load (ability to cope with differing demands) are investigated in both static and dynamic environments. A hybrid algorithm combining both approaches, is shown to exhibit improved efficiency and robustness. We employ nature inspired particle swarm optimisation to obtain optimised parameters for all algorithms in a range of representative environments. Although results are obtained for large population sizes to avoid finite size effects, the influence of population size on the performance is also analysed. From a theoretical point of view, we analyse the causes of efficiency loss, derive theoretical upper bounds for the efficiency, and compare these with the experimental results.

Reinsurance trading in Lloyd's of London:balancing conflicting-yet-complementary logics in practice

Drawing on a year-long ethnographic study of reinsurance trading in Lloyd’s of London, this paper makes three contributions to current discussions of institutional complexity. First, we shift focus away from structural and relatively static organizational responses to institutional complexity and identify three balancing mechanisms - segmenting, bridging, and demarcating - which allow individuals to manage competing logics and their shifting salience within their everyday work. Second, we integrate these mechanisms in a theoretical model that explains how individuals can continually keep coexisting logics, and their tendencies to either blend or disconnect, in a state of dynamic tension which makes them conflicting-yet-complementary logics. Our model shows how actors are able to dynamically balance coexisting logics, maintaining the distinction between them, whilst also exploiting the benefits of their interdependence. Third, in contrast to most studies of newly formed hybrids and/or novel complexity our focus on a long-standing context of institutional complexity shows how institutional complexity can itself become institutionalized and routinely enacted within everyday practice.

Dynamic network rating for low carbon distribution network operation:a U.K. application

Dynamic asset rating (DAR) is one of the number of techniques that could be used to facilitate low carbon electricity network operation. Previous work has looked at this technique from an asset perspective. This paper focuses, instead, from a network perspective by proposing a dynamic network rating (DNR) approach. The models available for use with DAR are discussed and compared using measured load and weather data from a trial network area within Milton Keynes in the central area of the U.K. This paper then uses the most appropriate model to investigate, through a network case study, the potential gains in dynamic rating compared to static rating for the different network assets - transformers, overhead lines, and cables. This will inform the network operator of the potential DNR gains on an 11-kV network with all assets present and highlight the limiting assets within each season.

Thermal modelling for dynamic transformer rating in low carbon distribution network operation

Dynamic asset rating is one of a number of techniques that could be used to facilitate low carbon electricity network operation. This paper focusses on distribution level transformer dynamic rating under this context. The models available for use with dynamic asset rating are discussed and compared using measured load and weather conditions from a trial Network area within Milton Keynes. The paper then uses the most appropriate model to investigate, through simulation, the potential gains in dynamic rating compared to static rating under two transformer cooling methods to understand the potential gain to the Network Operator.

Characterizing permanent deformation and fracture of asphalt mixtures by using compressive dynamic modulus tests

Permanent deformation and fracture may develop simultaneously when an asphalt mixture is subjected to a compressive load. The objective of this research is to separate viscoplasticity and viscofracture from viscoelasticity so that the permanent deformation and fracture of the asphalt mixtures can be individually and accurately characterized without the influence of viscoelasticity. The undamaged properties of 16 asphalt mixtures that have two binder types, two air void contents, and two aging conditions are first obtained by conducting nondestructive creep tests and nondestructive dynamic modulus tests. Testing results are analyzed by using the linear viscoelastic theory in which the creep compliance and the relaxation modulus are modeled by the Prony model. The dynamic modulus and phase angle of the undamaged asphalt mixtures remained constant with the load cycles. The undamaged asphalt mixtures are then used to perform the destructive dynamic modulus tests in which the dynamic modulus and phase angle of the damaged asphalt mixtures vary with load cycles. This indicates plastic evolution and crack propagation. The growth of cracks is signaled principally by the increase of the phase angle, which occurs only in the tertiary stage. The measured total strain is successfully decomposed into elastic strain, viscoelastic strain, plastic strain, viscoplastic strain, and viscofracture strain by employing the pseudostrain concept and the extended elastic-viscoelastic correspondence principle. The separated viscoplastic strain uses a predictive model to characterize the permanent deformation. The separated viscofracture strain uses a fracture strain model to characterize the fracture of the asphalt mixtures in which the flow number is determined and a crack speed index is proposed. Comparisons of the 16 samples show that aged asphalt mixtures with a low air void content have a better performance, resisting permanent deformation and fracture. © 2012 American Society of Civil Engineers.

Power in distribution channels - Supplier assortment strategy for balancing power

This paper focuses on the move from buyer dominance toward interdependence between buyers and suppliers in a distribution channel. The paper introduces a case study collected through in-depth interviews and participative observations. It examines the relationships between a timber supplier and its customers in the builders' merchants sector. We stress the relevance of considering actions intended to change the power balance, rather than focusing only on trust. The power balance in a dyadic relationship is dynamic, and power positions need to be constantly re-evaluated. An important power resource is information asymmetry, manifested in the supplier's information about: products, regional and local demand, and the usage of the products. For practitioners, we highlight the possibility of exerting a non-coercive power resource, such as information asymmetry, in order to increase the relative power. Furthermore, being open about the power position between a buyer and a seller can foster a more efficient collaboration.