Algorithmic Aspects of Cloud Computing

Todays IT services are provided by centralized infrastructure referred to as datacenters. In contrast to supercomputers aimed at the high-cost/high-performance scientific domain, datacenters consist of low-cost servers for high-volume data processing, communication and storage. Datacenter owners prioritize capital and operating costs (often measured in performance per watt) over ultimate performance.

The virtualization of network functions enables innovative new network services which can be deployed quickly and at low cost on (distributed) cloud computing infrastructure. This paper initiates the algorithmic study of the fundamental underlying problem of how to efficiently route traffic through a given set of Virtualized Network Functions (VNFs). We are given a link-capacitated network \(G=(V,E)\), a source-destination pair \((s,t)\in V^2\) and a set of waypoints \(\mathscr {W} \subset V\) (the VNFs). In particular, we consider the practically relevant but rarely studied case of bidirected networks. The objective is to find a (shortest) route from s to t such that all waypoints are visited. We show that the problem features interesting connections to classic combinatorial problems, present different algorithms, and derive hardness results.

We show that even the feasibility problem is NP-hard in general graphs. Hence we focus on DAGs. We show that the problem is still NP-hard in DAGs even for a very simple network, and even if the VNF specification consists of only one option (i.e., the virtual DAG is a path). On the other hand, we present an FPTAS for the case where the network is a DAG. In addition, based on our FPTAS, we provide algorithms for instances in which the service chain passes through a bounded number of vertices whose degree is larger than two.

The server allocation problem is a facility location problem for a distributed processing scheme on a real-time network. In this problem, we are given a set of users and a set of servers. Then, we consider the following communication process between users and servers. First a user sends his/her request to the nearest server. After receiving all the requests from users, the servers share the requests. A user will then receive the data processed from the nearest server. The goal of this problem is to choose a subset of servers so that the total delay of the above process is minimized. In this paper, we prove the following approximability and inapproximability results. We first show that the server allocation problem has no polynomial-time approximation algorithm unless P = NP. However, assuming that the delays satisfy the triangle inequality, we design a polynomial-time \({3 \over 2}\)-approximation algorithm. When we assume the triangle inequality only among servers, we propose a polynomial-time 2-approximation algorithm. Both of the algorithms are tight in the sense that we cannot obtain better polynomial-time approximation algorithms unless P = NP. Furthermore, we evaluate the practical performance of our algorithms through computational experiments, and show that our algorithms scale better and produce comparable solutions than the previously proposed method based on integer linear programming.

Allocating the right amount of resources to each service in any of the data centers in a cloud environment is a very difficult task. This task becomes much harder due to the dynamic nature of the workload and the fact that while long term statistics about the demand may be known, it is impossible to predict the exact demand in each point in time. As a result, service providers either over allocate resources and hurt the service cost efficiency, or run into situation where the allocated local resources are insufficient to support the current demand. In these cases, the service providers deploy overflow mechanisms such as redirecting traffic to a remote data center or temporarily leasing additional resources (at a higher price) from the cloud infrastructure owner. The additional cost is in many cases proportional to the amount of overflow demand.

In this paper we propose a stochastic based placement algorithm to find a solution that minimizes the expected total cost of ownership in case of two data centers. Stochastic combinatorial optimization was studied in several different scenarios. In this paper we extend and generalize two seemingly different lines of work and arrive at a general approximation algorithm for stochastic service placement that works well for a very large family of overflow cost functions. In addition to the theoretical study and the rigorous correctness proof, we also show using simulation based on real data that the approximation algorithm performs very well on realistic service workloads.

Graph Analytics has been gaining an increasing amount of attention in recent years. This has given rise to the development of numerous graph processing and storage engines, each featuring different models in computation, storage and execution as well as performance. Multi-Engine Analytics present a solution towards adaptive, cost-based complex workflow scheduling to the best available underlying technology. To achieve this in the Graph Analytics case, detailed and accurate cost models for the various runtimes and operators must be defined and exported, such that intelligent planning can take place. In this work, we take a first step towards defining a cost model for graph-based operators based on an algebra and its primitives. We evaluate its accuracy over a state of the art graph database and discuss its advantages and shortcomings.

The emergence of uncertainty as an inherent aspect of RDF and linked data has spurred a number of works of both theoretical and practical interest These works aim to incorporate such information in a meaningful way in the computation of queries. In this paper, we propose a framework of query evaluation in the presence of uncertainty, based on probabilistic automata, which are simple yet efficient computational models. We showcase this method on relevant examples, where we show how to construct and exploit the convenient properties of such automata to evaluate RDF queries with adjustable cutoff. Finally, we present some directions for further investigation on this particular line of research, taking into account possible generalizations of this work.

Cloud computing offers the opportunity to improve efficiency with cloud providers offering consumers the ability to automatically scale their applications to meet exact demands. However, “auto-scaling” is usually provided to consumers in the form of metric threshold rules which are not capable of determining whether a scaling alert is issued due to an actual change in the demand of the application or due to short-lived bursts evident in monitoring data. The latter, can lead to unjustified scaling actions and thus, significant costs. In this paper, we introduce AdaFrame, a novel library which supports the decision-making of rule-based elasticity controllers to timely detect actual runtime changes in the monitorable load of cloud services. Results on real-life testbeds deployed on AWS, show that AdaFrame is able to correctly identify scaling actions and in contrast to the AWS auto-scaler, is able to lower detection delay by at least 63%.

Allocating the right amount of resources to each service in any of the data centers in a cloud environment is a very difficult task. In a previous work we considered the case where only two data centers are available and proposed a stochastic based placement algorithm to find a solution that minimizes the expected total cost of ownership. This approximation algorithm seems to work well for a very large family of overflow cost functions, which contains three functions that describe the most common practical situations. In this paper we generalize this work for arbitrary number of data centers and develop a generalized mechanism to assign services to data centers based on the available resources in each data center and the distribution of the demand for each service. We further show, using simulations based on synthetic data that the scheme performs very well on different service workloads.

In the Big Data era, the batch processing of large volumes of data is simply not enough - data needs to be processed fast to support continuous reactions to changing conditions in real-time. Distributed stream processing systems have emerged as platforms of choice for applications that rely on real-time analytics, with Apache Storm [2] being one of the most prevalent representatives. Whether deployed on physical or virtual infrastructures, distributed stream processing systems are expected to make the most out of the available resources, i.e., achieve the highest throughput or lowest latency with the minimum resource utilisation. However, for Storm - as for most such systems - this is a cumbersome trial-and-error procedure, tied to the specific workload that needs to be processed and requiring manual tweaking of resource-related topology parameters. To this end, we propose ARiSTO, a system that automatically decides on the appropriate amount of resources to be provisioned for each node of the Storm workflow topology based on user-defined performance and cost constraints. ARiSTO employs two mechanisms: a static, model-based one, used at bootstrap time to predict the resource-related parameters that better fit the user needs and a dynamic, rule-based one that elastically auto-scales the allocated resources in order to maintain the desired performance even under changes in load. The experimental evaluation of our prototype proves the ability of ARiSto to efficiently decide on the resource-related configuration parameters, maintaining the desired throughput at all times.