A survey on resource allocation in high performance distributed computing systems

An efficient resource allocation is a fundamental requirement in high performance computing (HPC) systems. Many projects are dedicated to large-scale distributed computing systems that have designed and developed resource allocation mechanisms with a variety of architectures and services. In our study, through analysis, a comprehensive survey for describing resource allocation in various HPCs is reported. The aim of the work is to aggregate under a joint framework, the existing solutions for HPC to provide a thorough analysis and characteristics of the resource management and allocation strategies. Resource allocation mechanisms and strategies play a vital role towards the performance improvement of all the HPCs classifications. Therefore, a comprehensive discussion of widely used resource allocation strategies deployed in HPC environment is required, which is one of the motivations of this survey. Moreover, we have classified the HPC systems into three broad categories, namely: (a) cluster, (b) grid, and (c) cloud systems and define the characteristics of each class by extracting sets of common attributes. All of the aforementioned systems are cataloged into pure software and hybrid/hardware solutions. The system classification is used to identify approaches followed by the implementation of existing resource allocation strategies that are widely presented in the literature.     

Optimal recovery schemes in fault tolerant distributed computing

Clusters and distributed systems offer fault tolerance and high performance through load sharing. When all n computers are up and running, we would like the load to be evenly distributed among the computers. When one or more computers break down, the load on these computers must be redistributed to other computers in the system. The redistribution is determined by the recovery scheme. The recovery scheme is governed by a sequence of integers modulo n. Each sequence guarantees minimal load on the computer that has maximal load even when the most unfavorable combinations of computers go down. We calculate the best possible such recovery schemes for any number of crashed computers by an exhaustive search, where brute force testing is avoided by a mathematical reformulation of the problem and a branch-and-bound algorithm. The search nevertheless has a high complexity. Optimal sequences, and thus a corresponding optimal bound, are presented for a maximum of twenty one computers in the distributed system or cluster.Received: 26 May 2004, Published online: 14 March 2005     

On distributed dynamic channel allocation in mobile cellularnetworks

Distributed dynamic channel allocation (DDCA) is a fundamental resource management problem in mobile cellular networks. It has a flavor of distributed mutual exclusion but is not exactly a mutual exclusion problem. We establish the exact relationship between the two problems. Specifically, we introduce the problem of relaxed mutual exclusion to model one important aspect of the DDCA problem. We develop a general algorithm that guarantees relaxed mutual exclusion for a single resource and prove necessary and sufficient conditions for the information structure. Considering distributed dynamic channel allocation as a special case of relaxed mutual exclusion, we apply and extend the algorithm to further address the issues that arise in distributed channel allocation such as deadlock resolution, dealing with multiple channels, design of efficient information structures, and channel selection strategies. Based on these results, we propose an example distributed channel allocation scheme using one of the information structures proposed. Analysis and simulation results are provided and show that the results of this research can be used to design more efficient distributed channel allocation algorithms     

Modelling and analysing a distributed dynamic channel allocation algorithm for mobile computing using high-level net methods

A distributed dynamic channel allocation algorithm has been proposed in [11]. In this paper the algorithm is modelled using predicate/transition nets. The same model can be used for any number of cell and channel configurations. The Maria reachability analyser has been used to analyse the protocol for some configurations. These are deadlock-free and are shown to satisfy the requirement that the same channel is never allocated to two neighbouring cells. The suitability of high-level nets for the modelling and analysis of distributed algorithms is discussed. Published online: 24 August 2001     

A high-performance computing method for data allocation in distributed database systems

Enhancing the performance of the DDBs (Distributed Database system) can be done by speeding up the computation of the data allocation, leading to higher speed allocation decisions and resulting in smaller data redundancy and shorter processing time. This paper deals with an integrated method for grouping the distributed sites into clusters and customizing the database fragments allocation to the clusters and their sites. We design a high speed clustering and allocating method to determine which fragments would be allocated to which cluster and site so as to maintain data availability and a constant systemic reliability, and evaluate the performance achieved by this method and demonstrate its efficiency by means of tabular and graphical representation. We tested our method over different network sites and found it reduces the data transferred between the sites during the execution time, minimizes the communication cost needed for processing applications, and handles the database queries and meets their future needs.     

Optimal allocation in a multiresources graduated tariff communication environment

The designer of computer networks is often confronted with the problem of the optimal allocation of multiple communications resources, subject to a graduated tariff. Such optimality criteria for the correct mix of facilities for use in system design are obtained. The paper gives examples from data communications.     

An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems

This paper investigates the problem of allocating parallel application tasks to processors in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation for more than three processors is known to be NP-hard in the strong sense. To deal with this challenging problem, we propose a simple and effective iterative greedy algorithm to find the best possible solution within a reasonable amount of computation time. The algorithm first uses a constructive heuristic to obtain an initial assignment and iteratively improves it in a greedy way. We study the performance of the proposed algorithm over a wide range of parameters including problem size, the ratio of average communication time to average computation time, and task interaction density. The viability and effectiveness of our algorithm is demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature.     

