Quantum machine learning, crucial in the noisy intermediate-scale quantum (NISQ) era, confronts challenges in error mitigation. Current noise-aware training (NAT) methods often assume static error rates in quantum neural networks (QNNs), overlooking the dynamic nature of quantum noise. Our work highlights how error rates fluctuate over time and across different qubits, affecting QNN performance even when overall error rates are similar. We introduce a novel NAT strategy that dynamically adjusts to standard and fatal error conditions, incorporating a low-complexity search method to identify fatal errors during optimization. This strategy significantly improves robustness, maintaining competitive performance with leading NAT methods across varying error scenarios.

Classification tasks on ultra-lightweight devices demand devices that are resource-constrained and deliver swift responses. Binary Vector Symbolic Architecture (VSA) is a promising approach due to its minimal memory requirements and fast execution times compared to traditional machine learning (ML) methods. Nonetheless, binary VSA’s practicality is limited by its inferior inference performance and a design that prioritizes algorithmic over hardware optimization. This paper introduces UniVSA, a co-optimized binary VSA framework for both algorithm and hardware. UniVSA not only significantly enhances inference accuracy beyond current state-of-the-art binary VSA models but also reduces memory footprints. It incorporates novel, lightweight modules and design flow tailored for optimal hardware performance. Experimental results show that UniVSA surpasses traditional ML methods in terms of performance on resource-limited devices, achieving smaller memory usage, lower latency, reduced resource demand, and decreased power consumption.

Fairness and action smoothness are two crucial considerations in many online optimization problems, but they have yet to be addressed simultaneously. In this paper, we study a new and challenging setting of fairness-regularized smoothed online convex optimization with switching costs. First, to highlight the fundamental challenges introduced by the long-term fairness regularizer evaluated based on the entire sequence of actions, we prove that even without switching costs, no online algorithms can possibly achieve a sublinear regret or finite competitive ratio compared to the offline optimal algorithm as the problem episode length $T$ increases. Then, we propose **FairOBD** (Fairness-regularized Online Balanced Descent), which reconciles the tension between minimizing the hitting cost, switching cost, and fairness cost. Concretely, **FairOBD** decomposes the long-term fairness cost into a sequence of online costs by introducing an auxiliary variable and then leverages the auxiliary variable to regularize the online actions for fair outcomes. Based on a new approach to account for switching costs, we prove that **FairOBD** offers a worst-case asymptotic competitive ratio against a novel benchmark---the optimal offline algorithm with parameterized constraints---by considering $T\to\infty$. Finally, we run trace-driven experiments of dynamic computing resource provisioning for socially responsible AI inference to empirically evaluate **FairOBD**, showing that **FairOBD** can effectively reduce the total fairness-regularized cost and better promote fair outcomes compared to existing baseline solutions.

Artificial intelligence (AI) on tiny edge devices has become feasible thanks to the emergence of high-performance microcontrollers (MCUs) and lightweight machine learning (ML) models. Nevertheless, the cost and power consumption of these MCUs and the computation requirements of these ML algorithms still present barriers that prevent the widespread inclusion of AI functionality on smaller, cheaper, and lower-power devices. Thus, there is an urgent need for a more efficient ML algorithm and implementation strategy suitable for lower-end MCUs.

Deep neural network (DNN) models, despite their impressive performance, are vulnerable to exploitation by attackers who attempt to transfer them to other tasks for their own benefit. Current defense strategies mainly address this vulnerability at the model parameter level, leaving the potential of architectural-level defense largely unexplored. This paper, for the first time, addresses the issue of model protection by reducing transferability at the architecture level. Specifically, we present a novel neural architecture search (NAS)-enabled algorithm that employs zero-cost proxies and evolutionary search, to explore model architectures with low transferability. Our method, namely ArchLock, aims to achieve high performance on the source task, while degrading the performance on potential target tasks, i.e., locking the transferability of a DNN model. To achieve efficient cross-task search without accurately knowing the training data owned by the attackers, we utilize zero-cost proxies to speed up architecture evaluation and simulate potential target task embeddings to assist cross-task search with a binary performance predictor. Extensive experiments on NAS-Bench-201 and TransNAS-Bench-101 demonstrate that ArchLock reduces transferability by up to 30% and 50%, respectively, with negligible performance degradation on source tasks (<2%). The code is available at https://github.com/Tongzhou0101/ArchLock.

Public models offer predictions to a variety of downstream tasks and have played a crucial role in various AI applications, showcasing their proficiency in accurate predictions. However, the exclusive emphasis on prediction accuracy may not align with the diverse end objectives of downstream agents. Recognizing the public model's predictions as a service, we advocate for integrating the objectives of downstream agents into the optimization process. Concretely, to address performance disparities and foster fairness among heterogeneous agents in training, we propose a novel Equitable Objective. This objective, coupled with a policy gradient algorithm, is crafted to train the public model to produce a more equitable/uniform performance distribution across downstream agents, each with their unique concerns. Both theoretical analysis and empirical case studies have proven the effectiveness of our method in advancing performance equity across diverse downstream agents utilizing the public model for their decision-making. Codes and datasets are released at https://github.com/Ren-Research/Socially-Equitable-Public-Models.

Online Budgeted Matching (OBM) is a classic problem with important applications in online advertising, online service matching, revenue management, and beyond. Traditional online algorithms typically assume a small bid setting, where the maximum bid-to-budget ratio ($\kappa$) is infinitesimally small. While recent algorithms have tried to address scenarios with non-small or general bids, they often rely on the Fractional Last Matching (FLM) assumption, which allows for accepting partial bids when the remaining budget is insufficient. This assumption, however, does not hold for many applications with indivisible bids. In this paper, we remove the FLM assumption and tackle the open problem of OBM with general bids. We first establish an upper bound of $1-\kappa$ on the competitive ratio for any deterministic online algorithm. We then propose a novel meta algorithm, called MetaAd, which reduces to different algorithms with first known provable competitive ratios parameterized by the maximum bid-to-budget ratio $\kappa\in [0,1]$. As a by-product, we extend MetaAd to the FLM setting and get provable competitive algorithms. Finally, we apply our competitive analysis to the design learning- augmented algorithms.

Text watermarks for large language models (LLMs) have been commonly used to identify the origins of machine-generated content, which is promising for assessing liability when combating deepfake or harmful content. While existing watermarking techniques typically prioritize robustness against removal attacks, unfortunately, they are vulnerable to spoofing attacks: malicious actors can subtly alter the meanings of LLM-generated responses or even forge harmful content, potentially misattributing blame to the LLM developer. To overcome this, we introduce a bi-level signature scheme, Bileve, which embeds fine-grained signature bits for integrity checks (mitigating spoofing attacks) as well as a coarse-grained signal to trace text sources when the signature is invalid (enhancing detectability) via a novel rank-based sampling strategy. Compared to conventional watermark detectors that only output binary results, Bileve can differentiate 5 scenarios during detection, reliably tracing text provenance and regulating LLMs. The experiments conducted on OPT-1.3B and LLaMA-7B demonstrate the effectiveness of Bileve in defeating spoofing attacks with enhanced detectability.

The combination of the Bayesian game and learning has a rich history, with the idea of controlling a single agent in a system composed of multiple agents with unknown behaviors given a set of types, each specifying a possible behavior for the other agents. The idea is to plan an agent's own actions with respect to those types which it believes are most likely to maximize the payoff. However, the type beliefs are often learned from past actions and likely to be incorrect. With this perspective in mind, we consider an agent in a game with type predictions of other components, and investigate the impact of incorrect beliefs to the agent’s payoff. In particular, we formally define a tradeoff between risk and opportunity by comparing the payoff obtained against the optimal payoff, which is represented by a gap caused by trusting or distrusting the learned beliefs.Our main results characterize the tradeoff by establishing upper and lower bounds on the Pareto front for both normal-form and stochastic Bayesian games, with numerical results provided.

Carbon neutrality is a growing important objective for human activities, to prevent climate change. As for computer systems, we are urged to provide sustainability in computing to help mitigate such problems. As such, carbon neutrality shall occupy a critical role in the next-generation digital infrastructure. To this end, we have collected 15 established works towards carbon neutrality in computer systems in the Special Issue on Carbon-Neutral Computing for Next-Generation Digital Infrastructures.

Online optimization with multiple budget constraints is challenging since the online decisions over a short time horizon are coupled together by strict inventory constraints. The existing manually-designed algorithms cannot achieve satisfactory average performance for this setting because they often need a large number of time steps for convergence and/or may violate the inventory constraints. In this paper, we propose a new machine learning (ML) assisted unrolling approach, called LAAU (Learning-Assisted Algorithm Unrolling), which unrolls the agent’s online decision pipeline and leverages an ML model for updating the Lagrangian multiplier online. For efficient training via backpropagation, we derive gradients of the decision pipeline over time. We also provide the average cost bounds for two cases when training data is available offline and collected online, respectively. Finally, we present numerical results to highlight that LAAU can outperform the existing baselines.

Many problems, such as online ad display, can be formulated as online bipartite matching. The crucial challenge lies in the nature of sequentially-revealed online item information, based on which we make irreversible matching decisions at each step. While numerous expert online algorithms have been proposed with bounded worst-case competitive ratios, they may not offer satisfactory performance in average cases. On the other hand, reinforcement learning (RL) has been applied to improve the average performance, but it lacks robustness and can perform arbitrarily poorly. In this paper, we propose a novel RL-based approach to edge-weighted online bipartite matching with robustness guarantees (LOMAR), achieving both good average-case and worst-case performance. The key novelty of LOMAR is a new online switching operation which, based on a judicious condition to hedge against future uncertainties, decides whether to follow the expert’s decision or the RL decision for each online item. We prove that for any $\rho\in[0,1]$, LOMAR is $\rho$-competitive against any given expert online algorithm. To improve the average performance, we train the RL policy by explicitly considering the online switching operation. Finally, we run empirical experiments to demonstrate the advantages of LOMAR compared to existing baselines.

As a type of valuable intellectual property (IP), deep neural network (DNN) models have been protected by techniques like watermarking. However, such passive model protection cannot fully prevent model abuse. In this work, we propose an active model IP protection scheme, namely NNSplitter, which actively protects the model by splitting it into two parts: the obfuscated model that performs poorly due to weight obfuscation, and the model secrets consisting of the indexes and original values of the obfuscated weights, which can only be accessed by authorized users with the support of the trusted execution environment. Experimental results demonstrate the effectiveness of NNSplitter, e.g., by only modifying 275 out of over 11 million (i.e., 0.002%) weights, the accuracy of the obfuscated ResNet-18 model on CIFAR-10 can drop to 10%. Moreover, NNSplitter is stealthy and resilient against norm clipping and fine-tuning attacks, making it an appealing solution for DNN model protection. The code is available at: https://github.com/Tongzhou0101/NNSplitter.

Online optimization with memory costs has many real-world applications, where sequential actions are made without knowing the future input. Nonetheless, the memory cost couples the actions over time, adding substantial challenges. Conventionally, this problem has been approached by various expert-designed online algorithms with the goal of achieving bounded worst-case competitive ratios, but the resulting average performance is often unsatisfactory. On the other hand, emerging machine learning (ML) based optimizers can improve the average performance, but suffer from the lack of worst-case performance robustness. In this paper, we propose a novel expert-robustified learning (ERL) approach, achieving both good average performance and robustness. More concretely, for robustness, ERL introduces a novel projection operator that robustifies ML actions by utilizing an expert online algorithm; for average performance, ERL trains the ML optimizer based on a recurrent architecture by explicitly considering downstream expert robustification. We prove that, for any λ ≥ 1, ERL can achieve λ-competitive against the expert algorithm and λ•C-competitive against the optimal offline algorithm (where C is the expert’s competitive ratio). Additionally, we extend our analysis to a novel setting of multi-step memory costs. Finally, our analysis is supported by empirical experiments for an energy scheduling application.

We study the tradeoff between consistency and robustness in the context of a single-trajectory time-varying Markov Decision Process (MDP) with untrusted machine-learned advice. Our work departs from the typical approach of treating advice as coming from black-box sources by instead considering a setting where additional information about how the advice is generated is available. We prove a first-of-its-kind consistency and robustness tradeoff given Q-value advice under a general MDP model that includes both continuous and discrete state/action spaces. Our results highlight that utilizing Q-value advice enables dynamic pursuit of the better of machine-learned advice and a robust baseline, thus result in near-optimal performance guarantees, which provably improves what can be obtained solely with black-box advice.

