The on-demand activation of frequency bands in radio access networks can lead to a significant reduction of energy consumption, but risks to adversely impact performance. This approach to frequency band management can be applied either to a group of co-located base stations whose operators adopt a network sharing approach or to a single base station that uses multiple frequency bands. We develop a stochastic model based on the Matrix Analytic Method for the quantification of system performance and energy consumption in the case of coexisting streaming and elastic services. By computing numerical results in a specific setting, we show that the on-demand (de)activation, possibly combined with the adaptation of the data rate of streaming services, succeeds in greatly reducing energy consumption with respect to the case in which frequency bands are always active, with limited impact on the performance experienced by users. We also show that the introduction of a hysteresis in the frequency band activation/deactivation process allows the optimization of the energy/performance trade-off. Finally, we show that performance is not drastically altered by the burstiness of the elastic service request arrival process, and we prove that the separate analysis of streaming and elastic services provides quite optimistic results with respect to the joint analysis made possible by our model.

The efficient execution of data center jobs that require simultaneous use of different resource types is of critical importance. When processing capacity is the crucial resource for jobs execution, the locution multiserver jobs is used, where the term server indicates processors or CPU cores providing processing capacity. Each multiserver job carries a requirement expressed in number of servers it requires to run, and service duration. Achieving efficient execution of multiserver jobs relies heavily on effective scheduling of jobs on the existing servers. Several schedulers have been proposed, aimed at improving resource utilization, at the cost of increased complexity. Due to the limited availability of theoretical results on scheduler behavior in the case of multiserver jobs, data center schedulers are often designed based only on managers' experience. In this paper, aiming to expand the understanding of the multiserver job schedulers' performance, we study Small Shuffle (SMASH) schedulers, a class of nonpreemptive, service time oblivious, window-based multiserver job scheduling algorithms that strike a balance between simplicity and efficient resource utiliza tion, while allowing performance evaluation in simpler settings. SMASHimplies only a marginal increase in complexity compared to FIFO, yet it delivers substantial performance improvements for multiserver jobs. Depending on the system parameters, SMASH can nearly double the system's stability region with respect to FIFO, leading to significantly lower response times across a broad region of loads. Moreover, the magnitude of this improvement scales with the chosen window size, allowing performance to be tuned to the system's operating conditions. We first study the capacity of SMASH with analytical tools in simple settings, then we investigate the performance of SMASH and other schedulers with simulations under more realistic workloads, designed with parameters derived from measurements of real data centers. Results show that SMASH offers a very good compromise between performance and complexity.

We study the combination of Active Queue Management (AQM) techniques and age-based scheduling disciplines to improve network performance in the Linux packet scheduler. While AQM algorithms like CoDel, FQ-CoDel, and PIE manage queue lengths and ensure fair bandwidth sharing, age-based scheduling (e.g., Least Attained Service, Two-Level Processor Sharing) reduces mean flow completion time by prioritizing short flows. While their individual benefits are known, the integration of these orthogonal features had not been analysed so far. We propose a hybrid queuing solution using standard Linux utilities (tc, nftables) tested with state-of-the art open source traffic generators to generate realistic Pareto-distributed traffic. Our experiments on $1 \mathrm{~Gb} / \mathrm{s}$ and $10 \mathrm{~Gb} / \mathrm{s}$ links demonstrate that implementing age-based scheduling policies on top of AQM strategies significantly reduces flow completion time, with gains ranging from 3% to 20%. These improvements are achieved without increasing CPU load and while preserving or improving fairness among flows. The solution is easily implementable on any recent Linux kernel, and we provide all the code we realized to replicate and improve our results.

