Search

We present a general framework for understanding system intelligence, i.e., the level of system smartness perceived by users, and propose a novel metric for measuring the intelligence levels of dynamical human-in-the-loop systems, defined to be the maximum average reward obtained by proactively serving user demands, subject to a resource constraint. Our metric captures two important elements of smartness, i.e., being able to know what users want and pre-serve them, and achieving good resource management while doing so. We provide an explicit characterization of the system intelligence, and show that it is jointly determined by user demand volume (opportunity to impress), demand correlation (user predictability), and system resource and action costs (flexibility to pre-serve). We then propose an online learning-aided control algorithm called learning-aided budget-limited intelligent system control ( \mathtt LBISC ), and show that \mathtt LBISC achieves an intelligence level that is within O\left(N(T)^-\frac 12+\epsilon \right) of the highest level, where N(T) represents the number of data samples collected within a learning period T and is proportional to the user population size, while guaranteeing an O\left(\max \left( N(T)^-\frac 12/\epsilon , \log (1/\epsilon )^2\right)\right) average resource deficit. Moreover, we show that \mathtt LBISC possesses an O(\max ( N(T)^-\frac 12/\epsilon , \log (1/\epsilon )^2)+T) convergence time, which is smaller compared with the $\Theta (1/\epsilon )$ time required for existing non-learning-based algorithms. Our analysis rigorously quantifies the impact of data and user population (captured by $N(T)$ ), learning (captured by our learning method), and control (captured by \mathtt LBISC ) on the achievable system intelligence, and provides novel insight and guideline into designing future smart systems. [ABSTRACT FROM PUBLISHER]

In this paper, we develop optimal sleep/wake scheduling algorithms for smart mobile devices that are powered by batteries and are capable of harvesting energy from the environment. Using a novel combination of the two-timescale Lyapunov optimization approach and weight perturbation, we first design the Optimal Sleep/wake scheduling Algorithm (OSA), which does not require any knowledge of the harvestable energy process. We prove that OSA is able to achieve any system performance that is within $O(\epsilon)$ of the optimal, and explicitly compute the required battery size, which is $O(1/\epsilon)$ . We then extend our results to incorporate system information into algorithm design. Specifically, we develop the Information-aided OSA algorithm (IOSA) by introducing a novel drift augmenting idea in Lyapunov optimization. We show that IOSA is able to achieve the $O(\epsilon)$ close-to-optimal utility performance and ensures that the required traffic buffer and energy storage size are $O(\log (1/\epsilon)^2)$ with high probability. [ABSTRACT FROM AUTHOR]

Motivated by the increasing popularity of learning and predicting human user behavior in communication and computing systems, in this paper, we investigate the fundamental benefit of predictive scheduling, i.e., predicting and pre-serving arrivals, in controlled queueing systems. Based on a lookahead-window prediction model, we first establish a novel queue-equivalence between the predictive queueing system with a fully efficient scheduling scheme and an equivalent queueing system without prediction. This result allows us to analytically demonstrate that predictive scheduling necessarily improves system delay performance and drives it to zero with increasing prediction power. It also enables us to exactly determine the required prediction power for different systems and study its impact on tail delay. We then propose the Predictive Backpressure (PBP) algorithm for achieving optimal utility performance in such predictive systems. PBP efficiently incorporates prediction into stochastic system control and avoids the great complication due to the exponential state space growth in the prediction window size. We show that PBP achieves a utility performance that is within O(\epsilon) of the optimal, for any \epsilon > 0, while guaranteeing that the system delay distribution is a shifted-to-the-left version of that under the original Backpressure algorithm. Hence, the average delay under PBP is strictly better than that under Backpressure, and vanishes with increasing prediction window size. This implies that the resulting utility-delay tradeoff with predictive scheduling can beat the known optimal [O(\epsilon),O(\log(1/\epsilon))] tradeoff for systems without prediction. We also develop the Predictable-Only PBP (POPBP) algorithm and show that it effectively reduces packet delay in systems where traffic can only be predicted but not pre-served. [ABSTRACT FROM PUBLISHER]

This paper considers a stochastic optimization approach for job scheduling and server management in large-scale, geographically distributed data centers. Randomly arriving jobs are routed to a choice of servers. The number of active servers depends on server activation decisions that are updated at a slow time scale, and the service rates of the servers are controlled by power scaling decisions that are made at a faster time scale. We develop a two-time-scale decision strategy that offers provable power cost and delay guarantees. The performance and robustness of the approach is illustrated through simulations. [ABSTRACT FROM AUTHOR]

In this paper, we show how to achieve close-to-optimal utility performance in energy-harvesting networks with only finite capacity energy storage devices. In these networks, nodes are capable of harvesting energy from the environment. The amount of energy that can be harvested is time-varying and evolves according to some probability law. We develop an online algorithm, called the Energy-limited Scheduling Algorithm (ESA), which jointly manages the energy and makes power allocation decisions for packet transmissions. ESA only has to keep track of the amount of energy left at the network nodes and does not require any knowledge of the harvestable energy process. We show that ESA achieves a utility that is within O(\epsilon) of the optimal, for any \epsilon>0, while ensuring that the network congestion and the required capacity of the energy storage devices are deterministically upper-bounded by bounds of size O(1/\epsilon). We then also develop the Modified-ESA (MESA) algorithm to achieve the same O(\epsilon) close-to-utility performance, with the average network congestion and the required capacity of the energy storage devices being only O([\log (1/\epsilon)]^2), which is close to the theoretical lower bound O(\log (1/\epsilon)). [ABSTRACT FROM AUTHOR]

There has been considerable work developing a stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay-efficient. In this paper, we show that the Backpressure algorithm, when combined with the last-in–first-out (LIFO) queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is within O(1/V) of the optimal value, for any scalar V\geq 1, while maintaining an average delay of O([\log(V)]^2) for all but a tiny fraction of the network traffic. This result holds for a general class of problems with Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show a good match between theory and practice. Because some packets may stay in the queues for a very long time under LIFO-Backpressure, we further develop the LIFO^p-Backpressure algorithm, which generalizes LIFO-Backpressure by allowing interleaving between first-in–first-out (FIFO) and LIFO. We show that LIFO^p-Backpressure also achieves the same O(1/V) close-to-optimal utility performance and guarantees an average delay of O([\log(V)]^2) for the packets that are served during the LIFO period. [ABSTRACT FROM AUTHOR]