A terrain is an $x$-monotone polygon whose lower boundary is a single line segment. We present an algorithm to find in a terrain a triangle of largest area in $O(nlog n)$ time, where $n$ is the number of vertices defining the terrain. The best previous algorithm for this problem has a running time of $O(n^2)$.

Modern cloud-native applications are adopting the microservice architecture in which applications are deployed in lightweight containers that run inside a virtual machine (VM). Containers running different services are often co-located inside the same virtual machine. While this enables better resource optimization, it can cause interference among applications. This can lead to performance degradation. Detecting the cause of performance degradation at runtime is crucial to decide the correct remediation action such as, but not limited to, scaling or migrating. We propose a non-intrusive detection technique that differentiates between degradation caused by load and by interference. First, we define an operational zone for the application. Then we define a disambiguation method that uses models to classify interference and normal load. In contrast to previous work, our proposed detection technique does not require intrusive application instrumentation and incurs minimal performance overhead. We demonstrate how we can design effective Machine Learning models that can be generalized to detect interference from different types of applications. We evaluate our technique using realistic microservice benchmarks on AWS EC2. The results show that our approach outperforms existing interference detection techniques in F_1 score by at least 2.75% and at most 53.86%.

In self-adaptive systems, model-based control assumes decisions are taken based on a model that is identified at run-time. The model is built by measuring the control inputs, disturbances, and outputs of the controlled system and fitting the data into a function. Models can be accurate locally, that is, for data already seen by the system and by the model identification method. However, many times an Autonomic Manager (AM) needs to move the cloud-native applications into new operational points, e.g. by adding new applications to the shared environment, scaling applications or consolidating resources. There are no data points yet for these new operational regions to have any certainty that the prediction models are accurate. In this paper, we propose a method to identify a model that predicts metrics at any unexplored operational point of a cloud-native application. The method is based on a lightweight Look-Ahead Scanner (LAS) mechanism that explores different operational points by injecting controlled short-lived load. We evaluate our method on realistic applications deployed on public clouds. We show that the proposed method can build models that outperform the state of the art ML models by 42%.

Cloud-native applications are often composed of lightweight containers and conform to the microservice architecture. Cloud providers offer platforms for container hosting and orchestration. These platforms reduce the level of support required from the application owner as operational tasks are delegated to the platform. Furthermore, containers belonging to different applications can be co-located on the same virtual machine to utilize resources more efficiently. Given that there are underlying shared resources and consequently potential performance interference, predicting the level of interference before deciding to share virtual machines can avoid undesirable performance deterioration. We propose a lightweight performance interference modelling technique for cloud-native microservices. The technique constructs ML models for response time prediction and can dynamically account for changing runtime conditions through the use of a sliding window method. We evaluate our technique against realistic microservices on AWS EC2. Our technique outperforms baseline and competing techniques in MAPE by at least 1.45% and at most 92.04%.

Function as a Service (FaaS) is a new software technology with promising features such as automated resource management and auto-scaling. Since these operational aspects are transparent, software engineers may not fully understand the scaling characteristics as well as limitations of this technology and this lack of information can lead to undesired performance results. To address these concerns, we perform a study to characterize FaaS' scalability with intensive workloads on three popular FaaS cloud platforms, namely Amazon AWS Lambda, IBM and Azure Cloud Function. We also study a workload smoother design pattern to examine if it enhances FaaS overall performance. The results show that different FaaS platforms adopt distinct scaling strategies and by applying a workload smoother, software engineers can achieve 99 - 100% success rates compared to 60 - 80% when FaaS' system is saturated.

DevOps is an emerging paradigm that integrates the development and operations teams to enable fast and efficient continuous delivery of software. Applications and services deployed on cloud platforms can benefit from implementing the DevOps practice. This involves using different tools for enabling end-to-end automation to ensure continuous deployment and maintain good Quality-of-Service. Self-Adaptive systems can support the DevOps process by automating service deployment and maintenance without manual intervention by employing a MAPE-K (Monitoring, Analysis, Planning, Execution- Knowledge) framework. While industrial MAPE-K tools are robust and built for production environments, they lack the flexibility to adapt large applications on multi-cloud environments. Academic models are more flexible and can be used to perform sophisticated self-adaption, but can lack the robustness to be used in production environments. In this paper, we present a MAPE-K framework that is built with existing Components-off-the-Shelf (COTS) that interacts with each other to perform self-adaptive actions on multi-cloud environments. By integrating existing COTS, we are able to deploy a MAPE-K framework efficiently to support DevOps for applications running on a multi-cloud environment. We validate our framework with a prototype implementation and demonstrate its practical feasibility by a detailed case study done on a real industrial platform.

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T − S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here, the input is a tournament T and a weight function w : V ( T ) → N, and the task is to find a feedback vertex set S in T minimizing w ( S ) = ∑ v∈S w ( v ). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2.5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this article, we give the first polynomial time factor 2-approximation algorithm for this problem. Assuming the Unique Games Conjecture, this is the best possible approximation ratio achievable in polynomial time.