Cooperative game-based distributed resource allocation in horizontal dynamic cloud federation platform

Distributed resource allocation is a very important and complex problem in emerging horizontal dynamic cloud federation (HDCF) platforms, where different cloud providers (CPs) collaborate dynamically to gain economies of scale and enlargements of their virtual machine (VM) infrastructure capabilities in order to meet consumer requirements. HDCF platforms differ from the existing vertical supply chain federation (VSCF) models in terms of establishing federation and dynamic pricing. There is a need to develop algorithms that can capture this complexity and easily solve distributed VM resource allocation problem in a HDCF platform. In this paper, we propose a cooperative game-theoretic solution that is mutually beneficial to the CPs. It is shown that in non-cooperative environment, the optimal aggregated benefit received by the CPs is not guaranteed. We study two utility maximizing cooperative resource allocation games in a HDCF environment. We use price-based resource allocation strategy and present both centralized and distributed algorithms to find optimal solutions to these games. Various simulations were carried out to verify the proposed algorithms. The simulation results demonstrate that the algorithms are effective, showing robust performance for resource allocation and requiring minimal computation time.     

Secure dynamic fragment and replica allocation in large-scale distributed file systems

We present a distributed algorithm for file allocation that guarantees high assurance, availability, and scalability in a large distributed file system. The algorithm can use replication and fragmentation schemes to allocate the files over multiple servers. The file confidentiality and integrity are preserved, even in the presence of a successful attack that compromises a subset of the file servers. The algorithm is adaptive in the sense that it changes the file allocation as the read-write patterns and the location of the clients in the network change. We formally prove that, assuming read-write patterns are stable, the algorithm converges toward an optimal file allocation, where optimality is defined as maximizing the file assurance.     

Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization

This paper deals with the problem of task allocation (i.e., to which processor should each task of an application be assigned) in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation is known to be NP-hard in the strong sense. We propose a new swarm intelligence technique based on the honeybee mating optimization (HBMO) algorithm for this problem. The HBMO based approach combines the power of simulated annealing, genetic algorithms with a fast problem specific local search heuristic to find the best possible solution within a reasonable computation time. We study the performance of the algorithm over a wide range of parameters such as the number of tasks, the number of processors, the ratio of average communication time to average computation time, and task interaction density of applications. The effectiveness and efficiency of our algorithm are demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature.     

Deadline and energy constrained dynamic resource allocation in a heterogeneous computing environment

Energy-efficient resource allocation within clusters and data centers is important because of the growing cost of energy. We study the problem of energy-constrained dynamic allocation of tasks to a heterogeneous cluster computing environment. Our goal is to complete as many tasks by their individual deadlines and within the system energy constraint as possible given that task execution times are uncertain and the system is oversubscribed at times. We use Dynamic Voltage and Frequency Scaling (DVFS) to balance the energy consumption and execution time of each task. We design and evaluate (via simulation) a set of heuristics and filtering mechanisms for making allocations in our system. We show that the appropriate choice of filtering mechanisms improves performance more than the choice of heuristic (among the heuristics we tested).     

An autonomy-oriented computing approach to community mining in distributed and dynamic networks

A network community refers to a special type of network structure that contains a group of nodes connected based on certain relationships or similar properties. Our ability to mine communities hidden inside networks will readily enable us to effectively understand and exploit such networks. So far, various methods and algorithms have been developed to perform the task of community mining, where it is often required that the networks are processed in a centralized manner, and their structures will not dynamically change. However, in the real world, many applications involve distributed and dynamically evolving networks, in which resources and controls are not only decentralized but also updated frequently. It would be difficult for the existing methods to deal with these types of networks since their global topological representations are either not available or too hard to obtain due to their huge size, decentralization, and/or dynamic updates. The aim of our work is to address the problem of mining communities from a distributed and dynamic network. It differs from the previous ones in that here we introduce the notion of self-organizing agent networks, and provide an autonomy-oriented computing (AOC) approach to distributed and incremental mining of network communities. The AOC-based method utilizes reactive agents that can collectively detect and update community structures in a distributed and dynamically evolving network, based only on their local views and interactions. While providing detailed formulations, we present the results of our systematic validations using real-world benchmark networks as well as synthetic networks that include a distributed intelligent Portable Digital Assistant (iPDA) network example.     

Optimal flow control allocation policies in communication networkswith multiple message classes

Flow control is considered for M(⩾2) transmitting stations sending packets to a single receiver over a slotted time-multiplexed link. The optimal allocation problem is generalized to the case of nonidentical holding costs at the M transmitters. Qualitative properties of optimal discounted and time-average policies that reduce the computational complexity of the M-dimensional optimal flow control algorithm are derived. For M=2, a simple relationship between optimal allocations for states x and x +e_i (i=1,2) that leads to significant computational savings in the optimal algorithm is established     

Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system