The Multiserver Job Queuing Model (MJQM) is a queuing system that plays a key role in the study of the dynamics of resource allocation in data centers. The MJQM comprises a waiting line with infinite capacity and a large number of servers. In this paper, we look at the limiting case in which the number of servers is infinite. Jobs are termed “multiserver” because each one is characterized by a resource demand in terms of number of simultaneously used servers and by a service duration. Job classes are defined by collecting all jobs that require the same number of servers. Job service times are independent and identically distributed random variables whose distributions depend on the class of the job. We consider the case of only two job classes: “small” jobs use a fixed number of servers, while “big” jobs use all servers in the system. The service discipline is First-In First-Out (FIFO). This means that if the job at the Head-of-Line (HOL) cannot enter service because the number of free servers is not sufficient to meet the job requirement, it blocks all subsequent jobs, even if there are sufficient free servers for them. Despite its importance, only few results exist for the MJQM, whose analysis is challenging, especially because the MJQM is not work-conserving. This implies that even the stability region of the MJQM is known only in special cases. In a previous work, we obtained a closed-form stability condition for MJQM with big and small jobs under the assumption of exponentially distributed service times for small jobs. In this paper, we compute the stability condition of MJQM with an infinite number of servers processing big and small jobs, considering different distributions of the service times of small jobs. Simulations are used to support the analytical results and to investigate the impact of service time distributions on the average job waiting time before saturation.

Datacenters comprise a variety of resources (processors, memory, input/output modules, etc.) that are shared among requests for the execution of computing jobs submitted by datacenter users. Jobs differ in their frequency of arrivals, demand for resources, and execution times. Resource sharing generates contention, especially in heavily loaded systems, that must therefore implement effective scheduling policies for incoming jobs. The First-In First-Out (FIFO) policy is often used for batch jobs, but may produce under-utilization of resources, in terms of wasted servers. This is due to the fact that a job that requires many resources can block jobs arriving later that could be served because they require fewer resources. The mathematical construct often used to study this problem is the Multiserver Job Queuing Model (MJQM), where servers represent resources which are requested and used by jobs in different quantities. Unfortunately, very few explicit results are known for the MJQM, especially at realistic system loads (i.e., before saturation), and hardly any considers the case of non-exponential service time distributions. In this paper, we propose the first exact analytical model of the non-saturated MJQM in case of two classes of customers with service times having 2-phase Coxian distribution. Our analysis is based on the matrix geometric method. Our results provide insight into datacenter dynamics, thus supporting the design of more complex schedulers, capable of improving performance and energy consumption within large datacenters.

Queuing networks with finite capacity are widely discussed in performance analysis literature. One approach to address the finite capacity of stations involves the implementation of a skip-over policy. Under this policy, when a customer arrives at a saturated station, service at that station is skipped, and the customer is rerouted based on the predefined network routing protocol. Skip-over networks have been extensively investigated, and they exhibit a product-form stationary distribution under the exponential assumptions of Jackson networks. However, a comprehensive understanding of the celebrated Arrival Theorem for this class of product-form models is still lacking and relies on certain conjectures. This paper makes three contributions: (i) it provides an in-depth comprehension of the Arrival Theorem for skip-over networks by offering a proof for the conjectures outlined in existing literature, (ii) it introduces a Mean Value Analysis (MVA) algorithm tailored for this type of queuing networks, and (iii) it explores the implications of these findings on the class of product-form queuing networks with fetching and repetitive service discipline.

In this paper, we present the first remote timing attack based on formal stochastic models. Our attack uses queuing models from the field of performance evaluation to estimate the service times of different classes of network requests. By using Bayesian statistics, we then identify opportunities for remote timing attacks by answering the following inverse question: what is the probability that a given network request belongs to a target class, given an estimate of its service time? Our experimental evaluation on popular web applications and websites shows that our investigation is not just a theoretical exercise, because our attack outperforms existing empirical approaches in terms of standard performance figures. We believe that the formal foundations put forward in this paper can be successfully applied to the creation of principled remote timing attacks which are more effective, because better equipped to deal with the complexity of the problem they are trying to solve.

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.

Cloud computing has revolutionized how computational resources are accessed and utilized. However, the dynamic nature of the cloud computing environment, which is characterized by a variety of resource types and capabilities presents challenges for managing the workload and ensuring the quality of service. The selection and implementation of queueing policies can have a major impact on the efficiency of the cloud environment, and thus on the quality of service experienced by the end users. Understanding the performance metrics of different queueing policies in cloud computing environments with scalable resource management is essential for both cloud service providers and consumers. In response to this, our work aims to evaluate the effectiveness of some queueing policies in cloud environments characterized by dynamic resource allocation with a particular emphasis on their dropping probabilities. We proposed a simulation approach that combines the development of an accurate simulation model of a cloud computing environment with adaptable resource management, along with a comprehensive performance analysis of different queueing policies including First-Come-First-Serve and Priority queueing. The result revealed that assigning priority to jobs with longer service times and larger resource demands has a positive impact on small jobs as well.

