Search

Motivated by maximizing spot instances in cloud shared systems, in this work, we consider the problem of taking advantage of unused resources in highly dynamic cloud environments while preserving users' performance. We introduce an online model for sharing resources that captures basic properties of cloud systems, such as unpredictable users' demand patterns, very limited feedback from the system, and service level agreement (SLA) between the users and the cloud provider. We provide a simple and efficient algorithm for the single-resource case. For any demand patterns, our algorithm guarantees near-optimal resource utilization as well as high users' performance compared with their SLA baseline. In addition to this, we validate empirically the performance of our algorithm using synthetic data and data obtained from Microsoft's systems. Cloud computing has motivated renewed interest in resource allocation problems with new consumption models. A common goal is to share a resource, such as CPU or I/O bandwidth, among distinct users with different demand patterns as well as different quality of service requirements. To ensure these service requirements, cloud offerings often come with a service level agreement (SLA) between the provider and the users. A SLA specifies the amount of a resource a user is entitled to utilize. In many cloud settings, providers would like to operate resources at high utilization while simultaneously respecting individual SLAs. There is typically a trade-off between these two objectives; for example, utilization can be increased by shifting away resources from idle users to "scavenger" workload, but with the risk of the former then becoming active again. We study this fundamental tradeoff by formulating a resource allocation model that captures basic properties of cloud computing systems, including SLAs, highly limited feedback about the state of the system, and variable and unpredictable input sequences. Our main result is a simple and practical algorithm that achieves near-optimal performance on the above two objectives. First, we guarantee nearly optimal utilization of the resource even if compared with the omniscient offline dynamic optimum. Second, we simultaneously satisfy all individual SLAs up to a small error. The main algorithmic tool is a multiplicative weight update algorithm and a primal-dual argument to obtain its guarantees. We also provide numerical validation on real data to demonstrate the performance of our algorithm in practical applications. [ABSTRACT FROM AUTHOR]

We introduce a novel pricing and resource allocation approach for batch jobs on cloud systems. In our economic model, users submit jobs with a value function that specifies willingness to pay as a function of job due dates. The cloud provider in response allocates a subset of these jobs, taking into advantage the flexibility of allocating resources to jobs in the cloud environment. Focusing on social-welfare as the system objective (especially relevant for private or in-house clouds), we construct a resource allocation algorithm which provides a small approximation factor that approaches 2 as the number of servers increases. An appealing property of our scheme is that jobs are allocated non-preemptively, i.e., jobs run in one shot without interruption. This property has practical significance, as it avoids significant network and storage resources for checkpointing. Based on this algorithm, we then design an efficient truthful-in-expectation mechanism, which significantly improves the running complexity of black-box reduction mechanisms that can be applied to the problem, thereby facilitating its implementation in real systems. [ABSTRACT FROM AUTHOR]

We consider a dynamic spectrum access system in which Secondary Users (SUs) choose to either acquire dedicated spectrum or to use spectrum-holes (white spaces) which belong to Primary Users (PUs). The trade-off incorporated in this decision is between immediate yet costly transmission and free but delayed transmission (a consequence of both the possible appearance of PUs and sharing the spectrum holes with multiple SUs). We first consider a system with a single PU band, in which the SU decisions are fixed. Employing queueing-theoretic methods, we obtain explicit expressions for the expected delays associated with using the PU band. Based on that, we then consider self-interested SUs and study the interaction between them as a non-cooperative game. We prove the existence and uniqueness of a symmetric Nash equilibrium, and characterize the equilibrium behavior explicitly. Using our equilibrium results, we show how to maximize revenue from renting dedicated bands to SUs and briefly discuss the extension of our model to multiple PUs. Finally, since spectrum sensing can be resource—consuming, we characterize the gains provided by this capability. [ABSTRACT FROM AUTHOR]

A major problem in wireless networks is coping with limited resources, such as bandwidth and energy. These issues become a major algorithmic challenge in view of the dynamic nature of the wireless domain. We consider in this paper the single-transmitter power assignment problem under time-varying channels, with the objective of maximizing the data throughput. It is assumed that the transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, which leads to explicit “water-filling” solutions, by considering a realistic scenario where the channel state quality changes arbitrarily from one transmission to the other. The problem is accordingly tackled within the framework of competitive analysis, which allows for worst-case performance guarantees in setups with arbitrarily varying channel conditions. We address both a “discrete” case, where the transmitter can transmit only at a fixed power level, and a “continuous” case, where the transmitter can choose any power level out of a bounded interval. For both cases, we propose online power-allocation algorithms with proven worst-case performance bounds. In addition, we establish lower bounds on the worst-case performance of any online algorithm and show that our proposed algorithms are optimal. [ABSTRACT FROM PUBLISHER]