We study a general form of Smoothed Online Convex Optimization, a.k.a. SOCO, including multi-step switching costs and feedback delay. We propose a novel machine learning (ML) augmented online algorithm, Robustness-Constrained Learning (RCL), which combines untrusted ML predictions with a trusted expert online algorithm via constrained projection to robustify the ML prediction. Specifically, we prove that RCL is able to guarantee $(1+\lambda)$-competitiveness against any given expert for any $\lambda>0$, while also explicitly training the ML model in a robustification-aware manner to improve the average-case performance. Importantly, RCL is the first ML-augmented algorithm with a provable robustness guarantee in the case of multi-step switching cost and feedback delay. We demonstrate the improvement of RCL in both robustness and average performance using battery management as a case study.

This paper studies the problem of Anytime-Competitive Markov Decision Process (A-CMDP). Existing works on Constrained Markov Decision Processes (CMDPs) aim to optimize the expected reward while constraining the expected cost over random dynamics, but the cost in a specific episode can still be unsatisfactorily high. In contrast, the goal of A-CMDP is to optimize the expected reward while guaranteeing a bounded cost in each round of any episode against a policy prior. We propose a new algorithm, called Anytime-Competitive Reinforcement Learning (ACRL), which provably guarantees the anytime cost constraints. The regret analysis shows the policy asymptotically matches the optimal reward achievable under the anytime competitive constraints. Experiments on the application of carbon-intelligent computing verify the reward performance and cost constraint guarantee of ACRL.

The rapid uptake of intelligent applications is pushing deep learning (DL) capabilities to mobile devices. However, the heterogeneities in device capacity, DNN performances, and user preferences make it challenging to provide satisfactory Quality of Experience (QoE) to mobile users. This paper studies automated customization for DL inference on mobile devices (termed as on-device inference), and our goal is to enhance user QoE by configuring the on-device inference with an appropriate DNN for users under different usage scenarios. The core of our method is a DNN selection module that learns user QoE patterns on-the-fly and identifies the best-fit DNN for on-device inference with the learned knowledge. It leverages an online learning algorithm,NeuralUCB, that has excellent generalization ability for handling various user QoE patterns. We also embed the knowledge transfer technique in NeuralUCB to expedite the learning process. However, NeuralUCB frequently solicits QoE ratings from users, which incurs non-negligible inconvenience. To address this problem, we design feedback solicitation schemes to reduce the number of QoE solicitations while maintaining the learning efficiency of NeuralUCB. A pragmatic problem,aggregated QoE, is further investigated to improve the practicality of our framework. We conduct experiments on both synthetic and real-world data. The results indicate that our method efficiently learns the user QoE pattern with few solicitations and provides drastic QoE enhancement for mobile devices.

Thanks to the tiny storage and efficient execution, hyperdimensional Computing (HDC) is emerging as a lightweight learning framework on resource-constrained hardware. Nonetheless, the existing HDC training relies on various heuristic methods, significantly limiting their inference accuracy. In this paper, we propose a new HDC framework, called LeHDC, which leverages a principled learning approach to improve the model accuracy. Concretely, LeHDC maps the existing HDC framework into an equivalent Binary Neural Network architecture, and employs a corresponding training strategy to minimize the training loss. Experimental validation shows that LeHDC outperforms previous HDC training strategies and can improve on average the inference accuracy over 15% compared to the baseline HDC.

Hyperdimensional Computing (HDC) is facing infringement issues due to straightforward computations. This work, for the first time, raises a critical vulnerability of HDC --- an attacker can reverse engineer the entire model, only requiring the unindexed hypervector memory. To mitigate this attack, we propose a defense strategy, namely HDLock, which significantly increases the reasoning cost of encoding. Specifically, HDLock adds extra feature hypervector combination and permutation in the encoding module. Compared to the standard HDC model, a two-layer-key HDLock can increase the adversarial reasoning complexity by 10 order of magnitudes without inference accuracy loss, with only 21% latency overhead.

Malicious architecture extraction has been emerging as a crucial concern for deep neural network (DNN) security. As a defense, architecture obfuscation is proposed to remap the victim DNN to a different architecture. Nonetheless, we observe that, with only extracting an obfuscated DNN architecture, the adversary can still retrain a substitute model with high performance (e.g., accuracy), rendering the obfuscation techniques ineffective. To mitigate this under-explored vulnerability, we propose ObfuNAS, which converts the DNN architecture obfuscation into a neural architecture search (NAS) problem. Using a combination of function-preserving obfuscation strategies, ObfuNAS ensures that the obfuscated DNN architecture can only achieve lower accuracy than the victim. We validate the performance of ObfuNAS with open-source architecture datasets like NAS-Bench-101 and NAS-Bench-301. The experimental results demonstrate that ObfuNAS can successfully find the optimal mask for a victim model within a given FLOPs constraint, leading up to 2.6% inference accuracy degradation for attackers with only 0.14× FLOPs overhead. The code is available at: https://github.com/Tongzhou0101/ObfuNAS.

By integrating domain knowledge with labeled samples, informed machine learning has been emerging to improve the learning performance for a wide range of applications. Nonetheless, rigorous understanding of the role of injected domain knowledge has been under-explored. In this paper, we consider an informed deep neural network (DNN) with over-parameterization and domain knowledge integrated into its training objective function, and study how and why domain knowledge benefits the performance. Concretely, we quantitatively demonstrate the two benefits of domain knowledge in informed learning {—} regularizing the label-based supervision and supplementing the labeled samples {—} and reveal the trade-off between label and knowledge imperfectness in the bound of the population risk. Based on the theoretical analysis, we propose a generalized informed training objective to better exploit the benefits of knowledge and balance the label and knowledge imperfectness, which is validated by the population risk bound. Our analysis on sampling complexity sheds lights on how to choose the hyper-parameters for informed learning, and further justifies the advantages of knowledge informed learning.

Learning to optimize (L2O) has recently emerged as a promising approach to solving optimization problems by exploiting the strong prediction power of neural networks and offering lower runtime complexity than conventional solvers. While L2O has been applied to various problems, a crucial yet challenging class of problems — robust combinatorial optimization in the form of minimax optimization — have largely remained under-explored. In addition to the exponentially large decision space, a key challenge for robust combinatorial optimization lies in the inner optimization problem, which is typically non-convex and entangled with outer optimization. In this paper, we study robust combinatorial optimization and propose a novel learning-based optimizer, called LRCO (Learning for Robust Combinatorial Optimization), which quickly outputs a robust solution in the presence of uncertain context. LRCO leverages a pair of learning-based optimizers — one for the minimizer and the other for the maximizer — that use their respective objective functions as losses and can be trained without the need of labels for training problem instances. To evaluate the performance of LRCO, we perform simulations for the task offloading problem in vehicular edge computing. Our results highlight that LRCO can greatly reduce the worst-case cost and improve robustness, while having a very low runtime complexity.

Continual learning faces a crucial challenge of catastrophic forgetting. To address this challenge, experience replay (ER) that maintains a tiny subset of samples from previous tasks has been commonly used. Existing ER works usually focus on refining the learning objective for each task with a static memory construction policy. In this paper, we formulate the dynamic memory construction in ER as a combinatorial optimization problem, which aims at directly minimizing the global loss across all experienced tasks. We first apply three tactics to solve the problem in the offline setting as a starting point. To provide an approximate solution to this problem under the online continual learning setting, we further propose the Global Pseudo-task Simulation (GPS), which mimics future catastrophic forgetting of the current task by permutation. Our empirical results and analyses suggest that the GPS consistently improves accuracy across four commonly used vision benchmarks. We have also shown that our GPS can serve as the unified framework for integrating various memory construction policies in existing ER works.

Edge devices, including, in particular, mobile devices, have been emerging as an increasingly more important platform for deep neural network (DNN) inference. Typically, multiple lightweight DNN models generated using different architectures and/or compression schemes can fit into a device, thus selecting an optimal one is crucial in order to maximize the users’ Quality of Experience (QoE) for edge inference. The existing approaches to device-aware DNN optimization are usually time consuming and not scalable in view of extremely diverse edge devices. More importantly, they focus on optimizing standard performance metrics (e.g., accuracy and latency), which may not translate into improvement of the users’ actual subjective QoE. In this article, we propose a novel automated and user-centric DNN selection engine, called$\mathsf {Aquaman}$, which keeps users into a closed loop and leverages their QoE feedback to guide DNN selection decisions. The core of$\mathsf {Aquaman}$is a neural network-based QoE predictor, which is continuously updated online. Additionally, we use neural bandit learning to balance exploitation and exploration, with a provably efficient QoE performance. Finally, we evaluate$\mathsf {Aquaman}$on a 15-user experimental study as well as synthetic simulations, demonstrating the effectiveness of$\mathsf {Aquaman}$.

A standard assumption in contextual multi-arm bandit is that the true context is perfectly known before arm selection. Nonetheless, in many practical applications (e.g., cloud resource management), prior to arm selection, the context information can only be acquired by prediction subject to errors or adversarial modification. In this paper, we study a novel contextual bandit setting in which only imperfect context is available for arm selection while the true context is revealed at the end of each round. We propose two robust arm selection algorithms: MaxMinUCB (Maximize Minimum UCB) which maximizes the worst-case reward, and MinWD (Minimize Worst-case Degradation) which minimizes the worst-case regret. Importantly, we analyze the robustness of MaxMinUCB and MinWD by deriving both regret and reward bounds compared to an oracle that knows the true context. Our results show that as time goes on, MaxMinUCB and MinWD both perform as asymptotically well as their optimal counterparts that know the reward function. Finally, we apply MaxMinUCB and MinWD to online edge datacenter selection, and run synthetic simulations to validate our theoretical analysis.

Contextual multi-armed bandit (MAB) is a classic online learning problem, where a learner/agent selects actions (i.e., arms) given contextual information and discovers optimal actions based on reward feedback. Applications of contextual bandit have been increasingly expanding, including advertisement, personalization, resource allocation in wireless networks, among others. Nonetheless, the reward feedback is delayed in many applications (e.g., a user may only provide service ratings after a period of time), creating challenges for contextual bandits. In this paper, we address delayed feedback in contextual bandits by using semi-supervised learning — incorporate estimates of delayed rewards to improve the estimation of future rewards. Concretely, the reward feedback for an arm selected at the beginning of a round is only observed by the agent/learner with some observation noise and provided to the agent after some a priori unknown but bounded delays. Motivated by semi-supervised learning that produces pseudo labels for unlabeled data to further improve the model performance, we generate fictitious estimates of rewards that are delayed and have yet to arrive based on already-learnt reward functions. Thus, by combining semi-supervised learning with online contextual bandit learning, we propose a novel extension and design two algorithms, which estimate the values for currently unavailable reward feedbacks to minimize the maximum estimation error and average estimation error, respectively.

The widespread adoption of Internet of Things and latency-critical applications has fueled the burgeoning development of edge colocation data centers (a.k. a., edge colocation) — small-scale data centers in distributed locations. In an edge colocation, multiple entities/tenants house their own physical servers together, sharing the power and cooling infrastructures for cost efficiency and scalability. In this paper, we discover that the sharing of cooling systems also exposes edge colocations’ potential vulnerabilities to cooling load injection attacks (called thermal attacks) by an attacker which, if left at large, may create thermal emergencies and even trigger system outages. Importantly, thermal attacks can be launched by leveraging the emerging architecture of built-in batteries integrated with servers that can conceal the attacker’s actual server power (or cooling load). We consider both one-shot attacks (which aim at creating system outages) and repeated attacks (which aim at causing frequent thermal emergencies). For repeated attacks, we present a foresighted attack strategy which, using reinforcement learning, learns on the fly a good timing for attacks based on the battery state and benign tenants’ load. We also combine prototype experiments with simulations to validate our attacks and show that, for a small 8kW edge colocation, an attacker can potentially cause significant losses. Finally, we suggest effective countermeasures to the potential threat of thermal attacks.

