Skip to main content

About this book

This book constitutes the refereed proceedings of the 22nd International Conference on Analytical and Stochastic Modelling Techniques and Applications, ASMTA 2015, held in Albena, Bulgaria, in May 2015. The 15 full papers presented in this book were carefully reviewed and selected from numerous submissions. The papers discuss the latest developments in analytical, numerical and simulation algorithms for stochastic systems, including Markov processes, queueing networks, stochastic Petri nets, process algebras, game theory, etc.

Table of Contents


Optimal Analysis for M/G/1 Retrial Queue with Two-Way Communication

We consider an \(M/G/1\) retrial queue with two types of calls: incoming calls (regular one’s) and outgoing calls (which are made when the server is free). A blocked incoming call joins the orbit and retries for service after some random time while an outgoing call is made by the server after some random idle time. We assume that incoming and outgoing calls have random amount of works which are processed by the server at two distinct speeds. This assumption is suitable for evaluating the power consumption that depends on the speed of the server. We obtain the joint probability distribution of the server state and the number of requests in the orbit in terms of Laplace and \(z\)- transforms. From these transforms, we obtain some performance metrics of interest such as the probability that the server is idle or busy by an incoming (outgoing) call and the mean number of requests in orbit. We propose two optimization problems to find the optimal outgoing call rate and service speeds.
Amar Aissani, Tuan Phung-Duc

Use of Flow Equivalent Servers in the Transient Analysis of Product Form Queuing Networks

In this paper we deal with approximate transient analysis of Product Form Queuing Networks. In particular, we exploit the idea of flow equivalence to reduce the size of the model. It is well-known that flow equivalent servers lead to exact steady state solution in many cases. Our goal is to investigate the applicability of flow equivalence to transient analysis. We show that exact results can be obtained even in the transient phase, but the definition of the equivalent server requires the analysis of the whole original network. We propose thus to use approximate aggregate servers whose characterization demands much less computation. Specifically, the characterization corresponds to the steady state equivalent server of the stations that we aim to aggregate and thus can be achieved by analyzing the involved stations in isolation. This way, approximations can be derived for any queuing network, but the precision of the results depends heavily on the topology and on the parameters of the model. We illustrate the approach on numerical examples and briefly discuss a set of criteria to identify the cases when it leads to satisfactory approximation.
Alessio Angius, András Horváth, Sami M. Halawani, Omar Barukab, Ab Rahman Ahmad, Gianfranco Balbo

Model Checking of Open Interval Markov Chains

We consider the model checking problem for interval Markov chains with open intervals. Interval Markov chains are generalizations of discrete time Markov chains where the transition probabilities are intervals, instead of constant values. We focus on the case where the intervals are open. At first sight, open intervals present technical challenges, as optimal (min, max) value for reachability may not exist. We show that, as far as model checking (and reachability) is concerned, open intervals does not cause any problem, and with minor modification existing algorithms can be used for model checking interval Markov chains against PCTL formulas.
Souymodip Chakraborty, Joost-Pieter Katoen

Performance Modeling of Cellular Systems with Finite Processor Sharing Queues in Random Environment, Guard Policy and Flex Retrial Users

We investigate a two-station retrial queueing system to model the access in modern cellular networks managed by two service providers. Each provider owns a single access point, which operates under processor sharing discipline, and accepts three types of users: the handover users and, the originating subscribers and the originating flex users. At the arrival epoch, a flex user connects with the provider, which offers the largest data rate. Each access point can admit a limited number of users and employ a guard bandwidth policy in order to prioritize the handover users. Both blocked handover and originating subscriber users are lost. Blocked flex users join a virtual orbit queue of infinite capacity from where they retry independently to connect with the service provider that offers the largest data rate at their retrial time. Moreover, the system operates in varying environmental conditions. Using the matrix analytic formalism we construct a four-dimensional Markovian model, which allows to represent accurately the types of user behavior and the environmental aspects in cellular networks. We perform a steady-state analysis and a study of the main performance metrics.
Ioannis Dimitriou

Efficient Performance Evaluation of Wireless Networks with Varying Channel Conditions

This paper investigates the performance of opportunistic schedulers in wireless networks. A base station communicates over fading channels with multiple mobile nodes, each experiencing varying and not necessarily identical wireless channel conditions. An opportunistic scheduler optimises performance by accounting for both buffer size as well as channel conditions when allocating the transmitter energy among its users. The present study provides the necessary analytical tools to assess performance of opportunistic schedulers both fast and accurately, thereby allowing for fast evaluation and comparison of scheduling algorithms. The scheduler is modelled as a Markovian queueing system with multiple finite queues in a random environment. Already for a limited number of users and limited buffer capacities, the size of the state space of the Markov model makes the direct calculation of the steady-state probability vector nearly impossible. Therefore, we rely on Maclaurin series expansions so as to study the scheduler under light traffic conditions as well as in overload. The computational complexity for calculating the first \(N\) terms in the series expansions is \(O(NM^2S)\), where \(M\) is the size of the state space of the exogenous channel process and \(S\) is the size of the state space of the entire Markov chain.
Ekaterina Evdokimova, Koen De Turck, Sabine Wittevrongel, Dieter Fiems

Mixed Networks with Multiple Classes of Customers and Restart

We consider a network of queues with multiples classes of customers and restart signals. A restart signal makes a customer in the queue change its class and restart to the first step of service. The queues which receive signals can have an infinite server or a processor sharing discipline. The service time distributions are hyper-exponential, which can have high variance and are realistic for many real-world applications, such as transmission times over the internet. For distributions with large variability the restart mechanism can be useful. We prove that, under ergodicity condition, such a model has a product form steady-state distribution. This model contains two original features which were previously not allowed in a network of queues with negative customers: a part of the network is closed and some stations are Infinite Server queues.
Jean-Michel Fourneau, Katinka Wolter

