Modern data centers feature an extensive array of cores that handle quite a diverse range of jobs. Recent traces, shared by leading cloud data center enterprises like Google and Alibaba, reveal that the constant increase in data center services and computational power is accompanied by a growing variability in service demand requirements. The number of cores needed for a job can vary widely, ranging from one to several thousands, and the number of seconds a core is held by a job can span more than five orders of magnitude. In this context of extreme variability, the policies governing the allocation of cores to jobs play a crucial role in the performance of data centers. It is widely acknowledged that the First-In First-Out (FIFO) policy tends to underutilize available computing capacity due to the varying magnitudes of core requests. However, the impact of the extreme variability in service demands on job waiting and response times, that has been deeply investigated in traditional queuing models, is not as well understood in the case of data centers, as we will show. To address this issue, we investigate the dynamics of a data center cluster through analytical models in simple cases, and discrete event simulations based on real data. Our findings emphasize the significant impact of service demand variability, both in terms of requested cores and service times, and allow us to provide insight for enhancing data center performance. In particular, we show how data center performance can be improved thanks to the control of the interplay between service and waiting times through the assignment of cores to jobs.

Round robin (RR) is a widely adopted scheduling policy in modern computer systems. The scheduler handles the concurrency by alternating the run processes in such a way that they can use the processor continuously for at most a quantum of time. When the processor is assigned to another process, a context switch occurs. Although modern architectures handle context switches quite efficiently, the processes may incur in some indirect costs mainly due to cache overwriting.

In the last years, blockchains have become a popular technology to store immutable data validated in a peer-to-peer way. Software systems can take advantage of blockchains to publicly store data (organised in transactions) which is immutable by design. The most important consensus algorithm in public blockchains is the proof-of-work in which miners invest a huge computational power to consolidate new data in a ledger. Miners receive incentives for their work, i.e., a fee decided and paid for each transaction. Rational miners aim to maximise the profit generated by the mining activity, and thus choose the transactions offering the highest fee per byte for their consolidation. In this paper, we propose a queueing model to study the relation between the fee offered by a transaction and its expected consolidation time, i.e., the time required to be added to the blockchain by the miners. The solution of the queueing model, although approximate, is computationally and numerically efficient and software systems can use it online to analyse the trade-off between costs and response times. Indeed, a static configuration of the model would not account for the high variations in the blockchain workload and fees offered by other users.

We model networks of Energy Packets which have been previously introduced by Gelenbe and his colleagues to represent the interactions between communication units and energy units in data processing networks with energy harvesting. We consider failures of batteries and the network structure models the connectivity. The model explicitly represents the amount of Energy Packets needed to transfer a Data Packet. We consider both Data Packets and Jumbo Data Packets which require distinct amounts of energy to be transmitted. Unlike previous models, our approach is based on the assumption that the transmission time of a Data Packet can be neglected when we model Energy Packets harvesting and Leakage which are operating on a larger time scale. We prove that the network of queues associated with the batteries has a product form steady-state distribution under usual Markovian assumptions. An important feature of our model is the ability to study Data Packet losses due to the lack of energy at certain nodes or to the failure of the components which cannot be obtained in previous models with closed form solutions.

Stochastic Petri nets are an important formalism for performance evaluation of telecommunication systems and computer hardware and software architectures whose underlying process is a Continuous Time Markov Chain. In practice, performance evaluation based on Petri net models suffers the problem of state space explosion which makes exact analyses computationally prohibitive and hence practitioners usually resort to simulation. In this paper we propose an algorithm for perfect sampling in stochastic Petri nets whose transitions have single or infinite server semantics. Obtained samples are distributed according to stationary distribution of the net, allowing for running of stationary simulations without warm up period by starting a simulation run from an obtained sample. We implement coupling from the past -- an algorithm for perfect sampling of discrete time Markov chains -- to sample from the stationary probability distribution of the stochastic process underlying the Petri net. We study the performance of the algorithm under different scenarios.