Contextual bandit learning selects actions (i.e., arms) based on context information to maximize rewards while balancing exploitation and exploration. In many applications (e.g., cloud resource management with dynamic workloads), before arm selection, the agent/learner can either predict context information online based on context history or selectively query the context from an outside expert. Motivated by this practical consideration, we study a novel contextual bandit setting where context information is either predicted online or queried from an expert. First, considering predicted context only, we quantify the impact of context prediction on the cumulative regret (compared to an oracle with perfect context information) by deriving an upper bound on regret, which takes the form of a weighted combination of regret incurred by standard bandit learning and the context prediction error. Then, inspired by the regret's structural decomposition, we propose context query algorithms to selectively obtain outside expert's input (subject to a total query budget) for more accurate context, decreasing the overall regret. Finally, we apply our algorithms to virtual machine scheduling on cloud platforms. The simulation results validate our regret analysis and shows the effectiveness of our selective context query algorithms.

The microservice architecture is a hot trend which proposes to transform the traditional monolith application into massive dynamic and irregular small services. To boost the overall throughput and ensure the guaranteed latency, it is desirable to process massive service requests in parallel with efficient resource sharing in data centers. However, the disaggregation nature of microservice unavoidably upscales the design space of resource management and increases its complexity. In this paper, we propose AlphaR, a learning-powered resource management system tailored to the microservice environment. The basic idea of AlphaR is to generate microservice-specific resource management policies for improving efficiency. Specifically, we take the first step to use bipartite graph as a convenient abstraction for application built with microservices. Based on this, we devise a bipartite feature inference approach named Bi-GNN to extract the temporal characteristics of microservices. Furthermore, we implement a policy network to select appropriate resource allocation choices for maximizing the performance in resource-constrained data centers. AlphaR can improve the mean and p95 response time by up to 80% and 77.5% respectively compared with conventional schemes.

The majority of today's power-hungry datacenters are physically co-located with office rooms in mixed-use buildings (MUBs). The heating, ventilation, and air conditioning (HVAC) system within each MUB is often shared or partially-shared between datacenter rooms and office zones, for removing the heat generated by computing equipment and maintaining desired room temperature for building tenants. To effectively reduce the total energy cost of MUBs, it is important to leverage the scheduling flexibility in both the HVAC system and the datacenter workload. In this work, we formulate both HVAC control and datacenter workload scheduling as a Markov decision process (MDP), and propose a deep reinforcement learning (DRL) based algorithm for minimizing the total energy cost while maintaining desired room temperature and meeting datacenter workload deadline constraints. Moreover, we also develop a heuristic DRL-based algorithm to enable interactive workload allocation among geographically distributed MUBs for further energy reduction. The experiment results demonstrate that our regular DRL-based algorithm can achieve up to 26.9 percent cost reduction for a single MUB, when compared with a baseline strategy. Our heuristic DRL-based algorithm can reduce the total energy cost by an additional 5.5 percent, when intelligently allocating interactive workload for multiple geographically distributed MUBs.

With the rapid development of the Internet of Things (IoT), computational workloads are gradually moving toward the internet edge for low latency. Due to significant workload fluctuations, edge data centers built in distributed locations suffer from resource underutilization and requires capacity underprovisioning to avoid wasting capital investment. The workload fluctuations, however, also make edge data centers more suitable for battery-assisted power management to counter the performance impact due to underprovisioning. In particular, the workload fluctuations allow the battery to be frequently recharged and made available for temporary capacity boosts. But, using batteries can overload the data center cooling system which is designed with a matching capacity of the power system. In this paper, we design a novel power management solution, DeepPM, that exploits the UPS battery and cold air inside the edge data center as energy storage to boost the performance. DeepPM uses deep reinforcement learning (DRL) to learn the data center thermal behavior online in a model-free manner and uses it on-the-fly to determine power allocation for optimum latency performance without overheating the data center. Our evaluation shows that DeepPM can improve latency performance by more than 50% compared to a power capping baseline while the server inlet temperature remains within safe operating limits (e.g., 32°C).

With the deployment of artificial intelligent (AI) algorithms in a large variety of applications, there creates an increasing need for high-performance computing capabilities. As a result, different hardware platforms have been utilized for acceleration purposes. Among these hardware-based accelerators, the field-programmable gate arrays (FPGAs) have gained a lot of attention due to their re-programmable characteristics, which provide customized control logic and computing operators. For example, FPGAs have recently been adopted for on-demand cloud services by the leading cloud providers like Amazon and Microsoft, providing acceleration for various compute-intensive tasks. While the co-residency of multiple tenants on a cloud FPGA chip increases the efficiency of resource utilization, it also creates unique attack surfaces that are under-explored. In this paper, we exploit the vulnerability associated with the shared power distribution network on cloud FPGAs. We present a stealthy power attack that can be remotely launched by a malicious tenant, shutting down the entire chip and resulting in denial-of-service for other co-located benign tenants. Specifically, we propose stealthy-shutdown: a well-timed power attack that can be implemented in two steps: (1) an attacker monitors the realtime FPGA power-consumption detected by ring-oscillator-based voltage sensors, and (2) when capturing high power-consuming moments, i.e., the power consumption by other tenants is above a certain threshold, she/he injects a well-timed power load to shut down the FPGA system. Note that in the proposed attack strategy, the power load injected by the attacker only accounts for a small portion of the overall power consumption; therefore, such attack strategy remains stealthy to the cloud FPGA operator. We successfully implement and validate the proposed attack on three FPGA evaluation kits with running real-world applications. The proposed attack results in a stealthy-shutdown, demonstrating severe security concerns of co-tenancy on cloud FPGAs. We also offer two countermeasures that can mitigate such power attacks.

Deep neural networks (DNNs) have been increasingly deployed on and integrated with edge devices, such as mobile phones, drones, robots and wearables. Compared to cloud-based inference, running DNN inference directly on edge devices (a.k. a. edge inference) has major advantages, including being free from the network connection requirement, saving bandwidths, and better protecting user privacy [1].

Contextual bandit is a classic multi-armed bandit setting, where side information (i.e., context) is available before arm selection. A standard assumption is that exact contexts are perfectly known prior to arm selection and only single feedback is returned. In this work, we focus on multi-feedback bandit learning with probabilistic contexts, where a bundle of contexts are revealed to the agent along with their corresponding probabilities at the beginning of each round. This models such scenarios as where contexts are drawn from the probability output of a neural network and the reward function is jointly determined by multiple feedback signals. We propose a kernelized learning algorithm based on upper confidence bound to choose the optimal arm in reproducing kernel Hilbert space for each context bundle. Moreover, we theoretically establish an upper bound on the cumulative regret with respect to an oracle that knows the optimal arm given probabilistic contexts, and show that the bound grows sublinearly with time. Our simula- tion on machine learning model recommendation further validates the sub-linearity of our cumulative regret and demonstrates that our algorithm outper- forms the approach that selects arms based on the most probable context.

The massive energy consumption of data centers worldwide has resulted in a large carbon footprint, raising serious concerns to sustainable IT initiatives and attracting a great amount of research attention. Nonetheless, the current efforts to date, despite encouraging, have been primarily centered around owner-operated data centers (e.g., Google data center), leaving out another major segment of data center industry-colocation data centers-much less explored. As a major hindrance to carbon efficiency desired by the operator, colocation suffers from “split incentive”: tenants may not be willing to manage their servers for carbon efficiency. In this paper, we aim at minimizing the carbon footprint of geo-distributed colocation data centers, while ensuring that the operator's cost meets a long-term budget constraint. We overcome the “split incentive” hurdle by devising a novel online carbon-aware incentive mechanism, called GreenColo, in which tenants voluntarily bid for energy reduction at self-determined prices and will receive financial rewards if their bids are accepted at runtime. Using trace based simulation we show that GreenColo results in a carbon footprint fairly close (23 versus 18 percent) to the optimal offline solution with future information, while being able to satisfy the colocation operator's long-term budget constraint. We demonstrate the effectiveness of GreenColo in practical scenarios via both simulation studies and scaled-down prototype experiments. Our results show that GreenColo can reduce the carbon footprint by up to 24 percent without incurring any additional cost for the colocation operator (compared to the no-incentive baseline case), while tenants receive financial rewards for “free” without violating service level agreement.

In view of the high capital expense for scaling up power capacity to meet the escalating demand, maximizing the utilization of built capacity has become a top priority for multi-tenant data center operators, where many cloud providers house their physical servers. The traditional power provisioning guarantees a high availability, but is very costly and results in a significant capacity under-utilization. On the other hand, power oversubscription (i.e., deploying more servers than what the capacity allows) improves utilization but offers no availability guarantees due to the necessity of power reduction to handle the resulting power emergencies. Given these limitations, we propose a novel hybrid power provisioning approach, called HyPP, which provides a combination of two different power availabilities to tenants: capacity with a very high availability (100 percent or nearly 100 percent), plus additional capacity with a medium availability that may be unavailable for up to a certain amount during each billing period. For HyPP, we design an online algorithm for the operator to coordinate tenants' power reduction at runtime when the tenants' aggregate power demand exceeds the power capacities. Our algorithm aims at achieving long-term fairness in tenants' power reduction (defined as the ratio of total actual power reduction by a tenant to its contracted reduction budget over a billing period). We analyze the theoretical performance of our online algorithm and derive a good competitive ratio in terms of fairness compared to the offline optimum. We also validate our algorithm through simulations under realistic settings.

Data centers are key participants in emergency demand response (EDR), where the grid coordinates large electricity consumers for reducing their consumption during emergency situations to prevent major economic losses. While existing literature concentrates on owner-operated data centers (e.g., Google), this work studies EDR in multi-tenant colocation data centers (e.g., Equinix) where servers are owned and managed by individual tenants and which are better targets of EDR. Existing EDR mechanisms incentivize tenants energy reduction. Such designs can either be gamed by strategic tenants or untrustworthy colocation operators for illegal gains. These serious privacy concerns stand as barrier preventing the tenants' participation in EDR. This paper addresses such concerns by proposing a privacy-preserving and strategy-proof mechanism using the descending clock auction. Privacy is protected by implementing homomorphic encryption for aggregation through the clock auction, where operator can only know the aggregate of the tenants' values or bids but not their individual private values or confidential information submitted to meet the EDR. We evaluate the privacy and performance of this scheme by formulating descending clock auction, in which the amount of energy/price the tenants are willing to reduce for a given price/energy to meet EDR is protected.

Although network function virtualization (NFV) is a promising approach for providing elastic network functions, it faces several challenges in terms of adaptation to diverse network appliances and reduction of the capital and operational expenses of the service providers. In particular, to deploy service chains, providers must consider different objectives, such as minimizing the network latency or the operational cost, which are coupled objectives that have traditionally been addressed separately. In this paper, the problem of virtual network function (vNF) placement for service chains is studied for the purpose of energy and traffic-aware cost minimization. This problem is formulated as an optimization problem named the joint operational and network traffic cost (OPNET) problem. First, a sampling-based Markov approximation (MA) approach is proposed to solve the combinatorial NP-hard problem, OPNET. Even though the MA approach can yield a near-optimal solution, it requires a long convergence time that can hinder its practical deployment. To overcome this issue, a novel approach that combines the MA with matching theory, named as SAMA, is proposed to find an efficient solution for the original problem OPNET. Simulation results show that the proposed framework can reduce the total incurred cost by up to 19 percent compared to the existing non-coordinated approach.

In recent years, as a result of the rapidly growing volume of generated data, computation has been increasingly migrating from megascale data centers to Internet edges (a.k.a edge computing), for avoiding high latencies and overwhelmed bandwidths. Unlike centralized clouds, edge computing processes workloads generated by users nearby. Thus, due to the lack of statistical multiplexing from a large group of users, the resource demand at an edge data center exhibits more fluctuations, resulting in time-varying unused computation resources. In this paper, we propose our UNusEd spAred VM Re-uTilizing mecHanism, UNEARTH, to utilize different types of unused resources, such as storage, CPU, GPU, and so on, offered by an edge computing provider. Notably, the exact amount of unused VM resources is unknown before selling them. We evaluate the performance of our algorithms under realistic settings, showing that our proposed VM bundle allocation algorithm can achieve (1+ Ω/Ω-1 ε (e)M1/Ω-1-1)-approximation in the worst case compared with optimums; and overall, our algorithms outperform the existing and heuristic algorithms.

