Accepted Papers

Title: Improving Rule-Based Elasticity Control by Adapting the Sensitivity of the Auto-Scaling Decision Timeframe

Authors: Demetris Trihinas, Zacharias Georgiou, George Pallis and Marios Dikaiakos

Cloud computing offers the opportunity to reduce IT costs and im- prove the efficiency of deployed services 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 thresh- old 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 the monitoring data. The latter, can lead to unjustified scaling actions and thus, significant costs. In this paper, we introduce AdaSense, 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 AdaSense is able to correctly identify scaling actions and in contrast to the AWS auto-scaler, is able to lower detection delay on average by 63%.


Title: Towards an Algebraic Cost Model for Graph Operators

Authors: Alexander Singh and Dimitrios Tsoumakos

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 graph technology. To achieve this, detailed and accurate cost models for the various runtimes and operators must be defined and exported, such that intelligent meta- 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.

Title: Computing probabilistic queries in the presence of uncertainty via probabilistic automata

Authors: Theodore Andronikos, Alexander Singh, Konstantinos Giannakis and Spyros Sioutas

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, that aim to incorporate such information in a mean- ingful way in the computation of queries. Here, we propose a framework of query evaluation in the presence of uncertainty, based on probabilis- tic automata. 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.

Title: Risk Aware Stochastic Placement of Cloud services: The Case of Two Data Centers

Authors: Galia Shabtai, Dan Raz and Yuval Shavitt

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 min- imizes 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.

Title: A Walk in the Clouds: Routing through VNFs on Bidirected Networks

Authors: Klaus-Tycho Foerster, Mahmoud Parham, and Stefan Schmid

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) ∈ V2 and a set of waypoints W ⊂ 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.

Title: Service Chain Placement in SDNs

Authors: Gilad Kutiel and Dror Rawitz

We study the allocation problem of a compound request for a service chain in a software defined network that supports network function virtualization. Given a network that contains servers with limited processing power and of links with limited bandwidth, a service chain is a sequence of virtual network functions (VNFs) that service a certain flow request in the network. The allocation of a service chain consists of routing and VNF placement, namely each VNF from the sequence is placed in a server along a path. It is feasible if each server can handle the VNFs that are assigned to it, and if each link on the path can carry the flow that is assigned to it. A request for service is composed of a source and a destination in the network, an upper bound on the total latency, and a specification in the form of a directed acyclic graph (DAG) of VNFs that provides all service chains that are considered valid for this request. In addition, each pair of server and VNF is associated with a cost for placing the VNF in the server. Given a request, the goal is to find a valid service chain of minimum total cost that respects the latency constraint or to identify that such a service chain does not exist.

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 a randomized algorithm for instances in which the service chain passes through a bounded number of vertices whose degree is larger than two.

Title: Tight Approximability of the Server Allocation Problem for Real-Time Application

Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto and Taichi Shiitada

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 -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.

Title: Automatic Scaling of Resources in a Storm Topology

Authors: Evaggelos Golemis, Katerina Doka and Nectarios Koziris

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.

Title: Risk Aware Stochastic Placement of Cloud services: The Multiple Data Center Case

Authors: Galia Shabtai, Dan Raz and Yuval Shavitt

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 real data that the scheme performs very well on realistic service workloads.