Reward model solution methods with impulse and rate rewards: an algorithm and numerical results

Reward models have become an important method for specifying performability models for many types of systems. Many methods have been proposed for solving reward models, but no method has proven itself to be applicable over all system classes and sizes. Furthermore, specification of reward models has usually been done at the state level, which can be extremely cumbersome for realistic models. We describe a method to specify reward models as stochastic activity networks (SANs) with impulse and rate rewards, and a method by which to solve these models via uniformization. The method is an extension of one proposed by de Souza e Silva and Gail in which impulse and rate rewards are specified at the SAN level, and solved in a single model. Furthermore, we propose a new technique for discarding paths in the uniformized process whose contribution to the reward variable is minimal, which greatly reduces the time and space required for a solution. A bound is calculated on the error introduced by this discarding, and its effectiveness is illustrated through the study of the performability and availability of a degradable multi-processor system.     

计算机系统与计算机网络中的动态优化:模型、求解与应用

动态优化是计算机系统与计算机网络中进行资源分配与任务调度等方面研究所采用的主要理论工具之一.目前,国内外已开展大量研究,致力于深化动态优化的理论研究与工程应用.文中从模型、求解与应用3个角度,对马尔可夫决策过程动态优化理论模型进行了综述,并重点介绍了将动态优化理论与随机Petri网理论相结合的马尔可夫决策Petri网和随机博弈网模型,详细讨论了这些模型的建模方法、求解算法与一些应用实例.最后,对全文进行了总结,并对未来可能的研究方向进行了展望.     

Lumping partially symmetrical stochastic models

The performance and dependability evaluation of complex systems by means of dynamic stochastic models (e.g. Markov chains) may be impaired by the combinatorial explosion of their state space. Among the possible methods to cope with this problem, symmetry-based ones can be applied to systems including several similar components. Often however these systems are only partially symmetric: their behavior is in general symmetric except for some local situation when the similar components need to be differentiated.In this paper two methods to efficiently analyze partially symmetrical models are presented in a general setting and the requirements for their efficient implementation are discussed. Some case studies are presented to show the methods’ effectiveness and their applicative interest.     

Queueing Petri nets with product form solution

The product form results recently published for stochastic Petri nets are combined with the well-known product form results for queueing networks in the model formalism of queueing Petri nets yielding the class of product form queueing Petri nets. This model class includes stochastic Petri nets with product form solution and BCMP queueing networks as special cases. We introduce an arrival theorem for the model class and present an exact aggregation approach extending known approaches from queueing networks.     

On Markov reward modelling with FSPNs

In this paper, fluid stochastic Petri nets (FSPNs) will be used for modelling reward in a performability model. Two variations of a known performability model are presented in order to demonstrate the ability of FSPNs in modelling accumulated rate reward as well as accumulated impulse reward. In the first model two fluid places are used, one of which represents the profit (reward) obtained by operating the system and the other one the buffer that is approximated continuously. In the second model only one fluid place is used, representing the costs (negative reward) arising due to repair of system components. The costs increase continuously at deterministic rate while the system is in state of repair (which is a rate reward in the model). Additional costs incur each time the buffer fails (which is an impulse reward in the model). With a numerical solution algorithm the distribution of the reward and its mean are computed. The accuracy of the numerical algorithm is studied by showing for the first model the impact of the choice of the discretization stepsizes on the obtained solution. Different boundary conditions are discussed for the second model.     

Markov regenerative stochastic Petri nets with general execution policies: supplementary variable analysis and a prototype tool

Stochastic Petri nets (SPNs) with general firing time distributions are considered. Generally timed transitions can have general execution policies: the preemption policy may be preemptive repeat different (prd) or preemptive resume (prs) and the firing time distribution can be marking-dependent. A stationary analysis method covering all possible combinations is presented by means of supplementary variables. The method is implemented in a prototype tool SPNica which is based on Mathematica. The use of the general execution policies is illustrated by a WWW server model.     

Fluid Stochastic Petri Nets Augmented with Flush-out Arcs: Modelling and Analysis

Fluid(or Hybrid) Petri Nets are Petri net based models with two classesof places: discrete places that carry a natural number of distinctobjects (tokens), and fluid places that hold a positive amountof fluid, represented by a real number. With respect to previousformulations, the FSPN model presented in this paper, is augmentedwith a new primitive, called flush-out arc. A flush-out arc connectsa fluid place to a timed transition, and has the effect of instantaneouslyemptying the fluid place when the transition fires. The paperdiscusses the modeling power of the augmented formalism, andshows how the dynamics of the underlying stochastic process canbe analytically described by a set of integro-differential equations.A procedure is presented to automatically derive the solutionequations from the model specifications. The whole methodologyis illustrated by means of various examples.     

时间约束Petri 网的可调度性分析方法研究

在系统地研究了时间约束Ｐｅｔｒｉ网的基础上,提出了一般的状态可达性分析方法。通过讨论任意拓扑结构ＴＣＰＮ′ｓ的可调度分析,克服了以往ＴＣＰＮ′ｓ可达性分析方法的局限性,显示了该方法的准确性和实用性。     

时间约束Petri网的状态可达及可调度分析算法