Maliciously-injected power load, a.k.a. power attack, has recently surfaced as a new egregious attack vector for dangerously compromising the data center availability. This paper focuses on the emerging threat of power attacks in a multi-tenant colocation data center, an important type of data center where multiple tenants house their own servers and share the power distribution system. Concretely, we discover a novel physical side channel --- a voltage side channel --- which leaks the benign tenants' power usage information at runtime and helps an attacker precisely time its power attacks. The key idea we exploit is that, due to the Ohm's Law, the high-frequency switching operation (40~100kHz) of the power factor correction circuit universally built in today's server power supply units creates voltage ripples in the data center power lines. Importantly, without overlapping the grid voltage in the frequency domain, the voltage ripple signals can be easily sensed by the attacker to track the benign tenants' runtime power usage and precisely time its power attacks. We evaluate the timing accuracy of the voltage side channel in a real data center prototype, demonstrating that the attacker can extract benign tenants' power pattern with a great accuracy (correlation coefficient = 0.90+) and utilize 64% of all the attack opportunities without launching attacks randomly or consecutively. Finally, we highlight a few possible defense strategies and extend our study to more complex three-phase power distribution systems used in large multi-tenant data centers.

Despite the common practice of oversubscription, power capacity is largely under-utilized in data centers. A significant factor driving this under-utilization is fluctuation of the aggregate power demand, resulting in unused “spot (power) capacity”. In this paper, we tap into spot capacity for improving power infrastructure utilization in multi-tenant data centers, an important but under-explored type of data center where multiple tenants house their own physical servers. We propose a novel market, called SpotDC, to allocate spot capacity to tenants on demand. Specifically, SpotDC extracts tenants' racklevel spot capacity demand through an elastic demand function, based on which the operator sets the market price for spot capacity allocation. We evaluate SpotDC using both testbed experiments and simulations, demonstrating that SpotDC improves power infrastructure utilization and creates a “win-win” situation: the data center operator increases its profit (by nearly 10%), while tenants improve their performance (by 1.2-1.8x on average compared to the no spot capacity case, yet at a marginal cost).

Energy accounting plays a crucial role in datacenter energy management, wherein the energy consumption of non-IT units (e.g., UPS and cooling system) makes up a significant portion. However, it is challenging to fairly account for non-IT energy on an individual VM basis, because the non-IT units are shared by multiple VMs in a virtualized datacenter and only the system-level non-IT energy consumption can be measured. Existing policies, e.g., equally or proportionally allocating non-IT energy to VMs based on their IT energy, are not fair, in the sense that they can not satisfy a set of desired axiomatic principles of fair allocation. In this paper, we propose LEAPS, a Lightweight Energy Accounting Policy based on a provably fair methodology called Shapley value. We evaluate it using real-world datacenter trace and demonstrate that, compared to original Shapley value approach that has an exponential complexity, LEAPS yields almost the same energy accounting result within a maximum relative error less than 6.97%, while having a negligible computation time.

Installation of backup power supply plays a vital role in maintaining communication services which can save billions of dollars as well as human lives during natural disasters. Due to the higher capital and operational expense compared to public power, pooling and sharing the backup power supplies can be an economical solution since the backup power capacity can be sized based on the aggregate demand of co-located operators. However, how to pool and share the backup power at multi-operator cellular sites in a fair manner should be considered due to the limited capacity and high user demands. In this paper, we adopt the Nash Bargaining Solution (NBS) of a bargaining problem which can guarantee the fairness of backup power sharing and design a decentralized algorithm approach with limited information exchange among the operators. Our simulation demonstrates that the sharing the backup power reduces the average delay and requires less BS power consumption than the non-sharing approach, especially for high traffic load scenarios. In addition, we also extend the formulation with respect to admission control for very high traffic demand cases.

As the critical infrastructure for supporting Internet and cloud computing services, massive geo-distributed data centers are notorious for their huge electricity appetites and carbon footprints. Nonetheless, a lesser-known fact is that data centers are also “thirsty”: to operate data centers, millions of gallons of water are required for cooling and electricity production. The existing water-saving techniques primarily focus on improved “engineering” (e.g., upgrading to air economizer cooling, diverting recycled/sea water instead of potable water) and do not apply to all data centers due to high upfront capital costs and/or location restrictions. In this paper, we propose a software-based approach towards water conservation by exploiting the inherent spatio-temporal diversity of water efficiency across geo-distributed data centers. Specifically, we propose a batch job scheduling algorithm, called WACE (minimization of WAter, Carbon and Electricity cost), which dynamically adjusts geographic load balancing and resource provisioning to minimize the water consumption along with carbon emission and electricity cost while satisfying average delay performance requirement. WACE can be implemented online without foreseeing the far future information and yields a total cost (incorporating electricity cost, water consumption and carbon emission) that is provably close to the optimal algorithm with lookahead information. Finally, we validate WACE through a trace-based simulation study and show that WACE outperforms state-of-the-art benchmarks: 25 percent water saving while incurring an acceptable delay increase. We also extend WACE to joint scheduling of batch workloads and delay-sensitive interactive workloads for further water footprint reduction in geo-distributed data centers.

The ever-increasing computational demand drives modern electronic devices to integrate more processing elements for pursuing higher computing performance. However, the resulting soaring power density and potential thermal crisis constrain the system performance under a maximally allowed temperature. This paper analytically studies the throughput maximization problem of multi-core platforms under the peak temperature constraints. To take advantage of thermal heterogeneity of different cores for performance improvement, we propose to run each core with multiple speed levels and develop a schedule based on two novel concepts, i.e., the step-up schedule and the m-Oscillating schedule, for multi-core platforms. The proposed methodology can ensure the peak temperature guarantee with a significant improvement in computing throughput up to 89 percent, with an average improvement of 11 percent. Meanwhile, the computational time reduces orders of magnitude compared to the traditional exhaustive search-based approach.

Shared edge computing platforms deployed at the radio access network are expected to significantly improve the quality-of-service delivered by application service providers (ASPs) in a flexible and economic way. However, placing edge service in every possible edge site by an ASP is practically infeasible due to the ASP’s prohibitive budget requirement. In this paper, we investigate the edge service placement problem of an ASP under a limited budget, where the ASP dynamically rents computing/storage resources in edge sites to host its applications in close proximity to end users. Since the benefit of placing edge service in a specific site is usually unknown to the ASPa priori, optimal placement decisions must be made while learning this benefit. We pose this problem as a novel combinatorial contextual bandit learning problem. It is “combinatorial” because only a limited number of edge sites can be rented to provide the edge service given the ASP’s budget. It is “contextual” because we utilize user context information to enable finer-grained learning and decision-making. To solve this problem and optimize the edge computing performance, we propose SEEN, a Spatial-temporal Edge sErvice placemeNt algorithm. Furthermore, SEEN is extended to scenarios with overlapping service coverage by incorporating a disjunctively constrained knapsack problem. In both cases, we prove that our algorithm achieves a sublinear regret bound when it is compared with an Oracle algorithm that knows the exact benefit information. Simulations are carried out on a real-world dataset, whose results show that SEEN significantly outperforms benchmark solutions.

Keeping wireless base stations operating continually and providing uninterrupted communications services can save billions of dollars as well as human lives during natural disasters and/or electricity outages. Toward this end, wireless operators need to install backup power supplies whose capacity is sufficient to support their peak power demand, thus incurring a significant capital expense. Hence, pooling together backup power supplies and sharing it among co-located wireless operators can effectively reduce the capital expense, as the backup power capacity can be sized based on the aggregate demand of co-located operators instead of individual demand. Turning this vision into reality, however, faces a new challenge: how to fairly share the backup power supply? In this paper, we propose fair sharing of backup power supply by multiple wireless operators based on the Nash bargaining solution (NBS). In addition, we integrate our analysis with multiple time slots for emergency cases in which the study the backup energy sharing based on model predictive control and NBS subject to an energy capacity constraint regarding future service availability. Our simulations demonstrate that sharing backup power/energy improves the communications service quality with lower cost and consumes less base station power than the non-sharing approach.

The power capacity of multi-tenant data centers is typically oversubscribed in order to increase the utilization of expensive power infrastructure. This practice can create dangerous situations and compromise data center availability if the designed power capacity is exceeded. This paper demonstrates that current safeguards are vulnerable to well-timed power attacks launched by malicious tenants (i.e., attackers). Further, we demonstrate that there is a physical side channel --- a thermal side channel due to hot air recirculation --- that contains information about the benign tenants' runtime power usage and can enable a malicious tenant to time power attacks effectively. In particular, we design a state-augmented Kalman filter to extract this information from the side channel and guide an attacker to use its maximum power at moments that coincide with the benign tenants' high power demand, thus overloading the shared power capacity. Our experimental results show that an attacker can capture 54% of all attack opportunities, significantly compromising the data center availability. Finally, we discuss a set of possible defense strategies to safeguard the data center infrastructure against power attacks.

In this paper, we study the problem of how to schedule real-time tasks on multi-core platforms to maximize the energy efficiency under a peak temperature constraint. Different from the traditional load-balancing approach, we propose energy saving solutions under the ``thermal balancing'' heuristic, which can effectively avoid hotspots and maximize the throughput. We first establish and formally prove a lower bound of energy when scheduling a periodic task set on a multi-core platform using the thermal-balancing approach. Considering the NP-nature of this problem, we formulate the problem as a variable-sized-bin-packing~(VSBP) problem and develop a partitioning heuristic.

Emergency Demand Response (EDR) is crucial for improving the grid reliability and for meeting the power demand during crisis. Power-hungry data centers have been facing an urge to reduce their consumption to meet the EDR. The energy reduction in colocation data centers which house servers for multiple tenants (e.g., Equinix) that are better targets for EDR is less explored than the energy reduction in owner-operated data centers (e.g., Google). Existing EDR mechanisms incentivize tenants energy reduction. Such designs can either be gamed by strategic tenants or untrustworthy colocation operators for illegal gains. These serious privacy concerns stand as barrier preventing the tenants' participation in EDR. This paper addresses such concerns by proposing a privacy-preserving and strategy-proof mechanism using descending clock auction. Privacy is protected by implementing homomorphic encryption for aggregation of energy through clock auction, where operator can only know the aggregate of the tenants' values or bids but not their individual private values or confidential information submitted to meet the EDR. We evaluate the privacy and performance of this scheme by formulation through descending clock auction, in which the amount of energy the tenants are willing to reduce for a given price to meet EDR is protected.

Web search constitutes an important class of data-intensive online services in data centers. Optimizing search systems for energy efficiency, timely response and high search quality (i.e., how relevant the returned results are to a search query), however, is very challenging, as a search system involves a distributed architecture with hundreds of thousands of index serving nodes (ISNs) that return searching results to an aggregator through multiple interdependent retrieval stages in a partition-aggregate fashion. In this paper, we discover through experiments two important characteristics that can affect the system performance: (1) response time and energy consumption are greatly impacted by a small fraction of queries with long processing times; (2) the quality contribution of the ISN is independent of the query processing time. Based on our observation, we propose TailCut, which judiciously discards long query executions and enables ISN-aggregator coordination to minimize energy consumption subject to latency and quality constraints. Our experimental results show that TailCut can achieve up to 39% power saving, while satisfying the tail latency and quality constraint.

Spreading across many parts of the world and presently hard striking California, extended droughts could even potentially threaten reliable electricity production and local water supplies, both of which are critical for data center operation. While numerous efforts have been dedicated to reducing data centers' energy consumption, the enormity of data centers' water footprints is largely neglected and, if still left unchecked, may handicap service availability during droughts. In this paper, we propose a water-aware workload management algorithm, called WATCH (WATer-constrained workload sCHeduling in data centers), which caps data centers' long-term water consumption by exploiting spatio-temporal diversities of water efficiency and dynamically dispatching workloads among distributed data centers. We demonstrate the effectiveness of WATCH both analytically and empirically using simulations: based on only online information, WATCH can result in a provably-low operational cost while successfully capping water consumption under a desired level. Our results also show that WATCH can cut water consumption by 20 percent while only incurring a negligible cost increase even compared to state-of-the-art cost-minimizing but water-oblivious solution. Sensitivity studies are conducted to validate WATCH under various settings.