Datacenters comprise large quantities of processors, memory, and input/output modules. These resources are shared among requests (jobs) submitted by datacenter users. Jobs differ in their frequency of arrivals, demand for resources, and execution times. Resource sharing generates contention, especially in heavily loaded systems, that must therefore implement effective scheduling policies for incoming jobs. The First-In First-Out (FIFO) policy is often used for batch jobs, but may produce under-utilization of resources, in terms of wasted servers. This is due to the fact that a job that requires many resources can block jobs arriving later that could be served because they require fewer resources. The mathematical construct often used to study this problem is the Multiserver Job Queuing Model (MJQM), where servers represent resources which are requested and used by jobs in different quantities. Unfortunately, very few explicit results are known for the MJQM, especially at realistic system loads (i.e., before saturation). In this paper, we propose the first exact analytical model of the non-saturated MJQM in case of two classes of customers with exponentially distributed service times and an arbitrary number of identical servers. Our analysis is based on the matrix geometric method. Our results provide insight into datacenter dynamics, thus supporting the design of more complex schedulers, capable of improving performance and energy consumption within large datacenters.

Blockchain technology has experienced significant advancements, with Proof-of-Stake emerging as a notable alternative to traditional Proof-of-Work blockchains. Among various PoS blockchain systems, Cosmos stands out as a prominent example due to its ecosystem designed to facilitate interoperability between different blockchains built on their platform through the Inter-Blockchain Communication protocol. What is more, Cosmos is operated by the unique consensus mechanism, namely CosmosBFT that supports multiple rounds for an agreement on block of the same height. This study examines the current state of blockchains within the Cosmos ecosystem, highlighting two major issues. First, we observe the multi-round performance in Cosmos blockchain using the process algebra tool to create our model featured non-homogeneous proposers. Second, we propose a method for determining optimal timeouts for the Propose step in any network within the ecosystem. In addition, we identify a skewed distribution of voting power among validators, favouring top-ranked members. This concentration of VP threatens the network’s decentralisation and immutability, as it allows a small group of members to potentially corrupt the consensus process. Our models, although parameterised for a particular Cosmos instance, are applicable to any blockchain that use the CometBFT protocol, offering valuable insights for enhancing efficiency of consensus mechanisms in the decentralised networks.

We consider an access link carrying data generated by streaming and elastic services requested by fixed or mobile end users, and subjected to an admission control (AC) algorithm. For the performance analysis of such link we develop a new queuing model and we show that, with the considered AC, the queuing model admits a product form expression for the joint limiting probability distribution of the numbers of active services of the different types. In addition, we prove that, when mobility can be neglected, i.e., in the case of either fixed access or slow mobility, the queuing model is insensitive to the distribution of the amount of data to be transferred for the fulfilment of the different service requests. Numerical results show unexpected oscillating behaviors for several performance metrics, and provide interesting insight into the link performance.

In blockchain networks driven by Proof of Work, clients spend a certain amount of cryptocurrency (called fees) to control the speed of confirmation of the transactions that they generate. In fact, transactions are confirmed according to a strong priority policy that favours those offering the highest fees. The problem of determining the optimal fee to offer to satisfy certain delay requirements is still widely open and, at the state of the art, mainly reactive methods based on historical data are available. In this work, we propose a queueing model based on the exact transient analysis of a M/MB/1 system to address this problem. The model takes into account (i) the state of the Mempool (the backlog of pending work) when the transaction is generated, (ii) the current transaction arrival intensity and (iii) the distribution of the fees offered by other transactions to the miners. We apply the model to study the performance of the Bitcoin blockchain. Its parameterisation is based on an extensive statistical analysis of the transaction characteristics. To this aim, we collected data from over 1.5 million of pending transactions observed in the Mempool of our Bitcoin node. The outcome of our analysis allows us to provide an algorithm to quickly compute the expected transaction confirmation time given the blockchain state, and to highlight new insights on the relations between the transaction fees and confirmation time in BTC blockchain.

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.