A large class of modern servers are capable of providing services with different levels of quality. In general, more accurate output requires longer computation time, allowing the trade-off between quality of service and expected response time. In order to model a self-adaptive system that employs dynamic control of the quality of service, we study a queueing system with C classes of service, each of which is characterised by a quality of service and an expected service time. The routing of customers to classes occurs at the customer arrival epoch and depends on the number of customers in the system -- specifically, on C -- 1 thresholds that are parameters of the system. We aim at finding the values for these thresholds that maximise a reward function which we define based on the quality of provided service and expected response time. Differently from previous work, we consider processor sharing queueing discipline. We find the exact solution of the underlying Markov chain based model to be computationally too expensive for the purpose of maximising the reward function in a self-adaptive manner, and propose an approximate model which we use to maximise the reward function using deepest descent search.

Modern computer systems consist of a large number of dynamic hardware and software components that interact according to some specific rules. Quantitative models of such systems are important for performance engineering because they allow for an earlier prediction of the quality of service. The application of stochastic modelling for this purpose is limited by the problem of the explosion of the state space of the model, i.e. the number of states that should be considered for an exact analysis increases exponentially and is thus huge even when few components are considered. In this paper we resort to product-form theory to deal with this problem. We define an iterative algorithm with the following characteristics: a) it deals with models with infinite state space and block regular structure (e.g. quasi-birth&death) without the need of truncation; b) in case of detections of product-form according to RCAT conditions, it computes the exact solution of the model; c) in case of non-product-form, it computes an approximate solution. The very loose assumptions allow us to provide examples of analysis of heterogeneous product-form models (e.g., consisting of queues with catastrophes and/or batch removals) as well as approximating non-product-form models with non-exponential service time distributions and negative customers.

Performance engineering plays a pivotal role in the successful design of software system and the software development process. Stochastic modelling has been widely applied to predict and evaluate or estimate system performance. We consider the specification of models in terms of compositions of simpler components and their efficient solution. Various formalisms or classes of stochastic models have been applied for system performance engineering and evaluation. These formalisms includes queueing networks, Stochastic Petri Nets, and Stochastic Process Algebras. Their dynamic behaviour can be usually represented by an underlying stochastic (Markov) process. For each formalism some classes of product-form models have been identified, starting from the first remarkable results for BCMP queueing networks. For some product-form models various efficient algorithms have been defined. We discuss the problem of identifying and characterize classes of product-form models. We compare the properties of the various modeling formalisms, their solution and the combination of product-form (sub)models into a heterogeneous model. We illustrate the application of product-form stochastic models for system performance engineering with some examples of tools for the solution of heterogeneous models formed by synchronized sub-models, and some practical applications.

In queueing networks with blocking, stations wishing to transmit customers to a full queue are blocked and need to take alternative action on completing a service. In general, product-forms, i.e. separable solutions for such a network's equilibrium state probabilities, do not exist but some product-forms have been obtained over the years in special cases, using a variety of techniques. We show that the Reversed Compound Agent Theorem (RCAT) can obtain these diverse results in a uniform way by its direct application, so unifying product-forms in networks with and without blocking. New product-forms are also constructed for a type of blocking we call `skipping', where a blocked station sends its output-customers to the queue after the one causing the blocking in that customer's path. Finally, we investigate a novel congestion management scheme for networks of finite-capacity queues in which a station with a full queue transmits signals that delete customers from upstream queues in order to reduce incoming traffic.

In this paper we study product-form conditions for generalized stochastic Petri net models. We base our results on the reversed compound agent theorem (RCAT) that has been recently formulated in the stochastic process algebra research field. In previous works, we defined finite structured GSPN models equivalent to BCMP service stations. In this paper we prove the conditions under which it is possible to combine those GSPN models with other ones whose underlying stochastic processes satisfy RCAT conditions. Finally, we present a practical application which exhibits a product-form solution based on these new results and previous ones which were based on the M rArr M property. From a theoretical point of view, the results point out new relations among product-form model classes. As a practical consequence we have a possible definition of a hybrid formalism modelling tool that can identify product-forms.