The uncertainty due to performance variations of IC chips and resource sharing on multi-core platforms have significantly degraded the predictability of real-time systems. Traditional deterministic approaches based on the worst-case assumptions become extremely pessimistic and thus unpractical. In this article, we address the problem of scheduling a set of fixed-priority periodic real-time tasks on multi-core platforms in a probabilistic manner. Specifically, we consider task execution time as a probabilistic distribution and study how to schedule these tasks on multi-core platforms with guaranteed Quality of Service (QoS) requirements in terms of deadline-missing probabilities. Moreover, it is a well-known fact that the relationship among task periods, if exploited appropriately, can significantly improve the processor utilization. To this end, we present a novel approach to partition real-time tasks that can take both task execution time distributions and their period relationships into consideration. From our extensive experiment results, our proposed methods can greatly improve the schedulability of real-time tasks when compared with existing approaches.

Cloud data centers are widely employed to offer reliable cloud services. However, low resource utilization and high power consumption have been great challenges for cloud providers. Moreover, the rapid increase in demand for affordable cloud services magnifies the obstacles for proficient resource management policies. In this paper, we investigate how to improve resource utilization and power consumption in cloud data centers when delivering services with statistically guaranteed Quality of Service (QoS). We assume that the service provider hosts different types of services, each of which has request classes with different QoS requirements. Different from the traditional approaches that distribute workloads with different QoS levels on different Virtual Machines (VMs), we introduce an approach to pack requests of the same service type, even with different QoS requirements, into the same VM, and to remove potential failure requests in time to improve resource usage and energy cost. We formally prove that our algorithm can statistically guarantee QoS conditions in terms of deadline miss ratios. We develop a cloud prototype to empirically validate our proposed methods and algorithm. Our experimental results demonstrate that our approach can significantly outperform other traditional approaches in terms of QoS guarantees, power consumption, resource demand and electricity cost.

Mobile edge computing (a.k.a. fog computing) has recently emerged to enable in-situ processing of delay-sensitive applications at the edge of mobile networks. Providing grid power supply in support of mobile edge computing, however, is costly and even infeasible (in certain rugged or under-developed areas), thus mandating on-site renewable energy as a major or even sole power supply in increasingly many scenarios. Nonetheless, the high intermittency and unpredictability of renewable energy make it very challenging to deliver a high quality of service to users in renewable-powered mobile edge computing systems. In this paper, we address the challenge of incorporating renewables into mobile edge computing and propose an efficient reinforcement learning-based resource management algorithm, which learns on-the-fly the optimal policy of dynamic workload offloading (to centralized cloud) and edge server provisioning to minimize the long-term system cost (including both service delay and operational cost). Our online learning algorithm uses a decomposition of the (offline) value iteration and (online) reinforcement learning, thus achieving a significant improvement of learning rate and run- time performance when compared to standard reinforcement learning algorithms such as Q- learning.

Power oversubscription in data centers may occasionally trigger an emergency when the aggregate power demand exceeds the capacity. Handling such an emergency requires a graceful power capping solution that minimizes the performance loss. In this paper, we study power capping in a multi-tenant data center where the operator supplies power to multiple tenants that manage their own servers. Unlike owner-operated data centers, the operator lacks control over tenants' servers. To address this challenge, we propose a novel market mechanism based on supply function bidding, called COOP, to financially incentivize and coordinate tenants' power reduction for minimizing total performance loss (quantified in performance cost) while satisfying multiple power capping constraints. We build a prototype to show that COOP is efficient in terms of minimizing the total performance cost, even compared to the ideal but infeasible case that assumes the operator has full control over tenants' servers. We also demonstrate that COOP is "win-win", increasing the operator's profit (through oversubscription) and reducing tenants' cost (through financial compensation for their power reduction during emergencies).

Even though demand response of datacenters recently has received increasing attention due to huge demands and flexible power control knobs, most of current studies focus on the owner-operated datacenters, leaving behind another critical segment of datacenter business: multi-tenant colocation. In colocation datacenters, while there exist multiple tenants who manage their own servers, the colocation operator only provides other facilities such as cooling, reliable power, and network connectivity. Therefore, colocation has its unique feature that challenges any attempts to design its demand response program: uncoordinated power management among tenants. To tackle this challenge, we consider incentive mechanisms that can coordinate tenants' power consumption for emergency demand response, where a fixed energy reduction target must be fulfilled. For two types of price-taking and price-anticipating tenants, we propose two incentive schemes with distributed algorithms that can achieve the same optimal social cost. Finally, trace-based simulations are also provided to illustrate the efficacy of our proposed incentive schemes.

While multi-core architectures, by exploring the thread/process level parallelism, help to lower down the power/thermal barrier for single core architectures, power/thermal issues are still the primary limiting factors to achieve high computing performance. In this paper, we study the problem of how to maximize the computing performance of multi-core platforms without violating their peak temperature constraint. As different cores may exhibit different thermal behaviors, we propose to run each core with different working frequencies and develop a schedule based on two novel concepts, i.e. the step-up schedule and the m-Oscillating schedule, for multi-core platforms. We formally prove that the proposed schedule can guarantee the peak temperature constraint for a given multi-core platform. Compared with the traditional exhaustive search-based approach, our approach can reduce the computation time by orders of magnitude and improve the throughput up to 89%, with an average improvement of 11%.

Data centers are promising participants in emergency demand response (EDR) programs, in which the power grids incentivize large energy consumers to reduce energy consumption in emergency to avoid potential huge financial losses. However, in multi-tenant colocation data centers, tenants manage their own servers and often sign fixed energy contracts with data center operators, thus having no incentives to contribute to EDR. To solve this problem, several studies have investigated various market-based mechanisms to incentivize tenants to reduce their server energy consumption for EDR. Nonetheless, these purely market-based studies are severely limited in one or both of the following key aspects. (1) Lack of coordination of cooling system: Due to thermal unawareness, the existing mechanisms leave the supplied cooling air temperature at an unnecessarily low level to avoid server overheating, resulting in cooling energy inefficiency (2) Violation of cost efficiency: The mechanism must be implemented in a cost efficient way such that operators do not lose financial interest, which, however, is violated by many of the existing mechanisms. This work proposes a novel thermal-aware and cost efficient mechanism, called TECH, which coordinate tenants' energy reduction in concert with the cooling system control to enable colocation EDR in a cost efficient way.

In this paper, the problem of resource allocation in cloud datacenters, that own highly complex and heterogeneous tasks and servers, is considered. To address this problem, a novel framework, dubbed joint operation cost and network traffic cost (JOT) framework, is proposed. This framework combines notions from Gibbs sampling and matching theory to find an efficient solution addressing the NP-hard problem JOT. The proposed model is shown to be capable of controlling the active server set, in a coordinated manner while allocating VMs in order to reduce both operation cost and network traffic cost of the cloud datacenter. We also conduct a case-study to validate our proposed algorithm and the results show that JOT can reduce the total incurred cost by up to 19% compared to the existing non-coordinated approach.

Data centers with high yet elastic energy demand are ideal candidates for participation in demand response programs. This paper studies emergency demand response (EDR) at multi-tenant colocation data centers (colocations). While the colocation has no direct control over tenants' servers, we design online mechanisms to incentivize and coordinate tenants' energy reduction. Our mechanism is online in nature, aiming to maximize not only social welfare but also tenant utility. Our main proposal is a truthful incentive auction that provides tenants with monetary remuneration for EDR energy reduction, minimizing social cost, which combines seamlessly with an online primal-dual framework for each tenant to schedule their delay-tolerant workloads. The online optimization at each tenant targets its utility maximization, concurrently reporting valuation functions for the tenant to participate in the auction. Our online algorithms achieve long-term performance guarantees in both tenants' utility and social welfare maximization, while fulfilling the EDR requirement with minimal diesel generation. We validate the efficiency of our algorithms through both the theoretical analysis and real-world trace-driven simulations.

Even though demand response of data centers has attracted many studies, there are very limited attempts on an important segment: colocation datacenters. Unlike large-scale (Google-type) datacenters, the colocation operator lacks control over its tenant servers, which entails a special interest in a design of incentive mechanisms, such that the operator can coordinate tenants to reduce the power usage for demand response. However, most previous studies ignore the role of the demand response provider (DRP), who uses pricing signals as a guide for customer response and as a compensation for their cutting electricity usage. To address this oversight, we propose an incentive mechanism Reward-to-Reduce for colocation's economic demand response, which shows an interaction between the DRP compensation to the colocation operator, and the colocation operator reward to tenants. Observing that this interaction contains strategic behaviors, we first formulate a two-stage Stackelberg game, where we show a unique competitive equilibrium of the operator strategy in the second stage, and a nonconvex problem of finding the optimal DRP compensation price in the first stage. We next analyze the second-stage equilibrium using an exact analysis and design an algorithm that can efficiently search the first-stage optimal DRP price with a reduced search space. Since the exact analysis can be impractical due to required tenants' private information, we also propose an approximate approach with limited tenant information. Extensive case studies show that the approximate approach can have the same performance as the exact analysis in a wide array of case studies and the optimal DRP price can be determined effectively, with which the corresponding DRP individual cost is compared with the social cost.

Multicore platforms are becoming the primary choice to achieve high performance in today's embedded system design. However, under the current IC technology, the dramatic increase in power density has made the thermal issue a critical concern in design of multicore systems. In this paper, we study the problem on how to determine if a periodic dynamic voltage and frequency scaling (DVFS) schedule for a multicore platform is thermally feasible in satisfying a given peak temperature constraint. To solve this problem, we first develop a novel analytic method to quickly calculate the temperature at an arbitrary time instant, which can achieve orders-of-magnitude speedups over the HotSpot simulator. We then present an approach to pinpoint the peak temperature of a given periodic multicore DVFS schedule. Finally, we develop three methods to check the thermal feasibility of an arbitrary schedule. We formally prove the fundamental principles and validity of our proposed methods and use simulation results to demonstrate their effectiveness.

The growing environmental and sustainability concerns have made energy efficiency a pressing issue for data center operation. Governments, as well as various organizations, are urging data centers to cap the increasing energy consumption. Naturally, achieving long term energy capping involves deciding energy usage over a long timescale (without accurately foreseeing the far future) and hence, we call this process “energy budgeting”. In this paper, we introduce an online resource management solution, called eBud (energy Budgeting), for a virtualized data center. eBud determines the number of servers, resource allocation to virtual machines and corresponding workload distribution to minimize data center operational cost while satisfying a long term energy cap. We prove that eBud achieves a close-to-minimum cost compared to the optimal offline algorithm with future information, while bounding the potential violation of energy budget constraint, in an almost arbitrarily random environment. We also perform a trace-based simulation study to complement the performance analysis. The simulation results show that eBud reduces the cost by more than$\mathrm{16}$percent (compared to state-of-the-art prediction-based algorithm) while resulting in a zero energy budget deficit. We also perform an experimental study based on RUBiS, demonstrating that in a real life scenario, eBud can achieve energy capping with a negligible increase in operational cost.

Power-hungry data centers face an urgent pressure on reducing the energy cost. The existing efforts, despite being numerous, have primarily centered around owner-operated data centers (e.g., Google), leaving another critical data center segment - colocation data center (e.g., Equinix) which rents out physical space to multiple tenants for housing their own servers - much less explored. Colocations have a major barrier to achieve cost efficiency: server power management by individual tenants is uncoordinated. This paper proposes RECO (REward for COst reduction), which shifts tenants' power management from uncoordinated to coordinated, using financial reward as a lever. RECO pays (voluntarily participating) tenants for energy reduction such that the colocation operator's overall cost is minimized. RECO incorporates the time-varying operation environment (e.g., cooling efficiency, intermittent renewables), addresses the peak power demand charge, and also proactively learns tenants' unknown responses to the offered reward. RECO includes a new feedback-based online algorithm to optimize the reward without far future offline information. We evaluate RECO using both scaled-down prototype experiments and simulations. Our results show that RECO is "win-win" and can successfully reduce the colocation operator's overall cost, by up to 27% compared to the no-incentive baseline case. Further, tenants receive financial rewards (up to 15% of their colocation costs) for "free" without violating Service Level Agreements.

Demand response programs maintain transmission stability in power grid through reducing electricity use during peak period, making grid more efficient and robust. While numerous demand response programs are currently being deployed by utility companies, we focus on emergency demand response program, which is critical to ensure reliability during emergency situations. As a key participant in such program, we consider a critical type of data center: multi-tenant colocation data center (or colocation), where multiple tenants mange their own servers in shared space but typically lack incentives to reduce energy for demand response. To enable multi-tenant data center demand response, we propose a contract-based mechanism, called Contract-DR, which offers financial incentives to tenants to shed energy during emergency situations, reducing the usage of cost-ineffective and environmentally-unfriendly diesel generation. We conduct theoretical analysis to prove the optimality of Contract-DR and also validate it through a trace-based study.

