Abstract Autoscaling enables container cluster orchestrators to automatically adjust computational resources, such as containers and Virtual Machines (VMs), to handle fluctuating workloads effectively. This adaptation can involve modifying the amount of resources (horizontal scaling) or adjusting their computational capacity (vertical scaling). The motivation for our work stems from the limitations of previous autoscaling approaches, which are either partial (scaling containers or VMs, but not both) or excessively complex to be used in real systems. This complexity arises from their use of models with a large number of variables and the addressing of two simultaneous challenges: achieving the optimal deployment for a single scheduling window and managing the transition between successive scheduling windows. We propose an Integer Linear Programming (ILP) model to address the challenge of autoscaling containers and VMs jointly, both horizontally and vertically, to minimize deployment costs. This model is designed to be used with predictive autoscalers and be solved in a reasonable time, even for large clusters. To this end, improvements and reasonable simplifications with respect to previous models have been carried out to drastically reduce the size of the resource allocation problem. Furthermore, the proposed model provides an enhanced representation of system performance in comparison to previous approaches. A tool called Conlloovia has been developed to implement this model. To evaluate its performance, we have conducted a comprehensive assessment, comparing it with two heuristic allocators with different problem sizes. Our findings indicate that Conlloovia consistently demonstrates lower deployment costs in a significant number of cases. Conlloovia has also been evaluated with a real application, using synthetic and real workload traces, as well as different scheduling windows, with deployment costs approximately 20% lower than heuristic allocators.

For a long time, the common billing time slot used by cloud providers was the hour, but recently they have changed it to one second with a minimum charge of one minute. In this paper, the impact of this change on virtual machine allocation strategies is analyzed. With the minimum one-minute charge, the state-of-the-art allocation strategies are no longer optimal. This paper proposes a new analytic model to obtain the optimal allocation that minimizes the total cost considering this new billing scheme. However, the optimization problem using this model is unmanageable due to its computational complexity. Therefore, other sub-optimal allocations strategies are proposed. The performance of these strategies (in terms of total allocation cost and computational effort) is analyzed in order to assess the influence of the time slot length. Allocation time slots of one hour, one minute and one second are compared. The experimental work is carried out using synthetic workloads based on two real public traces. The study concludes that the time slot of one minute offers the best trade-off between allocation cost and computational effort. The experimentation shows that the proposed strategy can save up to 14 percent over using the time slot of one hour.

Stochastic analysis techniques for real-time systems model the execution time of tasks as random variables. These techniques constitute a very powerful tool to study the behaviour of real-time systems. However, as they can not avoid all the timing bugs in the implementation, they must be combined with measurement techniques in order to gain more confidence in the implemented system. In this paper, a set of tools to measure, analyze and visualize traces of real-time systems is presented. These tools are driven by stochastic models. In order to find bugs in the timing behaviour of the system, two metrics, called "pessimism" and "optimism", are proposed. They are based on two random variables, the optimistic and the pessimistic execution time, which are also introduced in this paper. These metrics are used in the debugging tools to compare the model and the measured system in order to find errors. The metrics are examined in three case studies.

This paper describes a stochastic analysis framework which computes the response time distribution and the deadline miss probability of individual tasks, even for systems with a maximum utilization greater than one. The framework is uniformly applied to fixed-priority and dynamic-priority systems and can handle, tasks with arbitrary relative deadlines and execution time distributions.

The exact stochastic analysis of most real-time systems is becoming unaffordable in current practice. On one side, the exact calculation of the response time distribution of the tasks is not possible except for simple periodic and independent task sets. On the other side, in practice, tasks introduce complexities like release jitter, blocking in shared resources, stochastic dependencies, etc, which can not be handled by the periodic and independent task set model. This paper introduces the concept of pessimism in the stochastic analysis of real-time systems in the following sense: the exact probability of missing any deadline is always lower than that derived from the pessimistic analysis. Therefore, if real-time constraints are expressed as probabilities of missing deadlines, the pessimistic stochastic analysis provides safe results. Some applications of the pessimism concept are presented. Firstly, the practical problems that arise in the stochastic analysis of periodic and independent task sets are addressed. Secondly, we extend to the stochastic case some well known techniques of the deterministic analysis, such as the blocking in shared resources, and the task priority assignment.

The utilization bound for real-time rate monotonic (RM) scheduling on uniprocessors is extended to multiprocessors with partitioning-based scheduling. This allows fast schedulability tests to be performed on multiprocessors and quantifies the influence of key parameters, such as the number of processors and task sizes on the schedulability of the system. The multiprocessor utilization bound is a function of the allocation algorithm, so among all the allocation algorithms there exists at least one allocation algorithm providing the minimum multiprocessor utilization bound, and one allocation algorithm providing the maximum multiprocessor utilization bound. We prove that the multiprocessor utilization bound associated with the allocation heuristic worst fit (WF) coincides with that minimum if we use Liu and Layland's bound (LLB) as the uniprocessor schedulability condition. In addition, we present a class of allocation algorithms sharing the same multiprocessor utilization bound which coincides with the aforementioned maximum using LLB. The heuristics first fit decreasing (FFD) and best fit decreasing (BFD) belong to this class. Thus, not even an optimal allocation algorithm can guarantee a higher multiprocessor utilization bound than that of FFD and BFD using LLB. Finally, the pessimism of the multiprocessor utilization bounds is estimated through extensive simulations.

This paper describes a stochastic analysis method for general periodic real-time systems. The proposed method accurately computes the response time distribution of each task in the system, thus making it possible to determine the deadline miss probability of individual tasks, even for systems with maximum utilization factor greater than one. The method uniformly covers both fixed-priority scheduling (such as rate monotonic) as well as dynamic-priority scheduling (such as earliest deadline first) and can handle arbitrary relative deadlines and execution time distributions. The accuracy of the method is proven by comparing the results from the analysis with those obtained from simulations, as well as other methodologies in the literature.

This paper deals with the problem of finding utilization bounds for multiprocessor rate monotonic scheduling with partitioning. The minimum and maximum utilization bounds among all the reasonable allocation algorithms are calculated. We prove that the utilization bound associated with the reasonable allocation heuristic Worst Fit (WF) is equal to that minimum. In addition, we prove that the utilization bound associated with the heuristics First Fit Decreasing (FFD) and Best Fit Decreasing (BFD) is equal to the maximum, of value (n+1)(2/sup 1/2/-1), where n is the number of processors.

Presents the utilization bound for earliest deadline first (EDF) scheduling on homogeneous multiprocessor systems with partitioning strategies. Assuming that tasks are pre-emptively scheduled on each processor according to the EDF algorithm, and allocated according to the first-fit (FF) heuristic, we prove that the worst-case achievable utilization is 0.5(n+1), where n is the number of processors. This bound is valid for arbitrary utilization factors. Moreover, if all the tasks have utilization factors under a value /spl alpha/, the previous bound is raised, and the new utilization bound considering /spl alpha/ is calculated. In addition, we prove that no uniprocessor scheduling algorithm/allocation algorithm pair can provide a higher worst-case achievable utilization than that of EDF-FF. Finally, simulation provides the average-case achievable utilization for EDF-FF.