Over the last decade, a lot of research has been directed toward integrating performance analysis into the software development process. Traditional software development methods focus on software correctness, introducing performance issues later in the development process. This approach does not take into account the fact that performance problems may require considerable changes in design, for example, at the software architecture level, or even worse at the requirement analysis level. Several approaches were proposed in order to address early software performance analysis. Although some of them have been successfully applied, we are still far from seeing performance analysis integrated into ordinary software development. In this paper, we present a comprehensive review of recent research in the field of model-based performance prediction at software development time in order to assess the maturity of the field and point out promising research directions.

Quantitative performance analysis of software systems should be integrated in the software development process from the early stages. Software performance modelling and analysis allows the software designer to address performance related issues such as the comparison of design alternatives. Software performance modeling based on simulation models allows the analyst to represent detailed characteristics of the system and makes it easier the integration of the performance model with the software specification model. We propose simulation-based performance modeling of software architectures specified in UML. We argue that simulation-based performance models are well suited for capturing the complex aspects and behaviors of software systems. We propose a methodology for deriving a simulation model from annotated UML software architectures. We introduce the annotation for some UML diagrams, i.e., Use Case, Activity and Deployment diagrams, to describe system performance parameters. Then we show how to derive a discrete-event simulation model by automatically extracting information from the UML diagrams. Simulation provides performance results that are reported into the UML diagrams as tagged values. The proposed methodology has been implemented into a prototype tool called SAPS (Software Architectures Performance Simulator). We describe an application example of the proposed methodology. Keywords Software Performance Models, Discrete-Event Simulation, Unified Modeling Language (UML). 1

Systems of heterogeneous parallel processing are studied such as arising in parallel programs executed on distributed systems. A lower and an upper bound model are suggested to obtain secure lower and upper bounds on the performance of these systems. The bounding models are solved by using a matrix-geometric algorithmic approach. Formal proofs of the bounds are provided along with error bounds on the accuracy of the bounds. These error bounds in turn are reduced to simple computational expressions. Numerical results are included. The results are of interest for application to arbitrary fork-join models with parallel heterogeneous processors and synchronization.

The authors investigate dynamic transaction routing strategies for locally distributed database systems in which the database is partitioned and distributed among multiple transaction-processing systems, and the incoming transactions are routed by a common front-end processor. If a transaction issues a database request referencing a nonlocal database partition, the request has to be shipped to the system owing the referenced partition for processing. Various dynamic strategies are studied. Their performance is compared with that of the optimal static strategy. A class of dynamic transaction routing strategies which take into account routing history and minimize the estimated response time of incoming transactions is proposed; they are found to provide a substantial improvement over the optimal static strategy. The robustness of the strategies is further studied through sensitivity analysis over various transaction loads, communication overheads, and database reference distributions.>

The mathematics of product-form queueing networks has traditionally dealt with the "analysis" of computer systems. That is, the system is assumed to be given and the question of how it performs is answered. In this paper the opposite process of system "synthesis" is dealt with: i.e., we answer the question of what the system topology and parameters should be in order to achieve a given performance objective. Possible research and industry applications range from the hierarchial top-down design of software systems to the management and design of computer installations.

Given a closed BCMP queueing network, the problem is considered of studying the behavior of any subsystem a without solving for the entire system. This paper proves that this is possible for a consisting of any number of queues, arbitrarily interfacing the rest of the system, thus generalizing the classic CHW theorem, also known as Norton's theorem. A general flow-equivalent solution procedure is given and its computational complexity is compared with that of the product-form and the exact aggregation procedure. The relative merits of these procedures are also expressed in terms of a's cardinality.