We consider an access link of a data network loaded with data flows generated by streaming and elastic services requested by fixed or mobile end users, and subjected to an admission control (AC) algorithm. For the performance analysis of such link we develop a new queuing model and we show that, with the considered AC, the queuing model admits a product form expression for the joint limiting probability distribution of the numbers of active services of the different types. Numerical results show unexpected oscillating behaviors for several performance metrics, and provide interesting insight into the link performance.

Abstract In this paper, we deal with the lumpability approach to cope with the state space explosion problem inherent to the computation of the stationary performance indices of large stochastic models. The lumpability method is based on a state aggregation technique and applies to Markov chains exhibiting some structural regularity. Moreover, it allows one to efficiently compute the exact values of the stationary performance indices when the model is actually lumpable. The notion of quasi-lumpability is based on the idea that a Markov chain can be altered by relatively small perturbations of the transition rates in such a way that the new resulting Markov chain is lumpable. In this case, only upper and lower bounds on the performance indices can be derived. Here, we introduce a novel notion of quasi-lumpability, named proportional lumpability, which extends the original definition of lumpability but, differently from the general definition of quasi-lumpability, it allows one to derive exact stationary performance indices for the original process. We then introduce the notion of proportional bisimilarity for the terms of the performance process algebra PEPA. Proportional bisimilarity induces a proportional lumpability on the underlying continuous-time Markov chains. Finally, we prove some compositionality results and show the applicability of our theory through examples.

Simulations for network implementations are an essential component for developing newer and better network solutions and protocols, especially when considering complex scenarios. For instance, networks composed of flying objects coordinating through multi-hop communication represent a foreseeable scenario in our society. The need for analyzing new and tailored solutions for this visionary context passes through the creation of specific tools. To this aim, we present here a novel discrete event simulator deployed to test Flying Ad-Hoc Networks (FANETs) and, in particular, their routing algorithms. In our simulator we have also implemented two different position-based routing protocols for FANETs; their implementation and results are discussed as well.

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.

In this paper, we study an information flow security property for systems specified as terms of a quantitative Markovian process algebra, namely the Performance Evaluation Process Algebra (PEPA). We propose a quantitative extension of the Non-Interference property used to secure systems from the functional point view by assuming that the observers are able to measure also the timing properties of the system, e.g., the response time of certain actions or its throughput. We introduce the notion of Persistent Stochastic Non-Interference (PSNI) based on the idea that every state reachable by a process satisfies a basic Stochastic Non-Interference (SNI) property. The structural operational semantics of PEPA allows us to give two characterizations of PSNI: one based on a bisimulation-like equivalence relation inducing a lumping on the underlying Markov chain, and another one based on unwinding conditions which demand properties of individual actions. These two different characterizations naturally lead to efficient methods for the verification and construction of secure systems. A decision algorithm for PSNI is presented and an application of PSNI to a queueing system is discussed.

Size-based scheduling policies have been widely studied in the literature, and their interest in networking applications has been huge in the last decade. These policies consist in deciding the priority of the packets belonging to a certain flow based on the service time that the flow has received up to a certain epoch or, when possible, on the remaining service time. The scientific literature has devoted many efforts to the comparison and analysis of these disciplines either by simulation or by analytical models although real-world implementations can have different performance for numerous reasons. In this paper, we consider the two-level processor sharing discipline (2LPS), i.e., packets are served with high priority if they belong to a flow that has required less than a work up to that moment, where a is a threshold-parameter of the model. The goal is that of assessing the performance of this discipline once implemented in a real router with a real-world network traffic and compare these measurements with the performance indices obtained by the queueing model. To characterise the networks traffic, we fit two datasets with an acyclic phase-type distribution thanks to an existing tool and then transform the resulting distribution into a generalised hypergeometric distribution. Our experiments confirm that the 2LPS improves the flow expected response time with respect to the standard scheduling by taking advantage of the heavily tailed distribution characterising the TCP flow sizes, but this improvement seems slightly smaller than what predicted by the analytical models.