Web services hosted on public cloud platforms are often subjected to performance anomalies. Runtime detection of such anomalies is crucial for operations in cloud data centers. With ever-increasing data center size, complexities in software applications and dynamic traffic workload patterns, automatically detecting performance anomalies is a challenging task. In this paper, we propose RAD, a lightweight runtime anomaly detection technique that does not require application level instrumentation and can be easily implemented for detecting anomalies in multi-tier cloud-based Web services. In particular, we focus on anomalies that are difficult to detect by simply monitoring system level metrics alone, such as anomalies that are caused by contention from within a service and also those caused by shared resource contention by other services running on the cloud. RAD continuously monitors service resource metrics and uses a queuing network model to detect performance anomalies at runtime. Additionally, RAD uses historical data and implements a statistical methodology to diagnose the root cause of an anomaly. We evaluate RAD on a private cloud and also on the EC2 public cloud platform to show that RAD incurs extremely low levels of performance overhead on the service and is effective for detecting anomalies in both multi-tier monolithic services and microservices.

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T – S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here the input is a tournament T and a weight function w: V(T) → ℕ and the task is to find a feedback vertex set S in T minimizing w(S) = ΣvϵSw(v). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2.5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this paper we give the first polynomial time factor 2 approximation algorithm for this problem. Assuming the Unique Games conjecture, this is the best possible approximation ratio achievable in polynomial time.

Network services, e.g., video streaming services, are increasingly being deployed on public cloud platforms. Such services often employ horizontal scaling where a group of resource instances, e.g., virtual machines (VMs), handle incoming workload. The response time of such services is often affected by interference, i.e., contention among resource instances belonging to multiple cloud subscribers for shared cloud resources. Most commercial cloud platforms do not support built-in mechanisms to detect interference and mitigate its impact. Consequently, subscribers of such platforms, i.e., network service providers, need to deploy their own mechanisms to ensure a specified end user response time target is continuously met even in the face of fluctuations in workload and interference. This paper describes PRIMA, our implementation of such a mechanism. PRIMA uses automated and controlled performance tests to build models that capture the joint impact of workload and interference on the response time of each resource instance employed by a service. It adapts the system to changing workload and interference conditions by using these models at runtime to control the number of instances in the system and the distribution of load among these instances. Unlike existing subscriber-oriented interference mitigation techniques in literature, PRIMA guarantees that a subscriber-specified response time threshold is satisfied at every resource instance assigned to a service. Furthermore, in contrast to these approaches PRIMA can help a subscriber avoid using more instances than necessary by automatically selecting at runtime the least number of instances required for handling the observed workload and interference. We experimentally validate the effectiveness of PRIMA in both private and public cloud environments. Results show that PRIMA outperforms competing approaches proposed by us and others, including those that are commonly used in practice. They also reveal that PRIMA can automatically calibrate its models at runtime to account for any model prediction errors.

Network services, e.g., video streaming services, are increasingly being deployed on public cloud platforms. Such services often employ horizontal scaling where a group of resource instances, e.g., virtual machines (VMs), handle the incoming workload. The response time of such services is often affected by interference, i.e., contention among resource instances belonging to multiple cloud subscribers for shared cloud resources. Most commercial cloud platforms do not support built-in mechanisms to detect interference and mitigate its impact. This paper outlines a solution called PRIMA that subscribers of such platforms, i.e., network service operators, can deploy to ensure a specified end user response time target is met even in the face of fluctuations in workload and interference. PRIMA uses automated and controlled performance tests to build models that capture the joint impact of workload and interference on the response time of each resource instance employed by a service. PRIMA adapts the system to changing workload and interference conditions by using these models at runtime to control the number of instances in the system and the distribution of load among these instances. Unlike existing subscriber-oriented interference mitigation techniques in literature, PRIMA provides an explicit mechanism to guarantee that the specified response time threshold is met at every resource instance assigned to a service. Furthermore, in contrast to these approaches PRIMA can help an operator avoid using more instances than necessary for handling the observed workload and interference.

Web services are now increasingly being hosted on public cloud infrastructure as a service platforms such as the Amazon Web service elastic compute cloud (EC2). However, previous studies have shown that the virtualized infrastructure used in public clouds can introduce contention among virtual machines (VMs) for shared physical host resources eventually leading to performance problems. Subscribers in a public cloud platform typically do not have access to metrics that can directly quantify the adverse impact of such inter-VM interference on Web service response times. We present a software probe based system to address this limitation. The probe is a lightweight application that runs on each Web service VM that needs to be monitored. We periodically measure the probe's response time on a monitored VM. We then compare this response time with the probe's previously recorded baseline no-interference response time when it executes in isolation on a VM of the same type. Statistically significant increase in the probe's response time from the baseline is used to detect interference. The probe also indicates the type of contention at the physical host that causes the interference. This information can be exploited by a subscriber to mitigate the problem. Results show that our approach is quite effective over two different cloud platforms and a wide variety of workload scenarios. In particular, results indicate that Web service instances hosted on EC2 suffer from interference. Our probe was able to detect 93% of performance degradations triggered by such interference. In all these cases, the probe imposed an average overhead of only 3%-4% on the mean response time of the Web service being monitored.

Public and private cloud computing environments employ virtualization methods to consolidate application workloads onto shared servers. Modern servers typically have one or more sockets each with one or more computing cores, a multi-level caching hierarchy, a memory subsystem, and an interconnect to the memory of other sockets. While resource management methods may manage application performance by controlling the sharing of processing time and input-output rates, there is generally no management of contention for virtualization kernel resources or for the memory hierarchy and subsystems. Yet such contention can have a significant impact on application performance. Hardware platform specific counters have been proposed for detecting such contention. We show that such counters alone are not always sufficient for detecting contention. We propose a software probe based approach for detecting contention for shared platform resources and demonstrate its effectiveness. We show that the probe imposes low overhead and is remarkably effective at detecting performance degradations due to inter-VM interference over a wide variety of workload scenarios and on two different server architectures. The probe successfully detected virtualization-induced software bottleneck and memory contention on both server architectures. Our approach supports the management of workload placement on shared servers and pools of shared servers.