Resource management in cloud computing is a difficult problem, as one is often tasked with balancing between adequate service to clients and cost minimization in dynamic environments of many ...interconnected components. To make correct decisions in these environments, good performance models are necessary. A common modeling methodology is to use networks of queues, but as these are prohibitively expensive to evaluate for many real-time applications, different approximation methods for important metrics are frequently employed. One such method—that provides both transient solutions and short, scalable computation times—is the fluid model, which approximates the dynamics of the mean queue lengths using a system of ordinary differential equations. However, finding a fluid model that can adequately approximate an arbitrary queueing network is in general difficult. In this paper, we extend the state of the art with the following three contributions. First, we show that for any mixed multiclass queueing network of processor sharing and delay queues with phase-type service time distributions, such a fluid model can be found via the mean-field approximation. Furthermore, we propose an improved model based on smoothing of the processor share function that improves the performance of certain systems. Finally, using the smoothed mean-field model, we introduce an accurate closed-form approximation of the response time CDF over any subset of classes and queues. The contributions are further evaluated in a large simulation experiment, which shows that they can be used to accurately predict performance metrics under some system perturbations common in cloud computing.
The proliferation of connected embedded devices, or
the Internet of Things
(IoT), together with recent advances in machine intelligence, will change the profile of future cloud services and introduce ...a variety of new research problems, both in cloud applications and infrastructure layers. These problems are centered around empowering individually resource-limited devices to exhibit intelligent behavior, both in sensing and control, thanks to a judicious utilization of cloud resources. Cloud services will enable learning from data, perform inference, and execute control, all with assurances on outcomes. This article discusses such emerging services and outlines five resulting new research directions towards enabling and optimizing intelligent, cloud-assisted sensing and control in the age of the Internet of Things.
This paper addresses the out-of-sequence measurement (OOSM) problem for mixed linear/nonlinear state-space models, which is a class of nonlinear models with a tractable, conditionally linear ...substructure. We develop two novel algorithms that utilize the linear substructure. The first algorithm effectively employs the Rao-Blackwellized particle filtering framework for updating with the OOSMs, and is based on storing only a subset of the particles and their weights over an arbitrary, predefined interval. The second algorithm adapts a backward simulation approach to update with the delayed (out-of-sequence) measurements, resulting in superior tracking performance. Extensive simulation studies show the efficacy of our approaches in terms of computation time and tracking performance. Both algorithms yield estimation improvements when compared with recent particle filter algorithms for OOSM processing; in the considered examples they achieve up to 10% enhancements in estimation accuracy. In some cases, the proposed algorithms even deliver accuracy that is similar to the lower performance bounds. Because the considered setup is common in various estimation scenarios, the developed algorithms enable improvements in different types of filtering applications.
In this 25th year anniversary paper for the IEEE Real Time Systems Symposium, we review the key results in real-time scheduling theory and the historical events that led to the establishment of the ...current real-time computing infrastructure. We conclude this paper by looking at the challenges ahead of us.
Harmonic periods have wide applicability in industrial real-time systems. Rate monotonic (RM) is able to schedule task sets with harmonic periods up to 100% utilization. Also, if there is no release ...jitter and execution time variation, RM and EDF generate the same schedule for each instance of a task. As a result, all instances of a task are interfered by the same amount of workload. This property decreases the jitters that happen during sampling and actuation of the tasks, and hence, it increases the quality of service in control systems. In this paper, we consider the problem of optimal period assignment where the periods are constrained to be harmonic and the task set is required to be feasible. We study two variants of this problem. In the first one, the objective is to maximize the system utilization, while in the second one, the goal is to minimize the total weighted sum of the periods. First, we assume that an interval is determined a priori for each task from which its period can be selected. We show that both variants of the problem are (at least) weakly NP-hard. This is shown by reducing the NP-complete number partitioning problem to the mentioned harmonic period assignment problems. Afterwards, we consider a variant of the second problem in which the periods are not restricted to a special interval. We present two approximation algorithms with polynomial-time complexity for this problem and show that the maximum relative error of these algorithms is bounded by a factor of 1.125. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution.
Brownout: building more robust cloud applications Klein, Cristian; Maggio, Martina; Årzén, Karl-Erik ...
Proceedings of the 36th International Conference on Software Engineering,
05/2014
Conference Proceeding
Open access
Self-adaptation is a first class concern for cloud applications, which should be able to withstand diverse runtime changes. Variations are simultaneously happening both at the cloud infrastructure ...level - for example hardware failures - and at the user workload level - flash crowds. However, robustly withstanding extreme variability, requires costly hardware over-provisioning.
In this paper, we introduce a self-adaptation programming paradigm called brownout. Using this paradigm, applications can be designed to robustly withstand unpredictable runtime variations, without over-provisioning. The paradigm is based on optional code that can be dynamically deactivated through decisions based on control theory.
We modified two popular web application prototypes - RUBiS and RUBBoS - with less than 170 lines of code, to make them brownout-compliant. Experiments show that brownout self-adaptation dramatically improves the ability to withstand flash-crowds and hardware failures.
A scheduling architecture for real-time control tasks is proposed. The scheduler uses feedback from execution-time measurements and feedforward from workload changes to adjust the sampling periods of ...the control tasks so that the combined performance of the controllers is optimized. The performance of each controller is described by a cost function. Based on the solution to the optimal resource allocation problem, explicit solutions are derived for linear and quadratic approximations of the cost functions. It is shown that a linear rescaling of the nominal sampling frequencies is optimal for both of these approximations. An extensive inverted pendulum example is presented, where the performance obtained with open-loop, feedback, combined feedback and feedforward scheduling, and earliest-deadline first scheduling are compared. The performance under earliest-deadline first scheduling is explained by studying the behavior of periodic tasks under overload conditions. It is shown that the average values of the sampling periods equal the nominal periods, rescaled by the processor utilization.
Cloud applications are often subject to unexpected events like flashcrowds and hardware failures. Users that expect a predictable behavior may abandon an unresponsive application when these events ...occur. Researchers and engineers addressed this problem on two separate fronts: first, they introduced replicas – copies of the application with the same functionality – for redundancy and scalability; second, they added a self-adaptive feature called brownout inside cloud applications to bound response times by modulating user experience. The presence of multiple replicas requires a dedicated component to direct incoming traffic: a load-balancer.
Existing load-balancing strategies based on response times interfere with the response time controller developed for brownout-compliant applications. In fact, the brownout approach bounds response times using a control action. Hence, the response time, that was used to aid load-balancing decision, is not a good indicator of how well a replica is performing.
To fix this issue, this paper reviews some proposal for brownout-aware load-balancing and provides a comprehensive experimental evaluation that compares them. To provide formal guarantees on the load-balancing performance, we use a randomized optimization approach and apply the scenario theory. We perform an extensive set of experiments on a real machine, extending the popular lighttpd web server and load-balancer, and obtaining a production-ready implementation. Experimental results show an improvement of the user experience over Shortest Queue First (SQF)—believed to be near-optimal in the non-adaptive case. The improved user experience is obtained preserving the response time predictability.
High-performance embedded systems require the execution of many applications on multicore platforms and are subject to stringent restrictions and constraints. The ACTORS project approach provides ...temporal isolation through resource reservation over a multicore platform, adapting the available resources on the basis of the overall quality requirements. The architecture is fully operational on both ARM MPCore and x86 multicore platforms.
PDF