We consider the scenario in which several TCP connections share the same access point (AP) and a congestion avoidance/control mechanism is adopted with the aim of assigning the available bandwidth to the clients with a certain fairness. When UDP traffic with real-time requirements is present, the problem becomes even more challenging. Very well-known congestion avoidance mechanisms are the Random Early Detection (RED) and the Explicit Congestion Notification (ECN). More recently, the Smart Access Point with Limited Advertised Window (SAP-LAW) has been proposed. Its main idea is that of computing the maximum TCP rate for each connection at the bottleneck, taking into account the UDP traffic to keep a low queue size combined with a reasonable bandwidth utilization. In this paper, we propose a new congestion control mechanism, namely, Smart-RED, inspired by SAP-LAW heuristic formula. We study its performance by using mean field models and compare the behaviours of ECN/RED, SAP-LAW, and Smart-RED under different scenarios. We show that while Smart-RED maintains some of the desirable properties of the SAP-LAW, it solves the problems it may have in case of bursty UDP traffic or TCP connections with very different needs of bandwidth.

In the last decade, underwater wireless sensor networks (UWSNs) have attracted a lot of attention from the research community thanks to their wide range of applications that include seabed mining, military and environmental monitoring. With respect to terrestrial networks, UWSNs pose new research challenges such as the three-dimensional node deployment and the use of acoustic signals. Despite the large number of routing protocols that have been developed for UWSNs, there are very few analytical results that study their optimal configurations given the system's parameters (density of the nodes, frequency of transmission, etc.). In this paper, we make one of the first steps to cover this gap. We study an abstraction of an opportunistic routing protocol and derive its optimal working conditions based on the network characteristics. Specifically, we prove that using a depth threshold, i.e., the minimum length of one transmission hop to the surface, is crucial for the optimality of opportunistic protocols and we give a numerical method to compute it. Moreover, we show that there is a critical depth threshold above which no packet can be transmitted successfully to the surface sinks in large networks, which further highlights the importance of properly configuring the routing protocol. We discuss the implications of our results and validate them by means of stochastic simulations on NS3.

Active Queue Management (AQM) techniques have been proposed to support scenarios with many connections sharing the same bottleneck. The basic idea is that a smart management of the bottleneck queue can avoid the saturation of the link and ensure a smoother use of the available bandwidth. This is generally achieved by exploiting the flux control mechanism of TCP and its behavior in case of packet losses or other explicit notifications. In this paper we consider classic and innovative AQM techniques and analyse their performance under different scenarios through the use of mean field models.

Probabilistic I/O automata (PIOAs) provide a modelling framework that is well suited for describing and analyzing distributed and concurrent systems. They incorporate a notion of probabilistic choice as well as a notion of composition that allows one to construct a PIOA for a composite system from a collection of simpler PIOAs representing the components. Differently from other probabilistic models, the local actions of a PIOA are associated with time delays governed by independent random variables with continuous-time exponential distributions. The contribution of this paper consists in studying the product-form property for PIOAs. Our main result is the formulation of a theorem giving sufficient conditions for a composition of PIOAs to be in product-form and hence to efficiently compute its stationary probabilities.

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.

In this paper we propose a new model for the analysis of systems with aging objects such as Time-To-Live cache. We consider a model with an underlying Continuous Time Markov Chain in which objects can be completely or partially rejuvenated. In the former case the object becomes fresh, while in the latter all the objects are simultaneously rejuvenated so that the youngest becomes fresh. We show that under the so-called Independent Reference Model assumption our model is numerically tractable and has a product-form equilibrium distribution. Furthermore, we consider the case in which the object aging stops after a certain threshold and hence the partial rejuvenation introduces a probabilistic behaviour. Also in this case, we can derive a product-form equilibrium distribution under some mild conditions. The models presented in this paper may be interpreted as a new class of G-networks with catastrophes and partial flushing.

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.