时间约束Petri网是具有广义时间约束的一类Petri网。时间约束的引入使TCPN’s的演化与系统每一时刻的状态密切相关,导致网的动态复杂性。目前有关TCPN’s状态可达性的研究仅局限于一些较简单的网,该文通过对TCPN’s的进一步研究,给出了更一般的可达性分析方法及变迁可调度决策算法,并讨论了含冲突结构的TCPN’s的可调度分析。     

Iterative analysis of Markov regenerative models

Conventional algorithms for the steady-state analysis of Markov regenerative models suffer from high computational costs which are caused by densely populated matrices. In this paper, a new algorithm is suggested which avoids computing these matrices explicitly. Instead, a two-stage iteration scheme is used. An extended version of uniformization is applied as a subalgorithm to compute the required transient quantities “on-the fly”. The algorithm is formulated in terms of stochastic Petri nets. A detailed example illustrates the proposed concepts.     

Specification techniques for Markov reward models

Markov reward models (MRMs) are commonly used for the performance, dependability, and performability analysis of computer and communication systems. Many papers have addressed solution techniques for MRMs. Far less attention has been paid to the specification of MRMs and the subsequent derivation of the underlying MRM. In this paper we only briefly address the mathematical aspects of MRMs. Instead, emphasis is put on specification techniques. In an application independent way, we distinguish seven classes of specification techniques: stochastic Petri nets, queuing networks, fault trees, production rule systems, communicating processes, specialized languages, and hybrid techniques. For these seven classes, we discuss the main principles, give examples and discuss software tools that support the use of these techniques. An overview like this has not been presented in the literature before. Finally, the paper addresses the generation of the underlying MRM from the high-level specification, and indicates important future research areas. This work was supported in part by the Naval Surface Warfare Center under contract N60921-92-C-0161 and by the National Science Foundation under grant CCR-9108114.     

A congruence relation for sPBC

In this paper we define a congruence relation for regular terms of sPBC (stochastic Petri Box Calculus), by means of which we identify those processes that have the same behaviour, not only in terms of the multiactions that they can perform, but also taking into account the stochastic information that they have associated. In order to define this equivalence relation we have to define an adequate semantics for the synchronization operator, as well as a new labelled transition system for regular terms of sPBC.     

客户机／服务器系统缓冲区容量的Petri网分析

本文在详细分析客户机／服务器架构的基础上,采用随机Petri网方法对客户机／服务器体系进行建模,着重就模型的缓冲区性能给出了相应的GSPN性能计算方法,并结合实例进行定性分析。     

基于Petri网的批处理调度研究

批处理过程存在于复杂的动态环境中,来自主客观的干扰及问题固有的易变性,会导致各种过程参数的变化,因此,需要研究对意外事件作出快速反应的动态调度方法,以捕捉生产环境的实时变化。该文针对批处理过程中最常出现的操作处理时间波动,提出了基于Petri网仿真技术的批处理过程动态调度方法。仿真结果表明,该方法能有效地改善调度性能,为批处理过程动态调度的研究提供了新思路。     

基于延迟特性的改进随机Petri网建模与分析

随机Petri网能够分析过程中的随机特性,但是不能有效地描述延迟和花费问题.为了解决上述问题,提出了一种基于延迟特性的随机Petri网模型.该模型能根据延迟时间和过程的随机性得到总的时间和花费特性.给出了状态类延迟时间和延迟花费的串联及并联化简方法.最后,通过首都机场的实例说明该方法能更好地表示出应急救援的时间和花费特性.     

Product-form and stochastic Petri nets: a structural approach

Stochastic Petri nets (SPNs) with product-form solution are nets for which there is an analytic expression of the steady-state probabilities with respect to place markings, as it is the case for product-form queueing networks with respect to queue lengths. The most general kind of SPNs with product-form solution introduced by Coleman et al. (and denoted here by -nets) suffers a serious drawback: the existence of such a solution depends on the values of the transition rates. Thus since their introduction, it is an open question to characterize -nets with product-form solution for any values of the rates. A partial characterization has been obtained by Henderson et al. However, this characterization does not hold for every initial marking and it is expressed in terms of the reachability graph. In this paper, we obtain a purely structural characterization of -nets for which a product-form solution exists for any value of probabilistic parameters of the SPN and for any initial marking. This structural characterization leads to the definition of -nets (Stochastic Parametric Product-form Petri nets). We also design a polynomial time (with respect to the size of the net structure) algorithm to check whether a SPN is a -net. Then, we study qualitative properties of -nets and -nets, the non-stochastic versions of -nets and -nets: we establish two results on the complexity bounds for the liveness and the reachability problems, which are central problems in Petri nets theory. This set of results complements previous studies on these classes of nets and improves the applicability of product-form solutions for SPNs.     

Performance modeling of IEEE 802.11 wireless LANs with stochastic Petri nets

In 1997, IEEE standardized the physical layers and the medium access for wireless local area networks. This paper presents a performance study of the distributed coordination function, the fundamental contention-based access mechanism. Most performance studies adopt unchecked simplifying assumptions or do not reveal all details of the simulation model. We develop a stochastic Petri net model, which captures all relevant system aspects in a concise way. Simulation allows to quantify the influence of many mandatory features of the standard on performance, especially the backoff procedure, extended interframe spaces, and the timing synchronization function. We identify conditions when simplifying assumptions commonly used in analytical modeling are justified. Applying these conditions, we derive a more compact and analytically tractable model from the detailed model.