The surge in demand for computing resources in data centers coupled with the rise of environmental concerns has motivated cloud providers to reduce carbon emission due to computational energy consumption. An opportunity lies in the fluctuating availability of renewable energy over time and the variability of power sources over grid regions, leading to variations in space and time in carbon intensity. Exploiting such variations, this paper introduces Caspian, a carbon-aware workload scheduler in multi-cluster Kubernetes environments, which aims at reducing the Carbon Footprint (CFP) due to executing workloads, while satisfying Quality of Service (QoS) requirements. Caspian cooperates with a multi-cluster management platform to apply scheduling and placement decisions over distributed clusters. We present efficient optimization algorithms to achieve these goals. Further, we describe an implementation of Caspian, integrated with Multi Cluster App Dispatcher (MCAD), a multi-cluster management platform which handles queuing and dispatching of workloads over multiple clusters. Our experimental results show that Caspian effectively reduces CFP with reasonable QoS, compared to a baseline scheduler which only satisfies the QoS of workloads. Specifically, Caspian reduces CFP by about 33%, with about 98% of workloads completing at an average fraction of 0.6 of their deadline.

The amount of carbon emission associated with the computational energy consumption in data centers depends, in a significant way, on the schedule of the workloads. Due to the inconsistent availability of renewable energy over time, in addition to the existence of various sources of power in grid regions, the carbon intensity of data centers changes over time and location. Thus, the placement and scheduling of flexible workloads, based on the carbon intensity of power sources in data centers, can remarkably decrease the carbon emission. In this paper, we address the problem of placement and scheduling of workloads over geographically distributed data centers. We propose two algorithms that take the variability of carbon intensity of the power sources of the data centers, as well as their computational resource availability, into account when deciding about the placement and scheduling of the workloads. The first is a randomized rounding approximation algorithm that provides solutions that are guaranteed to be within a given distance from the optimal solution. The second is a sample-based algorithm that improves the solutions obtained by the randomized rounding approximation algorithm. The experimental results show that the proposed algorithms can solve the problem efficiently.

In Vehicular Edge Computing (VEC) systems, the computing resources of connected Electric Vehicles (EV) are used to fulfill the low-latency computation requirements of vehicles. However, local execution of heavy workloads may drain a considerable amount of energy in EVs. One promising way to improve the energy efficiency is to share and coordinate computing resources among connected EVs. However, the uncertainties in the future location of vehicles make it hard to decide which vehicles participate in resource sharing and how long they share their resources so that all participants benefit from resource sharing. In this paper, we propose VECMAN, a framework for energy-aware resource management in VEC systems composed of two algorithms: (i) a resource selector algorithm that determines the participating vehicles and the duration of resource sharing period; and (ii) an energy manager algorithm that manages computing resources of the participating vehicles with the aim of minimizing the computational energy consumption. We evaluate the proposed algorithms and show that they considerably reduce the vehicles’ computational energy consumption compared to the state-of-the-art baselines. Specifically, our algorithms achieve between 7 and 18 percent energy savings compared to a baseline that executes workload locally and an average of 13 percent energy savings compared to a baseline that offloads vehicles’ workloads to RSUs.

In this paper, we address the problem of workload scheduling in data centers, while considering the greenness of the power sources. We prove that finding a feasible solution for the problem is NP-hard. Therefore, we develop an LP-based approximation algorithm to solve the problem in polynomial time. The proposed algorithm provides strong approximation bounds on the constraints and the objective of the problem. We conduct an extensive experimental analysis to evaluate the performance of the proposed algorithm using real world data.

We design a parallel algorithm for the Constrained Shortest Path (CSP) problem. The CSP problem is known to be NP-hard and there exists a pseudo-polynomial time sequential algorithm that solves it. To design the parallel algorithm, we extend the techniques used in the design of the Δ-stepping algorithm for the single-source shortest paths problem.

In this article, we address the Multi-Component Application Placement Problem (${\sf MCAPP}$) in Mobile Edge Computing (MEC) systems. We formulate this problem as a Mixed Integer Non-Linear Program (MINLP) with the objective of minimizing the total cost of running the applications. In our formulation, we take into account two important and challenging characteristics of MEC systems, the mobility of users and the network capabilities. We analyze the complexity of${\sf MCAPP}$and prove that it is$NP$-hard, that is, finding the optimal solution in reasonable amount of time is infeasible. We design two algorithms, one based on matching and local search and one based on a greedy approach, and evaluate their performance by conducting an extensive experimental analysis driven by two types of user mobility models, real-life mobility traces and random-walk. The results show that the proposed algorithms obtain near-optimal solutions and require small execution times for reasonably large problem instances.