Interconnected Wireless Sensors with Energy Harvesting

This paper studies interconnected wireless sensors with the paradigm of Energy Packet Networks (EPN) which were previously introduced. In the EPN model, both data transmissions and the flow of energy are discretized, so that an energy packet (EP) is the minimum amount of energy (say in microjules) that is needed to process and transmit a data packet (DP) or to process a job. Previous work has modeled such systems to determine the relation between energy flow and DP transmission, or to study the balance between energy and the processing of jobs in Cloud Servers. The lack of energy, in addition to processing times, is the main source of latency in networks of sensor nodes. Thus this paper models this phenomenon, and shows that under some reasonable conditions, assuming feedforward flow of data packets and local consumption and leakage of energy, such networks have product form solutions.
Erol Gelenbe, Andrea Marin

Measuring the Distance Between MAPs and Some Applications

This paper provides closed form expressions for the squared distance between the joint density functions of \(k\) successive inter-arrival times of two MAPs. The squared distance between the autocorrelation functions of two MAPs is expressed in a closed form as well.
Based on these results a simple procedure is developed to approximate a RAP by a MAP, in order to reduce the number of phases or to obtain a Markovian representation.
Gábor Horváth

Task Delegation in a Peer-to-Peer Volunteer Computing Platform

The paper reports an effort made for understanding the effect of task delegation policy in a peer-to-peer volunteer computing platform. This effort includes the implementation of a simulation environment and the development of associated analytical models for the analysis of task delegation policies in peer-to-peer computing platforms. Based on the analytical model best and worst task delegation policies are computed and the resulted system behavior is verified by simulation.
Kristóf Attila Horváth, Miklós Telek

On Convergence Rate to Stationarity of Queues with General Gaussian Input

The paper studies the rate of convergence to stationarity of the fluid queueing system with a constant service rate which is fed by a Gaussian process with stationary increments. It is assumed that variance of the input process is regularly varying with index \(2H\in (1,\,2)\). It is proved that the convergence rate is exactly the same that has been obtained for the fluid system fed by the corresponding fractional Brownian motion.
Oleg Lukashenko, Evsey Morozov

Model-Based Quantitative Security Analysis of Mobile Offloading Systems Under Timing Attacks

Mobile offloading systems have been proposed to migrate complex computations from mobile devices to powerful servers. While this may be beneficial from the performance and energy perspective, it certainly exhibits new challenges in terms of security due to increased data transmission over networks with potentially unknown threats. Among possible security issues are timing attacks which are not prevented by traditional cryptographic security. Metrics on which offloading decisions are based must include security aspects in addition to performance and energy-efficiency. This paper aims at quantifying the security attributes of mobile offloading systems. The offloading system is modeled as a stochastic process. The security quantification analysis is carried out for steady-state behaviour as to optimise a combined security and cost trade-off measure.
Tianhui Meng, Qiushi Wang, Katinka Wolter

Single-Server Systems with Power-Saving Modes

Vacations queues are motivated from the need of utilizing the server when it is idle. Most of papers in the literature assume that consecutive vacations follow the same distribution. Recently, Ibe et al. [5] consider a model where the lengths of consecutive vacations follow different distributions and obtain the steady state solution by a direct method. In this paper, we first consider the same model and obtain exact results as well as the decomposition for the queue length and the sojourn time via a generating function approach. We then demonstrate that our method can analyze more complex models with working vacations or with abandonment. Numerical results show insights into the performance of single server systems with power-saving modes.
Tuan Phung-Duc

Multiserver Queues with Finite Capacity and Setup Time

Multiserver queues with setup time have been extensively studied because they have application in modelling of power-saving data centers. Although the infinite buffer models are extensively investigated, less attention has been paid to finite buffer models. This paper considers an M/M/\(c\)/\(K\) queue with setup time for which we suggest a simple and numerically stable recursion for the stationary distribution of the system state. Numerical experiments show various insights into the performance of the system such as performance-energy tradeoff as well as the effect of the capacity on the blocking probability and the mean queue length.
Tuan Phung-Duc

Power Consumption Analysis of Replicated Virtual Applications

The search for green IT has inspired a wide spectrum of techniques for power management. In a data center where computational power is provided by means of virtualised resources, like virtual machines, the policy to allocate them on physical servers can strongly impact the power consumption of the entire system. We propose a generalised stochastic Petri net model to investigate the contribution to energy efficiency due to different allocation and deallocation policies.
Pietro Piazzolla, Gianfranco Ciardo, Andrew Miner

On the Influence of High Priority Customers on a Generalized Processor Sharing Queue

In this paper, we study a hybrid scheduling mechanism in discrete-time. This mechanism combines the well-known Generalized Processor Sharing (GPS) scheduling with strict priority. We assume three customer classes with one class having strict priority over the other classes, whereby each customer requires a single slot of service. The latter share the remaining bandwith according to GPS. This kind of scheduling is used in practice for the scheduling of jobs on a processor and in Quality of Service modules of telecommunication network devices. First, we derive a functional equation of the joint probability generating function of the queue contents. To explicitly solve the functional equation, we introduce a power series in the weight parameter of GPS. Subsequently, an iterative procedure is presented to calculate consecutive coefficients of the power series. Lastly, the approximation resulting from a truncation of the power series is verified with simulation results. We also propose rational approximations. We argue that the approximation performs well and is extremely suited to study these systems and their sensitivity in their parameters (scheduling weights, arrival rates, loads ...). This method provides a fast way to observe the behaviour of such type of systems avoiding time-consuming simulations.
Jasper Vanlerberghe, Joris Walraevens, Tom Maertens, Herwig Bruneel


Additional information

Premium Partner

    Image Credits