We present a multi-heuristic evolutionary task allocation algorithm to dynamically map tasks to processors in a heterogeneous distributed system. It utilizes a genetic algorithm, combined with eight common heuristics, in an effort to minimize the total execution time. It operates on batches of unmapped tasks and can preemptively remap tasks to processors. The algorithm has been implemented on a Java distributed system and evaluated with a set of six problems from the areas of bioinformatics, biomedical engineering, computer science and cryptography. Experiments using up to 150 heterogeneous processors show that the algorithm achieves better efficiency than other state-of-the-art heuristic algorithms.     

Optimal sequencing and arrangement in distributed single-level treenetworks with communication delays

The problem of obtaining optimal processing time in a distributed computing system consisting of (N+1) processors and N communication links, arranged in a single-level tree architecture, is considered. It is shown that optimality can be achieved through a hierarchy of steps involving optimal load distribution, load sequencing, and processor-link arrangement. Closed-form expressions for optimal processing time is derived for a general case of networks with different processor speeds and different communication link speeds. Using these closed-form expressions, the paper analytically proves a number of significant results that in earlier studies were only conjectured from computational results. In addition, it also extends these results to a more general framework. The above analysis is carried out for the cases in which the root processor may or may not be equipped with a front-end processor. Illustrative examples are given for all cases considered     

An SLA-based cloud computing that facilitates resource allocation in the distributed data centers of a cloud provider

The number of cloud service users has increased worldwide, and cloud service providers have been deploying and operating data centers to serve the globally distributed cloud users. The resource capacity of a data center is limited, so distributing the load to global data centers will be effective in providing stable services. Another issue in cloud computing is the need for providers to guarantee the service level agreements (SLAs) established with consumers. Whereas various load balancing algorithms have been developed, it is necessary to avoid SLA violations (e.g., service response time) when a cloud provider allocates the load to data centers geographically distributed across the world. Considering load balancing and guaranteed SLA, therefore, this paper proposes an SLA-based cloud computing framework to facilitate resource allocation that takes into account the workload and geographical location of distributed data centers. The contributions of this paper include: (1) the design of a cloud computing framework that includes an automated SLA negotiation mechanism and a workload- and location-aware resource allocation scheme (WLARA), and (2) the implementation of an agent-based cloud testbed of the proposed framework. Using the testbed, experiments were conducted to compare the proposed schemes with related approaches. Empirical results show that the proposed WLARA performs better than other related approaches (e.g., round robin, greedy, and manual allocation) in terms of SLA violations and the provider’s profits. We also show that using the automated SLA negotiation mechanism supports providers in earning higher profits.     

电力线通信中动态子载波组分配

针对电力线通信自适应OFDM系统的限制条件,探讨在每OFDM符号内各RT用户要求的约束下,研究系统总功率地窖注水分配后多子载波上的速率自适应子载波分配模型,提出一种新的动态子载波组分配算法。在典型电力线信道环境下对其仿真,并与另外两种分配算法进行比较,结果表明,本文动态子载波组分配算法的复杂度大大减小,能满足多用户资源分配的多目标要求。     

Cost-oriented task allocation and hardware redundancy policies in heterogeneous distributed computing systems considering software reliability

Task allocation policy and hardware redundancy policy for distributed computing system (DCS) are of great importance as they affect many system characteristics such as system cost, system reliability and performance. In recent years, abundant research has been carried out on the optimal task allocation and/or hardware redundancy problem, most of which took a reliability-oriented approach, i.e., the optimization criterion was system reliability maximization. Nevertheless, besides system reliability, other system characteristics such as system cost may be of great concern to management. In this paper, we take a cost-oriented approach to the optimal task allocation and hardware redundancy problem for DCS, which addresses both system cost and system reliability issues. A system cost model which could reflect the impact of system unreliability on system cost is developed, and by minimizing the total system cost, a satisfactory level of system reliability could be reached simultaneously. In the reliability modeling and analysis of DCS, we take both hardware reliability and software reliability into account. Two numerical examples are given to illustrate the formulation and solution procedures, in which genetic algorithm is used. Results show that based on the developed system cost model, appropriate decision-makings on task allocation and hardware redundancy policies for DCS could be made, and the result obtained seems to be a fairly good trade-off between system cost and system reliability.     

Multimedia resource allocation strategy of wireless sensor networks using distributed heuristic algorithm in cloud computing environment

The virtualized resource allocation (mapping) algorithm is the core issue of network virtualization technology. Universal and excellent resource allocation algorithms not only provide efficient and reliable network resources sharing for systems and users, but also simplify the complexity of resource scheduling and management, improve the utilization of basic resources, balance network load and optimize network performance. Based on the application of wireless sensor network, this paper proposes a wireless sensor network architecture based on cloud computing. The WSN hardware resources are mapped into resources in cloud computing through virtualization technology, and the resource allocation strategy of the network architecture is proposed. The experiment evaluates the performance of the resource allocation strategy. The proposed heuristic algorithm is a distributed algorithm. The complexity of centralized algorithms is high, distributed algorithms can handle problems in parallel, and reduce the time required to get a good solution with limited traffic.