In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic, and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corresponds to the well-known potential games. We refer to the second class of games as harmonic games, and demonstrate that this new class has interesting properties which contrast with properties of potential games. Exploiting the decomposition framework, we obtain explicit expressions for the projections of games onto the subspaces of potential and harmonic games. This enables an extension of the equilibrium properties of potential and harmonic games to "nearby" games. [ABSTRACT FROM AUTHOR]

We consider an uplink wireless collision channel, shared by multiple mobile users. The medium access protocol incorporates channel reservation that relies on RTS (request-to-send) and CTS (clear-to-send) control packets. Consequently, collisions are reduced to the relatively short periods where mobiles request channel use. In our model, users individually schedule their channel requests, and the objective of each user is to minimize its own power investment subject to a minimum-throughput demand. Our analysis reveals that for feasible throughput demands, there exist exactly two Nash equilibrium points in stationary strategies, with one superior to the other uniformly over all users. We then show how this better equilibrium point can be obtained through distributed best-response mechanisms. Finally, we quantify and discuss the effect of the relative length of data and control periods on capacity, power and delay. [ABSTRACT FROM AUTHOR]

Differentiated services architectures are scalable solutions for providing class-based Quality of Service (QoS) over packet switched networks. While qualitative attributes of the offered service classes are often well defined, the actual differentiation between classes is left as an open issue. We address here the proportional QoS model, which aims at maintaining pre-defined ratios between the service class delays (or related congestion measures). In particular, we consider capacity assignment among service classes as the means for attaining this design objective. Starting with a detailed analysis for the single hop model, we first obtain the required capacity assignment for fixed flow rates. We then analyze the scheme under a reactive scenario, in which self-optimizing users may choose their service class in response to capacity modifications. We demonstrate the existence and uniqueness of the equilibrium in which the required ratios are maintained, and address the efficient computation of the optimal capacities. We further provide dynamic schemes for capacity adjustment, and consider the incorporation of pricing and congestion control to enforce absolute performance bounds on top of the proportional ones. Finally, we extend our basic results to networks with general topology. [ABSTRACT FROM AUTHOR]

We consider a wireless collision channel, shared by a finite number of users who transmit to a common base station. Each user wishes to minimize its average transmission rate (or power investment), subject to minimum throughput demand. The channel quality between each user and the base station is randomly time-varying, and partially observed by the user through Channel State Information (CSI) signals. Assuming that all users employ stationary, CSI-dependent transmission policies, we investigate the properties of the Nash equilibrium of the resulting game between users. We characterize the feasible region of user's throughput demands, and provide lower bounds on the channel capacity that hold both for symmetric and non-symmetric users. Our equilibrium analysis reveals that, when the throughput demands are feasible, there exist exactly two Nash equilibrium points, with one strictly better than the other (in terms of power investment) for each user. We further demonstrate that the performance gap between the two equilibria may be arbitrarily large. This motivates the need for distributed mechanisms that lead to the better equilibrium. To that end, we suggest a simple greedy (best-response) mechanism, and prove convergence to the better equilibrium. Some important stability properties of this mechanism in face of changing user population are derived as well. [ABSTRACT FROM AUTHOR]

Reinforcement Learning (RL) is an approach for solving complex multi-stage decision problems that fall under the general framework of Markov Decision Problems (MDPs), with possibly unknown parameters. Function approximation is essential for problems with a large state space, as it facilitates compact representation and enables generalization. Linear approximation architectures (where the adjustable parameters are the weights of pre-fixed basis functions) have recently gained prominence due to efficient algorithms and convergence guarantees. Nonetheless, an appropriate choice of basis function is important for the success of the algorithm. In the present paper we examine methods for adapting the basis function during the learning process in the context of evaluating the value function under a fixed control policy. Using the Bellman approximation error as an optimization criterion, we optimize the weights of the basis function while simultaneously adapting the (non-linear) basis function parameters. We present two algorithms for this problem. The first uses a gradient-based approach and the second applies the Cross Entropy method. The performance of the proposed algorithms is evaluated and compared in simulations. [ABSTRACT FROM AUTHOR]