The increased resource sharing on multi-core platforms has posed significant challenges on the predictability of real-time systems. Cache memory partitioning has proven to be one of the most effective methods to improve the predictability and also the schedulability of real-time systems. In this paper, we study how to allocate cache memory of a multi-core platform when scheduling fixed-priority hard real-time tasks. As the bounded worst-case execution time (WCET) of a real-time task varies with its cache allocation, the challenges of this problem are twofold: how to judiciously allocate the cache memory among all real-time tasks and how to map real-time tasks to each core to improve the schedulability. To address these challenges, we develop an approach that takes into consideration not only the WCET variations with cache allocations but also the task period relationship and thus can significantly improve the schedulability of real-time tasks. Our simulation results, based on the SPEC CPU2000 benchmarks suite, show that our approach can increase the schedulability of real-time tasks up to four times when compared to other similar scheduling mechanisms.

Data centers are key participants in demand response programs, including emergency demand response (EDR), where the grid coordinates large electricity consumers for demand reduction in emergency situations to prevent major economic losses. While existing literature concentrates on owner-operated data centers, this work studies EDR in multi-tenant colocation data centers where servers are owned and managed by individual tenants. EDR in colocation data centers is significantly more challenging, due to lack of incentives to reduce energy consumption by tenants who control their servers and are typically on fixed power contracts with the colocation operator. Consequently, to achieve demand reduction goals set by the EDR program, the operator has to rely on the highly expensive and/or environmentally-unfriendly on-site energy backup/generation. To reduce cost and environmental impact, an efficient incentive mechanism is therefore in need, motivating tenants' voluntary energy reduction in case of EDR. This work proposes a novel incentive mechanism, Truth-DR, which leverages a reverse auction to provide monetary remuneration to tenants according to their agreed energy reduction. Truth-DR is computationally efficient, truthful, and achieves 2-approximation in colocation-wide social cost. Trace-driven simulations verify the efficacy of the proposed auction mechanism.

Reducing servers' power usage in data centers upon utility's request has been emerging as a valuable demand response resource for enhancing power grid's efficiency and reliability, especially during emergency events (e.g., extreme weather) that result in electricity production shortage and put the grid in jeopardy. Nonetheless, for demand response in multi-tenant colocation data centers, operators may have to leverage expensive and environmentally-unfriendly diesel generation, because individual tenants manage their own servers' power usage without coordination and are typically charged by data center operators based on fixed power contracts that provide no incentives for demand response. This paper focuses on emergency demand response (EDR) and proposes an auction-based incentive mechanism, called FairDR, that incentivizes and coordinates tenants' energy reduction through financial rewards for enabling cost-effective and low-carbon EDR in colocation data center. FairDR decides tenants' energy reduction online without knowing a priori the future energy reduction requirements. It is proved that FairDR ensures tenants' truthfulness in the auction process, attains a bounded overall cost saving compared to the offline optimum which knows all the demands, and guarantees fairness (i.e., similar rewards are offered if tenants reduce the same amount of energy) that is largely absent in the existing auction mechanisms. Finally, trace-driven simulations are performed to validate our analysis and demonstrate that FairDR outperforms the existing mechanisms by improving fairness and achieving a good cost saving that is comparable to the offline optimum.

Autoscaling has become an integral feature of cloud computing services, allowing users to dynamically scale the cloud resources on demand for both performance and cost. Moreover, recent survey shows the importance of satisfying long-term budget constraints (e.g., monthly or yearly) for cloud users. However, meeting such constraints while optimizing delay performance is challenging: it requires the knowledge of complete offline information such as workload demand over the entire budgeting period, which is difficult to predict accurately. This paper proposes a new autoscaling system, BATS, which optimizes delay performance while meeting long-term budget constraints using only past and instantaneous workload information. Analytically, we prove that, for arbitrary workload arrival, the autoscaling algorithm of BATS achieves close-to-optimal performance even compared to the optimal solution that has complete offline information. Empirically, we build BATS autoscaler as a user-friendly service for running applications on Windows Azure. The experimental results show that BATS achieves both lower cost and less delay compared with the state-of-art threshold-based autoscaling solutions. We also run simulation studies to complement the implementation results, demonstrating the effectiveness, scalability and robustness of BATS for reducing both average and tail latency under various workload scenarios.

A web search engine often employs partition-aggregate architecture, where an aggregator propagates a user query to all index serving nodes (ISNs) and collects the responses from them. An aggregation policy determines how long the aggregators wait for the ISNs before returning aggregated results to users, crucially affecting both query latency and quality. Designing an aggregation policy is, however, challenging: Response latency among queries and among ISNs varies significantly, and aggregators lack of knowledge about when ISNs will respond. In this paper, we propose aggregation policies that minimize tail latency of search queries subject to search quality service level agreements (SLAs), combining data-driven offline analysis with online processing. Beginning with a single aggregator, we formally prove the optimality of our policy: It achieves the offline optimal result without knowing future responses of ISNs. We extend our policy for commonly-used hierarchical levels of aggregators and prove its optimality when messaging times between aggregators are known. We also present an empirically-effective policy to address unknown messaging time. We use production traces from a commercial search engine, a commercial advertisement engine, and synthetic workloads to evaluate the aggregation policy. The results show that compared to prior work, the policy reduces tail latency by up to 40% while satisfying same quality SLAs.

This work studies the online electricity cost minimization problem at a co-location data center. A co-location data center serves multiple tenants who rent the physical infrastructure within the data center to run their respective cloud computing services. Consequently, the co-location operator has no direct control over power consumption of its tenants, and an efficient mechanism is desired for eliciting desirable consumption patterns from the co-location tenants. Electricity billing faced by a data center is nowadays based on both the total volume consumed and the peak consumption rate. This leads to an interesting new combinatorial optimization structure on the electricity cost optimization problem, which also exhibits an online nature due to the definition of peak consumption. We model and solve the problem through two approaches: the pricing approach and the auction approach. For the former, we design an offline 2-approximation algorithm as well as an online algorithm with a small competitive ratio in most practical settings. For the latter, we design an efficient (2+c)-competitive online algorithm, where c is a system dependent parameter close to 1.49, and then convert it into an efficient mechanism that executes in an online fashion, runs in polynomial time, and guarantees truthful bidding and (2+2c)-competitive in social cost.

Demand response programs have been considered critical for power grid reliability and efficiency. Especially, the demand response of datacenters has recently received encouraging efforts due to huge demands and flexible power control knobs of datacenters. However, most current efforts focus on owner-operated datacenters, omitting another critical segment of datacenter business: multitenant colocation. In colocation datacenters, while there exist multiple tenants who manage their own servers, the colocation operator only provides facilities such as cooling, reliable power, and network connectivity. Therefore, colocation has a unique feature that challenges any attempts to design a demand response program: uncoordinated power management among tenants. To tackle this challenge, two incentive mechanisms are proposed to coordinate tenant power consumption for demand response under two different scenarios. First, in the case of economic demand response where the operator can adjust an elastic energy reduction target, we show that there is an interaction between the operator and tenant strategies, where each side maximizes its own benefit. Hence, we apply a two-stage Stackelberg game to analyze this scenario and derive this game's equilibria. However, computing these equilibria can be intractable with exhaustive search; therefore, we propose an algorithm to find the Stackelberg equilibria with linear complexity. Second, in the case of emergency demand response where a fixed energy reduction target must be fulfilled, we devise two incentive schemes with the distributed algorithms that can achieve the same optimal social cost. While the first algorithm is based on the dual-decomposition method that is suitable for nonstrategic tenants, the second one is designed for strategic tenants to achieve a unique Nash equilibrium of a bidding game. Finally, trace-based simulations are also provided to illustrate the efficacy of our proposed incentive schemes.

In the dynamic spectrum access (DSA), pricing is an efficient approach providing economic incentives for operators, whereas load balancing yields congestion-avoidance incentives for secondary users (SUs). Despite complexities of 1) the couplings among pricing, load balancing, and SUs' spectrum access decision, and 2) the heterogeneity of primary users' traffic and SUs classes/types, we tackle the joint load balancing and pricing problem to maximize operators' revenue in two cognitive radio markets: monopoly and duopoly. For the monopoly market, we first show there exists a unique SUs' equilibrium arrival rate to the monopolist's channels. We then show that the joint problem can be solved efficiently by exploiting its convex structure. For the duopoly market, we first characterize a unique SUs' equilibrium arrival rate to two operators employing different DSA approaches. When two operators are noncooperative, we show that there exists a unique Nash equilibrium for each operator's revenue. When they are cooperative, we show that the social revenue optimization can achieve a unique optimal solution. Using the Nash bargaining framework, we also present a sharing contract that determines the optimal fraction of the social revenue for each operator. In both markets, we propose two algorithms that can find the largest SU class supportable by the operators.

This work studies the online electricity cost minimization problem at a co-location data center, which serves multiple tenants who rent the physical infrastructure within the data center to run their respective cloud computing services. The co-location operator has no direct control over power consumption of its tenants, and an efficient mechanism is desired for eliciting desirable consumption patterns from the tenants. Electricity billing faced by a data center is nowadays based on both the total volume consumed and the peak consumption rate. This leads to an interesting new combinatorial optimization structure on the electricity cost optimization problem, which also exhibits an online nature due to the definition of peak consumption. We model and solve the problem through two approaches: the pricing approach and the auction approach, and design online algorithms with small competitive ratios.

The huge demand for data center computing nowadays has resulted in a significant amount of electricity consumption as well as environmental impacts. While current works mainly focus on the energy cost of data centers, the severity of water consumption problem in data centers is largely neglected. In this paper, we propose an optimization framework for the workload management of data centers, which takes the efficiency of water usage into account. The workload management is formulated as a revenue maximization problem. To solve the large-scale optimization problem with scalability, the alternating direction method of multipliers (ADMM) is utilized. The optimization problem is decomposed into independent subproblems, which can be solved in a parallel fashion on distributed computing units and coordinated through dual variables. We evaluate the performance of proposed algorithm by simulations, and numerical results validate the effectiveness of the proposed algorithm.

The power consumption of enormous network devices in data centers has emerged as a big concern to data center operators. Despite many traffic-engineering-based solutions, very little attention has been paid on performance-guaranteed energy saving schemes. In this paper, we propose a novel energy-saving model for data center networks by scheduling and routing "deadline-constrained flows" where the transmission of every flow has to be accomplished before a rigorous deadline, being the most critical requirement in production data center networks. Based on speed scaling and power-down energy saving strategies for network devices, we aim to explore the most energy efficient way of scheduling and routing flows on the network, as well as determining the transmission speed for every flow. We consider two general versions of the problem. For the version of only flow scheduling where routes of flows are pre-given, we show that it can be solved polynomially and we develop an optimal combinatorial algorithm for it. For the version of joint flow scheduling and routing, we prove that it is strongly NP-hard and cannot have a Fully Polynomial-Time Approximation Scheme (FPTAS) unless P=NP. Based on a relaxation and randomized rounding technique, we provide an efficient approximation algorithm which can guarantee a provable performance ratio with respect to a polynomial of the total number of flows.

Web applications grow tremendously in both scale and scope, the application patterns turn to be more and more sophisticated. It is important but challenging for service providers to lower the operational costs without degrading user experiences, especially in the case where a service provider's profit is closely related to the user experience (e.g. response time.) In this paper, we study the problem of efficiently scheduling multi-tier time sensitive applications on distributed computing platforms with respect to the user's Quality of Service (QoS) requirements. The efficiency refers to the QoS satisfaction with low average response times. The service provider must ensures that service requests be served successfully before end-to-end deadlines with certain probabilities. To solve this problem, we propose an approach to judiciously assign a deadline for each service tier. An application request is dropped if any one of its services misses its deadline. Our simulation results demonstrate that our approach can statistically guarantee the required QoS more efficiently than the other widely applied methods (e.g. acceptance control, first-come-first-serve, deterministic sub deadline assignment, etc.) irrespective of whether the resources are shared or not by multiple different applications.

No abstract available.

