Network function virtualization is a promising technique to greatly improve the effectiveness and flexibility of network services through a process named service function chain (SFC) mapping, with which network functions are deployed over virtualized and shared platforms in data centers. However, failures are quite common in data centers. Therefore, a practical and yet theoretically challenging issue in SFC mapping in such an environment is to manage the availability of the requests. In this paper, we present a framework to provision availability of SFC requests in a data center with multiple layers of connected devices, and the devices follow heterogeneous failure processes with the objective of minimizing resource usage. To expedite the process, we further propose an optimization problem of request mapping and backup estimation and solve it efficiently with an approximation algorithm. With simulations, we demonstrate the effectiveness of our proposed framework.

Availability, as a part of Service Level Agreement (SLA), is a critically important issue in cloud services, as an application may not be able to run after certain server or network failures. Cloud service providers seek to not only fulfill the SLA, but also simultaneously minimize their operating costs, which are dominated by the energy consumption. In order to minimize the impact of a server/switch failure inside the datacenter on a single application, one would like to spread out the Virtual Machines (VM) for the application across different racks. However, in doing so, the power consumption may increase significantly. In this paper, we develop a variance-based metric to measure the risk of violating the availability requirement. We then propose two heuristic algorithms to place VMs in online and offline manners, respectively. These algorithms aim to strike a balance between minimizing the risk of violating the availability requirement and minimizing the energy, in order to reduce the overall cost.

A central challenge in developing cloud datacenters Service Level Agreements is the estimation of downtime distribution of a set of provisioned servers over a service window, which is compounded by three facts. First, while steady-state probabilities have been derived for birth-death processes involving server failures and repairs, they could be highly inaccurate under transience. Furthermore, steady-state cannot be assured under typical service windows. Therefore, estimation of transient distributions is essential. Second, the processes of failures and repairs may follow any distribution and hence need to be extracted using system log data and modeled using appropriate general distributions. Third, downtime distributions over service windows depend on the number of servers and their deployment structure for a contract. We develop an efficient and generalized sample path randomization approach to precisely estimate transient probabilities under three different checkpointing strategies and three flexible failure distribution models. The estimators are unbiased, consistent, efficient and sufficient. Their asymptotic convergence is established. The estimation algorithms are computationally efficient in solving practical problems and yield rich information on transient system behaviors. The methodology is general and extensible to various server failure and repair processes characterized using birth-death modeling.

Commodities such as cloud resources (storage, computing, bandwidth) are often sold to clients on a pay-as-you-go basis. Thus, resource providers absorb all risk arising from end users' demand volatilities. We focus on the revenue risk management of commodities with highly volatile demand profiles using cloud computing as the application domain and bandwidth as the exemplar commodity. We extend the state of the art in risk hedging by introducing a new concept of dynamic forward contracts where a provider and a client flexibly interact through offers and responses over a set of time periods in a horizon. We develop an optimal pricing mechanism that takes into account the risk propensities of the provider and the client. The overall mechanism is modeled as a pair of nested dynamic programs denoting the offer-response interactions. The mechanism also incorporates two learning components: short-term learning on the client's demand and long-term learning on the client's risk propensity. We characterize two approaches for predicting the client's demand—a recursive demand prediction model and an aggregate demand prediction model. Detailed experimental studies of the proposed mechanism using real Web traffic data on the clients of Amazon Web Services have been carried out. The empirical results clearly demonstrate the superiority of the proposed mechanism over benchmark mechanisms such as the current industry practice of spot markets and static forward pricing mechanisms proposed in the literature in ex ante and ex post settings. The results also highlight key interaction effects among parameters controllable by a provider and the risk propensities of the market players, leading to valuable managerial implications for the practical adoption of the proposed mechanism.

Although significant technical advances have been made in the commercial deployment of grid computing, the pricing and allocation of distributed computing resources remains understudied. We develop a customized clock auction that is able to allocate grid resources and discover separate prices for the different computing resources under the condition that buyers do not know with certainty how much of these resources they will need. The proposed clock auction facilitates the discovery of unit prices for the resources in each time period in a finite-horizon market. Our mechanism exploits the lopsided nature of the grid market where a small number of large-scale jobs are expected to be completed by a large number of heterogeneous, distributed machines. The traditional stopping rule used for clock auctions is not effective in our setting, and therefore we design several adaptations that can be implemented in real time, geared toward ending the auction process quickly while producing a close-to-efficient allocation. Our extensive computations show that our clock-and-offer auction outperforms the traditional clock auction in terms of computational tractability, social welfare, and expected bidder's utility. For large problems of practical interest, we develop a transportation-based heuristic for the NP-complete bid feasibility problem and demonstrate theoretically and computationally that it quickly produces high-quality solutions to the overall problem.

Grid computing uses software to integrate computing resources, such as CPU cycles, storage, network bandwidth, and even applications, across a distributed and heterogeneous set of networked computers. It is now widely deployed by organizations and provides seamless temporary processing-capacity expansion to handle peak-period demand on e-commerce servers, distributed gaming, and content storage and distribution. We develop a market-based resource-allocation model that adds an economic layer to the current approach of treating resource allocation as primarily a scheduling issue. We design a value-elicitation and allocation scheme that provides the economic incentives for buyers and sellers of computing resources to exchange assets. We formulate the problem as a combinatorial call auction and present a portfolio of three solution approaches that trade off economic properties, such as allocative efficiency, incentive compatibility, and fairness in allocation, with computational efficiency. The first of these is an efficient solution that maximizes social welfare and yields incentive-compatible Vickrey-Clarke-Groves prices, but requires solving multiple instances of an NP-hard problem. For markets where having a commodity price is critical, we show how the addition of fairness constraints to the efficient model can somewhat reduce the computational burden and yet preserve incentive compatibility. Finally, for markets that require real-time fast solution techniques, we propose a time-sensitive fair Grid (tsfGRID) heuristic that relaxes the maximal allocation requirement of the welfare-maximizing fair solution. Its solution is not guaranteed to be incentive-compatible, but the heuristic is designed to be fast, maintain fairness in allocations, and yield commodity prices. Notably, while incentive compatibility is not guaranteed by tsfGRID, computational results comparing it with the efficient solution technique indicate that there are no significant differences in the expected-revenue and operational-allocative characteristics.