A Cooperative Game Theoretical Technique for Joint Optimization of Energy Consumption and Response Time in Computational Grids

With the explosive growth in computers and the growing scarcity in electric supply, reduction of energy consumption in large-scale computing systems has become a research issue of paramount importance. In this paper, we study the problem of allocation of tasks onto a computational grid, with the aim to simultaneously minimize the energy consumption and the makespan subject to the constraints of deadlines and tasks' architectural requirements. We propose a solution from cooperative game theory based on the concept of Nash Bargaining Solution. In this cooperative game, machines collectively arrive at a decision that describes the task allocation that is collectively best for the system, ensuring that the allocations are both energy and makespan optimized. Through rigorous mathematical proofs we show that the proposed cooperative game in mere O(n mlog(m)) time (where n is the number of tasks and m is the number of machines in the system) produces a Nash Bargaining Solution that guarantees Pareto-optimally. The simulation results show that the proposed technique achieves superior performance compared to the Greedy and Linear Relaxation (LR) heuristics, and with competitive performance relative to the optimal solution implemented in LINDO for small-scale problems.     

A survey and taxonomy on energy efficient resource allocation techniques for cloud computing systems

In a cloud computing paradigm, energy efficient allocation of different virtualized ICT resources (servers, storage disks, and networks, and the like) is a complex problem due to the presence of heterogeneous application (e.g., content delivery networks, MapReduce, web applications, and the like) workloads having contentious allocation requirements in terms of ICT resource capacities (e.g., network bandwidth, processing speed, response time, etc.). Several recent papers have tried to address the issue of improving energy efficiency in allocating cloud resources to applications with varying degree of success. However, to the best of our knowledge there is no published literature on this subject that clearly articulates the research problem and provides research taxonomy for succinct classification of existing techniques. Hence, the main aim of this paper is to identify open challenges associated with energy efficient resource allocation. In this regard, the study, first, outlines the problem and existing hardware and software-based techniques available for this purpose. Furthermore, available techniques already presented in the literature are summarized based on the energy-efficient research dimension taxonomy. The advantages and disadvantages of the existing techniques are comprehensively analyzed against the proposed research dimension taxonomy namely: resource adaption policy, objective function, allocation method, allocation operation, and interoperability.     

A comparative study of rate monotonic schedulability tests

With the increased penetration of real-time systems into our surroundings, the selection of an efficient schedulability test under fixed priority system from a plethora of existing results, has become a matter of primary interest to real-time system designers. The need for a faster schedulability tests becomes more prominent when it applies to online systems, where processor time is a sacred resource and it is of central importance to assign processor to execute tasks instead of determining system schedulability. Under fixed priority nonpreemptive real-time systems, current schedulability tests (in exact form) can be divided into: response time based tests, and scheduling points tests. To the best of our knowledge, no comparative study of these test to date has ever been presented. The aim of this work is to assist the system designers in the process of selecting a suitable technique from the existing literature after knowing the pros and cons associated with these tests. We highlight the mechanism behind the feasibility tests, theoretically and experimentally. Our experimental results show that response time based tests are faster than scheduling points tests, which make the response time based tests an excellent choice for online systems.     

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.     

Road Oriented Traffic Information System for Vehicular Ad hoc Networks

Over the last few years, vehicular ad hoc networks (VANETs) have gained popularity for their interesting applications. To make efficient routing decisions, VANET routing protocols require road traffic density information for which they use density estimation schemes. This paper presents a distributed mechanism for road vehicular density estimation that considers multiple road factors, such as road length and junctions. Extensive simulations are carried out to analyze the effectiveness of the proposed technique. Simulation results suggested that, the proposed technique is more accurate compared to the existing technique. Moreover, it facilitate VANET routing protocols to increase packet delivery ratio and reduce end-to-end delay.     

Estimation of fog utility pricing: a bio-inspired optimisation techniques' perspective

ABSTRACT

Due to the limited data storage capacity available to Internet service providers and large-scale enterprises, the concept of resource sharing arises. The services can be given on lease to enterprises through Service Level Agreements. Being the extension of the cloud computing, fog computing architecture brings the resources near end users. In order to get the services on lease, the enterprises are supposed to pay for the resources or services which are being used by them. In this paper, four nature inspired algorithms are analysed in order to determine the efficient management of services or resources so that the cost of resources can be reduced and the billing can be attained through calculation of the utilised resources. Pigeon inspired optimization, enhanced differential evolution, binary bat algorithm and simple human learning optimization are used to evaluate the energy consumed by the edge nodes or cloudlets that in turn can be used for estimating the bill through the Time of Use pricing variable. We evaluate the aforementioned techniques to analyse their performance regarding the bill calculation on the basis of fog servers usage. Simulation results demonstrate that BAT algorithm gives significantly better results than other three algorithms in terms of resource utilisation and bill reduction.     

Distributed Online Algorithms for the Agent Migration Problem in WSNs

The mobile agent paradigm has been adopted by several systems in the area of wireless sensor networks as it enables a flexible distribution and placement of application components on nodes, at runtime. Most agent placement and migration algorithms proposed in the literature, assume that the communication rates between agents remain stable for a sufficiently long time to amortize the migration costs. Then, the problem is that frequent changes in the application-level communication may lead to several non-beneficial agent migrations, which may actually increase the total network cost, instead of decreasing it. To tackle this problem, we propose two distributed algorithms that take migration decisions in an online fashion, trying to deal with fluctuations in agent communication. The first algorithm is more of theoretical value, as it assumes infinite storage to keep information about the message exchange history of agents, while the second algorithm is a refined version that works with finite storage and limited information. We describe these algorithms in detail, and provide proofs for their competitive ratio vs. an optimal oracle. In addition, we evaluate the performance of the proposed algorithms for different parameter settings through a series of simulated experiments, also comparing their results with those achieved by an optimal static placement that is computed with full (a posteriori) knowledge of the execution scenarios. Our theoretical and experimental results are a strong indication for the robustness and effectiveness of the proposed algorithms.     

CA-DAG: Modeling Communication-Aware Applications for Scheduling in Cloud Computing

This paper addresses performance issues of resource allocation in cloud computing. We review requirements of different cloud applications and identify the need of considering communication processes explicitly and equally to the computing tasks. Following this observation, we propose a new communication-aware model of cloud computing applications, called CA-DAG. This model is based on Directed Acyclic Graphs that in addition to computing vertices include separate vertices to represent communications. Such a representation allows making separate resource allocation decisions: assigning processors to handle computing jobs, and network resources for information transmissions. The proposed CA-DAG model creates space for optimization of a number of existing solutions to resource allocation and for developing novel scheduling schemes of improved efficiency.