Decreasing the soaring energy cost is imperative in large data centers. Meanwhile, limited computational resources need to be fairly allocated among different organizations. Latency is another major concern for resource management. Nevertheless, energy cost, resource allocation fairness, and latency are important but often contradicting metrics on scheduling data center workloads. Moreover, with the ever-increasing power density, data center operation must be judiciously optimized to prevent server overheating. In this paper, we explore the benefit of electricity price variations across time and locations. We study the problem of scheduling batch jobs to multiple geographically-distributed data centers. We propose a provably-efficient online scheduling algorithm - GreFar - which optimizes the energy cost and fairness among different organizations subject to queueing delay constraints, while satisfying the maximum server inlet temperature constraints. GreFar does not require any statistical information of workload arrivals or electricity prices. We prove that it can minimize the cost arbitrarily close to that of the optimal offline algorithm with future information. Moreover, we compare the performance of GreFar with ones of a similar algorithm, referred to as T-unaware, that is not able to consider the server inlet temperature in the scheduling process. We prove that GreFar is able to save up to 16 percent of energy-fairness cost with respect to T-unaware.

In this paper, we consider a wireless cloud computing system in which the service provider operates a data center and provides cloud services to its subscribers at dynamic prices. We propose a joint optimization of scheduling and pricing decisions for delay-tolerant batch services to maximize the service provider's long-term profit. Unlike the existing research on jointly scheduling and pricing that focuses on static or asymptotic analysis, we focus on a dynamic setting and develop a provably-efficient Dynamic Scheduling and Pricing (Dyn-SP) algorithm which, without the necessity of predicting the future information, can be applied to an arbitrarily random environment that may follow an arbitrary trajectory overtime. We prove that, compared to the optimal offline algorithm with future information, Dyn-SP produces a close-to-optimal average profit while bounding the job queue length in the data center. We perform a trace-based simulation study to validate Dyn-SP. In particular, we show both analytically and numerically that a desired tradeoff between the profit and queueing delay can be obtained by appropriately tuning the control parameter. Our results also indicate that, compared to the existing algorithms which neglect demand-side management, cooling system energy consumption, and/or the queue length information, Dyn-SP achieves a higher average profit while incurring (almost) the same average queueing delay.

In this paper, we propose an efficient solution for supporting real-time stream mining applications on heterogeneous systems operating at various processing speeds. Unlike the existing solutions that (1) rely on accurate knowledge or prediction of the service demand of each individual service request and (2) only consider a single type of delay constraint (e.g., typically, average or maximum delay), we propose an optimal algorithm, MinEnergy-MD, which determines the processing speeds for all classifiers based on the probability distribution of the service demand to minimize the average energy consumption while simultaneously satisfying multiple delay constraints. We conduct an extensive study to quantify the performance of MinEnergy-MD.

In light of the growing trend of data center carbon emission that has raised serious sustainability concerns, data center operators are aggressively seeking ways to minimize the overall energy consumption by using more on-site renewable energy and ultimately achieving carbon neutrality (or "net"). In this paper, we propose a dynamic server provisioning algorithm, called SPAN (Server Provisioning for carbon Neutrality), to control the number of active servers for minimizing the data center operational cost (defined as a weighted sum of electricity cost and delay cost) while achieving carbon neutrality without requiring long-term future information. Leveraging the recently-developed Lyapunov optimization technique, it is rigorously proved that SPAN achieves a close-to-minimum operational cost compared to the optimal offline algorithm with future information, while bounding the potential violation of carbon neutrality. The simulation result is also consistent with our analysis, showing that SPAN can reduce the average operational cost by 20% while maintaining a carbon neutral data center.

Electric vehicles (EVs) will play an important role in the future smart grid because of their capabilities of storing electrical energy in their batteries during off-peak hours and supplying the stored energy to the power grid during peak hours. In this paper, we consider a power system with an aggregator and multiple customers with EVs and propose a novel electricity load scheduling which, unlike previous works, jointly considers the load scheduling for appliances and the energy trading using EVs. Specifically, we allow customers to determine how much energy to purchase from or to sell to the aggregator while taking into consideration the load demands of their residential appliances and the associated electricity bill. Under the assumption of the collaborative system where the customers agree to maximize the social welfare of the power system, we develop an optimal distributed load scheduling algorithm that maximizes the social welfare. Through numerical results, we show when the energy trading leads to an increase in the social welfare in various usage scenarios.

Future generation smart grids will allow customers to trade energy bidirectionally. Specifically, each customer will be able to not only buy energy from the aggregator during its peak hours but also sell its surplus energy during its off-peak hours. In these emerging energy trading markets, a key component will be the deployment of effective energy billing schemes which consider the customers residential load scheduling. In this paper, we consider a residential load scheduling problem with bidirectional energy trading. Compared with the previous work, in which customers are assumed to be obedient and agree to maximize the social welfare of the smart grid system, in this paper, we consider a non-collaborative approach, where consumers are self-interested. We model the energy scheduling problem as a non-cooperative game, where each customer determines its load scheduling and energy trading to maximize its own profit. In order to resolve the unfairness between heavy and light customers, we propose a novel tiered billing scheme that can control the electricity rates for customers according to their different energy consumption levels. We also propose a distributed energy scheduling algorithm that converges to the unique Nash equilibrium of the studied non-cooperative game. Through the numerical results, we study the impact of the proposed tiered billing scheme on the selfish customers' behavior and on their incentives to participate in the energy trading market.

In this paper, we consider a wireless cloud computing system in which a profit-maximizing wireless service provider provides cloud computing services to its subscribers. In particular, we focus on batch services, which, due to their non-urgent nature, allow more scheduling flexibility than their interactive counterparts. Unlike the existing research that studied separately demand-side management and energy cost saving techniques (both of which are critical to profit maximization), we propose a provably-efficient Dynamic Scheduling and Pricing (Dyn-SP) algorithm which proactively adapts the service demand to workload scheduling in the data center and opportunistically utilizes low electricity prices to process batch jobs for energy cost saving. Without the necessity of predicting future information as assumed by some prior works, Dyn-SP can be applied to an arbitrarily random environment in which the electricity price, available renewable energy supply, and wireless network capacities may evolve over time as arbitrary stochastic processes. It is proved that, compared to the optimal offline algorithm with future information, Dyn-SP can produce a close-to-optimal longterm profit while bounding the job queue length in the data center. We also show both analytically and numerically that a desired tradeoff between the profit and queueing delay can be obtained by appropriately tuning the control parameter. Finally, we perform a simulation study to demonstrate the effectiveness of Dyn-SP.

The advent of cloud systems has spurred the emergence of an impressive assortment of Internet services. Recent pressures on enhancing the profitability by curtailing surging dollar costs on energy have posed challenges to, as well as placed a new emphasis on, designing energy-efficient request dispatching and resource management algorithms. What further adds to the design challenge is the highly diverse nature of Internet service requests in terms of Quality-of-Service (QoS) constraints and business values. Nonetheless, most of the existing job scheduling and resource management solutions are for a single type of request and are profit oblivious. They are unable to reap the benefit of multi-service profit-aware algorithm designs. In this paper, we consider a cloud service provider operating geographically distributed data centers in a multi-electricity-market environment, and propose an energy-efficient, profit-and cost-aware request dispatching and resource allocation algorithm to maximize a service provider's net profit. We formulate the net profit maximization issue as a constrained optimization problem, using a unified task model capturing multiple cloud layers (e.g., SaaS, PaaS, IaaS.) The proposed approach maximizes a service provider's net profit by judiciously distributing service requests to data centers, powering on/off an appropriate number of servers, and allocating server resources to dispatched requests. We conduct extensive experiments to validate our proposed algorithm. Results show that our proposed approach can improve a service provider's net profit significantly.

Increasingly serious concerns about the IT carbon footprints have been pushing data center operators to cap their (brown) consumption. Naturally, achieving capping involves deciding the usage over a long timescale (without foreseeing the far future) and hence, we call this process energy budgeting. The specific goal of this paper is to study budgeting for virtualized data centers from an algorithmic perspective: we develop a provably-efficient online algorithm, called eBud (energy Budgeting), which determines server CPU speed and resource allocation to virtual machines for minimizing the data center operational cost while satisfying the long-term capping constraint in an online fashion. We rigorously prove that eBud achieves a close-to-minimum cost compared to the optimal offline algorithm with future information, while bounding the potential violation of budget constraint, in an almost arbitrarily random environment. We also perform a trace-based simulation study to complement the analysis. The simulation results are consistent with our theoretical analysis and show that eBud reduces the cost by more than 60% (compared to state-of-the-art prediction-based algorithm) while resulting in a zero budget deficit.

Due to the enormous energy consumption and associated environmental concerns, data centers have been increasingly pressured to reduce long-term net carbon footprint to zero, i.e., carbon neutrality. In this paper, we propose an online algorithm, called COCA (optimizing for COst minimization and CArbon neutrality), for minimizing data center operational cost while satisfying carbon neutrality without long-term future information. Unlike the existing research, COCA enables distributed server-level resource management: each server autonomously adjusts its processing speed and optimally decides the amount of workloads to process. We prove that COCA achieves a close-to-minimum operational cost (incorporating both electricity and delay costs) compared to the optimal algorithm with future information, while bounding the potential violation of carbon neutrality. We also perform trace-based simulation studies to complement the analysis, and the results show that COCA reduces cost by more than 25% (compared to state of the art) while resulting in a smaller carbon footprint.

Electric vehicles (EVs) will play an important role in the future smart grid because of their capabilities of storing electrical energy in their batteries during off-peak hours and supplying the stored energy to the power grid during peak hours. In this paper, we consider a power system with an aggregator and multiple customers with EVs and propose novel electricity load scheduling algorithms which, unlike previous works, jointly consider the load scheduling for appliances and the energy trading using EVs. Specifically, we allow customers to determine how much energy to purchase from or to sell to the aggregator while taking into consideration the load demands of their residential appliances and the associated electricity bill. We propose two different approaches: a collaborative and a non-collaborative approach. In the collaborative approach, we develop an optimal distributed load scheduling algorithm that maximizes the social welfare of the power system. In the non-collaborative approach, we model the energy scheduling problem as a non-cooperative game among self-interested customers, where each customer determines its own load scheduling and energy trading to maximize its own profit. In order to resolve the unfairness between heavy and light customers in the non-collaborative approach, we propose a tiered billing scheme that can control the electricity rates for customers according to their different energy consumption levels. In both approaches, we also consider the uncertainty in the load demands, with which customers' actual energy consumption may vary from the scheduled energy consumption. To study the impact of the uncertainty, we use the worst-case-uncertainty approach and develop distributed load scheduling algorithms that provide the guaranteed minimum performances in uncertain environments. Subsequently, we show when energy trading leads to an increase in the social welfare and we determine what are the customers' incentives to participate in the energy trading in various usage scenarios including practical environments with uncertain load demands.

Real-time stream mining such as surveillance and personal health monitoring, which involves sophisticated mathematical operations, is computation-intensive and prohibitive for mobile devices due to the hardware/computation constraints. To satisfy the growing demand for stream mining in mobile networks, we propose to employ a cloud-based stream mining system in which the mobile devices send via wireless links unclassified media streams to the cloud for classification. We aim at minimizing the classification-energy cost, defined as an affine combination of classification cost and energy consumption at the cloud, subject to an average stream mining delay constraint (which is important in real-time applications). To address the challenge of time-varying wireless channel conditions without a priori information about the channel statistics, we develop an online algorithm in which the cloud operator can dynamically adjust its resource provisioning on the fly and the mobile devices can adapt their transmission rates to the instantaneous channel conditions. It is proved that, at the expense of increasing the average stream mining delay, the online algorithm achieves a classification-energy cost that can be pushed arbitrarily close to the minimum cost achieved by the optimal offline algorithm. Extensive simulations are conducted to validate the analysis.

Focusing on a femtocell communications market, we study the entrant network service provider's (NSP's) long-term decision: whether to enter the market and which spectrum sharing technology to select to maximize its profit. This long-term decision is closely related to the entrant's pricing strategy and the users' aggregate demand, which we model as medium-term and short-term decisions, respectively. We consider two markets, one with no incumbent and the other with one incumbent. For both markets, we show the existence and uniqueness of an equilibrium point in the user subscription dynamics and provide a sufficient condition for the convergence of the dynamics. For the market with no incumbent, we derive upper and lower bounds on the optimal price and market share that maximize the entrant's revenue, based on which the entrant selects an available technology to maximize its long-term profit. For the market with one incumbent, we model competition between the two NSPs as a noncooperative game, in which the incumbent and the entrant choose their market shares independently, and provide a sufficient condition that guarantees the existence of at least one pure Nash equilibrium. Finally, we formalize the problem of entry and spectrum-sharing scheme selection for the entrant and provide numerical results to complement our analysis.

