Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPower-Aware Allocation of Graph Jobs in Geo-Distributed Cloud Networks
93
0
0.0
(
0
)
Added by
Seyyedali Hosseinalipour
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the era of big-data, the jobs submitted to the clouds exhibit complicated structures represented by graphs, where the nodes denote the sub-tasks each of which can be accommodated at a slot in a server, while the edges indicate the communication constraints among the sub-tasks. We develop a framework for efficient allocation of graph jobs in geo-distributed cloud networks (GDCNs), explicitly considering the power consumption of the datacenters (DCs). We address the following two challenges arising in graph job allocation: i) the allocation problem belongs to NP-hard nonlinear integer programming; ii) the allocation requires solving the NP-complete sub-graph isomorphism problem, which is particularly cumbersome in large-scale GDCNs. We develop a suite of efficient solutions for GDCNs of various scales. For small-scale GDCNs, we propose an analytical approach based on convex programming. For medium-scale GDCNs, we develop a distributed allocation algorithm exploiting the processing power of DCs in parallel. Afterward, we provide a novel low-complexity (decentralized) sub-graph extraction method, based on which we introduce cloud crawlers aiming to extract allocations of good potentials for large-scale GDCNs. Given these suggested strategies, we further investigate strategy selection under both fixed and adaptive DC pricing schemes, and propose an online learning algorithm for each.
rate research
Read More
Software-defined internet of vehicles (SDIoV) has emerged as a promising paradigm to realize flexible and comprehensive resource management, for next generation automobile transportation systems. In this paper, a vehicular cloud computing-based SDIoV framework is studied wherein the joint allocation of transmission power and graph job is formulated as a nonlinear integer programming problem. To effectively address the problem, a structure-preservation-based two-stage allocation scheme is proposed that decouples template searching from power allocation. Specifically, a hierarchical tree-based random subgraph isomorphism mechanism is applied in the first stage by identifying potential mappings (templates) between the components of graph jobs and service providers. A structure-preserving simulated annealing-based power allocation algorithm is adopted in the second stage to achieve the trade-off between the job completion time and energy consumption. Extensive simulations are conducted to verify the performance of the proposed algorithms.
Distributed dataflow systems like Spark and Flink enable the use of clusters for scalable data analytics. While runtime prediction models can be used to initially select appropriate cluster resources given target runtimes, the actual runtime performance of dataflow jobs depends on several factors and varies over time. Yet, in many situations, dynamic scaling can be used to meet formulated runtime targets despite significant performance variance. This paper presents Enel, a novel dynamic scaling approach that uses message propagation on an attributed graph to model dataflow jobs and, thus, allows for deriving effective rescaling decisions. For this, Enel incorporates descriptive properties that capture the respective execution context, considers statistics from individual dataflow tasks, and propagates predictions through the job graph to eventually find an optimized new scale-out. Our evaluation of Enel with four iterative Spark jobs shows that our approach is able to identify effective rescaling actions, reacting for instance to node failures, and can be reused across different execution contexts.
Vehicular cloud computing has emerged as a promising solution to fulfill users demands on processing computation-intensive applications in modern driving environments. Such applications are commonly represented by graphs consisting of components and edges. However, encouraging vehicles to share resources poses significant challenges owing to users selfishness. In this paper, an auction-based graph job allocation problem is studied in vehicular cloud-assisted networks considering resource reutilization. Our goal is to map each buyer (component) to a feasible seller (virtual machine) while maximizing the buyers utility-of-service, which concerns the execution time and commission cost. First, we formulate the auction-based graph job allocation as an integer programming (IP) problem. Then, a Vickrey-Clarke-Groves based payment rule is proposed which satisfies the desired economical properties, truthfulness and individual rationality. We face two challenges: 1) the above-mentioned IP problem is NP-hard; 2) one constraint associated with the IP problem poses addressing the subgraph isomorphism problem. Thus, obtaining the optimal solution is practically infeasible in large-scale networks. Motivated by which, we develop a structure-preserved matching algorithm by maximizing the utility-of-service-gain, and the corresponding payment rule which offers economical properties and low computation complexity. Extensive simulations demonstrate that the proposed algorithm outperforms the benchmark methods considering various problem sizes.
In cloud radio access networks (C-RANs), the baseband units and radio units of base stations are separated, which requires high-capacity fronthaul links connecting both parts. In this paper, we consider the delay-aware fronthaul allocation problem for C-RANs. The stochastic optimization problem is formulated as an infinite horizon average cost Markov decision process. To deal with the curse of dimensionality, we derive a closed-form approximate priority function and the associated error bound using perturbation analysis. Based on the closed-form approximate priority function, we propose a low-complexity delay-aware fronthaul allocation algorithm solving the per-stage optimization problem. The proposed solution is further shown to be asymptotically optimal for sufficiently small cross link path gains. Finally, the proposed fronthaul allocation algorithm is compared with various baselines through simulations, and it is shown that significant performance gain can be achieved.
Graph jobs represent a wide variety of computation-intensive tasks in which computations are represented by graphs consisting of components (denoting either data sources or data processing) and edges (corresponding to data flows between the components). Recent years have witnessed dramatic growth in smart vehicles and computation-intensive graph jobs, which pose new challenges to the provision of efficient services related to the Internet of Vehicles. Fortunately, vehicular clouds formed by a collection of vehicles, which allows jobs to be offloaded among vehicles, can substantially alleviate heavy on-board workloads and enable on-demand provisioning of computational resources. In this paper, we present a novel framework for vehicular clouds that maps components of graph jobs to service providers via opportunistic vehicle-to-vehicle communication. Then, graph job allocation over vehicular clouds is formulated as a non-linear integer programming with respect to vehicles contact duration and available resources, aiming to minimize job completion time and data exchange cost. The problem is addressed for two scenarios: low-traffic and rush-hours. For the former, we determine the optimal solutions for the problem. In the latter case, given the intractable computations for deriving feasible allocations, we propose a novel low complexity randomized graph job allocation mechanism by considering hierarchical tree based subgraph isomorphism. We evaluate the performance of our proposed algorithms through extensive simulations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