In this article, we address the resource allocation and monetization challenges in Mobile Edge Computing (MEC) systems, where users have heterogeneous demands and compete for high quality services. We formulate the Edge Resource Allocation Problem (ERAP) as a Mixed-Integer Linear Program (MILP) and prove that ERAP is NP-hard. To solve the problem efficiently, we propose two resource allocation mechanisms. First, we develop an auction-based mechanism and prove that the proposed mechanism is individually-rational and produces envy-free allocations. We also propose an LP-based approximation mechanism that does not guarantee envy-freeness, but it provides solutions that are guaranteed to be within a given distance from the optimal solution. We evaluate the performance of the proposed mechanisms by conducting an extensive experimental analysis on ERAP instances of various sizes. We use the optimal solutions obtained by solving the MILP model using a commercial solver as benchmarks to evaluate thequality of solutions. Our analysis shows that the proposed mechanisms obtain near optimal solutions for fairly large size instances of the problem in a reasonable amount of time.

The low-latency requirements of connected electric vehicles and their increasing computing needs have led to the necessity to move computational nodes from the cloud data centers to edge nodes such as road-side units (RSU). However, offloading the workload of all the vehicles to RSUs may not scale well to an increasing number of vehicles and workloads. To solve this problem, computing nodes can be installed directly on the smart vehicles, so that each vehicle can execute the heavy workload locally, thus forming a vehicular edge computing system. On the other hand, these computational nodes may drain a considerable amount of energy in electric vehicles. It is therefore important to manage the resources of connected electric vehicles to minimize their energy consumption. In this paper, we propose an algorithm that manages the computing nodes of connected electric vehicles for minimized energy consumption. The algorithm achieves energy savings for connected electric vehicles by exploiting the discrete settings of computational power for various performance levels. We evaluate the proposed algorithm and show that it considerably reduces the vehicles' computational energy consumption compared to state-of-the-art baselines. Specifically, our algorithm achieves 15-85% energy savings compared to a baseline that executes workload locally and an average of 51% energy savings compared to a baseline that offloads vehicles' workloads only to RSUs.

The Quality of Service (QoS) in Mobile Edge Computing (MEC) systems is significantly dependent on the application offloading and placement decisions. Due to the movement of users in MEC networks, an optimal application placement might turn into the least efficient placement in few minutes. Thus, it is crucial to take the dynamics of the system into account when designing application placement mechanisms. On the other hand, energy consumption of servers is a significant component of the cost of services in MEC systems and must also be considered in the design of the mechanisms. In this article, we model the problem of energy-aware application placement in edge computing systems as a multi-stage stochastic program. The objective is to maximize the QoS of the system while taking into account the limited energy budget of the edge servers. To solve the problem, we design a novel parallel Sample Average Approximation (SAA) algorithm. We conduct an extensive experimental analysis to evaluate the performance of the proposed algorithm using real-world trace data.

Mobile Edge Computing (MEC) is a new paradigm that aims at decreasing the response time of running mobile applications by offloading the component of the applications on the servers located at the edge of the network instead of on the cloud servers. In this paper, we address a very important problem in the management of MEC systems, that is, the problem of finding an efficient application placement on the edge servers such that the cost of execution is minimized. We develop a multi-stage stochastic programming model for the application placement problem in edge computing systems and design a novel parallel greedy algorithm based on the Sample Average Approximation method to solve it. We evaluate the performance of the proposed algorithm by conducting extensive experimental analysis using data extracted from a real-world dataset. The experimental results show that the proposed algorithm can solve the problem efficiently.

Recent works on quantum physical design have pushed the scheduling and placement of quantum circuit into their prominent positions. In this article, a mixed integer nonlinear programming model is proposed for the placement and scheduling of quantum circuits in such a way that latency is minimized. The proposed model determines locations of gates and the sequence of operations. The proposed model is proved reducible to a quadratic assignment problem which is a well-known NP-complete combinatorial optimization problem. Since it is impossible to find the optimal solution of this NP-complete problem for large quantum circuits within a reasonable amount of time, a metaheuristic solution method is developed for the proposed model. Some experiments are conducted to evaluate the performance of the developed solution approach. Experimental results show that the proposed approach improves average latency by about 24.09% for the attempted benchmarks.