Decreasing the soaring energy cost is imperative in large data centers. Meanwhile, limited computational resources need to be fairly allocated among different organizations. Latency is another major concern for resource management. Nevertheless, energy cost, resource allocation fairness, and latency are important but often contradicting metrics on scheduling data center workloads. In this paper, we explore the benefit of electricity price variations across time and locations. We study the problem of scheduling batch jobs, which originate from multiple organizations/users and are scheduled to multiple geographically-distributed data centers. We propose a provably-efficient online scheduling algorithm -- Gre Far -- which optimizes the energy cost and fairness among different organizations subject to queueing delay constraints. Gre Far does not require any statistical information of workload arrivals or electricity prices. We prove that it can minimize the cost (in terms of an affine combination of energy cost and weighted fairness) arbitrarily close to that of the optimal offline algorithm with future information. Moreover, by appropriately setting the control parameters, Gre Far achieves a desirable tradeoff among energy cost, fairness and latency.

In this paper, we consider a user-generated content platform monetized through advertising and managed by an intermediary. To maximize the intermediary's profit given the rational decision-making of content viewers and heterogeneous content producers, a payment scheme is proposed in which the intermediary can either tax or subsidize the content producers. First, we use a model with a representative content viewer to determine how the content viewers' attention is allocated across available content by solving a utility maximization problem. Then, by modeling the content producers as self-interested agents making independent production decisions, we show that there exists a unique equilibrium in the content production stage, and propose a best-response dynamics to model the decision-making process. Next, we study the intermediary's optimal payment based on decisions made by the representative content viewer and the content producers. In particular, by considering the well-known quality-adjusted Dixit-Stiglitz utility function for the representative content viewer, we derive explicitly the optimal payment maximizing the intermediary's profit and characterize analytical conditions under which the intermediary should tax or subsidize the content producers. Finally, we generalize the analysis by considering heterogeneity in terms of production costs among the content producers.

In this paper, we investigate the power allocation (PA) problem for two-way relay networks (TWRNs) with amplify-and-forward (AF) protocol. We propose a unified power allocation algorithm which can minimize average symbol error probability (SEP) and average outage probability while maximizing average sum rate in high signal to noise ratio (SNR) regions simultaneously. It is shown that the proposed algorithm has a closed-form solution which only depends on statistical channel knowledge. Simulation results show that the proposed scheme, although derived under the high SNR assumption, also works very well in low and medium SNR regions.

Online television (TV) market has been expanding rapidly over the last few years and provided TV studios with a cost-effective and reliable channel for the delivery of high-quality TV content. To maximize profit by setting up an online TV content platform, two major challenges are faced by the platform owner: what is the optimal investment (e.g., how many hosting servers, bandwidth acquisition) and how to price TV content producers who utilize the platform as a channel to distribute their content. To address these two challenges, we first derive the optimal pricing policy based on the widely-adopted “pay-per-usage” model, and then formalize and solve the optimal investment decision problem. Rationality of self-interested TV content producers and audiences is also taken into account. Specifically, we first use a model with a representative content viewer to determine how many times a TV content with a certain quality is watched. Then, by modeling the content providers as self-interested agents making independent production decisions, we show that for any price charged by the platform, there always exists a unique equilibrium in the content production stage, which makes it possible for the platform owner to maximize its profit without uncertainties because of the unique outcome in the content producers' decision stage. Finally, we develop an algorithm to derive the optimal price and then formalize the investment decision problem to maximize the platform's profit.

Existing network pricing solutions mainly focus on congestion-dependent pricing schemes, while ignoring the users' traffic state information, which we shall show in this paper can be exploited to significantly improve the service provider's revenue. In order to derive pricing strategies that explicitly take into account the users' traffic dynamics, we propose a systematic framework of traffic-dependent pricing by focusing on delay-sensitive multimedia networks. First, we introduce a finite-state Markov chain to capture the users' traffic dynamics, and a service demand model that is dependent on the users' traffic state information. Thus, we relate the users' traffic dynamics to the service provider's pricing policy, by means of the traffic-dependent demand model. Then, we formulate the service provider's pricing problem into a Markov decision process, and propose a low-complexity pricing algorithm, i.e., static pricing without considering the resource constraint, which can achieve a close-to-optimal performance. Next, by considering a practical scenario in which the service provider does not know the users' traffic dynamics a priori, we propose a learning-based algorithm that allows the service provider to identify an (locally) optimal pricing policy. Finally, we conduct simulations to quantify the proposed framework of traffic-dependent pricing.

In order to understand the complex interactions between different technologies in a communications market, it is of fundamental importance to understand how technologies affect the demand of users and competition between network service providers (NSPs). To this end, we analyze user subscription dynamics and revenue maximization in monopoly and duopoly communications markets. First, by considering a monopoly market with only one NSP, we investigate the impact of technologies on the users' dynamic subscription. It is shown that, for any price charged by the NSP, there exists a unique equilibrium point of the considered user subscription dynamics. We also provide a sufficient condition under which the user subscription dynamics converges to the equilibrium point starting from any initial point. We then derive upper and lower bounds on the optimal price and market share that maximize the NSP's revenue. Next, we turn to the analysis of a duopoly market and show that, for any charged prices, the equilibrium point of the considered user subscription dynamics exists and is unique. As in a monopoly market, we derive a sufficient condition on the technologies of the NSPs that ensures the user subscription dynamics to reach the equilibrium point. Then, we model the NSP competition using a non-cooperative game, in which the two NSPs choose their market shares independently, and provide a sufficient condition that guarantees the existence of at least one pure Nash equilibrium in the market competition game.

In order to understand the competition and interactions between different technologies, it is of fundamental importance to study how users select these technologies operated by different network service providers (NSPs) . In this paper, we study the dynamics of user subscription by users in a wireless communication market that includes a continuum of users. First, we focus on a monopoly market with only one NSP that provides to each user with an unreliable quality-of-service (QoS) subject to the number of subscribers. Users dynamically make their decisions regarding whether or not they subscribe to the NSP. It is shown that there exists a unique equilibrium point in the dynamics and that the dynamics is guaranteed to converge under some sufficient conditions that can be interpreted as that the provided QoS does not vary too rapidly with respect to the change of user subscriptions. Then, we extend the analysis to a duopoly market by adding into the market another NSP that has sufficient resources and thereby provides to each user a constant QoS.

In this paper, we consider a wireless amplify-and- forward relay network with one relay node and multiple source-destination pairs/users and propose a compensation framework such that the relay has incentives to forward the users' signals. Specifically, depending on the quality of the received signals, the relay sets the prices to maximize its revenue and correspondingly charges the users utilizing the relay for their transmissions. Given the specified price, the users competitively employ the relay node to forward their signals. We model each user as a strategic player, which aims at maximizing its own net utility through power allocation, and apply non-cooperative game theory to analyze the competition among the users. It is shown that, in the game played by the users, there always exists a unique Nash equilibrium point that can be achieved through distributed iterations. Then, subject to the availability of complete information about the users at the relay, we propose a low- complexity uniform pricing algorithm and an optimal differentiated pricing algorithm, in which the relay charges the users at a sub-optimal uniform price and at different prices, respectively.

In this paper, we propose a limited feedback scheme to improve outage performance for a wireless cooperative decode-and-forward network. Specifically, based on the instantaneous conditions of the source-destination and relay-destination channels, the destination will allocate the transmission time of the source and relay and feed back the allocation result to the source. Both limited and full (or infinite) rate feedback are considered. Under the practical assumption that only imperfect channel estimation is available at the receiver, we analyze the outage performance by deriving upper bounds on the outage probabilities. It will be demonstrated that, even with only one-bit feedback, the proposed feedback scheme can outperform the no feedback case. Furthermore, the outage performance can approach the optimality by exploiting limited (only a small number of bits) uniformly quantized feedback from the destination.

In this paper, we consider the amplify-and-forward relaying transmission in the downlink of a multi-channel cellular network with one base station and multiple relay-destination pairs. Spatial reuse of the relaying slot by allowing simultaneous transmissions from the relays is adopted to avoid the spectral loss incurred by the half-duplex relays. The relays are modeled as rational agents engaging in a non-cooperative game. In order to maximize its individual rate, each relay node iteratively allocates its power across different subchannels based on local information, while treating the signals from the other users as additive noise. First, we propose a distributed algorithm based on best response that is applicable in any signal to interference plus noise ratio (SINR) regions. Then, by focusing on the low SINR region, we propose a modified iterative water-filling algorithm. The existence of Nash equilibrium (NE) is guaranteed and the sufficient condition to reach a NE iteratively is determined. Next, we consider medium to high SINR regions and propose a distributed algorithm based on the sub-optimal response, which can be shown to reduce to the classic Gaussian interference channel model, for which analytical sufficient conditions for the convergence to the unique NE can be readily obtained. Finally, we extend the analysis to a general network topology wherein the users having different channel conditions coexist. The results show that, in low SINR regions, the proposed modified iterative water-filling algorithm yields a higher average sum rate than two simplified algorithms, i.e., the equal power allocation scheme and the conventional time-division based protocol, while in medium to high SINR regions, the sub-optimal-response based algorithm outperforms these two simplified algorithms in terms of the average sum rate

In this paper, we consider a wireless cooperative multimedia decode-and-forward network wherein one relay may assist multiple source-destination pairs. By exploiting the global channel state information at the relay, we propose a power allocation, a time allocation and an iterative joint power-time allocation algorithm to minimize the sum expected distortion. Firstly, we separately optimize the relay's transmission power and the system transmission time allocated to each source-destination pair such that the sum expected distortion can be minimized. Then, we propose an iterative joint power-time allocation algorithm subject to the relay's total power constraint to further improve the distortion performance. The proposed iterative algorithm is guaranteed to converge to an optimal, despite not necessarily globally optimal, point and can achieve the minimum sum expected distortion among all the schemes.

In this paper, we propose a resource allocation scheme to increase the effective capacity subject to the queue-overflow statistical Quality-of-Service (QoS) requirement for a multi-relay cooperative wireless network. Firstly, we consider the block fading channels and derive an algorithm in which each relay is allocated a time slot of optimal length during the cooperation phase, based on the channel statistics. Our analysis indicates that when the QoS requirement is loose, only the relay with the best average channel condition should be selected for cooperation. On the other hand, when the QoS requirement becomes more stringent, more relays should participate in cooperation. The asymptotic case when either the transmit power or the number of relays goes to infinity is discussed, and we shall reveal a tradeoff between the transmit power and the number of relays, given a target effective capacity. By modeling the channel correlation by a two-state Markov model, we will develop two sub-optimal time-slot allocation algorithms which can substantially increase the effective capacity compared with the opportunistic and equal allocation schemes. Our results will show that the channel correlation can sharply decrease the effective capacity and that applying the optimal time-slot allocation result obtained in block fading channels directly to correlated fading channels is no longer optimal.

In this paper, we propose a limited feedback scheme to minimize the outage probability for a wireless cooperative decode-and-forward network. Specifically, based on the instantaneous conditions of the source-destination and relay-destination channels, the destination will allocate the transmission time of the source and relay and feed back the allocation results to the source. Both full, or infinite-rate, feedback and limited feedback are considered. To simplify the expression of the outage probability in the full feedback case, a lower bound is proposed, based on which we find the sub-optimal location of the relay that can result in a close-to-optimal outage performance. Our results show that, even with only one-bit feedback, a significant improvement in terms of the outage probability can be achieved compared to the no feedback case. Furthermore, the outage performance can approach optimality by exploiting only two or three bits feedback from the destination.

In this paper, we propose a resource allocation scheme to maximize the system throughput subject to the queue overflow quality-of-service (QoS) requirement for wireless cooperative networks. Specifically, the considered network consists of one source-destination pair and N relays that can detect and forward the source's message. By integrating the concept of effective capacity with cooperative relay networks, the proposed scheme allocates each relay a time slot of optimal length during the cooperation phase, based on the channel statistics. Our analysis shows that selecting the relay with the best channel condition for cooperation is optimal when no QoS requirement is considered, while more relays should participate in cooperation when the level of QoS requirement becomes more stringent.