In the literature devoted to the efficient solution of Continuous Time Markov Chains (CTMCs) the notions of lump ability and reversibility have a central role. In the context of lump able Markov chains several definitions have been introduced: strong, exact and strict, just to mention a few of them. On the side of the analysis of reversible CTMCs the research community has shown great interest in the application of this notion with the aim of efficiently computing the stationary distribution of large models (e.g., obtained by composition of several processes). In this paper we show for the first time the relations between the above mentioned notions of lump ability and the concept of reversibility. The major outcome of our research is proving a strong connection between the notion of strict lump ability and that of reversibility.

A new algorithm is given to find product-form solutions for the joint equilibrium probabilities in a class of synchronized Markov processes. This is based on, and proved by, multiple applications of the Reversed Compound Agent Theorem (RCAT) and can describe multi-way synchronizations (seen as chains of pairwise synchronizations) that occur in a prescribed order. The length of the sequence is unbounded but finite with probability 1. Several applications are given to illustrate the methodology, which include various modes of resets in queueing networks with negative customers. In particular, it is shown that there is a type of reset that can propagate further transitions in a chain actively. Furthermore, a number of completely new product-form models, for example, where the transitions in a chain are non-homogeneous, are given.

The computation of the steady-state distribution of Continuous Time Markov Chains (CTMCs) may be a computationally hard problem when the number of states is very large. In order to overcome this problem, in the literature, several solutions have been proposed such as the reduction of the state space cardinality by lumping, the factorization based on product-form analysis and the application of the notion of reversibility. In this paper we address this problem by introducing the notion of auto reversibility which is defined as a symmetric co inductive relation which induces an equivalence relation among the chain's states. We show that all the states belonging to the same equivalence class share the same stationary probabilities and hence the computation of the steady-state distribution can be computationally more efficient. The definition of auto reversibility takes inspiration by the Kolmogorov's criteria for reversible processes and hence requires to test a property on all the minimal cycles of the chain. We show that the notion of auto reversibility is different from that of reversible processes and does not correspond to other state aggregation techniques such as lumping. Finally, we discuss the applicability of our results in the case of models defined in terms of a Markovian process Algebra such as the Performance Evaluation Process Algebra.

We present a framework for modelling ad-hoc Wireless Sensor Networks (WSNs) and studying both their connectivity properties and their performances in terms of energy consumption, throughput and other relevant indices. Our framework is based on a probabilistic process calculus where system executions are driven by Markovian probabilistic schedulers, allowing us to translate process terms into discrete time Markov chains (DTMCs) and use the probabilistic model checker PRISM to automatically evaluate/estimate the connectivity properties and the energy costs of the networks. To the best of our knowledge, this is the first work that proposes a unique framework for studying qualitative (e.g., by proving the equivalence of components or the correctness of a behaviour) and quantitative aspects of WSNs using a tool that allows both exact and approximate (via Monte Carlo simulation) analyses. We demonstrate our framework at work by considering different communication strategies based on gossip routing protocols, for a typical topology and a mobility scenario.

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.

Mobile ad-hoc and sensor networks play an important role in several application fields. The usage of wireless links and the node mobility make the networks prone to security attacks; among these, jamming attacks are insidious and they consist of one or more nodes continuously transmitting dummy packets to keep some wireless links busy. The goal is to destroy the network connectivity or highly reduce its throughput. In this paper we propose a probabilistic formal method, based on a process algebraic approach, targeted at the analysis of connectivity and the evaluation of interference in mobile networks. We show our framework at work on the analysis of an indoor wireless communication scenario.

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.

In the last few years several new results about product-form solutions of stochastic models have been formulated. In particular, the Reversed Compound Agent Theorem (RCAT) and its extensions play a pivotal role in the characterization of cooperating stochastic models in product-form. Although these results have been used to prove several well-known theorems (e.g., Jackson queueing network and G-network solutions) as well as novel ones, to the best of our knowledge, an automatic tool to derive the product-form solution (if present) of a generic cooperation among a set of stochastic processes, is not yet developed. In this paper we address the problem of solving the non-linear system of equations that arises from the application of RCAT. We present an iterative algorithm that is the base of a software tool currently under development. We illustrate the algorithm, discuss the convergence and the complexity, compare it with previous algorithms defined for the analysis of the Jackson networks and the G-networks. Several tests have been conducted involving the solutions of a (arbitrary) large number of cooperating processes in product-form by RCAT.