Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2009 | Book

Tagged Generalized Stochastic Petri Nets Read chapter Read first chapter

Computer Performance Engineering

6th European Performance Engineering Workshop, EPEW 2009 London, UK, July 9-10, 2009 Proceedings

Editor: Jeremy T. Bradley

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

Table of Contents

Frontmatter
Tagged Generalized Stochastic Petri Nets
Abstract
This paper introduces an extension of the Generalized Stochastic Petri Net (GSPN) formalism in order to enable the computation of first passage time distributions of tokens. A “tagged token” technique is used which relies on net’s structural properties to guide the correct specification of this extension. The extended model is suited for an automatic translation into an ordinary GSPN that can be used for the first passage time analysis. Scheduling policies of tokens in places, that are neglected in ordinary GSPNs, become relevant in the Tagged Generalized Stochastic Petri Net (TGSPN) formalism and specific submodels are proposed which are then used during the translation from TGSPNs to ordinary GSPNs. A running example inspired by a Flexible Manufacturing application is used throughout the paper to introduce the different concepts and to provide evidence of the relevance of the results.
Gianfranco Balbo, Massimiliano De Pierro, Giuliana Franceschinis
Modelling Zoned RAID Systems Using Fork-Join Queueing Simulation
Abstract
RAID systems are ubiquitously deployed in storage environments, both as standalone storage solutions and as fundamental components of virtualised storage platforms. Accurate models of their performance are crucial to delivering storage infrastructures that meet given quality of service requirements. To this end, this paper presents a flexible fork-join queueing simulation model of RAID systems that are comprised of zoned disk drives and which operate under RAID levels 01 or 5. The simulator takes as input I/O workloads that are heterogeneous in terms of request size and that exhibit burstiness, and its primary output metric is I/O request response time distribution. We also study the effects of heavy workload, taking into account the request-reordering optimisations employed by modern disk drives. All simulation results are validated against device measurements.
Abigail S. Lebrecht, Nicholas J. Dingle, William J. Knottenbelt
Performance of Auctions and Sealed Bids
Abstract
We develop models of automated E-commerce techniques, which predict the economic outcomes of these decision mechanisms, including the price attained by a good and the resulting income per unit time, as a function of the rate at which bidders provide the bids and of the time taken by the seller to decide whether to accept a bid. This paper extends previous work in two main directions. Since automated E-commerce mechanisms are typically implemented in software residing on the Internet, this paper shows how network quality of service will impact the economic outcome of automated auctions. We also analyse sealed bids which can also be automated, but which differ significantly from auctions in the manner in which information is shared between the bidders and the the party that decides the outcome. The approach that we propose opens novel avenues of research that bring together traditional computer and system performance analysis and the economic analysis of Internet based trading methods.
Erol Gelenbe, László Györfi
Applying Symbolic Techniques to the Representation of Non-Markovian Models with Continuous PH Distributions
Abstract
Among the proposed techniques for the analysis of non-Markovian models the state space expansion approach showed great flexibility in terms of modelling capacities. The principal drawback is the explosion of the state space. An attempt to alleviate such problem has been made in [1] but the storing of the reachability graph of the untimed system, augmented with information about active but not enabled events, still remains a bottleneck. This paper suggests a method for storing such an augmented reachability graph by the use of a Multi-terminal Multi-valued Decision Diagram and few Kronecker matrices. All the needed information is collected by applying a Saturation based algorithm that represents the main contribution of the work. An estimation of the memory occupation is also reported.
Francesco Longo, Marco Scarpa
Mean Value Analysis for a Class of PEPA Models
Abstract
In this paper a class of closed queueing network is modelled in the Markovian process algebra PEPA and solved using the classical Mean Value Analysis (MVA). This approach is attractive as it negates the need to derive the entire state space, and so certain metrics from large models can be obtained with little computational effort. The class of model considered includes models which are not obviously classical closed queueing models. The approach is illustrated with three examples.
Nigel Thomas, Yishi Zhao
Automatic Generation of Performance Analysis Results: Requirements and Demonstration
Abstract
This paper presents a performance model interoperability framework that brings together performance model interchange formats and experiment specifications with the automatic generation of performance analysis results for presentation and publication. We define the Use Cases and requirements and survey output and results used in practice. We present the output specification, the issues in the output-to-results transformation, the results specification schema extension, and a prototype implementation. A proof of concept example demonstrates the framework.
Connie U. Smith, Catalina M. Lladó, Ramon Puigjaner
Analytical Model of Traffic Compression in the UMTS Network
Abstract
The paper presents a new simple analytical method for a determination of the blocking probability in a full-availability group carrying a mixture of different multi-rate traffic classes with the compression property. The proposed model can be directly used for modelling of the Iub interface in the UMTS network servicing the Release 99 and HSDPA traffic classes. The described model can be applied for the validation of the efficiency of the Iub interface measured by the blocking probability and the average carried traffic for particular traffic classes.
Maciej Stasiak, Janusz Wiewióra, Piotr Zwierzykowski, Damian Parniewicz
From DFTs to PEPA: A Model-to-Model Transformation
Abstract
One of the main attractions of the stochastic process algebra PEPA is its clear compositional structure which allows building a model from elements which reflect the composition of the system to model. Dynamic Fault Trees (DFTs) constitute a simple combinatorial formalism which allows capturing the dynamic behaviour of system failure mechanisms. The resulting model is a combination of component failure events which determines the failure of the complete system. In this paper, we propose to exploit the compositional feature of both PEPA and DFTs in order to develop an automatic translation of a DFT into a PEPA model.
Leïla Kloul
Passage-End Analysis
Abstract
Passage-end calculations are a new style of passage measurement for eXtended Stochastic Probes (XSP) [1] which add the ability to split the analysis into several cases depending on conditions which hold at the end of a passage. This makes it possible to separate successful responses to a request from negative responses, timeouts or other failures. This allows the expression of service level agreements such as: “At least 90 percent of all requests receive a response within 10 seconds and at least 60 percent of all such requests are successful.”
Allan Clark, Adam Duguid, Stephen Gilmore
Stochastic Monotonicity in Queueing Networks
Abstract
Stochastic monotonicity is one of the sufficient conditions for stochastic comparisons of Markov chains. On a partially ordered state space, several stochastic orderings can be defined by means of increasing sets. The most known is the strong stochastic (sample-path) ordering, but weaker orderings (weak and weak*) could be defined by restricting the considered increasing sets. When the strong ordering could not be defined, weaker orderings represent an alternative as they generate less constraints. Also, they may provide more accurate bounds.
The main goal of this paper is to provide an intuitive event formalism added to stochastic comparisons methods in order to prove the stochastic monotonicity for multidimensional Continuous Time Markov Chains (CTMC). We use the coupling by events for the strong monotonicity. For weaker monotonicity, we give a theorem based on generator inequalities using increasing sets. We prove this theorem, and we present the event formalism for the definition of the increasing sets. We apply our formalism on queueing networks, in order to establish monotonicity properties.
H. Castel-Taleb, N. Pekergin
Fast Generation of Scale Free Networks with Directed Arcs
Abstract
To evaluate peer-to-peer systems through discrete-event simulation, one needs to be able to generate sufficiently large networks of nodes that exhibit the desired properties, such as the scale-free nature of the connectivity graph. In applications such as the web of trust or analysis of hyperlink structures, the direction of the arcs between two nodes is relevant and one therefore generates directed graphs. In this paper we introduce a model to generate directed scale free graphs without multiple arcs between the same pair of nodes and loops. This model is based on existing models that allows multiple arcs and loops, but considerably more challenging to implement in an efficient manner. We therefore design and implement a set of algorithms and compare them with respect to CPU and memory use, in terms of both theoretical complexity analysis and experimental results. We will show through experiments that with the fastest algorithms networks with a million or more nodes can be generated in mere seconds.
Huqiu Zhang, Aad van Moorsel
A More Realistic Peer-to-Peer Grid Market Model
Abstract
In this paper we investigate the behaviour of a peer to peer driven Grid computing network. We present mean field approximation of the simulation model and show that it captures the essence of the model. In contrast to earlier work we limit the budget of the nodes and observe the consequences for the price development. We also show that the proposed peer to peer network scales much better than a central server approach. By allowing the agents in the simulation to hibernate and change the price individually only using local information the price development of the model becomes stable. Lastly we investigate the distribution of the times the agents wait to sell or buy resources.
Uli Harder, Fernando Martínez Ortuño
Migrating Auctioneers on Internet Auctions for Improved Utility and Performance
Abstract
The paper studies a technique to improve the utility and performance of an automated auction application where the auctioneer and bidders communicate through the Internet. The lack of quality-of-service guarantees from site to site can severely influence the results of an auction by affecting the seller’s income rate, auction fairness, and overall protocol efficiency. By properly identifying and migrating auctioneers to suitable hosts on the network, it is shown that the expected seller’s utility can be improved along with other metrics of interest. The paper proposes a scalable approach to conduct the host search on a large network by applying the Simulated Annealing metaheuristic in conjunction with network probing. A detailed simulation study assess the performance of the system and quantifies the benefits of the proposal.
Ricardo Lent
Analytical Model of the Soft Handoff Mechanism in the UMTS Network
Abstract
The paper proposes an analytical approach to blocking probability calculation in the UMTS network. In the proposed method, handoff connections are modelled on the basis of the fixed point methodology. The results of analytical calculation of the blocking probability in the group of cells carrying a mixture of different multi-rate traffic streams are compared with the results of simulation experiments, which confirms a good accuracy of the method. The described calculation scheme is applicable for cost-effective resource management in 3G mobile networks and can be easily applied to network capacity calculations.
Maciej Stasiak, Piotr Zwierzykowski, Damian Parniewicz
Analytical Model of TCP NewReno through a CTMC
Abstract
An analytical model of the Transmission Control Protocol (TCP) New Reno [7] performance through a Continuous-Time Markov Chain (CTMC) is presented and its theoretical predictions are corroborated by the well known network simulator ns-2 [15]. An existing TCP Reno model [6] is modified in order to characterise the NewReno algorithm. The NewReno version is modelled given its proven better performance over channels presenting high loss rates and its extensive deployment in current web servers [14].
Nimbe L. Ewald, Andrew H. Kemp
Packet Loss Analysis of Load-Balancing Switch with ON/OFF Input Processes
Abstract
Lately, the number of Internet users and, correspondingly, the amount of traversing traffic is growing extremely fast. In spite of the fact that transmission links – mostly optical fibres – have high capacity, the internet routers still remain a point of traffic bottleneck. The construction of highly scalable switches for high-speed transmission still remains a real challenge for designers. In this paper we focus our efforts on the analysis of Load-Balancing Birkhof-von Neumann switch which is lately considered to be a highly efficient distributed switch with simple control and high scalability. Due to the fact that Internet traffic represents an asynchronous traffic which supports a variety of applications, we have introduced the analysis of possible loss inside the load-balanced switch under consideration of variable size packets and finite central stage buffers previously in [1]. Although the analysis has showed some interesting features of the switch, it has exponential complexity of \(O\left(N^N\right)\) which makes that model inapplicable for the switches with large number of ports, N. The main goal of this paper is to approximate the switch analysis with lower complexity, i.e., \(O\left(2^N\right)\) which can be useful for evaluation of packet loss in the larger load-balanced switches.
Yury Audzevich, Levente Bodrog, Yoram Ofek, Miklós Telek
Approximate Analysis of a Round Robin Scheduling Scheme for Network Coding
Abstract
Network coding (NC) has been proposed as a way to compress flows of packets by combining different packets, provided that there is sufficient redundancy through multiple transmission paths so that the receiving nodes can then decode the flows to reconstruct all of the individual packets. However NC does introduce additional computational overhead, and also creates different additional delays which are the subject of this paper. In particular, we evaluate the queueing and delay performance of NC at intermediate nodes of a store and forward packet network when the cross-encoding of packets is restricted within disjoint subsets of the traffic streams so that packets from different subsets cannot be encoded together. We propose a round robin scheduling scheme for serving these disjoint subsets, and present a queueing model for a single encoding node that captures the effect of NC. The model is analyzed approximately using a decoupling approach, and can be used to predict the additional delays incurred by packets in nodes that use NC. The accuracy of the analytical solution is validated via simulations.
Omer H. Abdelrahman, Erol Gelenbe
Analysis of Large Populations of Interacting Objects with Mean Field and Markovian Agents
Abstract
The necessity of studying sensor networks, rich internet applications, social networks and molecular biology have raised the need of being able to consider systems composed by very large population of similar objects. This lead to the development of new modelling paradigms, such as Fluid Process Algebra, Mean Field analysis and Markovian Agents. These methodologies produces exact results if the number of considered objects goes to the infinity, but provide reasonable approximations even for finite quantities. In this work Mean Field analysis and Markovian Agents models will be presented.
Marco Gribaudo
Backmatter
Metadata
Title
Computer Performance Engineering
Editor
Jeremy T. Bradley
Copyright Year
2009
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-02924-0
Print ISBN
978-3-642-02923-3
DOI
https://doi.org/10.1007/978-3-642-02924-0